/Solutions

1. Bureaucratic part

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. Anything else you'd like to say.

2. Technical part

2.1. 1. Conjunctive normal form

A Boolean formula is in conjunctive normal form (CNF) if it consists of an AND of a bunch of ORs of variables and their negations. For example, (x∨y)∧(¬x∨¬y) is a CNF formula for x XOR y. Transform each of the formulas below into CNF using De Morgan's laws, the expansion x⇒y ≡ ¬x∨y, the distributive law, and removing double negations, contradictions, and tautologies as needed. Show the intermediate steps.

1. (x∧y)∨(¬x∧¬y).
2. x⇒y⇒z.
3. (x∧y)⇒z.
4. ¬(¬x∨¬y∧¬z).
5. (x∨y)⇒(y∨z).

Clarification added 2010-09-19: Since people keep asking, a single clause (e.g. x∨y∨¬z) is in CNF form. So is x∧y.

2.2. 2. Predicate logic

Let S be a subset of the natural numbers ℕ. Translate each of the following statements into predicate logic. (You may find it helpful to use the shorthand notation ∀x∈S P ≡ ∀x (x∈S ⇒ P) and ∃x∈S P ≡ ∃x (x∈S ∧ P).)

After translating each statement into predicate logic, give an example of a nonempty set S (and element x, in the first case) for which the statement is true. Clarification added 2010-09-14: You may use the usual symbols of predicate logic plus ≤, +, and ∈.

1. x is the largest element of S.
2. S does not have a largest element.
3. Every element of S is equal to x+x, for some x∈ℕ.
4. Every element of S is the sum of two elements of S.
5. Every sum of two elements of S is also an element of S.

2.3. 3. A set problem

Prove or disprove: if A⊆C and B⊆D, then A∩B⊆C∩D.