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).
2.1.1. Solution
- (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).
- x⇒y⇒z ≡ ¬x∨(y⇒z) [expand ⇒] ≡ ¬x∨(¬y∨z) [expand ⇒] ≡ ¬x∨¬y∨z. [remove unnecessary parentheses]
- (x∧y)⇒z ≡ ¬(x∧y)∨z [expand ⇒] ≡ (¬x∨¬y)∨z [De Morgan's law] ≡ ¬x∨¬y∨z. [remove unnecessary parentheses]
- ¬(¬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]
- (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.
- 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.2.1. Solution
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}.
¬∃x∈S ∀y∈S ¬(y > x) (equivalently, ∀x∈S ∃y y > x). Example: S = ℕ; any infinite subset of ℕ works too.
- ∀x∈S ∃y∈ℕ x = y + y. Examples: S = {2,4,8}, S = { x+x | x∈ℕ }. Here we just need a set of even numbers.
- ∀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).
∀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.
- Assume the premise: A⊆C and B⊆D.
- Expand the definition in the conclusion: A∩B⊆C∩D is equivalent to ∀x x∈(A∩B) ⇒ x∈(C∩D).
- 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).
- We now have a new thing to prove: start by assuming the premise x∈(A∩B).
- Expand the definition of A∩B: x∈(A∩B) ⇔ (x∈A ∧ x∈B).
- Expand the definition of A⊆C: x∈A ⇒ x∈C.
- Use the previous two steps to conclude x∈C.
- Do the same with B⊆D to conclude x∈D.
- Combine the last two steps to get x∈C∧x∈D.
- 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.