CMSC250, Spring 2004 Homework 4 AnswersDue Wednesday, February 25 at the beginning of your discussion section.You must write the solutions to the problems single-sided on your own lined paper,with all sheets stapled together, and with all answers written in sequential order oryou will lose points.1. Complete the following proofs using the metho d described in class (line numbers, rules, etc).(a)P1 ∀x ∈ D P (x) → (T (x) ∨ Q(x))P2 ∀y ∈ D Q(y) ∨ (R(y) ∧ P (y))P3 ∀z ∈ D (T (z) ∧ R(z)) → S(z)∴ ∀w ∈ D ∼ Q(w) → S(w)Answer:Line Statement Rule Lines Used1 Q(a) ∨ (R(a) ∧ P (a)) ∀ instantiation P22 ∼ Q(a) Assume —3 R(a) ∧ P (a) Disjunctive syllogism 1, 24 P (a) Conjunctive simplification 35 T (a) ∨ Q(a) ∀ modus ponens 4, P16 R(a) Conjunctive simplification 37 T (a) Disjunctive syllogism 2, 58 T (a) ∧ R(a) Conjunctive addition 6, 79 S(a) ∀ modus ponens P3, 810 ∼ Q(a) → S(a) CCW w/out contra 2–911 ∀w ∈ D ∼ Q(w) → S(w) ∀ generalization 10Another way:Line Statement Rule Lines Used1 Q(a) ∨ (R(a) ∧ P (a)) ∀ instantiation P22 ∼ (∼ Q(a) → S(a)) Assume —3 ∼ Q(a)∧ ∼ S(a) Definition of → 24 ∼ Q(a) Conjunctive simplification 35 ∼ S(a) Conjunctive simplification 36 ∼ (T (a) ∧ R(a)) ∀ modus tollens 5, P37 ∼ T (a)∨ ∼ R(a) DeMorgan’s law 68 R(a) ∧ P (a) Disjunctive syllogism 1, 49 R(a) Conjunctive simplification 810 P (a) Conjunctive simplification 811 ∼ T (a) Disjunctive syllogism 7, 912 ∼ T (a)∧ ∼ Q(a) Conjunctive addition 4, 1113 ∼ (T (a) ∨ Q(a)) DeMorgan’s law 1214 ∼ P (a) ∀ modus tollens P1, 1315 ∼ P (a) ∧ P (a) Conjunctive addition 14, 1016 ∼ Q(a) → S(a) CCW w/ contra 2–1517 ∀w ∈ D ∼ Q(w) → S(w) ∀ generalization 161(b)P1 ∀t ∈ D (A(t) → B(t)) → (C(t) ∨ D(t))P2 ∃u ∈ D ∼ A(u) ∧ (D(u) → E(u))P3 ∀v ∈ D ∼ E(v) → (C(v) → A(v))∴ ∃h ∈ D ∼ B(h) ∨ E(h)Answer:Line Statement Rule Lines Used1 ∼ A(a) ∧ (D(a) → E(a)) ∃ instantiation P22 ∼ A(a) Conjunctive simplification 13 ∼ A(a) ∨ B(a) Disjunctive addition 24 A(a) → B(a) Definition of → 35 C(a) ∨ D(a) ∀ modus ponens P1, 46 D(a) → E(a) Conjunctive simplification 17 ∼ (∼ B(a) ∨ E(a)) Assume —8 B(a)∧ ∼ E(a) Double negation, DeMorgan’s law 79 ∼ E(a) Conjunctive simplification 810 ∼ D(a) Modus tollens 6, 911 C(a) Disjunctive syllogism 5, 1012 C(a)∧ ∼ A(a) Conjunctive addition 2, 1113 ∼ (∼ C(a) ∨ A(a)) Double negation, DeMorgan’s law 1214 ∼ (C(a) → A(a)) Definition of → 1315 E(a) ∀ modus tollens, Double negation P3, 1416 E(a)∧ ∼ E(a) Conjunctive addition 15, 917 ∼ B(a) ∨ E(a) Closing cond world w/ contra 7–1618 ∃h ∈ D ∼ B(h) ∨ E(h) ∃ generalization 17Another way:Line Statement Rule Lines Used1 ∼ A(a) ∧ (D(a) → E(a)) ∃ instantiation P22 ∼ A(a) Conjunctive simplification 13 D(a) → E(a) Conjunctive simplification 14 ∼ A(a) ∨ B(a) Disjunctive addition 25 A(a) → B(a) Definition of → 46 C(a) ∨ D(a) ∀ modus ponens P1, 57 C(a) Assume —8 C(a)∧ ∼ A(a) Conjunctive addition 7, 29 ∼ (C(a) → A(a)) Definition of → 810 E(a) ∀ modus tollens 9, P311 C(a) → E(a) Closing cond world w/out contra 7–1012 E(a) Dilemma 6, 3, 1113 ∼ B(a) ∨ E(a) Disjunctive addition 1214 ∃h ∈ D ∼ B(h) ∨ E(h) ∃ generalization 13(c)P1 ∀w ∈ D J (w) → M(w)P2 ∀x ∈ D M(x) → ((N(x) →∼ J(x))∧ ∼ K(x))P3 ∀y ∈ D N(y)∨ ∼ L(y)P4 ∀z ∈ D (J(z) ∧ K(z)) ∨ (L(z) ∧ M(z))∴ ∀q ∈ D ∼ J(q)2Answer:Line Statement Rule Lines Used1 N(a)∨ ∼ L(a) ∀ instantiation P32 (J(a) ∧ K(a)) ∨ (L(a) ∧ M(a)) ∀ instantiation P43 J(a) Assume —4 M(a) ∀ modus ponens P1, 35 (N(a) →∼ J (a))∧ ∼ K(a) ∀ modus ponens P2, 46 N(a) →∼ J (a) Conjunctive simplification 57 ∼ N(a) Modus tollens, double neg 6, 38 ∼ L(a) Disjunctive syllogism 1, 79 ∼ K(a) Conjunctive simplification 510 ∼ J(a)∨ ∼ K(a) Disjunctive addition 911 ∼ (J(a) ∧ K(a)) double neg, DeMorgan’s law 1012 L(a) ∧ M(a) Disjunctive syllogism 2, 1113 L(a) Conjunctive simplification 1214 L(a)∧ ∼ L(a) Conjunctive addition 8, 1315 ∼ J(a) CCW w/ contra 3–1416 ∀q ∈ D ∼ J(q) ∀ generalization 15Another way:Line Statement Rule Lines1 M(a) → ((N (a) →∼ J(a))∧ ∼ K(a)) ∀ instantiation P22 ∼ M(a) ∨ ((N(a) →∼ J (a))∧ ∼ K(a)) Definition of → 13 ∼ M(a) Assume —4 ∼ J(a) ∀ modus tollens P1, 35 ∼ M(a) →∼ J (a) CCW w/out contra 3–46 (N(a) →∼ J (a))∧ ∼ K(a) Assume —7 N(a) →∼ J (a) Conjunctive simp 68 ∼ K(a) Conjunctive simp 69 ∼ J(a)∨ ∼ K(a) Disjunctive addition 810 ∼ (J(a) ∧ K(a)) DeMorgan’s law 911 (J(a) ∧ K(a)) ∨ (L(a) ∧ M(a)) ∀ instantiation P412 L(a) ∧ M(a) Disjunctive syllogism 10, 1113 L(a) Conjunctive simp 1214 N(a)∨ ∼ L(a) ∀ instantiation P315 N(a) Disjunctive syllogism 13, 1416 ∼ J(a) Modus ponens 15, 717 [(N(a) →∼ J (a))∧ ∼ K(a)] →∼ J(a) CCW w/out contra 6–1618 ∼ J(a) Dilemma 2, 5, 1719 ∀q ∈ D ∼ J(q) ∀ generalization 182. Translate each of the following into formal language using the sets and predicates given.(a) Exactly two people completely understand quantum physics. (U = {universal set},P (m) = m is a person, Q(n) = n completely understands quantum physics.)Answer:∃a, b ∈ U P (a) ∧ Q(a) ∧ P (b) ∧ Q(b) ∧ a 6= b ∧ ∀x ∈ U (P (x) ∧ Q(x)) → (a = x ∨ b = x)3(b) I own at least three cats. (C = {all cats}, N (x) = I own x.)Answer: ∃a, b, c ∈ C N (a) ∧ N (b) ∧ N (c) ∧ a 6= b ∧ b 6= c ∧ c 6= a(c) No more than two people own both a kangaroo and a polar bear. (P = {all people},K(p) = p owns a kangaroo, B(p) = p owns a polar bear.)Answer:∀p, q, r ∈ P (K(p) ∧ K(q) ∧ K(r) ∧ B(p) ∧ B(q) ∧ B(r)) → (p = q ∨ q = r ∨ r = p)3. For each of the following, decide if the argument is valid or invalid, and write “invalid” or“valid” as appropriate. If it is invalid, draw an Euler diagram to verify this fact. If it is valid,draw an Euler diagram that shows the premises and conclusion all to b e true.(a) • All shortshops can steal bases.• Some shortstops can hit home runs.• Therefore, some shortstops can steal bases and hit home runs.Answer: VALIDshortstopsstealbaseshithomeruns(b) • All CS professors are intelligent.• All CS professors like music.• Therefore, all intelligent people like music.Answer:
View Full Document