Mathematics for Computer Science

2.4. Well Ordered Sets 33 The setNCFis different from the earlier examples. In all the earlier examples, each element was greate ...

Chapter 2 The Well Ordering Principle34 So supposeS.m10/holds. Then 5 j.m10/, because... But if 5 j.m10/, then obviously 5 jm, c ...

2.4. Well Ordered Sets 35 But by the defining equation (2.3),F.m/equals the sumF.m1/CF.m2/ of two even numbers, and so it is al ...

Chapter 2 The Well Ordering Principle36 Since the assumption thatCis nonempty leads to a contradiction, it follows that Cis empt ...

2.4. Well Ordered Sets 37 Problem 2.8. Euler’s Conjecturein 1769 was that there are no positive integer solutions to the equatio ...

Chapter 2 The Well Ordering Principle38 Assume for the purpose of obtaining a contradiction thatCis nonempty. Then by the WOP, t ...

2.4. Well Ordered Sets 39 (e)Conclude that equation (2.9) holds for all positive integers,n. Problem 2.12. Use the Well Ordering ...

Chapter 2 The Well Ordering Principle40 (f)LetWWWDN[Fbe the set consisting of the nonnegative integers along with all the fracti ...

3 Logical Formulas It is amazing that people manage to cope with all the ambiguities in the English language. Here are some sent ...

Chapter 3 Logical Formulas42 3.1 Propositions from Propositions In English, we can modify, combine, and relate propositions with ...

3.1. Propositions from Propositions 43 According to this table, the proposition “PANDQ” is true only whenPandQare both true. Thi ...

Chapter 3 Logical Formulas44 “If Goldbach’s Conjecture is true, thenx^2  0 for every real numberx.” Now, we already mentioned t ...

3.2. Propositional Logic in Computer Programs 45 For example, suppose only conditionsC 2 andC 5 are true, and the system indeed ...

Chapter 3 Logical Formulas46 LetAbe the proposition thatx > 0, and letBbe the proposition thaty > 100. Then we can rewrite ...

3.2. Propositional Logic in Computer Programs 47 equivalent. So we can simplify the code snippet without changing the program’s ...

Chapter 3 Logical Formulas48 English Symbolic Notation NOT.P/ :P (alternatively,P) PANDQ P^Q PORQ P_Q PIMPLIESQ P!Q ifPthenQ P!Q ...

3.3. Equivalence and Validity 49 thecontrapositiveof the implication “P IMPLIESQ.” The truth table shows that an implication and ...

Chapter 3 Logical Formulas50 3.3.2 Validity and Satisfiability Avalidformula is one which isalwaystrue, no matter what truth val ...

3.4. The Algebra of Propositions 51 You can read a disjunctive form for any propositional formula directly from its truth table. ...

Chapter 3 Logical Formulas52 Applying the same reasoning to theFentries of a truth table yields aconjunctive formfor any formula ...