Given individual propositions p and q, verify the following logical equivalences by constructing a truth table for each part (t and f represent true and false respectively):
(a) (10 points) p ∧ (t ∨ p) ≡ p ∧ t
(b) (10 points) ¬(p ⊕ q) ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
(c) (10 points) ¬((p ∧ ¬q) → q) ≡ p ∧ ¬q
2. given any individual propositions p, q, and r, use the laws of propositional logic (listed in table 1.5.1 of the textbook) to prove the following logical equivalences.
(a) (5 points) p ∧ (q ∨ ¬r) ≡ (p ∧ q) ∨ ¬(¬p ∨ r)
(b) (5 points) t ∧ (p ∨ t) ≡ f ∨ (f ⊕ t)
3. formulate the following sentences using (nested) quantified statements. in each part, you need to specify appropriate domain for any variable participating in the statements. 1 (a) (5 points) the product of any two negative integers is greater than their summation.
(b) (5 points) for any given positive number, there is another positive number greater than it and another positive number less than it.
4. (10 points) using the demorgan’s law, negate the quantified statements obtained in the previous question.
5. (10 points) state the contrapositive, converse, and inverse of the following conditional statements:
(a) if the gold price increases, then, the oil price decreases.
(b) if you become vegetarian, then, you will lose weight.
6. (80 points) in each part, use the given method to prove/disprove the statements:
(a) (10 points) disprove the following statement by finding an appropriate counterexample: for every real numbers x, y, and z, if x > 0, y > 0, and z > 0, then 10−3z + x 2 + y 2 + z 2 ≤ (x + y + z) 2 .
(b) (10 points) use the method of exhaustion to prove the following statement: “for every prime number p between 30 and 58, 10 does not divide p − 9.”
(c) (10 points) prove that 0.17461746 . . is rational (digits 1746 in the fractional part are repeated forever).
(d) (10 points) use prove by cases to show that for every integer n, n 2 + 3n − 7 is odd.
(e) (10 points) using the method of proof by division into cases, prove that for every integer n, (n + 4)2 is not prime.
(f) (10 points) use the method of direct proof to prove the following statement: ∀m, n, l ∈ z, (m is even ∧ n is odd) → (ml + n is odd)
(g) (10 points) using the method of proof by contradiction, prove that there is no largest negative rational number.
(h) (10 points) using the method of proof by contradiction, prove that if a product of two positive real numbers is greater than 1,000,000, then at least one of the numbers is greater than 1000.
7. (20 points) assuming that a, b, and c specify three sets, prove the following equations using the definition of set operations.
(a) (10 points) a ⊕ b = (a ∩ b) ∪ a ∪ b 2 (b) (10 points) a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪ c)
8. (20 points) in each of the following parts, specify the correctness of the statement and justify your answer
(a) (5 points) {1, 2, . . , 10} ⊂ {n ∈ z +|n 2 < 120}
(b) (5 points) {x ∈ r|1 < x < 5} ⊆ q
(c) (5 points) p(∅) ⊆ ∅ (d) (5 points) |{1, √ 9, 4, 3}| = 4
9. (20 points) let a = {1, 2, 3, 4} and b = {a, b, c, d}. in each part, specify whether the given set is a function from a to b or not. justify your answer.
(a) (5 points) f = {(1, , , , a)}
(b) (5 points) g = {(1, , , c)}
(c) (5 points) h = {(1, , , , , a)}
(d) (5 points) j = {(1, , , , a)}
10. (10 points) prove that the following function f : r + 7→ r> 2 is both injective and surjective and therefore, bijective. f(x) = 2 + √ x
11. (10 points) use the method of disproof by counterexample to show that function g : z 7→ z with the following general formula is neither injective nor surjective: g(n) = n 2 − 8
12. (10 points) let f and g be two boolean functions defined in the following way. by constructing input/output table for both functions, show that f = g. f(x, y, z) = xyz + (¯x + ¯y)z g(x, y, z) = xy + ¯z