Discrete Mathematics: Logic and Sets BSIT

Logic and Sets

1. LOGIC AND SETS Discrete Mathematical Structures

2. SET THEORY Actually, you will see that logic and set theory are very closely related.

3. Set: Collection of objects (“elements”) aA “a is an element of A” “a is a member of A” aA “a is not an element of A” A = {a 1 , a 2 , …, a n } “A contains…” Order of elements is meaningless It does not matter how often the same element is listed. SET THEORY

4. A set is any well-defined list, collection, or class of objects. The objects in sets can be anything: numbers, people, letters, cities, etc. These objects are called the elements or members of the set. Sets will usually be denoted by capital letters. A , B , C , X , . . .  The elements of a set will usually be represented by lower case letters. a , b , c , x , . . . Example: The numbers 2, 4, 5, 8, and 19

5. If a set is defined by actually listing its elements then the elements are separated by commas and enclosed in brackets { }. This is called the tabular form of a set. If the elements of set A are the letters a , e , i , o , and u then we write A = { a , e , i , o , u } If we define a particular set by stating the properties which its elements must satisfy then we use a letter, usually x , to represent an arbitrary element, i.e., B = { x | x is odd} This is read “ B is the set of numbers x such that x is odd” This is called the set-builder form of a set.

6. Sets A and B are equal if and only if they contain exactly the same elements . Examples: SET EQUALITY A = {9, 2, 7, -3}, B = {7, 9, -3, 2} A = B A = {dog, cat, horse}, B = {cat, horse, squirrel, dog} A  B A = {dog, cat, horse}, B = {cat, horse, dog} A = B Computer Science Department

7. “STANDARD” SETS: Natural numbers N = { 1, 2, 3, …} Integers Z = {…, -2, -1, 0, 1, 2, …} Positive Integers Z + = {1, 2, 3, 4, …} Real Numbers R = {47.3, -12, , …} Rational Numbers Q = {1.5, 2.6, -3.8, 15, …} EXAMPLES FOR SETS

8. A =  “empty set/null set” A = {z} Note: zA , but z  {z} A = {{b, c}, {c, x, d}} A = {{x, y}} Note: {x, y} A, but {x, y}  {{x, y}} A = {x | P(x)} “set of all x such that P(x)” A = {x | x N  x > 7} = {8, 9, 10, …} “called set builder notation ” EXAMPLES FOR SETS

9. To define the set of rational numbers Q: Q = {a/b | a Z  b Z + } or Q = {a/b | a Z  b Z  b0} And how about the set of real numbers R? R = {r | r is a real number} EXAMPLES FOR SETS

10. If an object x is a member of a set A , i.e., A contains x as one of its elements, then we write . Which is read “ x is an element of A ” or as “ x belongs to A ” or “ x is in A ” If on the other hand an object x is not a member of a set A , i.e., A does not contain x as one of its elements, then we write Which is read “ x is not an element of A ” Example 1: Let A = { a , b , c , d , e }. Then , and Example 2: Let B = { x | x is odd}. Then , and

11. Computer Science Department Re-write the following in tabular form or set-builder form. Use the variable A and x if necessary . 1. The numbers 2, 4, 5, 8, and 19 2. The solutions of the equation 3. The first five letters of the alphabet: a , b , c , d , e . 4 . The citizens of Singapore. 5. The days: Monday, Tuesday, Wednesday, Thursday, and Friday.

12. Computer Science Department 8: The cities of Australia. 9: The numbers 1, 3, 5, 7, 9, . . . 10: The street of Singapore. 7: The countries Singapore, Malaysia, Indonesia and Thailand. 6: The students in MS101.

13. A  B “A is a subset of B” A  B if and only if every element of A is also an element of B. We can completely formalize this: A  B  x ( xA  xB ) Examples: SUBSETS A = {3, 9}, B = {5, 9, 1, 3}, A  B ? A = {3, 3, 3, 9}, B = {5, 9, 1, 3}, A  B ? A = {1, 2, 3}, B = {2, 3, 4}, A  B ?

14. Useful rules: A = B  (A  B)  (B  A) (A  B)  (B  C)  A  C (see Venn Diagram) SUBSETS U A B C

