[Model] MinimumDisjunctiveNormalForm #936
Description
Motivation
MINIMUM DISJUNCTIVE NORMAL FORM (LO9) from Garey & Johnson, A9 p.261. Given a Boolean function f specified by its truth table, find a DNF formula with the minimum number of terms (disjuncts) equivalent to f. This is the classic two-level logic minimization problem addressed by the Quine-McCluskey algorithm. NP-hard (Masek 1979, via reduction from Minimum Cover). Polynomially equivalent to two-level AND-OR circuit minimization (Gimpel 1967). Applications in digital circuit design, compiler optimization, and machine learning (DNF learning).
The problem reduces naturally to Set Covering: enumerate prime implicants, then find minimum cover of minterms. MinimumSetCovering already exists in the codebase.
Definition
Name: MinimumDisjunctiveNormalForm
Reference: Garey & Johnson, Computers and Intractability, A9 LO9; Masek 1979
Mathematical definition:
INSTANCE: Set U of n boolean variables, Boolean function f: {0,1}^n → {0,1} specified by its truth table.
OBJECTIVE: Find a DNF formula with the minimum number of terms (disjuncts) that is equivalent to f. Each term is a conjunction of literals (variables or their negations).
Equivalently: find the minimum number of prime implicants of f whose union covers all minterms (truth table rows where f = 1).
Variables
- Count: |P| (one binary decision variable per prime implicant of f)
- Per-variable domain: {0, 1}
- Meaning: Whether each prime implicant is selected. The constraint is that every minterm must be covered by at least one selected prime implicant. The objective minimizes the number of selected prime implicants.
Schema (data type)
Type name: MinimumDisjunctiveNormalForm
Variants: none
| Field | Type | Description |
|---|---|---|
num_variables |
usize |
Number of boolean variables n |
truth_table |
Vec<bool> |
Truth table of f, length 2^n (indexed by binary assignment) |
Complexity
- NP-hardness: NP-hard (Masek 1979, transformation from MINIMUM COVER). The decision version is Σ₂ᴾ-complete when the function is given as a formula rather than a truth table (Umans 2001).
- Best known exact algorithm: Quine-McCluskey Phase 1 generates all prime implicants (O*(3^n/√n) worst case), then Phase 2 solves the NP-hard covering problem. The brute-force complexity is O*(2^|P|) where |P| is the number of prime implicants.
- Complexity string:
"2^(3^num_variables)"
Extra Remark
Full book text:
INSTANCE: Set U of variables, Boolean function f specified by its truth table over U, positive integer K.
QUESTION: Can f be expressed as a disjunctive normal form formula having K or fewer disjuncts (terms)?
Reference: [Masek, 1979]. Transformation from MINIMUM COVER.
Comment: Polynomially equivalent to "two-level AND-OR circuit minimization" [Gimpel, 1967].
Note: The original G&J formulation is a decision problem with threshold K. We use the equivalent optimization formulation: minimize the number of DNF terms.
How to solve
- It can be solved by (existing) bruteforce. (Enumerate all prime implicants via Quine-McCluskey Phase 1; enumerate subsets to find minimum cover.)
- It can be solved by reducing to integer programming.
- Other:
Reduction Rule Crossref
(Planned: MinimumCover → MinimumDisjunctiveNormalForm, R205 per G&J)
(Planned: MinimumDisjunctiveNormalForm → MinimumSetCovering, natural direction — the covering step is literally a Set Cover instance)
Example Instance
Input:
Boolean function on n = 3 variables (x₁, x₂, x₃):
| x₁ | x₂ | x₃ | f |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Minterms (6): {001, 010, 011, 100, 101, 110}. The function is 1 when exactly 1 or 2 variables are true.
Prime implicants (6):
| Prime | Expression | Covers |
|---|---|---|
| p₁ | ¬x₁ ∧ x₂ | {010, 011} |
| p₂ | ¬x₁ ∧ x₃ | {001, 011} |
| p₃ | x₁ ∧ ¬x₂ | {100, 101} |
| p₄ | x₁ ∧ ¬x₃ | {100, 110} |
| p₅ | ¬x₂ ∧ x₃ | {001, 101} |
| p₆ | x₂ ∧ ¬x₃ | {010, 110} |
Each prime implicant covers exactly 2 of the 6 minterms. No prime implicant is essential (no minterm is covered by only one prime).
Optimal solution (3 terms): Select {p₁, p₄, p₅} = {¬x₁∧x₂, x₁∧¬x₃, ¬x₂∧x₃}:
- p₁ covers {010, 011}
- p₄ covers {100, 110}
- p₅ covers {001, 101}
- Union = {001, 010, 011, 100, 101, 110} = all 6 minterms ✓
Minimum DNF: f = (¬x₁ ∧ x₂) ∨ (x₁ ∧ ¬x₃) ∨ (¬x₂ ∧ x₃)
Alternative optimal (also 3 terms): {p₂, p₃, p₆} = (¬x₁ ∧ x₃) ∨ (x₁ ∧ ¬x₂) ∨ (x₂ ∧ ¬x₃).
Why 2 terms is impossible: Each prime covers exactly 2 minterms. Two primes cover at most 4 minterms, but we need to cover 6. So at least 3 primes are needed.
Expected Outcome
Optimal value: Min(3) — the minimum number of DNF terms is 3. There are 2 optimal covers of size 3, plus 9 covers of size 4, 6 of size 5, and 1 of size 6, giving 18 total feasible covers across 4 distinct sizes.
References
- [Masek, 1979]: W. Masek. "Some NP-complete set covering problems." Unpublished manuscript, MIT.
- [Quine, 1952]: W. V. Quine. "The problem of simplifying truth functions." American Mathematical Monthly 59, pp. 521–531.
- [McCluskey, 1956]: E. J. McCluskey. "Minimization of Boolean functions." Bell System Technical Journal 35, pp. 1417–1444.
- [Umans, 2001]: C. Umans. "The minimum equivalent DNF problem and shortest implicants." J. Computer and System Sciences 63, pp. 597–611.
- [Gimpel, 1967]: J. F. Gimpel. "A reduction technique for prime implicant tables." IEEE Trans. Electronic Computers 14, pp. 535–541.