Discrete Mathematics Problems - University of North Florida

1 Discrete Mathematics ProblemsWilliam F. KlostermeyerSchool of ComputingUniversity of North FloridaJacksonville, FL 32224E-mail: Preface31 Basics .. Truth Tables and Logical Equivalences .. Quantifiers .. Circuits .. 112 Sets133 Functions174 Integers and Matrices215 Direct Proofs .. Proofs by Contradiction .. Proofs by Induction .. 276 Basic Problems .. Graphs .. Directed Graphs .. Problems Requiring Proofs .. 357 Counting398 Other Relations .. Algorithm Analysis .. Recurrence Relations .. Generating Functions .. Boolean Algebra .. 47 Chapter 0 PrefaceThis booklet consists of problem sets for a typical undergraduate discretemathematics course aimed at computer science students. These problemmay be used to supplement those in the course textbook.

2 We felt that inorder to become proficient, students need to solve many Problems on theirown, without the temptation of a solutions manual! These Problems havebeen collected from a variety of sources (including the authors themselves),including a few Problems from some of the texts cited in the Problems are marked with a .References to the bibliography are indicated by [x], where x is the num-ber of a bibliography 0. PREFACEC hapter BasicsEvaluate each of the 2 is even, then 5= 2 is odd, then 5= 4 is even, then 10 = 7+ 4 is odd, then 10= 7+ the following, assume thatpis true,qis false, andris q r(you may want to add parentheses!)6. q (q p)56 CHAPTER 1. p11.(q p) (q (r p)) Truth Tables and Logical EquivalencesGive truth tables for each of the q r2. p q3.(p q) p4.(p q) (q p)5.(p q) q6.(p q) (q p)7.

3 (p q) r8.(p q) TRUTH TABLES AND LOGICAL EQUIVALENCES79.(p q) (p q)Which of the following are tautologies?10.(p p) p11.(p q) ( p q)12.(p p) q13.(p q) ( p q)Prove or disprove each of the following using (a) truth tables and (b)the rules of (p q) (p q) True15. (p q) q True16.[2] (p (p q)) q q q p18. ( p q) q p q19. ( p q) q q (q r) p (q r) (q r) p (q r)8 CHAPTER 1. LOGIC22.(p (q r)) (p q) (p q) TrueRe-write the following using only ; ; (q r) (q r)26. q (p q)Re-write the following CNF formulae into DNF27.(p q r) ( p q)28.(p q r) ( p q r) (p q)Use truth tables to verify the following:29.[2] (p (p q)) p30.[2] (p (p q)) p31. Show that (p q r s) can be re-written into an equivalent CNFformula such that each clause contains exactly 3 variables or negationsof that p not (not q and not p) is logically equivalent to Quanti ersEvaluate each of the following for the universeZ, the set of (2), whereP(x) =x (4) whereP(x) = (x= 1) (x >5) (x) whereP(x) = (x <0) (x = 23)4.

4 X(x= 5) (x= 6)5. x(x= 5) (x 5)6. x(x= 5) (x 5)7. x(x <0) (x 2x)8. x x2>09. x x2= 010. x y x < y11. x y x < yIn the following, let the universe beZ+12. x y(x+y= 0) (x y= 0)13. x y(x y x+y)10 CHAPTER 1. LOGIC14. x y(x < y)15. x y(x y)16. x y((x= 3) (y= 4)17. x y z(x2 y+z= 0)18. x y((x >1y))19. x y(x2=y 1)20. y x z((y=x+z) (z x))Re-write the following without any negations on quantifiers21. xP(x)22. x yP(x; y)23. xP(x)24. x yP(x; y)25. x yP(x; y) that x yP(x; y) x yP(x; y) is (or is not) a that ( x(P(x) yP(y))) is equivalent to xP(x). CIRCUITS1128.[2] Argue that x(P(x) y) is equivalent to ( xP(x)) CircuitsDesign logic circuits, using AND, OR, and NOT gates to solve the two bits,x; yand output two bits representingx y(1 1 = 00,1 0 = 01, 0 0 = 00, 0 1 = 11). two bitsx; yand output two bits representing the absolute valueofx three bitsx; y; zand output one bit which is the majority of thethree input bits12 CHAPTER 1.)

5 LOGICC hapter 2 SetsList the elements of the following sets. Assume the universe isZ.(Note: 2 Xdenotes the power set ofX)1.{x|x2= 6}2.{x|x2= 9}3.{x|(xmod 2 = 1) (x <10)}(Assume universe isZ+for this prob-lem)4.[2]{x|x=x2}5.{x| k {2;3; : : : x 1}xmodk= 1}(Assume universe isZ+for thisproblem)6.{a; b; c} {1;2}7.{1;2} {a; b; c}1314 CHAPTER 2. SETS8.{a; b; c} 9.{a; b} {1} {x; y} {a;{a}}11.[2] Isx {x}? Isx {x}? Is {x}? Is {x}? Is{x} {x}?What is the cardinality of each of the following sets?12.{{x}}13. 14.{ }15.{{ }}16.{x;{x}; } LetA={1;2;4;5;7;8}; B={x|(x Z+) (x <10)}; C={x|(x Z+) (xmod 3<2}. List/describe the elements of the following { } B general, when are two setsD; Esuch thatD E=D E? B, then what is|A B|?16 CHAPTER 2. SETSP rove the following set identities, using either Venn Diagrams or therules of [2]A (B A) = 37.)

