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

# 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:

- Your name.
- Your status: whether you are an undergraduate, grad student, auditor, etc.
Whether you have ever taken a class that used Grade-o-Matic before.

^{1}- 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?

- p ⇒ ¬r ⇒ ¬q
- p ⇒ q ⇒ r
- p ⇒ ¬(q ⇒ r)
- (p ∧ q) ⇒ r
- (p ⇒ q) ⇒ r
- (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.

- ∀y∃x y=x+1.
∀y∃x y²>x.

∀y∃x y²<x.

∃y∀x y²<x.

- ∃x∀y y=x+1.
∃x∀y y²>x.

- ∃x∀y y²≠x.
- ∀x∃y y²≠x.

## 2.3. A modeling problem

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

- ∃x B(x).
- ∀x∃!y S(x,y).
- ∀x∀y S(x,y) ⇒ B(x) ⇒ ¬B(y).

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

- Is there a model of these axioms with exactly one element?
- Is there a model of these axioms with exactly two elements?
- Is there a model of these axioms with exactly three elements?

Ulterior motive: The information in your email will be used to create an account for you in Grade-o-Matic. (1)