[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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.

2014-06-17 11:57