This assignment is due Thursday, September 20th, 2007 at 11: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:

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

2.1. A surprising equivalence

1. Let P be the proposition "you study for the final exam", Q be the proposition "you take the final exam," and R the proposition "you will pass the final exam." Translate the statement "If you study for the final exam and you take the final exam, then you will pass the final exam" into an expression in terms of P, Q, R, and logical connectives.
2. With the same interpretation of P, Q, and R, translate the expression (P ⇒ R) ∨ (Q ⇒ R) back into English.
3. Show that the two expressions in the previous parts are logically equivalent.

2.1.1. Solution

1. (P ∧ Q) ⇒ R.
2. This one doesn't have a particular clean version in English, but a word-for-word translation might be "If you study for the final exam, then you will pass the final exam; or if you take the final exam, then you will pass the final exam."
3. Here's the truth table:

   • P	Q	R	P∧Q	(P∧Q)⇒R	P⇒R	Q⇒R	(P⇒R)∨(Q⇒R)
     0	0	0	0	1	1	1	1
     0	0	1	0	1	1	1	1
     0	1	0	0	1	1	0	1
     0	1	1	0	1	1	1	1
     1	0	0	0	1	0	1	1
     1	0	1	0	1	1	1	1
     1	1	0	1	0	0	0	0
     1	1	1	1	1	1	1	1

2.2. Resolution and CNF

Recall that a compound proposition is in conjunctive normal form (CNF) if it is written as an AND of ORs, e.g. (P∨Q)∧(P∨R)∧(¬P∨Q∨R)∨P. The resolution rule, which says that (P∨Q)∧(¬P∨R) ⊢ (Q∨R), can be applied to CNF propositions to prove simpler propositions.

1. Prove that the resolution rule actually works, by demonstration that (P∨Q)∧(¬P∨R) ⇒ (Q∨R) is a tautology.
2. Convert the proposition ((¬P∨¬Q)⇒(R∧S))∧(R⇒S)∧¬S into conjunctive normal form.
3. Use resolution to prove that the proposition you just converted implies P (you may need to use simplification at the end).

2.2.1. Solution

1. Here is a truth table:

   • P	Q	R	P∨Q	¬P∨R	(P∨Q)∧(¬P∨R)	(Q∨R)	(P∨Q)∧(¬P∨R) ⇒ (Q∨R)
     0	0	0	0	1	0	0	1
     0	0	1	0	1	0	1	1
     0	1	0	1	1	1	1	1
     0	1	1	1	1	1	1	1
     1	0	0	1	0	0	0	1
     1	0	1	1	1	1	1	1
     1	1	0	1	0	0	1	1
     1	1	1	1	1	1	1	1

2. Expand:

   • ((¬P∨¬Q)⇒(R∧S))∧(R⇒S)∧¬S
     ≡ (¬(¬P∨¬Q)∨(R∧S))∧(¬R∨S)∧(¬S)	(expand ⇒)
     ≡ ((P∧Q)∨(R∧S))∧(¬R∨S)∧(¬S)	De Morgan's law
     ≡ (P∨R)∧(P∨S)∧(Q∨R)∧(Q∨S)∧(¬R∨S)∧(¬S)	distributive law

3. Resolve:

   • (P∨R)∧(P∨S)∧(Q∨R)∧(Q∨S)∧(¬R∨S)∧(¬S)

     ⊢ (P∨R)∧(P∨S)∧(Q∨R)∧(Q∨S)∧(¬R)

     ⊢ (P)∧(P∨S)∧(Q∨R)∧(Q∨S)

     ⊢ P

2.3. The likable logicians theorem

Given two logicians x and y, Let P(x,y) represent the predicate "x likes y."

1. Use P to translate the statement "For every logician x, there is a logician y who likes x" into predicate logic.
2. Translate "There is a logician x who likes every logician y" into predicate logic.
3. Use the inference rules for predicate logic to show that one of the above statements implies the other.

2.3.1. Solution

1. ∀x∃y P(y,x).
2. ∃x∀y P(x,y).
3. We'll show ∃x∀y P(x,y) ⇒ ∀x∃y P(y,x). Assume ∃x∀y P(x,y). Let c be such that ∀y P(c,y) [existential specialization]. Let z be an arbitrary logician; then P(c,z) holds [universal specialization]. But then ∃y P(y,z) holds [existential generalization], and since z was arbitrary we have ∀z∃y P(y,z) ≡ ∀x∃y P(y,x). (In the other direction, ∀x∃y P(y,x). Let z be an arbitrary logician, then we have ∃y P(y,z). Call the winning y c, giving P(c,z). We'd like to apply universal generalization to get to ∀z P(c,z), but we can't: c was not arbitrary but depended on z.)

2.4. Recursion and induction

Let S be the successor function from the PeanoAxioms. Define the function P(x,y) by the axioms

• P(x,0) = x
• P(x,y) = P(y,x)
• P(x,Sy) = S(P(x,y))

Suppose the predicate Q(x) satisfies the axioms

• Q(0)
• ¬Q(S0)
• Q(SSx) ⇔ Q(x).

Prove from these axioms and the PeanoAxioms that ∀x Q(P(x,x)).

2.4.1. Solution

Apply the induction schema to Q(P(x,x)) to get

• Q(P(0,0)) ∧ (∀x (Q(P(x,x)) ⇒ Q(P(Sx,Sx)))) ⇒ ∀x Q(P(x,x)).

We want to show that the left-hand side holds. Observe that P(0,0) = 0 by definition, so Q(P(0,0)) ⇔ Q(0) which is given. Now suppose Q(P(x,x)) holds. Then P(Sx,Sx) = S(P(Sx,x)) = S(P(x,Sx)) = S(S(P(x,x))). But from Q(P(x,x)) we have Q(SSP(x,x)) ⇒ Q(P(Sx,Sx)). So we are done.