数理解析研究所講究録
第 1846 巻 2013 年 113-128

113

Upper and Lower Bounds on the Number of Disjunctive Forms巽久行 (1)

正弘 (1)宮川

向殿

政男 (2)(1) 筑波技術大学情報システム学科，(2) 明治大学理工学部情報科学科

Hisayuki TATSUMI (1)Masahiro MIYAKAWA(1)

Masao MUKAIDONO(1) Dept. of Computer Science,

Tsukuba University of Technology(2) Dept. of Computer Science,

Meiji University(2)

Abstract
In this paper we evaluate the upper and lower bounds on the number of disjunctive (normal) forms of

an

$n$

-variable Boolean function (for our purpose we take the constant 1 function which always takes the
The enumeration problem of the disjunctive forms is equivalent to enumerating elements of avalue 1).

distributive lattice, and it can be solved by enumerating antichains on the temary

isomorphic to the partially ordered set formed by all terms of the given function.

$n$-cube which is

For the upper bound weuse a newly invented decomposition of the partially ordered set into chains (we introduce a tree structure
which spans the cube). For the lower bounds, we evaluate the number of anticains on the cube byanalyzing dependency among three consecutive layers instead of two.
different disjunctive forms for the constant 1 function.

Put $|DF(1)|$ the number of

We obtain newly improved upper and lower

bounds:$2^{2^{r}\cdot(\begin{array}{l}nr\end{array})(\begin{array}{l}nr\end{array})\cdot(1+e^{-r^{2}2^{-r}})}<|DF(1)|<( \frac{\sqrt[4]{3}}{3}n)^{2^{r}\cdot(\begin{array}{l}nr\end{array})}$where$r\fallingdotseq 2n/3$, the Spemer rank for the temary cube.

bound on the number of disjunctive forms for all$n$‘Ihis serves as a basis for the upper and lower-variable Boolean functions as well as a basis for theenumeration of many-valued logic functions.

Keywords:

enumeration, disjunctive form, logic function, distributive lattice, antichain

114
1. Introduction
Logic function is usually represented by a disjunctive form, i.e., logical $OR$ of logical product of its

variables (terms), and so it is also called logical sum or disjunctive normal form. Given a logic function
there are in general many finite number of disjunctive forms representing it.

disjunctive forms for a function, or of the total number of them for the set of all

Finding the number of$n$-variable logic function

are fundamental for knowing the representing capability of disjunctive forms as well as for enumerating$k$-valued logic functions [1,2].
It is well-known that$\infty$unting the number of disjunctive forms is equivalent to$\infty$elements of a distributive lattice, and generally it is considered to be a hard problem.

unting that of the
Indeed, the exact

numbers of them are known hitherto only up to $n-4[3]$ . Among enumeration problem of logic
functions the so-called Dedekind problem is a famous one with more than a hundred years history. It is aproblem to$\infty unt$

the number of monotone logical functions of Boolean-variables. This is equivalent tocountming the number of elements of the free distributive lattice with$n$generating set [4]. This is a hard

enumeration problem and the numbers are known only up to $n-8$ [5]. As the set of disjunctive forms
include as its proper subset the set of monotone logic functions, the numbers of disjunctive forms are larger
than the Dededind numbers.

In this paper we present new upper and lower bounds on the number of disjunctive forms. It is
known that the number of elements of a finite distributive lattice is equal to the number of antichains in thepartial ordered set formed from its irreducible elements [6,7].

In our case terms (with some restrictions)coincides with the irreducible elements. So our task is to evaluate the number of antichains contained in

the partial ordered set formed from terms. Our approach follows the one used to obtain the upper andlower bounds on the number of monotone logical functions [8,9], but applyming technique used in theenumeration of the number of fuzzy logic functions [10,11]. To derive new bounds we introduce newideas in both analyzing upper and lower bounds.

2. Defmitions
LetTrue).

$n$be a positive integer.

Put $B-\{0,1\}$ .

An

$n$

Let

$0$

