Diskrete Mathematik - ETH Zürich Herbstsemester 2024 - PDF

ETH Zürich Departement Informatik Diskrete Mathematik Ueli Maurer Herbstsemester 2024 Vorwort Viele Disziplinen der Wissenschaft, insbesondere der Natur- und Ingenieurwis- senschaften, beruhen in einer zentralen Weise auf der Mathematik. Einerseits erlaubt die Mathematik, Sachverhalte zu modellieren und damit den Diskurs von einer intuitiven auf eine präzise und formale Stufe zu heben. Andererseits erlaubt die Mathematik, wenn Sachverhalte einmal präzise modelliert sind (z.B. die Statik als Teil der Physik), konkrete Probleme zu lösen (z.B. eine Brücke zu dimensionieren). Welche mathematischen Disziplinen sind für die Computerwissenschaften (Informatik, Computer Science) speziell relevant? Was muss in der Informa- tik modelliert werden? Welche Art von Problemen möchte man verstehen und lösen können? Der gemeinsame Nenner der vielen möglichen Antworten ist, dass es in der Informatik um diskrete, meist endliche Strukturen geht. Digita- le Computer haben einen endlichen Zustandsraum, d.h. der Zustand ist exakt beschreibbar als eine von endlich vielen Möglichkeiten. Zwei Zustände können nicht, wie in der Physik, beliebig ähnlich sein. Es gibt nicht das Problem, dass reellwertige Parameter (z.B. die Temperatur) nur approximativ gemessen wer- den können. In der Informatik im engeren Sinn gibt es keine kontinuierlichen Grössen.1 Das heisst natürlich nicht, dass sich die Informatik nicht mit Themen befasst, bei denen kontinuierliche Grössen wichtig sind. Die Informatik ist ja auch eine Hilfswissenschaft, z.B. für die Naturwissenschaften, wobei die Grenzen zwi- schen der eigentlichen Wissenschaft und der Hilfswissenschaft in einigen Berei- chen verschwommener werden. In Bereichen wie Computational Biology oder Computational Chemistry werden wesentliche Beiträge direkt von der Informa- tik beigesteuert. In diesen Bereichen der Informatik spielen reellwertig parame- trisierte Systeme eine wichtige Rolle.2 1 Die Mathematik der Informatik sollte demnach einfacher verständlich sein als die kontinuier- liche Mathematik (z.B. Analysis). Sollte dies dem Leser ab und zu nicht so erscheinen, so ist es vermutlich lediglich eine Frage der Gewöhnung. 2 Die Numerik befasst sich unter anderem mit dem Thema der (in einem Computer unvermeid- baren) diskreten Approximation reeller Grössen und den daraus resultierenden Problemen wie z.B. numerische Instabilitäten. Das Teilgebiet der Mathematik, das sich mit diskreten Strukturen befasst, heisst diskrete Mathematik. Der Begriff “diskret” ist zu verstehen als endlich oder abzählbar unendlich. Viele Teilbereiche der diskreten Mathematik sind so wichtig, dass sie vertieft in einer eigenen Vorlesung behandelt werden. Dazu gehören die Theorie der Berechnung, also die Formalisierung der Begriffe Berechnung und Algorithmus, welche in der Vorlesung “Theoretische Informatik” behan- delt wird, sowie die diskrete Wahrscheinlichkeitstheorie. Eine inhaltliche Ver- wandtschaft besteht auch zur Vorlesung über Algorithmen und Datenstruktu- ren. In dieser Lehrveranstaltung werden die wichtigsten Begriffe, Techniken und Resultate der diskreten Mathematik eingeführt. Hauptziele der Vorlesung sind nebst der Behandlung der konkreten Themen ebenso die adäquate Modellie- rung von Sachverhalten, sowie das Verständnis für die Wichtigkeit von Ab- straktion, von Beweisen und generell der mathematisch-präzisen Denkweise, die auch beim Entwurf von Softwaresystemen enorm wichtig ist. Zudem wer- den einige Anwendungen diskutiert, z.B. aus der Kryptografie, der Codierungs- theorie oder der Algorithmentheorie. Diskrete Mathematik ist ein sehr breites Gebiet. Entsprechend unterschiedliche Ansätze gibt es auch für den Aufbau ei- ner Vorlesung über das Thema. Mein Ziel bei der Konzipierung dieser Lehr- veranstaltung war es, speziell auf Themen einzugehen, die in der Informatik wichtig sind, sowie dem Anspruch zu genügen, keine zentralen Themen der diskreten Mathematik auszulassen. Ausnahmen sind die Kombinatorik und die Graphentheorie, die früher als Kapitel 4 und 5 dieses Skriptes erschienen, in der letzten Studienplanrevision aber in andere Vorlesungen verschoben wurden. Die sechs Kapitel sind 1. Introduction and Motivation 2. Mathematical Reasoning and Proofs 3. Sets, Relations, and Functions 4. Number Theory 5. Algebra 6. Logic Viele Beispiele werden nur an der Tafel oder in den Übungen behandelt. Die Vorlesung und die Übungen bilden einen integralen Bestandteil der Lehrveran- staltung und des Prüfungsstoffes. Es gibt kein einzelnes Buch, das den ganzen Stoff der Lehrveranstaltung behandelt. Aber unten folgt eine Liste guter Bücher, die als Ergänzung dienen können. Sie decken aber jeweils nur Teile der Vorle- sung ab, gehen zum Teil zu wenig tief, oder sind zu fortgeschritten im Vergleich zur Vorlesung. N. L. Biggs, Discrete Mathematics, Clarendon Press. iv K. H. Rosen, Discrete Mathematics and its Applications, fourth edition, McGraw-Hill. A. Steger, Diskrete Strukturen, Band 1, Springer Verlag. M. Aigner, Diskrete Mathematik, Vieweg. J. Matousek, J. Nesetril, Discrete Mathematics, Clarendon Press. I. Anderson, A First Course in Discrete Mathematics, Springer Verlag. U. Schöning, Logik für Informatiker, Spektrum Verlag, 5. Auflage, 2000. M. Kreuzer and S. Kühling, Logik für Informatiker, Pearson Studium, 2006. Das Skript ist aus verschiedenen Gründen englischsprachig verfasst, unter anderem, weil daraus eventuell einmal ein Buch entstehen soll. Wichtige Begrif- fe sind auf deutsch in Fussnoten angegeben. Das Skript behandelt mehr Stoff als die Vorlesung. Abschnitte, die nicht Prüfungsstoff sind und vermutlich in der Vorlesung auch nicht behandelt werden, sind mit einem Stern (∗) markiert und in einem kleineren Font gedruckt. Im Verlauf der Vorlesung werde ich eventuell einzelne weitere Teile als nicht prüfungsrelevant deklarieren. Zum Schluss einige Überlegungen und Empfehlungen für die Arbeitswei- se beim Besuch dieser Lehrveranstaltung. Die Lehrveranstaltung besteht aus der Vorlesung, dem Skript, den Übungsblättern, den Musterlösungen, den Übungsstunden, und dem Selbststudium. Die verschiedenen Elemente sind aufeinander abgestimmt. Insbesondere ist die Vorlesung unter der Annahme konzipiert, dass die Studierenden das Skript zu den behandelten Teilen nach jeder Vorlesung lesen, allenfalls auch vorher als Vorbereitung. Es ist unabding- bar, dass Sie das Skript regelmässig und detailiert erarbeiten, da dies dem Konzept der Vorlesung entspricht. Ebenso ist es unabdingbar, zusätzlich zur Übungsstunde mehrere Stunden pro Woche eigenständig oder in Teamarbeit für das Lösen der Übungen aufzuwenden; ein Teil dieser Zeit soll vor der Übungsstunde investiert werden. Ich danke Giovanni Deligios und David Lanzenberger für viele konstruktive Kommentare und die kritische Durchsicht des Manuskripts. Zürich, im September 2024 Ueli Maurer v Contents 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 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.1.3 Mathematical Statements in Computer Science....... 10 2.2 The Concept of a Proof......................... 10 2.2.1 Examples of Proofs....................... 10 2.2.2 Examples of False Proofs................... 11 2.2.3 Two Meanings of the Symbol =⇒............... 12 2.2.4 Proofs Using Several Implications.............. 12 2.2.5 An Informal Understanding of the Proof Concept..... 13 2.2.6 Informal vs. Formal Proofs.................. 13 2.2.7 The Role of Logic........................ 15 2.2.8 Proofs in this Course...................... 15 2.3 A First Introduction to Propositional Logic............. 16 2.3.1 Logical Constants, Operators, and Formulas........ 16 2.3.2 Formulas as Functions..................... 18 2.3.3 Logical Equivalence and some Basic Laws......... 19 2.3.4 Logical Consequence (for Propositional Logic)....... 20 2.3.5 Lifting Equivalences and Consequences to Formulas... 21 vii 2.3.6 Tautologies and Satisfiability................. 22 2.3.7 Logical Circuits *........................ 23 2.4 A First Introduction to Predicate Logic................ 23 2.4.1 Predicates............................ 23 2.4.2 Functions and Constants.................... 24 2.4.3 The Quantifiers ∃ and ∀.................... 24 2.4.4 Nested Quantifiers....................... 25 2.4.5 Interpretation of Formulas................... 26 2.4.6 Tautologies and Satisfiability................. 27 2.4.7 Equivalence and Logical Consequence............ 27 2.4.8 Some Useful Rules....................... 28 2.5 Logical Formulas vs. Mathematical Statements........... 28 2.5.1 Fixed Interpretations and Formulas as Statements..... 28 2.5.2 Mathematical Statements about Formulas.......... 29 2.6 Some Proof Patterns.......................... 29 2.6.1 Composition of Implications................. 30 2.6.2 Direct Proof of an Implication................. 30 2.6.3 Indirect Proof of an Implication................ 30 2.6.4 Modus Ponens......................... 31 2.6.5 Case Distinction......................... 31 2.6.6 Proofs by Contradiction.................... 32 2.6.7 Existence Proofs......................... 34 2.6.8 Existence Proofs via the Pigeonhole Principle........ 34 2.6.9 Proofs by Counterexample.................. 36 2.6.10 Proofs by Induction...................... 36 3 Sets, Relations, and Functions 39 3.1 Introduction............................... 39 3.1.1 An Intuitive Understanding of Sets............. 39 3.1.2 Russell’s Paradox........................ 40 3.2 Sets and Operations on Sets...................... 41 3.2.1 The Set Concept......................... 41 3.2.2 Set Equality and Constructing Sets From Sets........ 42 3.2.3 Subsets.............................. 43 3.2.4 Union and Intersection..................... 44 3.2.5 The Empty Set.......................... 45 viii 3.2.6 Constructing Sets from the Empty Set............ 46 3.2.7 A Construction of the Natural Numbers........... 47 3.2.8 The Power Set of a Set..................... 48 3.2.9 The Cartesian Product of Sets................. 48 3.3 Relations................................. 49 3.3.1 The Relation Concept..................... 49 3.3.2 Representations of Relations................. 50 3.3.3 Set Operations on Relations.................. 51 3.3.4 The Inverse of a Relation.................... 51 3.3.5 Composition of Relations................... 52 3.3.6 Special Properties of Relations................ 53 3.3.7 Transitive Closure....................... 55 3.4 Equivalence Relations......................... 55 3.4.1 Definition of Equivalence Relations............. 55 3.4.2 Equivalence Classes Form a Partition............ 56 3.4.3 Example: Definition of the Rational Numbers....... 57 3.5 Partial Order Relations......................... 58 3.5.1 Definition............................ 58 3.5.2 Hasse Diagrams......................... 59 3.5.3 Combinations of Posets and the Lexicographic Order... 61 3.5.4 Special Elements in Posets................... 61 3.5.5 Meet, Join, and Lattices.................... 63 3.6 Functions................................. 63 3.7 Countable and Uncountable Sets................... 65 3.7.1 Countability of Sets....................... 65 3.7.2 Between Finite and Countably Infinite............ 66 3.7.3 Important Countable Sets................... 67 3.7.4 Uncountability of {0, 1}∞................... 70 3.7.5 Existence of Uncomputable Functions............ 71 4 Number Theory 72 4.1 Introduction............................... 72 4.1.1 Number Theory as a Mathematical Discipline....... 72 4.1.2 What are the Integers?..................... 73 4.2 Divisors and Division.......................... 74 4.2.1 Divisors............................. 74 ix 4.2.2 Division with Remainders................... 74 4.2.3 Greatest Common Divisors.................. 75 4.2.4 Least Common Multiples................... 77 4.3 Factorization into Primes........................ 77 4.3.1 Primes and the Fundamental Theorem of Arithmetic... 77 4.3.2 Proof of the Fundamental Theorem of Arithmetic *.... 78 4.3.3 Expressing gcd and lcm.................... 79 4.3.4 Non-triviality of Unique Factorization *........... 79 4.3.5 Irrationality of Roots *..................... 80 4.3.6 A Digression to Music Theory *................ 80 4.4 Some Basic Facts About Primes *................... 81 4.4.1 The Density of Primes..................... 81 4.4.2 Remarks on Primality Testing................. 82 4.5 Congruences and Modular Arithmetic................ 83 4.5.1 Modular Congruences..................... 83 4.5.2 Modular Arithmetic...................... 84 4.5.3 Multiplicative Inverses..................... 86 4.5.4 The Chinese Remainder Theorem.............. 87 4.6 Application: Diffie-Hellman Key-Agreement............ 88 5 Algebra 91 5.1 Introduction............................... 91 5.1.1 What Algebra is About..................... 91 5.1.2 Algebraic Structures...................... 91 5.1.3 Some Examples of Algebras.................. 92 5.2 Monoids and Groups.......................... 92 5.2.1 Neutral Elements........................ 93 5.2.2 Associativity and Monoids.................. 93 5.2.3 Inverses and Groups...................... 94 5.2.4 (Non-)minimality of the Group Axioms........... 95 5.2.5 Some Examples of Groups................... 96 5.3 The Structure of Groups........................ 97 5.3.1 Direct Products of Groups................... 97 5.3.2 Group Homomorphisms.................... 98 5.3.3 Subgroups............................ 99 5.3.4 The Order of Group Elements and of a Group....... 99 x 5.3.5 Cyclic Groups.......................... 100 5.3.6 Application: Diffie-Hellman for General Groups..... 101 5.3.7 The Order of Subgroups.................... 101 5.3.8 The Group Z∗m and Euler’s Function............. 102 5.4 Application: RSA Public-Key Encryption.............. 104 5.4.1 e-th Roots in a Group...................... 105 5.4.2 Description of RSA....................... 105 5.4.3 On the Security of RSA *.................... 107 5.4.4 Digital Signatures *....................... 107 5.5 Rings and Fields............................. 108 5.5.1 Definition of a Ring....................... 108 5.5.2 Units and the Multiplicative Group of a Ring........ 109 5.5.3 Divisors............................. 110 5.5.4 Zerodivisors and Integral Domains............. 110 5.5.5 Polynomial Rings........................ 111 5.5.6 Fields............................... 113 5.6 Polynomials over a Field........................ 115 5.6.1 Factorization and Irreducible Polynomials......... 115 5.6.2 The Division Property in F [x]................. 117 5.6.3 Analogies Between Z and F [x], Euclidean Domains *... 118 5.7 Polynomials as Functions....................... 119 5.7.1 Polynomial Evaluation..................... 119 5.7.2 Roots............................... 119 5.7.3 Polynomial Interpolation................... 120 5.8 Finite Fields............................... 121 5.8.1 The Ring F [x]m(x)....................... 121 5.8.2 Constructing Extension Fields................ 123 5.8.3 Some Facts About Finite Fields *............... 125 5.9 Application: Error-Correcting Codes................. 126 5.9.1 Definition of Error-Correcting Codes............. 126 5.9.2 Decoding............................ 127 5.9.3 Codes based on Polynomial Evaluation........... 128 6 Logic 130 6.1 Introduction............................... 130 6.2 Proof Systems.............................. 131 xi xii 6.2.1 Definition............................ 131 6.2.2 Examples............................ 133 6.2.3 Discussion............................ 135 6.2.4 Proof Systems in Theoretical Computer Science *...... 136 6.3 Elementary General Concepts in Logic................ 136 6.3.1 The General Goal of Logic................... 137 6.3.2 Syntax.............................. 137 6.3.3 Semantics............................ 138 6.3.4 Connection to Proof Systems *................ 139 6.3.5 Satisfiability, Tautology, Consequence, Equivalence.... 139 6.3.6 The Logical Operators ∧, ∨, and ¬.............. 140 6.3.7 Logical Consequence vs. Unsatisfiability.......... 142 6.3.8 Theorems and Theories.................... 142 6.4 Logical Calculi.............................. 143 6.4.1 Introduction........................... 143 6.4.2 Hilbert-Style Calculi...................... 144 6.4.3 Soundness and Completeness of a Calculus......... 145 6.4.4 Some Derivation Rules..................... 146 6.4.5 Derivations from Assumptions................ 147 6.4.6 Connection to Proof Systems *................ 148 6.5 Propositional Logic........................... 148 6.5.1 Syntax.............................. 148 6.5.2 Semantics............................ 149 6.5.3 Brief Discussion of General Logic Concepts......... 149 6.5.4 Normal Forms......................... 150 6.5.5 The Resolution Calculus for Propositional Logic...... 152 6.6 Predicate Logic (First-order Logic).................. 156 6.6.1 Syntax.............................. 156 6.6.2 Free Variables and Variable Substitution........... 156 6.6.3 Semantics............................ 157 6.6.4 Predicate Logic with Equality................. 159 6.6.5 Some Basic Equivalences Involving Quantifiers...... 159 6.6.6 Substitution of Bound Variables............... 160 6.6.7 Normal Forms......................... 161 6.6.8 Derivation Rules........................ 162 6.6.9 An Example Theorem and its Interpretations........ 162 xiii 6.7 Beyond Predicate Logic *........................ 165 Chapter 1 Introduction and Motivation 1.1 Discrete Mathematics and Computer Science Discrete mathematics is concerned with finite and countably infinite mathemati- cal structures. Most areas within Computer Science make heavy use of concepts from discrete mathematics. The applications range from algorithms (design and analysis) to databases, from security to graphics, and from operating systems to program verification.1 There are (at least) three major reasons why discrete mathematics is of cen- tral importance in Computer Science: 1. Discrete structures. Many objects studied in Computer Science are dis- crete mathematical objects, for example a graph modeling a computer net- work or an algebraic group used in cryptography or coding theory. Many applications exploit sophisticated properties of the involved structures. 2. Abstraction. Abstraction is of paramount importance in Computer Sci- ence. A computer system can only be understood by considering a num- ber of layers of abstraction, from application programs via the operating system layer down to the physical hardware. Discrete mathematics, espe- cially the way we present it, can teach us the art of abstraction. We refer to Section 1.3 for a discussion. 3. Mathematical derivations. Mathematical reasoning is essential in any en- gineering discipline, and especially in Computer Science. In many disci- plines (e.g.2 mechanical engineering), mathematical reasoning happens in 1 We also refer to the preface to these lecture notes where the special role of mathematics for Computer Science is mentioned. 2 “e.g.”, the abbreviation of the Latin “exempli gratia” should be read as “for example”. 1 1.2. Discrete Mathematics: A Selection of Teasers 2 the form of calculations (e.g. calculating the wing profile for an airplane). In contrast, in Computer Science, mathematical reasoning often happens in the form of a derivation (or, more mathematically stated, a proof). For example, understanding a computer program means to understand it as a well-defined discrete mathematical object, and making a desirable state- ment about the program (e.g. that it terminates within a certain number of steps) means to prove (or derive) this statement. Similarly, the state- ment that a system (e.g. a block-chain system) is secure is a mathematical statement that requires a proof. 1.2 Discrete Mathematics: A Selection of Teasers We present a number of examples as teasers for this course. Each example is representative for one or several of the topics treated in this course.3 Example 1.1. Consider a k × k chess board (ignoring the black/white coloring). Prove or disprove the following statement: No matter which of the squares is marked, the remaining area of the board (consisting of k 2 − 1 squares) can be covered completely with (non-overlapping) L-shaped pieces of paper each con- sisting of three squares. This example allows us to informally introduce a few mathematical concepts that will be discussed in detail later in this course. The above statement depends on k. For certain k it is true and for certain k it is false. Let us therefore intro- duce a so-called logical predicate P , a function from the natural numbers to {0, 1}, where 1 stands for true and 0 stands for false. Then P (k) = 1 means that the statement is true for k, and P (k) = 0 means that the statement is false for k. The case k = 2 is trivial: If any square (which is a corner square) is removed from a 2 × 2 chess board, the remaining three squares form the given L-shape. Hence we have P (2) = 1. For k = 3, a simple counting argument shows that P (3) = 0. Since k 2 − 1 = 8 squares should be covered three at a time (by L-shapes), two squares remain at the end. More generally, a solution can exist only if k 2 − 1 is divisible by 3. For which k is this the case? In our notation we will (in Chapter 4) write k 2 ≡3 1 for this condition, read as “k 2 is congruent to 1 modulo 3.” This condition is equivalent to k ≡3 1 or k ≡3 2. 3 The reader should not worry too much if he or she is not familiar with some of the concepts discussed in this section, for example the interpolation of a polynomial, computation modulo a number n, Euclid’s algorithm for computing greatest common divisors, or matrices. 3 Chapter 1. Introduction and Motivation Hence we have P (k) = 0 for all k with k ≡3 0 (i.e.,4 the k divisible by 3).5 The case k = 4 can be solved easily by finding a solution for each of the three types of squares (corner, edge, interior of board) that could be marked. Hence we have proved P (4) = 1. This proof type will later be called a proof by case distinction. For the case k = 5 one can prove that P (5) = 0 by showing that there is (at least) a square which, when marked, leaves an area not coverable by L-shapes. Namely, if one marks a square next to the center square, then it is impossible to cover the remaining area by L-shapes. This proof type will later be called a proof by counterexample. We have P (6) = 0 because 6 is divisible by 3, and hence the next interesting case is k = 7. The reader can prove as an exercise that P (7) = 1. (How many cases do you have to check?) The question of interest is, for a general k, whether P (k) = 1 or P (k) = 0. But one can prove (explained in the lecture) that P (k) = 1 =⇒ P (2k) = 1, i.e., that if the statement is true for some k, then it is also true for two times k. This implies that P (2i ) = 1 for any i and also that P (7 · 2i ) = 1 for any i. Hence we have P (8) = 1, and P (9) = 0, leaving P (10) and P (11) as the next open cases. One can also prove the following generalization of the above-stated fact: P (k) = 1 and P (ℓ) = 1 =⇒ P (kℓ) = 1. We point out that, already in this first example, we understand the reasoning leading to the conclusion P (k) = 0 or P (k) = 1 as a proof. Example 1.2. Consider the following simple method for testing primality. Prove or disprove that an odd number n is a prime if and only if 2n−1 divided by n yields remainder 1, i.e., if 2n−1 ≡n 1. One can easily check that 2n−1 ≡n 1 holds for the primes n = 3, 5, 7, 11, 13 (and many more). Moreover, one can also easily check that 2n−1 6≡n 1 for the first odd composite numbers n = 9, 15, 21, 25, etc. But is the formula a general primality test? The solution to this problem will be given in Chapter 4. Example 1.3. The well-known cancellation law for real numbers states that if ab = ac and a 6= 0, then b = c. In other words, one can divide both sides by a. How general is this law? Does it hold for the polynomials over R, i.e., does 4 “i.e.”, the abbreviation of the Latin “id est”, should be read as “that is” (German: “das heisst”). 5 Thefact that the equation k 2 ≡p 1 has two solutions modulo p, for any prime p, not just for p = 3, will be obvious once we understand that computing modulo p is a field (see Chapter 5) and that every element of a field has either two square roots or none. 1.3. Abstraction: Simplicity and Generality 4 a(x)b(x) = a(x)c(x) imply b(x) = c(x) if a(x) 6= 0? Does it hold for the integers modulo m, i.e., does ab ≡m ac imply b ≡m c if a 6= 0? Does it hold for the permutations, when multiplication is defined as composition of permutations? What does the condition a 6= 0 mean in this case? Which abstraction lies behind the cancellation law? This is a typical algebraic question (see Chapter 5). Example 1.4. It is well-known that one can interpolate a polynomial a(x) = ad xd + ad−1 xd−1 + · · · a1 x + a0 of degree d with real coefficients from any d + 1 values a(αi ), for distinct α1 ,... , αd+1. Can we also construct polynomials over a finite domain (which is of more interest and use in Computer Science), keeping this interpolation property? For example, consider computation modulo 5. There are 53 = 125 polyno- mials a2 x2 + a1 x + a0 of degree 2 because we can freely choose three coefficients from {0, 1, 2, 3, 4}. It is straight-forward (though cumbersome) to verify that if we fix any three evaluation points (for example 0, 2, and 3), then the polyno- mial is determined by the values at these points. In other words, two different polynomials p and q result in distinct lists (p(0), p(2), p(3)) and (q(0), q(2), q(3)) of polynomial values. What is the general principle explaining this? For the answer and applications, see Chapter 5. 1.3 Abstraction: Simplicity and Generality A main theme of this course is abstraction. In everyday life, the term “abstract” has a negative meaning. It stands for non-intuitive and difficult-to-understand. For us, abstraction will have precisely the opposite meaning. It will stand for simplicity and generality. I hope to be able to convey the joy and importance of simplification and generalization by abstraction. Indeed, abstraction is probably the most important principle in program- ming and the design of information systems. Computers and computer pro- grams are highly (perhaps unimaginably) complex systems. For a computer sys- tem with only 1000 bits of storage, the number 21000 of system states is greater than the number of atoms in the known universe. The immense complexity of software systems is usually grossly underestimated, resulting in potentially catastrophic software failures. For typical commercial software, failures are the rule rather than the exception. In order to manage the complexity, software systems are divided into com- ponents (called modules, layers, objects, or abstract data types) that interact with each other and with the environment in a well-defined manner. For ex- ample, the Internet communication software is divided into a number of lay- ers, each with a dedicated set of tasks. The IP layer transports packets between computers, and the TCP layer manages reliable connections. The potential com- plexity of the interaction between subsystems is channeled into clearly specified interfaces. The behavior of a subsystem is described by a manageable number 5 Chapter 1. Introduction and Motivation of rules. This is abstraction. Without abstraction, writing good software is im- possible. Abstraction means simplification. By an abstraction one ignores all aspects of a system that are not relevant for the problem at hand, concentrating on the properties that matter. Abstraction also means generalization. If one proves a property of a system described at an abstract level, then this property holds for any system with the same abstraction, independently of any details. Example 1.5. A standard Swiss chocolate consists of 6 rows of 4 pieces each. We would like to break it into its 24 pieces using the minimal number of breaking operations. The first breaking operation can break the chocolate in any of the 5 ways parallel to the short side, or in any of the 3 ways parallel to the long side. Afterwards, a breaking operation consists of taking an arbitrary piece of chocolate and breaking it along one of the marked lines. Stacking pieces is not allowed. What is the minimal number of breaking operations needed to break the chocolate into its 24 pieces? Is it better to first break the chocolate into two equal pieces or to break off one row? Is it better to first break along a short or a long line? Which abstraction explains the answer? Find a similar problem with the same abstraction. Example 1.6. Can the shape in Figure 1.1 be cut into 9 identical pieces? If not, why? If yes, what is the abstraction that explains this? What would more gen- eral examples with the same abstraction look like? Why would it be easier to see the answer in such generalized examples? a a a a Figure 1.1: A shape to be cut into identical pieces. Example 1.7. Extend the following sequence of numbers: 0, 1, 1, 3, 5, 11, 21, 43, 85,.... It is a natural human behavior to find a simple explanation consistent with a given observation, i.e., to abstract.6 Which is the simplest rule that defines the sequence? There may be several answers that make sense. Example 1.8. Euclid’s well-known algorithm for computing the greatest com- mon divisor of two positive integers a and b works as follows: In each step, 6 Unfortunately, this also leads to over-simplifications and inappropriate generalizations. 1.3. Abstraction: Simplicity and Generality 6 the larger integer is divided by the smaller integer, and the pair of integers is replaced by the pair consisting of the smaller integer and the remainder of the division. This step is repeated until the remainder is 0. The greatest common divisor is the last non-zero remainder. Essentially the same algorithm works for two polynomials a(x) and b(x), say with integer (or real) coefficients, where the size of a polynomial is defined to be its degree. In which sense are integer numbers and polynomials similar? At which level of abstraction can they be seen as instantiations of the same abstract concept? As we will see in Chapter 5, the answer is that they are both so-called Euclidean domains, which is a special type of a so-called integral domain, which in turn is a special case of a ring. Chapter 2 Mathematical Reasoning, Proofs, and a First Approach to Logic 2.1 Mathematical Statements 2.1.1 The Concept of a Mathematical Statement People make many statements in life, like “I love you”, “tomorrow it will rain”, “birds can fly”, or “Roger Federer is the best tennis player”. By making the statement, the person making it intends to claim that it is true. However, most such statements are not sufficiently precise to be considered true or false, and often they are subjective. This is in contrast to mathematical statements. Definition 2.1. A mathematical statement (also called proposition) is a statement that is true or false in an absolute, indisputable sense, according to the laws of mathematics. We often simply say “statement” instead of “mathematical statement”. A mathematical statement that is known to be true is often called a theorem, a lemma, or a corollary.1 A mathematical statement not known (but believed) to be true or false is often called a conjecture. An assumption is a statement not known to be true but assumed to be true in a certain line of reasoning. Some- times, before a proof of a true mathematical statement is given, it is also called 1 The term “theorem” is usually used for an important result, whereas a lemma is an interme- diate, often technical result, possibly used in several subsequent proofs. A corollary is a simple consequence (e.g. a special case) of a theorem or lemma. 7 2.1. Mathematical Statements 8 assertion2 or claim. Examples of mathematical statements are 71 is a prime number. If p is a prime number, then 2p − 1 is also a prime number. Every natural number is the sum of at most four square numbers. (Exam- ple: 22 = 42 + 22 + 12 + 12 and 74 = 62 + 52 + 32 + 22.) Every even natural number greater than 2 can be expressed as the sum of two primes.3 For example, 108 = 37 + 71 and 162 = 73 + 89. Any n lines ℓ1 ,... , ℓn in the plane, no two of which are parallel, intersect in one point (see Example 2.4). For the chess game there exists a winning strategy for the player making the first move (playing “white”). The first statement is easily shown to be true. The second statement is false, and this can be proved by giving a counter-example: 11 is prime but 211 − 1 = 2047 = 23 ·89 is not prime.4 The third statement is true but by no means obvious (and requires a sophisticated proof). The fourth statement is not known to be true (or false). The fifth statement is false. The sixth statement is not known to be true (or false). Example 2.1. Consider the following statement which sounds like a statement of interest in Computer Science: “There is no algorithm for factoring any n- bit integer in n3 steps”. This is not a precise mathematical statement because its truth (namely the complexity of the best algorithm) generally depends on the particular computational model one is considering. A goal of Theoretical Computer Science (TCS) is therefore to define precise models of computation and the complexity of algorithms, allowing to make such claims precise. If one makes a statement, say S, for example in the context of these lecture notes, there can be two different meanings. The first meaning is that by stating it one claims that S is true, and the second meaning is simply to discuss the statement itself (for example as an assumption), independently of whether it is true or not. We should try to distinguish clearly between these two meanings. 2.1.2 Composition of Mathematical Statements We can derive new mathematical statements from given statements. For exam- ple, when given three statements S, T , and U , then we can defined the following well-defined statement: Exactly two the statements S, T , and U are true. Four specific forms of derived statements are discussed below. Let S and T be math- ematical statements. 2 German: Behauptung 3 Thisstatement is called the Goldbach conjecture and is one of the oldest unproven conjectures in mathematics. 4 2p − 1 is prime for most primes p (e.g. for 2, 3, 5, 7, 13 and many more), but not all. 9 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic Negation: S is false. And: S and T are (both) true. Or: At least one of S and T is true. Implication: If S is true, then T is true. Examples of such derived statements are: “4 is even” is false. 4 is an even number and 71 is a prime number. 5 is an even number and 71 is a prime number. 5 is an even number or 71 is a prime number. The first statement is false because “4 is even” is true. The second statement is true because both statements “4 is an even number” and “71 is a prime number” are true. In contrast, the third statement is false because the statement “5 is an even number” is false. However, the fourth statement is again true because “71 is a prime number” is true and hence it is irrelevant whether “5 is an even number” is true or false. For the first three types of statements, there is no particular notation used in mathematics.5 However, interestingly, for the fourth type (implication) there exists a notation that is often used, namely S =⇒ T. One also says “S implies T ”. The statement S =⇒ T is false if S is true and T is false, and in all other three cases, S =⇒ T is true. In other words, the first three statements below are true while the last one is false. 4 is an even number =⇒ 71 is a prime number. 5 is an even number =⇒ 71 is a prime number. 5 is an even number =⇒ 70 is a prime number. 4 is an even number =⇒ 70 is a prime number. We point out that S =⇒ T does not express any kind of causality like “because S is true, T is also true” (but see the discussion in Section 2.2.3). Similarly, S ⇐⇒ T means that S is true if and only if T is true. This can equivalently be stated as “S implies T and T implies S.” 5 Note that, when introducing logic and its symbols, we will for example use the symbol ∧ for the logical “and” of two formulas, but we avoid using the symbols of logic outside of logic. Thus, in order to avoid confusion, we avoid writing something like S ∧ T for “S and T.” 2.2. The Concept of a Proof 10 2.1.3 Mathematical Statements in Computer Science Many statements relevant in Computer Science are mathematical statements which one would like to prove. We give a few examples of such statements: Program P terminates (i.e., does not enter an infinite loop) for all inputs. Program P terminates within k computation steps for all inputs. Program P computes f (x) for every input x, where f is a function of in- terest. Algorithm A solves problem S within accuracy ǫ. The error probability of file transmission system F in a file transmission is at most p (where p can be a function of the file length). The computer network C has the property that if any t links are deleted, every node is still connected with every other node. Encryption scheme E is secure (for a suitable definition of security). Cryptocurrency system C operates correctly as long as a majority of the involved nodes behave honestly, even if all the other nodes behave arbi- trarily maliciously. Database system D provides data privacy (for a suitable definition of pri- vacy). Programs, algorithms, encryption schemes, etc., are (complex) discrete mathematical objects, and proving statements like those mentioned above is highly non-trivial. This course is not about programs or algorithms, let alone encryption schemes, but it provides the foundations so that later courses can reason mathematically about these objects. 2.2 The Concept of a Proof The purpose of a proof is to demonstrate (or prove) a mathematical statement S. In this section we informally discuss the notion of a proof. We also discuss several proof strategies. In Chapter 6 about logic, the notion of a proof in a proof calculus will be formalized. 2.2.1 Examples of Proofs We already gave examples of proofs in Chapter 1. We give one more simple example. Example 2.2. Claim: The number n = 2143 − 1 is not a prime. Proof: n is divisible by 2047, as one can check by a (for a computer) simple calculation. 11 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic That this is true can even be easily seen without doing a calculation, by prov- ing a more general claim of which the above one is a special case: Claim: n is not prime =⇒ 2n − 1 is not prime.6 Proof: If n is not a prime, then (by definition of prime numbers) n = ab with a > 1 and a < n. Now we observe that 2a − 1 divides 2ab − 1: b−1 X 2ab − 1 = (2a − 1) 2ia = (2a − 1) 2(b−1)a + 2(b−2)a + · · · + 2a + 1 i=0 as can easily be verified by a simple calculation. Since 2a − 1 > 1 and 2a − 1 < 2ab − 1, i.e., 2a − 1 is a non-trivial divisor of 2ab − 1, this means that 2ab − 1 is not a prime, concluding the proof of the claim. Let us state a warning. Recall from the previous section that n is prime =⇒ 2n − 1 is prime is a false statement, even though it may appear at first sight to follow from the above claim. However, we observe that if S =⇒ T is true, then generally it does not follow that if S is false, then T is false. Example 2.3. An integer n is called a square if n = m · m for some integer m. Prove that if a and b are squares, then so is a · b. a and b are squares. =⇒ a = u · u and b = v · v for some u and v (def. of squares). =⇒ a · b = (u · u) · (v · v) (replace a by u · u and b by v · v). =⇒ a · b = (u · v) · (u · v). (commutative and associative laws). =⇒ a · b is a square (def. of squares) The above proof follows a standard pattern of proofs as a sequence of im-. plications, each step using the symbol =⇒. Such a proof step requires that the justification for doing the step is clear. Often one justifies the proof step either in the accompanying text or as a remark on the same line as the implication state- ment (as in the above proof). But even more often the justification for the step is simply assumed to be understood from the context and not explicitly stated, which can sometimes make proofs hard to follow or even ambiguous. 2.2.2 Examples of False Proofs As a next motivating example, let us prove a quite surprising assertion.7 6 It is understood that this statement is meant to hold for an arbitrary n. 7 This example is taken from the book by Matousek and Nesetril. 2.2. The Concept of a Proof 12 Example 2.4. Claim: Any n lines ℓ1 ,... , ℓn in the plane, no two of which are parallel, intersect in one point (i.e., have one point in common). Proof: The proof proceeds by induction.8 The induction basis is the case n = 2: Any two non-parallel lines intersect in one point. The induction hypothesis is that any n lines intersect in one point. The induction step states that then this must be true for any n+1 lines. The proof goes as follows. By the hypothesis, the n lines ℓ1 ,... , ℓn intersect in a point P. Similarly, the n lines ℓ1 ,... , ℓn−1 , ℓn+1 intersect in a point Q. The line ℓ1 lies in both groups, so it contains both P and Q. The same is true for line ℓn−1. But ℓ1 and ℓn−1 intersect at a single point, hence P = Q. This is the common point of all lines ℓ1 ,... , ℓn+1. Something must be wrong! (What?) This example illustrates that proofs must be designed with care. Heuristics and intuition, though essential in any engineering discipline as well as in mathematics, can sometimes be wrong. Example 2.5. In the lecture we present a “proof” for the statement 2 = 1. 2.2.3 Two Meanings of the Symbol =⇒ It is important to note that the symbol =⇒ is used in the mathematical literature for two different (but related) things: to express composed statements of the form S =⇒ T (see Section 2.1.2), to express a derivation step in a proof, as above.. To make this explicit and avoid confusion, we use a slightly different symbol =⇒. for the second meaning.9 Hence S =⇒ T means that T can be obtained from S by a proof step, and in this case we also know that the statement S =⇒ T is true. However, conversely, if S =⇒ T is true for some statements S and T , there may. not exist a proof step demonstrating this, i.e. S =⇒ T may not hold.. An analogous comment applies to the symbol ⇐⇒, i.e., S ⇐⇒ T can be used to express that T follows from S by a simply proof step, and also S follows from T by a simply proof step. 2.2.4 Proofs Using Several Implications Example 2.3 showed a proof of a statement of the form S =⇒ T using a se-... quence of several implications of the form S =⇒ S2 , S2 =⇒ S3 , S3 =⇒ S4 , and. S4 =⇒ T. 8 Here we assume some familiarity with proofs by induction; in Section 2.6.10 we discuss them in depth.. 9 This notation is not standard and only used in these lecture notes. The symbol =⇒ is intention- ally chosen very close to the symbol =⇒ to allow someone not used to this to easily overlook the difference. 13 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic A proof based on several implications often has a more general form: The implications do not form a linear sequence but a more general configuration, where each implication can assume several of the already proved statements. For example, one can imagine that in order to prove a given statement T , one starts with two (known to be) true statements S1 and S2 and then, for some statements S3 ,... , S7 , proves the following six implications:. S1 =⇒ S3 ,. S1 =⇒ S4 ,. S2 =⇒ S5 ,. S3 and S5 =⇒ S6 ,. S1 and S4 =⇒ S7 , as well as. S6 and S7 =⇒ T. Example 2.6. In the lecture we demonstrate the proof of Example 2.2 in the above format, making every intermediate statement explicit. 2.2.5 An Informal Understanding of the Proof Concept There is a common informal understanding of what constitutes a proof of a mathematical statement S. Informally, we could define a proof as follows: Definition 2.2. (Informal.) A proof of a statement S is a sequence of simple, eas- ily verifiable, consecutive steps. The proof starts from a set of axioms (things postulated to be true) and known (previously proved) facts. Each step corre- sponds to the application of a derivation rule to a few already proven state- ments, resulting in a newly proved statement, until the final step results in S. Concrete proofs vary in length and style according to which axioms and known facts one is assuming, what is considered to be easy to verify, how much is made explicit and how much is only implicit in the proof text, and. to what extent one uses mathematical symbols (like =⇒) as opposed to just writing text. 2.2.6 Informal vs. Formal Proofs Most proofs taught in school, in textbooks, or in the scientific literature are in- tuitive but quite informal, often not making the axioms and the proof rules ex- plicit. They are usually formulated in common language rather than in a rigor- ous mathematical language. Such proofs can be considered completely correct 2.2. The Concept of a Proof 14 if the reasoning is clear. An informal proof is often easier to read than a pedantic formal proof. However, a proof, like every mathematical object, can be made rigorous and formally precise. This is a major goal of logic (see Section 2.2.7 and Chapter 6). There are at least three (related) reasons for using a more rigorous and formal type of proof. Prevention of errors. Errors are quite frequently found in the scientific lit- erature. Most errors can be fixed, but some can not. In contrast, a com- pletely formal proof leaves no room for interpretation and hence allows to exclude errors. Proof complexity and automatic verification. Certain proofs in Computer Sci- ence, like proving the correctness of a safety-critical program or the se- curity of an information system, are too complex to be carried out and verified “by hand”. A computer is required for the verification. A com- puter can only deal with rigorously formalized statements, not with semi- precise common language, hence a formal proof is required.10 Precision and deeper understanding. Informal proofs often hide subtle steps. A formal proof requires the formalization of the arguments and can lead to a deeper understanding (also for the author of the proof). There is a trade-off between mathematical rigor and an intuitive, easy-to- read (for humans) treatment. In this course, our goal is to do precise mathemat- ical reasoning, but at the same time we will try to strike a reasonable balance between formal rigor and intuition. In Chapters 3 to 5, our proofs will be in- formal, and the Chapter 6 on logic is devoted to understanding the notion of a formal proof. A main problem in teaching mathematical proofs (for example in this course) is that it is hard to define exactly when an informal proof is actually a valid proof. In most scientific communities there is a quite clear understanding of what constitutes a valid proof, but this understanding can vary from commu- nity to community (e.g. from physics to Computer Science). A student must learn this culture over the years, starting in high school where proof strategies like proofs by induction have probably been discussed. There is no quick and easy path to understanding exactly what constitutes a proof. The alternative to a relatively informal treatment would be to do everything rigorously, in a formal system as discussed in Chapter 6, but this would proba- bly turn away most students and would for the most parts simply not be man- ageable. A book that tries to teach discrete mathematics very rigorously is A logical approach to discrete math by Gries and Schneider. 10 A crucial issue is that the translation of an informal statement to a formal statement can be error-prone. 15 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic 2.2.7 The Role of Logic Logic is the mathematical discipline laying the foundations for rigorous mathe- matical reasoning. Using logic, every mathematical statement as well as a proof for it (if a proof exists) can, in principle, be formalized rigorously. As mentioned above, rigorous formalization, and hence logic, is especially important in Com- puter Science where one sometimes wants to automate the process of proving or verifying certain statements like the correctness of a program. Some principle tasks of logic (see Chapter 6) are to answer the following three questions: 1. What is a mathematical statement, i.e., in which language do we write statements? 2. What does it mean for a statement to be true? 3. What constitutes a proof for a statement from a given set of axioms? Logic (see Chapter 6) defines the syntax of a language for expressing statements and the semantics of such a language, defining which statements are true and which are false. A logical calculus allows to express and verify proofs in a purely syntactic fashion, for example by a computer. 2.2.8 Proofs in this Course As mentioned above, in the literature and also in this course we will see proofs at different levels of detail. This may be a bit confusing for the reader, especially in the context of an exam question asking for a proof. We will try to be always clear about the level of detail that is expected in an exercise or in the exam. For this purpose, we distinguish between the following three levels: Proof sketch or proof idea: The non-obvious ideas used in the proof are described, but the proof is not spelled out in detail with explicit reference to all definitions that are used. Complete proof: The use of every definition is made explicit. Every proof step is justified by stating the rule or the definition that is applied. Formal proof: The proof is entirely phrased in a given proof calculus. Proof sketches are often used when the proof requires some clever ideas and the main point of a task or example is to describe these ideas and how they fit together. Complete proofs are usually used when one systematically applies the definitions and certain logical proof patterns, for example in our treatments of relations and of algebra. Proofs in the resolution calculus in Chapter 6 can be considered to be formal proofs. 2.3. A First Introduction to Propositional Logic 16 2.3 A First Introduction to Propositional Logic We give a brief introduction to some elementary concepts of logic. We point out that this section is somewhat informal and that in the chapter on logic (Chap- ter 6) we will be more rigorous. In particular, we will there distinguish between the syntax of the language for describing mathematical statements (called for- mulas) and the semantics, i.e., the definition of the meaning (or validity) of a formula. In this section, the boundary between syntax and semantics is (inten- tionally) not made explicit. 2.3.1 Logical Constants, Operators, and Formulas Definition 2.3. The logical values (constants) “true” and “false” are usually de- noted as 1 and 0, respectively.11 One can define operations on logical values: Definition 2.4. (i) The negation (logical NOT) of a propositional symbol A, denoted as ¬A, is true if and only if A is false. (ii) The conjunction (logical AND) of two propositional symbol A and B, de- noted A ∧ B, is true if and only if both A and B are true. (iii) The disjunction (logical OR) of two propositional symbols A and B, de- noted A ∨ B, is true if and only if A or B (or both) are true.12 The logical operators are functions, where ¬ is a function {0, 1} → {0, 1} and ∧ and ∨ are functions {0, 1} × {0, 1} → {0, 1}. These functions can be described by function tables, as follows: A B A∧B A B A∨B A ¬A 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 Logical operators can also be combined, in the usual way of combining func- tions. For example, the formula A ∨ (B ∧ C) 11 These values 1 and 0 are not meant to be the corresponding numbers, even though the same symbols are used. 12 Sometimes ¬A, A ∧ B, and A ∨ B are also denoted as NOT(A), A AND B, and A OR B, respec- tively, or a similar notation. 17 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic has function table A B C A ∨ (B ∧ C) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 A slightly more complicated example is (A ∧ (¬B)) ∨ (B ∧ (¬C)) with function table A B C (A ∧ (¬B)) ∨ (B ∧ (¬C)) 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 Definition 2.5. A correctly formed expression involving the propositional sym- bols A, B, C,... and logical operators is called a formula (of propositional logic). We introduce a new, logical operator, implication, denoted as A → B and defined by the function table A B A→B 0 0 1 0 1 1 1 0 0 1 1 1 Note that A → B is true if and only if A implies B. This means that when A is true, then also B is true. Note that A → B is false if and only if A is true and B is false, or, stated differently, if B is false despite that A is true. A → B can be understood as an alternative notation for ¬A ∨ B, which has the same function table. Example 2.7. Consider the following sentence: If student X reads the lecture notes every week and solves the exercises (A), then student X will get a good grade in the exam (B). This is an example of an implication A → B. Saying that A → B is true does not mean that A is true and it is not excluded that B is true 2.3. A First Introduction to Propositional Logic 18 even if A is false, but it is excluded that B is false when A is true. Let’s hope the statement A → B is true for you : -). Two-sided implication, denoted A ↔ B, is defined as follows: A B A↔B 0 0 1 0 1 0 1 0 0 1 1 1 Note that A ↔ B is equivalent to (A → B) ∧ (B → A) in the sense that the two formulas have the same function table. We now discuss a few notational simplifications. We have already seen that parentheses can sometimes be dropped in a formula without changing its mean- ing. For example we can write A ∨ B ∨ C instead of A ∨ (B ∨ C) or (A ∨ B) ∨ C. There are also precedence rules for logical operators which allow to simplify the notation, in the same sense as in algebra one can write ab + c rather than (a · b) + c because · binds stronger than +. However, to keep things simple and avoid confusion, we will generally not make use of such rules, except that we adopt the convention that ¬ binds stronger than anything else. For example, we can write ¬A ∧ B instead of (¬A) ∧ B, or we can write A → ¬B instead of A → (¬B). 2.3.2 Formulas as Functions An arithmetic expression such as (a+b)·c can be understood as a function. If we consider as domain the natural numbers N, the arithmetic expression (a + b) · c corresponds to the function N3 → N assigning to every triple (a, b, c) the value (a + b) · c, for example the value 42 to the triple (4, 2, 7) (because (4 + 2) · 7 = 42). Analogously, a logical formula such as (A ∨ B) ∧ C can be interpreted as a function from the set of truth assignments for the proposition symbols A, B, and C to truth values, i.e., as a function {0, 1}3 → {0, 1}. For example, the function evaluates to 1 for A = 0, B = 1, and C = 1. Since in propositional logic13 the domain is finite, a function can be com- pletely characterized by a function table. For example, the function table of the function {0, 1}3 → {0, 1} corresponding to the formula (A ∧ (¬B)) ∨ (B ∧ (¬C)) is shown in the previous section. 13 but not for other logics such as predicate logic 19 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic 2.3.3 Logical Equivalence and some Basic Laws Different arithmetic expressions can correspond to the same function. For ex- ample, the expressions (a + b) · c and (c · a) + (b · c) denote the same functions. Analogously, different logical formulas can correspond to the same function. Definition 2.6. Two formulas F and G (in propositional logic) are called equiva- lent, denoted as F ≡ G, if they correspond to the same function, i.e., if the truth values are equal for all truth assignments to the propositional symbols appear- ing in F or G. For example, it is easy to see that ∧ and ∨ are commutative and associative, i.e., A∧B ≡ B∧A and A∨B ≡ B∨A as well as A ∧ (B ∧ C) ≡ (A ∧ B) ∧ C. Because of this equivalence, we introduce the notational convention that such unnecessary parentheses can be dropped:. A ∧ B ∧ C ≡ A ∧ (B ∧ C). Similarly we have A ∨ (B ∨ C) ≡ (A ∨ B) ∨ C and can write A ∨ B ∨ C instead, and we also have ¬(¬A) ≡ A. Let us look at some equivalences involving more than one operation, which are easy to check. The operator ∨ can be expressed in terms of ¬ and ∧, as follows: ¬(A ∨ B) ≡ ¬A ∧ ¬B, which also means that A ∨ B ≡ ¬(¬A ∧ ¬B). In fact, ¬ and ∧ are sufficient to express every logical function (of propositional logic). Similarly we have ¬(A ∧ B) ≡ ¬A ∨ ¬B. Example 2.8. A ↔ B ≡ (A → B) ∧ (B → A) ≡ (A ∧ B) ∨ (¬A ∧ ¬B). Example 2.9. Here is a more complicated example which the reader can verify as an exercise: (A ∧ (¬B)) ∨ (B ∧ (¬C)) ≡ (A ∨ B) ∧ ¬(B ∧ C). The following example shows a distributive law for ∧ and ∨. Such laws will be discussed more systematically in Chapter 6. 2.3. A First Introduction to Propositional Logic 20 Example 2.10. (A ∧ B) ∨ C ≡ (A ∨ C) ∧ (B ∨ C). We summarize the basic equivalences of propositional logic: Lemma 2.1. 1) A ∧ A ≡ A and A ∨ A ≡ A (idempotence); 2) A ∧ B ≡ B ∧ A and A ∨ B ≡ B ∨ A (commutativity of ∧ and ∨); 3) (A ∧ B) ∧ C ≡ A ∧ (B ∧ C) and (A ∨ B) ∨ C ≡ A ∨ (B ∨ C) (associativity); 4) A ∧ (A ∨ B) ≡ A and A ∨ (A ∧ B) ≡ A (absorption); 5) A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) (first distributive law); 6) A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C) (second distributive law); 7) ¬¬A ≡ A (double negation); 8) ¬(A ∧ B) ≡ ¬A ∨ ¬B and ¬(A ∨ B) ≡ ¬A ∧ ¬B (de Morgan’s rules). 2.3.4 Logical Consequence (for Propositional Logic) For arithmetic expressions one can state relations between them that are more general than equivalence. For example the relation a + b ≤ a + b + (c · c) between the expressions a + b and a + b + (c · c). What is meant by the relation is that for all values that a, b, and c can take on, the inequality holds, i.e., it holds for the functions corresponding to the expressions. Analogously, one can state relations between formulas. The perhaps most important relation is logical consequence which is analogous to the relation ≤ between arithmetic expressions. Definition 2.7. A formula G is a logical consequence14 of a formula F , denoted F |= G, if for all truth assignments to the propositional symbols appearing in F or G, the truth value of G is 1 if the truth value of F is 1. Intuitively, if we would interpret the truth values 0 and 1 as the numbers 0 and 1 (which we don’t!), then F |= G would mean F ≤ G (as functions). Example 2.11. A ∧ B |= A ∨ B. Example 2.12. Comparing the truth tables of the two formulas (A ∧ B) ∨ (A ∧ C) and ¬B → (A ∨ C) one can verify that (A ∧ B) ∨ (A ∧ C) |= ¬B → (A ∨ C). 14 German: (logische) Folgerung, logische Konsequenz 21 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic Note that the two formulas are not equivalent. Example 2.13. The following logical consequence, which the reader can prove as an exercise, captures a fact intuitively known to us, namely that implication is transitive:15 (A → B) ∧ (B → C) |= A → C. We point out (see also Chapter 6) that two formulas F and G are equivalent if and only if each one is a logical consequence of the other, i.e.,16 F ≡G ⇐⇒ F |= G and G |= F. 2.3.5 Lifting Equivalences and Consequences to Formulas Logical equivalences and consequences continue to hold if the propositional symbols A, B, C... are replaced by other propositional symbols or by formulas F, G, H.... At this point, we do not provide a proof of this intuitive fact. For example, because of the logical consequences stated in the previous section we have F ∧G ≡ G∧F and F ∨G ≡ G∨F as well as F ∧ (G ∧ H) ≡ (F ∧ G) ∧ H for any formulas F , G, and H. The described lifting is analogous to the case of arithmetic expressions. For example, we have (a + b) · c = (a · c) + (b · c) for any real numbers a, b, and c. Therefore, for any arithmetic expressions f , g, and h, we have (f + g) · h = (f · h) + (g · h). Example 2.14. We give a more complex example of such a lifting. Because of the logical consequence stated in Example 2.13, we have (F → G) ∧ (G → H) |= F → H for any formulas F , G, and H. 15 The term “transitive” will be discussed in Chapter 3. 16 Notethat we DO NOT write F |= G ∧ G |= F because the symbol ∧ is used only between two formulas in order to form a new (combined) formula, and F |= G and G |= F are not formulas. 2.3. A First Introduction to Propositional Logic 22 2.3.6 Tautologies and Satisfiability Definition 2.8. A formula F (in propositional logic) is called a tautology17 or valid18 if it is true for all truth assignments of the involved propositional sym- bols. One often writes |= F to say that F is a tautology. Example 2.15. The formulas A∨(¬A) and (A∧(A → B)) → B are tautologies. One often wants to make statements of the form that some formula F is a tautology. As stated in Definition 2.8, one also says “F is valid” instead of “F is a tautology”. Definition 2.9. A formula F (in propositional logic) is called satisfiable19 if it is true for at least one truth assignment of the involved propositional symbols, and it is called unsatisfiable otherwise. The symbol ⊤ is sometimes used to denote a tautology, and the symbol ⊥ is sometimes used to denote an unsatisfiable formula. One sometimes writes F ≡ ⊤ to say that F is a tautology, and F ≡ ⊥ to say that F is unsatisfiable. For example, for any formula F we have F ∨ ¬F ≡ ⊤ and F ∧ ¬F ≡ ⊥. Example 2.16. The formula (A ∧ ¬A) ∧ (B ∨ C) is unsatisfiable, and the formula A ∧ B is satisfiable. The following lemmas state two simple facts that follow immediately from the definitions. We only prove the second one. Lemma 2.2. A formula F is a tautology if and only if ¬F is unsatisfiable. Lemma 2.3. For any formulas F and G, F → G is a tautology if and only if F |= G. Proof. The lemma has two directions which we need to prove. To prove the first direction (=⇒), assume that F → G is a tautology. Then, for any truth assignment to the propositional symbols, the truth values of F and G are either both 0, or 0 and 1, or both 1 (but not 1 and 0). In each of the three cases it holds that G is true if F is true, i.e., F |= G. To prove the other direction (⇐=), assume F |= G. This means that for any truth assignment to the propositional symbols, the truth values of G is 1 if it is 1 for F. In other words, there is no 17 German: Tautologie 18 German: allgemeingültig 19 German: erfüllbar 23 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic truth assignment such that the truth value of F is 1 and that of G is 0. This means that the truth value of F → G is always 1, which means that F → G is a tautology. 2.3.7 Logical Circuits * A logical formula as discussed above can be represented as a tree where the leaves cor- respond to the propositions and each node corresponds to a logical operator. Such a tree can be implemented as a digital circuit where the operators correspond to the logical gates. This topic will be discussed in a course on the design of digital circuits20. The two main components of digital circuits in computers are such logical circuits and memory cells. 2.4 A First Introduction to Predicate Logic The elements of logic we have discussed so far belong to the realm of so-called propositional logic21. Propositional logic is not sufficiently expressive to capture most statements of interest in mathematics in terms of formulas. For example, the statement “There are infinitely many prime numbers” cannot be expressed as a formula in propositional logic (though it can of course be expressed as a sen- tence in common language). We need quantifiers22 , predicates, and functions. The corresponding extension of propositional logic is called predicate logic23 and is substantially more involved than propositional logic. Again, we refer to Chap- ter 6 for a more thorough discussion. 2.4.1 Predicates Let us consider a non-empty set U as the universe in which we want to reason. For example, U could be the set N of natural numbers, the set R of real numbers, the set {0, 1}∗ of finite-length bit-strings, or a finite set like {0, 1, 2, 3, 4, 5, 6}. Definition 2.10. A k-ary predicate24 P on U is a function U k → {0, 1}. A k-ary predicate P assigns to each list (x1 ,... , xk ) of k elements of U the value P (x1 ,... , xk ) which is either true (1) or false (0). For example, for U = N we can consider the unary (k = 1) predicate prime(x) defined by 1 if x is prime prime(x) = 0 else. 20 German: Digitaltechnik 21 German: Aussagenlogik 22 German: Quantoren 23 German: Prädikatenlogik 24 German: Prädikat 2.4. A First Introduction to Predicate Logic 24 Similarly, one can naturally define the unary predicates even(x) and odd(x). For any universe U with an order relation ≤ (e.g. U = N or U = R), the binary (i.e., k = 2) predicate less(x, y) can be defined as 1 if x < y less(x, y) = 0 else. However, in many cases we write binary predicates in a so-called “infix” nota- tion, i.e., we simply write x < y instead of less(x, y). For the universe of all human beings, we can define a binary predicate child as follows: child(x, y) = 1 if and only if x is y’s child. One can similarly define predicates parent, grandparent, etc. 2.4.2 Functions and Constants In predicate logic one can also use functions on U and constants (i.e., fixed el- ements) in U. For example, if the universe is U = N, we can use the functions add addition and multiplication mult and the constants 3 and 5. The formula less(add(x, 3), add(x, 5)) can also be written in infix notation as x + 3 < x + 5. This is a true statement for every value x in U. In the next section we see how we can express this as a formula. 2.4.3 The Quantifiers ∃ and ∀ Definition 2.11. For a universe U and predicate P (x) we define the following logical statements:25 ∀x P (x) stands for: P (x) is true for all x in U. ∃x P (x) stands for: P (x) is true for some x in U , i.e., there exists an x in U for which P (x) is true. More generally, for a formula F with a variable x, which for each value x in U is either true or false, the formula ∀x F is true if and only if F is true for all x in U , and the formula ∃x F is true if and only if F is true for some x in U. 25 Inthe literature one also finds the notations ∀x: P (x) and ∀x. P (x) instead of ∀x P (x), and similarly for ∃. 25 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic Example 2.17. Consider the universe U = N. Then ∀x (x ≥ 0) is true.26 Also, ∀x (x ≥ 2) is false, and ∃x (x + 5 = 3) is false. The name of the variable x is irrelevant. For example, the formula ∃x (x+5 = 3) is equivalent to the formula ∃y (y + 5 = 3). The formula could be stated in words as: “There exists a natural number (let us call it y) which, if 5 is added to it, the result is 3.” How the number is called, x or y or z, is irrelevant for the truth or falsity of the statement. (Of course the statement is false; it would be true if the universe were the integers Z.) Sometimes one wants to state only that a certain formula containing x is true for all x that satisfy a certain condition. For example, to state that x2 ≥ 25 whenever x ≥ 5, one can write ∀x (x ≥ 5) → (x2 ≥ 25). A different notation sometimes used to express the same statement is to state the condition on x directly after the quantifier: ∀x ≥ 5 : (x2 ≥ 25). 2.4.4 Nested Quantifiers Quantifiers can also be nested27. For example, if P (x) and Q(x, y) are predicates, then ∀x P (x) ∨ ∃y Q(x, y) is a logical formula. Example 2.18. The formula ∀x ∃y (y < x) states that for every x there is a smaller y. In other words, it states that there is no smallest x (in the universe under consideration). This formula is true for the universe of the integers or the universe of the real numbers, but it is false for the universe U = N. Example 2.19. For the universe of the natural numbers, U = N, the predicate prime(x) can be defined as follows:28 def prime(x) ⇐⇒ x > 1 ∧ ∀y ∀z (yz = x) → ((y = 1) ∨ (z = 1)). 26 But note that ∀x (x ≥ 0) is false for the universe U = R. 27 German: verschachtelt def 28 We use the symbol “⇐⇒” if the object on the left side is defined as being equivalent to the object on the right side. 2.4. A First Introduction to Predicate Logic 26 Example 2.20. Fermat’s last theorem can be stated as follows: For universe N \ {0},29 ¬ ∃ x ∃y ∃z ∃n (n ≥ 3 ∧ xn +y n = z n ). Example 2.21. The statement “for every natural number there is a larger prime” can be phrased as ∀x ∃y y > x ∧ prime(y) and means that there is no largest prime and hence that there are infinitely many primes. If the universe is N, then one sometimes uses m, n, or k instead of x and y. The above formula could hence equivalently be written as ∀m ∃n n > m ∧ prime(n). Example 2.22. Let U = R. What is the meaning of the following formula, and does it correspond to a true statement? ∀x x = 0 ∨ ∃y (xy = 1) Example 2.23. What is the meaning of the following formula, and for which universes is it true (or false)? ∀x ∀y (x < y) → ∃z((x < z) ∧ (z < y)) 2.4.5 Interpretation of Formulas A formula generally has some “free parts” that are left open for interpretation. To begin with, the universe is often not fixed, but it is also quite common to write formulas when the universe is understood and fixed. Next, we observe that the formula ∀x P (x) → Q(x) contains the predicate symbols P and Q which can be interpreted in different ways. Depending on the choice of universe and on the interpretation of P and Q, the formula can either be true or false. For example let the universe be N and let P (x) mean that “x is divisible by 4”. Now, if Q(x) is interpreted as “x is odd”, then ∀x (P (x) → Q(x)) is false, but if Q(x) is interpreted as “x is even”, then ∀x (P (x) → Q(x)) is true. However, the precise definition of an interpretation is quite involved and deferred to Chapter 6. 29 In formulas with sequences of quantifiers of the same type one sometimes omits parentheses or even multiple copies of the quantifier. For example one writes ∃xyz instead of ∃x ∃y ∃z. We will not use such a convention in this course. 27 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic 2.4.6 Tautologies and Satisfiability The concepts interpretation, tautology, and satisfiability for predicate logic will be defined in Chapter 6. Informally, a formula is satisfiable if there is an interpretation of the involved symbols that makes the formula true. Hence ∀x (P (x) → Q(x)) is satisfiable as shown above. Moreover, a formula is a tautology (or valid) if it is true for all interpretations, i.e., for all choices of the universe and for all interpretations of the predicates.30 We will use the terms “tautology” and “valid” interchangeably. For example, ∀x (P (x) ∧ Q(x)) → (P (x) ∨ Q(x)) is a tautology, or valid. 2.4.7 Equivalence and Logical Consequence One can define the equivalence of formulas and logical consequence for predi- cate logic analogously to propositional logic, but again the precise definition is quite involved and deferred to Chapter 6. Intuitively, two formulas are equiva- lent if they evaluate to the same truth value for any interpretation of the symbols in the formula. Example 2.24. Recall Example 2.22. The formula can be written in an equivalent form, as: ∀x x = 0 ∨ ∃y (xy = 1) ≡ ∀x ¬(x = 0) → ∃y (xy = 1). The order of identical quantifiers does not matter, i.e., we have for example: ∃x∃y P (x, y) ≡ ∃y∃x P (x, y) and ∀x∀y P (x, y) ≡ ∀y∀x P (x, y). A simple example of a logical consequence is ∀x P (x) |= ∃x P (x). It holds because if P (x) is true for all x in the universe, then it is also true for some (actually an arbitrary) x. (Recall that the universe is non-empty.) Some more involved examples of equivalences and logical consequences are stated in the next section. 30 We will see in Chapter 6 that predicate logic also involves function symbols, and an interpreta- tion also instantiates the function symbols by concrete functions. 2.5. Logical Formulas vs. Mathematical Statements 28 2.4.8 Some Useful Rules We list a few useful rules for predicate logic. This will be discussed in more detail in Chapter 6. We have ∀x P (x) ∧ ∀x Q(x) ≡ ∀x P (x) ∧ Q(x) since if P (x) is true for all x and also Q(x) is true for all x, then P (x) ∧ Q(x) is true for all x, and vice versa. Also,31 ∃x P (x) ∧ Q(x) |= ∃x P (x) ∧ ∃x Q(x) since, no matter what P and Q actually mean, any x that makes P (x)∧Q(x) true (according to the left side) also makes P (x) and Q(x) individually true. But, in contrast, ∃x (P (x) ∧ Q(x)) is not a logical consequence of ∃x P (x) ∧ ∃x Q(x), as the reader can verify. We can write ∃x P (x) ∧ ∃x Q(x) 6|= ∃x (P (x) ∧ Q(x)). We also have: ¬∀x P (x) ≡ ∃x ¬P (x) and ¬∃x P (x) ≡ ∀x ¬P (x). The reader can prove as an exercise that ∃y ∀x P (x, y) |= ∀x ∃y P (x, y) but that ∀x ∃y P (x, y) 6|= ∃y ∀x P (x, y). 2.5 Logical Formulas vs. Mathematical Statements A logical formula is generally not a mathematical statement because the symbols in it can be interpreted differently, and depending on the interpretation, the formula is true or false. Without fixing an interpretation, the formula is not a mathematical statement. 2.5.1 Fixed Interpretations and Formulas as Statements If for a formula F the interpretation (including the universe and the meaning of the predicate and function symbols) is fixed, then this can be a mathematical 31 We point out that defining logical consequence for predicate logic is quite involved (see Chap- ter 6), but intuitively it should be quite clear. 29 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic statement that is either true or false. Therefore, if an interpretation is under- stood, we can use formulas as mathematical statements, for example in a proof with implication steps. In this case (but only if a fixed interpretation is under- stood) it is also meaningful to say that a formula is true or that it is false. Example 2.25. For the universe N and the usual interpretation of < and >, the formula ∃n (n < 4 ∧ n > 5) is false and the formula ∀n (n > 0 → (∃m m < n)) is true. 2.5.2 Mathematical Statements about Formulas As mentioned, logical formulas are often not mathematical statements them- selves, but one makes mathematical statements about formulas. Examples of such mathematical statements are: F is valid (i.e., a tautology, also written as |= F ), F is unsatisfiable, F |= G. The statement “F is valid” is a mathematical statement (about the formula F ). Therefore we may for example write F is valid =⇒ G is valid, (2.1) as a mathematical statement about the formulas F and G. This statement is different from the statement F |= G. In fact, for any formulas F and G, the statement F |= G implies statement (2.1), but the converse is generally false: Lemma 2.4. For any two formulas F and G, if F |= G, then (2.1) is true. Proof. F |= G states that for every interpretation, if F is true (for that interpre- tation), then also G is true (for that interpretation). Therefore, if F is true for every interpretation, then also G is true for every interpretation, which is state- ment (2.1). 2.6 Some Proof Patterns In this section we discuss a few important proof patterns (which we could also call proof methods or proof techniques). Such a proof pattern can be used to prove one step within a longer proof, or sometimes also to directly prove a the- orem of interest. Many proof patterns correspond to logical deduction rules. One can define a logical calculus consisting of such deduction rules, but we will defer the discussion of this topic to Chapter 6. Often, a given statement can be proved in different ways, i.e., by using different proof patterns. 2.6. Some Proof Patterns 30 2.6.1 Composition of Implications We first explain why the composition of implications, as occurring in many proofs, is sound. Definition 2.12. The proof step of composing implications is as follows: If S =⇒ T and T =⇒ U are both true, then one concludes that S =⇒ U is also true. The soundness of this principle is explained by the following lemma of propositional logic which was already stated in Example 2.13. Lemma 2.5. (A → B) ∧ (B → C) |= A → C. Proof. One writes down the truth tables of the formulas (A → B) ∧ (B → C) and A → C and checks that whenever the first evaluates to true, then also the second evaluates to true. 2.6.2 Direct Proof of an Implication Many statements of interest (as intermediate steps or as the final statement of interest) are implications of the form S =⇒ T for some statements S and T.32 Definition 2.13. A direct proof of an implication S =⇒ T works by assuming S and then proving T under this assumption. 2.6.3 Indirect Proof of an Implication Definition 2.14. An indirect proof of an implication S =⇒ T proceeds by assum- ing that T is false and proving that S is false, under this assumption. The soundness of this principle is explained by the following simple lemma of propositional logic, where A stands for “statement S is true” and B stands for “statement T is true”. Lemma 2.6. ¬B → ¬A |= A → B. Proof. One can actually prove the stronger statement, namely that ¬B → ¬A ≡ A → B, simply by examination of the truth table which is identical for both formulas ¬B → ¬A and A → B. √ Example 2.26. Prove the following claim: If x > 0 is irrational, √ then also x is irrational. The indirect proof proceeds by assuming that x is not irrational and 32 Recall Section 2.1.2. 31 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic showing that then x is also not irrational. Here “not irrational” means rational, i.e., we prove √ x is rational =⇒ x is rational √ √ Assume hence that x is rational, i.e., that x = m/n for m, n ∈ Z. This means that x = m2 /n2 , i.e., x is the quotient of two natural numbers (namely m2 and n2 ) and thus is rational. This completes the proof of the claim. 2.6.4 Modus Ponens Definition 2.15. A proof of a statement S by use of the so-called modus ponens proceeds in three steps: 1. Find a suitable mathematical statement R. 2. Prove R. 3. Prove R =⇒ S. The soundness of this principle is explained by the following lemma of propositional logic. Again, the proof is by a simple comparison of truth tables. Lemma 2.7. A ∧ (A → B) |= B. Examples will be discussed in the lecture and the exercises. 2.6.5 Case Distinction Definition 2.16. A proof of a statement S by case distinction proceeds in three steps: 1. Find a finite list R1 ,... , Rk of mathematical statements (the cases). 2. Prove that at least one of the Ri is true (at least one case occurs). 3. Prove Ri =⇒ S for i = 1,... , k. More informally, one proves for a complete list of cases that the statement S holds in all the cases. The soundness of this principle is explained by the following lemma of propositional logic. Lemma 2.8. For every k we have (A1 ∨ · · · ∨ Ak ) ∧ (A1 → B) ∧ · · · ∧ (Ak → B) |= B. Proof. For a fixed k (say k = 2) one can verify the statement by examination of the truth table. The statement for general k can be proved by induction (see Section 2.6.10). 2.6. Some Proof Patterns 32 Note that for k = 1 (i.e., there is only one case), case distinction corresponds to the modus ponens discussed above. Example 2.27. Prove the following statement S: The 4th power of every natural number n, which is not divisible by 5, is one more than a multiple of 5. To prove the statement, let n = 5k + c, where 1 ≤ c ≤ 4. Using the usual binomial formula (a + b)4 = a4 + 4a3 b + 6a2 b2 + 4ab3 + b4 we obtain: n4 = (5k + c)4 = 54 k 4 + 4 · 53 k 3 c + 6 · 52 k 2 c2 + 4 · 5kc3 + c4. Each summand is divisible by 5, except for the last term c4. The statement S is hence equivalent to the statement that c4 is one more than a multiple of 5, for 1 ≤ c ≤ 4. This statement S can be proved by case distinction, i.e., by considering all four choices for c. For c = 1 we have c4 = 1, which is trivially one more than a multiple of 5. For c = 2 we have c4 = 16, which is also one more than a multiple of 5. The same is true for c = 3 where c4 = 81 and for c = 4 where c4 = 256. This concludes the proof. With a few insights from number theory and algebra we will see later that the above statement holds when 5 is replaced by any odd prime number. 2.6.6 Proofs by Contradiction Definition 2.17. A proof by contradiction of a statement S proceeds in three steps: 1. Find a suitable mathematical statement T. 2. Prove that T is false. 3. Assume that S is false and prove (from this assumption) that T is true (a contradiction). In many cases, the proof steps appear in a different order: One starts from assuming that S is false, derives statements from it until one observes that one of these statements is false (i.e., is the statement T in the above description). In this case, the fact that T is false (step 2) is obvious and requires no proof. The soundness of this principle is explained by the following lemma of propositional logic which can again be proved by comparing the truth tables of the involved formulas. Lemma 2.9. (¬A → B) ∧ ¬B |= A. Since ¬A → B is equivalent to A ∨ B, the principle of a proof by contradic- tion can alternatively be described as follows: To prove S, one proves for some statement T that either S or T is true (or both) and that T is false. This is justified because we have (A ∨ B) ∧ ¬B |= A. 33 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic √ Example 2.28. We discuss the classical proof of three statement that 2 is irra- tional. (This is the statement S to be proved.) Recall (from basic number theory) that a number a is rational if and only if a = m/n (i.e., m = an) for two relatively prime33 integers m and n (i.e., with gcd(m, n) = 1).34 The proof by contradiction starts by assuming that S is false and deriving, from this assumption, a false statement T. In the following derivation we may use formulas as a compact way of writing statements, but the derivation itself is “normal” mathematical reasoning and is not to be understood as a formula- based logical reasoning.35. √ S is false ⇐⇒ 2 is rational. ⇐⇒ ∃m ∃n m2 = 2n2 ∧ gcd(m, n) = 1 We now consider, in isolation, the statement m2 = 2n2 appearing in the above formula, derive from it another statement (namely gcd(m, n) ≥ 2), and then plug this into the above formula. Each step below is easy to verify. For arbitrary m and n we have. m2 = 2n2 =⇒ m2 is even. =⇒ m is even. =⇒ 4 divides m2. =⇒ 4 divides 2n2 (also using m2 = 2n2 ). =⇒ 2 divides n2. =⇒ n is even. =⇒ gcd(m, n) ≥ 2 (also using that m is even) Hence we have ∃m ∃n m2 = 2n2 ∧ gcd(m, n) = 1. =⇒ ∃m ∃n m2 = 2n2 ∧ gcd(m, n) ≥ 2 ∧ gcd(m, n) = 1. | {z } false for arbitrary m and n | {z } statement T , which is false This concludes the proof by contradiction. 33 German: teilerfremd 34 gcd(m, n) denotes the greatest common divisor of m and n (see Section 4.2.3). 35 We can write ⇐⇒. if the implication holds in both directions, but it would be sufficient to always.. replace ⇐⇒ by =⇒. 2.6. Some Proof Patterns 34 2.6.7 Existence Proofs Definition 2.18. Consider a universe X of parameters and consider for each x in X a statement, denoted Sx. An existence proof is a proof of the statement that Sx is true for at least one x ∈ X. An existence proof is constructive if it exhibits an a for which Sa is true, and otherwise it is non-constructive. Example 2.29. Prove that there exists a prime36 number n such that n − 10 and n + 10 are also primes, i.e., prove ∃n prime(n) ∧ prime(n − 10) ∧ prime(n + 10). | {z } Sn A constructive proof is obtained by giving the example n = 13 and verifying that S13 is true. Example 2.30. We prove that there are infinitely many primes by involving a non-constructive existence proof.37 This statement can be rephrased as follows: For every number m there exists a prime p greater than m; as a formula: ∀m ∃p prime(p) ∧ p > m. | {z } Sp To prove this, consider an arbitrary but fixed number m and consider the state- ments Sp parameterized by p: There exists a prime p greater than m, i.e., such that prime(p) ∧ p > m is true. To prove this, we use the known fact (which has been proved) that every natural number n ≥ 2 has at least one prime divisor. We consider the specific number m! + 1 (where m! = 2 · 3 · · · (m − 1) · m). We observe that for all k in the range 2 ≤ k ≤ m, k does not divide m! + 1. In particular, no prime smaller than m divides m! + 1. Because m! + 1 has at least one prime divisor, there exists a prime p greater than m which divides m! + 1. Hence there exists a prime p greater than m.38 2.6.8 Existence Proofs via the Pigeonhole Principle The following simple but powerful fact is known as the pigeonhole principle39. This principle is used as a proof technique for certain existence proofs.40 36 Recall that prime(n) is the predicate that is true if and only if n is a prime number. 37 See also Example 2.21, where different variable names are used. 38 Note that p is not known explicitly, it is only known to exist. In particular, p is generally not equal to m! + 1. 39 German: Schubfachprinzip 40 This principle is often described as follows: If there are more pigeons than pigeon holes, then there must be at least one pigeon hole with more than one pigeon in it. Hence the name of the principle. 35 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic Theorem 2.10. If a set of n objects is partitioned into k < n sets, then at least one of these sets contains at least ⌈ nk ⌉ objects.41 Proof. The proof is by contradiction. Suppose that all sets in the partition have at most ⌈ nk ⌉ − 1 objects. Then the total number of objects is at most k ⌈ nk ⌉

Diskrete Mathematik - ETH Zürich Herbstsemester 2024 - PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue