This preview shows page 1-2-3-4-5-6-7-8-9-10-67-68-69-70-71-72-73-74-75-136-137-138-139-140-141-142-143-144-145 out of 145 pages.
AdministrationMidterm 1 is not early after all.We don’t think 3 weeks is enough material to merit a midterm.CS70: Lecture 3. Outline.1. Proofs2. Simple3. Direct4. by Contrapositive5. by Cases6. by ContradictionSimple theorem..Theorem: P =⇒ (P ∨ Q).Proof:IP is true.P ∨ Q is true“ ’anything’ =⇒ true” is trueso X =⇒ (P ∨ Q) is true for all X ,and in particular, P =⇒ (P ∨ Q) is trueIP is false.“false =⇒ ’anything’ ”, is trueso “P =⇒ ’anything’ ” is true.in particular P =⇒ (P ∨ Q) is true.More detailed but the “same” as truth table proof in somesense.Simple theorem..Theorem: P =⇒ (P ∨ Q).Proof:IP is true.P ∨ Q is true“ ’anything’ =⇒ true” is trueso X =⇒ (P ∨ Q) is true for all X ,and in particular, P =⇒ (P ∨ Q) is trueIP is false.“false =⇒ ’anything’ ”, is trueso “P =⇒ ’anything’ ” is true.in particular P =⇒ (P ∨ Q) is true.More detailed but the “same” as truth table proof in somesense.Simple theorem..Theorem: P =⇒ (P ∨ Q).Proof:IP is true.P ∨ Q is true“ ’anything’ =⇒ true” is trueso X =⇒ (P ∨ Q) is true for all X ,and in particular, P =⇒ (P ∨ Q) is trueIP is false.“false =⇒ ’anything’ ”, is trueso “P =⇒ ’anything’ ” is true.in particular P =⇒ (P ∨ Q) is true.More detailed but the “same” as truth table proof in somesense.Simple theorem..Theorem: P =⇒ (P ∨ Q).Proof:IP is true.P ∨ Q is true“ ’anything’ =⇒ true” is trueso X =⇒ (P ∨ Q) is true for all X ,and in particular, P =⇒ (P ∨ Q) is trueIP is false.“false =⇒ ’anything’ ”, is trueso “P =⇒ ’anything’ ” is true.in particular P =⇒ (P ∨ Q) is true.More detailed but the “same” as truth table proof in somesense.Simple theorem..Theorem: P =⇒ (P ∨ Q).Proof:IP is true.P ∨ Q is true“ ’anything’ =⇒ true” is trueso X =⇒ (P ∨ Q) is true for all X ,and in particular, P =⇒ (P ∨ Q) is trueIP is false.“false =⇒ ’anything’ ”, is trueso “P =⇒ ’anything’ ” is true.in particular P =⇒ (P ∨ Q) is true.More detailed but the “same” as truth table proof in somesense.Simple theorem..Theorem: P =⇒ (P ∨ Q).Proof:IP is true.P ∨ Q is true“ ’anything’ =⇒ true” is trueso X =⇒ (P ∨ Q) is true for all X ,and in particular, P =⇒ (P ∨ Q) is trueIP is false.“false =⇒ ’anything’ ”, is trueso “P =⇒ ’anything’ ” is true.in particular P =⇒ (P ∨ Q) is true.More detailed but the “same” as truth table proof in somesense.Simple theorem..Theorem: P =⇒ (P ∨ Q).Proof:IP is true.P ∨ Q is true“ ’anything’ =⇒ true” is trueso X =⇒ (P ∨ Q) is true for all X ,and in particular, P =⇒ (P ∨ Q) is trueIP is false.“false =⇒ ’anything’ ”, is trueso “P =⇒ ’anything’ ” is true.in particular P =⇒ (P ∨ Q) is true.More detailed but the “same” as truth table proof in somesense.Simple theorem..Theorem: P =⇒ (P ∨ Q).Proof:IP is true.P ∨ Q is true“ ’anything’ =⇒ true” is trueso X =⇒ (P ∨ Q) is true for all X ,and in particular, P =⇒ (P ∨ Q) is trueIP is false.“false =⇒ ’anything’ ”, is trueso “P =⇒ ’anything’ ” is true.in particular P =⇒ (P ∨ Q) is true.More detailed but the “same” as truth table proof in somesense.Simple theorem..Theorem: P =⇒ (P ∨ Q).Proof:IP is true.P ∨ Q is true“ ’anything’ =⇒ true” is trueso X =⇒ (P ∨ Q) is true for all X ,and in particular, P =⇒ (P ∨ Q) is trueIP is false.“false =⇒ ’anything’ ”, is trueso “P =⇒ ’anything’ ” is true.in particular P =⇒ (P ∨ Q) is true.More detailed but the “same” as truth table proof in somesense.Simple theorem..Theorem: P =⇒ (P ∨ Q).Proof:IP is true.P ∨ Q is true“ ’anything’ =⇒ true” is trueso X =⇒ (P ∨ Q) is true for all X ,and in particular, P =⇒ (P ∨ Q) is trueIP is false.“false =⇒ ’anything’ ”, is trueso “P =⇒ ’anything’ ” is true.in particular P =⇒ (P ∨ Q) is true.More detailed but the “same” as truth table proof in somesense.Proof by truth table.Theorem: P =⇒ (P ∨ Q).Proof:P Q P ∨ QT T TT F TF T TF F FLook only at appropriate rows. Where theorem condition is true.When P is true since we are proving an implication.Proof by truth table.Theorem: P =⇒ (P ∨ Q).Proof:P Q P ∨ QT T TT F TF T TF F FLook only at appropriate rows. Where theorem condition is true.When P is true since we are proving an implication.Proof by truth table.Theorem: P =⇒ (P ∨ Q).Proof:P Q P ∨ QT T TT F TF T TF F FLook only at appropriate rows. Where theorem condition is true.When P is true since we are proving an implication.Proof by truth table.Theorem: P =⇒ (P ∨ Q).Proof:P Q P ∨ QT T TT F TFTTFFFLook only at appropriate rows. Where theorem condition is true.When P is true since we are proving an implication.An aside from piazza question/answer.Theorem: ¬(P ⇐⇒ Q) =⇒ (P =⇒ ¬Q).Proof:P Q ¬(P ⇐⇒ Q) P =⇒ ¬QT T F FT F T TF T T TF F F TLook only at appropriate rows. Where theorem condition is T.When ¬(P ⇐⇒ Q) is true then P =⇒ ¬Q is true.An aside from piazza question/answer.Theorem: ¬(P ⇐⇒ Q) =⇒ (P =⇒ ¬Q).Proof:P Q ¬(P ⇐⇒ Q) P =⇒ ¬QT T F FT F T TF T T TF F F TLook only at appropriate rows. Where theorem condition is T.When ¬(P ⇐⇒ Q) is true then P =⇒ ¬Q is true.An aside from piazza question/answer.Theorem: ¬(P ⇐⇒ Q) =⇒ (P =⇒ ¬Q).Proof:P Q ¬(P ⇐⇒ Q) P =⇒ ¬QT T F FT F T TF T T TF F F TLook only at appropriate rows. Where theorem condition is T.When ¬(P ⇐⇒ Q) is true then P =⇒ ¬Q is true.Existential statement.How to prove existential statement?Give an example. (Sometimes called ”proof by example.”)Theorem: ∃x ∈ N.x = x2Pf: 0 = 02= 0Existential statement.How to prove existential statement?Give an example. (Sometimes called ”proof by example.”)Theorem: ∃x ∈ N.x = x2Pf: 0 = 02= 0Existential statement.How to prove existential statement?Give an example. (Sometimes called ”proof by example.”)Theorem: ∃x ∈ N.x = x2Pf: 0 = 02= 0Existential statement.How to prove existential statement?Give an example. (Sometimes called ”proof by example.”)Theorem: ∃x ∈ N.x = x2Pf: 0 = 02= 0Existential statement.How to prove existential statement?Give an example. (Sometimes called ”proof by example.”)Theorem: ∃x ∈ N.x = x2Pf: 0 = 02= 0Universal
View Full Document
Unlocking...