This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) This article'stone or style may not reflect theencyclopedic tone used on Wikipedia. See Wikipedia'sguide to writing better articles for suggestions.(February 2009) (Learn how and when to remove this message) This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Canonical normal form" – news ·newspapers ·books ·scholar ·JSTOR(October 2010) (Learn how and when to remove this message) This articlepresents an incomplete view of the subject. (Learn how and when to remove this message)

InBoolean algebra, anyBoolean function can be expressed in thecanonical disjunctive normal form (CDNF),^[1]minterm canonical form, orSum of Products (SoP orSOP) as a disjunction (OR) of minterms. TheDe Morgan dual is thecanonical conjunctive normal form (CCNF),maxterm canonical form, orProduct of Sums (PoS orPOS) which is a conjunction (AND) of maxterms. These forms can be useful for the simplification of Boolean functions, which is of great importance in the optimization of Boolean formulas in general anddigital circuits in particular.

Othercanonical forms include the complete sum of prime implicants orBlake canonical form (and its dual), and thealgebraic normal form (also called Zhegalkin or Reed–Muller).

For aboolean function of${\displaystyle n}$ variables${\displaystyle x_1,\dots ,x_n}$, aminterm is aproduct term in which each of the${\displaystyle n}$ variables appearsexactly once (either in its complemented or uncomplemented form). Thus, aminterm is a logical expression ofn variables that employs only the complement operator and the conjunction operator (logical AND). A minterm gives a true value for just one combination of the input variables, the minimum nontrivial amount. For example,ab'c, is true only whena andc both are true andb is false—the input arrangement wherea = 1,b = 0,c = 1 results in 1.

There are 2ⁿ minterms ofn variables, since a variable in the minterm expression can be in either its direct or its complemented form—two choices per variable. Minterms are often numbered by a binary encoding of the complementation pattern of the variables, where the variables are written in a standard order, usually alphabetical. This convention assigns the value 1 to the direct form (${\displaystyle x_i}$) and 0 to the complemented form (${\displaystyle x_i^{\prime }}$); the minterm is then${\displaystyle \sum _{i=1}^n{2}^{i-1}\mathrm{value}(x_i)}$. For example, minterm${\displaystyle ab{c}^{\prime }}$ is numbered 110₂ = 6₁₀ and denoted${\displaystyle m_6}$.

Given thetruth table of a logical function, it is possible to write the function as a "sum of products" or "sum of minterms". This is a special form ofdisjunctive normal form. For example, if given the truth table for the arithmetic sum bitu of one bit position's logic of an adder circuit, as a function ofx andy from the addends and the carry in,ci:

Observing that the rows that have an output of 1 are the 2nd, 3rd, 5th, and 8th, we can writeu as a sum of minterms${\displaystyle m_1,m_2,m_4,}$ and${\displaystyle m_7}$. If we wish to verify this:${\displaystyle u(ci,x,y)=m_1+m_2+m_4+m_7=(c{i}^{\prime },x^{\prime },y)+(c{i}^{\prime },x,y^{\prime })+(ci,x^{\prime },y^{\prime })+(ci,x,y)}$ evaluated for all 8 combinations of the three variables will match the table.

For aboolean function ofn variables${\displaystyle x_1,\dots ,x_n}$, amaxterm is a sum term in which each of then variables appearsexactly once (either in its complemented or uncomplemented form). Thus, amaxterm is a logical expression ofn variables that employs only the complement operator and the disjunction operator (logical OR). Maxterms are a dual of the minterm idea, following the complementary symmetry ofDe Morgan's laws. Instead of using ANDs and complements, we use ORs and complements and proceed similarly. It is apparent that a maxterm gives afalse value for just one combination of the input variables, i.e. it is true at the maximal number of possibilities. For example, the maxterma′ +b +c′ is false only whena andc both are true andb is false—the input arrangement where a = 1, b = 0, c = 1 results in 0.

