Discrete Structures

# HW #4 — §1.4: Nested Quantifiers

 Last Update: 24 September 2010 Note: or material is highlighted

Each HW problem's solution should consist of:

All solutions must be handwritten.

 PUT YOUR NAME, DATE, RECITATION SECTION & "HW #4" AT TOP RIGHT OF EACH PAGE; STAPLE MULTIPLE PAGES

1. (3 points each; total = 21 points)

p. 59: 10 a–b, d, f–i

• This problem asks you to translate 7 English sentences into the language of FOL
(using one, 2-place predicate).

2. (3 points each; total = 12 points)

p. 59: 12 a, d, f–g

• This problem asks you to translate 4 English sentences into the language of FOL
(using one, 1-place predicate and one, 2-place predicate).

3. (3 points each; total = 15 points)

p. 61: 28 a–e

• This problem gives you 5 FOL propositions whose domain is R (the set of all real numbers),
and asks you to determine their truth values.

• If a universally quantified proposition is false,
give a counterexample!

• You may have to do a bit of elementary algebra;
if you need algebra hints, send me email.

• It may help if you translate the FOL into English.

• You will get partial credit only if you show all your work.
(And by now you should know what "only if" means :-)

4. (3 points each; total = 12 points)

p. 61: 32 a–d

• This problem gives you 4 FOL propositions,
and asks you to compute their negations in such a way that all negation signs appear only in front of predicates.

Here's an example: As you learned in lecture and read about in the text,

¬∀xP(x) ≡ ∃x[¬P(x)]

So, the negation of ∀xP(x) can be written in either of those two ways.
But only the one on the right-hand side of the logical-equivalence sign has its negation sign in front of the predicate.

• Hint for part (c): Do you remember what the negation of a biconditional is?

Total points = 60

A       57-60
A-      54-56
B+      51-53
B       47-50
B-      44-46
C+      41-43
C       34-40
C-      27-33
D+      21-26
D       11-20
F        0-10

 DUE: AT THE BEGINNING OF LECTURE, FRI., OCT. 1