CMSC 250 Homework 2 ANSWERS Spring 2006

Due Wed Feb 8 at the beginning of your discussion section.

1. Give the negations of the following statements using DeMorgan's Law.
   1. Either cats or dogs are allowed here.

   2. Either poodles or dobermans don't make good pets.

   3. Fish or birds are not allowed, or dogs are allowed.

2. For each of the following statements, state ``inverse,'' ``converse,'' ``contrapositive,'' or ``none.'' I may have changed verb tenses to make so that the statements sound right, but tell if the form matches.
   1. Converse.
   2. Inverse.
   3. Inverse.
   4. None.
   5. Converse.
   6. Contrapositive.
   7. None.

3. Write the complete truth table for each of the following:

   1. $p$	$q$	$r$	$p \rightarrow q$	$\sim r$	$\sim r \vee p$	$(p \rightarrow q) \rightarrow (\sim r \vee p)$
      1	1	1	1	0	1	1
      1	1	0	1	1	1	1
      1	0	1	0	0	1	1
      1	0	0	0	1	1	1
      0	1	1	1	0	0	0
      0	1	0	1	1	1	1
      0	0	1	1	0	0	0
      0	0	0	1	1	1	1

   2. $a$	$b$	$a \wedge b$	$a \vee b$	$(a \wedge b) \leftrightarrow (a \vee b)$
      1	1	1	1	1
      1	0	0	1	0
      0	1	0	1	0
      0	0	0	0	1

4. For each of the following state the one single rule from Theorem 1.1.1 (page 14) or Table 1.3.1 (Page 40) that could be used to go directly from the statement(s) to the conclusion, or ``none'' if there is no one single rule. (note: the answer if ``none'' even if a series of rules can be applied)
   1. None.
   2. None.
   3. Modus Ponens.
   4. None.
   5. Modus Tollens.
   6. Disjunctive Syllogism.
   7. None.
   8. None.

5. Use a truth table to determine if the following argument is valid or not. State whether or not it is valid, and give your reasons why it is valid or not.

   $p$	$q$	$r$	$p\vee q$	$\sim r$	$\sim r \rightarrow q$	$\sim p$	$\sim p\rightarrow\sim r$	$p$
   1	1	1	1	0	1	0	1	1
   1	1	0	1	1	1	0	1	1
   1	0	1	1	0	1	0	1	1
   1	0	0	1	1	0	0	1	1
   0	1	1	1	0	1	1	0	0
   0	1	0	1	1	1	1	1	0
   0	0	1	0	0	1	1	0	0
   0	0	0	0	1	0	1	1	0

   NOT VALID. All three premises are true in rows 1, 2, 3 and 6, but the conclusion is not true in row 6.

6. Use the rules of inference you were given to prove the following:

   1. P1	$p \vee ((\sim q) \wedge r)$
      P2	$\sim (p \wedge s)$
      P3	$s$
      S1	$\sim p \vee \sim s$	DeMorgan's laws	P2
      S2	$\sim (\sim s)$	Double negative	P3
      S3	$\sim p$	Disjunctive Syllogism	S1 and S2
      S4	$\sim q \wedge r$	Disjunctive Syllogism	S3 and P1
      S5	$r \wedge \sim q$	Commutative law	S4
      S6	$\sim (r \rightarrow q)$	Definition of Implication	S5

   2. P1	$p\vee q$
      P2	$\sim p \vee r$
      P3	$\sim r \vee s$
      S1	$q \vee p$	Commutative law	P1
      S2	$\sim q \rightarrow p$	Def. of Implication and D.Neg.	S1
      S3	$p \rightarrow r$	Definition of Implication	P2
      S4	$r \rightarrow s$	Definition of Implication	P3
      S5	$p \rightarrow s$	Hypothetical Syllogysim	S3 and S4
      S6	$\sim q \rightarrow s$	Hypothetical Syllogysim	S2 and S5
      S7	$q \vee s$	Def. of Implication and D.Neg.	S6

   3. P1	$p \rightarrow r$
      P2	$q \rightarrow s$
      P3	$x \wedge y$
      S1	$\vert$Assume $p \wedge q$	Conditional World
      S2	$\vert p$	Conjunctive Simplification	S1
      S3	$\vert r$	Modus Ponens	P1 and S2
      S4	$\vert q$	Conjunctive Simplification	S1
      S5	$\vert s$	Modus Ponens	P2 and S4
      S6	$\vert r \wedge s$	Conjunctive Addition	S3 and S5
      S7	$(p \wedge q) \rightarrow (r \wedge s)$	Closing C.W. without contradiction	S1 - S6
      S8	$x$	Conjunctive Simplification	P3
      S9	$x \vee m$	Disjunctive Addition	S8
      S10	$((p\wedge q) \rightarrow (r \wedge s)) \wedge (x \vee m)$	Conjunctive Addition	S7 and S9

Web Accessibility