Chapter 5, Set TheorySet definitionsDiscrete Structures CMSC 250 Lecture 28More set conceptsSubsetDo these represent the same sets or not?Formal definitions of set operationsVenn diagramsThe empty set and its propertiesDiscrete Structures CMSC 250 Lecture 29Ordered n-tuplesThe Cartesian productProper subsetDisjoint setsPower setProperties of sets in Theorem 5.2.1Discrete Structures CMSC 250 Lecture 30Properties of sets in Theorem 5.2.2Using Venn diagrams to help find counterexamplesDeriving new properties using rules and Venn diagramsDiscrete Structures CMSC 250 Lecture 32Partitions of a setProofs about power setsRussell’s paradoxThe halting problemDiscrete Structures CMSC 250 Lecture 33Proof for the halting problemWhat if Test is run on itself?1CMSC 250Chapter 5, Set Theory2CMSC 250Set definitionsDefinition of a set:name of set = {list of elements, or a description of the elements}Examples: A = {1,2,3} or B = {x Z | 4 < x < 4} or C = {x Z+ | 4 < x < 4}A set is completely defined by its elements, i.e., {a,b} = {b,a} = {a,b,a} = {a,a,a,b,b,b}3CMSC 250Discrete StructuresCMSC 250Lecture 28April 7, 20084CMSC 250More set conceptsThe universal set (U) is the set consisting of all possible elements in some particular situation under considerationA set can be finite or can be infiniteFor a set S, n(S) or |S| are used to refer to the cardinality of S, which is the number of elements in SThe symbol means "is an element of"The symbol means "is not an element of"5CMSC 250SubsetA B (x U)[x A x B] A is contained in B B contains AA B (x U)[x A x B]Relationship between membership and subset:(x U)[x A {x} A]Definition of set equality: A = B A B B A6CMSC 250Do these represent the same sets or not?X = {x Z | (p Z)[x = 2p]}Y = {y Z | (q Z)[y = 2q 2]}A = {x Z | (i Z)[x = 2i + 1]}B = {x Z | (i Z)[x = 3i + 1]}C = {x Z | (i Z)[x = 4i + 1]}7CMSC 250Formal definitions of set operationsUnion:Intersection:Complement:Difference:}|{ BxAxUxBA }|{ BxAxUxBA }|{ BxAxUxBA }|{' AxUxAAAc'BABA 8CMSC 250Venn diagramsSets are represented as regions (usually circles) in the plane in order to graphically illustrate relationships between them.ABAB9CMSC 250The empty set and its propertiesThe empty set has no elements, so = {}.1. ( sets X)[ X]2. There is only one empty set.3. ( sets X)[X = X]4. ( sets X)[X X' = ]5. ( sets X)[X = ] 6. U' = .7 ' = U10CMSC 250Discrete StructuresCMSC 250Lecture 29April 9, 200811CMSC 250Ordered n-tuplesAn ordered n-tuple takes order and multiplicity into accountThe tuple (x1,x2,x3,…,xn) –has n values–which are not necessarily distinct–and which appear in the order listed(x1,x2,x3,…,xn) = (y1,y2,y3,…,yn) (i 1 i n)[xi = yi ]2-tuples are called pairs, and 3-tuples are called triples12CMSC 250The Cartesian productThe Cartesian product of sets A and B is defined asn(A B) = n(A) n(B)}|),{( BbAabaBA 13CMSC 250Proper subsetBABABA 14CMSC 250Disjoint setsA and B are disjoint A and B have no elements in common (x U)[x A x B x B x A]A B = A and B are disjoint sets15CMSC 250Power setP (A) = the set of all subsets of AExamples- what are P ({a})? P ({a,b,c})? P ()? P ({})? P ({,{}})?16CMSC 250Properties of sets in Theorem 5.2.1Inclusion TransitivityABA BBA BAA BAB CACBBA 17CMSC 250Discrete StructuresCMSC 250Lecture 30April 11, 200818CMSC 250Properties of sets in Theorem 5.2.2 DeMorgan’s for complementDistribution of union and intersectionThere are a number of others as well; see the text or the handout of logical rules and equivalences for the full list'')'( BABA '')'( BABA )()()( CABACBA )()()( CABACBA 19CMSC 250Using Venn diagrams to help find counterexamples )()(?)( CABACBA CBACBA )(?)( 20CMSC 250Deriving new propertiesusing rules and Venn diagrams )()()( CBABCAB )( BAABA )( CBACABA 21CMSC 250Discrete StructuresCMSC 250Lecture 32April 16, 200822CMSC 250Partitions of a setA collection of nonempty sets {A1,A2,…,An} is a partition of the set A if and only if1. A = A1 A2 … An2. A1,A2,…,An are mutually disjointAn infinite set can be partitioned. The partitions can be infinite, or can be finite.23CMSC 250Proofs about power setsProve that ( sets A,B)[A B P(A) P(B)]Prove that( sets A)[n(A) = k n(P(A)) = 2k ]24CMSC 250Russell’s paradoxA set can be an element or member of itself.Consider the set S = {A | A is a set and A A}–Is S an element of itself?25CMSC 250The halting problemIs there a computer program (suppose it’s called Halt) which will read as input any program pgm (plus some input for that program), and be able to determine whether pgm will eventually halt or loop infinitely when run on that input?What if we write a program which just runs another program on some input and sees whether it halts, and prints the result?26CMSC 250Discrete StructuresCMSC 250Lecture 33April 18, 200827CMSC 250Proof for the halting problemSuppose there is a program Halt(pgm, input) which can determine whether any program pgm will halt when run on the input data input, or loop infinitely.Create a new program Test (which also reads another program as input) as follows: void Test(pgm) { if Halt(pgm, pgm) prints that pgm halts then while (true) ; // infinite loop- never quit else // Halt(pgm, pgm) prints that pgm // loops infinitely on input exit}28CMSC 250What if Test is run on itself?Now run Test(Test):–if Test(Test) halts then Halt(Test, Test) will print that Test will halt, in which case Test(Test) loops forever–if Test(Test) loops forever then Halt(Test, Test) will print that Test will loop infinitely, in which case Test(Test)
View Full Document
Unlocking...