Sets Theory - Discrete Mathematics PDF

Sets Theory Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 1 Eng. Dep./Dr. Salar Atroshi Set: A set is a collection of objects of any sort always denoted by capital letters, and its elements denoted by small letters. A={x, y, z}. Set: A set is an un...

Sets Theory Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 1 Eng. Dep./Dr. Salar Atroshi Set: A set is a collection of objects of any sort always denoted by capital letters, and its elements denoted by small letters. A={x, y, z}. Set: A set is an unordered collection of objects, called elements or members of the set. A set is said to contain its elements. We write a ∈ A to denote that a is an element of the set A. The notation a ∉ A denotes that a is not an element of the set A. It is common for sets to be denoted using uppercase letters. Lowercase letters are usually used to denote elements of sets. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 2 Eng. Dep./Dr. Salar Atroshi We can specified any set by one of the following Methods: 1. Roster Method (Tabulation Method): In which the element one enclosed in braces and separated by commas. A={1, 2, 3, x, y}. 2. Rule Method (Predicate): In which a set can be defined by any predicate. T={x/P(x)}, where P(x) is any predicate, then a∈ T when P(a) is true value. A={x/x≤ 4, x∈ N}. 3. A set can be defined by some of its elements. A={1, 2, 3,…….., 15} B={1, 2, 3,…………} Finite Set Infinite Set Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 3 Eng. Dep./Dr. Salar Atroshi Cardinality of a set: the number of elements of any set is called cardinality of a set and denoted by ||. Finite Set: A set is finite if it contains a finite number of distinct elements, otherwise is Infinite Set. Empty Set (Null Set): A set which does not contain any element is called Empty Set or Null Set denoted by ∅ or { }. Singleton Set (Unit Set): A set which contain only one element is called Singleton Set or Unit Set. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 4 Eng. Dep./Dr. Salar Atroshi Standard Sets: N = {0, 1, 2, 3,...}, the set of Natural numbers Z = {... ,−2,−1, 0, 1, 2,...}, the set of Integers Q = {p/q | p ∈ Z, q ∈ Z, and q ≠ 0}, the set of Rational numbers R={ ………., -4,……., -0.5,….., 0,……, 0.5,…….., 4, ………..}, the set of Real numbers Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 5 Eng. Dep./Dr. Salar Atroshi Inclusion and Equality of Sets: Subset: Let A and B be any two sets, if every element of A is an element of B, then A is called Subset of B. i.e. A ⊆ B {∀𝑥, 𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵. Equal Sets: Two sets A and B are said to be equal iff A ⊆ B and B ⊆ A. i.e. A=B (A ⊆ B ∧ B ⊆ A). Proper Subset: A set A is called Proper Subset of B iff A ⊆ B and A ≠ B and denoted by A ⊂ B. i.e. A ⊂ B={A ⊆ B ∧ A ≠ B}. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 6 Eng. Dep./Dr. Salar Atroshi Universal Set: A set is called Universal Set, if it includes every sets under discussion and denoted by U. Power Set: For a set A the collection or family of all subsets of A is called Power Set and denoted by P(A) or 2A. Set Operations: Union of the Sets: If A and B are any two sets, then the Union is the Set of all elements that belong to set A or set B or both denoted by A∪B. i.e. A∪B={x/x∈ A ∨ x∈B}. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 7 Eng. Dep./Dr. Salar Atroshi Intersection of the Sets: If A and B are any two sets, then intersection is the set of all elements that belong to set A and set B denoted by A∩B. i.e. A∩B={x/x∈ A ∧ x∈B}. Disjoint Sets: Two sets A and B are called disjoint iff A∩B=∅. Difference of the Sets: If A and B are any two sets, then the complement of B with respect to A (Difference) is the set of all elements that belong to A but not belong to B denoted by A-B. i.e. A-B={x/x∈ A ∧ x∉B}. B-A={x/x∈ B ∧ x∉A}. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 8 Eng. Dep./Dr. Salar Atroshi Complement of the Set: If U is an Universal set containing A, then U-A is called the complement of a set A denoted by Ac. i.e. Ac={x/x∉A}. Symmetric Difference Set: If A and B are two sets, then the Symmetric Difference Set is the set of all elements that belong to A or B but not both A and B denoted by A⨁B. i.e. A⨁B={x/x∈ A ∧ x∉B}∨{x/x∈ B ∧ x∉A}. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 9 Eng. Dep./Dr. Salar Atroshi Properties of the Symmetric Difference Set ⨁: 1. A⨁B= B⨁A. 2. (A⨁B)⨁C= A⨁(B⨁C). 3. A⨁∅=A. 4. A⨁A=∅. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 10 Eng. Dep./Dr. Salar Atroshi Set Identities: Identity Name A∪A=A Idempotent laws A∩A=A A ∪ (B ∪ C) = (A ∪ B) ∪ C Associative laws A ∩ (B ∩ C) = (A ∩ B) ∩ C A∪B=B∪A Commutative laws A∩B=B∩A A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Distributive laws A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 11 Eng. Dep./Dr. Salar Atroshi Set Identities: Identity Name A∩U=A Identity laws A∪∅=A A∪U=U Domination laws A∩∅ = ∅ A ∪ Ac = U Complement laws A ∩ Ac = ∅ ∅c=U Uc=∅ Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 12 Eng. Dep./Dr. Salar Atroshi Set Identities: Identity Name Acc =A Complementation law (A ∪ B)c =Ac ∩Bc De Morgan’s laws (A ∩ B)c =Ac ∪Bc A ∪ (A ∩ B) = A Absorption laws A ∩ (A ∪ B) = A Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 13 Eng. Dep./Dr. Salar Atroshi Index Family Set: Let J={S1, S2, S3, ………….} and A be family of sets A={AS1, AS2, AS3,…….}, such that for any si∈J we suppose set ASi∈A and also ASi=ASJ, iff si=sj, then A is called an indexed set, J the index of the set and any Asi in A is called an index, index family of sets can be written as: A={Ai}, i∈J. The Union of Index Family Set: Let {Ai}, i∈ I be an indexed set. We define the Union ‫ 𝑖𝐴 𝐼∈𝑖ڂ‬as the set of elements that belong to at least one i∈ I in Ai. i.e. ‫{ = 𝑖𝐴 𝐼∈𝑖ڂ‬x/x ∈ Ai for some i ∈ I} ≡ {𝑥/∃𝑖 ∈ 𝐼, x ∈ 𝐴𝑖}. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 14 Eng. Dep./Dr. Salar Atroshi The Intersection of Index Family Set: Let {Ai}, i∈ I be an indexed set. We define the Intersection ‫ 𝑖𝐴 𝐼∈𝑖ځ‬as the set of elements that belong to all i∈ I in Ai. i.e. ‫{ = 𝑖𝐴 𝐼∈𝑖ځ‬x/x ∈ Ai for all i ∈ I} ≡ {𝑥/∀𝑖 ∈ 𝐼, x ∈ 𝐴𝑖}. Theorem: Let A be a set and {Bi}, i∈ I be an indexed set then: 1. 𝐴 ∪ (‫ 𝑖𝐵 ∪ 𝐴 𝐼∈𝑖ځ=)𝑖𝐵 𝐼∈𝑖ځ‬. 2. 𝐴 ∩ (‫ 𝑖𝐵 ∩ 𝐴 𝐼∈𝑖ڂ=)𝑖𝐵 𝐼∈𝑖ڂ‬. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 15 Eng. Dep./Dr. Salar Atroshi Ordered Pairs: An ordered pair is a pair of two objects (a, b) given in a fixed order. i.e. (a, b)≠(b, a). The Equality of two ordered pairs is defined as (x, y)=(u, v), iff (x=u ⋀ y=v). Ordered Triple: An ordered triple is an order pair, such that the first member is itself an order pair. i.e ((x, y), z). The Equality of two ordered triple is defined as ((x, y), z)=((u, v), w), iff ((x, y)=(u, v) ⋀ z=w). Ordered n Tuples: An ordered n triple is an order pair , whose first element is an n-1 tuples. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 16 Eng. Dep./Dr. Salar Atroshi The Equality of two ordered n tuples is defined as ((x1, x2, x3,…….., xn-1), xn)=((y1, y2, y3,….,yn-1), yn), iff ((x1, x2, x3, …., xn-1)=(y1, y2, y3, ….., yn-1)⋀ (xn=yn)). Cartesian product: Let A and B be two sets, then the set of all order pairs such that the first member of it is an element in A and the second member is an element in B denoted by A×B. i.e. A×B={(a, b)/a ∈A, b∈ B}. Discrete Mathematics/Salahaddin University-Erbil/College of Eng./Software 17 Eng. Dep./Dr. Salar Atroshi