Diskrete Mathematik (Discrete Mathematics)

Vorwort iii
1 Introduction and Motivation 1
1.1 Discrete Mathematics and Computer Science . . . . . . . . . . . . 1
1.2 Discrete Mathematics: A Selection of Teasers . . . . . . . . . . . . 2
1.3 Abstraction: Simplicity and Generality . . . . . . . . . . . . . . . . 4
1.4 Programs as Discrete Mathematical Objects . . . . . . . . . . . . . 6
2 Math. Reasoning, Proofs, and a First Approach to Logic 7
2.1 Mathematical Statements . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 The Concept of a Mathematical Statement . . . . . . . . . . 7
2.1.2 Composition of Mathematical Statements . . . . . . . . . . 8
2.2 The Concept of a Proof . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Examples of Proofs . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Two Meanings of the Symbol =⇒ . . . . . . . . . . . . . . . 10
2.2.3 Examples of False Proofs . . . . . . . . . . . . . . . . . . . 10
2.2.4 An Informal Understanding of the Proof Concept . . . . . 11
2.2.5 Informal vs. Formal Proofs . . . . . . . . . . . . . . . . . . 11
2.2.6 The Role of Logic . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 A First Introduction to Logic . . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 Logical Constants, Operators, and Formulas . . . . . . . . 13
2.3.2 Formulas as Functions . . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Logical Equivalence and some Basic Laws . . . . . . . . . 16
2.3.4 Logical Consequence (for Propositional Logic) . . . . . . . 17
2.3.5 Lifting Equivalences and Consequences to Formulas . . . 18
2.3.6 Tautologies and Satisfiability . . . . . . . . . . . . . . . . . 19
vii
2.3.7 Logical Circuits * . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Predicates and Quantifiers . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.1 Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.2 The Quantifiers ∃ and ∀ . . . . . . . . . . . . . . . . . . . . 21
2.4.3 Nested Quantifiers . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.4 Interpretation of Formulas . . . . . . . . . . . . . . . . . . . 23
2.4.5 Tautologies and Satisfiability . . . . . . . . . . . . . . . . . 23
2.4.6 Equivalence and Logical Consequence . . . . . . . . . . . . 24
2.4.7 Some Useful Rules . . . . . . . . . . . . . . . . . . . . . . . 24
2.5 Logical Formulas vs. Mathematical Statements . . . . . . . . . . . 25
2.5.1 Formulas that are Mathematical Statements . . . . . . . . . 25
2.5.2 Mathematical Statements about Formulas . . . . . . . . . . 26
2.6 Some Proof Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.6.1 Composition of Implications . . . . . . . . . . . . . . . . . 26
2.6.2 Direct Proof of an Implication . . . . . . . . . . . . . . . . . 27
2.6.3 Indirect Proof of an Implication . . . . . . . . . . . . . . . . 27
2.6.4 Modus Ponens . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6.5 Case Distinction . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6.6 Proofs by Contradiction . . . . . . . . . . . . . . . . . . . . 29
2.6.7 Existence Proofs . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6.8 Existence Proofs via the Pigeonhole Principle . . . . . . . . 32
2.6.9 Proofs by Counterexample . . . . . . . . . . . . . . . . . . 33
2.6.10 Proofs by Induction . . . . . . . . . . . . . . . . . . . . . . 34
3 Sets, Relations, and Functions 36
3.1 Sets and Operations on Sets . . . . . . . . . . . . . . . . . . . . . . 36
3.1.1 The Set Concept . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.2 Set Description . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.3 Set Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.4 Sets as Elements . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.5 Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.6 The Empty Set . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.7 Constructing Sets from the Empty Set . . . . . . . . . . . . 41
3.1.8 A Construction of the Natural Numbers . . . . . . . . . . . 41
3.1.9 The Power Set . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.10 Union, Intersection, Difference, and Complement . . . . . 42
3.1.11 The Cartesian Product . . . . . . . . . . . . . . . . . . . . . 44
3.1.12 Russell’s Paradox . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.1 The Relation Concept . . . . . . . . . . . . . . . . . . . . . 46
3.2.2 Representations of Relations . . . . . . . . . . . . . . . . . 47
3.2.3 Set Operations on Relations . . . . . . . . . . . . . . . . . . 47
3.2.4 The Inverse of a Relation . . . . . . . . . . . . . . . . . . . . 48
3.2.5 Composition of Relations . . . . . . . . . . . . . . . . . . . 48
3.2.6 Special Properties of Relations . . . . . . . . . . . . . . . . 50
3.2.7 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . 51
3.3 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.1 Definition of Equivalence Relations . . . . . . . . . . . . . 52
3.3.2 Equivalence Classes Form a Partition . . . . . . . . . . . . 52
3.3.3 Example: Definition of the Rational Numbers . . . . . . . 53
3.4 Partial Order Relations . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.2 Hasse Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.3 Combinations of Posets and the Lexicographic Order . . . 57
3.4.4 Special Elements in Posets . . . . . . . . . . . . . . . . . . . 57
3.4.5 Meet, Join, and Lattices . . . . . . . . . . . . . . . . . . . . 59
3.5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5.1 The Function Concept . . . . . . . . . . . . . . . . . . . . . 59
3.5.2 Properties of Functions and Function Composition . . . . 61
3.6 Countable and Uncountable Sets . . . . . . . . . . . . . . . . . . . 61
3.6.1 Countability of Sets . . . . . . . . . . . . . . . . . . . . . . . 61
3.6.2 Between Finite and Countably Infinite . . . . . . . . . . . . 62
3.6.3 Important Countable Sets . . . . . . . . . . . . . . . . . . . 63
3.6.4 Uncountability of {0,1} ∞ . . . . . . . . . . . . . . . . . . . 64
3.6.5 Existence of Uncomputable Functions . . . . . . . . . . . . 65
4 Number Theory 67
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.1.1 Number Theory as a Mathematical Discipline . . . . . . . 67
4.1.2 What are the Integers? . . . . . . . . . . . . . . . . . . . . . 68
4.2 Divisors and Division . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.1 Division with Remainders . . . . . . . . . . . . . . . . . . . 69
ix
4.2.2 Greatest Common Divisors . . . . . . . . . . . . . . . . . . 70
4.3 Factorization into Primes . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.1 The Fundamental Theorem of Arithmetic * . . . . . . . . . 72
4.3.2 Irrationality of Roots . . . . . . . . . . . . . . . . . . . . . . 74
4.3.3 A Digression to Music Theory * . . . . . . . . . . . . . . . . 75
4.3.4 Least Common Multiples . . . . . . . . . . . . . . . . . . . 75
4.4 Some Basic Facts About Primes * . . . . . . . . . . . . . . . . . . . 76
4.4.1 The Density of Primes . . . . . . . . . . . . . . . . . . . . . 76
4.4.2 Remarks on Primality Testing . . . . . . . . . . . . . . . . . 77
4.5 Congruences and Modular Arithmetic . . . . . . . . . . . . . . . . 78
4.5.1 Modular Congruences . . . . . . . . . . . . . . . . . . . . . 78
4.5.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . 79
4.5.3 Multiplicative Inverses . . . . . . . . . . . . . . . . . . . . . 81
4.5.4 The Chinese Remainder Theorem . . . . . . . . . . . . . . 81
4.6 Application: Diffie-Hellman Key-Agreement . . . . . . . . . . . . 83
5 Algebra 86
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.1.1 What Algebra is About . . . . . . . . . . . . . . . . . . . . . 86
5.1.2 Algebraic Systems . . . . . . . . . . . . . . . . . . . . . . . 86
5.1.3 Some Examples of Algebras . . . . . . . . . . . . . . . . . . 87
5.2 Monoids and Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2.1 Neutral Elements . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2.2 Associativity and Monoids . . . . . . . . . . . . . . . . . . 88
5.2.3 Inverses and Groups . . . . . . . . . . . . . . . . . . . . . . 89
5.2.4 (Non-)minimality of the Group Axioms . . . . . . . . . . . 90
5.2.5 Some Examples of Groups . . . . . . . . . . . . . . . . . . . 91
5.3 The Structure of Groups . . . . . . . . . . . . . . . . . . . . . . . . 92
5.3.1 Direct Products of Groups . . . . . . . . . . . . . . . . . . . 92
5.3.2 Group Homomorphisms . . . . . . . . . . . . . . . . . . . . 92
5.3.3 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3.4 The Order of Group Elements and of a Group . . . . . . . 94
5.3.5 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.3.6 Application: Diffie-Hellman for General Groups . . . . . 96
5.3.7 The Order of Subgroups . . . . . . . . . . . . . . . . . . . . 96
5.3.8 The Group Z ∗
m and Euler’s Function . . . . . . . . . . . . .
97
5.4 Application: RSA Public-Key Encryption . . . . . . . . . . . . . . 99
5.4.1 e-th Roots in a Group . . . . . . . . . . . . . . . . . . . . . . 100
5.4.2 Description of RSA . . . . . . . . . . . . . . . . . . . . . . . 100
5.4.3 On the Security of RSA * . . . . . . . . . . . . . . . . . . . . 102
5.4.4 Digital Signatures * . . . . . . . . . . . . . . . . . . . . . . . 102
5.5 Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.5.1 Definition of a Ring . . . . . . . . . . . . . . . . . . . . . . . 103
5.5.2 Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.5.3 Units, Zerodivisors, and Integral Domains . . . . . . . . . 105
5.5.4 Polynomial Rings . . . . . . . . . . . . . . . . . . . . . . . . 106
5.5.5 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.6 Polynomials over a Field . . . . . . . . . . . . . . . . . . . . . . . . 110
5.6.1 Factorization and Irreducible Polynomials . . . . . . . . . 110
5.6.2 The Division Property in F[x] . . . . . . . . . . . . . . . . . 112
5.6.3 Analogies Between Z and F[x], Euclidean Domains * . . . 113
5.7 Polynomials as Functions . . . . . . . . . . . . . . . . . . . . . . . 114
5.7.1 Polynomial Evaluation . . . . . . . . . . . . . . . . . . . . . 114
5.7.2 Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.7.3 Polynomial Interpolation . . . . . . . . . . . . . . . . . . . 115
5.8 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.8.1 The Ring F[x] m(x) . . . . . . . . . . . . . . . . . . . . . . . 116
5.8.2 Constructing Extension Fields . . . . . . . . . . . . . . . . 118
5.8.3 Some Facts About Finite Fields * . . . . . . . . . . . . . . . 120
5.9 Application: Error-Correcting Codes . . . . . . . . . . . . . . . . . 121
5.9.1 Definition of Error-Correcting Codes . . . . . . . . . . . . . 121
5.9.2 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.9.3 Codes based on Polynomial Evaluation . . . . . . . . . . . 123
6 Logic 125
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2 Proof Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
6.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
6.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.2.4 Proof Systems in Theoretical Computer Science * . . . . . . 131
6.3 Elementary General Concepts in Logic . . . . . . . . . . . . . . . . 131
xi
xii
6.3.1 The General Goal of Logic . . . . . . . . . . . . . . . . . . . 131
6.3.2 Syntax, Semantics, Interpretation, Model . . . . . . . . . . 132
6.3.3 Satisfiability, Tautology, Consequence, Equivalence . . . . 133
6.3.4 The Logical Operators ∧, ∨, and ¬ . . . . . . . . . . . . . . 134
6.3.5 Logical Consequence vs. Unsatisfiability . . . . . . . . . . 135
6.3.6 Theorems and Theories . . . . . . . . . . . . . . . . . . . . 136
6.4 Logical Calculi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.4.2 Hilbert-Style Calculi . . . . . . . . . . . . . . . . . . . . . . 137
6.4.3 Soundness and Completeness of a Calculus . . . . . . . . . 139
6.4.4 Derivations from Assumptions . . . . . . . . . . . . . . . . 140
6.4.5 Connection to Proof Systems . . . . . . . . . . . . . . . . . 140
6.5 Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.5.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.5.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.5.3 Brief Discussion of General Logic Concepts . . . . . . . . . 141
6.5.4 Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.5.5 Some Derivation Rules . . . . . . . . . . . . . . . . . . . . . 144
6.5.6 The Resolution Calculus for Propositional Logic . . . . . . 145
6.6 Predicate Logic (First-order Logic) . . . . . . . . . . . . . . . . . . 149
6.6.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.6.2 Free Variables and Variable Substitution . . . . . . . . . . . 149
6.6.3 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.6.4 Predicate Logic with Equality . . . . . . . . . . . . . . . . . 152
6.6.5 Some Basic Equivalences Involving Quantifiers . . . . . . 152
6.6.6 Substitution of Bound Variables . . . . . . . . . . . . . . . 153
6.6.7 Universal Instantiation . . . . . . . . . . . . . . . . . . . . . 154
6.6.8 Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.6.9 An Example Theorem and its Interpretations . . . . . . . . 155
6.7 Beyond Predicate Logic * . . . . . . . . . . . . . . . . . . . . . . . . 158