

A003183


Number of NPNequivalence classes of unate Boolean functions of n or fewer variables.
(Formerly M0814)


0




OFFSET

0,2


COMMENTS

Number of inequivalent (under the group of permutations and "inversion of variables") monotone Boolean functions of n of fewer variables.
Given f, a function of n variables, we define the "inversion of variables", i, by (i.f)(x1,...,xn)=1+f(1+x1,...,1+xn) (we can write (i.f)(x)=1+f(1+x) where the second "1" denotes (1,...,1)). It turns out that if f is monotone, then i.f is also monotone. On the other hand, a permutation of n elements, p, acts on f by (p.f)(x)=f(p(x)). It turns out that if f is monotone, then p.f is also monotone. We define p.i by (p.i)(f)=p.(i.f) and i.p by (i.p)(f)=i.(p.f). If we define a.b by (a.b).f=a.(b.f) for a,b elements of G, it turns out that G={p.i,p: p is a permutation of n elements} is a group. In this context, f and g are equivalent if there exists b (an element of G) such that b.f=g.


REFERENCES

S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2.  Row 18.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Table of n, a(n) for n=0..6.
S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971 [Annotated scans of a few pages]
Index entries for sequences related to Boolean functions


EXAMPLE

a(2)=3 because m(x,y)=x,n(x,y)=y,k(x,y)=0,h(x,y)=1,f(x,y)=xy,g(x,y)=x+y+xy are the six monotone Boolean functions of 2 or fewer variables; m and n are equivalent, k and h are equivalent, f and g are equivalent. Then we have 3 inequivalent monotone Boolean functions of 2 or fewer variables.


CROSSREFS

Cf. A120608, A120587, A006602.
Sequence in context: A122939 A321399 A169974 * A213616 A131788 A294455
Adjacent sequences: A003180 A003181 A003182 * A003184 A003185 A003186


KEYWORD

nonn,more


AUTHOR

N. J. A. Sloane.


EXTENSIONS

Additional comments from Alan VelizCuba (alanavc(AT)vt.edu), Jun 18 2006


STATUS

approved



