COT3100 01 Fall 2000 Test 1Print Name S Lang 10 3 2000 Social Security No Instruction The test is a closed book closed notes and no calculator test The test has 4 pages 10 questions and 100 total points The last sheet contains the relevant definitions and theorems from the notes which you can tear off and use for reference In writing your proofs you need to show all the steps and explain each by using the appropriate definition or theorem by either stating the name stating the actual contents or giving its reference number as shown on the reference sheet Also be aware that the subset notation used in the test questions means a subset of or equal to which is denoted in the text Your signature below indicates you have read and understood this instruction Signature Part I 42 pts True False questions No explanation is needed 1 Let A B C denote arbitrary finite sets Answer each of the following True False questions If C A B then C B A If A B then A B C A C B C A A B B 2 Let a b c d denote integers positive zero or negative Answer each of the following True False questions If a b c d then a c b d If a b is even then a 3b is odd If ac bc 0 then a b 3 Let p q r denote arbitrary statements propositions Answer each of the following True False questions If p q is false and q is true then p is false If p and r is false and p is true then r is false p p and r is true 4 Let W S and T denote sets of strings over an alphabet A Answer each of the following True False questions W S If W and T both are finite sets then WT W T 5 Consider the graph given in the figure consisting of intersecting circles in which the vertices are labeled by numbers 1 2 etc and edges are the curved lines connecting the vertices no edge labels are given Answer each of the following Yes No questions Can the edges of the graph be traversed by an Euler path or circuit Yes No Does the graph contain edges that are selfloops Yes No 2 1 4 3 5 Part II 30 pts Short Questions Justify each step of your proof 6 10 pts Let A B and C denote three sets If A C B C C prove A B Hint Prove the contrapositive 7 10 pts Let a b and c denote integers Suppose a b and a c and a 1 that is a is a common divisor of b and c and a 1 If 12b 25c p where p is a prime number prove a p Hint First prove a 12b 25c Part II Cont d 8 10 pts Let W S and T denote sets of strings over an alphabet A If W S T prove that S W T Part III 28 pts Longer Questions Justify each step of your proof 9 14 pts Let A and B denote sets Prove Power A B Power A A B Note that there are two parts in the question 10 14 pts Let p q r denote arbitrary statements propositions Use the truth table method or another method to prove that p and q or r p and r q is equivalent to r p and q
View Full Document
Unlocking...