LO7 is Satisfiability of Boolean Expressions, which is what we now call Cook’s Theorem. It’s related to the “regular” (clause-based) Satisfiability we’ve done all along because it’s possible to turn any Boolean expression into CNF form.

LO8 is DNF Non-Tautology.

The next problem’s paper was written in 1965, so before NP-Completeness was a concept. As a result, the paper doesn’t line up exactly with what we want to do, and I think I’m misunderstanding something.

**The problem: **Minimum Disjunctive Normal Form. This is problem LO7 in the appendix.)

**The description: **Given a set u_{1} through u_{n} of variables, a set A of n-tuples containing T or F symbols (possible truth assignments of the variables), and an integer K, can we create a DNF form expression E that is true for the variable set *exactly* for the truth assignments in A (everything in A and nothing more) using K clauses or less?

**Example: **Suppose we had 3 variables, and A was {(T,T,F), (T,F,F)}.

Then the DNF expression (u_{1} ∧ u_{2} ∧ ~u_{3}) ∨ (u_{1} ∧~u_{2 }∧ ~u_{3}) will be true only on the truth assignments listed in A.

We can get away with less than “one clause for each element of A” though. For example, if A = {(T,T,T), (T,T,F), (T,F,T), (F,T,T), (T,F,F), (F,T,F)} then we can just use u_{1} ∨ u_{2} to cover exactly those truth assignments.

**Reduction: **The paper by Gimpel was written in 1965 (before Cook’s 1971 paper), so wasn’t conceived of as an NP-Completeness reduction. But it does show how to translate from Set Covering.

The basic idea is that we will represent a covering instance as a 0/1 table A. We start with an m by n table, with variables representing the rows and sets representing the columns (a_{ij} = 1 means that variable i is in set j)

We’re now going to build some boolean expressions over m+n variables:

p_{i} = u_{1} ∧ u_{2} ∧ … ∧ ~u_{i} ∧ … ∧ u_{m+n}

(All of the positive variables and-ed together, except the negation of u_{i})

f_{1} = p_{1} ∨ p_{1} ∨ … p_{n}

F_{i }= {j | a_{ij} = 0} (The set of all variables not in set i)

P_{i} = u_{n+i} ∧ u_{j} (the conjunct of all u_{j} where j ∈ F_{i})

f_{2} = P_{1} ∨ … P_{n}

Then he proves that f1 and f2 form a pair of functions for which A is the prime implicant table of those functions. By which he means that a_{ij} = 1 if and only if p_{j} ∈ P_{i}.

Then we build a table B that represents the prime implicant table of a related function. If we remove the last r rows and 2r columns from B (I think this is related to K somehow), we get a table that is equivalent to our A.

**Difficulty: **9. I’m pretty sure I’m missing something here. I don’t see how these tables relate. I don’t see how you can take f_{1} and f_{2} and make a single DNF formula out of them. I don’t see where K shows up- I guess it’s a limit on n? But how does it relate to the covering matrix?