Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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.

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

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

1. p ⇒ ¬r ⇒ ¬q ≡ ¬p ∨ (r ∨ ¬q) ≡ ¬p ∨ ¬q ∨ r.
2. p ⇒ q ⇒ r ≡ ¬p ∨ (¬q ∨ r) ≡ ¬p ∨ ¬q ∨ r.
3. p ⇒ ¬(q ⇒ r) ≡ ¬p ∨ ¬(¬q ∨ r) ≡ ¬p ∨ (¬¬q ∧ ¬r) ≡ ¬p ∨ (q ∧ ¬r).
4. (p ∧ q) ⇒ r ≡ ¬(p ∧ q) ∨ r ≡ ¬p ∨ ¬q ∨ r.
5. (p ⇒ q) ⇒ r ≡ ¬(¬p ∨ q) ∨ r ≡ (¬¬p ∧ ¬q) ∨ r ≡ (p ∧ ¬q) ∨ r.
6. (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.

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

1. ∀y∃x y=x+1. True: Given y, let x = y-1, then y = (y-1)+1 = x+1.
2. ∀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.

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

4. ∃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².

5. ∃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.
6. ∃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.)

7. ∃x∀y y²≠x. True: Let x = -1.
8. ∀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.

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

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?

### 2.3.1. Solution

1. 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.
2. 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.
3. 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.)
1. Ulterior motive: The information in your email will be used to create an account for you in Grade-o-Matic. (1)

2014-06-17 11:57