Peer Instruction in Discrete Mathematics

Explore the world of discrete mathematics with Dr. Cynthia Bailey Lee and Dr. Shachar Lovett through peer instruction. Dive into topics like step-by-step equivalence proofs and the equivalence of logical operators. Discover the different methods to show propositions are equivalent and delve into logical equivalences, questioning the necessity of certain logical connectives.

• Discrete Mathematics
• Peer Instruction
• Equivalence Proofs
• Logical Operators
• Creative Commons

haer862 Follow

Uploaded on Sep 19, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Creative Commons License CSE 20 Discrete Mathematics Dr. Cynthia Bailey Lee Dr. Shachar Lovett Peer Instruction in Discrete Mathematics by Cynthia Leeis licensed under a Creative Commons Attribution- NonCommercial-ShareAlike 4.0 International License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org.

2. 2 Today s Topics: 1. Step-by-step equivalence proofs 2. Equivalence of logical operators

3. 3 1. Step-by-Step Equivalence Proofs

4. 4 Two ways to show two propositions are equivalent 1. Using a truth table Make a truth table with a column for each Equivalent iff the T/F values in each row are identical between the two columns 2. Using known logical equivalences Step-by-step, proof-style approach Equivalent iff it is possible to evolve one to the other using only the known logical equivalence properties

5. 5 Logical Equivalences 1. (p q r) (p q r) ( p q r) ( p q r) (p (q r)) (p ( q r)) ( p (q r)) ( p ( q r)) 2. (p ((q r) ( q r))) ( p ((q r) ( q r))) a) Substitute s = (q r) ( q r) gives (p s) ( p s) b) (s p) (s p) c) s (p p) d) s t e) s, substitute back for s gives: 3. (q r) ( q r) Which law is NOT used? A. Commutative B. Associative C. Distributive D. Identity E. DeMorgan s

6. 6 3. Equivalence of Logical Operators Do we really need IMPLIES and XOR?

7. 7 Are all the logical connectives really necessary? You already know that IMPLIES is not necessary p q p q What about IFF? A. Replace with ( p q) Replace with ( p q) (p q) C. Replace with (p q) (p q) D. Replace with something else XOR is necessary B. E.

8. 8 Are all the logical connectives really necessary? You already know that IMPLIES is not necessary p q p q What about XOR? A. Replace with ( p q) Replace with ( p q) (p q) C. Replace with (p q) (p q) D. Replace with something else XOR is necessary B. E.

9. 9 Are all the logical connectives really necessary? You already know that IMPLIES is not necessary p q p q What about AND? A. Replace with ( p q) Replace with ( p q) (p q) C. Replace with (p q) (p q) D. Replace with something else AND is necessary B. E.

10. 10 Are all the logical connectives really necessary? Not necessary: IF IFF XOR AND We can replicate all these using just two: OR NOT Can we get it down to just one?? A. YES, just OR B. YES, just NOT C. NO, there must be at least 2 connectives D. Other

11. 11 It turns out, yes, you can manage with just one! But it is one we haven t learned yet: NAND (NOT AND) Another option is NOR (NOT OR) Their truth tables look like this: p q P NOR q p q P NAND q T T F F T F T F F F F T T T F F T F T F F T T T Ex: p OR q (p NAND p) NAND (q NAND q)

12. 12 Using NAND to simulate the other connectives NOT p is equivalent to A. p NAND p B. (p NAND p) NAND p C. p NAND (p NAND p) D. NAND p E. None/more/other p q P NAND q T T F F T F T F F T T T

13. 13 Using NAND to simulate the other connectives p AND q is equivalent to A. p NAND q B. (p NAND p) NAND (q NAND q) C. (p NAND q) NAND (p NAND q) D. None/more/other p q P NAND q T T F F T F T F F T T T

14. 14 Using NAND to simulate the other connectives p OR q is equivalent to A. p NAND q B. (p NAND p) NAND (q NAND q) C. (p NAND q) NAND (p NAND q) D. None/more/other p q P NAND q T T F F T F T F F T T T