Discrete Structures COT 3100 Final Exam Spring 2000 Section 2 4 25 00 Lecturer Arup Guha TA 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 or FALSE 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 FALSE b x y x y 10 TRUE FALSE c If the contrapositive of a statement is true TRUE FALSE then the converse of statement is true as well d x p x x p x TRUE FALSE e Let A B and C be sets If A B and A B B C then A C TRUE FALSE f The total number of subsets of 2 4 5 6 9 is 25 TRUE FALSE g If a b and a c then gcd b c a TRUE FALSE h If R is a bijection A B and S is a surjection B C then R S is an injection A C TRUE FALSE i Let A and B be sets of strings such that A B then A B TRUE FALSE j 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 of strings 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 FALSE 2 8 pts Fill in the following Truth Table to evaluate the expression p q r r q p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 q r p q r r q p q r r q 3 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 b bbbbbbbbb c aabaaaa d ababababa e aabbabbabbaaaa f babababa YES YES YES YES YES YES NO NO NO NO NO NO 8 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 n i i n 1 1 i 1 13 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 on
View Full Document
Unlocking...