6 [2] (A B) (A B) =A38.[2] (A B) C A C39.[2] (A C) (C B) = that the symmetric difference operator does , or does not, alwayssatisfy the associative the elements in the following sets. Assume the universe isZ+:41.{x|x <8}42.{x|x= 6 x 4} the elements of{1;2;3;4} {2;3;5;7} {1;5;9} the elements of{1;2;3;4} {2;3;5;7}Chapter 3 FunctionsWhat is the value of each of the following:1. 1:5 2. 2:6 3. 1:1 4. 1:3 isxsuch that x x= x x6.[2] Show that 2x = x + x+12 log227 9. log285 1718 CHAPTER 3. ! 25 Convert the following to the following binary numbers to base 10 each of the following, assume thatf:Z Z. Then identify whethereach is a function, onto function, one-to-one function, (x) =x2 (x) =x2+ (x) = (x) = x (x) = (x) = (x) = (i)x2if x is even; (ii)2x 1 if x is (x) = log x, where log x= 1 + log ( log2x ) and log x= 1 forx compute log a recursive function such thatf(n) = 5(2n).

7 (n) = 1 forn 1 andf(n) = 2f(n 1) + 3. Compute the valuesoff(n) forn (n) = 1 forn 2 andf(n) = 2f(n 1) +f(n 1)f(n 2).Compute the values off(n) forn that log(n!) nlognfor alln (n) = 2 forn 2 andf(n) =f(n 1) +f(n 2) + 1. Computethe values off(n) forn (n) = 1 forn 2 andf(n) = 2f(n 1) 1. Compute the valuesoff(n) forn 3. FUNCTIONSC hapter 4 Integers and is the prime factorization of 90? of 8100? is 57 modxfor eachx= 2;3;4;5? many integers less than 45 are relatively prime to 45?4.[2] Show that ifa; b; mare positive integers, thenamodm=bmodmifa =b(modm).5.[2] Show that ifa; b; mare positive integers, thena =b(modm) ifamodm= is the gcd of 200 and 88? is the gcd of 17 and 42? that ifa|bandb|cthena| is the value of i=6i=22i+1?2122 CHAPTER 4. INTEGERS AND 2n 1 prime for all values ofn? is the value of i=5i=0i+ 1? is the value of i=8i=1 i2 ?

8 Is 17 mod 5? is 81 mod 7? is 812mod 7? is the value of i=6i=1i 2? 7 and 49 relatively prime? is the value of (19 3001) mod 3? a closed form formula that is equal to of i=ni=23i 1? is 10! mod 2? is 487! mod 67? that if every even integern 4 is the sum of two (not necessar-ily distinct) primes, then every odd integerm 7 is the sum of three(not necessarily distinct) is 7272mod 3? is 833mod 3? is the largest positive integerksuch that (324 modk) = (374 modk) = (549 modk)? (What principle can you use to solve this problemquickly?) what positive values ofnis 2n+ 1 divisible by 3? Prove youranswer is 4. INTEGERS AND MATRICESC hapter Direct that ifnis odd, thenn2is the solution to the previous problem to prove that ifnis odd, thenn3is odd. Also, find a direct proof that does not rely on the solutionto the previous thatnis even if and only ifn2is that the power set of an infinite set is also (A) denote the power set of setA.

9 Let A and B be sets such thatA =B. That is, there exists an elementxsuch thatx Aandx = thatP(A) =P(B) by showing there exists a specific element inP(A) that is not inP(B) or a specific element inP(B) that is not inP(A). that ifnandmare positive, even integers, thennmis divisibleby perfect number is a positive integernsuch that the sum of the fac-tors ofnis equal to 2n(1 andnare considered factors ofn). So 6 is2526 CHAPTER 5. PROOFSa perfect number since 1 + 2 + 3 + 6 = 12 = 2 6. Prove that a primenumber cannot be a perfect that there does not exist an integern >3 such thatn; n+2; n+4are each that (amod 2)(bmod 2) = (ab) mod or disprove that ifa2 b2(modc) thena b(modc).11.[2] Prove that there are no integer solutions tox2 3 = 4y. (Hint: Doa proof by cases, the cases being the value ofxmodulo 4). that ifp; qare positive integers such thatp|qandq|p, thenp= that for any integerx, the integerx(x+ 1) is that the product of any two odd integers is y 1.

10 Prove that ifgcd(x; y) =ythenlcm(x; y) = ; ybe positive integers. Prove thatlcm(x; y) =xy=gcd(x; y). Proofs by ; Bbe sets. Prove that if|A B|=|A|+|B|, thenA B= . (x) andg(x) be functions. Prove, using contradiction method,that iff(g(x)) is one-to-one, theng(x) is one-to-one. That is, supposethatg(x) were not one-to-one and derive thatf(g(x)) cannot be PROOFS BY ; Bbe sets. Prove that (A B) (B A) = . A, B be non-empty sets. Prove that ifA B=B A, thenA= that in any set ofnnumbers, there is one number whose valueis at least the average of A, B be finite sets. Prove that ifA B= 0 and there is a bijectionbetween A and B, thenA= problem is taken from Maryland Math Olympiad problem, andwas posted on the Computational Complexity Web Log. Suppose wecolor each of the natural numbers with a color from{red; blue; green}.Prove that there exist distinctx; ysuch that|x y|is a perfect square.