login
A003039
Maximal number of prime implicants of a Boolean function of n variables.
(Formerly M1596)
3
1, 2, 6, 13, 32, 92
OFFSET
1,2
COMMENTS
Dunham and Fridsal showed that a(8) is at least 576. - Don Knuth, Aug 25 2005
REFERENCES
M. M. Gadzhiev, Maximal length of the reduced disjunctive normal form for Boolean functions with five and six variables, Diskretnyi Analiz (Novosibirsk), (1971), 3-24 [ Computing Reviews #23,815, Sep. 1972 ].
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
B. Dunham and R. Fridshal, The problem of simplifying logical expressions, Journal of Symbolic Logic, 24 (1959), 17-19.
M. M. Gadzhiev, Maximal length of the reduced disjunctive normal form for Boolean functions with five and six variables, Diskretnyi Analiz (Novosibirsk), (1971), 3-24 [ Computing Reviews #23,815, Sep. 1972 ]. [Annotated scanned copy]
M. M. Gadzhiev, Maximal length of the reduced disjunctive normal form for Boolean functions with five and six variables (abstract), Diskretnyi Analiz (Novosibirsk), (1971), 3-24 [ Computing Reviews #23,815, Sep. 1972 ]. [Annotated scanned copy of abstract]
EXAMPLE
a(3)=6 because of (x XOR y) OR (x XOR z) OR (y XOR z).
CROSSREFS
Sequence in context: A099232 A280758 A053562 * A109385 A244578 A238827
KEYWORD
nonn,hard,more,nice
STATUS
approved