Discrete Mathematics.pdf
Transcript
DISCRETE MATHEMATICS I for SE Engr. Marian Mie Alimo-ot EMATH 1105 Engr. Yeseil Sacramento EMath 1105 – DISCRETE MATHEMATICS I for SE CHAPTER 1: BASIC STRUCTURES...
DISCRETE MATHEMATICS I for SE Engr. Marian Mie Alimo-ot EMATH 1105 Engr. Yeseil Sacramento EMath 1105 – DISCRETE MATHEMATICS I for SE CHAPTER 1: BASIC STRUCTURES SETS FUNCTIONS SEQUENCES AND SUMMATIONS MATRICES BASIC CONCEPTS OF A SET EMath 1105 – DISCRETE MATHEMATICS I for SE BASIC CONCEPTS OF A SET ✓ A set is an unordered collection of objects, called elements or members of the set. ✓ It is common for sets to be denoted using uppercase letters. Lowercase letters are usually used to denote elements of sets. EMath 1105 – DISCRETE MATHEMATICS I for SE THE BASIC CONCEPTS OF A SET EMath 1105 – DISCRETE MATHEMATICS I for SE WAYS TO DESCRIBE A SET: ROSTER METHOD EXAMPLES: Roster Method Sometimes the roster method is used to describe a set without listing all its members. Some members of the set are listed, and then ellipses (...) are used when the general pattern of the elements is obvious. EMath 1105 – DISCRETE MATHEMATICS I for SE WAYS TO DESCRIBE A SET: SET BUILDER NOTATION EMath 1105 – DISCRETE MATHEMATICS I for SE WAYS TO DESCRIBE A SET: SET BUILDER NOTATION Some important Sets: EMath 1105 – DISCRETE MATHEMATICS I for SE WAYS TO DESCRIBE A SET: INTERVAL NOTATION EMath 1105 – DISCRETE MATHEMATICS I for SE ADDITIONAL EXAMPLES: DESCRIBING A SET What is the set of all fingers? Solution: P = {thumb, index, middle, ring, little} P = {thumb, pointer, middle, fourth, pinky} EMath 1105 – DISCRETE MATHEMATICS I for SE ADDITIONAL EXAMPLES: DESCRIBING A SET What is the set of all even whole numbers between 0 and 10? Solution: Q = {2, 4, 6, 8} EMath 1105 – DISCRETE MATHEMATICS I for SE ADDITIONAL EXAMPLES: DESCRIBING A SET Which of the following is the set of all suits in a standard deck of playing cards? (a) R = {ace, two, three, four, five, six, seven, eight, nine, ten, jack, queen, king} (b) S = {hearts, diamonds, clubs, spades} (c) T = {jokers} Answer: (b) (d) None of the above. EMath 1105 – DISCRETE MATHEMATICS I for SE ADDITIONAL EXAMPLES: DESCRIBING A SET Which of the following is the set of all types of matter? (a) X = {iron, aluminum, nickel, copper, gold, silver} (b) Y = {hydrogen, oxygen, nitrogen, carbon dioxide} (c) Z = {liquids, solids, gases, plasmas} (d) None of the above. Answer: (c) EMath 1105 – DISCRETE MATHEMATICS I for SE UNIVERSAL SET AND EMPTY SET EMath 1105 – DISCRETE MATHEMATICS I for SE SOME IMPORTANT THINGS TO REMEMBER EMath 1105 – DISCRETE MATHEMATICS I for SE SET EQUALITY EMath 1105 – DISCRETE MATHEMATICS I for SE SUBSETS EMath 1105 – DISCRETE MATHEMATICS I for SE SUBSETS EMath 1105 – DISCRETE MATHEMATICS I for SE BASIC CONCEPTS OF A SET EMath 1105 – DISCRETE MATHEMATICS I for SE Example: 𝐿𝑒𝑡 𝑋 = −3, 0, 5 , 𝑌 = 0, 5, −3 , 𝑎𝑛𝑑 𝑍 = 0,5. 𝑇𝑟𝑢𝑒 𝑜𝑟 𝐹𝑎𝑙𝑠𝑒. 1. Z ⊂ X 4. X = Y 2. X ⊂ Y 5. X ≠ Z 3. Z ⊂ Y 6. ⊘⊂ X EMath 1105 – DISCRETE MATHEMATICS I for SE BASIC CONCEPTS OF A SET Finite Set – a set which contains a definite number of elements Examples: 1. The set of all colors in the rainbow. 2. N = {x|x ∈ N, x < 7} 3. P = {2, 3, 5, 7, 11, 13, 17, … , 97} EMath 1105 – DISCRETE MATHEMATICS I for SE BASIC CONCEPTS OF A SET Infinite Set – a set whose elements cannot be listed, i.e., set containing never ending elements Examples: 1. Set of all points in a plane. 2. A = {x|x ∈ N, x > 1} 3. B = {x|x ∈ W, x = 2n} EMath 1105 – DISCRETE MATHEMATICS I for SE BASIC CONCEPTS OF A SET: POWER SET Determine the power set of A = {1, 2, 3} P(A) = {{1,2,3} ,{1,2} ,{1,3} ,{2,3} ,{1} ,{2} ,{3} ,⊘} EMath 1105 – DISCRETE MATHEMATICS I for SE BASIC CONCEPTS OF A SET: SET CARDINALITY EMath 1105 – DISCRETE MATHEMATICS I for SE PRACTICE! PRACTICE! PRACTICE! If U = 1, 3, 5, 7, 9, 11, 13 then which of the following are subsets of U? A = {0} B = {2, 4} C = {1, 9, 5, 13} D = {5, 11, 1} E = {13, 7, 9, 11, 5, 3, 1} F = {2, 3, 4, 5} Answer: (C,D,E) EMath 1105 – DISCRETE MATHEMATICS I for SE PRACTICE! PRACTICE! PRACTICE! Which of the following sets is a universal set for the other four sets? (a) The set of even natural numbers. (b) The set of odd natural numbers (c) The set of integers. (d) The set of negative numbers. (e) The set of natural numbers. Answer: (C) EMath 1105 – DISCRETE MATHEMATICS I for SE PRACTICE! PRACTICE! PRACTICE! Find the number of subsets for the following set (a) containing 5 elements (b) whose cardinal number is 9 Answer: a=32; b=512 EMath 1105 – DISCRETE MATHEMATICS I for SE PRACTICE! PRACTICE! PRACTICE! State whether TRUE or FALSE. (a) quadrilateral ⊂ polygon (b) whole numbers ⊂ natural numbers Answer: a=TRUE, b=FALSE; c=TRUE; d=TRUE (c) {a} ∈ {d, e, f, a} (d) natural numbers ⊂ whole numbers e=TRUE; f=FALSE; g=FALSE (e) natural numbers ⊂ integers (f) 0 ∈ ⊘ (g) ⊘ ∈ {1, 2, 3} EMath 1105 – DISCRETE MATHEMATICS I for SE INSTRUCTION: Indicate TRUE if the statement is correct and FALSE if otherwise. 1. 4 ∈ 2, 3, 4 5. 4, 3 ⊂ 2, 3, 4 2. 5 ∉ 2, 3, 4 6. ⊘⊂ 2, 3, 4 7. {} ∈ 1 3. 4, 2, 3 = 2, 3, 4 4. 2, 3, 4 ⊂ 4, 2, 3 EMath 1105 – DISCRETE MATHEMATICS I for SE SETS OPERATIONS AND VENN DIAGRAMS EMath 1105 – DISCRETE MATHEMATICS I for SE SETS OPERATIONS AND VENN DIAGRAMS EMath 1105 – DISCRETE MATHEMATICS I for SE SETS OPERATIONS AND VENN DIAGRAMS EMath 1105 – DISCRETE MATHEMATICS I for SE SETS OPERATIONS AND VENN DIAGRAMS The set of all elements under consideration is called the universal set U. The complement of A (relative to U), denoted by A’, is the set of elements in U that are not in A. EMath 1105 – DISCRETE MATHEMATICS I for SE SETS OPERATIONS AND VENN DIAGRAMS EMath 1105 – DISCRETE MATHEMATICS I for SE CARTESIAN PRODUCT OF TWO SETS ❖ A new set can be constructed by associating every element of one set with every element of another set. ❖ The Cartesian product of two sets A and B, denoted by A x B is the set of all ordered pairs (a, b) such that “a” is a member of A and “b” is a member of B. Ex. {1, 2} x {red, white} = { (1,red), (1,white), (2, red), (2, white) } EMath 1105 – DISCRETE MATHEMATICS I for SE PROPERTIES OF CARTESIAN PRODUCT EMath 1105 – DISCRETE MATHEMATICS I for SE SET OPERATIONS: EXAMPLES Given: S = {1, 2, 3}, T = {1, 3, 5} and U = {2, 3, 4, 5} Then: (a) 𝑆 ∪ 𝑇 (b) 𝑆 ∪ 𝑈 (c) 𝑇 ∪ 𝑈 EMath 1105 – DISCRETE MATHEMATICS I for SE SET OPERATIONS: EXAMPLES Given: S = {1, 2, 3, 5}, T = {1, 3, 4, 5} and U = {2, 3, 4, 5} Then: (a) 𝑆 ∩ 𝑇 (b) 𝑆 ∩ 𝑈 (c) 𝑇 ∩ 𝑈 EMath 1105 – DISCRETE MATHEMATICS I for SE SET OPERATIONS: EXAMPLES (a) Let the universal set be the integers. Then the complement of the even integers is the _______________. (b) U = {1, 2, 3, 4, 5} If S = {1, 2, 3} then S’ = _______. If T = {1, 3, 5} then T’= _______. EMath 1105 – DISCRETE MATHEMATICS I for SE Given: A = {2, 4, 8, 16}; B = {6, 8, 10, 12, 14, 16} U = {positive even integers} Find: (a) 𝐴 ∪ 𝐵 (b) 𝐴 ∩ 𝐵 (c) 𝐴 ∩ 𝐵 ′ (d) Is 𝐴 ⊂ 𝐵? EMath 1105 – DISCRETE MATHEMATICS I for SE Given: U = {10, 20, 30, 40, 50, 60} A = {10}; B = {10, 40, 60} Find: (a) 𝐴 ∪ 𝐵 (b) 𝐴 ∩ 𝐵 ′ (c) 𝐴 ∩ 𝐵 (d) 𝐴 ∪ 𝐵 ′ (d) Is 𝐴 ⊂ 𝐵? EMath 1105 – DISCRETE MATHEMATICS I for SE SET OPERATIONS: EXAMPLES In a group of 100 persons, 72 people can speak English and 43 can speak French. How many can speak English only? How many can speak French only and how many can speak both English and French? EMath 1105 – DISCRETE MATHEMATICS I for SE Practice! Let A, B, C be three sets as shown in the following Venn diagram. For each of the following sets, draw a Venn diagram and shade the area representing the given set. 1. A ∪ 𝐵 ∪ 𝐶 2. A ∩ 𝐵 ∩ 𝐶 3. A ∪ (𝐵 ∩ 𝐶) EMath 1105 – DISCRETE MATHEMATICS I for SE REVIEW: INSTRUCTION: Indicate TRUE if the statement is correct and FALSE if otherwise. 1. 1,2,3,4,5 ∪ 1,2,4,8 ∩ 1,2,3,5,7 = (1,2,3,5) 2. 1,2,3,4,5 ∪ 1,2,4,8 ∩ (1,2,3,5,7) = (1,2,3,4,5) 3. 𝑠𝑒𝑡 𝐴 𝑥 ⊘ = ⊘ 4. 𝑎, 𝑏, 𝑐 𝑥 𝑑, 𝑒 = { 𝑎, 𝑑 , 𝑎, 𝑒 , 𝑏, 𝑑 , 𝑏, 𝑐 , 𝑏, 𝑒 , 𝑐, 𝑑 , 𝑐, 𝑒 } EMath 1105 – DISCRETE MATHEMATICS I for SE REFERENCE: Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 8th Edition: McGrawHill DISCRETE MATHEMATICS I for SE Engr. Marian Mie Alimo-ot EMATH 1105 Engr. Yeseil Sacramento EMath 1105 – DISCRETE MATHEMATICS I for SE CHAPTER 1: BASIC STRUCTURES SETS FUNCTIONS SEQUENCES AND SUMMATIONS MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE Definition of Functions – Given any sets A, B, a function f from (or “mapping”) A to B (𝑓: 𝐴 → 𝐵) is an assignment of exactly one element 𝒇 𝒙 𝑩 to each element 𝒙 𝑨. Note the subtlety – Each and every element of A has a single mapping – Each element of B may be mapped to by several elements in A or not at all 4 EMath 1105 – DISCRETE MATHEMATICS I for SE Graphical Representations – Functions can be represented graphically in several ways: f A B f y a b A x B Like Venn diagrams Graph Plot EMath 1105 – DISCRETE MATHEMATICS I for SE FUNCTIONS Terminology – Let 𝑓: 𝐴 → 𝐵 and 𝑓(𝑎) = 𝑏. Then we use the following terminology: – A is the domain of 𝑓, denoted 𝑑𝑜𝑚(𝑓) – B is the co-domain of 𝑓 – 𝑏 is the image of 𝑎 – 𝑎 is the preimage (antecedent) of 𝑏 – The range of 𝑓 is the set of all images of elements of A, denoted 𝑟𝑛𝑔(𝑓) EMath 1105 – DISCRETE MATHEMATICS I for SE Function: Visualization Preimage Range Image, 𝑓(𝑎) = 𝑏 f a b A B Domain Co-Domain A function, 𝒇: 𝑨 → 𝑩 EMath 1105 – DISCRETE MATHEMATICS I for SE Example: EMath 1105 – DISCRETE MATHEMATICS I for SE Example: Determine the following: EMath 1105 – DISCRETE MATHEMATICS I for SE Example: ANSWER EMath 1105 – DISCRETE MATHEMATICS I for SE Function Addition/Multiplication – We can add and multiply functions 𝑓, 𝑔: 𝑹→𝑹: 𝑓 + 𝑔 : 𝑹→𝑹, 𝑤ℎ𝑒𝑟𝑒 (𝑓 + 𝑔)(𝑥) = 𝑓(𝑥) + 𝑔(𝑥) (𝑓 × 𝑔): 𝑹→𝑹, 𝑤ℎ𝑒𝑟𝑒 (𝑓 × 𝑔)(𝑥) = 𝑓(𝑥) × 𝑔(𝑥) EMath 1105 – DISCRETE MATHEMATICS I for SE Function Composition – For functions 𝑔: 𝐴→𝐵 𝑎𝑛𝑑 𝑓: 𝐵→ 𝐶, there is a special operator called compose (“ ○ ”). – It composes a new function out of 𝑓, 𝑔 by applying 𝒇 to the result of 𝒈. (𝑓 ○ 𝑔): 𝐴→𝐶, where (𝑓 ○ 𝑔)(𝑎) = 𝑓(𝑔(𝑎)). In general, 𝒇 ○ 𝒈 𝒈 ○ 𝒇. 12 EMath 1105 – DISCRETE MATHEMATICS I for SE Sample Problems EMath 1105 – DISCRETE MATHEMATICS I for SE Sample Problems EMath 1105 – DISCRETE MATHEMATICS I for SE INJECTIONS (one-to-one) One-to-one EMath 1105 – DISCRETE MATHEMATICS I for SE SURJECTIONS (onto) Definition: A function 𝒇: 𝑨→𝑩 is onto or surjective or a surjection iff its range is equal to its codomain (𝑏𝐵, 𝑎𝐴: 𝑓(𝑎) = 𝑏). – An onto function maps the set A onto (over, covering) the entirety of the set B, not just over a piece of it. Onto EMath 1105 – DISCRETE MATHEMATICS I for SE BIJECTIONS (both one-to-one and onto) Definition: A function f is a one-to-one correspondence, or a bijection, or reversible, or invertible, iff it is both one- to-one and onto. Both 1-1 and onto 21 EMath 1105 – DISCRETE MATHEMATICS I for SE Sample Problems Example 1: What type of correspondence is given? A. Injective (one-to-one) B. Surjective (onto) C. Bijective (both one-to-one and onto) D.Neither of the correspondence Example 2: What type of correspondence is given? A. Injective (one-to-one) B. Surjective (onto) C. Bijective (both one-to-one and onto) D. Neither of the correspondence Example 3: What type of correspondence is given? A. Injective (one-to-one) B. Surjective (onto) C. Bijective (both one-to-one and onto) D. Neither of the correspondence Example 4: What type of correspondence is given? A. Injective (one-to-one) B. Surjective (onto) C. Bijective (both one-to-one and onto) D. Neither of the correspondence Example 5: What type of correspondence is given? A. Injective (one-to-one) B. Surjective (onto) C. Bijective (both one-to-one and onto) D. Neither of the correspondence EMath 1105 – DISCRETE MATHEMATICS I for SE INVERSE OF A FUNCTION For bijections 𝑓: 𝐴→𝐵, there exists an inverse of 𝑓, which is the unique function such that: −1 f f =I 28 EMath 1105 – DISCRETE MATHEMATICS I for SE Inverse of a function 29 EMath 1105 – DISCRETE MATHEMATICS I for SE Inverse of a function EMath 1105 – DISCRETE MATHEMATICS I for SE Sample Problems EMath 1105 – DISCRETE MATHEMATICS I for SE Sample Problems EMath 1105 – DISCRETE MATHEMATICS I for SE Sample Problems EMath 1105 – DISCRETE MATHEMATICS I for SE FUNCTIONS Some Important Functions In discrete math, we frequently use the following functions over real numbers: x (“floor of x”) is the largest integer x. x (“ceiling of x”) is the smallest integer x. 34 EMath 1105 – DISCRETE MATHEMATICS I for SE FUNCTIONS VISUALIZING FLOOR & CEILING – Real numbers “fall to their floor” or “rise to their ceiling” – Note that if xZ, 3 −x − x 1.6 = 2 2 −x − x 1.6. 1 1.6 = 1 – Note that if xZ, 0 −1.4 = −1 x = x = x. −1 −1.4. −2 −1.4 = −2 −3 −3 −3 = −3 = −3 35 EMath 1105 – DISCRETE MATHEMATICS I for SE Example: Plots with floor/ceiling – Plot of graph of a floor function. f(x) Set of points (x, f(x)) +2 −3 +3 x −2 EMath 1105 – DISCRETE MATHEMATICS I for SE Sample Problem: Floor and Ceiling What is the value of − 3.2 ? A) - 4 B) - 3 C) 3 Answer: - 4 D) 4 EMath 1105 – DISCRETE MATHEMATICS I for SE Sample Problem: Floor and Ceiling What is the value of 1.5? A) 1 B) 2 C) 3 D) 4 Answer: 1 EMath 1105 – DISCRETE MATHEMATICS I for SE Sample Problem: Floor and Ceiling What is the value of 1.5? A) 1 B) 2 C) 3 D) 4 Answer: 2 EMath 1105 – DISCRETE MATHEMATICS I for SE Sample Problem: Floor and Ceiling What is the value of 2 ? A) 1 B) 2 C) 3 D) 4 Answer: 2 EMath 1105 – DISCRETE MATHEMATICS I for SE REFERENCE: Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 8th Edition: McGrawHill DISCRETE MATHEMATICS I for SE Engr. Marian Mie Alimo-ot EMath 1105 Engr. Yeseil Sacramento EMath 1105 – DISCRETE MATHEMATICS I for SE CHAPTER 1: BASIC STRUCTURES SETS FUNCTIONS SEQUENCES AND SUMMATIONS MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE Sequences: Definition EMath 1105 – DISCRETE MATHEMATICS I for SE Sequences: Definition Finite Sequence: Example: 2, 4, 6, 8, 12, 14 (there is a last number) Infinite Sequence: Example: 1, 1/2, 1/3, 1/4, 1/5, … (three dots with no number following indicate that there is no last number) EMath 1105 – DISCRETE MATHEMATICS I for SE Sequences: Definition EMath 1105 – DISCRETE MATHEMATICS I for SE Sequences: Definition EMath 1105 – DISCRETE MATHEMATICS I for SE Sequences: Example Geometric Progression/Sequence Example: 1,2,4,8,16,32, … 2/1 = 2, 4/2 = 2, 8/4 = 2, 16/8 = 2, 32/16 = 2 The common ratio r = 2. EMath 1105 – DISCRETE MATHEMATICS I for SE Sequences: Example Arithmetic Progression/Sequence Example: 11, 7, 3, -1, -5, -9 By observing: 11 – 7 = 4 7–3=4 3 – (-1) = 4 and so on… The arithmetic sequence has a common difference of 4. EMath 1105 – DISCRETE MATHEMATICS I for SE Sequences: Example EMath 1105 – DISCRETE MATHEMATICS I for SE Strings EMath 1105 – DISCRETE MATHEMATICS I for SE Recurrence Relation EMath 1105 – DISCRETE MATHEMATICS I for SE Recurrence Relation EMath 1105 – DISCRETE MATHEMATICS I for SE Recurrence Relation EMath 1105 – DISCRETE MATHEMATICS I for SE Recurrence Relation: Fibonacci Sequence EMath 1105 – DISCRETE MATHEMATICS I for SE Exercises (Sequences) Let f be the function defined by f(n) = 5n where n = (1,2,3,4,5) If f finite or infinite? What are the elements of the sequence? What are the ordered pair in f? EMath 1105 – DISCRETE MATHEMATICS I for SE Answers Let f be the function defined by f(n) = 5n where n = (1,2,3,4,5) If f finite or infinite? Finite Sequence Function What are the elements of the sequence? f=(5,10,15,20,25) What are the ordered pair in f? (1,5),(2,10),(3,15),(4,20),(5,25) EMath 1105 – DISCRETE MATHEMATICS I for SE Exercises (Sequences) Find the next term of each sequence: 1. 1, 6, 11, 16, … 21 2. 1, 8, 27, 64, … 125 3. 1, 3, 6, 10, … 15 4. 20, 17, 13, 8, … 2 5. 1, 3, 5, 7, 9, … 11 EMath 1105 – DISCRETE MATHEMATICS I for SE Exercises (Sequences) Find the 20th element of the arithmetic sequence for which the first element is 14 and the second element is 9. Let: 𝑎!" be the 20th element of the arithmetic sequence d = 9 – 14 = -5 𝑎# = 14 n = 20 𝑎!" = 𝑎# + 𝑛 − 1 𝑑 = 14 + (20-1)(-5) = -81 EMath 1105 – DISCRETE MATHEMATICS I for SE Summations EMath 1105 – DISCRETE MATHEMATICS I for SE Summations EMath 1105 – DISCRETE MATHEMATICS I for SE Summations EMath 1105 – DISCRETE MATHEMATICS I for SE Exercises (Summations) Write the following sums with sigma (Σ )notation: 𝟕 1.2 + 4 + 6 + 8 + 10 + 12 + 14 = # 𝟐𝒋 𝟔 𝒋"𝟏 2. 1 + 3 + 5 + 7 + 9 + 11 = #(𝟐𝒋 − 𝟏) 𝒋"𝟏 𝟓 ! " 3. x − x + x − x + x # $ %& = #(−𝟏)𝒋'𝟏 𝒙𝟐𝒋 𝒋"𝟏 EMath 1105 – DISCRETE MATHEMATICS I for SE Exercises (Summations) Write the expression in expanded form, then find the sum. 1. ∑+)"* −2𝑗 , 2. ∑.-"*(2𝑥 + 1) ) ∑ 3. '(%(𝑖 − 1)(2𝑖 + 1) EMath 1105 – DISCRETE MATHEMATICS I for SE REFERENCE: Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th Edition, McGrawHill, 2012 DISCRETE MATHEMATICS I for SE Engr. Marian Mie Alimo-ot EMath 1105 Engr. Yeseil Sacramento EMath 1105 – DISCRETE MATHEMATICS I for SE CHAPTER 1: BASIC STRUCTURES SETS FUNCTIONS SEQUENCES AND SUMMATIONS MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE MATRICES 𝑎!" − 𝑟𝑜𝑤 2, 𝑐𝑜𝑙𝑢𝑚𝑛 3 EMath 1105 – DISCRETE MATHEMATICS I for SE MATRIX ARITHMETIC - SUM The sum of two matrices of the same size is obtained by adding elements in the corresponding positions. Matrices of different sizes cannot be added, because the sum of two matrices is defined only when both matrices have the same number of rows and the same number of columns. EMath 1105 – DISCRETE MATHEMATICS I for SE MATRIX ARITHMETIC – SUM EMath 1105 – DISCRETE MATHEMATICS I for SE MATRIX ARITHMETIC - PRODUCT Ø A product of two matrices is defined only when the number of columns in the first matrix equals the number of rows of the second matrix. Ø The product of two matrices is not defined when the number of columns in the first matrix and the number of rows in the second matrix are not the same. EMath 1105 – DISCRETE MATHEMATICS I for SE MATRIX ARITHMETIC - PRODUCT EMath 1105 – DISCRETE MATHEMATICS I for SE MATRIX ARITHMETIC - PRODUCT EMath 1105 – DISCRETE MATHEMATICS I for SE TRANSPOSES and POWERS OF MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE TRANSPOSES and POWERS OF MATRICES Ø Multiplying a matrix by an appropriately sized identity matrix does not change this matrix. Ø In other words, when A is an m×n matrix, we have EMath 1105 – DISCRETE MATHEMATICS I for SE TRANSPOSES and POWERS OF MATRICES ! 2 1 Example: A= −1 0 2 1 2 1 2 1 = % % −1 0 −1 0 −1 0 2 1 3 2 = % −1 0 −2 −1 4 3 = −3 −2 EMath 1105 – DISCRETE MATHEMATICS I for SE TRANSPOSES and POWERS OF MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE TRANSPOSES and POWERS OF MATRICES Ø A matrix is symmetric if and only if it is a square matrix and it is symmetric with respect to its main diagonal (which consists of entries that are in the ith row and ith column for some i). EMath 1105 – DISCRETE MATHEMATICS I for SE TRANSPOSES and POWERS OF MATRICES Which of the following matrices is symmetric? 1 1 −2 1 3 A= 1 1 B= 1 0 −1 1 1 3 −1 2 3 0 1 C= 0 2 −1 1 1 −2 EMath 1105 – DISCRETE MATHEMATICS I for SE ZERO-ONE MATRICES Ø A matrix all of whose entries are either 0 or 1 is called a zero–one matrix. Ø Algorithms using these structures are based on Boolean arithmetic with zero–one matrices. Ø This arithmetic is based on the Boolean operations ∧ (meet/AND) and ∨ (join/OR), which operate on pairs of bits, defined by EMath 1105 – DISCRETE MATHEMATICS I for SE ZERO-ONE MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE ZERO-ONE MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE ZERO-ONE MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE ZERO-ONE MATRICES Ø The Boolean product of A and B is obtained in an analogous way to the ordinary product of these matrices, but with addition replaced with the operation ∨ and with multiplication replaced with the operation ∧. EMath 1105 – DISCRETE MATHEMATICS I for SE ZERO-ONE MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE ZERO-ONE MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE ZERO-ONE MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE ZERO-ONE MATRICES Exercise. Perform the given operations below. EMath 1105 – DISCRETE MATHEMATICS I for SE ZERO-ONE MATRICES Answers: EMath 1105 – DISCRETE MATHEMATICS I for SE Inverse of a 2 x 2 Matrix Exchange elements of main diagonal Change sign in elements off main diagonal Divide resulting matrix by the determinant éa b ù A=ê ú ë c d û EMath 1105 – DISCRETE MATHEMATICS I for SE Inverse of a 2 x 2 Matrix Example EMath 1105 – DISCRETE MATHEMATICS I for SE Practice Exercises 1. Find A + B for each of the following. EMath 1105 – DISCRETE MATHEMATICS I for SE Practice Exercises 2. Find AB for each of the following. EMath 1105 – DISCRETE MATHEMATICS I for SE Practice Exercises 3. Find a matrix A that would satisfy the equation. EMath 1105 – DISCRETE MATHEMATICS I for SE REFERENCE: Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 8th Edition: McGrawHill DISCRETE MATHEMATICS Engr. Marian Mie Alimo-ot EMath 1105 Engr. Yeseil Sacramento EMath 1105 – DISCRETE MATHEMATICS I for SE CHAPTER 1: BASIC STRUCTURES SETS FUNCTIONS SEQUENCES AND SUMMATIONS MATRICES EMath 1105 – DISCRETE MATHEMATICS I for SE Exercises: Determine the nth term of the sequence : a) 2, 4, 6, 8, 10, … b) 1, 3, 5, 7,9, … c) 99, 199, 299, 399, 499, … d) 3, -5, 7, -9, 11, … e) 1, 4, 9, 16, 25, … EMath 1105 – DISCRETE MATHEMATICS I for SE Exercises: Find the sum of the first five terms of the sequence given by the recurrence relation :
