CMSC 250 Fall 2004 -- Homework 4 Answer

Due Wed., Sept. 29 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. Complete the following proofs using the method described in class (line numbers, rules, etc).

   1. P1	$\exists w \in D \ Q(w) \to P(w)$
      P2	$\forall x \in D \ Q(x) \vee R(x)$
      P3	$\forall y \in D \ R(y) \to P(y)$
      $\therefore$	$\exists z \in D \ P(z)$

      
      Answer:

      Line	Statement	Rule	Lines Used
      1	$\vert \forall z \in D \ \sim P(z)$	Assume	--
      2	$\vert \ Q(a) \to P(a)$	$\exists$ instantiation	P1
      3	$\vert \sim P(a)$	$\forall$ instantiation	1
      4	$\vert \sim Q(a)$	Modus Tollens	2,3
      5	$\vert Q(a) \vee R(a)$	$\forall$ instantiation	P2
      6	$\vert R(a)$	Disjunctive Syllogism	4,5
      7	$\vert P(a)$	$\forall$ Modus Ponens	P3,6
      8	$\vert P(a) \wedge \sim P(a)$	Conjunctive Addition	3,7
      9	$\sim ( \forall z \in D \ \sim P(z))$	CCW w/contradiction	1-8
      10	$\exists z \in D \ P(z)$	Negation of Quantifiers	9

      OR

      Line	Statement	Rule	Lines Used
      1	$Q(a) \to P(a)$	$\exists$ inst	P1
      2	$Q(a) \vee R(a)$	$\forall$ inst	P2
      3	$R(a) \to P(a)$	$\forall$ inst	P3
      4	$P(a)$	Dilema	1,2,3
      5	$\exists x \in D, P(x)$	$\exists$ generalization	5

   2. P1	$\forall w \in D \ \sim R(w) \wedge Q(w)$
      P2	$\forall x \in D \ Q(x) \to ( \sim P(x) \vee \sim S(x) )$
      P3	$\forall y \in D \ (T(y) \to R(y) ) \to P(y)$
      $\therefore$	$\forall z \in D \ S(z) \to T(z)$

      
      Answer:

      Line	Statement	Rule	Lines Used
      1	$\sim R(a) \wedge Q(a)$	$\forall$ instantiation	P1
      2	$Q(a)$	Conjunctive Simplification	1
      3	$\sim R(a)$	Conjunctive Simplification	1
      4	$\sim P(a) \vee \sim S(a)$	$\forall$ Modus Ponens	P2,2
      5	$\vert S(a)$	Assume	--
      6	$\vert \sim P(a)$	DN and Disjunctive Syllogism	4,5
      7	$\vert\sim (T(a) \to R(a) )$	$\forall$ Modus Tollens	P3,6
      8	$\vert\sim (\sim T(a) \vee R(a) )$	Def of Implication	7
      9	$\vert T(a) \wedge \sim R(a)$	DeMorgan's and DN	8
      10	$\vert T(a)$	Conjunctive Simplification	9
      11	$S(a) \to T(a)$	CCW w/o contradiction	5-10
      12	$\forall z \in D \ S(z) \to T(z)$	$\forall$ generalization	11

2. Let the predicate $P(i, j)$ mean ``Person $i$ speaks language $j$,'' let $M = \{$all people$\}$, and $L = \{$all languages$\}$. For each of the following statements, write the meaning of the statement in English, write the negation of the statement formally using symbols, and then write the meaning of the negation in English.

   Note: Do not negate a logic statement just by putting a $\sim$ symbol in front; the $\sim$ may only appear immediately in front of the predicate. The same thing applies for your English sentences - you may not simply put ``it is not the case'' or something similar in front of the sentence.

   1. $\forall i \in M \ \exists j \in L \ P(i, j)$
      Answer:
      • Every person speaks at least one language.
      • $\exists i \in M \ \forall j \in L \ \sim P(i, j)$
      • There is a person who speaks no languages.
   2. $\exists i \in M \ \forall j \in L \ P(i, j)$
      Answer:
      • There is a person who speaks all languages.
      • $\forall i \in M \ \exists j \in L \ \sim P(i, j)$
      • Every person has at least one language that he doesn't speak.
   3. $\forall j \in L \ \exists i \in M \ P(i, j)$
      Answer:
      • Every language is spoken by at least one person.
      • $\exists j \in L \ \forall i \in M \ \sim P(i, j)$
      • There is a language that isn't spoken by any person.
   4. $\exists j \in L \ \forall i \in M \ P(i, j)$
      Answer:
      • There is a language that is spoken by all people.
      • $\forall j \in L \ \exists i \in M \ \sim P(i, j)$
      • Every language has at least one person who doesn't speak it.
   5. $\forall i \in M \ \forall j \in L \ P(i, j)$
      Answer:
      • All people speak all languages.
      • $\exists i \in M \ \exists j \in L \ \sim P(i, j)$
      • There is a person who does not speak some language.
   6. $\exists i \in M \ \exists j \in L \ P(i, j)$
      Answer:
      • There is a person somewhere who speaks some language.
      • $\forall i \in M \ \forall j \in L \ \sim P(i, j)$
      • No people speak any languages.
3. For each of the following, decide if the argument is valid or invalid. If it is invalid, draw an Euler diagram to verify this fact. If it is valid, draw an Euler diagram that shows the premises and conclusion all to be true.
   1. Some TA's are smart.
      Some TA's are helpful to students.
      Therefore, some TA's are smart and helpful to students.
      Answer: Invalid argument.
      
   2. All pigs are fat.
      Some pigs like sleeping a lot.
      Therefore, some fat creatures like sleeping a lot.
      Answer: Valid argument.
      

4. Explain (in an English sentence or two) whether the following argument is valid or not. Do not use an Euler diagram.

   	$\exists q \in D \ M(q) \to N(q)$
   	$\exists q \in D \ \sim N(q)$
   $\therefore$	$\exists q \in D \ \sim M(q)$

   
   Answer: The argument is invalid because when the $q$'s are instantiated, they do not necessarily refer to the same member of $D$. Therefore, modus tollens cannot be applied here.

5. Translate each of the following into formal language using the sets and predicates given.
   1. All orchestras have exactly one conductor. ( $R = \{$all orchestras$\}$, $C = \{$all conductors$\}$, $H(a, b) =$ orchestra $a$ has conductor $b$.)
      Answer: $\forall r \in R \ [ \exists x \in C \ H(r,x) \wedge \forall y \in C \ H(r,y) \to (x=y) ]$
   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 c \in C \ \exists x,y,z \in N \ D(x,c)\wedge D(y,c)\wedge D(z,c)\wedge (x\neq y)\wedge (y\neq z) \wedge (x \neq z)$
   3. At most 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: $\forall x,y,z \in G \ I(x)\wedge I(y) \wedge I(z) \to (x=y)\vee (x=z)\vee (y=z)$

Web Accessibility