and 1 represent Boolean values as well$(0$

for False and 1 for-variable logic (or Boolean) function is a map $f:B^{n}arrow B$ . Let$P_{2}^{n}$115
denote the set of all$n$

Let us denote (Boolean) variables by $x_{i}(i-1,\cdots,n)$-variable logic functions.

and let us denote logical operations (connectives) AND, $OR$ and NOT by(logical sum) and$v$$\sim$

combining the variables$n$(negation).

$x_{i}(i\approx 1,\cdots,n)$-variable logical function.

index

$i$

$\alpha_{j}$The relation

and$\{\alpha_{1},\cdots,\alpha_{s}\}$a literal.

$\sim x_{i}$$x_{i}$

and$A$$\sim x_{i}$$\Leftrightarrow$

Define arelation

every hteral offunction defined by a formula$A$formula represents anappears in it simultaneously. Let$\alpha_{j}$$\subset$

formula

$T$

Let

be
$\alpha_{i}$by:appears in$\alpha_{i}$

.

(1)
$T$

of all terms.

as the result does not depend on the application order of[Definition 1]$A$

term is a product of literals where eachnaturally induces a partial order on the set$\subset$variables) is a formula obtained by

By definition null term (null string) is a term and we represent it by 1.

be distinct tenns.
$\alpha_{i}\subset\alpha_{j}$$\alpha_{i}\not\subset\alpha_{j}$$x_{i}$$n$by the above logical operations.

appears at most once, i.e., no hterals

the set of all terms.

and

Call

