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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: