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

2.1.1. Solution

1. (x∧y)∨(¬x∧¬y) ≡ (x∨¬x)∧(x∨¬y)∧(y∨¬x)∧(y∨¬y) [Distributive law] ≡ 1∧(x∨¬y)∧(y∨¬x)∧1 [tautologies] ≡ (x∨¬y)∧(¬x∨y).
2. x⇒y⇒z ≡ ¬x∨(y⇒z) [expand ⇒] ≡ ¬x∨(¬y∨z) [expand ⇒] ≡ ¬x∨¬y∨z. [remove unnecessary parentheses]
3. (x∧y)⇒z ≡ ¬(x∧y)∨z [expand ⇒] ≡ (¬x∨¬y)∨z [De Morgan's law] ≡ ¬x∨¬y∨z. [remove unnecessary parentheses]
4. ¬(¬x∨¬y∧¬z) ≡ ¬(¬x∨(¬y∧¬z)) ≡ ¬¬x∧¬(¬y∧¬¬z) [De Morgan's law] ≡ ¬¬x∧(¬¬y∨¬¬z) [De Morgan's law] ≡ x∧(y∨z). [remove double negations]
5. (x∨y)⇒(y∨z) ≡ ¬(x∨y)∨(y∨z) [expand ⇒] ≡ (¬x∧¬y)∨(y∨z) [De Morgan's law] ≡ ((¬x∨y)∧(¬y∨y))∨z [distributive law] ≡ (¬x∨y)∨z [x∧1≡x] ≡ ¬x∨y∨z. [remove unnecessary parentheses]

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.

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.2.1. Solution

1. x∈S ∧ ∀y∈S ¬(y > x) (equivalently, x∈S ∧ ¬∃y∈S y > x). Don't forget to make x be an element of S. Example: x = 3, S = {0,1,3}.

2. ¬∃x∈S ∀y∈S ¬(y > x) (equivalently, ∀x∈S ∃y y > x). Example: S = ℕ; any infinite subset of ℕ works too.

3. ∀x∈S ∃y∈ℕ x = y + y. Examples: S = {2,4,8}, S = { x+x | x∈ℕ }. Here we just need a set of even numbers.
4. ∀x∈S ∃y∈S ∃z∈S x = y + z. Examples: S = {0}, S = { 0, 3, 27 }, S = ℕ. Pretty much any set that includes 0 works here (and any set that doesn't, doesn't).

5. ∀x∈S ∀y∈S ∃z∈S z = x + y. Examples: S = {0}, S = ℕ, S = { x∈ℕ | x > 37 }.

If S were allowed to be the empty set, then S = ∅ would also work for (2)–(5).

2.3. 3. A set problem

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

2.3.1. Solution

Here is a proof showing the strategy used at each step.

1. Assume the premise: A⊆C and B⊆D.
2. Expand the definition in the conclusion: A∩B⊆C∩D is equivalent to ∀x x∈(A∩B) ⇒ x∈(C∩D).
3. Since we are trying to prove a universal statement, pick an arbitrary x, and show that the statement is true for x. In effect, this means we drop the ∀x part and just prove x∈(A∩B) ⇒ x∈(C∩D).
4. We now have a new thing to prove: start by assuming the premise x∈(A∩B).
5. Expand the definition of A∩B: x∈(A∩B) ⇔ (x∈A ∧ x∈B).
6. Expand the definition of A⊆C: x∈A ⇒ x∈C.
7. Use the previous two steps to conclude x∈C.
8. Do the same with B⊆D to conclude x∈D.
9. Combine the last two steps to get x∈C∧x∈D.
10. Use the definition of C∩D to change this to x∈(C∩D). We're done!

A more compact version of the proof might look like this:

Let x∈(A∩C). Then x∈A and A⊆C implies x∈C. Similarly x∈B and B⊆D implies x∈D. It follows that x∈(C∩D). Since x was arbitrary, we have ∀x x∈(A∩C) ⇒ x∈(C∩D), or A∩B⊆C∩D.