cp's OEIS Frontend

A120587 Number of inequivalent (under the group of permutations and "inversion of variables") nondegenerate monotone Boolean functions of n variables.

%I A120587 #2 Dec 06 2006 03:00:00
%S A120587 1,1,1,3,11,95
%N A120587 Number of inequivalent (under the group of permutations and "inversion of variables") nondegenerate monotone Boolean functions of n variables.
%C A120587 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.
%C A120587 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. Then 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, where p is a permutation of n elements} is a group.
%C A120587 In this context, f and g are equivalent if there exists b (an element of G) such that b.f=g. If we need to study monotone Boolean functions, we only need to study a "few" of them.
%C A120587 For example, if we want to study monotone Boolean functions of 5 variables (there are 7581 of them) we only need to study 1 of 0 variables, 1 of 1 variable, 1 of 2 variables, 3 of 3 variables, 11 of 4 variables and 95 of five variables (a total of 112 functions). Those functions "generate" all the monotone Boolean functions of 5 variables.
%e A120587 a(2)=1 because f(x,y)=xy is equivalent to g(x,y)=x+y+xy and there are no more nondegenerate monotone Boolean functions of 2 variables.
%K A120587 nonn,more
%O A120587 0,4
%A A120587 Alan Veliz-Cuba (alanavc(AT)vt.edu), Jun 16 2006