Minimum Disjunctive Normal Form

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 u1 through un 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 (u1 ∧ u2 ∧ ~u3) ∨ (u1 ∧~u2 ∧ ~u3) 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 u1 ∨ u2 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 (aij = 1 means that variable i is in set j)

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

pi = u1 ∧ u2 ∧ … ∧ ~ui ∧ … ∧ um+n

(All of the positive variables and-ed together, except the negation of ui)

f1 = p1 ∨ p1 ∨ … pn

Fi = {j | aij = 0}  (The set of all variables not in set i)

Pi = un+i ∧ uj (the conjunct of all uj where j ∈ Fi)

f2 = P1 ∨ … Pn

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 aij = 1 if and only if pj ∈ Pi.

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 f1 and f2 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?

Leave a Reply

Your email address will not be published. Required fields are marked *