login
Smallest Boolean functions from small equivalence classes (counted by A000231).
5

%I #29 Dec 16 2017 22:43:34

%S 0,1,3,5,6,7,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,51,53,54,

%T 55,60,61,63,85,86,87,90,91,95,102,103,105,107,111,119,123,125,126,

%U 127,255,257,258,259,260,261,262,263,264,265,266,267

%N Smallest Boolean functions from small equivalence classes (counted by A000231).

%C Two Boolean functions belong to the same small equivalence class (sec) when they can be expressed by each other by negating arguments. E.g., when f(p,~q,r) = g(p,q,r), then f and g belong to the same sec. Geometrically this means that the functions correspond to hypercubes with 2-colored vertices that are equivalent up to reflection (i.e., exchanging opposite hyperfaces).

%C Boolean functions correspond to integers, so each sec can be denoted by the smallest integer corresponding to one of its functions. There are A000231(n) small equivalence classes of n-ary Boolean functions. Ordered by size they form the finite sequence A_n. It is the beginning of A_(n+1) which leads to this infinite sequence A.

%H Tilman Piesk, <a href="/A227722/b227722.txt">Table of n, a(n) for n = 0..9999</a>

%H Tilman Piesk, <a href="http://en.wikiversity.org/wiki/Equivalence_classes_of_Boolean_functions#sec">Small equivalence classes of Boolean functions</a>

%H Tilman Piesk, <a href="http://commons.wikimedia.org/wiki/File:Boolean_functions_like_0110_1000.svg">sec of 3-ary functions</a> corresponding to a(12) = 22 = 0x16

%H Tilman Piesk, <a href="http://pastebin.com/kdZBTYnU">MATLAB code used for the calculation</a>

%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>

%F a( A000231 - 1 ) = a(2,6,45,4335...) = 3,15,255,65535... = A051179

%F a( A000231 ) = a(3,7,46,4336...) = 5,17,257,65537... = A000215

%e The 16 2-ary functions ordered in A000231(2) = 7 small equivalence classes:

%e a a(n) Boolean functions, the left one corresponding to a(n)

%e 0 0 0000

%e 1 1 0001, 0010, 0100, 1000

%e 2 3 0011, 1100

%e 3 5 0101, 1010

%e 4 6 0110, 1001

%e 5 7 0111, 1011, 1101, 1110

%e 6 15 1111

%Y Cf. A227723 (subsequence that does the same thing for big equivalence classes).

%Y Cf. A000231, A051179, A000215.

%K nonn

%O 0,3

%A _Tilman Piesk_, Jul 22 2013