CMSC 250

KEY Quiz #3

Monday, Sept. 24, 2001

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. [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$). On the next line write the negation of the original statement using formal notation.

   There is a tree taller than any building.

   Domains: all buildings and all trees

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

   statement: $\exists x \in trees$ $\forall y \in buildings$ $T(x,y)$

   negation: $\forall x \in trees$ $\exists y \in buildings$ $\sim T(x,y)$

   The square of any even integer is an even integer.

   Domain: all integers

   Predicates: E(x) = x is even

   statement: $\forall x \in Z$ $E(x) \rightarrow E(x^2)$

   negation: $\exists x \in Z$ $E(x) \wedge \sim E(x^2)$

   No pigs have wings.

   Domain: all pigs

   Predicate: W(x) = x has wings

   statement:$\sim$ $(\exists x \in pigs$ $W(x))$

   or $\forall x \in pigs$ $\sim W(x)$

   negation: $\exists x \in pigs$ $W(x)$

   or $\sim (\forall x \sim W(x))$

   There are at least two people here.

   Domain: all people

   Predicate: H(x) = x is here

   statement: $\exists x \in people$ $\exists y \in people$ $((x \neq y) \wedge H(x) \wedge H(y))$

   negation: $\forall x \in people$ $\forall y \in people$ $\sim ((x \neq y) \wedge H(x) \wedge H(y))$

   or $(\forall x \in people \,\, \sim H(x))$ $\vee$ $(\forall x \in people$ $\forall y \in people$ $(H(x) \wedge H(y)) \rightarrow (x = y))$

2. [7 pnts.] Express the negation of the propositon $p$: $\forall n \in N$ $\exists y \in N$ such that $y > n$ Use neither the negation symbol ($\sim$) nor the word ``not''.

   answer: $\, \exists n \in N$ $\forall y \in N$ $y \leq n$

   [7 pnts.] Give an example of a predicate P(x,y) where the (Domain of x = Domain of y = Z (integers)) so that it it true that
   

   $$\forall x \exists y \,\, P(x,y)$$

   
   

   but false that
   

   $$\exists y \forall x \,\, P(x,y)$$

   
   

   answer: $\,\, P(x,y) = \,\,\, y = x^2$

   For all integers x there is an integer which is its square.

   meaning: Every integer has another integer that is its square.

   It is not the case that (there exists an integer y such that for all integers x, y is the square of x)

   meaning: It isn't the cast that ``There is an integer so that every. integer squared is that value.''

   or: For all integers there is another integer where the square of the second is not equal to the first.

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -show_section_numbers -split 0 -no_navigation -no_footnode quiz3k

The translation was initiated by John Arras on 2001-10-10