0 PRELIMINARIES
0.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2 Ordered pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.3 Cartesian product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.4 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
0.5 Important types of binary relations . . . . . . . . . . . . . . . . . . . . . . . . 7
0.6 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
0.7 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.8 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1 INDUCTION 17
1.1 Fundamental properties of the natural numbers . . . . . . . . . . . . . . . . . 17
1.2 Mathematical induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3 Complete induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2 CORRECTNESS OF ITERATIVE AND RECURSIVE PROGRAMS 47
2.1 Program correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.2 Specification through preconditions and postconditions . . . . . . . . . . . . . 47
2.3 Correctness of binary search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.4 The correctness of a multiplication program . . . . . . . . . . . . . . . . . . . 54
2.5 A more interesting proof of termination . . . . . . . . . . . . . . . . . . . . . . 58
2.6 Comments on proving the correctness of iterative programs . . . . . . . . . . . 60
2.7 Proof of correctness of recursive programs . . . . . . . . . . . . . . . . . . . . 62
2.8 Correctness of a recursive sorting program . . . . . . . . . . . . . . . . . . . . 66

3 FUNCTIONS DEFINED BY INDUCTION 75
3.1 Recursively defined functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.2 Divide-and-conquer recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.3 Another recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

4 SETS DEFINED BY INDUCTION AND STRUCTURAL INDUCTION 97
4.1 Defining sets recursively . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.2 Structural induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.3 An alternative to structural induction proofs . . . . . . . . . . . . . . . . . . . 103
4.4 Elements of recursively defined sets as trees . . . . . . . . . . . . . . . . . . . 104
4.5 Inductive definition of binary trees . . . . . . . . . . . . . . . . . . . . . . . . 105

5 PROPOSITIONAL LOGIC 111
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.2 Formalising propositional reasoning . . . . . . . . . . . . . . . . . . . . . . . . 112
5.3 Truth tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.4 Tautologies and satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.5 Logical implication and logical equivalence . . . . . . . . . . . . . . . . . . . . 120
5.6 Some important logical equivalences . . . . . . . . . . . . . . . . . . . . . . . . 122
5.7 Conditional statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.8 Analysis of three proof techniques . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.9 Normal forms for propositional formulas . . . . . . . . . . . . . . . . . . . . . 128
5.10 Boolean functions and the design of digital circuits . . . . . . . . . . . . . . . 131
5.11 Complete sets of connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

6 PREDICATE LOGIC 143
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.2 The syntax of predicate logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.3 Semantics of predicate logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.4 Validity and satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6.5 Logical implication and logical equivalence . . . . . . . . . . . . . . . . . . . . 156
6.6 Some important logical equivalences . . . . . . . . . . . . . . . . . . . . . . . . 157
6.7 Predicate logic and relational databases . . . . . . . . . . . . . . . . . . . . . . 161
6.8 Logical implication revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
6.9 Prenex normal form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
6.10 Order of quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
6.11 Reference and its effect on meaning . . . . . . . . . . . . . . . . . . . . . . . . 175

7 FINITE STATE AUTOMATA AND REGULAR EXPRESSIONS 183
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.2 Regular expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
7.3 Deterministic finite state automata . . . . . . . . . . . . . . . . . . . . . . . . 199
7.4 Nondeterministic finite state automata . . . . . . . . . . . . . . . . . . . . . . 211
7.5 Closure properties of FSA-accepted languages . . . . . . . . . . . . . . . . . . 222
7.6 Equivalence of regular expressions and FSA . . . . . . . . . . . . . . . . . . . 225
7.7 Proving nonregularity: the Pumping Lemma . . . . . . . . . . . . . . . . . . . 234

8 CONTEXT-FREE GRAMMARS AND PUSHDOWN AUTOMATA 241
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
8.2 Context-free grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
8.3 CFG are more powerful than regular expressions . . . . . . . . . . . . . . . . . 246
8.4 Right-linear grammars and regular languages . . . . . . . . . . . . . . . . . . . 247
8.5 Pushdown automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
8.6 Equivalence of CFG and PDA . . . . . . . . . . . . . . . . . . . . . . . . . . . 254