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 onthe 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 thevertices (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 self-loops? _______ (Yes/No).12345Part 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 (oranother method) to prove that (p and q) or ((r p) and (r q)) is equivalent to (r (p and
View Full Document