CMSC 250 (0201 & 0202) Homework 4 Fall 2005

Due Wed Sept 28 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. Determine the validity of the following arguments. If the argument is invalid, present a Euler diagram that clearly shows the argument to be invalid. If the argument is valid, (you can't have an Euler diagram that shows it is invalid) but state that you believe the argument to be valid.

   1. All of your children must go to school.

      This child goes to school.

      Therefore, this is one of your children.

      
      Invalid

   2. Some frogs have four legs.

      All things with four legs cute and cuddly.

      Therefore, some frogs are cute and cuddly.

      
      Valid
      

   3. No chess players are football fans.

      No chess players like computers.

      Some football fans do not like computers.

      
      Invalid

   4. No clarinet players play the tuba.

      All tuba players are fun to be around.

      No clarinet players are fun to be around.

      
      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.

   1. P1	$\forall x\in D, S(x)\rightarrow R(x)$.
      P2	$\exists y\in D, S(y)\vee T(y)$.
      P3	$\forall z\in D, \sim T(z)\vee R(z)$.
      P4	$\forall u\in D, J(u)\rightarrow c$
      	Therefore $\exists w\in D, \sim (J(w) \vee \sim R(w))$

      Number	Statement	Reason	Line Used
      1	$S(a) \vee T(a)$	$\exists$ inst.	P2
      2	$J(a) \rightarrow c$	$\forall$ inst.	P4
      3	$\sim J(a)$	Law of Contra.	2
      4	$\hspace{0.6in}\vert \sim R(a)$	Assume
      5	$\hspace{0.6in}\vert \sim T(a) \vee R(a)$	$\forall$ inst.	P3
      6	$\hspace{0.6in}\vert \sim T(a)$	Disj. Syll.	4, 5
      7	$\hspace{0.6in}\vert S(a)$	Disj, Syll.	6, 1
      8	$\hspace{0.6in}\vert R(a)$	$\forall$ M.P.	P1, 7
      9	$\hspace{0.6in}\vert R(a) \wedge \sim R(a)$	Conj. Add.	4, 8
      10	$R(a)$	Closing conditional world	4-9
      11	$\sim J(a) \wedge R(a)$	Conj. Add.	10
      12	$\sim \sim ( \sim J(a) \wedge R(a))$	D.N.	11
      13	$\sim (\sim \sim J(a) \vee \sim R(a))$	D.M.	12
      14	$\sim (J(a) \vee \sim R(a))$	D.N.	13

   2. P1	$\forall x\in D, \sim J(x)\rightarrow K(x))$
      P2	$\forall z\in D, (Q(z)\wedge J(z))\vee L(z)$
      P3	$\forall x\in D, L(x)\rightarrow \sim K(x)$
      	Therefore $\forall y\in D, J(y)\vee (L(y)\wedge P(y))$

      Number	Statement	Reason	Line Used
      1	$(Q(a) \wedge J(a) \vee L(a)$, a is arbitrary in D	$\forall$ inst.	P2
      2	$\hspace{0.6in}\vert \sim J(a)$	Assume
      3	$\hspace{0.6in}\vert K(a)$	$\forall$ M.P.	P1, 2
      4	$\hspace{0.6in}\vert \sim \sim K(a)$	D.N.	3
      5	$\hspace{0.6in}\vert \sim L(a)$	$\forall$ M.T.	P3, 4
      6	$\hspace{0.6in}\vert \sim Q(a) \vee \sim J(a)$	Disj. Add.	2
      7	$\hspace{0.6in}\vert \sim (Q(a) \wedge J(a))$	D.M.	6
      8	$\hspace{0.6in}\vert (Q(a) \wedge J(a)) \vee L(a)$	$\forall$ inst.	P2
      9	$\hspace{0.6in}\vert L(a)$	Disj. Sylll	7, 8
      10	$\hspace{0.6in}\vert L(a) \wedge \sim L(a)$	Conj. Add.	5, 9
      11	$J(a)$	Colsing Conditional world	2-10
      12	$J(a) \vee (L(a) \wedge P(a))$	Disj. Add.	11
      13	$\forall y in D, J(a) \wedge (L(y) \wedge P(y))$	$\forall$ Gen.	12

   3. P1	$\forall w\in D, \sim (R(w)\wedge U(w))$
      P2	$\forall w\in D, R(w)\vee (Q(w)\wedge S(w))$
      P3	$\exists x\in D, U(x)$
      	Therefore $\exists x \in D, Q(x)$

      Number	Statement	Reason	Line Used
      1	$U(a)$	$\exists$ inst.	P3
      2	$\sim (R(a) \wedge U(a))$	$\forall$ inst.	P1
      3	$\sim R(a) \wedge \sim U(a)$	D.M.	2
      4	$\sim R(a)$	Disj. Syll.	3, 1
      5	$R(a) \vee (Q(a) \wedge S(a))$	$\forall$ inst.	P2
      6	$Q(a) \wedge S(a)$	Disj. Syll.	4, 5
      7	$Q(a)$	Conj. Simp.	6
      8	$\exists x \in D, Q(a)$	$\exists$ Gen.	7

   4. P1	$\forall y\in D, M(y)\vee L(y)$
      P2	$\forall z\in D, L(z)\rightarrow \sim J(z)$
      P3	$\forall y\in D, H(y)\rightarrow J(y)$
      P4	$\exists x\in D, N(x)\wedge H(x)$
      	Therefore $\exists w\in D, P(w)\rightarrow M(w)$

      Number	Statement	Reason	Line Used
      1	$N(a) \wedge H(a)$	$\exists$ inst.	P4
      2	$H(a)$	Conj. Simp.	1
      3	$J(a)$	M.P.	2, P3
      4	$\sim \sim J(a)$	D.N.	3
      5	$\sim L(a)$	M.T.	4, P2
      6	$M(a)$	Disj. Syll.	5, P1
      7	$\sim P(a) \vee M(a)$	Disj. Add.	6
      8	$P(a) \rightarrow M(a)$	Def. Impl.	7
      9	$\exists w \in D, P(w) \rightarrow M(w)$	$\exists$ Gen.	8

   5. P1	$\forall w\in D, R(w)\rightarrow K(w)$
      P2	$\forall z\in D, \sim T(z)\rightarrow \sim K(z)$
      P3	$\forall y\in D, R(y)\wedge U(y)$
      P4	$\forall y\in D, T(y)\leftrightarrow S(y)$
      	Therefore $\forall z\in D, \sim (\sim S(z)\vee \sim U(z))$

      Number	Statement	Reason	Line Used
      1	$R(a) \wedge U(a)$	$\forall$ inst.	P3
      2	$R(a)$	Conj. Simp.	1
      3	$K(a)$	M.P.	2, P1
      4	$\sim \sim K(a)$	D.N.	3
      5	$\sim \sim T(a)$	M.T	4
      6	$T(a)$	D.N.	5, P2
      7	$T(a) \leftrightarrow S(a)$	$\forall$ inst.	P4
      8	$(T(a) \rightarrow S(a)) \wedge (S(a) \rightarrow T(a))$	Def. BiCond.	7
      9	$T(a) \rightarrow S(a)$	Conj. Simp.	8
      10	$S(a)$	M.P.	9, 6
      11	$U(a)$	Conj. Simp.	1
      12	$S(a) \wedge U(a)$	Conj. Add.	11, 10
      13	$\sim \sim (S(a) \wedge U(a))$	D.N.	12
      14	$\sim (\sim S(a) \vee \sim U(a))$	D.M.	13
      15	$\forall z \in D, \sim (\sim S(z) \vee \sim U(z))$	$\forall$ Gen.	14

3. Translate each of the following into formal language using only the domains and predicates given.
   1. An orchestra can have more than one conductor. ( $R = \{$all orchestras$\}$, $C = \{$all conductors$\}$, $H(a, b) =$ orchestra $a$ has conductor $b$.) Answer: $\exists x \in R, \exists a, b \in C, H(x, a) \wedge H(x, b) \wedge (a \neq b)$
   2. Each composite has at least three different numbers that divide it. ( $N = \{$all numbers$\}$, $C = \{$all composites$\}$, $D(x, y) =$ number $x$ divides composite $y$.) Answer: $\forall x \in C, \exists a, b, c \in N, D(a, x) \wedge D(b, x) \wedge D(c, x) \wedge (a \neq b) \wedge (b \neq c) \wedge (c \neq a)$
   3. At least two guest speakers will be invited to give talks in the conference. ( $G = \{$all guest speakers$\}$, $I(x) =$ guest speaker $x$ will be invited to give talks in the conference).) Answer: $\exists a, b \in G, I(a) \wedge I(b) \wedge (a \neq b)$
   4. All orchestras need at least one conductor. ( $R = \{$all orchestras$\}$, $C = \{$all conductors$\}$, $H(a, b) =$ orchestra $a$ has conductor $b$.) Answer: $\forall x \in R, \exists a \in C, H(x, a)$

Web Accessibility