## Access structures and CNF versus DNF

Suppose there are $n$ people, numbered from $1$ up to $n$. Some subsets of these people are authorized to launch a nuclear strike. We suppose that the access structure is monotone: that is, if $Y$ is an authorized set and $Z$ contains $Y$, then $Z$ is also authorized. Thus the set $\Gamma$ of authorized sets is determined by its subset $\Delta$ of minimal elements. For example, if $n=4$ and any set of at least three people is authorized, then $\Delta = \big\{ \{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\} \bigr\}$ and $\Gamma = \Delta \cup \big\{ \{1,2,3,4\} \bigr\}$. If in addition, $\{1,2\}$ is an authorized set then $\Delta = \big\{ \{1,2\}, \{1,3,4\}, \{2,3,4\} \bigr\}$.

Let $x_i$ be true if Person $i$ is present and false otherwise. Let $S$ be the proposition ‘a nuclear strike can be launched’. Considering each minimal authorized set in turn, and assuming that any person present is happy to play their role in an epoch-defining nuclear strike, we see that

$\displaystyle S \longleftrightarrow \bigvee_{X \in \Delta} \bigl( \bigwedge_{i \in X} x_i \bigr).$

This expresses $S$ in disjunctive normal form: a disjunction in which each term is a conjunction in the variables $x_i$ and $\neg x_i$. In this example, corresponding to the monotonicity of the access structure, negated variables never appear.

It is an interesting, and maybe not completely obvious fact, that any proposition is logically equivalent to one in disjunctive normal form. Roughly, one proof goes as follows: consider all true/false assignments to the variables $x_1, \ldots, x_n$ that make a given proposition $P$ true. Then $P$ is logically equivalent to ‘at least one of these assignments holds’, which is easily written in DNF.

For instance, in the first example above, the assignments that make $S$ true are $TTTT, FTTT, TFTT, TTFT, TTTF$, and $S$ is logically equivalent to

$S' = Q \vee P_1 \vee P_2 \vee P_3 \vee P_4$

where $Q$ is $x_1 \wedge x_2 \wedge x_3 \wedge x_4$, $P_1$ is $\neg x_1 \wedge x_2 \wedge x_3 \wedge x_4$, $P_2$ is $x_1 \wedge \neg x_2 \wedge x_3 \wedge x_4$, and so on. A disjunction, like $S'$ above, in which every clause is of the form $y_1 \wedge y_2 \wedge \cdots \wedge y_n$, where each $y_i$ is either $x_i$ or $\neg x_i$, is said to be in full disjunctive normal form. Since there are $2^n$ such clauses, and taking the disjunction over different subsets of them gives logically inequivalent propositions, there are exactly $2^{2^n}$ propositional formulae in the variables $x_i$, up to logical equivalence. (The empty disjunction is false by convention.)

The Dedekind number $D_n$ is the number of such formulae not involving any $\neg x_i$. Thus $D_n$ is the number of monotone boolean functions in $n$ variables, or the number of monotone access structures with $n$ people, or (by the minimal authorized subsets interpretation), the number of antichains in the poset of subsets of $\{1,2,\ldots, n\}$, ordered by inclusion. The OEIS link gives several further combinatorial interpretations. The sequence of Dedekind numbers, for $n \in \mathbb{N}$, begins 2, 3, 6, 20, 168, 7581, 7828354. No exact formula is known (or likely ever to be known), but the antichain interpretation makes it plausible that

$\log_2 \displaystyle D_n \sim \binom{n}{n/2} \sim \sqrt{\frac{2}{\pi}} \frac{2^{n}}{\sqrt{n}},$

and this was first proved by Kleitman.

Negating formulae in DNF, it follows from de Morgan’s laws that any proposition is equivalent to a conjunction of clauses, each of the form $y_1 \vee y_2 \vee \cdots \vee y_n$, where each $y_i$ is either $x_i$ or $\neg x_i$. (The empty conjunction is true by convention.) The access structure interpretation makes an alternative conjunctive form apparent: for every transversal of the authorized sets, we require at least one member is present. (Clearly this condition holds if everyone from a particular authorized set is present, and if Person $P_X$ is missing from authorized set $X$ then this is detected by the clause $\vee_X P_X$ in the conjunction.) Thus if the authorized sets are $X_1, \ldots, X_m$ then

$\displaystyle S \longleftrightarrow \bigwedge_{i_1 \in X_1, \ldots, i_m \in X_m} \bigvee_{j=1}^m x_{i_j}$.

A related identity is

$\displaystyle \bigvee_{X \subseteq \{1,\ldots, n\} \atop |X| = r} \bigl( \bigwedge_{i \in X} x_i \bigr) \longleftrightarrow \bigwedge_{Y \subseteq \{1,\ldots, n\} \atop |Y| = n-r+1} \bigl( \bigvee_{j \in Y} x_j \bigr).$

For a direct proof, just note that at least $r$ people are present if and only if at most $n-r$ people are absent, so if and only if at least one person from every subset of size $n-r+1$ is present.