CMSC 250 Homework 4 ANSWERS Spring 2006

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

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.

   

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)$
      S1	$A(a) \rightarrow B(a)$	Universal Instantiation	P1
      		a is arbitrary in D
      S2	$B(a) \rightarrow M(a)$	Universal Instantiation	P2
      S3	$A(a) \rightarrow M(a)$	Hypothetical Syllogism	S1 and S2
      S4	$\sim A(a) \vee M(a)$	Definition of Implication	S3
      S5	$\forall z \in D, \sim A(z) \vee M(z)$	Universal Generalization	S4

   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)$
      S1	$(A(a) \wedge B(a)) \vee N(a)$	Existential Instantiation	P2
      S2	$\sim N(a) \wedge Y(a)$	Universal Instantiation	P3
      S3	$\sim N(a)$	Conjunctive Simplification	S2
      S4	$A(a) \wedge B(a)$	Disjunctive Syllogism	S3 and S1
      S5	$A(a)$	Conjunctive Simplification	S4
      S6	$B(a)$	Conjunctive Simplification	S4
      S7	$M(a)$	Universal Modus Ponens	S6 and P1
      S8	$A(a) \wedge M(a)$	Conjuctive Addition	S5 and P7
      S9	$\exists x \in D, A(x) \wedge M(x)$	Existential Generalization	S8

   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)$
      S1	$N(a)$	Universal Instantiation	P3
      S2	$\sim \sim N(a)$	Double Negative	S1
      S3	$\sim A(a)$	Disjunctive Syllogism	S2 and P2
      S4	$\exists x \in D, \sim A(x)$	Existential Generalization	S3

   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)$
      S1	$A(a) \wedge \sim B(a)$	Existential Instantiation	P2
      S2	$A(a)$	Conjunctive Simplification	S1
      S3	$\sim B(a)$	Conjunctive Simplification	S1
      S4	$B(a) \vee M(a)$	Universal Modus Ponens	S2 and P1
      S5	$M(a)$	Disjunctive Syllogism	S3 and S4
      S6	$\exists z \in D, M(z)$	Existential Generalization	S5

   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)$
      S1	$A(a) \wedge B(a)$	Existential Instantiation	P1
      S2	$A(a)$	Conjuctive Simplification	S1
      S3	$B(a)$	Conjuctive Simplification	S1
      S4	$M(a)$	Universal Modus Ponens	S2 and P2
      S5	$N(a)$	Universal Modus Ponens	S3 and P3
      S6	$M(a) \wedge N(a)$	Conjuctive Addition	S4 and S5
      S7	$\exists x \in D, M(x) \wedge N(x)$	Existential Generalization	S6

Web Accessibility