CMSC250 Spring 2004 Homework 4 Answers Due 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 or you will lose points 1 Complete the following proofs using the method 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 1 Q a R a P a instantiation 2 Q a Assume 3 R a P a Disjunctive syllogism 4 P a Conjunctive simplification 5 T a Q a modus ponens 6 R a Conjunctive simplification 7 T a Disjunctive syllogism 8 T a R a Conjunctive addition 9 S a modus ponens 10 Q a S a CCW w out contra 11 w D Q w S w generalization Lines Used P2 1 2 3 4 P1 3 2 5 6 7 P3 8 2 9 10 Another way Line 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Statement Q a R a P a Q a S a Q a S a Q a S a T a R a T a R a R a P a R a P a T a T a Q a T a Q a P a P a P a Q a S a w D Q w S w Rule instantiation Assume Definition of Conjunctive simplification Conjunctive simplification modus tollens DeMorgan s law Disjunctive syllogism Conjunctive simplification Conjunctive simplification Disjunctive syllogism Conjunctive addition DeMorgan s law modus tollens Conjunctive addition CCW w contra generalization 1 Lines Used P2 2 3 3 5 P3 6 1 4 8 8 7 9 4 11 12 P1 13 14 10 2 15 16 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 1 A a D a E a instantiation 2 A a Conjunctive simplification 3 A a B a Disjunctive addition 4 A a B a Definition of 5 C a D a modus ponens 6 D a E a Conjunctive simplification 7 B a E a Assume 8 B a E a Double negation DeMorgan s law 9 E a Conjunctive simplification 10 D a Modus tollens 11 C a Disjunctive syllogism 12 C a A a Conjunctive addition 13 C a A a Double negation DeMorgan s law 14 C a A a Definition of 15 E a modus tollens Double negation 16 E a E a Conjunctive addition 17 B a E a Closing cond world w contra 18 h D B h E h generalization Lines Used P2 1 2 3 P1 4 1 7 8 6 9 5 10 2 11 12 13 P3 14 15 9 7 16 17 Another way Line 1 2 3 4 5 6 7 8 9 10 11 12 13 14 c P1 P2 P3 P4 Statement A a D a E a A a D a E a A a B a A a B a C a D a C a C a A a C a A a E a C a E a E a B a E a h D B h E h Rule instantiation Conjunctive simplification Conjunctive simplification Disjunctive addition Definition of modus ponens Assume Conjunctive addition Definition of modus tollens Closing cond world w out contra Dilemma Disjunctive addition generalization w D J w M w x D M x N x J x K x y D N y L y z D J z K z L z M z q D J q 2 Lines Used P2 1 1 2 4 P1 5 7 2 8 9 P3 7 10 6 3 11 12 13 Answer Line Statement 1 N a L a 2 J a K a L a M a 3 J a 4 M a 5 N a J a K a 6 N a J a 7 N a 8 L a 9 K a 10 J a K a 11 J a K a 12 L a M a 13 L a 14 L a L a 15 J a 16 q D J q Rule instantiation instantiation Assume modus ponens modus ponens Conjunctive simplification Modus tollens double neg Disjunctive syllogism Conjunctive simplification Disjunctive addition double neg DeMorgan s law Disjunctive syllogism Conjunctive simplification Conjunctive addition CCW w contra generalization Lines Used P3 P4 P1 3 P2 4 5 6 3 1 7 5 9 10 2 11 12 8 13 3 14 15 Another way Line 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Statement M a N a J a K a M a N a J a K a M a J a M a J a N a J a K a N a J a K a J a K a J a K a J a K a L a M a L a M a L a N a L a N a J a N a J a K a J a J a q D J q Rule instantiation Definition of Assume modus tollens CCW w out contra Assume Conjunctive simp Conjunctive simp Disjunctive addition DeMorgan s law instantiation Disjunctive syllogism Conjunctive simp instantiation Disjunctive syllogism Modus ponens CCW w out contra Dilemma generalization Lines P2 1 P1 3 3 4 6 6 8 9 P4 10 11 12 P3 13 14 15 7 6 16 2 5 17 18 2 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 be true a All shortshops can steal bases Some …
View Full Document
Unlocking...