|
COMMENT
|
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. 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.
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.
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.
|
