Discrete Structures(COT 3100) Final ExamSpring 2000Section 24/25/00Lecturer: Arup GuhaTA: __________________First Name : ________________Last Name : ________________(Note: On all questions that contain a blank line, please place your answer on that line clearly. If a short answer question doesn’t have a line for you to place your answer, please neatly write your answer directly below the question. Circle TRUE orFALSE for all true/false questions.)1) (15 pts) True/False. You will get one point for each question answered correctly, zero points for each question left blank, and negative one point for each incorrect response.a) (p q) (q p) TRUE FALSEb) xy [x + y = 10] TRUE FALSEc) If the contrapositive of a statement is true, TRUE FALSEthen the converse of statement is true as well.d) [x p(x)] x p(x) TRUE FALSEe) Let A, B and C be sets. If AB and A B = B C, then A = C. TRUE FALSEf) The total number of subsets of {2,4,5,6,9} is 25. TRUE FALSEg) If a | b and a | c, then gcd(b,c) a. TRUE FALSEh) If R is a bijection (A B), and S is a surjection (B C), then RS is an injection (A C). TRUE FALSEi) Let A and B be sets of strings such that A* B*, then A B. TRUE FALSEj) The number of bijective functions over a set A={1,2,3} is 6. TRUE FALSE k) A DFA must have more than one final state. TRUE FALSE l) A language containing a finite number ofstrings is a regular language. TRUE FALSE m) A DFA with n states that accepts at least one string MUST accept at least one string with a length less than or equal to n. TRUE FALSE n) a+ is NOT a valid regular expression. TRUE FALSE o) | | = 0. TRUE FALSE2) (8 pts) Fill in the following Truth Table to evaluate the expression (p (q r)) (r q).p q r q r p (q r) r q (p (q r)) (r q)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 13) Let the set A = {1, 4, 9, 16, 25, 36, 49, 64}. a) (4 pts)How many non-empty subsets of A have the property that __________ the product of all of their elements is less than or equal to 100? b) (2 pts) How many subsets of A contain no odd numbers? __________ c) (2 pts) How many subsets of A contain at least one odd number? ___________4) (4 pts) Use Euclid’s Algorithm to find the greatest common divisor of 240 and 87.5) (5 pts) Draw a DFA to recognize the language of all binary strings (over the alphabet 0 and 1) that are divisible by 4.6) (4 pts) The regular expression R1 = a*b b*a is NOT equivalent to the regular expression R2 = (a b)*ab. Find a string that fits R1 but NOT R2, and also find a string that fits R2 but NOT R1. A string that fits R1 but not R2 is _______________________ A string that fits R2 but not R1 is _______________________7) (6 pts) Consider the following DFA: Which of the following strings are accepted by this DFA? a) aaabb YES NO b) bbbbbbbbb YES NO c) aabaaaa YES NO d) ababababa YES NO e) aabbabbabbaaaa YES NO f) babababa YES NO8) (5 pts) Let A be a set such that |Power(A)| = |A| + 2. What is |A|? _________9) (7 pts) What is the regular expression for the language over the __________ alphabet {a,b} that contains all strings that do not have consecutive b’s in them.10) (15 pts) Prove that 9 | (22n – 3n – 1), for all integers n 0. (Hint: For all positive integers a > 1 and m > 0, (a-1) | (am – 1). )11) (7 pts) Draw a DFA to accept the language of strings over the alphabet {a,b} that contains exactly 3 a’s.12) (10 pts) Remember that n! = 1*2*3*...*n. Prove the following summation for all integers n 1 using induction:niii1!* = (n+1)! – 113) (10 pts) If a relation is transitive and reflexive is it necessarily symmetric? If so, justify your answer. If not, show a counter example.14) (10 pts) Consider the first line of the Euclidean algorithm: a = bq + r1, 0 < r1 < b, a and b are positive integers such that a > b.Prove that a > 2r1. (Hint: Break your proof into two cases. Consider all sets of values a and b such that a > 2b, and a < 2b. Since r1> 0, you are guaranteed that a 2b.)15) (5 pts) Prove or disprove: Let W and T be sets of strings over the alphabet {a,b}. If (W T)* = T*, then W T.16) (10 pts) Let R = {(a,b) | a Z+ and b Z+ and both a and b have a digit in common.} Thus, (17,76) R, since both 17 and 76 contain a 7. Is R reflexive? Is R symmetric? Is R transitive? Prove your answers.17) (10 pts) Prove that (p q) (p ( (q r) (q r) ) ) (p q) p, using the laws of logic. State each rule you use. (You may continue onto the next page.)18) (10 pts) Let A, B and C denote three sets. If A B C, prove that A – C A – B.19) (1 pt) Who hosts the Oprah Winfrey show? _________________________Extra Page – If you want any work on this page to be graded, clearly mark the question you are working
View Full Document
Unlocking...