Peer Instruction in Discrete Mathematics
Engage in peer instruction to explore topics in discrete mathematics such as set theory with Venn diagrams, proving set equality, algebraic proofs, and more. Utilize Creative Commons resources under a non-commercial license for interactive learning experiences.
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.
E N D
Presentation Transcript
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 Today s Topics: 1. Set Theory: Venn Diagrams 2. Set Theory: Proving two sets are equal 3. Set Theory: Power Set and Cross Product
3 Set notations Union: A B = {x:x A x B} Intersection: A B = {x:x A x B} Complement: A =Ac= {x:x A} Difference: A-B = {x:x A x B} Empty set:
4 1. Venn Diagrams
5 If A, B, and C are subsets of U, then ? ? ? ? ? ? = We will prove this using Venn Diagram method First, we need to draw a generic Venn Diagram: U B A C
6 If A, B, and C are subsets of U, then ? ? ? ? ? ? = Which area(s) represent ? ? ? A. 1,2 2,5,8 C. 1,2,3,4 D. 3,4 Other/none/more B. U B A E. C
7 If A, B, and C are subsets of U, then ? ? ? ? ? ? = Which area(s) represent ? ? ? A. 1,4 2,3 C. 8,7 D. 5,6 Other/none/more B. U B A E. C
8 If A, B, and C are subsets of U, then ? ? ? ? ? ? = Which area(s) represent ? ? ? A = 2,3,5,6 B = 3,4,6,7 A B = 2,5 U B A A-C = 2,3 B-C = 3,4 A-B = 2,5 There is no number that appears in all three lists, so the intersection is empty set C
9 If A, B, and C are subsets of U, then ? ? ? ? ? ? = Algebraic proof: ? ? ? ? ? ? = ? ?? ? ?? ? ?? (by definition of set difference, and by associative law removing parentheses) = ? ?? ?? ? (?? ?) (by commutative law, and by associative law adding parentheses) = ? ?? ?? ? (by complement law) = (by universal bound law)
10 2. Proving two sets are equal
11 Set equality Given sets X and Y, X = Y means: ? ? So we can use our proof template for if and only if to show that two sets are equal (Your book shows a different way, chain of iffs ) Recall: ? ?is equivalent to? ? AND? ? IFF proof template says do this as two proofs: 1. Prove ? ? 2. Next, prove ? ? (Each part uses the proving implications template) ?, ? ?
12 Set equality Another take: one way to prove that X=Y is to prove that both X Y Y X
13 Set equality Can also prove directly Claim: (A ) =A Proof: A ={x: x A} (A ) = {x: x A } = {x: x A}
14 3. Power Set and Cross Product
15 Power Sets For any set A, let P(A) be its power set, which is the set of all its subsets Note that A is itself a member of P(A). Recall: denotes the empty set. Question: What is P({1,2})? A. {1, 2, {1,2}} {{1}, {2}, {1,2}, } C. {1, 2, {1,2}, {2,1}} D. None/other/more than one B.
16 Cross Product For any sets A and B, let A x B = {(x, y); x A and y B} Question: What is {1,2} x {1, 2, 3} ? A. {1, 2, 3} {(1,1), (2,2), ( ,3)} C. {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)} D. {(1),(1,2),(1,3),(2),(2,3)} None/other/more than one B. E.
