Logic and Discrete Mathematics

Chapter 1: Preliminaries

• • 1.1 Sets
• • 1.1.1 Exercises
• • 1.2 Basics of logical connectives and expressions
• • 1.2.1 Propositions, logical connectives, truth tables, tautologies
• • 1.2.2 Individual variables and quantifiers
• • 1.2.3 Exercises
• • 1.3 Mathematical induction
• • 1.3.1 Exercises

Chapter 2: Sets, Relations, Orders

• • 2.1 Set inclusions and equalities
• • 2.1.1 Properties of the set theoretic operations
• • 2.1.2 Exercises
• • 2.2 Functions
• • 2.2.1 Functions and their inverses
• • 2.2.2 Composition of mappings
• • 2.2.3 Exercises
• • 2.3 Binary relations and operations on them
• • 2.3.1 Binary relations
• • 2.3.2 Matrix and graphical representations of relations on finite sets
• • 2.3.3 Boolean operations on binary relations
• • 2.3.4 Inverse and composition of relations
• • 2.3.5 Exercises
• • 2.4 Special binary relations
• • 2.4.1 Properties of binary relations
• • 2.4.2 Functions as relations
• • 2.4.3 Reflexive, symmetric and transitive closures of a relation
• • 2.4.4 Exercises
• • 2.5 Equivalence relations and partitions
• • 2.5.1 Equivalence relations
• • 2.5.2 Quotient sets and partitions
• • 2.5.3 The kernel equivalence of a mapping
• • 2.5.4 Exercises
• • 2.6 Ordered sets
• • 2.6.1 Pre-orders and partial orders
• • 2.6.2 Graphical representing posets: Hasse diagrams
• • 2.6.3 Lower and upper bounds. Minimal and maximal elements
• • 2.6.4 Well-ordered sets
• • 2.6.5 Exercises
• • 2.7 An introduction to cardinality
• • 2.7.1 Equinumerosity and cardinality
• • 2.7.2 Exercises
• • 2.8 Isomorphisms of ordered sets. Ordinal numbers
• • 2.8.1 Exercises
• • 2.9 Application: relational databases
• • 2.9.1 Exercises

Chapter 3: Propositional Logic

• • 3.1 Propositions, logical connectives, truth tables, tautologies
• • 3.1.1 Propositions and propositional connectives. Truth tables
• • 3.1.2 Some remarks on the meaning of the connectives
• • 3.1.3 Propositional formulae
• • 3.1.4 Construction and parsing tree of a propositional formula
• • 3.1.5 Truth tables of propositional formulae
• • 3.1.6 Tautologies
• • 3.1.7 A better idea: search for a falsifying truth assignment
• • 3.1.8 Exercises
• • 3.2 Propositional logical consequence. Valid and invalid propositional inferences
• • 3.2.1 Propositional logical consequence
• • 3.2.2 Logically sound rules of propositional inference. Logically correct propositional arguments
• • 3.2.3 Fallacies of the implication
• • 3.2.4 Exercises
• • 3.3 The concept and use of deductive systems
• • 3.4 Semantic tableaux
• • 3.4.1 Exercises
• • 3.5 Logical equivalences. Negating propositional formulae
• • 3.5.1 Logically equivalent propositional formulae
• • 3.5.2 Some important equivalences
• • 3.5.3 Exercises
• • 3.6 Normal forms. Propositional resolution
• • 3.6.1 Conjunctive and disjunctive normal forms of propositional formulae
• • 3.6.2 Clausal form. Clausal resolution
• • 3.6.3 Resolution-based derivations
• • 3.6.4 Optimizing the method of resolution
• • 3.6.5 Exercises

Chapter 4: First-Order Logic

• • 4.1 Basic concepts of first-order logic
• • 4.1.1 First-order structures
• • 4.1.2 First-order languages
• • 4.1.3 Terms and formulae
• • 4.1.4 The semantics of first-order logic: an informal outline
• • 4.1.5 Translating first-order formulae to natural language
• • 4.1.6 Exercises
• • 4.2 The formal semantics of first–order logic
• • 4.2.1 Interpretations
• • 4.2.2 Variable assignment and term evaluation
• • 4.2.3 Truth evaluation games
• • 4.2.4 Exercises
• • 4.3 The language of first-order logic: a deeper look
• • 4.3.1 Translations from natural language into first-order languages
• • 4.3.2 Restricted quantification
• • 4.3.3 Free and bound variables. Scope of a quantifier
• • 4.3.4 Renaming of a bound variable in a formula. Clean formulae
• • 4.3.5 Substitution of a term for a variable in a formula. Capture of a variable
• • 4.3.6 Exercises
• • 4.4 Truth, logical validity, equivalence and consequence in first-order logic
• • 4.4.1 More on truth of sentences in structures. Models and countermodels
• • 4.4.2 Satisfiability and validity of first-order formulae
• • 4.4.3 Logical equivalence in first-order logic
• • 4.4.4 Some logical equivalences involving quantifiers
• • 4.4.5 Negating first-order formulae
• • 4.4.6 Logical consequence in first-order logic
• • 4.4.7 Exercises
• • 4.5 Semantic tableaux for first-order logic
• • 4.5.1 Some derivations using first-order semantic tableau
• • 4.5.2 Semantic tableaux for first-order logic with equality
• • 4.5.3 Discussion on the quantifier rules and on termination of semantic tableaux
• • 4.5.4 Exercises
• • 4.6 Prenex and clausal normal forms
• • 4.6.1 Prenex normal forms
• • 4.6.2 Skolemization
• • 4.6.3 Clausal forms
• • 4.6.4 Exercises
• • 4.7 Resolution in first-order logic
• • 4.7.1 Propositional resolution rule in first-order logic
• • 4.7.2 Substitutions of terms for variables revisited
• • 4.7.3 Unification of terms
• • 4.7.4 Resolution with unification in first-order logic
• • 4.7.5 Examples of resolution-based derivations
• • 4.7.6 Resolution for first-order logic with equality
• • 4.7.7 Optimizations of the resolution method for first-order logic
• • 4.7.8 Exercises
• • 4.8 Applications of first-order logic to mathematical reasoning and proofs
• • 4.8.1 Proof strategies: direct and indirect proofs
• • 4.8.2 Tactics for logical reasoning
• • 4.8.3 Exercises

