Content deleted Content added
Pollinosisss (talk | contribs) No edit summary |
→Complexity?: new section |
||
Line 84:
Which value is correct then? --[[User:CiaPan|CiaPan]] 06:50, 13 September 2007 (UTC)
== Complexity? ==
If ''prime implicant'' refers to an irreducible product of sums term, and any boolean function of ''n'' variables can be written in less than 2<sup>''n''</sup> POS terms, then then the upper bound of prime implicants is less than 2<sup>''n''</sup>, since the number of reduced terms is always less than or equal to the number of outputs of a boolean function(which has 2<sup>''n''</sup> outputs). This means that either the complexity section of the article is either using incorrect terms (in which case ''implicants'' is meant, rather than ''prime implicants''), is grossly inaccurate, or should be clarified.
| |||