Lecture Notes Discrete Mathematics

how discrete mathematics is used in computer science. lecture notes on algebraic structures in discrete mathematics and its applications pdf free download
OliverFinch Profile Pic
Published Date:15-07-2017
Your Website URL(Optional)
Lecture Notes for College Discrete Mathematics GÆbor HorvÆth and Szabolcs T engely 2013Chapter 1 Introduction These lecture notes are based on the class material College Discrete Mathe- matics for students in the F oundation Semester year at University of Debre- cen, Hungary . The lecture notes are intended to help the students understand and learn the course material, but they do not substitute participation and active work on the class. Discrete mathematics deals with the non-continuous mathematics. This usually means ni te mathematics, but prop erties of natural numb ers are discussed, as well. The course sets the basis for future mathematical classes, and is essential to understand those later. In Chapter 1 we intro duce basic mathematical concepts, such as sets, subsets, sums and pro ducts, the Euclidean algorithm and numeral systems. In Chapter 2 we show dierent counting arguments. W e count the numb er of sequences, subsets, p ermutations, and anagrams. Then we consider the numb er of ordered subsets, the numb er of subsets of a given size. Finally , we count the numb er of p ossibilities to distribute money , and to take out some balls from an urn. In Chapter 3 we explain dierent basic mathematical pro of metho ds, such as mathematical induction and pro of by contradiction. W e show how one can prove theorems in a constructive way , or by using the pigeonhole principle. At the end of the chapter we use these pro of techniques to bring the reader b ehind the curtains of a mathematical card trick. In Chapter 4 we consider Pascal’s famous triangle built up from the bi-1.1 Sets 5 nomial co ecients. W e prove several identities related to the triangle, and use it to show the Binomial theorem. In Chapter 5 recurrence sequences are discussed. W e start by the famous T owers of Hanoi, then work our way up to more general recurrence sequences and to the explicit formulas determining them. Finally , in Chapter 6 we give all solutions to the exercises o ccurring in the lecture notes. 1.1 Sets In mathematics a set is a collection of ob jects that are called elements. Usu- ally we denote sets by capital letters and elements by small letters. If A is a set and a is an element of A, then we write a2 A. If a is not an element of A, then we write a2= A. Now we deal with the problem how to provide a set.  Sets given by enumeration. If we have a set containing certain elements, then we enclose these elements in braces. F or example, if A is a set containing 1, 2 and 3 we write A =f1;2;3g. This notation is dicult to use if the given set has large amount of elements. In this case we list only some (usually consecutive) elements such that it is easy to see which are the remaining elements of the set. As an example let us assume that B is a set containg the integers b etween 1 and 1000. Here we write B =f1;2;3;:::;1000g. If C is the set containing the o dd integers b etween 1 and 99, then we have C =f1;3;5;:::;99g. It is also p ossible to provide some families of sets, for example D =f1g; D =f1;3;:::;2k1g: 1 k In this case D denotes the set containing the rst k p ositive o dd inte- k gers.6 INTRODUCTION k D k 1 f1g 2 f1;3g 3 f1;3;5g 4 f1;3;5;7g  Standard sets. There are certain frequently used sets which have their own symb ols. These are the set of natural numb ers, the set of integers, the set of rational numb ers, the set of real numb ers and the set of complex numb ers. N =f1;2;3;:::g, the set of natural numb ers. Z =f:::;2;1;0;1;2;:::g, the set of integers. Q, the set of rational numb ers. R, the set of real numb ers. C, the set of complex numb ers.  Set-builder notation. It is also p ossible to dene sets using the so-called set-builder notation. As an example consider the set D = 3 f1;3;5g, we can dene this set in many dierent ways, e.g. f1;3;5g =faj (a1)(a3)(a5) = 0g; f1;3;5g =faja = 2k1;k2f1;2;3gg; f1;3;5g =faj 1a 5; and a is o ddg: W e can use semicolon instead of the vertical line, as well: f1;3;5g =fa : (a1)(a3)(a5) = 0g; f1;3;5g =fa :a = 2k1;k2f1;2;3gg; f1;3;5g =fa : 1a 5; and a is o ddg: Let us dene the set of even natural numb ers: f2njn2Ng:1.1 Sets 7 The set of rational numb ers can b e given as follows fa=bja;b2Z;b =6 0g: T o study some basic prop erties of sets we give some denitions. First we intro duce the concept of cardinality . Denition 1.1. A set is called nite if it has nite numb er of elements. If a set is not nite it is called innite. Now we consider cardinality of nite sets. The cardinality of innite sets is more complicated and we will not discuss it. Denition 1.2. Let A b e a nite set. The c ar dinality of A is the numb er of dierent elements of A. Notation:jAj. F or example, the cardinality of D is 3 and the cardinality of the set 3 f1;2;3;6;7;8g is 6. Denition 1.3. Let A and B b e sets. The set B is a subset of A if and only if every element of B is an element of A. Notation: BA. There is a sp ecial set which is a subset of all sets, the so-called empty set. As the name suggests it is the set which has no element, that is, its cardinality is 0. The empty set is denoted by;. Denition 1.4. If B A and B6=;;B =6 A, then B is a pr op er subset of A. Denition 1.5. Let A and B b e sets. The two sets are e qual if AB and BA. Now we dene some basic op erations of sets. Denition 1.6. Let A and B b e sets. The interse ction of A and B is the setfxjx2A and x2Bg. Notation: A\B . The so-called V enn diagrams are often useful in case of sets to understand the situation b etter. By shading the appropriate region we illustrate the intersection of A and B .8 INTRODUCTION A B Let A =f1;2;3;4;5g and B =f3;4;5;6;7g. The intersection of these two sets is the set A\B =f3;4;5g. Denition 1.7. Let A and B b e sets. The union of A and B is the set fxjx2A or x2Bg. Notation: AB . The corresp onding V enn diagram is as follows. A B Let A =f1;2;3;4;5g and B =f3;4;5;6;7g. The union of these two sets is the set AB =f1;2;3;4;5;6;7g. It is easy to see that the following prop erties hold A\B = B\A and AB = BA. It is not true for the dierence of two sets. Denition 1.8. Let A and B b e sets. The dier enc e of A and B is the set fxjjx2A and x2= Bg. Notation: AnB . The V enn diagram of AnB : A B1.1 Sets 9 T o see the dierence b etween AnB and BnA we draw the V enn diagram of BnA as well: A B Again, let A =f1;2;3;4;5g and B =f3;4;5;6;7g. Now we have that AnB =f1;2g; BnA =f6;7g: Now we intro duce the symmetric dierence of sets. Denition 1.9. Let A and B b e sets. The symmetric dier enc e of A and B is the set (AB)n(A\B). Notation: A4B . The V enn diagram of the symmetric die rence of A and B : A B W e give an example using sets A =f1;2;3;4;5g andB =f3;4;5;6;7g. W e obtain that A4B =f1;2;6;7g: Finally , we dene the complement of a set. Denition 1.10. Let U b e a set (called the universe) and A is a subset of U: The complement of A consists of elements of U which do not b elong to A: Notation: A:10 INTRODUCTION The corresp onding V enn diagram is as follows. U A A As an example consider the sets U =f1;2;3;4;5;6g and A =f1;3;5g: The complement of A is the setf2;4;6g: Exercise 1.1. LetA =f3;4;6;7;8g;B =f2;4;5;6;8g andC =f1;2;4;5;8g. What are the elements of the set (AnB)(C\B)? Exercise 1.2. LetA =f1;3;4;6;7g;B =f2;4;5;6;8g andC =f1;3;4;5;8g. What are the elements of the set (A\B)n(C\B)? Exercise 1.3. Let A =f1;3;4;6;7g;B =f2;4;6;8g and C =f1;3;4;8g. What are the elements of the set (AnB)(CnB)? Exercise 1.4. List all elements of the following sets: (a)f3k+1jk2f2;3;4gg, 2 (b)fk jk2f1;0;1;2gg, (c)fuvju2f3;4;5g;v2f1;2gg. Exercise 1.5. Describ e the following sets using set-builder notation. (a)f2;4;6;8;10g, (b)f1;4;9;16;25g,  1 1 1 (c) 1; ; ;:::; ;::: , k 2 4 2 (d) the set of rational numb ers b etween 1 and 2. Exercise 1.6. Draw a V enn diagram for the following sets: (a) (A\B)C , (b) (AnB)(AnC),1.2 Sums and pro ducts 11 (c) (AB)\C , (d) (A\B)(B\C)(A\C), (e) ((A\B)nC)((A\C)nB)((B\C)nA), (f ) (AnB)(BnC)(CnA). Exercise 1.7. Provide three sets A;B and C which satisfy the following cardinality conditions jA\B\Cj = 2; jA\Bj =jA\Cj =jB\Cj = 2; jAj =jBj =jCj = 4: Exercise 1.8. Provide three sets A;B and C which satisfy the following cardinality conditions jA\B\Cj = 2; jA\Bj = 2; jA\Cj = 2; jB\Cj = 3; jAj = 4; jBj = 5; jCj = 6: 1.2 Sums and products In this section we intro duce summation notation and pro duct notation which P we will use later on. The sp ecial symb ol is used to denote sums. Let us consider an example 5 X k = 1+2+3+4+5: k=1 In a more general form n X k =m+(m+1)+:::+(n1)+n: k=m Here m is the lower b ound of summation and n is the upp er b ound of sum- mation. There are some other p ossibilities to express the ab ove sum, e.g. X k; mkn X k; where S =fm;m+1;:::;ng: k2S12 INTRODUCTION It is imp ortant to note that the v ariable used in the summation is arbitrary . That is, the v alues of the following summations are equal: 3 X 2 2 2 2 k = 1 +2 +3 = 14 k=1 and 3 X 2 2 2 2 m = 1 +2 +3 = 14: m=1 Now we write out explicitly some other summations: (a) 6 X (2i) = (22)+(32)+(42)+(52)+(62) = 10; i=2 (b) 5 X j2 32 42 52 2 = 2 +2 +2 = 14; j=3 (c) X ij = (11)+(12)+(21)+(22) = 9: 1i;j2 Now we deal with pro ducts of mathematical expressions. The symb ol used Q in this case is . Pro duct notation is very similar to summation notation so it is straightforward to learn to use. The rst example in case of summation notation was 5 X k = 1+2+3+4+5: k=1 P Q If we change the symb ol to , then we obtain 5 Y k = 12345: k=1 Let us consider the pro duct of integers b etween m and n, where mn. W e1.2 Sums and pro ducts 13 can write it in pro duct notation in dierent forms: n Y k; k=m Y k; mkn Y k; where S =fm;m+1;:::;ng: k2S It may happ en that the sum or pro duct should b e ev aluated on the empty set. By denition, in such situations the sum is always 0 and the pro duct is always 1, e.g. X k = 0; k2; Y k = 1: k2; If S and T b e two disjoint sets, then X X X k+ k = k; k2S k2T k2ST Y Y Y k k = k: k2S k2T k2ST Note, that this is true even if S or T is the empty set. (This is the main reason we dene the empty sum to b e 0 and the empty pro duct to b e 1.) There is a sp ecial notation for the pro duct of p ositive integers up to n, that is, when we multiply the elements of S =fkjk is a p ositive integer;kng =f1;2;:::;ng: n The pro duct of the elements of S is called n factorial and denoted by n, n that is, n Y Y n = k = k = 12(n1)n: k2S k=1 n W e even dene 0, that is, the pro ducts of elements of S : 0 Y Y 0 = k = k = 1: k2S k2; 014 INTRODUCTION F actorials are always computed b efore any other op eration. F or example 2+3 = 2+123 = 2+6 = 8; (2+3) = 5 = 12345 = 120: Exercise 1.9. Expand the following sums. P 7 (a) i, i=4 P 5 2 (b) (i i), i=1 P 4 i (c) 10 , i=1 P 1 (d) , i 2i5 2 P i (e) (1) , where S =f2;3;5;8g. i2S Exercise 1.10. W rite the following expressions in summation notation. (a) 2+4+6+8+10, (b) 1+4+7+10, 1 1 (c) + +1+2+4, 4 2 1 1 (d) +12+4. 4 2 Exercise 1.11. Expand the following pro ducts. Q 1 (a) i, i=4 Q 4 2 (b) (i ), i=1 Q 3 i (c) 2 , i=1 Q 1 (d) , i 2i3 2 Q i (e) (1) , where S =f2;4;6;7g. i2S Exercise 1.12. W rite the following expressions in pro duct notation. (a) 1357, (b) (1)258, 1 1 (c)  139. 9 3 Exercise 1.13. Compute the v alues of n for everyn2f0;1;2;3;4;5;6;7;8g.1.3 The Euclidean algorithm 15 Exercise 1.14. Compute the v alues of 5+3 (5+3) 423 (42)3 4(23) 32 (32) 43 45: Exercise 1.15. Prove that n = n (n 1) for every p ositive integer n. Note, that it is even true for n = 1, which is one of the reasons we dene 0 to b e equal to 1. 1.3 The Euclidean algorithm In this section we intro duce the so-called Division algorithm, we dene the greatest common divisor of given integers and we consider the Euclidean algorithm, which is one of the oldest mathematical algorithms. Division algorithm. Given two integers a and b such that b 0. There exist unique integers q and r for which a =qb+r; 0r b: Here q is called quotient and r is called r emainder. There is a sp ecial case, when the Division algorithm yields r = 0. In such a situation a = qb for some q . Denition 1.11. W e say that b divides a (b is a divisor ofa ora is a multiple of b) if there exists q such that a =qb. Notation: bja. How to nd an appropriate q and r ? Let us assume that we have two p ositive integers a andb. W e start with q = 0 andr =a. Clearlya = 0b+a.16 INTRODUCTION Ifab, then we are done, otherwise ab 0. So we write a = 1b+(ab). W e check ifabb. If this is the case then we have found q andr , otherwise we have a2b 0 and a = 2b+(a2b). W e stop when we have akbb for some k . F or example, let a = 76 and b = 7 : k akb 0 76 1 69 2 62 3 55 4 48 5 41 6 34 7 27 8 20 9 13 10 6 that is, we obtain that 76 = 107+6 and 0 6 7. Denition 1.12. Let a;b2 Z. A p ositive integer d is called a c ommon divisor of a and b, if d divides a and d divides b. The largest p ossible such integer is called the gr e atest c ommon divisor of a and b. Notation: gcd(a;b). The Euclidean algorithm. Now we study a metho d to determine gcd(a;b) of given p ositive integers a and b. The metho d also provides so- lution of the linear Diophantine equation ax+by = gcd(a;b): If we apply the Division algorithm to a;b;ab, then we have a =qb+r; 0r b: If d is a common divisor of a and b, then d divides r =aqb as well. That is the basic idea of the algorithm. The Euclidean algorithm works as follows. First we apply the Division algorithm for a and b to obtain a quotient q and 11.3 The Euclidean algorithm 17 a remainder r . Then we apply the Division algorithm for b and r to get a 1 1 new quotient q and a new remainder r . W e continue, we divide r by r to 2 2 1 2 obtain q andr . W e stop if we obtain a zero remainder. Since the pro cedure 3 3 pro duces a decreasing sequence of non-negative integers so must eventually terminate by descent. The last non-zero remainder is the greatest common divisor of a and b. As an example we compute gcd(553;161). W e write the computations in the following way: 553 = 3161+70 q = 3;r = 70 1 1 161 = 270+21 q = 2;r = 21 2 2 70 = 321+7 q = 3;r = 7 3 3 21 = 37+0 q = 3;r = 0: 4 4 That is, the last non-zero remainder is 7, so gcd(553;161) = 7. If we would like to express 7 as 553x+161y for some x;y2Z, we can do it by working backwards 7 = 70321 = 703(161270) =3161+770 =3161+7(5533161) = 755324161: It follows that x = 7 and y =24. Exercise 1.16. Use the Euclidean algorithm to nd gcd(a;b) and compute integers x and y for which ax+by = gcd(a;b) : (a) a = 678;b = 567, (b) a = 803;b = 319, (c) a = 2701;b = 2257, (d) a = 3397;b = 1849.18 INTRODUCTION 1.4 Numeral systems In this Section we learn ab out the die rent numeral systems. In everyday life we use base 10. That is, when we talk ab out numb ers, we use the base 10 notation. Let us consider counting. Imagine Robinson Cruso e sp ending his days on an uninhabited island, and he counts all the days by carving a vertical line every day into a ro ck. He was raised using the base 10 numb ers, thus after reaching 9 lines, he crosses them on the tenth day (thus marking them as ten). That way he groups together every ten days. Then, when he reaches ten of such groups, then he carves a big b ox around them. That is how he indicates hundreds. Then he circles around every ten b oxes, indicating thousands, etc. Then, reaching ten circles on one ro ck he would lo ok for a new ro ck to carve days into. Assume Robinson had arrived at the island 1st May 1817, and was rescued on 30th April 1850. How would his stones lo ok like, after so much time? He sp ent 33 years on the island, that is, 33365 = 12045 days, not counting leap years. The leap years are 1820, 1824, 1828, 1832, 1836, 1840, 1844, 1848, that is, he sp ent 12053 days altogether on the island. That means one of the ten thousands, two of the thousands, zero of hundreds, ve of tens and three of ones. That is, he would have one ro ck completely full with ten circles, ten b oxes in each circle, and ten of the ten lines crossed in each b ox. Then on his second ro ck he would have two full circles, and next to them he would have ve of the ten crossed lines and three separate lines. Robinson is basically writing the numb ers in base 10 by grouping every ten together. This is what we do, as well, except mayb e in a bit more abstract and automatic way . When we think ab out the numb er 12053, we automatically give the meaning to the p ositions with the appropriate p owers of 10: 12053 = 110 000+21 000+0100+510+31 = 4 3 2 1 0 = 110 +210 +010 +510 +310 : By writing the digits next to each other we indicate their v alue by their1.4 Numeral systems 19 0 p ositioning. The v alue of the rightmost digit is 1 = 10 , then going from right to left the v alue increases by a factor of 10. That is, the v alue of the second 1 2 rightmost digit is 10 , the digit left from it is 10 , etc. W e have ten digits altogether (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), b ecause every tens will b e group ed together by this p ositioning. All other numeral systems are based on the same idea. Considering for example base 2 (the binary system ), we will only need two digits: 0 and 1, b ecause every twos will b e group ed together. The v alues of the digits from right to left will b e the two p owers in increasing order, that is, 1, 2, 4, 8, 16, 32, 64, etc. W e indicate by the numb er 2 in the lower right corner of the numb er that the base is 2. F or example 5 4 3 2 1 0 101011 = 12 +02 +12 +02 +12 +12 = 32+8+2+1 = 43 : 2 10 Numb ers are almost exclusively represented in their binary form in Computer Science. Another typical example from Computer Science could b e the o ctal sys- tem, i.e. base 8 (1 byte equals to 8 bits). Then there are eight digits (0, 1, 2, 3, 4, 5, 6, 7), and the v alues of the digits from right to left are the increasing p owers of 8. Similarly , in Computer Science, base 16 (hexade cimal numb er system) is used. Here, the v alues of the digits from right to left are the in- creasing p owers of 16, and we need 16 digits. That is, we need separate digits for the digits corresp onding to 10, 11, 12, 13, 14 and 15. By convention, we denote these digits by the rst six letters of the alphab et: A = 10 ; B = 11 C = 12 ; 16 10 16 10 16 10 D = 13 ; E = 14 F = 15 : 16 10 14 10 16 10 At rst, it might lo ok strange to use digits for the numb er ten, eleven or twelve. This is actually not so surprising if we think ab out some historical numb er systems. Counting months, or lo oking at the clo ck we use base 12 numeral system. Until 1971 British p eople used base 12 for money exchange (12 p ennies were worth 1 shilling). Moreover, in the English language eleven and twelve have dierent names, they are not generated as all the others20 INTRODUCTION b etween 10 and 20, indicating that they may have b een distinguished as extra digits. Generally , in base n we need n digits, running from 0 to (n 1). W e will write numb ers in p ositional system, as ab ove. The v alues of the digits are the p owers of n going from right to left. That is, the rightmost digit 0 1 has v alue n = 1, the second rightmost digit has v alue n =n, the digit left 2 to it has v alue n , etc. Thus, the numb er a a :::a a a in base n (where t t1 2 1 0 0a n1 for every 0kt) represents the numb er k t X k t t1 2 1 0 (a a :::a a a ) = an =an +a n ++an +an +an : t t1 2 1 0 n k t t1 2 1 0 k=0 Now, the question is how to write numb ers into dierent numeral systems. First of all, to write numb ers from a numeral system into base 10 we basically calculate the v alues of the digits using the p ositional systems, and sum the results: 4 3 2 1 0 10101 = 12 +02 +12 +02 +12 = 16+4+1 = 21 2 10 3 2 1 0 1212 = 13 +23 +13 +23 = 27+18+3+2 = 50 3 10 2 1 0 372 = 38 +78 +28 = 192+56+2 = 250 8 10 2 1 0 AFE = 1016 +1516 +1416 = 2560+240+14 = 2814 : 16 10 Another metho d is to rep eatedly multiply by the base and add the next digit. F or example: 10101 = (((12+0)2+1)2+0)2+1 2 ((22+1)2+0)2+1 = (52+0)2+1 = 21 10 1212 = ((13+2)3+1)3+2 3 = (53+1)3+2 = 163+2 = 50 10 372 = (38+7)8+2 = 318+2 = 250 8 10 AFE = (1016+15)16+14 = 17516+14 = 2814 : 16 10 The other direction is to nd a base n representation of a decimal numb er. Again, it can b e done in two dierent ways. The rst is that we check1.4 Numeral systems 21 the highest n-p ower which is not greater than our numb er, execute division algorithm with this n-p ower, and rep eat the pro cess for the remainder, until the remainder is 0. F or example, write 250 in base 8. The 8-p owers are (in 10 increasing order) 1, 8, 64, 512, the last one is already greater than 250. Thus we execute the division algorithm with 64: 250 = 364+58. Now, 8 is not greater than 58, thus we execute the division algorithm by 8: 58 = 78+2. Finally , 1 is the highest 8-p ower not greater than 2, and after the division algorithm we obtain 2 = 21+0. Thus 2 1 0 250 = 364+78+21 = 38 +78 +28 = 372 : 10 8 Exercise 1.17. W rite 21 in base 2, 50 in base 3, 2814 in base 16 using 10 10 10 the metho d explained ab ove. The other metho d is to execute the division algorithm rep eatedly on the quotients until the quotient is not 0, and then the numb er will consist of the remainders b ackwar ds . F or example, if we want to rewrite 2814 into base 10 16, then 2814 = 17516+14; 175 = 1016+15; 10 = 016+10: The remainders backwards are 10 =A, 15 =F , 14 =E , thus 2814 =AFE : 10 16 Exercise 1.18. W rite 21 in base 2, 50 in base 3, 250 in base 8 using 10 10 10 the division algorithm. How would we write a numb er of an arbitrary base into another (arbi- trary) base? One metho d could b e that we simply rewrite it rst into base 10, then write it into the other system. F or example, if we need to write 372 8 into base 3, we can do the following. Rewrite 372 rst into base 10: 8 2 1 0 372 = 38 +78 +28 = 192+56+2 = 250 : 8 1022 INTRODUCTION Now, rewrite 250 into base 3: 10 250 = 833+1; 83 = 273+2; 27 = 93+0; 9 = 33+0; 3 = 13+0; 1 = 03+1: The remainders backwards are 1, 0, 0, 0, 2, 1, thus 372 = 250 = 100021 : 8 10 3 Finally , we mention that some rewriting can b e done much quicker if one 3 base is a full p ower of another. F or example, 8 = 2 , and then every base 8 digit can b e rewritten easily to three base 2 digits: 0 = 000 ; 1 = 001 ; 8 2 8 2 2 = 010 ; 3 = 011 ; 8 2 8 2 4 = 100 ; 5 = 101 ; 8 2 8 2 6 = 110 ; 7 = 111 : 8 2 8 2 Going from right to left, every three base 2 digits can b e easily rewritten into base 8, as well. Thus, it is easy to rewrite 372 into base 2 or 10101 into 8 2 base 8: 372 = 011 111 010 = 11111010 ; 8 2 2 10101 = 010 101 = 25 : 2 2 8 4 Similarly , as 16 = 2 , every base 16 digit can b e rewritten easily to four

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.