There are again 2ⁿ maxterms ofn variables, since a variable in the maxterm expression can also be in either its direct or its complemented form—two choices per variable. The numbering is chosen so that the complement of a minterm is the respective maxterm. That is, each maxterm is assigned an index based on the opposite conventional binary encoding used for minterms. The maxterm convention assigns the value 0 to the direct form${\displaystyle (x_i)}$ and 1 to the complemented form${\displaystyle (x_i^{\prime })}$. For example, we assign the index 6 to the maxterm${\displaystyle a^{\prime }+b^{\prime }+c}$ (110) and denote that maxterm asM₆. The complement${\displaystyle (a^{\prime }+b^{\prime }+c{)}^{\prime }}$ is the minterm${\displaystyle ab{c}^{\prime }=m_6}$, usingde Morgan's law.

If one is given atruth table of a logical function, it is possible to write the function as a "product of sums" or "product of maxterms". This is a special form ofconjunctive normal form. For example, if given the truth table for the carry-out bitco of one bit position's logic of an adder circuit, as a function ofx andy from the addends and the carry in,ci:

Observing that the rows that have an output of 0 are the 1st, 2nd, 3rd, and 5th, we can writeco as a product of maxterms${\displaystyle M_0,M_1,M_2}$ and${\displaystyle M_4}$. If we wish to verify this:

${\displaystyle co(ci,x,y)=M_0{M}_1{M}_2{M}_4=(ci+x+y)(ci+x+y^{\prime })(ci+x^{\prime }+y)(c{i}^{\prime }+x+y)}$

evaluated for all 8 combinations of the three variables will match the table.

It is often the case that the canonical minterm form is equivalent to a smaller SoP form. This smaller form would still consist of a sum of product terms, but have fewer product terms and/or product terms that contain fewer variables. For example, the following 3-variable function:

has the canonical minterm representation${\displaystyle f=a^{\prime }bc+abc}$, but it has an equivalent SoP form${\displaystyle f=bc}$. In this trivial example, it is obvious that${\displaystyle bc=a^{\prime }bc+abc}$, and the smaller form has both fewer product terms and fewer variables within each term. Theminimal SoP representations of a function according to this notion of "smallest" are referred to asminimal SoP forms. In general, there may be multiple minimal SoP forms, none clearly smaller or larger than another.^[2] In a similar manner, a canonical maxterm form can be reduced to various minimal PoS forms.

While this example was simplified by applying normal algebraic methods [${\displaystyle f=(a^{\prime }+a)bc}$], in less obvious cases a convenient method for finding minimal PoS/SoP forms of a function with up to four variables is using aKarnaugh map. TheQuine–McCluskey algorithm can solve slightly larger problems. The field oflogic optimization developed from the problem of finding optimal implementations of Boolean functions, such as minimal PoS and SoP forms.

The sample truth tables for minterms and maxterms above are sufficient to establish the canonical form for a single bit position in the addition of binary numbers, but are not sufficient to design the digital logic unless your inventory of gates includes AND and OR. Where performance is an issue (as in the Apollo Guidance Computer), the available parts are more likely to be NAND and NOR because of the complementing action inherent in transistor logic. The values are defined as voltage states, one near ground and one near the DC supply voltage V_cc, e.g. +5 VDC. If the higher voltage is defined as the 1 "true" value, a NOR gate is the simplest possible useful logical element.

Specifically, a 3-input NOR gate may consist of 3 bipolar junction transistors with their emitters all grounded, their collectors tied together and linked to V_cc through a load impedance. Each base is connected to an input signal, and the common collector point presents the output signal. Any input that is a 1 (high voltage) to its base shorts its transistor's emitter to its collector, causing current to flow through the load impedance, which brings the collector voltage (the output) very near to ground. That result is independent of the other inputs. Only when all 3 input signals are 0 (low voltage) do the emitter-collector impedances of all 3 transistors remain very high. Then very little current flows, and the voltage-divider effect with the load impedance imposes on the collector point a high voltage very near to V_cc.

The complementing property of these gate circuits may seem like a drawback when trying to implement a function in canonical form, but there is a compensating bonus: such a gate with only one input implements the complementing function, which is required frequently in digital logic.

This example assumes the Apollo parts inventory: 3-input NOR gates only, but the discussion is simplified by supposing that 4-input NOR gates are also available (in Apollo, those were compounded out of pairs of 3-input NORs).

