[Math] Is the minimal conjunctive normal form for positive formula unique? If so, how do you calculate it

Question

I am considering positive Boolean formulas (no negations). Take for example $A$. Here are two of its positive conjunctive normal forms.

$$A$$
$$A \land (A \lor B)$$

The minimal example is $A$.

Does every positive boolean formula have a unique minimal conjunctive normal form? If so, how does one calculate it?

(I conjecture that you can do so by finding a positive conjuctive normal form, and then pruning any terms that are implied by other terms (for example, $A \lor B$ is implied by the previous term $A$, so it gives no additional information in a conjuction). I don't know how to prove that this is correct, if it is so. (It is also not very efficient.))

Answer 1

This showed up on the Wikipedia Math Help Desk, see 1. It looks like the minimal expression is unique for positive expressions.

Proof: Let S and T be two equivalent positive expressions in CNF which are both minimal. Let {S_i} be the set of clauses in S and {T_j} be the set of clauses in T. Each S_i and T_j, in turn, corresponds to a subset of a set of Boolean variables {x_k}. Since S is minimal, no S_i is contained in S_j for j≠i, and similarly for T. For each assignment a:x_k → {T, F}, define Z(a) to be the set of variables for which a is F, i.e. Z(a) is the compliment of the support of a. A clause S_i evaluates to F iff S_i⊆Z(a) and the expression S evaluates to F iff S_i⊆Z(a) for some i. A similar statements holds for T. Fix i and define the truth assignment a_i(x_k) to be T when x_k is not in S_i, in other words a_i is the truth assignment so that Z(a_i) = S_i. The clause S_i evaluates to F under this assignment, so S evaluates to F. But S and T are equivalent so T evaluates to F. Therefore T_j⊆Z(a_i)= S_i for some j. Similarly, for each j there is k so that S_k ⊆ T_j. (I think another way of saying this is that S and T are refinements of each other.) If S_i is an element of S, then there is T_j in T so that T_j ⊆ S_i, and there is an S_k so that S_k ⊆ T_j. Then S_k ⊆ S_i and so, since ''S'' is minimal, i=k. We then have S_i ⊆ T_j ⊆ S_i, S_i = T_j ∈ T. So S ⊆ T and similarly T ⊆ S, therefore S = T.

Another (probably better) approach is to characterize the clauses that appear.