cp's OEIS Frontend

A003183 Number of NPN-equivalence classes of unate Boolean functions of n or fewer variables.

%I A003183 M0814 #31 May 01 2025 21:43:58
%S A003183 1,2,3,6,17,112,8282
%N A003183 Number of NPN-equivalence classes of unate Boolean functions of n or fewer variables.
%C A003183 Number of inequivalent (under the group of permutations and "inversion of variables") monotone Boolean functions of n of fewer variables.
%C A003183 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.
%D A003183 S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 18.
%D A003183 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003183 Aniruddha Biswas and Palash Sarkar, <a href="https://arxiv.org/abs/2304.14069">Counting unate and balanced monotone Boolean functions</a>, arXiv:2304.14069 [math.CO], 2023.
%H A003183 Aniruddha Biswas and Palash Sarkar, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL28/Biswas/biswas6.html">Counting Unate and Monotone Boolean Functions Under Restrictions of Balancedness and Non-Degeneracy</a>, J. Int. Seq. (2025) Vol. 28, Art. No. 25.3.4. See pp. 2, 8, 17.
%H A003183 Saburo Muroga, <a href="/A000371/a000371.pdf">Threshold Logic and Its Applications</a>, Wiley, NY, 1971. [Annotated scans of a few pages]
%H A003183 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%e A003183 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.
%Y A003183 Cf. A120608, A120587, A006602.
%K A003183 nonn,more
%O A003183 0,2
%A A003183 _N. J. A. Sloane_
%E A003183 Additional comments from Alan Veliz-Cuba (alanavc(AT)vt.edu), Jun 18 2006