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:

- 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

## 2.1. A surprising equivalence

- 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.
- With the same interpretation of P, Q, and R, translate the expression (P ⇒ R) ∨ (Q ⇒ R) back into English.
- Show that the two expressions in the previous parts are logically equivalent.

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

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

## 2.3. The likable logicians theorem

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

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

## 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)).

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