COT3100 01 Spring 2000 Test 1Print Name S Lang 2 16 2000 Social Security No Instruction The test is a closed book closed notes and no calculator test The test has 4 pages 11 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 their name or giving their 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 or fill in the blank questions No explanation is needed 1 Let A B C denote arbitrary finite sets Answer each of the following True False questions If A C B C then A B If A C and B C then A B C A B A B If A B A then A B B 2 Let a b c denote integers Answer each of the following True False questions If a b c and a b then c 0 If a b is odd then ab is odd If a b and a c then a b c 3 Let p q r denote arbitrary statements propositions Answer each of the following True False questions p and p or q is equivalent to p and q If p q is true then p and r q and r is true If p q is false then p is false and q is false 4 Let W T and Y denote sets of strings over an alphabet A Answer each of the following True False questions If W T then W T If W T then WY TY 5 If u and v are two distinct vertices in a graph G V E Suppose there is a simple path connecting vertex u to vertex v and there is a simple path connecting vertex v to vertex u then there must be a simple cycle circuit connecting vertex u to itself True False 6 Consider the graph given in the figure consisting of intersecting squares and lines in which there is a vertex at each corner and at each point of intersecting lines and there is an edge between each pair of adjacent vertices no vertex or edge labels are given Can the edges of the graph be traversed by an Euler path or circuit Yes No Part II 33 pts Short Questions Justify each step of your proof 7 Let A and B denote two arbitrary sets a 8 pts Prove Power A Power A B b 5 pts Prove that Power A Power B 8 10 pts Let A and B denote two sets Prove A B A A B Part II Cont d 9 10 pts Let a b denote two integers If a b is odd then prove a2 ab is odd or b2 ab is odd Part III 25 pts Longer Questions Justify each step of your proof 10 10 pts Let W and T denote two sets of strings If W T prove WT T Hint First prove WT T 11 15 pts Let p q r denote arbitrary statements propositions Use the truth table method to prove that p or q or r is equivalent to p r and q r
View Full Document
Unlocking...