MATH 221, Formal Logic and Discrete Mathematics Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. Brian W. Kernighan Table Of Contents Chapter 1: Logic and Proofs Chapter 2: Sets, functions, sequences and sums Chapter 3: Algorithms, the integers and matrices Chapter 4: Induction and recursion Chapter 5: Counting Chapter 9: Graphs Chapter 10: Trees 1 13 20 35 44 50 61 Chapter 1: Logic and Proofs Section 1: Propositional logic proposition - a declarative statement that is either true or false, but not both {p, q, r, s} - typically represent a proposition Logical Operators negation: not p read, not p true when p is false connectives: conjunction disjunction exclusive or pq pq pq read, p and q read, p or q read, p x-or q true when both p and q are true true when either p or q are true true when p  q F but p  q T conditional: implication p →q read, p implies q true when p F or p  q T read, p if and only if q true when p → q T and q → p T biconditional: bi-implication pq Important Conditional Constructs p→q statement contrapositive p→q statement converse p→q statement inverse Order of operations q → p q→ p p → q 1. ( ) 2.  3.  4.  5. → 6.  Truth Tables Truth tables start with a systematic and exhaustive list of the possible truth values for each proposition, typically followed by the resulting truth value of the compound propositions leading ultimately to the final truth value. Example ( p  q ) → r There are three variables (simple propositions). There is a compound or, the negation of r and the complete statement. p q r pq r ( p  q ) → r T T T T F F F F T T F F T T F F T F T F T F T F T T T T T T F F F T F T F T F T F T F T F T T T Bit strings consist of a sequence of 0's and 1's, each of which is a bit. The length of the string is the number of bits. By convention 1 denotes true an