CMSC 250 Homework 4 Spring 2006

Due Wed Feb 22 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. For each of the following, either draw an Euler diagram to demonstrate that the argument is invalid OR state that you believe the argument to be valid because you can't draw an Euler diagram that convinces you that it is invalid.

   1. No cats like to play fetch.

      This animal does not like to play fetch.

      Therefore, This animal is a cat.

   2. All cats sleep all day.

      No dogs are cats.

      Therefore, no dogs sleep all day.

   3. All cats like to purr.

      Freddie likes to purr.

      Therefore, Freddie is a cat.

   4. All cats drink milk.

      Some things that drink milk make good pets.

      Therefore, cats make good pets.

2. Prove the following using the rules on the sheet you were given. Assume in all cases that D is nonempty and give justification for each step. Assume that $t$ represents a tautology and $c$ represents a contradiction unless otherwise stated. Also assume a and b are members of the set D.

   1. P1	$\forall x \in D, A(x) \rightarrow B(x)$.
      P2	$\forall y \in D, B(y) \rightarrow M(y)$.
      	Therefore $\forall z \in D, \sim A(z) \vee M(z)$

   2. P1	$\forall x \in D, B(x) \rightarrow M(x)$
      P2	$\exists x \in D, (A(x) \wedge B(x)) \vee N(x)$
      P3	$\forall x \in D, \sim N(x) \wedge Y(x)$
      	Therefore $\exists x \in D, A(x) \wedge M(x)$

   3. P1	$\forall x \in D, A(x) \rightarrow B(x)$
      P2	$\sim A(a) \vee \sim N(a)$
      P3	$\forall x \in D, N(x)$
      	Therefore $\exists x \in D, \sim A(x)$

      $\downarrow$ Turn Over $\downarrow$

   4. P1	$\forall x \in D, A(x) \rightarrow (B(x) \vee M(x))$
      P2	$\exists y \in D, A(y) \wedge \sim B(y)$
      	Therefore $\exists z \in D, M(z)$

   5. P1	$\exists x \in D, A(x) \wedge B(x)$
      P2	$\forall x \in D, A(x) \rightarrow M(x)$
      P3	$\forall x \in D, B(x) \rightarrow N(x)$
      P4	$\exists x \in D, \sim M(x) \wedge \sim N(x)$
      	Therefore $\exists x \in D, M(x) \wedge N(x)$

Web Accessibility