|
In a Boolean algebra, any Boolean function can be expressed in a canonical form using the dual concepts of minterms and maxterms. All logical functions are expressible in canonical form, both as a "sum of minterms" and as a "product of maxterms". This allows for greater analysis into the simplification of these functions, which is of great importance in the minimization of digital circuits. In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. ...
In mathematics, a finitary boolean function is a function of the form f : Bk → B, where B = {0, 1} is a boolean domain and where k is a nonnegative integer. ...
Generally, in mathematics, a canonical form is a function that is written in the most standard, conventional, and logical way. ...
A Boolean function expressed as a disjunction (OR) of minterms is commonly known as the "sum of products" (SoP), and its De Morgan dual is the "product of sums" (PoS), which is a function expressed as a conjunction (AND) of maxterms. OR logic gate. ...
note that demorgans laws are also a big part in circut design. ...
Minterms
For a boolean function of n variables x1,...xn, a product term in which each of the n variables appears once (either complemented, or uncomplemented) is called a minterm. Thus, a minterm is a logical expression of n variables consisting of only the logical conjunction operator and the complement operator. In mathematics, a finitary boolean function is a function of the form f : Bk → B, where B = {0, 1} is a boolean domain and where k is a nonnegative integer. ...
In Boolean logic, a product term is a conjunction of literals, where each literal is either a variable or its negation. ...
AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ...
For example, abc, ab'c and abc' are examples of minterms for a boolean function of the three variables a, b and c.
There are 2n minterms of n variables - this is true since a variable in the minterm expression can either be in the form of itself or its complement - two choices per n variables.
Indexing minterms In general, one assigns each minterm (ensuring the variables are written in the same order, usually alphabetic), an index based on the binary value of the minterm. A complemented term, like a' is considered a binary 0 and a noncomplemented term like a is considered a binary 1. For example, one would associate the number 6 with a b c'(1102), and write the minterm expression as m6. So m0 of three variables is a'b'c'(0002) and m7 would be a b c(1112).
Functional equivalence It is apparent that minterm n gives a true value for the n+1 th unique function input for that logical function. For example, minterm 5, a b' c, is true only when a and c both are true and b is false - the input where a = 1, b = 0, c = 1 results in 1.
If one is given a truth table of a logical function, it is possible to write the function as a "sum of products". This is a special form of disjunctive normal form, qv. For example, if given the truth table Truth tables are a type of mathematical table used in logic to determine whether an expression is true or whether an argument is valid. ...
In boolean logic, a disjunctive normal form (DNF) is a standardization (or normalization) of a logical formula which is a disjunction of conjunctive clauses. ...
a b f(a, b) 0 0 1 0 1 0 1 0 1 1 1 0 observing that the rows that have an output of 1 are the first and third, so we can write f as a sum of minterms m0 and m2.
If we wish to verify this:
- f(a,b) = m0 + m2 = (a'b')+(ab')
then the truth table for this function, by direct computation, will be the same.
Maxterms A maxterm is a logical expression of n variables consisting of only the logical disjunction operator and the complement operator. Maxterms are a dual of the minterm idea. Instead of using ANDs and complements, we use ORs and complements, and proceed similarly. OR logic gate. ...
For example, the following are maxterms:
- a+b'+c
- a'+b+c
There are again 2n maxterms of n variables - this is true since a variable in the maxterm expression can also be in the form of itself or its complement - two choices per n variables.
Dualization The complement of a minterm is the respective maxterm. This can be easily verified by using de Morgan's law. For example In logic, De Morgans laws (or De Morgans theorem) are the two rules of propositional logic, boolean algebra and set theory not (P and Q) = (not P) or (not Q) not (P or Q) = (not P) and (not Q) which allow us to move a negation over a...
- m1' = M1
- (a'b)' = a+b'
Indexing maxterms Indexing maxterms is done in the opposite way as with minterms. One assigns each maxterm an index based on the order of its complements (again, ensuring the variables are written in the same order, usually alphabetic). For example, one might assign M6 (Maxterm 6) to the maxterm a'+b'+c. Similarly M0 of these three variables could be a+b+c and M7 could be a'+b'+c'.
Functional equivalence It is apparent that maxterm n now gives a false value for the n+1 th unique function input for that logical function. For example, maxterm 5, a'+b+c', is false only when a and c both are true and b is false - the input where a = 1, b = 0, c = 1 results in 0.
If one is given a truth table of a logical function, it is possible to write the function as a "product of sums". This a special form of conjunctive normal form, q.v. For example, if given the truth table Truth tables are a type of mathematical table used in logic to determine whether an expression is true or whether an argument is valid. ...
In boolean logic, a formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals. ...
a b f(a, b) 0 0 1 0 1 0 1 0 1 1 1 0 observing that the rows that have an output of 0 are the second and fourth, so we can write f as a product of maxterms M1 and M3.
If we wish to verify this:
- f(a,b) = M1 M3 = (a+b')(a'+b')
then the truth table for this function, by direct computation, will be the same.
Non canonical PoS and SoP forms It is often the case that the canonical minterm form can be simplifyed to an equivelent SoP form. This simplified form would still consist of a sum of product terms. However, in the simplifyed form it is posible to have either less product terms, and/or product terms that contain less variables (=that are shorter). For example, the following 3-variable function: 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 1 1 0 0 1 1 1 1 Has the canonical minterm representation: f = a'bc + abc But it has an equivelent simplified form: f = bc In this trivial example it is obvious that bc = a'bc + abc. But the simplified form has both fewer product terms, and the term has fewer variables. The most simplified SoP representation of a function is referred to as a minimal SoP form.
In the similar manner, a canonical maxterm form can have a simplified PoS form.
A convinient method for finding the minimal Pos/Sop form of a functions with up to four variables is using a Karnaugh map. An example Karnaugh map The Karnaugh map, also known as a Veitch diagram (K-map or KV-map for short), is a tool to facilitate management of Boolean algebraic expressions. ...
The minimal PoS and SoP forms are very important for finding optimal implementations of boolean functions and minimizing logic circuits.
See also | 
Feeds |
Contact