Suppose there are people, numbered from up to . Some subsets of these people are authorized to launch a nuclear strike. We suppose that the access structure is monotone: that is, if is an authorized set and contains , then is also authorized. Thus the set of authorized sets is determined by its subset of minimal elements. For example, if and any set of at least three people is authorized, then and . If in addition, is an authorized set then .
Let be true if Person is present and false otherwise. Let 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
This expresses in disjunctive normal form: a disjunction in which each term is a conjunction in the variables and . 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 that make a given proposition true. Then 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 true are , and is logically equivalent to
where is , is , is , and so on. A disjunction, like above, in which every clause is of the form , where each is either or , is said to be in full disjunctive normal form. Since there are such clauses, and taking the disjunction over different subsets of them gives logically inequivalent propositions, there are exactly propositional formulae in the variables , up to logical equivalence. (The empty disjunction is false by convention.)
The Dedekind number is the number of such formulae not involving any . Thus is the number of monotone boolean functions in variables, or the number of monotone access structures with people, or (by the minimal authorized subsets interpretation), the number of antichains in the poset of subsets of , ordered by inclusion. The OEIS link gives several further combinatorial interpretations. The sequence of Dedekind numbers, for , 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
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 , where each is either or . (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 is missing from authorized set then this is detected by the clause in the conjunction.) Thus if the authorized sets are then
A related identity is
For a direct proof, just note that at least people are present if and only if at most people are absent, so if and only if at least one person from every subset of size is present.