A set of 8 NOR gates, if their inputs are all combinations of the direct and complement forms of the 3 input variablesci, x, andy, always produce minterms, never maxterms—that is, of the 8 gates required to process all combinations of 3 input variables, only one has the output value 1. That's because a NOR gate, despite its name, could better be viewed (using De Morgan's law) as the AND of the complements of its input signals.

The reason this is not a problem is the duality of minterms and maxterms, i.e. each maxterm is the complement of the like-indexed minterm, and vice versa.

In the minterm example above, we wrote${\displaystyle u(ci,x,y)=m_1+m_2+m_4+m_7}$ but to perform this with a 4-input NOR gate we need to restate it as a product of sums (PoS), where the sums are the opposite maxterms. That is,

${\displaystyle u(ci,x,y)=\mathrm{A}\mathrm{N}\mathrm{D}(M_0,M_3,M_5,M_6)=\mathrm{N}\mathrm{O}\mathrm{R}(m_0,m_3,m_5,m_6).}$

In the maxterm example above, we wrote${\displaystyle co(ci,x,y)=M_0{M}_1{M}_2{M}_4}$ but to perform this with a 4-input NOR gate we need to notice the equality to the NOR of the same minterms. That is,

${\displaystyle co(ci,x,y)=\mathrm{A}\mathrm{N}\mathrm{D}(M_0,M_1,M_2,M_4)=\mathrm{N}\mathrm{O}\mathrm{R}(m_0,m_1,m_2,m_4).}$

One might suppose that the work of designing an adder stage is now complete, but we haven't addressed the fact that all 3 of the input variables have to appear in both their direct and complement forms. There's no difficulty about the addendsx andy in this respect, because they are static throughout the addition and thus are normally held in latch circuits that routinely have both direct and complement outputs. (The simplest latch circuit made of NOR gates is a pair of gates cross-coupled to make a flip-flop: the output of each is wired as one of the inputs to the other.) There is also no need to create the complement form of the sumu. However, the carry out of one bit position must be passed as the carry into the next bit position in both direct and complement forms. The most straightforward way to do this is to passco through a 1-input NOR gate and label the outputco′, but that would add a gate delay in the worst possible place, slowing down the rippling of carries from right to left. An additional 4-input NOR gate building the canonical form ofco′ (out of the opposite minterms asco) solves this problem.

${\displaystyle c{o}^{\prime }(ci,x,y)=\mathrm{A}\mathrm{N}\mathrm{D}(M_3,M_5,M_6,M_7)=\mathrm{N}\mathrm{O}\mathrm{R}(m_3,m_5,m_6,m_7).}$

The trade-off to maintain full speed in this way includes an unexpected cost (in addition to having to use a bigger gate). If we'd just used that 1-input gate to complementco, there would have been no use for the minterm${\displaystyle m_7}$, and the gate that generated it could have been eliminated. Nevertheless, it is still a good trade.

Now we could have implemented those functions exactly according to their SoP and PoS canonical forms, by turning NOR gates into the functions specified. A NOR gate is made into an OR gate by passing its output through a 1-input NOR gate; and it is made into an AND gate by passing each of its inputs through a 1-input NOR gate. However, this approach not only increases the number of gates used, but also doubles the number of gate delays processing the signals, cutting the processing speed in half. Consequently, whenever performance is vital, going beyond canonical forms and doing the Boolean algebra to make the unenhanced NOR gates do the job is well worthwhile.

We have now seen how the minterm/maxterm tools can be used to design an adder stage in canonical form with the addition of some Boolean algebra, costing just 2 gate delays for each of the outputs. That's the "top-down" way to design the digital circuit for this function, but is it the best way? The discussion has focused on identifying "fastest" as "best," and the augmented canonical form meets that criterion flawlessly, but sometimes other factors predominate. The designer may have a primary goal of minimizing the number of gates, and/or of minimizing the fanouts of signals to other gates since big fanouts reduce resilience to a degraded power supply or other environmental factors. In such a case, a designer may develop the canonical-form design as a baseline, then try a bottom-up development, and finally compare the results.

