login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056287 Maximal AND-OR formula complexity (operator count) for n-input Boolean functions 4

%I

%S 1,3,9,15,28

%N Maximal AND-OR formula complexity (operator count) for n-input Boolean functions

%C a(n) = minimal number of edges in 2-terminal series-parallel switching network (where edges are labeled with the variables X_i and X_i') which achieves the worst f.

%C Consider all 2^2^n Boolean functions f of n variables X_1, ..., X_n; the X_i's and their negated values X_1', ..., X_n' are available and we must realize f using AND's and OR's of these 2n variables with the smallest total number of AND's and OR's; call the minimal total number of AND's and OR's used G(f); then a(n) = max G(f).

%H Russ Cox, <a href="/A056287/a056287.txt">Notes on computing a(4)</a>

%H Russ Cox, <a href="http://research.swtch.com/boolean">Minimum Boolean Formulas</a>

%e For n=2 a worst f is X XOR Y, which can be realized by X AND Y' OR X' AND Y = XY' + X'Y.

%e For n=3 a worst f is X XOR Y XOR Z, which can be realized by (X*Z'+X'*Z+Y')*(X*Z+X'*Z'+Y).

%e For n=4 a worst f is W XOR X XOR Y XOR Z, which can be realized by ((X XOR Z)'+(W XOR Y)')*((X XOR Z)+(W XOR Y)) = (X*Z'+X'*Z+W'*Y+W*Y')*(X*Z+X'*Z'+W*Y+W'*Y').

%e For n=5 there are three worst f's up to permutation and negation of input variables. They have 32-bit truth tables 0x16686997, 0x16696997 and 0x1669e996 (in hexadecimal).

%Y Cf. A058759, A057241, A178939.

%K nonn,nice,hard,more

%O 1,2

%A _N. J. A. Sloane_, Jan 05 2001

%E a(3) and a(4) computed by _Russ Cox_, Jan 03 2001

%E a(5) computed by _Russ Cox_ and _Alex Healy_, Jul 12 2010

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 23 14:53 EDT 2017. Contains 289688 sequences.