Name (PRINTED):
Student ID #:
Section # (or TA's:
name and time)

CMSC 250	Quiz #4 ANSWERS	Wed., Sept. 21, 2005
(0201&0202)

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.

1. [8 pnts.] Draw the simplest diagram (fewest number of gates) which will represent the expression given by the following truth table.
   Write the Simplest (fewest operators) Logic Expression corresponding to this truth table:

   p	q	r	Output
   1	1	1	0
   1	1	0	1
   1	0	1	1
   1	0	0	1
   0	1	1	0
   0	1	0	0
   0	0	1	0
   0	0	0	0

   
   
   
   
   
   
   
   
   
   
   
   
   
   
2. [6 pnts.] Give an example of a predicate P(x,y) where
   it is true that
   
   $$\exists x \in {\bf Z} \forall y \in {\bf Z}\,\,\,\,\,\, P(x,y)$$
   
   
   but false that
   
   $$\forall y \in {\bf Z} \exists x \in {\bf Z} \,\,\,\,\,\, P(y,x)$$
   
   
   
   
   
   
   
   
   
   
   $\downarrow$ TURN OVER $\downarrow$
3. [16 pnts.] For each of the following English Sentences, translate the meaning into formal notation using the symbols ($\exists$, $\forall$, $\wedge$, $\vee$, $\sim$, and $\rightarrow$). You may also use algebraic symbols as needed. On the next line write the negation of the original statement using formal notation. NOTE: Any $\sim$ symbol in any statement can only be immediately before the predicate - thre can not be any negated quantity or negated quantifier.

   There is a tallest building.

   Domain(s): B = {All buildings}

   Predicate: T(x,y) = building x is taller than building y

   statement:

   negation:

   There is no prime integer which is greater than a million.

   Domain(s): Z = {all integers}

   Predicates: P(x) = integer x is prime, G(x) = integer x is greater than one million

   statement:

   negation:

   There a store where nobody shops.

   Domain(s): P={All people}, S={all stores}

   Predicate: B(x,y) = person x shops at store y

   statement:

   negation:

   There will be at most one person in this class who fails this quiz.

   Domain: P={all people}

   Predicate: F(x) = x fails this quiz, C(x) = x is in this class.

   statement:

   negation:

Web Accessibility