15. Useful rules:   A for any set A A  A for any set A SUBSETS A set that contains no elements is called an empty set , or a null set . It is denoted by the symbol Æ   Example: Let A be the set of people in the world who are older than 200 years. As there are no people in the known world older than 200 the set A is empty.

16. A  B “A is a proper subset of B” A  B  x ( xA  xB )  x ( xB  xA ) or A  B  x ( xA  xB )  x ( xB  xA ) PROPER SUBSETS:

17. Computer Science Department We call B a proper subset of A if, first B is a subset of A and, secondly if B is not equal to A We denote B is a proper subset of A as means B is a subset of A , where B may be equal to A means B is a proper subset of A , since

18. Example 1: Let A = {1, 2, 3}, B = {1, 2, 3, 4}, then . Which can be written as . Example 2: Let A = {1, 2, 3}, B = {3, 2, 1}, then and , so this cannot be written as

19. Computer Science Department Example Let’s take the set: Every element of is in . . Therefore, (proper subset). Every element of is in . But . So, is a subset , but not a proper subset .  

20. If a set S contains n distinct elements, n N , we call S a finite set with cardinality n. Examples: CARDINALITY OF SETS B = {1, {2, 3}, {4, 5}, 6} |B| = ? C =  |C| = ? D = { x N | x  7000 } |D| = ? E = { x N | x  7000 } E is ? Computer Science Department A = {Mercedes, BMW, Porsche} |A| = 3 V={1 2 3 4 5} |V|=5 A={1,2,3,4, ..., 20} |A| =20 • |  |=0

21. 2 A or P(A) “power set of A” 2 A = {B | B  A} (contains all subsets of A) Examples: A = {x, y, z} 2 A = {  , {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}} A =  2 A = {} Note: |A| = 0, |2 A | = 1 THE POWER SET

22. The power set of a set X , denoted by P( X ), is the set of all subsets of X . If a set X is finite, say X has n elements, then the P( X ) can be shown to have elements. Example: Let X = {0, 1}, then P( X ) = { Æ , {0}, {1}, {0, 1}} Example : Let Y = { a , b , c }, then ?

23. Cardinality of power sets: THE POWER SET . Subsets: . → . . ( The only subset is the empty set itself.)  

24. The ordered n-tuple (a 1 , a 2 , a 3 , …, a n ) is an ordered collection of objects. Two ordered n-tuples (a 1 , a 2 , a 3 , …, a n ) and (b 1 , b 2 , b 3 , …, b n ) are equal if and only if they contain exactly the same elements in the same order. CARTESIAN PRODUCT An ordered -tuple is a sequence (or list) of elements written in a specific order. (a 1, a 2, a 3,…, a n ) where each is an element, and the position matters .  

25. Key Points Order matters → (1,2) . Repetition allowed → (1,1,2) is valid. n = number of elements .   Special Cases 1-tuple (single element): . 2- tuple: called an ordered pair → ( a,b ) . 3- tuple: called an ordered triple → ( a,b,c ) . In general: 4-tuple = quadruple. 5-tuple = quintuple etc.  

26. Examples: Ordered pair : represents a point in the plane. Example: (2,5) Ordered triple : (x,y,z) represents a point in 3D space. Example: (3, -1, 14) Ordered 5-tuple :   (”Anna”, “25”, “Manila”, “Teacher”, “Traveling”) Example: (name, age, city, job, hobby) Note: An ordered -tuple is just a sequence of items where order and position are important (unlike in a set, where order doesn’t matter).  

27. The Cartesian product of two sets is defined as: AB = {(a, b) | aA  bB } Example: A = {x, y}, B = {a, b, c} AB = {(x, a), (x, b), (x, c), (y, a), (y, b), (y, c)} CARTESIAN PRODUCT S = {1,2} and T = { a,b,c } Note that: A =  A =  S x T = ? T x S = ? Note: SxT  TxS !!!!

28. Computer Science Department Cardinality of the Cartesian product • | SxT |=|S|*|T|. Example: A= {John, Peter, Mike} B ={Jane, Ann, Laura} A x B= {(John, Jane),(John, Ann) , (John, Laura), (Peter, Jane), (Peter, Ann) , (Peter, Laura) , (Mike, Jane) , (Mike, Ann) , (Mike, Laura)} | AxB |=9 |A|=3, |B|=3 |A||B|= 9

29. Thank you for listening!