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

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.

2014-06-17 11:57