This assignment is due Friday, September 19th, 2008, at 5:00pm. For due dates of future assignments, see CS202/Assignments.

/Solutions

1. Bureaucratic part

This part you will not be graded on, but you should do it anyway.

Send me email. My address is <aspnes@cs.yale.edu>. In your message, include:

1. Your name.
2. Your status: whether you are an undergraduate, grad student, auditor, etc.

3. Whether you have ever taken a class that used Grade-o-Matic before.¹

4. Anything else you'd like to say.

2. Technical part

This part you will be graded on.

2.1. Logical equivalences

Which of the following propositions are logically equivalent?

1. p ⇒ ¬r ⇒ ¬q
2. p ⇒ q ⇒ r
3. p ⇒ ¬(q ⇒ r)
4. (p ∧ q) ⇒ r
5. (p ⇒ q) ⇒ r
6. (p ∨ q) ⇒ r

2.2. An attempt at realism

Suppose that our universe is the real numbers. Which of the following statements are true? Justify your answers.

1. ∀y∃x y=x+1.

2. ∀y∃x y²>x.

3. ∀y∃x y²<x.

4. ∃y∀x y²<x.

5. ∃x∀y y=x+1.

6. ∃x∀y y²>x.

7. ∃x∀y y²≠x.
8. ∀x∃y y²≠x.

2.3. A modeling problem

Consider the following axioms on a unary predicate B and a binary predicate S.

1. ∃x B(x).
2. ∀x∃!y S(x,y).
3. ∀x∀y S(x,y) ⇒ B(x) ⇒ ¬B(y).

Answer each of these questions, justifying your answer in each case:

1. Is there a model of these axioms with exactly one element?
2. Is there a model of these axioms with exactly two elements?
3. Is there a model of these axioms with exactly three elements?