Logic and Discrete Mathematics

Willem Conradie, University of Johannesburg, South Africa.Valentin Goranko, University of Stockholm, Sweden.

• List of Boxes xiiiPreface xviiAcknowledgements xxiAbout the Companion Website xxiii1. Preliminaries 11.1 Sets 21.1.1 Exercises 71.2 Basics of logical connectives and expressions 91.2.1 Propositions, logical connectives, truth tables, tautologies 91.2.2 Individual variables and quantifiers 121.2.3 Exercises 151.3 Mathematical induction 171.3.1 Exercises 182. Sets, Relations, Orders 202.1 Set inclusions and equalities 212.1.1 Properties of the set theoretic operations 222.1.2 Exercises 262.2 Functions 282.2.1 Functions and their inverses 282.2.2 Composition of mappings 312.2.3 Exercises 332.3 Binary relations and operations on them 352.3.1 Binary relations 352.3.2 Matrix and graphical representations of relations on finite sets 382.3.3 Boolean operations on binary relations 392.3.4 Inverse and composition of relations 412.3.5 Exercises 422.4 Special binary relations 452.4.1 Properties of binary relations 452.4.2 Functions as relations 472.4.3 Reflexive, symmetric and transitive closures of a relation 472.4.4 Exercises 492.5 Equivalence relations and partitions 512.5.1 Equivalence relations 512.5.2 Quotient sets and partitions 532.5.3 The kernel equivalence of a mapping 562.5.4 Exercises 572.6 Ordered sets 592.6.1 Pre-orders and partial orders 592.6.2 Graphical representing posets: Hasse diagrams 612.6.3 Lower and upper bounds. Minimal and maximal elements 632.6.4 Well-ordered sets 652.6.5 Exercises 672.7 An introduction to cardinality 692.7.1 Equinumerosity and cardinality 692.7.2 Exercises 732.8 Isomorphisms of ordered sets. Ordinal numbers 752.8.1 Exercises 792.9 Application: relational databases 802.9.1 Exercises 863. Propositional Logic 893.1 Propositions, logical connectives, truth tables, tautologies 903.1.1 Propositions and propositional connectives. Truth tables 903.1.2 Some remarks on the meaning of the connectives 903.1.3 Propositional formulae 913.1.4 Construction and parsing tree of a propositional formula 923.1.5 Truth tables of propositional formulae 933.1.6 Tautologies 953.1.7 A better idea: search for a falsifying truth assignment 963.1.8 Exercises 973.2 Propositional logical consequence. Valid and invalid propositional inferences 1013.2.1 Propositional logical consequence 1013.2.2 Logically sound rules of propositional inference. Logically correct propositional arguments 1043.2.3 Fallacies of the implication 1063.2.4 Exercises 1073.3 The concept and use of deductive systems 1093.4 Semantic tableaux 1133.4.1 Exercises 1173.5 Logical equivalences. Negating propositional formulae 1213.5.1 Logically equivalent propositional formulae 1213.5.2 Some important equivalences 1233.5.3 Exercises 1243.6 Normal forms. Propositional resolution 1263.6.1 Conjunctive and disjunctive normal forms of propositional formulae 1263.6.2 Clausal form. Clausal resolution 1293.6.3 Resolution-based derivations 1303.6.4 Optimizing the method of resolution 1313.6.5 Exercises 1324. First-Order Logic 1354.1 Basic concepts of first-order logic 1364.1.1 First-order structures 1364.1.2 First-order languages 1384.1.3 Terms and formulae 1394.1.4 The semantics of first-order logic: an informal outline 1434.1.5 Translating first-order formulae to natural language 1464.1.6 Exercises 1474.2 The formal semantics of first–order logic 1524.2.1 Interpretations 1524.2.2 Variable assignment and term evaluation 1534.2.3 Truth evaluation games 1564.2.4 Exercises 1594.3 The language of first-order logic: a deeper look 1614.3.1 Translations from natural language into first-order languages 1614.3.2 Restricted quantification 1634.3.3 Free and bound variables. Scope of a quantifier 1644.3.4 Renaming of a bound variable in a formula. Clean formulae 1654.3.5 Substitution of a term for a variable in a formula. Capture of a variable 1664.3.6 Exercises 1674.4 Truth, logical validity, equivalence and consequence in first-order logic 1714.4.1 More on truth of sentences in structures. Models and countermodels 1714.4.2 Satisfiability and validity of first-order formulae 1724.4.3 Logical equivalence in first-order logic 1734.4.4 Some logical equivalences involving quantifiers 1744.4.5 Negating first-order formulae 1754.4.6 Logical consequence in first-order logic 1764.4.7 Exercises 1804.5 Semantic tableaux for first-order logic 1854.5.1 Some derivations using first-order semantic tableau 1864.5.2 Semantic tableaux for first-order logic with equality 1894.5.3 Discussion on the quantifier rules and on termination of semantic tableaux 1894.5.4 Exercises 1914.6 Prenex and clausal normal forms 1954.6.1 Prenex normal forms 1954.6.2 Skolemization 1974.6.3 Clausal forms 1984.6.4 Exercises 1994.7 Resolution in first-order logic 2014.7.1 Propositional resolution rule in first-order logic 2014.7.2 Substitutions of terms for variables revisited 2014.7.3 Unification of terms 2024.7.4 Resolution with unification in first-order logic 2044.7.5 Examples of resolution-based derivations 2054.7.6 Resolution for first-order logic with equality 2074.7.7 Optimizations of the resolution method for first-order logic 2074.7.8 Exercises 2074.8 Applications of first-order logic to mathematical reasoning and proofs 2114.8.1 Proof strategies: direct and indirect proofs 2114.8.2 Tactics for logical reasoning 2154.8.3 Exercises 2165. Number Theory 2195.1 The principle of mathematical induction revisited 2205.1.1 Exercises 2225.2 Divisibility 2245.2.1 Basic properties of divisibility 2245.2.2 Division with a remainder 2245.2.3 Greatest common divisor 2255.2.4 Exercises 2275.3 Computing greatest common divisors. Least common multiples 2305.3.1 Euclid’s algorithm for computing greatest common divisors 2305.3.2 Least common multiple 2325.3.3 Exercises 2335.4 Prime numbers. The fundamental theorem of arithmetic 2365.4.1 Relatively prime numbers 2365.4.2 Prime numbers 2375.4.3 The fundamental theorem of arithmetic 2385.4.4 On the distribution of prime numbers 2395.4.5 Exercises 2405.5 Congruence relations 2435.5.1 Exercises 2465.6 Equivalence classes and residue systems modulo n 2485.6.1 Equivalence relations and partitions 2485.6.2 Equivalence classes modulo n. Modular arithmetic 2495.6.3 Residue systems 2505.6.4 Multiplicative inverses in ℤn 2515.6.5 Exercises 2515.7 Linear Diophantine equations and linear congruences 2535.7.1 Linear Diophantine equations 2535.7.2 Linear congruences 2545.7.3 Exercises 2565.8 Chinese remainder theorem 2575.8.1 Exercises 2595.9 Euler’s function. Theorems of Euler and Fermat 2615.9.1 Theorems of Euler and Fermat 2625.9.2 Exercises 2645.10 Wilson’s theorem. Order of an integer 2665.10.1 Wilson’s theorem 2665.10.2 Order of an integer 2665.10.3 Exercises 2675.11 Application: public key cryptography 2695.11.1 About cryptography 2695.11.2 The idea of public key cryptography 2695.11.3 The method RSA 2705.11.4 Exercises 2716. Combinatorics 2746.1 Two basic counting principles 2756.1.1 Exercises 2816.2 Combinations. The binomial theorem 2846.2.1 Counting sheep and combinations 2846.2.2 Some important properties 2866.2.3 Pascal’s triangle 2876.2.4 The binomial theorem 2876.2.5 Exercises 2896.3 The principle of inclusion–exclusion 2936.3.1 Exercises 2966.4 The Pigeonhole Principle 2996.4.3 Exercises 3026.5 Generalized permutations, distributions and the multinomial theorem 3046.5.1 Arranging nondistinct objects 3046.5.2 Distributions 3066.5.3 The multinomial theorem 3086.5.4 Summary 3106.5.5 Exercises 3116.6 Selections and arrangements with repetition; distributions of identical objects 3126.6.1 Selections with repetition 3126.6.2 Distributions of identical objects 3146.6.3 Arrangements with repetition 3156.6.4 Summary 3166.6.5 Exercises 3166.7 Recurrence relations and their solution 3186.7.1 Recurrence relations. Fibonacci numbers 3186.7.2 Catalan numbers 3196.7.3 Solving homogeneous linear recurrence relations 3226.7.4 Exercises 3276.8 Generating functions 3296.8.1 Introducing generating functions 3296.8.2 Computing coefficients of generating functions 3326.8.3 Exercises 3356.9 Recurrence relations and generating functions 3376.9.1 Exercises 3416.10 Application: classical discrete probability 3436.10.1 Common sense probability 3436.10.2 Sample spaces 3436.10.3 Discrete probability 3456.10.4 Properties of probability measures 3466.10.5 Conditional probability and independent events 3486.10.6 Exercises 3527. Graph Theory 3567.1 Introduction to graphs and digraphs 3577.1.1 Graphs 3577.1.2 Digraphs 3647.1.3 Exercises 3677.2 Incidence and adjacency matrices 3707.2.1 Exercises 3747.3 Weighted graphs and path algorithms 3777.3.1 Dijkstra’s algorithm 3787.3.2 The Floyd–Warshall algorithm 3817.3.3 Exercises 3837.4 Trees 3857.4.1 Undirected trees 3857.4.2 Computing spanning trees: Kruskal’s algorithm 3887.4.3 Rooted trees 3907.4.4 Traversing rooted trees 3927.4.5 Exercises 3937.5 Eulerian graphs and Hamiltonian graphs 3957.5.1 Eulerian graphs and digraphs 3967.5.2 Hamiltonian graphs and digraphs 3987.5.3 Exercises 4007.6 Planar graphs 4047.6.1 Exercises 4087.7 Graph colourings 4117.7.1 Colourings 4117.7.2 The four- and five-colour theorems 4137.7.3 Exercises 414Index 419

"This is a very well-written brief introduction to discrete mathematics that emphasizes logic and set theory and has shorter sections on number theory, combinatorics, and graph theory." (MAA Reviews, 4 January 2016)