Chapter 5: Number Theory

• • 5.1 The principle of mathematical induction revisited
• • 5.1.1 Exercises
• • 5.2 Divisibility
• • 5.2.1 Basic properties of divisibility
• • 5.2.2 Division with a remainder
• • 5.2.3 Greatest common divisor
• • 5.2.4 Exercises
• • 5.3 Computing greatest common divisors. Least common multiples
• • 5.3.1 Euclid’s algorithm for computing greatest common divisors
• • 5.3.2 Least common multiple
• • 5.3.3 Exercises
• • 5.4 Prime numbers. The fundamental theorem of arithmetic
• • 5.4.1 Relatively prime numbers
• • 5.4.2 Prime numbers
• • 5.4.3 The fundamental theorem of arithmetic
• • 5.4.4 On the distribution of prime numbers
• • 5.4.5 Exercises
• • 5.5 Congruence relations
• • 5.5.1 Exercises
• • 5.6 Equivalence classes and residue systems modulo n
• • 5.6.1 Equivalence relations and partitions
• • 5.6.2 Equivalence classes modulo n. Modular arithmetic
• • 5.6.3 Residue systems
• • 5.6.4 Multiplicative inverses in ℤn
• • 5.6.5 Exercises
• • 5.7 Linear Diophantine equations and linear congruences
• • 5.7.1 Linear Diophantine equations
• • 5.7.2 Linear congruences
• • 5.7.3 Exercises
• • 5.8 Chinese remainder theorem
• • 5.8.1 Exercises
• • 5.9 Euler’s function. Theorems of Euler and Fermat
• • 5.9.1 Theorems of Euler and Fermat
• • 5.9.2 Exercises
• • 5.10 Wilson’s theorem. Order of an integer
• • 5.10.1 Wilson’s theorem
• • 5.10.2 Order of an integer
• • 5.10.3 Exercises
• • 5.11 Application: public key cryptography
• • 5.11.1 About cryptography
• • 5.11.2 The idea of public key cryptography
• • 5.11.3 The method RSA
• • 5.11.4 Exercises

Chapter 6: Combinatorics

• • 6.1 Two basic counting principles
• • 6.1.1 Exercises
• • 6.2 Combinations. The binomial theorem
• • 6.2.1 Counting sheep and combinations
• • 6.2.2 Some important properties
• • 6.2.3 Pascal’s triangle
• • 6.2.4 The binomial theorem
• • 6.2.5 Exercises
• • 6.3 The principle of inclusion–exclusion
• • 6.3.1 Exercises
• • 6.4 The Pigeonhole Principle
• • 6.4.3 Exercises
• • 6.5 Generalized permutations, distributions and the multinomial theorem
• • 6.5.1 Arranging nondistinct objects
• • 6.5.2 Distributions
• • 6.5.3 The multinomial theorem
• • 6.5.4 Summary
• • 6.5.5 Exercises
• • 6.6 Selections and arrangements with repetition; distributions of identical objects
• • 6.6.1 Selections with repetition
• • 6.6.2 Distributions of identical objects
• • 6.6.3 Arrangements with repetition
• • 6.6.4 Summary
• • 6.6.5 Exercises
• • 6.7 Recurrence relations and their solution
• • 6.7.1 Recurrence relations. Fibonacci numbers
• • 6.7.2 Catalan numbers
• • 6.7.3 Solving homogeneous linear recurrence relations
• • 6.7.4 Exercises
• • 6.8 Generating functions
• • 6.8.1 Introducing generating functions
• • 6.8.2 Computing coefficients of generating functions
• • 6.8.3 Exercises
• • 6.9 Recurrence relations and generating functions
• • 6.9.1 Exercises
• • 6.10 Application: classical discrete probability
• • 6.10.1 Common sense probability
• • 6.10.2 Sample spaces
• • 6.10.3 Discrete probability
• • 6.10.4 Properties of probability measures
• • 6.10.5 Conditional probability and independent events
• • 6.10.6 Exercises

Chapter 7: Graph Theory

• • 7.1 Introduction to graphs and digraphs
• • 7.1.1 Graphs
• • 7.1.2 Digraphs
• • 7.1.3 Exercises
• • 7.2 Incidence and adjacency matrices
• • 7.2.1 Exercises
• • 7.3 Weighted graphs and path algorithms
• • 7.3.1 Dijkstra’s algorithm
• • 7.3.2 The Floyd–Warshall algorithm
• • 7.3.3 Exercises
• • 7.4 Trees
• • 7.4.1 Undirected trees
• • 7.4.2 Computing spanning trees: Kruskal’s algorithm
• • 7.4.3 Rooted trees
• • 7.4.4 Traversing rooted trees
• • 7.4.5 Exercises
• • 7.5 Eulerian graphs and Hamiltonian graphs
• • 7.5.1 Eulerian graphs and digraphs
• • 7.5.2 Hamiltonian graphs and digraphs
• • 7.5.3 Exercises
• • 7.6 Planar graphs
• • 7.6.1 Exercises
• • 7.7 Graph colourings
• • 7.7.1 Colourings
• • 7.7.2 The four- and five-colour theorems
• • 7.7.3 Exercises