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)