Discrete Mathematics Past Paper (BS102 - Fall 2020) PDF

BS102 Discrete Mathematics Chapter 02 Basic Structures Dr. Ahmed Hagag Faculty of Computers and Artificial Intelligence Benha University Fall 2020  Chapter 2: Basic Structures Sets. Functions....

BS102 Discrete Mathematics Chapter 02 Basic Structures Dr. Ahmed Hagag Faculty of Computers and Artificial Intelligence Benha University Fall 2020  Chapter 2: Basic Structures Sets. Functions. Sequences, and Summations. Matrices. @Ahmed Hagag BS102 Discrete Mathematics 2  Sets (1/24) A set is an unordered collection of objects. The objects in a set are called the elements, or members, of the set. A set is said to contain its elements. @Ahmed Hagag BS102 Discrete Mathematics 3  Sets (2/24) 𝑆 = {𝑎, 𝑏, 𝑐, 𝑑} We write 𝑎 ∈ 𝑆 to denote that 𝑎 is an element of the set 𝑆. The notation 𝑒 ∉ 𝑆 denotes that 𝑒 is not an element of the set 𝑆. @Ahmed Hagag BS102 Discrete Mathematics 4  Sets (3/24) The set 𝑂 of odd positive integers less than 10 can be expressed by 𝑂 = {1, 3, 5, 7, 9}. The set of positive integers less than 100 can be denoted by {1, 2, 3, … , 99}. ellipses (…) @Ahmed Hagag BS102 Discrete Mathematics 5  Sets (4/24) Another way to describe a set is to use set builder notation. The set 𝑂 of odd positive integers less than 10 can be expressed by 𝑂 = {1, 3, 5, 7, 9}. @Ahmed Hagag BS102 Discrete Mathematics 6  Sets (5/24) @Ahmed Hagag BS102 Discrete Mathematics 7  Sets (6/24) Interval Notation Closed interval [𝑎, 𝑏] Open interval (𝑎, 𝑏) [𝑎, 𝑏] = {𝑥 | 𝑎 ≤ 𝑥 ≤ 𝑏} [𝑎, 𝑏) = {𝑥 | 𝑎 ≤ 𝑥 < 𝑏} (𝑎, 𝑏] = {𝑥 | 𝑎 < 𝑥 ≤ 𝑏} (𝑎, 𝑏) = {𝑥 | 𝑎 < 𝑥 < 𝑏} @Ahmed Hagag BS102 Discrete Mathematics 8  Sets (7/24) If 𝐴 and 𝐵 are sets, then 𝐴 and 𝐵 are equal if and only if ∀𝑥(𝑥 ∈ 𝐴 ↔ 𝑥 ∈ 𝐵). We write 𝐴 = 𝐵, if 𝐴 and 𝐵 are equal sets. The sets {1, 3 , 5} and {3, 5 , 1} are equal, because they have the same elements. {1 , 3 , 3 , 5 , 5 , 5} is the same as the set {1, 3 , 5} because they have the same elements. @Ahmed Hagag BS102 Discrete Mathematics 9  Sets (8/24) Empty Set There is a special set that has no elements. This set is called the empty set, or null set, and is denoted by ∅. The empty set can also be denoted by { } @Ahmed Hagag BS102 Discrete Mathematics 10  Sets (9/24) Cardinality The cardinality is the number of distinct elements in 𝑆. The cardinality of 𝑆 is denoted by 𝑆. @Ahmed Hagag BS102 Discrete Mathematics 11  Sets (10/24) Example1 𝑆 = {𝑎, 𝑏, 𝑐, 𝑑} 𝑆 =4 𝐴 = {1, 2, 3, 7, 9} ∅= @Ahmed Hagag BS102 Discrete Mathematics 12  Sets (10/24) Example1 𝑆 = {𝑎, 𝑏, 𝑐, 𝑑} 𝑆 =4 𝐴 = {1, 2, 3, 7, 9} 𝐴 =5 ∅= |∅| = 0 @Ahmed Hagag BS102 Discrete Mathematics 13  Sets (11/24) Example2 𝑆 = 𝑎, 𝑏, 𝑐, 𝑑, 2 𝑆 = 𝐴 = {1, 2, 3, {2,3}, 9} 𝐴 = {∅} = { } ∅ = @Ahmed Hagag BS102 Discrete Mathematics 14  Sets (11/24) Example2 𝑆 = 𝑎, 𝑏, 𝑐, 𝑑, 2 𝑆 =5 𝐴 = {1, 2, 3, {2,3}, 9} 𝐴 =5 {∅} = { } ∅ =1 @Ahmed Hagag BS102 Discrete Mathematics 15  Sets (12/24) Infinite A set is said to be infinite if it is not finite. The set of positive integers is infinite. 𝑍 + = {1,2,3, … } @Ahmed Hagag BS102 Discrete Mathematics 16  Sets (13/24) Subset The set 𝐴 is said to be a subset of 𝐵 if and only if every element of 𝐴 is also an element of 𝐵. We use the notation 𝐴 ⊆ 𝐵 to indicate that 𝐴 is a subset of the se𝑡 𝐵. 𝐴 ⊆ 𝐵 ↔ ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵) @Ahmed Hagag BS102 Discrete Mathematics 17  Sets (13/24) Subset The set 𝐴 is said to be a subset of 𝐵 if and only if every element of 𝐴 is also an element of 𝐵. We use the notation 𝐴 ⊆ 𝐵 to indicate that 𝐴 is a subset of the se𝑡 𝐵. (𝑨 ⊆ 𝑩) ≡ (𝑩 ⊇ 𝑨) 𝐴 ⊆ 𝐵 ↔ ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵) @Ahmed Hagag BS102 Discrete Mathematics 18  Sets (13/24) Subset To show that two sets A and B are equal, show that 𝐴 ⊆ 𝐵 and 𝐵 ⊆ 𝐴. @Ahmed Hagag BS102 Discrete Mathematics 19  Sets (14/24) Proper Subset The set 𝐴 is a subset of the set 𝐵 but that 𝐴 ≠ 𝐵, we write 𝐴 ⊂ 𝐵 and say that 𝐴 is a 𝐩𝐫𝐨𝐩𝐞𝐫 𝐬𝐮𝐛𝐬𝐞𝐭 of 𝐵. 𝐴 ⊂ 𝐵 ↔ ∀𝑥 𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵 ∧ ∃𝑥 𝑥 ∈ 𝐵 ∧ 𝑥 ∉ 𝐴 @Ahmed Hagag BS102 Discrete Mathematics 20  Sets (15/24) Example For each of the following sets, determine whether 3 is an element of that set. 1,2,3,4 1, 2, 3, 4 1,2, 1,3 @Ahmed Hagag BS102 Discrete Mathematics 21  Sets (16/24) Venn Diagram 𝐴 = 1,2,3,4,7 𝐵 = 0,3,5,7,9 𝐶 = 1,2 @Ahmed Hagag BS102 Discrete Mathematics 22  Sets (17/24) Venn Diagram 𝐴 = 1,2,3,4,7 𝐵 = 0,3,5,7,9 𝐶 = 1,2 1, 2 4 3, 7 0, 5, 9 Universal Set @Ahmed Hagag BS102 Discrete Mathematics 23  Sets (18/24) Power Set 𝐓𝐡𝐞 𝐬𝐞𝐭 𝐨𝐟 𝐚𝐥𝐥 𝐬𝐮𝐛𝐬𝐞𝐭𝐬. If the set is 𝑆. The power set of 𝑆 is denoted by 𝑃(𝑆). The number of elements in the power set is 2 𝑆 @Ahmed Hagag BS102 Discrete Mathematics 24  Sets (18/24) Power Set 𝐓𝐡𝐞 𝐬𝐞𝐭 𝐨𝐟 𝐚𝐥𝐥 𝐬𝐮𝐛𝐬𝐞𝐭𝐬. If the set is 𝑆. The power set of 𝑆 is denoted by 𝑃(𝑆). The number of elements in the power set is 2 𝑆 𝑆 = 1,2,3 𝑷 𝑺 = 𝟐𝟑 = 𝟖 𝐞𝐥𝐞𝐦𝐞𝐧𝐭𝐬 𝑃 𝑆 = 2𝑆 = ∅, 1 , 2 , 3 , 1,2 , 1,3 , 2,3 , 1,2,3 @Ahmed Hagag BS102 Discrete Mathematics 25  Sets (19/24) Example1 @Ahmed Hagag BS102 Discrete Mathematics 26  Sets (19/24) Example1 @Ahmed Hagag BS102 Discrete Mathematics 27  Sets (20/24) Example2 @Ahmed Hagag BS102 Discrete Mathematics 28  Sets (20/24) Example2 @Ahmed Hagag BS102 Discrete Mathematics 29  Sets (22/24) Cartesian Products Let 𝐴 and 𝐵 be sets. The Cartesian product of 𝐴 and 𝐵, denoted by 𝐴 × 𝐵, is the set of all ordered pairs (𝑎, 𝑏), where 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵. Hence, 𝐴 × 𝐵 = {(𝑎, 𝑏) | 𝑎 ∈ 𝐴 ∧ 𝑏 ∈ 𝐵}. @Ahmed Hagag BS102 Discrete Mathematics 31  Sets (22/24) Cartesian Products - Example Let 𝐴 = 1,2 , and 𝐵 = 𝑎, 𝑏, 𝑐 𝐴×𝐵= 1, 𝑎 , 1, 𝑏 , 1, 𝑐 , 2, 𝑎 , 2, 𝑏 , 2, 𝑐. 𝐴×𝐵 = 𝐴 ∗ 𝐵 =2∗3=6 @Ahmed Hagag BS102 Discrete Mathematics 32  Sets (22/24) Cartesian Products - Example Let 𝐴 = 1,2 , and 𝐵 = 𝑎, 𝑏, 𝑐 𝐴×𝐵= 1, 𝑎 , 1, 𝑏 , 1, 𝑐 , 2, 𝑎 , 2, 𝑏 , 2, 𝑐. 𝐴×𝐵 = 𝐴 ∗ 𝐵 =2∗3=6 Find 𝐵 × 𝐴 ? @Ahmed Hagag BS102 Discrete Mathematics 33  Sets (23/24) The Cartesian product of more than two sets. The Cartesian product of the sets 𝐴1 , 𝐴2 , … , 𝐴𝑛 , denoted by 𝐴1 × 𝐴2 × ⋯ × 𝐴𝑛 , is the set of ordered 𝑛-tuples (𝑎1 , 𝑎2 , … , 𝑎𝑛 ), where 𝑎𝑖 belongs to 𝐴𝑖 for 𝑖 = 1, 2, … , 𝑛. In other words, 𝐴1 × 𝐴2 × ⋯ × 𝐴𝑛 = 𝑎1 , 𝑎2 , … , 𝑎𝑛 𝑎𝑖 ∈ 𝐴𝑖 for 𝑖 = 1, 2, … , 𝑛. @Ahmed Hagag BS102 Discrete Mathematics 34  Sets (24/24) Example: @Ahmed Hagag BS102 Discrete Mathematics 35  Set Operations (1/7) Union Let 𝐴 and 𝐵 be sets. The union of the sets A and B , denoted by 𝐴 ∪ 𝐵, is the set that contains those elements that are either in 𝐴 or in 𝐵 , or in both. @Ahmed Hagag BS102 Discrete Mathematics 36  Set Operations (1/7) Union Let 𝐴 and 𝐵 be sets. The union of the sets A and B , denoted by 𝐴 ∪ 𝐵, is the set that contains those elements that are either in 𝐴 or in 𝐵 , or in both. @Ahmed Hagag BS102 Discrete Mathematics 37  Set Operations (1/7) Union Let 𝐴 and 𝐵 be sets. The union of the sets A and B , denoted by 𝐴 ∪ 𝐵, is the set that contains those elements that are either in 𝐴 or in 𝐵 , or in both. The union of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 2, 3, 5} @Ahmed Hagag BS102 Discrete Mathematics 38  Set Operations (2/7) Intersection Let 𝐴 and 𝐵 be sets. The intersection of the sets A and B , denoted by 𝐴 ∩ 𝐵, is the set that contains those elements that are in both 𝐴 and 𝐵. @Ahmed Hagag BS102 Discrete Mathematics 39  Set Operations (2/7) Intersection Let 𝐴 and 𝐵 be sets. The intersection of the sets A and B , denoted by 𝐴 ∩ 𝐵, is the set that contains those elements that are in both 𝐴 and 𝐵. @Ahmed Hagag BS102 Discrete Mathematics 40  Set Operations (2/7) Intersection Let 𝐴 and 𝐵 be sets. The intersection of the sets A and B , denoted by 𝐴 ∩ 𝐵, is the set that contains those elements that are in both 𝐴 and 𝐵. The intersection of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 3} @Ahmed Hagag BS102 Discrete Mathematics 41  Set Operations (3/7) Disjoint Two sets are called disjoint if their intersection is the empty set. 𝐴∩𝐵 =∅ @Ahmed Hagag BS102 Discrete Mathematics 42  Set Operations (4/7) Difference Let 𝐴 and 𝐵 be sets. The difference of 𝐴 and 𝐵 , denoted by 𝐴 − 𝐵 , is the set containing those elements that are in 𝐴 but not in 𝐵. @Ahmed Hagag BS102 Discrete Mathematics 43  Set Operations (4/7) Difference Let 𝐴 and 𝐵 be sets. The difference of 𝐴 and 𝐵 , denoted by 𝐴 − 𝐵 , is the set containing those elements that are in 𝐴 but not in 𝐵. 𝐴 = 1,3,5 , 𝐵 = 1,2,3 𝐴−𝐵= 5 @Ahmed Hagag BS102 Discrete Mathematics 44  Set Operations (4/7) Difference @Ahmed Hagag BS102 Discrete Mathematics 45  Set Operations (5/7) Complement Let 𝑈 be the universal set. The complement of the set 𝐴 , denoted by 𝐴ҧ An element 𝑥 belongs to 𝑈 if and only if 𝑥 ∉ 𝐴. @Ahmed Hagag BS102 Discrete Mathematics 46  Set Operations (5/7) Complement Let 𝑈 be the universal set. The complement of the set 𝐴 , denoted by 𝐴ҧ An element 𝑥 belongs to 𝑈 if and only if 𝑥 ∉ 𝐴. 𝑈 = 1,2,3,4,5 , 𝐴 = 1,3 𝐴ҧ = 2,4,5 @Ahmed Hagag BS102 Discrete Mathematics 47  Set Operations (5/7) Complement @Ahmed Hagag BS102 Discrete Mathematics 48  Set Operations (6/7) Generalized Unions @Ahmed Hagag BS102 Discrete Mathematics 49  Set Operations (6/7) Generalized Unions @Ahmed Hagag BS102 Discrete Mathematics 50  Set Operations (7/7) Generalized Intersections @Ahmed Hagag BS102 Discrete Mathematics 51  Set Operations (7/7) Generalized Intersections @Ahmed Hagag BS102 Discrete Mathematics 52  Set Identities (1/8) @Ahmed Hagag BS102 Discrete Mathematics 53  Set Identities (2/8) @Ahmed Hagag BS102 Discrete Mathematics 54  Set Identities (3/8) Example1 @Ahmed Hagag BS102 Discrete Mathematics 55  Set Identities (4/8) Example1 – Answer @Ahmed Hagag BS102 Discrete Mathematics 56  Set Identities (5/8) @Ahmed Hagag BS102 Discrete Mathematics 57  Set Identities (6/8) @Ahmed Hagag BS102 Discrete Mathematics 58  Set Identities (7/8) Example2 @Ahmed Hagag BS102 Discrete Mathematics 59