logical formula (of$A$(logical product operation),$v$

For a set of terms, there corresponds a logical$f-\alpha_{1}\vee\cdots va_{s}.$$f-\alpha_{1}v\cdots\alpha_{s}$is a disjunctive form if its every term is irreducible, that isfor every $i\neq j.$$\square$

It is well-known that every logical function can be represented by a disjunctive form. ($A$ constantfunction$0$which takes the constant is represented by null disjunctive form which has no term.)$0$

For a function $f$ there can be, in general, many disjunctive fonns apart from the difference of ordersof the terms.

Put $V=\{O,1/2,1\}$ . Define a partial order$0\prec 1/2$$\prec$

on

$V$

by

and $1\prec 1/2$ .

Put $V-\{0,1/2,1\}^{n}$ , the temaryorder$\prec$(2)$n$-cube which is the set of all temary$n$-vectors.

We extend the partial

on V coordinate-wise as follows.

[Defmition 2]$a\prec b$

Let $a=(a_{1},\cdots,a_{n})$ and $b=(b_{1},\cdots,b_{n})$ .
$\Leftrightarrow$$a_{i}\prec b_{i}$for all $i(i\approx 1,\cdots,n)$ .

Then
(3)
口

116
Define a 1:1 map between V and[Definition 3]

as follows.

$T$

For $a-(a_{1},\cdots,a_{n})\in V$ we map$rightarrowrightarrowarrow$$\{a_{i^{-1/2}}^{a_{i}-0}a_{i}-1$$\alpha(a)-x_{1}^{a_{1}}\cdots\cdot\cdot x_{n}^{a_{\hslash}}$where we put(4)$x_{i}^{a_{i}}-\sim x_{i}x_{i}^{a_{i}}-x_{i}x_{i}^{a_{i}}-1$($x_{i}$

does not appear)口

It is easy to prove that the partial order$a\prec b$$\Leftrightarrow$$a(a)\subset a(b)$So the statements about$(T,\subset)$$(T,\subset)$and$(V, \prec)$aoe isomorphic, i.e.,.

(5)can be interpreted as ones about$(V, \prec)$, and vice versa.

For $a-(a_{1},\cdots,a_{n})\in V$ , put$I(a)-\{i|a_{i}-1 or a_{i}-0\}$.

The number $r(a)-|I(a)|$ is the rank of
$k$

(6)
$a$

. Let us denote by$V_{k}$

the set of vectors whose rank equals:$V_{k}-\{a|r(a)-k, a\in V\}$We have$V-\bigcup_{k-0}^{n}V_{k}$element of

$V$

.

(7)

and $|V_{k}|-2^{k}\cdot(kn)$ .

$(w.r.t. \prec)$

The sole element $(1/2,\cdots,1/2)\in V_{0}$ is the maximaland every element of $V_{n}(-B^{n}-\{0,1\}^{n})$ is a minimal element of V (noother element is minimal). We put$V_{\overline{n}}(-V\backslash V_{n})$which exactly$\infty$

rresponds to the set of terms $T.$

3. Preliminaries
Let $S-\{a_{1},\cdots,a_{s}\}$ be a subset from the temary[Defmition 4]$i,$$j(i\sim j)$.

The set$S$

is a chain if holds$n$-cube V.

$a_{1}\prec\cdots\prec a_{s}$. It is an antichain if holds$a_{i}\prec a_{j}$for no口The integer $|S|$ is the length (size) of the chain (antichain). We include the empty set as antichain.
[Theorem 1]

For an antichain of V there exists a disjunctive form (uniquely up to the order of its

117
terms) and vice versa.

口Thus there is a 1:1 correspondence between the sets of antichains of V and those of disjunctive

forms of.

$T$

So, counting the disjunctive forms is reduced to that of antichains in V.

the number of disjunctive form is bounded from above by
The set of disjunctive forms of[Theorem 2]operation$S$$\vee(OR)$and$\wedge(AND)$$n$

As $|V|=3^{n}$

It is well-known:$2^{3^{n}}$-variables forms a distributive lattice with respect to the.

口So our problem is also to count the number of elements of a finite distributive lattice.

It is clear thatthe Dedekind problem (counting the monotone functions) is a special case of our problem as disjunctive

forms can be of terms with only positive literals as a special subset of disjunctive forms.

First we consider the number of disjunctive forms for a given logic function$n$-variable logic function $f(x_{1},\cdots,x_{n})$ is given.

$f$. Assume that an

We evaluate the number of disjunctive forms which

represent $f.$Let$\alpha=x_{1}^{a_{1}}\cdots\cdot\cdot x_{n}^{a_{n}}$be a term.

$f([a_{1}],\cdots,[a_{n}])-1$

where

i

$[a_{i}]$

$A$

term

$\alpha$belongs to$f$

if holds

,

( )
$S$

denotes largest integer not exceeding$a_{i}$, e.g., $[1/2]-0$. The set $V(f)$ of terms of

$f$

$S$

(9)

$V(f)-\{\alpha=x_{1}^{a_{1}}\cdots\cdot\cdot x_{n}^{a_{n}}|f([a_{1}],\cdots,[a_{n}])=1, a_{1},\cdots,a_{n}\in V\}$To a $=(a_{1},\cdots,a_{n})$ assign a subset of$a^{*}\simeq$[Theorem 3]

and let{$(b_{1},\cdots,b_{n})\in B^{n}|b_{i}-0$$B^{n}$or 1 if $a_{i}=1/2,$$b_{i}-a_{i}$otherwise}

Let an -ary logic function $f$ be represented by a disjunctive form$n$$\alpha_{i}-x_{1}^{a_{i_{1}}}\cdots\cdot\cdot x_{n}^{a_{i_{n}}}$and let$a_{i}=(a_{i_{1}},\cdots,a_{i_{n}})$for $i(i-1,\cdots,n)$ .

(10)$f-\alpha_{1}\vee\cdots\vee\alpha_{s}$Then the set$\{a_{1},\cdots,a_{n}\}$is an antichain of V and holds$a_{1}\cup\cdots\cup a_{s}^{*}-V_{n}*(f)$

(11)

118
Conversely, if the last sentence is true, then the set of terms

defined by $a_{i}(i-1\cdots,n)$ is a$\{a_{1},\cdots,a_{s}\}$disjunctive form of $f.$
(Proof)This follows from Theorem 1.

口We have the following.
[Theorem 4]$\vee(OR)$andThe set of disjunctive forms of $f$ forms a distributive lattice with respect to the operations
(AND)

口

Thus the problem to find all disjunctive forms for$f$is to find all antichains$\{a_{1},\cdots,a_{n}\}$in $V(f)$such that the equation (11) holds.

The next statement is a slight improvement of this statement (we omit the proof).
$V_{\overline{n}}(f)-V(f)\backslash V_{n}(f)$[Theorem 5]

Put.

The number of disjunctive forms of$f$is equal to the number of antichains in$V_{\overline{n}}(f)$.

口Let us denote the set of disjunctive forms of
disjunctive forms for the
$DF-$

$n$

$f$

by $DF(f)$ .

Let $DF$ denote the set of all-variable function. Then
(12)$\cup DF(f)$$f$ぢ

As $DF(f)$ ’s are disjoint we have$|DF|-DF(f)f$

$|$

.

(13)

明

[Theorem 6]

The maximal number of $|DF(f)|$ is attained when $f-1$ (a$\infty$

nstant function which

always takes the value 1).

口

Thus we have$|DF(1)|<|DF|<2^{2^{n}}\cdot|DF(1)|$

We use this formula for evaluating the bounds for $|DF|$ . So we$DF(1)$.

(14)$\infty$ncentrate on the evaluation of

119
4. Upper boundFirst, we introduce the upper bound described in [10].
poset$V_{\overline{n}}$union of$(that is,$, Dilworth’s theorem[7,12] says that$m$

$V_{\overline{n}}$chains. Each chain has at mostelement $in V_{0})$ .

intersection with each ofThus, if$m$

$S$

the size of a largest antichain in theelements from

$V_{\overline{n}}$, then$V_{\overline{n}}$$V_{\overline{n}}$$S$$V_{\overline{n}}$)and shares the maximal element$S$

is uniquely determined by its

chains; the intersection contains at most one element.

ignore the maximal element of
$n$

$m$

is the disjoint (except the maximal element ofis an antichain in

has the maximal element, all elements inthere are at most

$n$

For

In the case that$S$

are included by this element. As a result, we can safely, and so assume that each chain has at most $n-1$ elements.

Since

possibilities (including the case that we select no element) for the intersection of$S$

with any chain, $|DF(1)|$ is bounded as follows:$|DF(1)|<n^{m}$

Here, sincein$V_{\overline{n}}$enjoys the Spemer property [7,14] from [13], we assume that the largest-sized antichain

has cardinality$V_{\overline{n}}$the cardinality

$m$

(15)

$m$

, i.e., we put $m:- \max(|V_{k}|)$ .

(let us call it Spemer rank).

Let

$r$

be the rank of the layer inThen, $r-\lceil 2n/3\rceil$ holds [10].

$V_{\overline{n}}$havingSo, the above upperbound becomes as follows:$|DF(1)|<n^{2^{r}(\begin{array}{l}nr\end{array})}$

.

(16)

This argument is similar to one used in [8] for estimating the upper bound of monotone logic functions with$n$-variables.
Now, we proceed to improve the upper bound by incorporating a new idea.

The poset$V_{\overline{n}}$divide at the $r-$ th (the Spemer) rank into two parts, and we focus our attention on the part ofwe$2^{r}$

temary -vecters derived by expanding $(a_{i,j}\approx 0,1:1\leq j\leq r)$ the temary -vector $(a_{i_{1}},1/2,\cdots,1/2,a_{i_{r}})$ ,$n$where 1/2 appears at $n-r$ fixed (but any) coordinates; three arepart).

$n$$(\begin{array}{l}nr\end{array})$such copies (see Figure 1, shaded

120

Figure 1. Dividing the poset

First part is a poset$\cup V_{b}$$V_{\overline{n}}$into two parts at the Spemer rank $r.$

, which is composed of $r+1$ layers in$V_{\overline{n}}$whose rank$b$

is equal to$0\leq bsr$

or smaller than $r.$
the rank$d$$Se\infty nd$larger than$r$part is a poset$r+kdsn-1\cup V_{d}$, which consists of $n-1-r$ layers in. Here, we can observe that$\cup V_{b}$$V_{\overline{n}}$with

can be divided into disjoint except the$0sbsr$maximal element$(1/2, \cdots,1\int 2)(\begin{array}{l}nr\end{array})$binary trees, each of which has$2^{r}$

minimum elements inwhere, $the 1/2$ ’s positions $of each$ minimum element $is the same)$ (see Figure 2).

$($

Figure 2. Partition of the upper cube into$(\begin{array}{l}nr\end{array})$binary trees $(n-3, r-2)$.

$V_{r}$

121
Now we divide each tree into disjoint chains in the following way: For a given tree we select alargest path (chain) from the root of the tree (if there are many we take the leftmost path). Then weremove the chain from the tree breaking the tree into a forest (a set of trees). We repeat the sameprocedure for each tree of the forest until there remains a tree which consists of a single node (see Figure 3).

Now from the largest chain we remove the largest element of the chain; i.e. the element ofway, each binary tree is divided into 2 chains of length(see Figure 4).

The sum of these chains is

$r$

and

$2+ \sum_{k}2^{k}(=2^{r})$$2^{k}$

.

ra 永
$I$

$r-11r02::\ovalbox{\tt\small REJECT}_{\ovalbox{\tt\small REJECT}\Vert}^{V_{0}}\ovalbox{\tt\small REJECT}\ldots\xi[\cdots[\cdots \emptyset\emptyset\cdots\bullet$$2^{0}rightarrow 2^{1} \cdots \overline{2^{k}} \cdots rightarrow^{2^{r-1}}$$2^{r}$

chains in$($$\cup V_{b})$$b$.

In thischains of length $r-k,$ $1\leq k\leq r-1$

Figure3. Decomposition ofabinary tree into diqjoint chains.

Figure 4.

$V_{0}$

obtained from a binary tree.

122
In addition, the second poset$\bigcup_{d}V_{d}$can be divided into disjoint$2^{r}(\begin{array}{l}nr\end{array})$

chains with a length of at most$n-1-r$ by Dilworth’s theorem[7,12](see Figure5).

rank$n-1r+2r+1: \frac{\iota||||\cdots||\cdots|||\cdots|\prime\backslash }{\backslashr}$$2^{r}$

Figure5.

Then, for$2^{r}$

elements inchains in$2^{r}$$V_{r}$$($$\bigcup_{d}V_{d})$obtained by Dilworth’stheorem, there exist 2 chains with a length of at most $r+(n-1-r)$ andchains with a length of at most $(r-k)+(n-1-r),$ $1\leq k\leq r-1$ in the poset$\cup V_{b}$and$\cup V_{b}$

$b$

and

$\cup V_{d}$$($namely,$in V_{\overline{n}})$, then, for$2^{r}$

elements in

. If

$S$

$d$

$b$

is any antichain in$\cup V_{d}$$2^{k}$$V_{r},$$S$

is uniquely$d$detennined by its intersection with each of the above chains. Considering all possibilities, including thecase of no select, the intersections of$S$with any chain give the upper bound of $|DF(1)|$ as follows:$((r+(n-1-r)+1)^{2} \cdot\prod_{k-1}^{r-1}((r-k)+(n-1-r)+1)^{2^{k}})^{(\begin{array}{l}nr\end{array})}$$-(n \cdot\prod_{k-0}^{r-1}(n-k)^{2^{k}})^{(\begin{array}{l}nr\end{array})}(n^{2^{r-1}}\cdot(n-r+1)^{2^{r-1}}\cdot\prod_{k-0}^{r-2}(1-\frac{k}{n})^{2^{k}})^{(\begin{array}{l}nr\end{array})}$(17)

Put $r-2n/3$ , the Spemer rank, then the equation (17) $be\infty mes$ as follows:(17)$<(n^{2^{r-1}} \cdot(\frac{n}{3}I^{2^{r-1}}\cdot(\frac{1}{3}I^{2^{r-2}})^{(\begin{array}{l}nr\end{array})}(\frac{\sqrt[4]{3}}{3}n)^{2^{r}(\begin{array}{l}nr\end{array})}$(18)

From the above result, using the following Stirling’s approximation [15] for factorials:$2^{r} (\begin{array}{l}nr\end{array})-\frac{3}{2\sqrt{\pi}}\cdot\frac{3^{n}}{\sqrt{n}}\cdot(1+o(\frac{1}{n}))$,

the new upper bound of $|DF(1)|$ is rewritten as follows:

(19)

123
(20)

$|DF(1)|<2^{\alpha},$where$\alpha=3^{n}\cdot\frac{3}{2\sqrt{n\pi}}(1+\frac{c}{n})\cdot\log_{2}\frac{\sqrt{3}^{4}n}{3}.$5. Lower boundFor any $0<k<n$ , in two adjacent ranks

We first introduce the lower bound described in [10].
and $k-1$ in a poset$s$elements inelements in$V_{k}$$V_{k-1}$$V_{\overline{n}}$, each element in$V_{k}$are covered by at most
do not cover the$s$is covered by

$ks$

$k$

elements inelements in$V_{k}$

elements in$V_{k-1}$.

$V_{k-1}$(see Figure 6).

$s$number of antichain obtained from the remaining elements inelements where, $0\leq s\leq|V_{k}|)$ in$($$V_{k-1}$

So,

Since the remaining $|V_{k-1}|-ks$, any subset of the remaining elements informs an antichain. Therefore, in the case of choosing$k$$V_{k}$$V_{k-1}$, theis at least as follows, and this gives

the lower bound of $|DF(1)|.$(21)$\sum_{s}(^{|V_{k}|}s)2^{V_{k-1}\vdash k}=2^{\psi_{k-1}1}\cdot\sum_{s}(s)2^{一}$

By applying the binomial theorem [15], the equation (21) becomes as follows:(22)$-2^{V_{k-1}1.b+2^{-k}\uparrow^{v_{k}|}}-2^{\psi_{k-1}1}\cdot e_{u}(kn)$where,

In equation (22), take(22)

$e_{u}-(1+2^{-k}\rangle^{2^{k}}$

$k$

as

$r$

, where $r=2n/3$ is the Spemer rank as described in the previous section.

If $narrow$ oo, then$e_{u}arrow e$(the base of natural logarithm) and$(\begin{array}{l}nr-1\end{array})arrow 2\cdot(\begin{array}{l}nr\end{array}).$So$|V_{r-1}|-|V_{r}|$holds.

(23)

Consequently, we obtain the lower bound of $|DF(1)|$ in [10] as follows:$|DF(1)|>2^{|v_{r}|}\cdot e(\begin{array}{l}nr\end{array})(-2^{2^{r}(^{n})_{e}(^{n})}\prime\cdot\prime)$

(24)

124

Figure6. Counting the antichains in two adjacent layers.

This argument follows in a similar way one used in [9] for counting antichains in two adjacent ranks

between$n$$k$

and $k-1$ in a poset$V_{\overline{n}}$for estimating the lower bound of monotone logic functions with-variables.
Here, we can obtain the same lower bound as the equation (24) by

ranks

$k$

and $k+1$ in a poset

elements in$V_{k+1}$

.

So,

$s$

$V_{\overline{n}}$(see Figure 6).

elements inremaining $|V_{k+1}|-2(n-k)s$ elements in
the remaining elements in$(0\leq s\leq|V_{k}|)$in$V_{k}$$V_{k+1}$$V_{k}$$\infty$unting antichains in two adjacent

That is, each element incover at most $2(n-k)s$ elements in$V_{k+1}$

are not covered by$s$covers $2(n-k)$$V_{k}$

elements in$V_{k+1}$$V_{k}$, any subset offorms an antichain. Therefore, in the case of choosing, the number of antichains obtained from the remaining elements in. Since the$s$elements$V_{k+1}$

is at leastas follows, and gives the lower bound of $|DF(1)|.$$\sum_{s}(^{|V_{k}|}s)2^{\psi_{k+1}|-2(n-k)s}-2^{\psi_{k+1}1}\cdot\sum_{s}(^{|V_{k}|}s)2^{-2(n-k)s}$(25)

By applying the binomial theorem [15], the equation (25) is as follows.

(25)$-2$ 阪 1$+$$|$$\beta_{+2^{-2(n-k)}}\gamma_{-2^{|v_{k+1}|}\cdot e_{d}}^{1}r_{k}2^{3k-2n}(nk)$

,

(26)

125
where $e_{d}=b+2^{-2(n-k)})^{2^{2(n-k)}}$In the equation (26), take$narrow\infty$

as

$k$

$r$

, where $r-2n/3$ , Spemer rank.

Then $2^{3r-2n}=1$ holds.

If, then$e_{d}arrow e$(the base of natural logarithm) and$(\begin{array}{ll} nr -1\end{array})arrow 2\cdot(\begin{array}{l}nr\end{array}).$

So
(27)

$|V_{r+1}|-|V_{r}|$holds.

Consequently, we obtain the same lower bound as the equation (24), as follows:$|DF(1)|>2^{|V_{r}|}\cdot e(\begin{array}{l}nr\end{array})$($2S$)In two equations (24) and (28), antichains we have counted are independent each other (because, the former

is derived from the relation between$V_{r}$

and$V_{r-1}$, and the latter from one between$V_{r}$

and$V_{r+1}$).

By adding both results, we can improve the lower bound only slightly as follows:$|DF(1)|>2\cdot 2$ 巴$|e(\begin{array}{l}nr\end{array})$

.

(29)

Now, we proceed to improve the lower bound by counting antichains in three adjacent-ranked posets$(V_{r-1}, V_{r} and V_{r+1})$of$V_{\overline{n}}$Figure 7.

, where we take $r-2n/3$ , the Spemer rank (see Figure 7).

Counting the antichains in the three adjacent layers,
where $r=2n/3$ , the Spamer rank.

126
Here, to simplify calculation, we regard that an element in one layer

elements in the other layer between two adjacent ranked-layers.
$\infty$$t$vered by at most $rs$ elements inelements in$V_{r-1}$

In Figure 7, we$\infty$

cover at most$rt$That is,, and are covered by at most$V_{r}$

elements innsider the case that, firstly$s$$V_{r}$$\infty vers$

elements are chosen inare chosen from the elements which have remained after removing the$r^{2}t$$V_{r+1}$$\infty$$($shadow of theelements in$s$$V_{r+1}$

nor in the anti-shadow of the

any subset of the remaining elements inelements $(0\leq s\leq|V_{r+1}|)$ in$V_{r+1}$

elements) in$|V_{r}|-rs-rt$

vering$V_{r}$$t$$V_{r}$

elements in, and secondly(since the number of remaining elements is at most $|V_{r-1}|-r^{2}s$ elements).
relations, the remaining elements namely,

elements in$t$$r^{2}s$$V_{r+1}$$t$).

elements

elements inare included neither in theelements in$V_{r-1}$, respectively.

$V_{r}$$V_{r-1}$(30)$\sum_{s}(^{|V_{r+1}|}s)2^{-rs}\sum_{t}(^{|V_{r-1}|-r^{2_{S}}}t)2^{-rt}$Here, in the above equation, by applying the binomial theorem we have:$\underline{V_{r-1}|} -\underline{r^{2_{S}}}$$\sum_{t}(^{|V_{r-1}|-r^{2_{S}}}t)2^{-rt}-\beta_{+2^{-r}}V^{r-1}|-r^{2_{S}}-e_{1^{2^{r}}}$$e_{1}2^{r}$(31)

where $e_{1}-b+2^{-r})^{2^{r}}$So the equation (30) becomes as follows:.

$2^{\psi_{r}1} \cdot e\sum_{s}(^{|V_{r+1}|}s)2^{-r(1+\frac{r}{2^{r}}\log_{2}e_{1})s}\frac{\psi_{r-1}1}{1^{2^{r}}}$$s$

can be at least as follows, and this gives a new$\sum_{s}(^{|V_{r+1}|}s)\sum_{t}(^{|V|-r^{2_{S}}}r-1_{t})2^{\psi_{r}|-rs-rt}$.

So,, the number

lower bound of $|DF(1)|$ :$|$$V_{r-1}$

Then, as for inclusion

elements $(0\leq t\leq|V_{r-1}|-r^{2}s)$ inof antichains obtained from the remaining elements in$-2$ 防are$V_{r+1}$

forms an antichain. Therefore, in the case of choosing

and choosing$r$elements in $V_{r-1}(s-$larly,$r^{2}s$, and cover at most$s$(or, is covered by)

(32)

127
Furthermore, in the above equation (32), put $A-1+ \frac{r}{2^{r}}\log_{2}e_{1}$ .

By repeated application of thebinomial theorem we have:(33)$\sum_{s}(^{|V_{r+1}|}s)2^{-rAs}=(1+2^{-rA}l^{v_{r+1}|}=e^{\frac{r_{r+1}^{\gamma}1}{2^{2^{rA}}}}$

where$e_{2}\approx(1+2^{-rA}\rangle^{2^{rA}}$

So the equation (32) becomes as follows:$\underline{V_{r-1}|} |v_{r+1}|$$2^{\psi_{r}1}\cdot e_{1^{2^{r}}}$In equation (34), if(34)$e_{\overline{2^{2^{rA}}}}$$narrow\infty$, then$e_{1}arrow e$and$e_{2}arrow e$

.

Then,

$|V_{r-1}|-|V_{r}|$and $|V_{r+1}|-|V_{r}|$ hold.

Consequently, the new lower bound of $|DF(1)|$ we obtain as follows:$|DF(1)|>2$ 跨 $|.ee=2^{|V_{r}|}\cdot e$

Combining (14), (18), (35) we can obtain bounds for the number of disjunctive foms for all$n$-variable

logic functions.

6. Conclusions
In this paper we have presented new upper and lower bounds on the number of disjunctive forms of an$n$-variable binary logic function (we took the constant function 1 for our purpose). We have followed

the methods described in [10] (they originate from [8,9]) incorporating new ideas.

It is interesting to notethat the lower bound by counting antichains contained in the adjacent three layers (the Spemer rank,$r\approx 2n/3$

at the center) can be simplified as shown herein.

If we apply Gilbert’s method [8] andShapiro’s method [9] to upper and lower bound, respectively, for the poset$V_{\overline{n}}$satisfying Spemer’s lemma,

we would not expect to obtain an essential improvement over the upper and lower bounds obtained here.

References[1] Mukaidono $M$ ., “New canonical forms and their applications to enumerating fuzzy switching

128
functions”, IEEE Proc. 12th Int. Symp. Multiple-Valued Logic, pp.275-279, 1982.
[2] Tatsumi $H$ ., Mukaidono $M$ ., ”Enumerating regular temary logic functions”, Trans. IEICE Japan,

vol.J68- , no.5, pp.1027-1034, (in Japanese) 1985.
$D$[3] Tatsumi $H$ ., Mukaidono

$M$

.,

$Enumeratin_{g}$Boolean disjunctive forms”, Trans. IEICE Japan,

vol.J66- , no. 10, pp. 1201-1208, (in Japanese) 1983.
$D$

[4]

Balbes ., Dwinger ., ”Distributive lattices”, Univ. Missouri $Pr.$ , pp.88-97, 1974.
$R$

$P$

[5] Wiedemann D., ”Computation of the eight Dedekind number”, Order, vol.8, pp.5-6, 1991.
[6]

Birkhoff $G$ , “Lattice theory”, 3rd edn., Amer. Math. Soc., Colloq. Pub. no.25, 1967.

[7] Aigner $M$ ., Combinatorial theory”, Springer-Verlag, 1979.
[8]

Gilbert E.

$N$., ”Lattice theoretic properties of frontal switching function”, J. Math. Phys., vol.33,

pp.57-67, 1954.
[9] Shapiro H. $N$ ., “On the$\infty$unting problem for monotone Boolean function”, Comm. Pure. Appl. Math.,vol.23, pp.299-312, 1970.
[10] Berman ., Mukaidono $M$ .,$J$$Enumeratin_{g}$fuzzy switching functions and free Kleene algebra”, Comp.

Math. Appl., vol.10, pp.25-35, 1984.
[11] Tatsumi $H$ ., Araki., Mukaidono $M$ ., Kizawa $M$ ., ”Bounds on the number of fuzzy switching$T$functions”, Proc. First Asian Fuzzy Systems Symposium, pp.166-172, 1993.
[12] Trotter W.

., ”Partially ordered sets”, in “Handbook of Combinatorics (vol.1, chap.8)”, Elsevier$T$

Science, pp.433-480, 1995.
[13] Baker $K$ , “ $A$ generalization of Spemer’s lemma”, J. Combinatorial Theory., vol.6, pp.224-225, 1969.
[14] Engel $K$ , ”Sperner theory”, Cambridge Univ. $Pr.$ , 1997.
[15] Knuth D.

$E$., ’The art of$\infty$

mputer programming”, vol.1, 3rd edn., Addison-Wesley, 1997.