A discrepancy in the total number of conjunctive normal forms and the number of distinct boolean functions.

135 Views Asked by At

Consider a set of truth literals $C$.

The set $\{\text T, \text F\}^{\mathcal{P}(C)}$ is the set of all boolean functions over all subsets of $C$. This comes from the notation $\mathcal{Y}^\mathcal{X}$ which is the set of all functions $f : \mathcal{X} \to \mathcal{Y}$.

The set of all conjugations will be a subset of $\{\text T, \text F\}^{\mathcal{P}(C)}$ which I'd like to call $\mathcal{H}_C$.

$$ \mathcal{H}_C = \left\{\ \bigwedge_c^X c \ \middle| \ X \in \mathcal{P}(C) \ \right\} $$

I still can't see a simpler notation to describe the set. This still feels somewhat burdensome, but it's all I've got for now.

Some things to note about $\mathcal{H}_C$ if we allow $C$ to contain all of its complimentary elements.

$$ \mathcal{L}_C = \left\{\ \bigvee_c^X c \ \middle| \ X \in \mathcal{P}(C) \ \right\} $$

$$ \mathcal{L}_{\mathcal{H}_C} \equiv \mathcal{H}_{\mathcal{L}_C} $$

Any boolean function over $C$ will have at least one corresponding element in each of those two sets and there are no boolean functions over $C$ that are unrepresented by either of them. This follows from the fact that every boolean function has a conjunctive normal form and a disjunctive normal form. The set of all disjunctive normal forms is $\mathcal{L}_{\mathcal{H}_C}$ and the set of all conjunctive normal forms is $\mathcal{H}_{\mathcal{L}_C}$.


Now the fruit of the question:

For any set of literals $C$, $\mathcal{H}_{\mathcal{L}_C} \subseteq \{\text T, \text F\}^{\mathcal{P}(C)}$.

$$ \left|\mathcal{H}_C\right| = \left|\mathcal{L}_C\right| = \sqrt{3}^{|C|} \\ \left|\mathcal{H}_{\mathcal{L}_C}\right| = \left|\mathcal{L}_{\mathcal{H}_C}\right| = \sqrt{3^{\sqrt{3}^{|C|}}} \\ \left|\{\text T, \text F\}^{\mathcal{P}(C)}\right| = \sqrt{2^{\sqrt{2}^{|C|}}} $$

Any conjunction can be described as a tuple of states for every non-complementary literal. Each literal can be either absent, present, or its complement can be present. Half of the literals are compliments of other literals, so they're excluded. Therefore, there are $3^{\frac{|C|}{2}}$ conjugations. The same applies to disjunctions. Combining this logic, we have a total number of conjunctive normal forms over $C$. The same applies for disjunctive normal forms.

You can easily see that the number of distinct functions is smaller than the number of conjunctive normal forms. However, shouldn't there be an equal number of distinct functions as there are normal forms? I've read before that every distinct function has exactly one conjunctive normal form. Is this wrong or am I wrong in something I've presented above?

As seen on Wikipedia right now

Any particular Boolean function can be represented by one and only one full disjunctive normal form...

Above, I showed that the number of disjunctive normal forms and the number of conjunctive normal forms are the same, so either set can be used for this argument.

Edit: The total number of boolean functions was accounting for literals and their complements both being independent variables. This is not the case so the number was rooted. The question still stands: Why are there are more forms than functions?