1. Bureaucratic part
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.
- 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.
- (x∧y)∨(¬x∧¬y).
- x⇒y⇒z.
- (x∧y)⇒z.
- ¬(¬x∨¬y∧¬z).
- (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 ∈.
- x is the largest element of S.
- S does not have a largest element.
- Every element of S is equal to x+x, for some x∈ℕ.
- Every element of S is the sum of two elements of S.
- 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.