Diskrete Mathematik (Discrete Mathematics)

Description

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