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 understoodthis 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 andat each point of intersecting lines, and thereis 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
View Full Document
Unlocking...