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.1.1. Solution

There are basically two ways to do this: with truth tables, or by applying logical equivalences to bring each expression into some standard form (e.g. CNF).

Let's try the second approach first:

- p ⇒ ¬r ⇒ ¬q ≡ ¬p ∨ (r ∨ ¬q) ≡ ¬p ∨ ¬q ∨ r.
- p ⇒ q ⇒ r ≡ ¬p ∨ (¬q ∨ r) ≡ ¬p ∨ ¬q ∨ r.
- p ⇒ ¬(q ⇒ r) ≡ ¬p ∨ ¬(¬q ∨ r) ≡ ¬p ∨ (¬¬q ∧ ¬r) ≡ ¬p ∨ (q ∧ ¬r).
- (p ∧ q) ⇒ r ≡ ¬(p ∧ q) ∨ r ≡ ¬p ∨ ¬q ∨ r.
- (p ⇒ q) ⇒ r ≡ ¬(¬p ∨ q) ∨ r ≡ (¬¬p ∧ ¬q) ∨ r ≡ (p ∧ ¬q) ∨ r.
- (p ∨ q) ⇒ r ≡ ¬(p ∨ q) ∨ r ≡ (¬p ∧ ¬q) ∨ r.

Now we scan down the right-hand side and see that (1), (2), and (4) are all equivalent to ¬p ∨ ¬q ∨ r, which means they are are equivalent to each other. The rest aren't equivalent to any of the others.

Here is the same thing using a giant truth table:

p |
q |
r |
1 |
2 |
3 |
4 |
5 |
6 |

0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |

0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |

0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |

0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |

1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |

1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |

1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |

1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |

And here again we can read off that (1), (2), and (4) are equivalent but the others aren't.

(Note: I was too lazy to compute the truth table by hand, so I used this program).

## 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.2.1. Solution

- ∀y∃x y=x+1. True: Given y, let x = y-1, then y = (y-1)+1 = x+1.
∀y∃x y²>x. True: Given y, observe that y²≥0. So let x = -1 (for example), and we have y²≥0>x ⇒ y²>x.

∀y∃x y²<x. True: Given y, let x = y²+1. Then y²<y²+1=x.

∃y∀x y²<x. False: To show this, we prove the negation ¬∃y∀x y²<x ≡ ∀y∃x ¬(y²<x) ≡ ∀y∃x y²≥x. This holds because we can set x = -1 < 0 ≤ y².

- ∃x∀y y=x+1. False: Again consider the negation ¬∃x∀y y=x+1 ≡ ∀x∃y y≠x+1. Given y, let x = y, then y≠x+1=y+1.
∃x∀y y²>x. True: Let x = -1. (Note that in this case the order of the quantifiers didn't matter very much. This doesn't always happen; we got lucky.)

- ∃x∀y y²≠x. True: Let x = -1.
- ∀x∃y y²≠x. True: Given x, if x = 0, let y = 1. Then y²=1≠x. If x≠0, let y=0. Then y²=0≠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?

### 2.3.1. Solution

- No. Suppose such a model exists. Call the unique element 0. From the first axiom we have B(0). Specializing the second axiom to 0 gives ∃!y S(0,y). Stripping off the uniqueness part gives ∃y S(0,y). Since we only have 0, y must equal 0, giving S(0,0). Specializing the third axiom to x = 0 and y = 0 gives S(0,0) ⇒ B(0) ⇒ ¬B(0), from which we get B(0) ⇒ ¬B(0), and thus ¬B(0). But now we have B(0) ∧ ¬B(0), a contradiction.
- Yes. Call the elements 0 and 1, and let ¬S(0,0), S(0,1), S(1,0), ¬S(1, 0), B(0), and ¬B(1) all hold. Axiom (1) holds because B(0) implies ∃x B(x). Axiom (2) holds because for x = 0, y = 1 gives S(x,y) and for any z with S(0,z) we have z = y = 1. Axiom (3) holds because the only assignment of x and y with S(x,y) and B(x) is x = 0, y = 1, in which case ¬B(y) holds.
- Yes. Start with the elements 0 and 1 above, and add a new element q such that S(q,1) holds, but ¬S(q,0), ¬S(q,q), ¬S(0, q) and ¬S(1,q). Choose B(q) or ¬B(q) arbitrarily (it doesn't matter). Now q has a unique successor 1 (so axiom 2 holds for q), and the successor has ¬B(1), making axiom (3) hold. (In fact, we can tack on as many extra elements as we like as long as we all point them at 1.)

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