

A003039


Maximal number of prime implicants of a Boolean function of n variables.
(Formerly M1596)


3




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), 324 [ 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

Table of n, a(n) for n=1..6.
B. Dunham and R. Fridshal, The problem of simplifying logical expressions, Journal of Symbolic Logic, 24 (1959), 1719.
M. M. Gadzhiev, Maximal length of the reduced disjunctive normal form for Boolean functions with five and six variables, Diskretnyi Analiz (Novosibirsk), (1971), 324 [ 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), 324 [ Computing Reviews #23,815, Sep. 1972 ]. [Annotated scanned copy of abstract]
Index entries for sequences related to Boolean functions


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
Adjacent sequences: A003036 A003037 A003038 * A003040 A003041 A003042


KEYWORD

nonn,hard,more,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



