**Unformatted text preview:**

COT3100 Application of Discrete StructuresSample Test (120 min)January 24, 2017NOTE: This Sample test is only to indicate the rough formal and appearance of the test. DO NOTEXPECT the problems in the actual test to follow the pattern of the problems here. The GOAL of thiscourse is to wean you off the idea that solving problems means following patterns and recipes. The GOALis to get you to think about and solve problems whose ”type” you may never have seen before. The GOALis to get you to think analytically using your native skills and using first principles.NOTE: All tests are CLOSED BOOK. NO CHEAT SHEETS ALLOWED. This class is not about mem-orization. However, if you do all the zybook reading and all the homeworks, you will automatically knowcertain definitions. Any definitions beyond those will be provided in the problem. You would have to readthe definitions carefully, digest them, and use them in understanding the actual problem.1. Prove or disprove that “(¬q → ¬p) ∧ (¬r → ¬q) → (p → r) is a tautology”. (6 points)2. Are the following statements equivalent? “You can go to the movies only if you are over age or havepermission” and “You can go to the movies whenever you are over age or have permission”. Justifyyour answer. (5 points)13. Prove or disprove that [(p → q) ∧ (p → r)] and [p → (q ∧ r)] are logically equivalent. (5 points)4. Consider the following predicates where the domain of x is students and the domain of y is courses.U(y) : y is an upper-level course. M(y) : y is a math course. F (x) : x is a freshman. B(x) : x is afull-time student. T (x, y) : student x is taking course y. If in English, convert to predicate logic. If inpredicate logic, translate to English without using variables. (10 points)(a) All full time students are freshmen.(b) No freshman is taking an upper level math course.(c) ∀x ∃y T (x, y).(d) ∀x ∀y [(T (x, y) ∧ U (y)) ↔ B(x)].25. Are the following system specifications consistent? The system is in multiuser state if and only if it isoperating normally. If the system is operating normally, the kernel is functioning. The kernel is notfunctioning or the system is in interrupt mode. If the system is not in multiuser state, then it is ininterrupt mode. The system is in interrupt mode. Justify your answer. (5 points)6. On the island of knights, knaves and spies you encounter three kinds of people. Knights who alwaystell the truth, knaves who always lie and spies who can either tell the truth or lie. You encounter 3people A, B and C. One of them is a knight, one of them is a knave and one is a spy. (8 points)(a) Suppose Person A says “I’m a knight”, B says “A is not the knave” and C says “B is not theknave”. Can you determine which of these persons is the knight, the knave and the spy? Justifyyour answer.(b) Suppose Person A says “I’m a knave”, B says “A is not the knave” and C says “I’m a knight”.Can you determine which of these persons is the knight, the knave and the spy? Justify youranswer.37. Are the following statements true? Justify your answer. (8 points)(a) ∀x, x2≥ 0, where the domain of x is the set of real numbers.(b) ∃m ∃n m2+ n2= 25, where m and n are integers.8. Are these valid arguments? Justify your answer. (5 points)(a) Suppose x is a real number. If x2is irrational, then x is irrational. Therefore if x is irrational, x2is irrational.(b) Suppose n is a real number. If n > 1, n2> 1. Suppose n2> 1, then n > 1.9. Prove or disprove “The product of two irrational numbers is always irrational”. (5 points)410. Prove or disprove min(a, min(b, c)) = min(min(a, b), c). Given that a, b, and c are integers and thatmin(a, b) gives the minimum of the two numbers. (5 points)11. Let A, B and C be sets. Prove or disprove that A − (B − C) ⊆ A − B. (5 points)12. If A, B and C are sets, prove or disprove A − (B ∩ C) = (A − B) ∪ (A − C). (5 points)513. Consider the following statement. If you do problems, then you learn discrete math.Give the (5 points)(a) Converse(b) Inverse(c) Contrapositive14. Suppose P (x, y) is a predicate and the universe for the variables x and y is {1, 2, 3}. SupposeP (1, 3), P (2, 1), P (2, 2), P (2, 3), P (3, 1), P (3, 2) are true, and P (x, y) is false otherwise. Determinewhether the following statements are true. (5 points)(a) ∀x∃yP (x, y)(b) ∃x∀yP (x, y).(c) ∃x∃y(P (x, y)P (y, x)).6(d) ∀y∃x(P (x, y)P (y, x)).(e) ∀x∀y(x) = y(P (x, y)P (y,

View Full Document