CMSC 250 (0201 & 0202) Homework 2 Fall 2005

Solutions

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. Give the negations of the following statements using DeMorgan's Law.
   1. Fords and Chevys are good cars. Either Fords are not good cars OR Chevys are not good cars.
   2. Either Sue won't go to the wedding or Fred will. Sue will go to the wedding AND Fred won't go to the wedding.
   3. Neither the Sun nor the Moon are heavenly bodies. Either the Sun is a heavenly body OR the Moon is a heavenly body.
2. For each of the following statements, give its inverse, converse and contrapositive.
   1. If it rains in Spain, then it is May. Inverse: If it doesn't rain in Spain, then it is not May Converse: If it is May, then it rains in Spain Contrapositive: If it isn't May, then it doesn't rain in Spain.
   2. Good times will follow if you go to a party. Inverse: If you do not go to a party, then good times will not follow. Converse: If good times followed, then you went to a party. Contrapositive: If good times do not follow, then you didn't go to a party.
   3. If trees are blooming, then it's spring. Inverse: If trees are not blooming, then it isn't spring. Converse: If it's spring, then trees are blooming. Contrapositive: If it isn't spring, then trees are not blooming.
   4. You will pass only if you work hard. Inverse: You will not pass only if you do not work hard. Converse: If you passed, then you worked hard. Contrapositive: If you did not pass, then you did not work hard.
3. Write the complete truth table for each of the following:
   1. $(p\rightarrow q)\vee (\sim r \wedge p)$.

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

   2. $a\leftrightarrow (b\wedge \sim c)$

      $a$	$b$	$c$	$\sim c$	$b \wedge \sim c$	$a\leftrightarrow (b\wedge \sim c)$
      1	1	1	0	0	0
      1	1	0	1	1	1
      1	0	1	0	0	0
      1	0	0	1	0	0
      0	1	1	0	0	1
      0	1	0	1	1	0
      0	0	1	0	0	1
      0	0	0	1	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 39) that could be used to go directly from the statement(s) to the conclusion, or ``none'' if there is no such rule.
   1. statement: $(p\rightarrow q) \wedge p$
      conclusion: $q$. None.
   2. statements: $p \rightarrow q$
      $p$
      conclusion $q$. Modus ponens.
   3. statements: $a\rightarrow b$
      $\sim a\rightarrow c$
      conclusion: $b\vee c$ None. item statements: $a\rightarrow b$
      $a\vee c$
      conclusion: $c\rightarrow b$ 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.

   P1	$p\vee q$
   P2	$r\rightarrow q$
   P3	$\sim p\rightarrow\sim r$
   Therefore	$\sim p$

   			Premise	Premise			Premise	Conclusion
   $p$	$q$	$r$	$p\vee q$	$r\rightarrow q$	$\sim p$	$\sim r$	$\sim p\rightarrow\sim r$	$\sim p$
   1	1	1	1	1	0	0	1	0	$\leftarrow$ Critical
   1	1	0	1	1	0	1	1	0	$\leftarrow$ Critical
   1	0	1	1	0	0	0	1	0
   1	0	0	1	1	0	1	1	0	$\leftarrow$ Critical
   0	1	1	1	1	1	0	0	1
   0	1	0	1	1	1	1	1	1	$\leftarrow$ Critical
   0	0	1	0	0	1	0	0	1
   0	0	0	0	1	1	1	1	1

   Since the premises are all true in the first row and the conclusion is false in the first row, the argument is invalid.
6. Use the rules of inference you were given to prove the following:

   1. P1	$r\vee s$
      P2	$y\rightarrow \sim s$
      P3	$\sim (y\wedge w)$
      P4	$\sim p\rightarrow\sim r$
      P5	$w\rightarrow \sim s$
      P6	$y\vee w$
      Therefore	$p\vee x$

      Number	Statement	Reason	Lines Used
      (1)	$\sim s$	``Dilemma: proof by division into cases''	P2, P5, and P6
      (2)	$r$	Disjunctive syllogism	P1 and (1)
      (3)	$\sim \sim r$	Double negation law	(2)
      (4)	$\sim \sim p$	Modus tollens	P4 and (3)
      (5)	$p$	Double negation law	(4)
      (6)	$p\vee x$	Disjunctive addition	(5)

   2. P1	$a\vee (b\wedge m)$
      P2	$(a\vee b\vee g)\rightarrow d$
      P3	$(a\vee m)\rightarrow (\sim e\rightarrow f)$
      P4	$\sim f$
      Therefore	$(d\vee h)\wedge (e\vee h)$

      Number	Statement	Reason	Lines Used
      (1)	$(a \vee b) \wedge (a \vee m)$	Distributive law	P1
      (2)	$a \vee m$	Conjunctive Simplification	(1)
      (3)	$\sim e \rightarrow f$	Modus ponens	P3 and (2)
      (4)	$\sim \sim e$	Modus Tolens	P4 and (3)
      (5)	$e$	Double negative law	(4)
      (6)	$e \vee h$	Disjunctive addition	(5)
      (7)	$a \vee b$	Conjunctive Simplification	(1)
      (8)	$a \vee b \vee g$	Disjunctive addition	(7)
      (9)	$d$	Modus ponens	P2 and (8)
      (10)	$d \vee h$	Disjunctive addition	(9)
      (11)	$(d\vee h)\wedge (e\vee h)$	Conjunctive addition	(6) and (10)

      P1	$x\rightarrow y$
      P2	$\sim y\vee q$
      P3	$(r\wedge \sim q)\vee g$
      Therefore	$\sim g\rightarrow \sim (x\vee \sim r)$

   3. Number	Statement	Reason	Lines Used
      (1)	$\vert \sim g$	Assume
      (2)	$\vert (r\wedge \sim q)$	Disj. Syll.	P3 and (1)
      (3)	$\vert r$	Conj. Simp.	(2)
      (4)	$\vert \sim q$	Conj. Simp.	(2)
      (5)	$\vert \sim y$	Disj. Syll.	P2 and (4)
      (6)	$\vert \sim x$	Modus Tollens	P1 and (5)
      (7)	$\vert \sim x\wedge r$	Conj. Addition	(3) and (6)
      (8)	$\vert \sim (x\vee \sim r)$	De Morgan's Law	(7)
      (9)	$\sim g\rightarrow \sim (x\vee \sim r)$	Close Condit Wld.	(1)-(8)

Web Accessibility