CMSC 250 Fall 2004 -- Homework 4

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)$

   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)$

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)$
   2. $\exists i \in M \ \forall j \in L \ P(i, j)$
   3. $\forall j \in L \ \exists i \in M \ P(i, j)$
   4. $\exists j \in L \ \forall i \in M \ P(i, j)$
   5. $\forall i \in M \ \forall j \in L \ P(i, j)$
   6. $\exists i \in M \ \exists j \in L \ P(i, j)$
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.
   2. All pigs are fat.
      Some pigs like sleeping a lot.
      Therefore, some fat creatures like sleeping a lot.

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)$

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$.)
   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$.)
   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).)

Web Accessibility