The bottom-up development involves noticing thatu = ci XOR (x XORy), where XOR means eXclusive OR [true when either input is true but not when both are true], and thatco =ci x +x y +y ci. One such development takes twelve NOR gates in all: six 2-input gates and two 1-input gates to produceu in 5 gate delays, plus three 2-input gates and one 3-input gate to produceco′ in 2 gate delays. The canonical baseline took eight 3-input NOR gates plus three 4-input NOR gates to produceu, co andco′ in 2 gate delays. If the circuit inventory actually includes 4-input NOR gates, the top-down canonical design looks like a winner in both gate count and speed. But if (contrary to our convenient supposition) the circuits are actually 3-input NOR gates, of which two are required for each 4-input NOR function, then the canonical design takes 14 gates compared to 12 for the bottom-up approach, but still produces the sum digitu considerably faster. The fanout comparison is tabulated as:

The description of the bottom-up development mentionsco′ as an output but notco. Does that design simply never need the direct form of the carry out? Well, yes and no. At each stage, the calculation ofco′ depends only onci′,x′ andy′, which means that the carry propagation ripples along the bit positions just as fast as in the canonical design without ever developingco. The calculation ofu, which does requireci to be made fromci′ by a 1-input NOR, is slower but for any word length the design only pays that penalty once (when the leftmost sum digit is developed). That's because those calculations overlap, each in what amounts to its own little pipeline without affecting when the next bit position's sum bit can be calculated. And, to be sure, theco′ out of the leftmost bit position will probably have to be complemented as part of the logic determining whether the addition overflowed. But using 3-input NOR gates, the bottom-up design is very nearly as fast for doing parallel addition on a non-trivial word length, cuts down on the gate count, and uses lower fanouts ... so it wins if gate count and/or fanout are paramount!

We'll leave the exact circuitry of the bottom-up design of which all these statements are true as an exercise for the interested reader, assisted by one more algebraic formula:u =ci(x XORy) +ci′(x XORy)′]′. Decoupling the carry propagation from the sum formation in this way is what elevates the performance of acarry-lookahead adder over that of aripple carry adder.

One application of Boolean algebra is digital circuit design, with one goal to minimize the number of gates and another to minimize the settling time.

There are sixteen possible functions of two variables, but in digital logic hardware, the simplest gate circuits implement only four of them:conjunction (AND),disjunction (inclusive OR), and the respective complements of those (NAND and NOR).

Most gate circuits accept more than 2 input variables; for example, the spaceborneApollo Guidance Computer, which pioneered the application of integrated circuits in the 1960s, was built with only one type of gate, a 3-input NOR, whose output is true only when all 3 inputs are false.^{[3][page needed][4]}

• List of Boolean algebra topics

• Bender, Edward A.; Williamson, S. Gill (2005).A Short Course in Discrete Mathematics. Mineola, NY: Dover Publications, Inc.ISBN 0-486-43946-1.
  The authors demonstrate a proof that any Boolean (logic) function can be expressed in either disjunctive or conjunctive normal form (cf pages 5–6); the proof simply proceeds by creating all 2^N rows ofN Boolean variables and demonstrates that each row ("minterm" or "maxterm") has a unique Boolean expression. Any Boolean function of theN variables can be derived from a composite of the rows whose minterm or maxterm are logical 1s ("trues")
• McCluskey, E. J. (1965).Introduction to the Theory of Switching Circuits. NY: McGraw–Hill Book Company. p. 78.LCCN 65-17394.Canonical expressions are defined and described
• Hill, Fredrick J.; Peterson, Gerald R. (1974).Introduction to Switching Theory and Logical Design (2nd ed.). NY: John Wiley & Sons. p. 101.ISBN 0-471-39882-9.Minterm and maxterm designation of functions

The WikibookElectronics has a page on the topic of:Boolean Algebra

• Boole, George (1848)."The Calculus of Logic".Cambridge and Dublin Mathematical Journal.III. Translated by Wilkins, David R.:183–198.

• Boolean algebra
• Logic
• Algebraic logic

• Articles with short description
• Short description is different from Wikidata
• Wikipedia articles with style issues from February 2009
• All articles with style issues
• Articles needing additional references from October 2010
• All articles needing additional references
• Articles with multiple maintenance issues
• Use dmy dates from April 2020
• Wikipedia articles needing page number citations from December 2019
• Articles with example code