With the term 'anti-monotonic function', we designate specific boolean functions on subsets of a finite set of positive integers which we call the universe. Through the well-known bijective relationship between the set of monotonic functions and the set of anti-monotonic functions, the study of the anti-monotonic functions is equivalent to the study of monotonic functions. The true-set of an anti-monotonic function is an antichain. If the universe is denoted by N , the set of anti-monotonic functions is denoted by AM F (N ). This set can be partially ordered in a natural way. This paper studies enumeration in the resulting lattice of anti-monotonic functions. We define intervals of anti-monotonic functions according to this order and present four properties of such intervals, Finally we give a formula for the size of a general interval and a recursion formula for the n-th number of Dedekind.
c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 57{67, ISBN 978{2{7466{6566{8, Laboratory L3i, University of La Rochelle, 2013. Copying permitted only for private and academic purposes. case we will occasionally use the notation AM F (n) ≡ AM F (N ). The size of
Example 1. For N = {1, 2}, the Boolean function 2N → B, {∅ → f alse, {∅} → f alse, {1} → true, {2} → true, {1, 2} → f alse} is anti-monotonic. The antichain of true sets is given by {{1}, {2}}. This antichain will be used to denote the antimonotonic function.
For finite N , anti-monotonic functions form a finite distributive lattice with the
join, meet and partial order given by
(
(⇔ α ∨ β = β ⇔ α ∧ β = α), where for a general set S of subsets of N , max(S) is the set containing only the largest sets in S according to ⊆. A comprehensive textbook on Boolean functions is [2]. A recent study on counting non-equivalent monotone Boolean functions is found in [1]. Our antichains correspond to the notion of minimal sets playing an important role in the latter paper. A first analysis of intervals and decomposition is in [9]. We will make extensive use of the intervals in this lattice. For two antichains α, β ∈ AM F (N ), the closed interval with bounds α and β is given by
[α, β] = {χ ∈ AM F (N )|α ≤ χ ≤ β}.
empty in case α 6≤ β, in particular in case of non comparable α and β. 2
{χ ∨ χ0|χ ∈ [ρ1, ρ2], χ0 ∈ [ρ01, ρ02]} = [ρ1 ∨ ρ01, ρ2 ∨ ρ02].
[ρ1, ρ2] ∨ [ρ01, ρ02] ≡ [ρ1 ∨ ρ01, ρ2 ∨ ρ02].
cept of (dis)-connectedness. Two intervals are said to be disconnected if the decomposition in equation 6 is unique. Two intervals are connected if they are not disconnected. If two intervals are disconnected, we will call the join of these intervals direct: Definition 1. The interval [ρ1 ∨ ρ01, ρ2 ∨ ρ02] is the direct join of two intervals [ρ1, ρ2] and [ρ01, ρ02] in AM F (N ) if the intervals are disconnected. The direct join is denoted by [ρ1, ρ2] 6 [ρ01, ρ02].
Example 2. For N = {1, 2, 3}, we have [{{1}}, {{1, 3}}] ∨ [{{2}}, {{2, 3}}] = [{{1}, {2}}, {{1, 3}, {2, 3}}]. The element {{1}, {2}, {3}} = {{1}} ∨ {{2}, {3}} = {{1}, {3}}∨{{2}} shows that the two intervals on the lefthand side are connected. In the case of [{{1}, {3}}, {{1, 3}}]∨[{{2}, {3}}, {{2, 3}}] = [{{1}, {2}, {3}}, {{1, 3}, {2, 3}}], we see that the underlying intervals are disconnected and [{{1}, {2}, {3}}, {{1, 3}, {2, 3}}] = [{{1}, {3}}, {{1, 3}}] 6 [{{2}, {3}}, {{2, 3}}]. 3
Lemma 1. For two anti-monotonic functions α, β ∈ AM F (N ) we have
(
Proof. It is clear that for χα ∈ [α ∧ β, α] and χβ ∈ [α ∧ β, β], we have χα ∨ χβ ∈ [α ∧ β, α ∨ β]. Moreover, since χβ ∧ α ≤ β ∧ α, we have χα = (χα ∨ χβ) ∧ α and similarly χβ = (χα ∨ χβ) ∧ β. For χ ∈ [α ∧ β, α ∨ β] we have χ ∧ α ∈ [α ∧ β, α], χ ∧ β ∈ [α ∧ β, β] and
(χ ∧ α ∨ χ ∧ β) = χ ∧ (α ∨ β) = χ.
Theorem 1. For three anti-monotonic functions α, β, ρ ∈ AM F (N ) such that ρ ∈ [α ∧ β, α ∨ β] we have
[ρ, α ∨ β] = [ρ, α ∨ ρ] 6 [ρ, β ∨ ρ].
Proof. Note that (α ∨ρ)∧(β ∨ρ) = (α ∧β)∨ρ = ρ so that the interval [ρ, α ∨β] = [ρ, (α ∨ ρ) ∨ (β ∨ ρ)] satisfies the conditions of Lemma 1. Any χ ∈ [ρ, α ∨ β] has the unique decomposition χ = (χ ∧ (α ∨ ρ)) ∨ (χ ∧ (β ∨ ρ)).
Theorem 2. For three anti-monotonic functions α, β, ρ ∈ AM F (N ) such that ρ ∈ [α ∧ β, α ∨ β] we have
[ρ, α ∨ β] = [ρ ∧ α, α] 6 [ρ ∧ β, β].
Proof. Any χ ∈ [ρ, α∨β] satisfies χ = (χ∧α)∨(χ∧β), with χ∧α ∈ [ρ∧α, α], χ∧ β ∈ [ρ ∧ β, β]. Any χ = χα ∨ χβ with χα ∈ [ρ ∧ α, α], χβ ∈ [ρ ∧ β, β] is in [ρ, α ∨ β]. Furthermore χ∧α = (χα ∧α)∨(χβ ∧α) where χα ∧α = χα (since χα ∈ [ρ∧α, α]) and χβ ∧ α ≤ β ∧ α (since χβ ∈ [ρ ∧ β, β]) so that χβ ∧ α ≤ ρ ∧ α ≤ χα , and we conclude χα = χ ∧ α. Equivalently, we obtain χβ = χ ∧ β proving the uniqueness of decomposition. Corollary 1. For any two anti-monotonic functions α, ρ, the intervals [ρ, ρ ∨ α] and [ρ ∧ α, α] are isomorphic lattices.
Proof. Since ρ∧α ≤ ρ, we can apply Theorem 2 to find [ρ, ρ∨α] = [ρ, ρ]6[ρ∧α, α]. This implies that [ρ ∧ α, α] → [ρ, ρ ∨ α] : χ → ρ ∨ χ defines an isomorphism with inverse [ρ, ρ ∨ α] → [ρ ∧ α, α] : χ → α ∧ χ.
Corollary 2. For two anti-monotonic functions ρ1, ρ2 = ∨i∈I αi with ∀i, j ∈ I : αi ∧ αj ≤ ρ1, we have [ρ1, ρ2] = 6i∈I [ρ1, ρ1 ∨ αi]
= 6i∈I [ρ1 ∧ αi, αi].
Proof. The proof follows from a simple iteration over the indices i ∈ I, applying Theorems 1 and 2 for each component αi, i ∈ I.
functions ρ ≥ γ to denote the largest χ for which χ ∧ ρ = γ. A general partition of an interval is given by Theorem 3.
Theorem 3. For anti-monotonic functions ρ1 ≤ ρ ≤ ρ2
[ρ1, ρ2] = ∪γ∈[ρ1,ρ][γ, oρ,γ ∧ ρ2].
The intervals [γ, oρ,γ ∧ ρ2] for γ ≤ ρ are disjoint and nonempty. Proof. For each γ ∈ [ρ1, ρ] consider the set Sγ = {χ ∈ [ρ1, ρ2]|χ ∧ ρ = γ}. These sets are disjoint. Since for each χ ∈ [ρ1, ρ2], we have χ ∧ ρ ∈ [ρ1, ρ], the union of these sets is the whole interval. γ is a lower bound on Sγ . Since (χ1 ∧ ρ = γ and χ2 ∧ ρ = γ) ⇒ (χ1 ∨ χ2) ∧ ρ = γ, the set has exactly one maximal element. We denote this element in the case of ρ2 = {N } by oρ,γ . Since, in addition, χ1 ∧ ρ = γ, χ2 ∧ ρ = γ ⇒ (χ1 ∧ χ2) ∧ ρ = γ, the set of all solutions to the equation in the lattice is closed under ∧ and ∨ and hence equals the full interval [γ, oρ,γ ]. For general ρ2, Sγ is the intersection with [ρ1, ρ2] which is given by [γ, oρ,γ ∧ ρ2].
The function oρ,γ defined for any ρ ≥ γ ∈ AM F (N ) is the top of the interval [γ, oρ,γ ] = {χ|χ ∧ ρ = γ}. It is given by (13) (14) oρ,γ = γ˜g\ρ˜ where˜denotes the dual in the lattice AM F (N ).
itly to anti-monotonic functions. In fact, they only relied on the properties of the operators ∧ and ∨ and are seen to be valid in any complete distributive lattice.
Definition 2. Given two anti-monotonic functions ρ, α ∈ AM F (N ) with ρ ≤ α. Two sets A, B ∈ α are said to be connected with respect to ρ if and only if {A ∩ B} 6≤ ρ. Connectedness of such sets is denoted by Cρ(A, B). Cρ(., .) defines a graph with the sets of α as vertices. The vertices of each connected component of this graph correspond to a subset of α and thus to an anti-monotonic function. We will refer to these anti-monotonic functions as the connected components of α with respect to ρ and denote the set of such components by Cρ,α.
Corollary 3. For anti-monotonic functions ρ1, ρ2 ∈ AM F (N ) with ρ1 ≤ ρ2 [ρ1, ρ2] = 6χ∈Cρ1,ρ2 [ρ1 ∧ χ, χ]. (15) Proof. The proof follows immediately from Corollary 2.
Example 3. Consider the interval [{∅}, {{1, 2}, {3}}]. Since we have {{1, 2} ∩ {3}} = {∅} ≤ {∅} so that C{∅},{{1,2},{3}} = {{{1, 2}}, {{3}}}, and [{∅}, {{1, 2}, {3}}] = [{∅}, {{1, 2}}] 6 [{∅}, {{3}}].
Example 4. Consider the interval [{{4}}, {{1, 2, 4}, {3, 4}}]. Since we have {{1, 2, 4}∩ {3, 4}} = {{4}} ≤ {{4}} so that C{{4}},{{1,2,4},{3,4}} = {{{1, 2, 4}}, {{3, 4}}}, and [{{4}}, {{1, 2, 4}, {3, 4}}] = [{{4}}, {{1, 2, 4}}] 6 [{{4}}, {{3, 4}}].
Example 5. Consider the interval [{{4}, {6}}, {{1, 2, 4}, {3, 4}, {3, 5, 6}}]. Since we have {{1, 2, 4}∩{3, 4}} = {{4}} ≤ {{4}, {6}}, {{1, 2, 4}∩{3, 5, 6}} = {∅} ≤ {{4}, {6}}, {{3, 4} ∩ {3, 5, 6}} = {{3}} 6≤ {{4}, {6}}, so that C{{4},{6}},{{1,2,4},{3,4},{3,5,6}} = {{{1, 2, 4}}, {{3, 4}, {3, 5, 6}}}, and [{{4}, {6}}, {{1, 2, 4}, {3, 4}, {3, 5, 6}}] = [{{4}}, {{1, 2, 4}}]6[{{4}, {6}}, {{3, 4}, {3, 5, 6}}].
Require: ρ1 ≤ ρ2 Ensure: Result is a set of intervals, {I1, I2, . . . , Ik}, such that [ρ1, ρ2] = 6i=1...kIi function decomposeInterval(ρ1, ρ2)
Compute the set Cρ1,ρ2 of connected components according to Definition 2. return {[ρ1 ∧ γ, γ]|γ ∈ Cρ1,ρ2 } end function
Definition 3. Let ρ1, ρ2 ∈ AM F (N ), ρ1 ≤ ρ2. We use the notion of level λl in the interval [ρ1, ρ2] to denote maximal anti-monotonic functions consisting of elements of a specific size l, and we introduce the (.)+ and (.)− operators to transform functions from one level to a neighboring level, as follows: λl = {A ⊆ N |ρ1 ∨ {A} ∈]ρ1, ρ2], |A| = l}(∀l ≥ 0), α− = {X ∈ λl−1|∃A ∈ α : X ⊆ A}, (∀α ⊆ λl, ∀l > 0). α+ = {X ∈ λl+1|∀x ∈ X : X\{x} ∈ λl ⇒ X\{x} ∈ α}, (∀α ⊆ λl, ∀l ≥ 0),(17) (18) (16) Note that in Definition 3, in (17) α+ ⊆ λl+1 and in (18) α− ⊆ λl−1, 4
Decomposition of a General Interval into
Computationally Easy Intervals
Lemma 2. Let ρ1, ρ2 ∈ AM F (N ), ρ1 ≤ ρ2 and χ ∈ [ρ1, ρ2]. Then χ has the following unique decomposition: χ = ρ1 ∨ χ0 ∨ χ1 ∨ χ2 ∨ . . . , (19) where ∀l ≥ 0 : χl ⊆ λl, χl−+1 ≤ χl, χl+1 ≤ χl+.
Proof. We start from the decomposition in sets of specific levels: χ = (χ ∩ ρ1) ∨ (χ ∩ λ0) ∨ (χ ∩ λ1) ∨ (χ ∩ λ2) ∨ . . . (χ ∩ λs−1) ∨ (χ ∩ λs) (20) where s is the size of the largest set in χ. We now set χl = ∅ for l > s. Further, let χs = χ ∩ λs and note that the decomposition does not change if we add χs− to the sets of level s − 1.
χ = (χ ∩ ρ1) ∨ (χ ∩ λ0) ∨ (χ ∩ λ1) ∨ (χ ∩ λ2) ∨ . . . (χ ∩ λs−1 ∨ χs−) ∨ χs. (21) This suggests the recursive definition leading to and since χ ≥ ρ1:
∀l ∈ {0, . . . , s − 1} : χl = (χ ∩ λl) ∨ χl−+1 χ = (χ ∩ ρ1) ∨ χ0 ∨ χ1 ∨ χ2 ∨ . . . χs−1 ∨ χs
χ = ρ1 ∨ χ0 ∨ χ1 ∨ χ2 ∨ . . . χs−1 ∨ χs.
The inequalities in (19) now follow immediately from (22) and Definition 3. Given the decomposition (19), it follows immediately that χs = χ∩λs. χs−1 ≥ χs− (22) (23) (24) implies χs− ⊆ χs−1. Furthermore, necessarily χ ∩ λs−1 ⊆ χs−1 so that we find χs−1 ≥ χs− ∨ (χ ∩ λs−1). Since any set in χs−1 not dominated by a set in χs is necessarily in χ, we have χs−1 ≤ χs− ∨ (χ ∩ λs−1) and equality follows. Recursive application of this reasoning proves uniqueness.
Theorem 4. For ρ1, ρ2 ∈ AM F (N ) with ρ1 ≤ ρ2, we have Proof. Note that the number of non trivial summations in (25) and ( 26 ) is always finite: there is a maximal level for any finite interval, above this level α++ will be empty and the contribution in the power of 2 will be zero. Given the decomposition in Lemma 2, and a list of specific levels l1 < l2 < . . . < lk where σli ⊆ λli are given such that
∀li, li+1 : σl−i+d1i ≤ σli and ∀li−1, li : σli ≤ σl+i−d1i−1 where di = li+1 − li and α+/−d = (. . . ((α+/−)+/−) . . . )+/− (d operators (.)+/−), one can ask for the set of χ decomposing according to (19) such that ∀i : χli = σli . This set has a lower bound χb = ρ1 ∨ σl−0l0 ∨ σl−0(l0−1) . . . ∨ σl0 ∨ σl−1d0 ∨ σl−1(d0−1) . . . and an upper bound χt = ρ1 ∨ λ0 ∨ λ1 . . . ∨ λl0−1 ∨ σl0 ∨ σl+0 ∨ σl+02 . . . ∨ σl+0(l1−l0−1) ∨ σl1 ∨ σl+1 . . .. In fact, all elements in the interval [χb, χt] satisfy this requirement. In the case of all odd, respectively all even, levels given, summing the sizes of all such intervals over all possible specifications σ2l+1, respectively σ2l, results in the expansions of the Theorem.
Theorem 4 allows to compute intervals in AM F (N ) for |N | = 7, and computes all intervals for |N | = 6 in milliseconds.
IN = [{∅}, N2 ] where, for convenience, we use the notation Nk to denote the set of subsets of size k of a set N = {1, 2, ..., n}. IN is seen to have only two nonempty levels. Indeed, λ0 = {}, λ1 is the set of all singletons of elements of N and λ2 = N2 . Since λ0 = {}, for each α1 ⊆ λ1 we have α1− = {}, while α1+ = span(α1) 1. We find 2 1 Here the span of an anti-monotonic function is the set of elements occurring in true sets of the function, i.e. span(α) = SX∈α X which is the well known formula for the number of labeled graphs with at most n nodes (Sloane series A006896 [7]). This identity becomes obvious when we apply the alternative expression: graphs g on n vertices = Xn |graphs covering {1, 2, ..., i}| ni 2n−i. (28) (29) (31) (32) (33) 5
A Recursion Formula for the Size of the Complete Space
In this section, we present a formula for the size of AM F (n + k), k ≥ 0 summing over the space AM F (n). The formula is used to generate an efficient algorithm to compute the size of AM F (n + 2) from AM F (n). We start from the following observation, using the operator × defined as 2 ∀χ ∈ AM F (N ), S ⊂ N, S ∩ N = ∅ : χ × {S} = {X ∪ S|X ∈ χ}. (30) Example 7. For χ = {{1}, {2, 3}, {3, 4}} and S = {5, 6, 7} we have according to this definition χ × {S} = {{1, 5, 6, 7}, {2, 3, 5, 6, 7}, {3, 4, 5, 6, 7}}.
Lemma 3. Given n, k > 0, N = {1, . . . , n} and Kn = {n + 1, . . . , n + k}, for each χ ∈ AM F (N ∪ K) there exists exactly one sequence {χ{S}|S ⊆ Kn} of functions in AM F (N ) such that χ = _
χS × {S},
S⊆Kn ∀S ⊆ Kn : χS ∈ AM F (N ), ∀S, S0 ⊆ Kn : S ⊆ S0 ⇒ χS ≥ χS0 .
Proof. For each S ⊆ Kn define χS = {X\Kn|X ∈ χ, S ⊆ X} Corollary 4. For finite N, K ⊆ N, N ∩ K = ∅ as in Lemma 3, the size of AM F (N ∪K) is equal to the number of homomorphisms (2K , ⊆) → (AM F (N ), ≥ ). 2 This is a restricted definition of the × operator discussed extensively in [9]. This paper introduces an effective enumeration technique which can be used in to sum over the space AM F (N ). Now consider the restricted homomorphisms (2K \{∅, K}, ⊆) → (AM F (N ), ≥ ), i.e fix χS for any S 6∈ {∅, N }. Any such restricted homomorphism can be completed by components χ0 ≥ Wk∈K χ{k} and χN ≤ Vk∈K χN\{k}. We define coefficients PN,K,ρ0,ρN as follows Definition 4. For finite N, K ⊆ N, N ∩K = ∅, and for ρ0, ρN ∈ AM F (N ), ρ0 ≥ ρN , PN,K,ρ0,ρN is the number of homomorphisms f : (2K \{∅, K}, ⊆) → ([ρN , ρ0], ≥ ) such that Wk∈K f ({k}) = ρ0 and Vk∈K f (N \{k}) = ρN and we find Theorem 5. For finite N, K ⊆ N, N ∩ K = ∅, |AM F (N ∪ K)| = |[∅, ρN ]|PN,K,ρ0,ρN |[ρ0, {N }]|.
(34)
X ρ0≥ρN ∈AMF (N) Proof. Any restricted homomorphism f can be extended by elements of the intervals [∅, ρN ] and [ρ0, {N }], and any extension results in a different function in AM F (N ∪ K).
The P-coefficients are in general hard to compute. In the special case of |K| = 2 however, the following property leads to a simple algorithm.
Property 1. For finite N, K ⊆ N, N ∩ K = ∅, |K| = 2, we have
PN,K,ρ0,ρN = 2|CρN \ρ0,ρ0\ρN |.
Proof. Let K = {k1, k2}. The coefficient is the number of solutions to the simultaneous equations χ{k1} ∨ χ{k2} = ρ0, χ{k1} ∧ χ{k2} = ρN .
Let A, B ⊆ ρ0\ρN such that CρN (A, B), i.e. {A ∩ B} 6≤ (ρN \ρ0). Then A and B must be in at least one of χ{k1} or χ{k2} due to (36) and in at most one due to (37). On the other hand, any set A in ρ0\ρN must be in either χ{k1} or χ{k2} and can not be in both.
X ρ0≥ρn∈AMF (n) |AM F (n + 2)| = |[∅, ρn]||[ρ0, {N }]|2Cρn\ρ0,ρ0\ρn . (38)
tions only for ρN in AM F (
Some structural properties were derived which allowed decomposition. We used the properties of intervals to derive a formula allowing efficiently computing the size of any interval in spaces with values of n up to 7. Finally, we derived an expansion of the size of the (n + k)th space based on an enumeration of the space n. The terms in this expansion are products of sizes of intervals multiplied by coefficients which we termed ’P-coefficients of order k’. P-coefficients of order 2 turn out to be efficiently computable, and the resulting formula, combined with a reduction to nonequivalent anti-monotonic functions, allowed computing the
The results in sections 1 − 3 were obtained using the operators ∧ and ∨ only and are thus valid for any distributive lattice. The proofs of the results in sections 4, 5 explicitly relied on properties of sets. It is not hard to see that there are more general equivalents of these formulae. We plan to extend the analysis of intervals and derive the more general equivalents in a forthcoming paper.
The success in computing |AM F (
for n = 6 equipped with a fast evaluator for order 3 P-coefficients could produce
|AM F (