|
Search: id:A056287
|
|
|
| A056287 |
|
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). |
|
+0
3
|
| |
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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.
|
|
REFERENCES
|
a(3) and a(4) computed by Russ Cox (rsc(AT)swtch.com) Jan 03, 2001.
|
|
LINKS
|
Notes from Russ Cox
|
|
EXAMPLE
|
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.
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).
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')
|
|
CROSSREFS
|
Cf. A058759, A057241.
Sequence in context: A111907 A136562 A100785 this_sequence A050005 A152247 A077932
Adjacent sequences: A056284 A056285 A056286 this_sequence A056288 A056289 A056290
|
|
KEYWORD
|
nonn,nice,hard,bref,more
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Jan 05 2001
|
|
EXTENSIONS
|
Russ Cox conjectures that X_1 XOR ... XOR X_n is always a worst f and that a(5) = 33 and a(6) = 63. But (Jan 27 2006) Alex Healy points out that this conjecture is definitely false for large n. So what is a(5)?
|
|
|
Search completed in 0.002 seconds
|
