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
Aniruddha Biswas and Palash Sarkar, Counting unate and balanced monotone Boolean functions, arXiv:2304.14069 [math.CO], 2023.
S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971. [Annotated scans of a few pages]
EXAMPLE
a(2)=3 because m(x,y)=x, n(x,y)=y, k(x,y)=0, h(x,y)=1, f(x,y)=x*y, 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
KEYWORD
nonn,more
AUTHOR
EXTENSIONS
Additional comments from Alan Veliz-Cuba (alanavc(AT)vt.edu), Jun 18 2006
STATUS
approved