login
Smallest Boolean functions from big equivalence classes (counted by A000616).
5

%I #22 Dec 16 2017 22:43:55

%S 0,1,3,6,7,15,22,23,24,25,27,30,31,60,61,63,105,107,111,126,127,255,

%T 278,279,280,281,282,283,286,287,300,301,303,316,317,318,319,360,361,

%U 362,363,366,367,382,383,384,385,386,387,390,391,393,395

%N Smallest Boolean functions from big equivalence classes (counted by A000616).

%C Two Boolean functions belong to the same big equivalence class (bec) when they can be expressed by each other by negating and permuting arguments. E.g., when f(~p,r,q) = g(p,q,r), then f and g belong to the same bec. Geometrically this means that the functions correspond to hypercubes with binarily colored vertices that are equivalent up to rotation and reflection.

%C Boolean functions correspond to integers, so each bec can be denoted by the smallest integer corresponding to one of its functions. There are A000616(n) big 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="/A227723/b227723.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#bec">Big equivalence classes of Boolean functions</a>

%H Tilman Piesk, <a href="http://commons.wikimedia.org/wiki/File:0111_1000_1000_1000_Boolean_function_16*24.svg#File">bec of 4-ary functions</a> corresponding to a(85) = 854 = 0x0356

%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( A000616 - 1 ) = a(2,5,21,401,...) = 3,15,255,65535,... = A051179

%e The 16 2-ary functions ordered in A000616(2) = 6 big equivalence classes:

%e a a(n) Boolean functions hypercube (square)

%e 0 0 0000 empty

%e 1 1 0001, 0010, 0100, 1000 one in a corner

%e 2 3 0011, 1100, 0101, 1010 ones on a side

%e 3 6 0110, 1001 ones on a diagonal

%e 4 7 0111, 1011, 1101, 1110 ones in 3 corners

%e 5 15 1111 full

%Y Cf. A227722 (does the same for small equivalence classes).

%Y Cf. A000616, A051179.

%K nonn

%O 0,3

%A _Tilman Piesk_, Jul 22 2013