Mathematical Foundations of Computing Problems 1. Write each of the following conditional statements and the corresponding converse, inverse, and contrapositive as English sentences in the form "if p, then q." Example: Whenever it rains, it pours. Answer: Original statement: If it rains, then it pours. Converse: If it pours, then it rains. Inverse: If it doesn't rain, then it doesn't pour. Contrapositive: If it doesn't pour, then it doesn't rain. 1.1 You can do it if you put your mind to it. 1.2 Being cold implies that you need a jacket. 1.3 Petting the cat is sufficient for it to purr. 2. Determine the truth value of each of the following statements if the domain consists of all integers. If it is true, find a different domain for which it is false. If it is false, find a different domain for which it is true. Justify your answers. Example: vx(x≤ 2x) Answer: False. If x = -1, then 2x = -2 and -1 > -2. True when the domain consists of all nonnegative integers. For all nonnegative integers x, x ≤ 2x. 2.1 3x(x + 2 = 3) 2.2 x(x^320) 2.3 vxy(x >y) 2.4 3xvy(xy > 0) 3. Let F(x) be the statement "x is a freshman," S(x) be the statement "x is a sophomore," and W(x, y) be the statement "x waved at y." If the domain of x and y consists of all students, express each of the following sentences in terms of F(x), S(x). W(x, y), quantifiers, and logical operators. Example: Some freshman waved at every sophomore. Answer: 3x(F(x)^vy(S(y) → W(x, y))) 3.1 There is a freshman and a sophomore who waved at each other. 3.2 There is a sophomore who was not waved at by any freshman. 3.3 Every freshman waved at another freshman. 3.4 There is exactly one sophomore who didn't wave at any student. 4. Use the laws of propositional logic to prove that the following compound propositions are logically equivalent. You must indicate the name of the law used in each step of the proof. Example: pq and q p Answer: p-q =pV q Conditional identity qVp Commutative law =¬q→→p Conditional identity 4.1 (p/q) →r and p → ¬(q^¬r) 4.2 (pr) V (qr) and (p ^q) → r 4.3 p+q and (p ^¬q) V (q ^p) 4.4 (p^q) →q and q→ p 5. Use the laws of propositional logic to prove that the following compound propositions are tautologies. You must indicate the name of the law used in each step of the proof. Example: p → p Answer: P-p p V pר = ET Conditional identity Complement law 5.1 (p^q) (p— q) 5.2 ((pq)^(p → r)) → (~r— q ) A compound proposition is said to be satisfiable if there is an assignment of truth values to its variables that makes it true. For example, p ^ q is satisfiable because it is true when p = I and q = T. When no such assignment exists, the compound proposition is said to be unsatisfiable. For example, p^p is unsatisfiable because it is always false. To show that a compound proposition is satisfiable, we need to find at least one assignment of truth values to its variables that makes it true. However, to show that a compound proposition is unsatisfiable, we need to show that every assignment of truth values to its variables makes it false. Determine whether each of the following compound propositions is satisfiable or unsatisfiable. Justify your answers. 6.1 (pq) →(p v q) 6.2 (pq)^(p → ¬q) 6.3 (pq)^(p → ¬q) ^ (¯p →q)^(p-q) 6.4 (pvq)^(-pv-q) ^ (¯p \ q) ^ (pvr) ^ (¯p \ -r)