Discrete Maths II Lecture Notes PDF

CSM 166 Lecture One Topic: The Fundamental Counting Principles  Introduction Counting means determining the number of different ways of arranging objects in certain patterns or the number of ways of carrying out a...

CSM 166 Lecture One Topic: The Fundamental Counting Principles  Introduction Counting means determining the number of different ways of arranging objects in certain patterns or the number of ways of carrying out a sequence of tasks. Example1.1, Suppose we want to count the number of ways of making a bit string of length two. Such a problem is small enough that the possible arrangements can be counted by brute force. We can simply make a list of all the possibilities: 00, 01, 10, 11. Therefore having an answer of four (4). If the problem were to determine the number of bit strings of length fifty, the brute force counting becomes an unreasonable alternative. In this case, two basic principles can apply to aid in the counting. These are the Sum Rule and the Product Rule. Emmanuel Kpeglo KNUST 4-2  The Sum Rule The sum rule says that if the sets A and B are disjoint, then A B = A + B All sets mentioned will be finite sets, and if A is a set, A will denote the number of elements in A. I other words, if we can do task 1 in a ways and task 2 in b ways, where none of the set of a ways is the same as any of the set of b ways (the tasks are independent), then there are a + b ways to do one of the two tasks. Example1.2, “In how many different ways we can select either a queen or a six from an ordinary deck of 52 cards?” That task of selecting queen can be done in 4 ways. The 2nd task of selecting a six can be done in 4 ways. These 2 tasks are independent, hence there are 4 + 4 = 8 ways of selecting one card from a deck, and having that card to be either a queen or a six. Compare this question… “In how many ways can we select either a queen or a diamond from a deck of 52 cards?” Not 4 + 13 = 17,why? Emmanuel Kpeglo KNUST 4-3  Extended sum rule If A1 , A2 , A3 ,  , An is a collection of pairwise disjoint sets, then A1  A2  A3    An = A1 + A2 + A3 +  + An Example 1.3, How many ordered pairs of integers (x, y) are there such that 0 < xy ≤ 5 ? { } Solution: Let E k = ( x, y ) ∈ Ζ 2 : xy = k for k = 1, ,5. Then the desired number is E1 + E 2 + E3 + E 4 + E5. We can compute each of these as follows : E1 = {(− 1,−1), (− 1, 1), (1,−1), (1, 1)} E 2 = {(− 2,−1), (− 2, 1)(− 1,−2), (− 1, 2), (1,−2), (1, 2), (2,−1), (2, 1)} E3 = {(− 3,−1), (− 3, 1)(− 1,−3), (− 1, 3), (1,−3), (1, 3), (3,−1), (3, 1)} E 4 = {(− 4,−1), (− 4, 1)(− 2,−2), (− 2, 2), (− 1,−4 ), (− 1, 4 ), (1,−4 ), (1, 4 ), (2,−2 ), (2, 2 ), (4,−1), (4, 1)} E5 = {(− 5,−1), (− 5, 1)(− 1,−5), (− 1, 5), (1,−5), (1, 5), (5,−1), (5, 1)} The desired number is therefore 4 + 8 + 8 + 12 + 8 = 40. Emmanuel Kpeglo KNUST 4-4  The Product Rule The product rule says: A × B = A ⋅ B An explanation of this is that A × B consists of all ordered pairs (a, b) where a ∈ A and b ∈ B. There are A choices for a and then B choices for b. Generally, let A1 , A2 , A3 ,  , An , be finite sets. Then A1 × A2 × A3 ×  × An = A1 ⋅ A2 ⋅ A3 ⋅  ⋅ An If you need to accomplish some task that takes n steps, and there are a1 ways of accomplishing the first step, a2 ways of accomplishing the second step, etc., and an ways of accomplishing the n th step, then there are a1 ⋅ a 2 ⋅  ⋅ a n ways of accomplishing the task. Emmanuel Kpeglo KNUST 4-5  The Product Rule Example 1.5 Suppose we are buying a car with five choices for the exterior color and three choices for the interior color. There is a total of 3(5) = 15 possible color combinations that we can choose from. First task, select an exterior color. There are 5 ways to do that. Second task, select an interior color. There are 3 ways to do that. So the product rule says there are 15 ways total to do both tasks. Note: there is no requirement of independence of tasks when using the product rule. the number of ways of doing the second task must be the same no matter what choice is made for doing the first task. Example 1.6 How many different 2-digit numbers could we form using the digits 1, 2, 3, 4, 5, 6, 7, 8, and 9? Task 1, fill in the left digit, There are 9 ways to do the first task. and Task 2, fill in the right digit. No matter how we do the first task, there are 9 ways to do the second task as well. By the product rule, there are 9(9) = 81 possible such two-digit numbers. COMPARE: Suppose we wanted 2-digit numbers made up of those same nine digits, but we do not want to use a digit more than once in any of the numbers. Emmanuel Kpeglo KNUST 4-6  Using both the sum and product rules Example 1.7 Suppose we wanted to count the number of different possible bit strings of length five that start with either three 0’s or with two 1’s. In how many ways can we do that? Solution: There are 1 x 1 x 1 x 2 x 2 = 4 bit strings of length five starting with three 0’s. Using the same reasoning, there are 1 x 1 x 2 x 2 x 2 = 8 bit strings of length five starting with two 1’s. A bit string cannot both start with three 0’s and also with two 1’s, (in other words, starting with three 0’s and starting with two 1’s are independent). Hence, 4 + 8 = 12 bit strings of length five starting with either three 0’s or two 1’s. Emmanuel Kpeglo KNUST 4-7  Using both the sum and product rules Example 1.8 Count the number of strings on license plates which either consist of three capital English letters, followed by three digits, or consist of two digits followed by four capital English letters. Solution: Let A be the set of strings which consist of three capital English letters followed by three digits, and B be the set of strings which consist of two digits followed by four capital English letters. By the product rule A = 26 3 ⋅ 10 3 and B = 10 2 ⋅ 26 4 Since A  B = φ , by the sum rule the answer is A  B = 263 ⋅103 + 10 2 + 26 4 = 63,273,600 Emmanuel Kpeglo KNUST 4-8  Using both the sum and product rules Example 1.9 Each user on a computer system has a password, which is six to eight characters long, where each character is an uppercase letter or a digit. Each password must contain at least one digit. How many possible passwords are there? Solution: Let P be the total number of possible passwords, and let P6, P7, and P8 denote the number of possible passwords of length 6, 7, and 8, respectively. By the sum rule, P = P6 + P7 + P8. To find P6 it is easier to find the number of strings of uppercase letters and digits that are six characters long, including those with no digits, and subtract from this the number of strings with no digits. 6 By the product rule, the number of strings of six characters is 36 , and the number of strings with no digits is 26 6. 366 − 26 = 1,867,866,560. 6 Hence, P6 = Similarly, we have P7 = 36 7 − 26 7 = 70,332,353,920 and P8 = 368 − 268 = 2,612,282,842,880. Consequently, P = P6 + P7 + P8 = 2,684,483,063,360. Emmanuel Kpeglo KNUST 4-9  The Subtraction Rule and The Division Rule The Subtraction Rule If a task can be done in either a1 ways or a2 ways, then the number of ways to do the task is a1 + a2 minus the number of ways to do the task that are common to the two different ways. Thus A B = A + B − A B The Division Rule There are n/d ways to do a task if it can be done using a procedure that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to way w. Emmanuel Kpeglo KNUST 4-10  The Subtraction Rule and The Division Rule Example 1.11 A computer company receives 350 applications from college graduates for a job planning a line of new web servers. Suppose that 220 of these applicants majored in computer science, 147 majored in business, and 51 majored both in computer science and in business. How many of these applicants majored neither in computer science nor in business? Solution: Finding the number of applicants who majored neither in computer science nor in business, subtract the number of students who majored either in computer science or in business (or both) from the total number of applicants. Let A be the set of students who majored in computer science and B the set of students who majored in business. Then A ∪ B is the set of students who majored in computer science or business (or both), and A ∩ B is the set of students who majored both in computer science and in business. By the subtraction rule the number of students who majored either in computer science or in business (or both) equals |A ∪ B| = |A| + |B| − |A ∩ B| = 220 + 147 − 51 = 316. We conclude that 350 − 316 = 34 of the applicants majored neither in computer science nor in business. Emmanuel Kpeglo KNUST 4-11  The Subtraction Rule and The Division Rule Example 1.12 How many different ways are there to seat four people around a circular table, where two seatings are considered the same when each person has the same left neighbor or the same right neighbor? Solution: We arbitrarily select a seat at the table and label it seat 1. We number the rest of the seats in numerical order, proceeding clockwise around the table. Note that are four ways to select the person for seat 1, three ways to select the person for seat 2, two ways to select the person for seat 3, and one way to select the person for seat 4. Thus, there are 4! = 24 ways to order the given four people for these seats. However, each of the four choices for seat 1 leads to the same arrangement, as we distinguish two arrangements only when one of the people has a different immediate left or immediate right neighbor. Because there are four ways to choose the person for seat 1, by the division rule there are 24 ∕4 = 6 different seating arrangements of four people around the circular table. Emmanuel Kpeglo KNUST 4-12  The Pigeonhole Principle If there are more items than containers, then at least one container must contain more than one item. For example, if a mother has three children, at least two of them have the same sex. Theorem 1.1 (The Generalized Pigeonhole Principle). If n objects are placed into k boxes, then there is at least one box that contains at least ⌈n/k⌉ objects. Proof: We will use a proof by contraposition. Assume not. Then each of the k boxes contains no more than ⌈n/k⌉−1 objects. Notice that ⌈n/k⌉ < n/k + 1 (convince yourself that this is always true). Thus, the total number of objects in the k boxes is at most k (⌈n/k⌉ − 1) < k(n/k + 1 − 1) = n, contradicting the fact that there are n objects in the boxes. Therefore, some box contains at least ⌈n/k⌉ objects. Emmanuel Kpeglo KNUST 4-13  The Pigeonhole Principle Remark A common type of problem asks for the minimum number of objects such that at least r of these objects must be in one of k boxes when these objects are distributed among the boxes. When we have n objects, the generalized pigeonhole principle tells us there must be at least r objects in one of the boxes as long as ⌈n/k⌉ ≥ r. The smallest integer n with n/k > r − 1, namely, n = k(r − 1) + 1, is the smallest integer satisfying the inequality ⌈n/k⌉ ≥ r. Emmanuel Kpeglo KNUST 4-14  The Pigeonhole Principle Example 1.13 What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades, A, B, C, D, and F? Solution: Remember n = k(r − 1) + 1, is the smallest integer satisfying the inequality ⌈n/k⌉ ≥ r. The minimum number of students needed to ensure that at least six students receive the same grade is the smallest integer n such that ⌈n/5⌉ = 6. The smallest such integer is n = 5 ⋅ 5 + 1 = 26. If you have only 25 students, it is possible for there to be five who have received each grade so that no six students have received the same grade. Thus, 26 is the minimum number of students needed to ensure that at least six students will receive the same grade. Emmanuel Kpeglo KNUST 4-15  The Pigeonhole Principle Example1.14 A drawer contains an infinite supply of white, black, and blue socks. What is the smallest number of socks you must take from the drawer in order to be guaranteed that you have a matching pair? Solution: Clearly I could grab one of each color, so three is not enough. But according the Pigeonhole Principle, if I take 4 socks, then I will get at least ⌈n/3⌉ ≥ 2 of the same color (the colors correspond to the boxes). Thus n = k(r − 1) + 1 = 3 ⋅ 1 + 1 = 4 So 4 socks will guarantee a matched pair. Emmanuel Kpeglo KNUST 4-16  The Pigeonhole Principle Example1.15 How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of the same suit are selected? Solution: Using the generalized pigeonhole principle, we see that if n cards are selected, there is at least one box containing at least ⌈n/4⌉ cards. Consequently, we know that at least three cards of one suit are selected if ⌈n/4⌉ ≥ 3. The smallest integer n such that ⌈n/4⌉ ≥ 3 is n = 2 ⋅ 4 + 1 = 9, so nine cards suffice. Note that if eight cards are selected, it is possible to have two cards of each suit, so more than eight cards are needed. Consequently, nine cards must be selected to guarantee that at least three cards of one suit are chosen. One good way to think about this is to note that after the eighth card is chosen, there is no way to avoid having a third card of some suit. Emmanuel Kpeglo KNUST 4-17  The Pigeonhole Principle Example1.16 How many must be selected from a standard deck of 52 cards to guarantee that at least three hearts are selected? Solution: We do not use the generalized pigeonhole principle to answer this question, because we want to make sure that there are three hearts, not just three cards of one suit. Note that in the worst case, we can select all the clubs, diamonds, and spades, 39 cards in all, before we select a single heart. The next three cards will be all hearts, so we may need to select 42 cards to get three Emmanuel Kpeglo KNUST 4-18  Exercise 1 1. To meet the science requirement a student must take one of the following courses: a choice of 5 biology courses, 4 physics courses, or 6 chemistry courses. In how many ways can the one course be selected? 2. A multiple choice test contains 10 questions. There are four possible answers for each question. (a) How many ways can a student complete the test if every question must be answered? (b) How many ways can a student complete the test if questions can be left unanswered? 3. How many license plates can be made using either three digits followed by three uppercase English letters or three uppercase English letters followed by three digits? 4. In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride and the groom are among these 10 people, if (a) the bride must be in the picture? (b) both the bride and groom must be in the picture? (c) exactly one of the bride and the groom is in the picture? Emmanuel Kpeglo-KNUST 4-19  Exercise 1 5. Every student in a discrete mathematics class is either a computer science or a mathematics major or is a joint major in these two subjects. How many students are in the class if there are 38 computer science majors (including joint majors), 23 mathematics majors (including joint majors), and 7 joint majors? 6. A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them. (a) How many balls must she select to be sure of having at least three balls of the same color? (b) How many balls must she 7. There are six professors teaching the introductory discrete mathematics class at a university. The same final exam is given by all six professors. If the lowest possible score on the final is 0 and the highest possible score is 100, how many students must there be to guarantee that there are two students with the same professor who earned the same final examination score? Emmanuel Kpeglo-KNUST 4-20  CSM 166 Lecture TWO Topic: The Fundamental Counting Principles  Permutations and Combinations A permutation of a set of distinct objects is an ordered arrangement of these objects. We are interested in ordered arrangements of some of the elements of a set. An ordered arrangement of r elements of a set is called an r- permutation. For example, there are six possible permutations of the set A = {a, b, c}. They are … abc, acb, bac, bca, cab,cba. Product rule explains these: there are 3 choices for the first letter, 2 choices for the second letter, and finally 1 choice for the last letter. So the total number of permutations is 3 2 1 = 6. We have shown that a 3-set has 3 2 1 = 6 permutations. Considering all 3. Generally, n-set has n (n − 1) (n − 2) 2 1 = n! permutations. Emmanuel Kpeglo KNUST 2  Permutations and Combinations THEOREM 2.1: If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are P(n, r) = n(n − 1)(n − 2)⋯(n − r + 1) r-permutations of a set with n distinct elements. P (n, r ) = n(n − 1) ⋅  ⋅ (n − r + 1) n(n − 1) ⋅  ⋅ (n − r + 1)(n − r )(n − r − 1) ⋅  ⋅ 2 ⋅ 1 = (n − r )(n − r − 1) ⋅  ⋅ 2 ⋅ 1 n! = (n − r )! NB: Here, the permutation is without replacement Emmanuel Kpeglo KNUST 3  Permutations and Combinations Example 2.1: Suppose that a saleswoman has to visit eight different cities. She must begin her trip in a specified city, but she can visit the other seven cities in any order she wishes. How many possible orders can the saleswoman use when visiting these cities? Solution 2.1: Since the first city is fixed, the remaining seven can be ordered arbitrarily. Consequently, there are 7! = 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 5040 ways for the saleswoman to choose her tour. Emmanuel Kpeglo KNUST 4  Permutations and Combinations Example 2.2: In how many ways can we select a president, vice-president, secretary, and treasurer from a group of 20 people assuming no person can hold more than one office. Solution 2.2: Because no team can occupy more than one position, it is a permutation without replacement. 20! 20 ⋅ 19 ⋅ 18 ⋅ 17 ⋅ 16! P(20,4) = = = 116280 (20 − 4)! 16! Emmanuel Kpeglo KNUST 5  Permutations and Combinations Example 2.3: Suppose that there are eight runners in a race. The winner receives a gold medal, the second place finisher receives a silver medal, and the third-place finisher receives a bronze medal. How many different ways are there to award these medals, if all possible outcomes of the race can occur and there are no ties? 8! 8 ⋅ 7 ⋅ 6 ⋅ 5! Solution 2.3: P(8,3) = = = 336 (8 − 3)! 5! Combinations: If n and r are integers, such that 1 ≤ r ≤ n, then the number of ways to make unordered selections of r objects from a set of n distinct objects but without repetition (i.e., combination without replacement) is as follows: n n! C (n, r ) =   = Emmanuel Kpeglo KNUST  r  r!(n − r )! 6  Permutations and Combinations Example 2.4: There are 22 players on a soccer team. The starting lineup consists of only 11 players. How many possible starting lineups are there, assuming what positions they play is of no concern? Solution 2.4: Because the order of the selection of the players is immaterial and no player can be selected more than once, it is a combination without replacement. 22! C (22,11) = = 705,432 11!(22 − 11)! Emmanuel Kpeglo KNUST 7  Permutations and Combinations Example 2.5: Suppose that there are 9 faculty members in the mathematics department and 11 in the computer science department. How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of three faculty members from the mathematics department and four from the computer science department? Solution 2.5: 9! 11! C (9,3) ⋅C (11,4) = ⋅ = 84 ⋅ 330 = 27,720 3!6! 4!7! Emmanuel Kpeglo KNUST 8  Permutations and Combinations NB: If n and k are integers, such that 0 ≤ k and 1 ≤ n, then the number of ways to make ordered arrangements of k objects from a set of n objects, when repetition of objects allowed (i.e., permutation with replacement) is as follows: n × n ×  × n = nk If n and k are integers, such that 0 ≤ k and 1 ≤ n, then the number of ways to make unordered selections of k objects from a set of n objects, when repetition of objects allowed (i.e., combination with replacement) is as follows:  n + k − 1 (n + k − 1)!   = Emmanuel Kpeglo KNUST  k  k!(n − 1)! 9  Permutations and Combinations Example 2.6: How many solutions does the equation x1 + x2 + x3 = 11 have, where x1, x2, and x3 are nonnegative integers? Solution 2.6: In solving this, we note that a solution corresponds to a way of selecting 11 items from a set with three elements so that x1 items of type one, x2 items of type two, and x3 items of type three are chosen. Hence, the number of solutions is equal to the number of 11- combinations with repetition.  n + k − 1 (n + k − 1)!  3 + 11 − 1 (3 + 11 − 1)! 13!   = therefore   = = = 78  k  k!(n − 1)!  11  11!(3 − 1)! 11!2! Emmanuel Kpeglo KNUST 10  Permutations and Combinations Example 2.7: How many four-letter passwords from the capital letters A to Z inclusive can be made, noting that a letter can be repeated in a password? Solution 2.7: This is a permutation with replacement, as the order of capital letters in a password matters and a capital letter can be used in a password more than once. Noting that n = 26 and k = 4, the number of passwords is thus n × n ×  × n = 26 4 = 456,976 Emmanuel Kpeglo KNUST 11  Permutations and Combinations Example 2.8: How many different strings can be made by reordering the letters of the word SUCCESS? Solution 2.8: Since the letters in SUCCESS are all not same, the answer is not given by the number of permutations of seven letters. This word contains three Ss, two Cs, one U, and one E. Note that the three Ss can be placed among the seven positions in C(7, 3) different ways, then the two Cs can be placed in C(4, 2) ways, then U can be placed in C(2, 1) ways, then E in C(1, 1) way. Therefore… 7! 4! 2! 1! 7! C (7,3)C (4,2)C (2,1)C (1,1) = ⋅ ⋅ ⋅ = = 420 3!4! 2!2! 1!1! 1!0! 3!2!1!1! This solution leads to the following theorem… Emmanuel Kpeglo KNUST 12  Permutations and Combinations Theorem 2.2 (Permutations with Indistinguishable Objects): The number of different permutations of n objects, where there are n1 indistinguishable objects of type 1, n2 indistinguishable objects of type 2,…, and nk n! indistinguishable objects of type k, is. n1!n2 ! nk ! Example 2.9 How many permutations of the letters from MASSACHUSETTS contain MASS? Solution: We can consider MASS as one block along with the remaining 9 letters A, C, H, U, S, E, T, T, S. Thus, we are permuting 10 ‘letters’. There are 2 S’s, 2 T’s, and others 1and so the total number of permutations sought is n! 10! = = 907,200 n1!n2! nk ! 2!⋅2!⋅1!1! Emmanuel Kpeglo KNUST 13  Permutations and Combinations Theorem 2.2 (Permutations with Indistinguishable Objects): The number of different permutations of n objects, where there are n1 indistinguishable objects of type 1, n2 indistinguishable objects of type 2,…, and nk n! indistinguishable objects of type k, is. n1!n2 ! nk ! Example 2.9 How many permutations of the letters from MASSACHUSETTS contain MASS? Solution: We can consider MASS as one block along with the remaining 9 letters A, C, H, U, S, E, T, T, S. Thus, we are permuting 10 ‘letters’. There are 2 S’s, 2 T’s, and others 1and so the total number of permutations sought is n! 10! = = 907,200 n1!n2! nk ! 2!⋅2!⋅1!1! Emmanuel Kpeglo KNUST 14  Binomial Coefficients and Identities The Binomial Theorem It is well known (a + b) 2 = a 2 + 2ab + b 2. Multiplying this last equality by a + b one obtains (a + b)3 = (a + b) 2 (a + b) = a 3 + 3a 2b + 3ab 2 + b3 Again, multiplying (a + b)3 = a 3 + 3a 2b + 3ab 2 + b3 by a + b one obtains (a + b) 4 = (a + b)3 (a + b) = a 4 + 4a 3b + 6a 2b 2 + 4ab3 + b 4 This generalizes, as we see in the next theorem. Theorem 2.3 (The Binomial Theorem): Let x and y be variables and n be a nonnegative integer. n  n  n −i i Then ( x + y ) = ∑  x y n i =0  i  Emmanuel Kpeglo KNUST 15  Binomial Coefficients and Identities Example 2.11: Expand (4 x + 5) 3, simplifying as much as possible. Solution 2.11:  3  3  3  3 (4 x + 5)3 =  (4 x)3 50 +  (4 x) 2 51 +  (4 x)1 52 +  (4 x) 0 53  0  1  2  3 = (4 x) 3 + 3(4 x) 2 (5) + 3(4 x)(5) 2 + 53 = 64 x 3 + 240 x 2 + 300 x + 125 Example 2.12: In the following, i = − 1, so that i 2 = −1, evaluate (2 + i )5 Solution 2.12: 5  5 5  5 5  5 (2 + i )5 =  (2)5 i 0 +  (2) 4 i1 +  (2)3 i 2 +  (2) 2 i 3 +  (2)1 i 4 +  (2)0 i 5  0 1  2  3  4  5 = 32 + 80i − 80 − 40i + 10 + i = −38 + 39i Emmanuel Kpeglo KNUST 16  Binomial Coefficients and Identities Example 2.13: 12 13 What is the coefficient of x y in the expansion of ( x + 2) 25 ? Solution 2.13:  25  25!   = = 5,200,300  13  13!12! Emmanuel Kpeglo KNUST 17  Inclusion-Exclusion The Sum Rule gives us the cardinality for unions of finite sets that are mutually disjoint. In this section we will drop the disjointness requirement and obtain a formula for the cardinality of unions of general finite sets. Theorem 2.4 (Inclusion-Exclusion for Two Sets). Let A and B be sets. Then |A ∪ B| = |A| + |B| − |A ∩ B| Proof: Clearly there are |A∩B| elements that are in both A and B. Therefore, |A|+|B| is the number of element in A and B, where the elements in |A∩B| are counted twice. From this it is clear that |A ∪ B| = |A| + |B| − |A ∩ B|. Emmanuel Kpeglo KNUST 18  Inclusion-Exclusion Example 2.14: Consider the set A that are multiples of 2 no greater than 114. That is, A = {2, 4, 6,... , 114}. (a) How many elements are there in A? (b) How many are divisible by 3? (c) How many are divisible by 5? (d) How many are divisible by 15? (e) How many are divisible by either 3, 5 or both? (f) How many are neither divisible by 3 nor 5? (g) How many are divisible by exactly one of 3 or 5? Emmanuel Kpeglo KNUST 19  Inclusion-Exclusion Solution 2.14: Let Ak ⊂ A be the set of those integers divisible by k. (a) How many elements are there in A? Notice that the elements are 2 = 2(1), 4 = 2(2),... , 114 = 2(57). Thus |A| = 57. (b) How many are divisible by 3? Notice that A3 = {6, 12, 18,... , 114} = {1 · 6, 2 · 6, 3 · 6,... , 19 · 6}, so |A3| = 19. (c) How many are divisible by 5? Notice that A5 = {10, 20, 30,... , 110} = {1 · 10, 2 · 10, 3 · 10,... , 11 · 10}, so |A5| = 11. Emmanuel Kpeglo KNUST 20  Inclusion-Exclusion Solution 2.14: Let Ak ⊂ A be the set of those integers divisible by k. (d) How many are divisible by 15? Notice that A15 = {30, 60, 90}, so |A15| = 3. (e) How many are divisible by either 3, 5 or both? First notice that A3∩A5 = A15. Then it is clear that the answer is |A3∪A5| = |A3| + |A5| − |A15| = 19 + 11 − 3 = 27. (f) How many are neither divisible by 3 nor 5? |A \ (A3 ∪ A5)| = |A| − |A3 ∪ A5| = 57 − 27 = 30. (g) How many are divisible by exactly one of 3 or 5? |(A3 ∪ A5) \ (A3 ∩ A5)| = |(A3 ∪ A5)| − |A3 ∩ A5| = 27 − 3 = 24. Emmanuel Kpeglo KNUST 21  Inclusion-Exclusion Theorem 2.5 (Inclusion-Exclusion for Three Sets). Let A, B, and C be sets. Then |A ∪ B ∪ C| = |A| + |B| + |C| −|A ∩ B| − |B ∩ C| − |C ∩ A| +|A ∩ B ∩ C| Proof: Using the associativity and distributivity of unions of sets, we see that |A ∪ B ∪ C| = |A ∪ (B ∪ C)| = |A| + |B ∪ C| − |A ∩ (B ∪ C)| = |A| + |B ∪ C| − |(A ∩ B) ∪ (A ∩ C)| = |A| + |B| + |C| − |B ∩ C| − |A ∩ B| − |A ∩ C| + |(A ∩ B) ∩ (A ∩ C)| = |A| + |B| + |C| − |B ∩ C| − (|A ∩ B| + |A ∩ C| − |A ∩ B ∩ C|) = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C|. Emmanuel Kpeglo KNUST 22  Inclusion-Exclusion Example 2.15: At Prempeh College, there are forty students. Amongst them, fourteen like mathematics, sixteen like theology, and eleven like accounting. It is also known that seven like mathematics and theology, eight like theology and accounting and five like mathematics and accounting. All three subjects are favored by four students. How many students like neither mathematics, nor theology, nor accounting? Solution 2.15: Let A be the set of students liking mathematics, B the set of students liking theology, and C be the set of students liking accounting. We are given that |A| = 14, |B| = 16, |C| = 11, |A ∩ B| = 7, |B ∩ C| = 8, |A ∩ C| = 5, and |A ∩ B ∩ C| = 4. Therefore A  B C = A B C = |U| − |A ∪ B ∪ C| = |U| − |A| − |B| − |C| + |A ∩ B| + |A ∩ C| + |B ∩ C| − |A ∩ B ∩ C| = 40 − 14 − 16 − 11 + 7 + 5 + 8 − 4 Emmanuel Kpeglo KNUST = 15. 23  Counting Using Recurrence Relations Recurrence Relations Recursive definition of a sequence specifies one or more initial terms and a rule for determining subsequent terms from those that precede them. A rule of the latter sort (whether or not it is part of a recursive definition) is called a recurrence relation. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. Example 2.16 Let’s use an to denote the number of bit strings of length n with no adjacent 0’s. Here are a few sample cases for small values of n. Emmanuel Kpeglo KNUST 24  Counting Using Recurrence Relations Example 2.16… n=0: Just one good bit string of length zero, and that is l, the empty bit string. So a0 = 1. n=1: There are two good bit strings of length one. Namely 0 and 1. So a1 = 2. n=2: There are three good bit strings of length two. Namely, 01, 10 and 11. (Of course, 00 is a bad bit string.) That means a2 = 3. n=3: Things start to get confusing now. But here is the list of good bit strings of length three: 010, 011, 101, 110, and 111. So a3 = 5. Emmanuel Kpeglo KNUST 25  Counting Using Recurrence Relations Example 2.16… n=4: A little scratch work produces the good bit strings 0101, 0111, 1011,1101, 1111, 0110, 1010, and 1110, for a total of eight. That means a4 = 8. List so far looks like 1, 2, 3, 5, 8. Trying a bit more, it turns out the list continues 13, 21, 34. The solution to the counting problem can be expressed recursively as a0 = 1, a1 = 2, and for 2 ≤ n, an = an-1 + an-2 Emmanuel Kpeglo KNUST 26  Exercise 2.1 1. An auto insurance company has 10, 000 policyholders. Each policy holder is classified as young or old, male or female, and married or single. Of these policyholders, 3000 are young, 4600 are male, and 7000 are married. The policyholders can also be classified as 1320 young males, 3010 married males, and 1400 young married persons. Finally, 600 of the policyholders are young married males. How many of the company’s policyholders are young, female, and single? 2. Expand and simplify the following: (2i + 3) 4 − (2i − 3i ) 4 3. What is the coefficient of x 6 y 9 in (3x − 2 y )15 4 6 What is the coefficient of x y in ( x 2 − y ) 10 4. Emmanuel Kpeglo KNUST 27 Graph Theory - Lecture 1 (of 2)  Graph Theory Click here for a movable graph Graph Theory Graph Theory Graph Theory Graph Theory Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Definition (Graph) A graph G is an ordered pair (V , E ), where V = V (G ) is a non-empty set of vertices – The vertex set of G ; E = E (G ) is a set of edges the edge set of G ; and the two sets are related through a function fG : E → {{u, v } : u, v ∈ V } called the incidence function, assigning to each edge the unordered pair of its end-points. 1/20 Graph Theory - Example za e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g The drawing above represents a graph with vertex set V = {a, b, c, d, e, f , g }, edge set E = {e1 , e2 , · · · , e8 }, and incidence function defined by f (e1 ) = {a, b} f (e2 ) = {b, c} f (e3 ) = {b, d} f (e4 ) = {b, e} f (e5 ) = {c, e} f (e6 ) = {d, f } f (e7 ) = {e, f } f (e8 ) = {c, g } 2/20 Graph Theory - Loop and Parallel Edges Definition An edge e in a graph G is called a loop if fG (e) = {u} for some vertex u ∈ V (G ) (that is, if its endpoints coincide) link if fG (e) = {u, v }for distinct vertices u, v ∈ V (G ). Distinct edges e1 and e2 in a graph G are called parallel or multiple if fG (e1 ) = fG (e2 ),that is, if they have the same endpoints. 3/20 Graph Theory - Loop and Parallel Edges In this example, edges e1 ande7 are loops, and all other edges are links. Edges e3 , e4 , and e5 are pairwise parallel. 4/20 Graph Theory - Loop and Parallel Edges In this example, edges e1 ande7 are loops, and all other edges are links. Edges e3 , e4 , and e5 are pairwise parallel. Definition (Simple Graph) A simple graph is a graph without loops and without multiple edges. 4/20 Graph Theory - Directed Graph Definition A directed graph (or digraph) D is an ordered pair (V , A), where V = V (D) is a non-empty set of vertices – the vertex set of D; A = A(D) is a set of arcs or directed edges the arc set of D; and the two sets are related via an incidence function fD :→ V × V , assigning to each arc the ordered pair of its endpoints. 5/20 Graph Theory - Directed Graph Example We have a digraph with vertex set V = {v1 , v2 , v3 , v4 } and arc set A = {a1 , a2 ,..., a9 }. The incidence function returns fD (a1 ) = (v1 , v1 ) fD (a2 ) = (v1 , v2 ) fD (a3 ) = (v3 , v2 ) fD (a4 ) = (v2 , v3 ) fD (a5 ) = (v2 , v3 ) fD (a6 ) = (v2 , v4 ) fD (a7 ) = (v3 , v3 ) fD (a8 ) = (v3 , v4 ) fD (a9 ) = (v4 , v3 ) 6/20 Graph Theory - Directed Graph Example If a ∈ A(D) and u, v ∈ V (D) are such that fD (a) = (u, v ), then u is called the initial and v is called the terminal vertex of the arc a. 7/20 Graph Terminology Graph Theory - Graph Terminology Adjacent: Let G = (V , E ) be a graph. Vertices u, v ∈ V are called adjacent or neighbours in G if uv is an edge of G. 8/20 Graph Theory - Graph Terminology Adjacent: Let G = (V , E ) be a graph. Vertices u, v ∈ V are called adjacent or neighbours in G if uv is an edge of G. Incident An edge uv is said to be incident with each of its end points u and v. 8/20 Graph Theory - Graph Terminology Adjacent: Let G = (V , E ) be a graph. Vertices u, v ∈ V are called adjacent or neighbours in G if uv is an edge of G. Incident An edge uv is said to be incident with each of its end points u and v. Degree The degree of a vertex u ∈ V , denoted by degG (u), is the number of edges of G incident with vertex u, each loop counting twice. 8/20 Graph Theory - Graph Terminology Adjacent: Let G = (V , E ) be a graph. Vertices u, v ∈ V are called adjacent or neighbours in G if uv is an edge of G. Incident An edge uv is said to be incident with each of its end points u and v. Degree The degree of a vertex u ∈ V , denoted by degG (u), is the number of edges of G incident with vertex u, each loop counting twice. – A vertex of degree 0 is called isolated, and a vertex of degree 1 is called pendant (or a leaf in the context of trees). 8/20 Some Useful Graphs Graph Theory - Complete Graph 9/20 Graph Theory - Complete Graph Complete Graph A complete graph Kn (for n ≥ 1) is a simple graph with n vertices in which every pair of distinct vertices are adjacent. More formally V (Kn ) = {u1 , u2 , · · · , un } E (Kn ) = {xy : x, y ∈ V , x 6= y } 9/20 Graph Theory - Complete Bi-partite Graph 10/20 Graph Theory - Complete Bi-partite Graph Complete Bi-partite Graph A complete bipartite graph Km,n (for m, n ≥ 1) is a simple graph with m + n vertices. The vertex set partitions into sets X and Y of cardinalities m and n, and each pair of vertices from distinct parts are adjacent. That is: V (Km,n ) = {x1 , x2 , · · · , xm } ∪ {y1 , y2 , · · · , yn } E (Km,n ) = {xi yj : xi ∈ X , yj ∈ Y } 10/20 Graph Theory - Bipartite Graph 11/20 Graph Theory - Bipartite Graph Bipartite Graph A bipartite graph Km,n (for m, n ≥ 1) is a simple graph with m + n vertices. The vertex set partitions into sets X and Y of cardinalities m and n. And edges are only of the form xy , where x ∈ X , y ∈ Y : V (Km,n ) = {x1 , x2 , · · · , xm } ∪ {y1 , y2 , · · · , yn } E (Km,n )⊆{xi yj : xi ∈ X , yj ∈ Y } 11/20 Graph Theory - Cycle 12/20 Graph Theory - Cycle 13/20 Graph Theory - Cycle Cycle A cycle Cn (of length n ≥ 1) is a graph with n vertices that are linked in a circular way, creating n edges. That is, V (Cn ) = {u1 , u2 , · · · , un } E (Cn ) = {u1 u2 , u2 u3 , u3 u4 , · · · , un−1 un , un u1 } 13/20 Graph Theory - Cycle Cycle A cycle Cn (of length n ≥ 1) is a graph with n vertices that are linked in a circular way, creating n edges. That is, V (Cn ) = {u1 , u2 , · · · , un } E (Cn ) = {u1 u2 , u2 u3 , u3 u4 , · · · , un−1 un , un u1 } Note that any cycle Cn for n ≥ 3 is a simple graph, while for n = 2, the edge set E (Cn ) consists of a pair of parallel edges. 13/20 Graph Theory - Path 14/20 Graph Theory - Path 15/20 Graph Theory - Path Path A path Pn (of length n ≥ 0) is a graph with n + 1 vertices that are linked in a linear way. More precisely, V (Pn ) = {u1 , u2 , · · · , un } E (Pn ) = {u1 u2 , u2 u3 , u3 u4 , · · · , un−1 un } 15/20 Graph Theory - Subgraph a b c h d e i j G f g H k Subgraph Let G and H be simple graphs. We say that H is a subgraph of G if V (H) ⊆ V (G ) and E (H) ⊆ E (G ). But is it induced subgraph? What is that by the way? 16/20 Graph Theory - Subgraph a b c h d e i j G f g H k Subgraph Let G and H be simple graphs. We say that H is a subgraph of G if V (H) ⊆ V (G ) and E (H) ⊆ E (G ). But is it induced subgraph? What is that by the way? 16/20 Matrix Representation of Graphs Matrix Representation of Graphs Graph Theory - Incident Matrix Representation Incident Matrix Representation Let G be a graph with V (G ) = {u1 , u2 , · · · , un }, E (G ) = {e1 , e2 , · · · , em },and incidence function fG. We define: the incidence matrix of G : an n × m matrix M = [mij ] such that  2, if fG (ej ) = {vj }  mij = 1, if fG (ej ) = {ui , uk } for some k 6= i (1)  0 otherwise.  17/20 Graph Theory - Adjacency Matrix Representation Adjacency Matrix Representation Let G be a graph with V (G ) = {u1 , u2 , · · · , un }, E (G ) = {e1 , e2 , · · · , em },and incidence function fG. We define: the adjacency matrix of G : an n × n matrix A = [aij ] such that aij = |{ek : fG (ek ) = {ui , uj }}| = number of edges with end points ui and uj. 18/20 Graph Theory - Adjacency Matrix Representation 19/20 Thank you for your attention!! 20/20 Graph Theory - Lecture 2 (of 2)  Graph Theory Click here for a movable graph Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)= 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)= 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)= 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, deg(d)= 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)= 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)= 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=2 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=2 deg(g)= 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=2 deg(g)=1. 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=2 deg(g)=1. Degree sequence is: 1/25 Graph Theory a e1 e2 c b e4 d e3 e5 e6 e e8 e7 G f g Degree Sequence deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=2 deg(g)=1. Degree sequence is: 1, 1, 2, 2, 3, 3, 4. 1/25 Graph Theory - Bipartite Graph Bipartite Graph A bipartite graph Km,n (for m, n ≥ 1) is a simple graph with m + n vertices. The vertex set partitions into sets X and Y of cardinalities m and n. And edges are only of the form xy , where x ∈ X , y ∈ Y : V (Km,n ) = {x1 , x2 , · · · , xm } ∪ {y1 , y2 , · · · , yn } E (Km,n ) ⊆ {xi yj : xi ∈ X , yj ∈ Y } 2/25 Bipartite Graph, 2-Coloring and No Odd-length Cycle Theorem The following are equivalent: 1 G is bipartite. 2 G admits a proper 2-vertex-colouring; that is, the vertices of G can be coloured with 2 colours (say, red and blue) so that the endpoints of each edge receive distinct colours. 3 G has no subgraph that is a cycle of odd length. 3/25 Bipartite Graph, 2-Coloring and No Odd-length Cycle Theorem The following are equivalent: 1 G is bipartite. 2 G admits a proper 2-vertex-colouring; that is, the vertices of G can be coloured with 2 colours (say, red and blue) so that the endpoints of each edge receive distinct colours. 3 G has no subgraph that is a cycle of odd length. 5 6 1 2 3 4 8 7 G Bipartite Graph, 2-Coloring and No Odd-length Cycle Theorem The following are equivalent: 1 G is bipartite. 2 G admits a proper 2-vertex-colouring; that is, the vertices of G can be coloured with 2 colours (say, red and blue) so that the endpoints of each edge receive distinct colours. 3 G has no subgraph that is a cycle of odd length. 5 6 1 2 3 4 8 7 G 3/25 Bipartite Coloring 4/25 Bipartite Coloring 4/25 Bipartite Coloring 4/25 Bipartite Coloring 4/25 Matrix Representation of Graphs Graph Theory - Incident Matrix Representation Incident Matrix Representation Let G be a graph with V (G ) = {u1 , u2 , · · · , un }, E (G ) = {e1 , e2 , · · · , em },and incidence function fG. We define: the incidence matrix of G : an n × m matrix M = [mij ] such that  2, if fG (ej ) = {vj }  mij = 1, if fG (ej ) = {ui , uk } for some k 6= i (1)  0 otherwise.  5/25 Graph Theory - Adjacency Matrix Representation Adjacency Matrix Representation Let G be a graph with V (G ) = {u1 , u2 , · · · , un }, E (G ) = {e1 , e2 , · · · , em },and incidence function fG. We define: the adjacency matrix of G : an n × n matrix A = [aij ] such that aij = |{ek : fG (ek ) = {ui , uj }}| = number of edges with end points ui and uj. 6/25 Graph Theory - Adjacency Matrix Representation 7/25 Graph Isomorphism Graph Isomorphism Problem is one of the most interesting problems in computer science. a g 5 6 b h 1 2 c i 3 4 d j 8 7 G H Click here for an animated example Graph Isomorphism Graph Isomorphism Problem is one of the most interesting problems in computer science. a g 5 6 b h 1 2 c i 3 4 d j 8 7 G H Click here for an animated example Graph Isomorphism Graph Isomorphism Problem is one of the most interesting problems in computer science. An Isomorphism between G and H a g 5 6 f (a) = 5 f (b) = 2 b h 1 2 f (c) = 3 f (d) = 7 c i 3 4 f (g ) = 1 f (h) = 6 d j 8 7 f (i) = 8 f (j) = 4 G H 8/25 Graph Isomorphism Graph Isomorphism Problem is one of the most interesting problems in computer science. An Isomorphism between G and H a g 5 6 f (a) = 5 f (b) = 2 b h 1 2 f (c) = 3 f (d) = 7 c i 3 4 f (g ) = 1 f (h) = 6 d j 8 7 f (i) = 8 f (j) = 4 G H Click here for an animated example 8/25 Graph Isomorphism Are these two graph isomorphic? Definition (Graph Isomorphism) Let G and H be simple graphs. An isomorphism from G to H is a bijection ϕ : V (G ) → V (H) such that u ∼G v ⇔ ϕ(u) ∼H ϕ(v ) for all u, v ∈ V (G ). Graphs G and H are called isomorphic (denoted G∼ = H) if there exists an isomorphism from G to H. 9/25 Graph Isomorphism Definition (Graph Invariant) A graph invariant is a graph property or parameter that is preserved under isomorphisms; that is, isomorphic graphs must agree on this property or parameter. Many graph properties are invariants; for example: Number of vertices Number of edges Degree Sequence (all the degrees of the vertices of the graph in sorted order) Being bipartite Containing specific subgraph etc. 10/25 Graph Isomorphism Observation To prove that graphs G and H are isomorphic, we must find an isomorphism from G to H. To prove that graphs G and H are not isomorphic, it suffices to find an invariant in which G and H differ. 11/25 Graph Isomorphism -Example 1 Are these two graph isomorphic? Solution: 12/25 Graph Isomorphism -Example 1 Are these two graph isomorphic? Solution: No. They have the same degree sequence. But these two graphs are not isomorphic. H has a subgraph isomorphic to C3 , while G does not (it is, in fact, bipartite and isomorphic to K3,3 ). 12/25 Graph Isomorphism -Example 2 Are these two graph isomorphic? Solution: 13/25 Graph Isomorphism -Example 2 Are these two graph isomorphic? Solution: Yes, these two graphs are isomorphic. An isomorphism ϕ : (G ) → V (H) is given by ϕ(1) = a ϕ(2) = d ϕ(3) = b ϕ(4) = e ϕ(5) = c ϕ(6) = f 13/25 Graph Isomorphism -Example 3 Are these two graph isomorphic? Solution: 14/25 Graph Isomorphism -Example 3 Are these two graph isomorphic? Solution: No, these two graphs are not isomorphic. They have the same degree sequence, however, graph H contains no pair of adjacent vertices of degree 3, while G does. 14/25 Walks, Trails, Paths, Cycle Walks, Trails, Paths, Cycles Definition Walk Let G = (V , E ) be a graph with the incidence function fG. Let x, y ∈ V and k ∈ N. An (x, y )-walk of length k in G is an alternating sequence of vertices and edges. 15/25 Walks, Trails, Paths, Cycles Definition Walk Let G = (V , E ) be a graph with the incidence function fG. Let x, y ∈ V and k ∈ N. An (x, y )-walk of length k in G is an alternating sequence of vertices and edges. A (v1 , v3 )-walk of length 4 W = v1 e2 v2 e6 v4 e8 v3 e7 v3 15/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. 16/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. 16/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 1a2h6n5f 1a2b3 16/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 1a2h6n5f 1a2b3 is a (1,3)-walk of length 6 that is not a trail. 16/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 1a2h6n5f 1a2b3 is a (1,3)-walk of length 6 that is not a trail. W = 1e4d4c3 16/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 1a2h6n5f 1a2b3 is a (1,3)-walk of length 6 that is not a trail. W = 1e4d4c3 is a (1,3)-trail of length 3 that is not a path. 16/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 1a2h6n5f 1a2b3 is a (1,3)-walk of length 6 that is not a trail. W = 1e4d4c3 is a (1,3)-trail of length 3 that is not a path. W = 1f 5m8k3 16/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 1a2h6n5f 1a2b3 is a (1,3)-walk of length 6 that is not a trail. W = 1e4d4c3 is a (1,3)-trail of length 3 that is not a path. W = 1f 5m8k3 is a (1,3)-path of length 3. 16/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 2b3j7i2h6o7i2 17/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 2b3j7i2h6o7i2 is a closed walk of length 6 that contains vertex 2 and is not a trail:. 17/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 2b3j7i2h6o7i2 is a closed walk of length 6 that contains vertex 2 and is not a trail:. W = 4d4l8k3c4 17/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 2b3j7i2h6o7i2 is a closed walk of length 6 that contains vertex 2 and is not a trail:. W = 4d4l8k3c4 is a closed trail of length 4 that contains vertex 4 and is not a cycle. 17/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 2b3j7i2h6o7i2 is a closed walk of length 6 that contains vertex 2 and is not a trail:. W = 4d4l8k3c4 is a closed trail of length 4 that contains vertex 4 and is not a cycle. W = 2b3j7o6h2 17/25 Walks, Trails, Paths, Cycles Definition A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called closed if v0 = vk , and open otherwise; a trail if its edges are pairwise distinct; a path if its vertices are pairwise distinct; and a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise distinct. W = 2b3j7i2h6o7i2 is a closed walk of length 6 that contains vertex 2 and is not a trail:. W = 4d4l8k3c4 is a closed trail of length 4 that contains vertex 4 and is not a cycle. W = 2b3j7o6h2 is a cycle of length 4 containing vertex 2. 17/25 Trees and Forests Trees and Forests Warm up: Connected Graph Connected Graph A graph G = (V , E ) is called connected if for any x, y ∈ V there exists an (x, y )-path (or equivalently, (x, y )-walk) in G. A graph that is not connected is called disconnected. 18/25 Trees Tree and Forest A graph without cycles is called acyclic or a forest. A tree is a connected acyclic graph ,that is, a connected forest. 19/25 Trees Theorem 1 Let G be a graph. Then G is a tree if and only if for any two vertices u, v ∈ V (G ), there exists a unique (u, v )-path in G. Theorem 2 and 3 Every tree with at least 2 vertices has at least 2 vertices of degree 1 (called leaves). Any tree with n vertices has exactly n − 1 edges. 20/25 Rooted Trees Rooted Tree A tree with a vertex designated as the root is called a rooted tree. 21/25 Rooted Trees Similar terminologies for rooted trees? 22/25 Rooted Trees Terminology for rooted trees: Let T = (V , E ) be a rooted tree with root r and u, v ∈ V. If u lies on the unique (v , r )-path, then u is called anancestor of v , and v is called a descendant to u. If u lies on the unique (v , r )-path and uv has an edge, then u is called the parent of v , and v is called a child of u. If u and v have the same parent, then they are called siblings. If vertex u has a child, then it is called an internal vertex; if it has no children, thenit is called a leaf. 23/25 Rooted m-ary Trees A Rooted m-ary Tree: an m-ary tree if every internal vertex has at most m children; and a full m-ary tree if every internal vertex has exactly m children. A Binary is a 2-ary tree. A Ternary is a 3-ary tree. 24/25 Thank you for your attention!! 25/25  CSM 166 Lecture FIVE Topic: Boolean Algebra 1 of 2  INTRODUCTION. Inputs.. Network. Outputs.. Boolean algebra is used to describe the relationship between inputs and outputs. It is developed by English Mathematician George Boole in between 1815 - 1864. It is described as an algebra of logic or an algebra of two values i.e True or False. The term logic means a statement having binary decisions i.e True/Yes/On or False/No/Off. Emmanuel Kpeglo KNUST 2  INTRODUCTION Why Study Boolean Algebra? When we learned numbers like 1, 2, 3, we also then learned how to add, multiply, etc. with them. Boolean Algebra covers operations that we can do with 0’s and 1’s. Computers do these operations ALL THE TIME and they are basic building blocks of computation inside your computer program. Emmanuel Kpeglo KNUST 3  APPLICATION OF BOOLEAN ALGEBRA Boolean algebra is used to perform the logical operations in digital computer. In digital computer True represent by ‘1’ (high volt) and False represent by ‘0’ (low volt). Logical operations are performed by logical operators. The fundamental logical operators are: 1. AND (conjunction) 2. OR (disjunction) 3. NOT (negation/complement) AND is denoted by a dot (·). OR is denoted by a plus (+). NOT is denoted by an overbar ( ¯ ), a single quote mark (') after, or (~) before the variable. Emmanuel Kpeglo KNUST 4  BINARY LOGIC AND GATES Binary variables take on one of two values. Logical operators operate on binary values and binary variables. Basic logical operators are the logic functions AND, OR and NOT. Logic gates implement logic functions. Boolean Algebra: a useful mathematical system for specifying and transforming logic functions. We study Boolean algebra as foundation for designing and analyzing digital systems! Emmanuel Kpeglo KNUST 5  BINARY LOGIC AND GATES  Boolean Algebra applied in computers electronic circuits. These circuits perform Boolean operations and these are called logic circuits or logic gates. A gate is an digital circuit which operates on one or more signals and produce single output. Gates are digital circuits because the input and output signals are denoted by either 1(high voltage) or 0(low voltage). There are three basic gates and are: 1. AND gate 2. OR gate 3. NOT gate Emmanuel Kpeglo KNUST 6  OPERATOR DEFINITIONS The NOT gate is an electronic circuit that gives a high output (1) if its input is low. NOT gate inverts the value (flip 0 and 1) y = NOT (A)= A’ A A’ A NOT A 0 1 1 0 Emmanuel Kpeglo KNUST 7  OPERATOR DEFINITIONS The OR gate is an electronic circuit that gives a high output (1) if one or more of its inputs are high. OR gate: Output is true if either input is true y= A OR B (A + B) AB A+B A 0 0 0 A+B B 0 1 1 1 0 1 1 1 1 Emmanuel Kpeglo KNUST 8  OPERATOR DEFINITIONS Example: Logic circuit with its Boolean expression Emmanuel Kpeglo KNUST 9  OPERATOR DEFINITIONS The AND gate is an electronic circuit that gives a high output (1) only if all its inputs are high. AND gate: Output is true only if all inputs are true, y= A AND B (A∙B) AB A∙B A 0 0 0 A∙B B 0 1 0 1 0 0 1 1 1 Emmanuel Kpeglo KNUST 10  OPERATOR DEFINITIONS Example: Logic circuit with its Boolean expression Emmanuel Kpeglo KNUST 11  TRUTH TABLE Truth table is a table that contains all possible values of logical variables/state-ments in a Boolean expression. No. of possible combination = 2n, where n=number of variables used in a Boolean expression. Emmanuel Kpeglo KNUST 12  TRUTH TABLE The truth table for XY + Z is as follows: X Y Z XY XY+Z 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 Emmanuel Kpeglo KNUST 13  TAUTOLOGY AND FALLACY  If the output of Boolean expression is always True or 1 is called Tautology.  If the output of Boolean expression is always False or 0 is called Fallacy.  For example: Verify that P+(PQ)’ is a Tautology. P Q PQ (PQ)’ P+(PQ)’ 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 1 Emmanuel Kpeglo KNUST 14  PRACTICAL APPLICATIONS OF LOGIC GATES AND Gate So while going out of the house you set the "Alarm Switch" and if the burglar enters he will set the "Person switch", and tada the alarm will ring. Emmanuel Kpeglo KNUST 15  PRACTICAL APPLICATIONS OF LOGIC GATES AND Gate Electronic door will only open if it detects a person and the switch is set to unlocked. Microwave will only start if the start button is pressed and the door close switch is closed. Emmanuel Kpeglo KNUST 16  PRACTICAL APPLICATIONS OF LOGIC GATES OR Gate You would of course want your doorbell to ring when someone presses either the front door switch or the back door switch. Emmanuel Kpeglo KNUST 17  PRACTICAL APPLICATIONS OF LOGIC GATES NOT Gate When the temperature falls below 20c the Not gate will set on the central heating system (cool huh). Emmanuel Kpeglo KNUST 18  EXERCISE 5.1 1. Evaluate the following Boolean expression using Truth Table. (a) X’Y’+X’Y (b) X’YZ’+XY’ (c) XY’(Z+YZ’)+Z’ 2. Verify that (X+Y)’=X’Y’ 3. Show that xy + yz + xz = xy + yz + xz. Emmanuel Kpeglo KNUST 19  EXERCISE 5.2 Use a table to express the values of each of these Boolean functions. a) F(x, y, z) = x’y b) F(x, y, z) = x + yz c) F(x, y, z) = xy’ + (xyz)’ d) F(x, y, z) = x(yz + y’z’) e) F(x, y, z) = z’ f) F(x, y, z) = x’y + yz’ g) F(x, y, z) = xy’z + (xyz)’ h) F(x, y, z) = y’(xz + x’z’) Emmanuel Kpeglo KNUST 20  Duality  Definition The dual of a Boolean expression is obtained by interchanging Boolean sums and Boolean products and interchanging 0s and 1s. Example Find the duals of x(y + 0) and x’ ⋅ 1 + (y’ + z) Solution Interchanging ⋅ signs and + signs and interchanging 0s and 1s in these expressions produces their duals. The duals are x + (y ⋅ 1) and (x’ + 0)(y’z), resp. Emmanuel Kpeglo KNUST 21  EXERCISE 5.3 1. Find the duals of these Boolean expressions. a) x+y b) xy c) xyz + x y z d) xz + x ⋅ 0 + x ⋅ 1 2. The Boolean operator ⊕, called the XOR operator, is defined by 1 ⊕ 1 = 0, 1 ⊕ 0 = 1, 0 ⊕ 1 = 1, and 0 ⊕ 0 = 0. a) Simplify these expressions. i) x ⊕ 0 ii) x ⊕ 1 iii) x ⊕ x iv) x ⊕ x’ b) Show that these identities hold. i) x ⊕ y = (x + y)(xy)’ ii) x ⊕ y = (xy’) + (x’y) Emmanuel Kpeglo KNUST 22  AXIOMS, LAWS, THEOREMS We need to know some rules (axioms) about how those 0’s and 1’s can be operated on together. Learning Axioms and theorems of Boolean algebra Allows you to design logic functions Allows you to know how to combine different logic gates Allows you to simplify or optimize on the complex operations A Boolean algebra comprises... A set of elements B Binary operators {+ , } Boolean sum and product A unary operation { ' } (or { }) example: A’ or A …and the following axioms… Emmanuel Kpeglo KNUST 23  AXIOMS, LAWS, THEOREMS …and the following axioms… 1. The set B contains at least two elements {a b} with a ≠ b 2. Closure: a+b is in B a b is in B 3. Commutative: a+b = b+a a b = b a 4. Associative: a+(b+c) = (a+b)+c a (b c) = (a b) c 5. Identity: a+0 = a a 1 = a 6. Null: a+1 = 1 a 0 = 0 7. Distributive: a+(b c)=(a+b) (a+c) a (b+c)=(a b)+(a c) 8. Complementarity: a+a' = 1 a a' = 0 9. Idempotent: a+a = a a a = a 10. Involution: (a’)‘ = a 11. De Morgan’s laws: (a+b)' = a' b’ (a b)’ = a' +b' Emmanuel Kpeglo KNUST 24  Proving theorems Example 1: Prove using axioms the uniting theorem: X Y+X Y'=X Distributive X Y+X Y' = X (Y+Y') Complementarity = X (1) Identity =X Example 2: Prove using axioms the absorption theorem: X+X Y=X Identity X+X Y = (X 1)+(X Y) Distributive = X (1+Y) Null = X (1) Identity =X Emmanuel Kpeglo KNUST 25  Proving theorems Example 3: Prove using axioms the consensus theorem: (XY)+(YZ)+(X'Z)= XY+X'Z Complementarity XY+YZ+X'Z = XY+(X+X')YZ + X'Z Distributive = XYZ+XY+X'YZ+X'Z Use absorption {AB+A=A} with A=XY and B=Z = XY+X'YZ+X'Z Rearrange terms = XY+X'ZY+X'Z Use absorption {AB+A=A} with A=X'Z and B=Y XY+YZ+X'Z = XY+X'Z Emmanuel Kpeglo KNUST 26  EXERCISE 5.4 1. Find the duals of these Boolean expressions. a) x+y b) xy c) xyz + x y z d) xz + x ⋅ 0 + x ⋅ 1 2. The Boolean operator ⊕, called the XOR operator, is defined by 1 ⊕ 1 = 0, 1 ⊕ 0 = 1, 0 ⊕ 1 = 1, and 0 ⊕ 0 = 0. a) Simplify these expressions. i) x ⊕ 0 ii) x ⊕ 1 iii) x ⊕ x iv) x ⊕ x’ b) Show that these identities hold. i) x ⊕ y = (x + y)(xy)’ ii) x ⊕ y = (xy’) + (x’y) Emmanuel Kpeglo KNUST 27  CSM 166 Lecture six Topic: Boolean Algebra 2 of 2  Boolean Expressions and Boolean Functions Recall  Let B = {0, 1}. Then B ͫ = {(x , x ,…, x ) ∣ x ∈ B for 1 ≤ i ≤ 1 2 m i m} is the set of all possible m-tuples of 0s and 1s.  The variable x is called a Boolean variable if it assumes values only from B, that is, if its only possible values are 0 and 1.  A function from B ͫ to B is called a Boolean function of degree m. Example  The function F(x, y) = xy’ from the set of ordered pairs of Boolean variables to the set {0, 1} is a Boolean function of degree 2 with F(1, 1) = 0, F(1, 0) = 1, F(0, 1) = 0, and F(0, 0) = 0. Emmanuel Kpeglo KNUST 2  Boolean Expressions and Boolean Functions Example 6.2  How many different Boolean functions of degree n are there? The Number of Boolean Functions of Degree n. Degree Number 1 4 2 16 3 256 4 65,536 5 4,294,967,296 6 18,446,744,073,709,551,616 Emmanuel Kpeglo KNUST 3  Representing Boolean Functions Given the values of a Boolean function, how can a Boolean expression that represents this function be found? This problem will be solved by showing that any Boolean function can be represented by a Boolean sum of Boolean products of the variables and their complements. The solution of this problem shows that every Boolean function can be represented using the three Boolean operators ⋅,+, and ‘. Is there a smaller set of operators that can be used to represent all Boolean functions? We will answer this question by showing that all Boolean functions can be repre