login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003183 Number of NPN-equivalence classes of unate Boolean functions of n or fewer variables.
(Formerly M0814)
0
1, 2, 3, 6, 17, 112, 8282 (list; graph; refs; listen; history; text; internal format)
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 Veliz-Cuba (alanavc(AT)vt.edu), Jun 18 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 1 06:45 EDT 2021. Contains 346384 sequences. (Running on oeis4.)