This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (February 2009) (Learn how and when to remove this message) This article needs additional citations for verification. Please help improve this article by adding 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 article presents an incomplete view of the subject. (Learn how and when to remove this message)

In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form (CDNF),^[1] minterm canonical form, or Sum of Products (SoP or SOP) as a disjunction (OR) of minterms. The De Morgan dual is the canonical conjunctive normal form (CCNF), maxterm canonical form, or Product of Sums (PoS or POS) 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 and digital circuits in particular.

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

Minterms

For a boolean function of ${\displaystyle n}$ variables ${\displaystyle {x_{1},\dots ,x_{n}}}$, a minterm is a product term in which each of the ${\displaystyle n}$ variables appears exactly once (either in its complemented or uncomplemented form). Thus, a minterm is a logical expression of n 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, a b' c, is true only when a and c both are true and b is false—the input arrangement where a = 1, b = 0, c = 1 results in 1.

Indexing minterms

There are 2ⁿ minterms of n 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}}$); the minterm is then ${\displaystyle \sum \limits _{i=1}^{n}2^{i-1}\operatorname {value} (x_{i})}$. For example, minterm ${\displaystyle abc'}$ is numbered 110₂ = 6₁₀ and denoted ${\displaystyle m_{6}}$.

Minterm canonical form

Given the truth 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 of disjunctive normal form. For example, if given the truth table for the arithmetic sum bit u of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci:

ci	x	y	u(ci,x,y)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Observing that the rows that have an output of 1 are the 2nd, 3rd, 5th, and 8th, we can write u 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}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)}$ evaluated for all 8 combinations of the three variables will match the table.

Maxterms

For a boolean function of n variables ${\displaystyle {x_{1},\dots ,x_{n}}}$, a maxterm is a sum term in which each of the n variables appears exactly once (either in its complemented or uncomplemented form). Thus, a maxterm is a logical expression of n 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 of De Morgan's laws. Instead of using ANDs and complements, we use ORs and complements and proceed similarly. It is apparent that a maxterm gives a false value for just one combination of the input variables, i.e. it is true at the maximal number of possibilities. For example, the maxterm a′ + b + c′ is false only when a and c both are true and b is false—the input arrangement where a = 1, b = 0, c = 1 results in 0.

Indexing maxterms

There are again 2ⁿ maxterms of n 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})}$. For example, we assign the index 6 to the maxterm ${\displaystyle a'+b'+c}$ (110) and denote that maxterm as M₆. The complement ${\displaystyle (a'+b'+c)'}$ is the minterm ${\displaystyle abc'=m_{6}}$, using de Morgan's law.

Maxterm canonical form

If one is given a truth 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 of conjunctive normal form. For example, if given the truth table for the carry-out bit co of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci:

ci	x	y	co(ci,x,y)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Observing that the rows that have an output of 0 are the 1st, 2nd, 3rd, and 5th, we can write co 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')(ci+x'+y)(ci'+x+y)}$

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

Minimal PoS and SoP forms

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:

Zdroj:https://en.wikipedia.org?pojem=Canonical_normal_form
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---



---

www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk

---

a	b	c	f(a,b,c)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0