From WikiChip
Difference between revisions of "boolean algebra"

Line 205: Line 205:
  
 
===Sum of Products (SoP) ===
 
===Sum of Products (SoP) ===
−
:A '''[[minterm]]''' is the Boolean product (ANDing) of <math>n</math> variables and contains all <math>n</math> variables of the function just once, in either normal or complemented form. For example, for the function <math>f(a, b)</math> with two variables, we can have the following minterms: <math>a \land b</math>, <math>a  \land  \bar b</math>, <math>\bar a  \land  b</math>, and <math>\overline{a  \land  b}</math>. If the value assigned to a variable is 0, the variable is complemented, conversely a variable remains uncomplemented if the value assigned to it is 1. Consider the table to the right, since in the first row, the variables <math>a</math>, <math>b</math>, and <math>c</math> are all <math>0</math>, the minterms for them is <math>\bar a \land \bar b \land \bar c</math>
+
A '''[[minterm]]''' is the Boolean product (ANDing) of <math>n</math> variables and contains all <math>n</math> variables of the function just once, in either normal or complemented form. For example, for the function <math>f(a, b)</math> with two variables, we can have the following minterms: <math>a \land b</math>, <math>a  \land  \bar b</math>, <math>\bar a  \land  b</math>, and <math>\overline{a  \land  b}</math>. If the value assigned to a variable is 0, the variable is complemented, conversely a variable remains uncomplemented if the value assigned to it is 1. Consider the table to the right, since in the first row, the variables <math>a</math>, <math>b</math>, and <math>c</math> are all <math>0</math>, the minterms for them is <math>\bar a \land \bar b \land \bar c</math>
  
−
The '''[[sum of minterms]]''' (also called '''canonical sum of products''', '''minterm expansion''', and '''disjunctive normal form''') ('''SoP''' or '''CDNF''') is a Boolean expression in which each term contains all the variables, either in normal or complemented form. For example, consider the following Boolean functions.
+
A '''[[sum term]]''' is the Boolean sum (ORing) of  variables as a subset of the possible variables or their complements. For example, for the function <math>f(a,b,c)</math>, the following are a few possible sum terms: <math>\bar c</math>, <math>a \lor b</math>, and <math>\bar a \lor b</math>.
−
:<math>f(a,b,c, d) = a \land (b \lor c \lor d)</math>
+
 
−
We can express that function in SoP form by expanding all the terms.
+
The '''[[sum of minterms]]''' also called '''Sum of Product''' ('''SoP'''), '''canonical sum of products''', '''minterm expansion''', and '''canonical disjunctive normal form''' ('''CDNF''') is a Boolean expression in which each term contains all the variables, either in normal or complemented form as sum of all the minterms. For example, consider the following Boolean functions.
−
:<math>f(a,b,c, d) = (a \land b) \lor (a \land c) \lor (a \land d)</math>
+
:<math>f(a,b,c, d) = a(b+c+d)</math>
−
Or
+
We can express that function in SoP form as follows.
−
:<math>f(a,b,c,d) = ab+ac+ad</math>
+
:<math>f(a,b,c, d) = (abcd) + (abc \bar d) + (ab \bar c d) + (ab \bar c \bar d) + (a \bar bcd) + (a \bar b c \bar d) + (a \bar b \bar c d)</math>
  
 
{| class="wikitable" style="float: right; margin-left: 20px;"
 
{| class="wikitable" style="float: right; margin-left: 20px;"
−
! colspan="7" | Sum of Product Examples
+
! colspan="7" | Sum of Product Example
 
|-
 
|-
 
! colspan="7" | Function
 
! colspan="7" | Function
Line 253: Line 253:
 
This function can now be more concisely written a in the following way:
 
This function can now be more concisely written a in the following way:
  
−
:<math>f(a,b,c) = \sum(\mbox{list of 1-minterm indices})</math>
+
:<math>f(a,b,c) = \sum m(\mbox{list of 1-minterm indices})</math>
  
 
I.e.
 
I.e.
  
−
:<math>f(a,b,c) = m_3 + m_4 + m_5 + m_6 + m_7 = \sum(3,4,5,6,7)</math>
+
:<math>f(a,b,c) = m_3 + m_4 + m_5 + m_6 + m_7 = \sum m(3,4,5,6,7)</math>
  
 
Likewise, the inverse of the function can be expressed as the '''sum of 0-minterms''':
 
Likewise, the inverse of the function can be expressed as the '''sum of 0-minterms''':
Line 265: Line 265:
 
   f^\prime(a,b,c)  &= \bar a \bar b \bar c + \bar a \bar b c + \bar a b \bar c \\
 
   f^\prime(a,b,c)  &= \bar a \bar b \bar c + \bar a \bar b c + \bar a b \bar c \\
 
                     &= m_0 + m_1 + m_2 \\
 
                     &= m_0 + m_1 + m_2 \\
−
                     &= \sum(0,1,2) \\
+
                     &= \sum m(0,1,2) \\
 
\end{align}
 
\end{align}
 
</math>
 
</math>
Line 271: Line 271:
  
 
===Product of Sum (PoS) ===
 
===Product of Sum (PoS) ===
−
:A '''[[maxterm]]''' is the Boolean sum (ORing) of <math>n</math> variables and contains all <math>n</math> variables of the function just once, in either normal or complemented form. For example, for the function <math>f(a, b)</math> with two variables, we can have the following maxterms: <math>a \lor b</math>, <math>a \lor \bar b</math>, <math>\bar a \lor b</math>, and <math>\bar a \lor \bar b</math>.
+
{| class="wikitable" style="float: right; margin-left: 20px;"
 +
! colspan="7" | Sum of Product Example
 +
|-
 +
! colspan="7" | Function
 +
|-
 +
| colspan="7" | <math>f(a,b,c) = a \lor (b \land c)</math>
 +
|-
 +
! a !! b !! c !! minterms !! notation !! <math>f</math> !! <math>f^\prime</math>
 +
|-
 +
| 0 || 0 || 0 || <math>a \lor b \lor c</math> || <math>M_0</math> || 0 || 1
 +
|-
 +
| 0 || 0 || 1 || <math>a \lor b \lor \bar c</math> || <math>M_1</math> || 0 || 1
 +
|-
 +
| 0 || 1 || 0 || <math>a \lor \bar b \lor c</math> || <math>M_2</math> || 0 || 1
 +
|-
 +
| 0 || 1 || 1 || <math>a \lor \bar b \lor \bar c</math> || <math>M_3</math> || 1 || 0
 +
|-
 +
| 1 || 0 || 0 || <math>\bar a \lor b \lor c</math> || <math>M_4</math> || 1 || 0
 +
|-
 +
| 1 || 0 || 1 || <math>\bar a \lor b \lor \bar c</math> || <math>M_5</math> || 1 || 0
 +
|-
 +
| 1 || 1 || 0 || <math>\bar a \lor \bar b \lor c</math> || <math>M_6</math> || 1 || 0
 +
|-
 +
| 1 || 1 || 1 || <math>\bar a \lor \bar b \lor \bar c</math> || <math>M_7</math> || 1 || 0
 +
|}
 +
A '''[[maxterm]]''' is the Boolean sum (ORing) of <math>n</math> variables and contains all <math>n</math> variables of the function just once, in either normal or complemented form. For example, for the function <math>f(a, b)</math> with two variables, we can have the following maxterms: <math>a \lor b</math>, <math>a \lor \bar b</math>, <math>\bar a \lor b</math>, and <math>\bar a \lor \bar b</math>.
 +
 
 +
A '''[[product term]]''' is the Boolean product (ANDing) of variables as a subset of the possible variables or their complements. For example, for function <math>f(a,b,c)</math>, the following are possible product terms: <math>\bar c</math>, <math>a \land \bar b</math>, and <math>c \land a</math>.
 +
 
 +
The '''[[sum of maxterms]]''' also called '''Product of Sum''' ('''PoS'''), '''canonical sum of products''', '''maxterm expansion''', '''canonical conjunctive normal form''' ('''CCNF''') is a Boolean expression in which each term contains all the variables, either in normal or complemented form as the sum of all the maxterms.
 +
 
 +
:<math>f(a,b,c, d) = a(b+c+d)</math>
 +
We can express that function in PoS form as follows.
 +
:<math>
 +
\begin{align}
 +
f(a,b,c, d) = (a+b+c+d)\cdot(a+b+c+\bar d)\cdot(a+b+\bar c+d)\cdot(a+b+\bar c+\bar d)\cdot \\
 +
      (a+\bar b+c+d)\cdot(a+\bar b+c+\bar d)\cdot(a+\bar b+\bar c+d)\cdot(a+\bar b+\bar c+\bar d)\cdot \\
 +
      (\bar a+b+c+d)
 +
\end{align}
 +
</math>
 +
 
 +
The maxterms for which the function produces a <math>1</math> are called '''1-maxterms'''. Likewise, maxterms for which the function produces a <math>0</math> are called '''0-maxterms'''. Any Boolean function can be expressed as product of its 0-maxterms. For example, consider the following function:
 +
 
 +
:<math>f(a,b,c) = a+(bc)</math>
  
−
:A '''[[sum term]]''' is the Boolean sum (ORing) of  variables as a subset of the possible variables or their complements. For example, for the function <math>f(a,b,c)</math>, the following are a few possible sum terms: <math>\bar c</math>, <math>a \lor b</math>, and <math>\bar a \lor b</math>.
+
The truth table for it is on the right. We can express this function as '''product of 0-maxterms''':
 +
 
 +
:<math>f(a,b,c) = (a+b+c)\cdot(a+b+\bar c)\cdot(a+\bar b+c)</math>
 +
 
 +
We can replace the individual minterms with their respective index which is also shown in the table.
 +
 
 +
:<math>f(a,b,c) = M_0 + M_1 + M_2</math>
 +
 
 +
This function can now be more concisely written a in the following way:
 +
 
 +
:<math>f(a,b,c) = \prod M(\mbox{list of 1-minterm indices})</math>
 +
 
 +
I.e.
 +
 
 +
:<math>f(a,b,c) = M_0 + M_1 + M_2 = \prod M(0,1,2)</math>
 +
 
 +
Likewise, the inverse of the function can be expressed as the '''product of 0-maxterms''':
 +
 
 +
::<math>
 +
\begin{align}
 +
  f^\prime(a,b,c)  &= (a+\bar b+\bar c)\cdot(\bar a+b+c)\cdot(\bar a +b+\bar c)\cdot(\bar a+\bar b+c)\cdot(\bar a+\bar b+\bar c) \\
 +
                    &= M_3+M_4+M_5+M_6+M_7 \\
 +
                    &= \prod M(3,4,5,6,7)
 +
\end{align}
 +
</math>
  
−
:A '''[[product term]]''' is the Boolean product (ANDing) of variables as a subset of the possible variables or their complements. For example, for function <math>f(a,b,c)</math>, the following are possible product terms: <math>\bar c</math>, <math>a \land \bar b</math>, and <math>c \land a</math>.
 
  
 
== Minimization ==
 
== Minimization ==

Revision as of 10:17, 2 December 2015

Boolean algebra (or less commonly symbolic logic) is a branch algebra that deals with only two logic values - 0 (corresponding to false) and 1 (corresponding to true).

Today, Boolean algebra is the primary mathematical tool used in designing modern digital systems. Switching functions are described using Boolean algebra since they deal with two discrete states - ON and OFF (or 1 and 0). Those functions are in turn implemented via transistors which act as switches, a natural implementation for representing Boolean algebra operations. Once primitive Boolean operation circuits such as NOT, AND, and OR gates are implemented, any conceivable system of logic can be implemented using them like Lego pieces.

Variables

Main articles: Boolean Variables and boolean data type

Boolean algebra uses variables just like normal algebra. Those variables can only have one of two values - either a 0 or a 1. Variable are commonly represented as a single alphabet letter. While there is no one acceptable convention, a it's not uncommon to see letters such as Equation upper A comma upper B comma and upper C used for inputs and Equation upper P comma upper Q comma upper R comma and upper Z for output. That's also the convention used on WikiChip. Sometimes it's desired to represent the negated (opposite) value of a variable, that's often done with a bar or a tick (prime) above or next to the letter, for example Equation upper A overbar or Equation normal not-sign upper B although other notations exist. Equation upper A overbar is read "not A", regardless of notation.

Operations & Truth tables

Main articles: Boolean Operations and truth table

Boolean algebra has a set of operations that can be performed on Boolean values, those operations are conveniently enough called binary operations. The three common Boolean operators are AND, OR, and NOT. Understanding those operators can better be done by examining their behavior via tool called a truth table. truth tables is a table that lists all possible input values and their respective output values. Truth tables can be said to be the unique signature of a specific Boolean function. Truth tables are an excellent way of seeing the relationships between input values and given Boolean expressions. While there may be many ways to realize or construct a Boolean function to represent a specific relation, they all share the very same truth table.

AND operator

Main article: conjunction
Inputs Outputs
A B Q
0 0 0
0 1 0
1 0 0
1 1 1

The Boolean operator AND is usually represented by either Equation logical-and , Equation dot , or no symbol at all: for example " Equation upper A logical-and upper B ", " Equation upper A dot upper B ", and " Equation upper A upper B " are all equivalent and are read "A AND B". The behavior of this operator is shown in the truth table on the right. The result of "A AND B" is true if both A and B are true; otherwise the result is false. This expression is also called a Boolean product.

For example, suppose we have the function Equation f left-parenthesis a comma b comma c right-parenthesis equals left-parenthesis a logical-and b right-parenthesis logical-and c

Equation StartLayout 1st Row 1st Column upper Q 2nd Column equals f left-parenthesis 1 comma 0 comma 1 right-parenthesis 2nd Row 1st Column Blank 2nd Column equals left-parenthesis 1 logical-and 0 right-parenthesis logical-and 1 3rd Row 1st Column Blank 2nd Column equals 0 logical-and 1 4th Row 1st Column Blank 2nd Column equals 0 Subscript 2 EndLayout

Or

Equation StartLayout 1st Row 1st Column upper Q 2nd Column equals f left-parenthesis 1 comma 1 comma 1 right-parenthesis 2nd Row 1st Column Blank 2nd Column equals left-parenthesis 1 logical-and 1 right-parenthesis logical-and 1 3rd Row 1st Column Blank 2nd Column equals 1 logical-and 1 4th Row 1st Column Blank 2nd Column equals 1 Subscript 2 EndLayout

OR operator

Main article: disjunction
Inputs Outputs
A B Q
0 0 0
0 1 1
1 0 1
1 1 1

The Boolean operator OR is usually represented by Equation logical-or or Equation plus operators. For example " Equation upper A logical-or upper B " and " Equation upper A plus upper B ". The expression Equation upper A plus upper B is read "A or B". The result of "A OR B" is true if either A is true or B is true; otherwise the result is false. This expression is also called a Boolean sum.

For example, suppose we have the function Equation f left-parenthesis a comma b comma c right-parenthesis equals left-parenthesis a logical-or b right-parenthesis logical-or c

Equation StartLayout 1st Row 1st Column upper Q 2nd Column equals f left-parenthesis 1 comma 0 comma 1 right-parenthesis 2nd Row 1st Column Blank 2nd Column equals left-parenthesis 1 logical-or 0 right-parenthesis logical-or 1 3rd Row 1st Column Blank 2nd Column equals 1 logical-or 1 4th Row 1st Column Blank 2nd Column equals 1 Subscript 2 EndLayout

Or

Equation StartLayout 1st Row 1st Column upper Q 2nd Column equals f left-parenthesis 0 comma 0 comma 1 right-parenthesis 2nd Row 1st Column Blank 2nd Column equals left-parenthesis 0 logical-or 0 right-parenthesis logical-or 1 3rd Row 1st Column Blank 2nd Column equals 0 logical-or 1 4th Row 1st Column Blank 2nd Column equals 1 Subscript 2 EndLayout

NOT operator

Main article: negation
Inputs Outputs
A Q
0 1
1 0

The Boolean operator NOT is represented by many notations, the three most popular ones are " Equation normal not-sign upper A ", " Equation upper A overbar ", and " Equation upper A prime ". Note that unlike the AND and OR operators, the NOT operator is a unary operator and is thus drawn above or on the side of the variable. The expression Equation upper A overbar is read "not A". The truth table for the NOT operator is shown on the right. The result of the NOT operator is true if A is false, otherwise the result is true. This expression is called a Boolean complement.

For example, suppose we have the function Equation f left-parenthesis a right-parenthesis equals a overbar

Equation StartLayout 1st Row 1st Column upper Q 2nd Column equals f left-parenthesis 1 right-parenthesis 2nd Row 1st Column Blank 2nd Column equals ModifyingAbove 1 With bar 3rd Row 1st Column Blank 2nd Column equals 0 Subscript 2 EndLayout

Or

Equation StartLayout 1st Row 1st Column upper Q 2nd Column equals f left-parenthesis 0 right-parenthesis 2nd Row 1st Column Blank 2nd Column equals ModifyingAbove 0 With bar 3rd Row 1st Column Blank 2nd Column equals 1 Subscript 2 EndLayout

Order of operations

Main article: Order of Operations

So far we've made it simple by explicitly using parenthesis in all of our examples to indicate a certain part of the expression is evaluated before another part. The order of operations of a Boolean expression is very important to obtain correct result. For example consider the function Equation f left-parenthesis a comma b comma c right-parenthesis equals a logical-and b logical-or c for input Equation f left-parenthesis 0 comma 0 comma 1 right-parenthesis . Does it mean Equation left-parenthesis 0 logical-and 0 right-parenthesis logical-or 1 equals left-parenthesis 0 right-parenthesis logical-or 1 equals 1 ? or does it mean Equation 0 logical-and left-parenthesis 0 logical-or 1 right-parenthesis equals 0 logical-and left-parenthesis 1 right-parenthesis equals 0 ? Same expression, different results. It turns out the the correct order is Equation left-parenthesis a logical-and b right-parenthesis logical-or c (and Equation f left-parenthesis 0 comma 0 comma 1 right-parenthesis equals 1 ). In Boolean expressions, the NOT operator has the highest precedence, followed by AND, then OR.

For example,

Equation f left-parenthesis a comma b comma c right-parenthesis equals upper A logical-and upper B overbar logical-or upper A logical-and upper C overbar logical-or upper A logical-and upper B logical-and upper C equals left-parenthesis left-parenthesis upper A logical-and left-parenthesis upper B overbar right-parenthesis right-parenthesis logical-or left-parenthesis upper A logical-and left-parenthesis upper C overbar right-parenthesis right-parenthesis logical-or left-parenthesis left-parenthesis upper A logical-and upper B right-parenthesis logical-and upper C right-parenthesis right-parenthesis

and

Equation f left-parenthesis a comma b right-parenthesis equals upper A overbar logical-or upper B logical-and upper A equals left-parenthesis left-parenthesis upper A overbar right-parenthesis logical-or left-parenthesis upper B logical-and upper A right-parenthesis right-parenthesis

Axioms

Main article: Boolean Algebra Axioms

Boolean algebra is govern by a set of special axioms that say what kind of Boolean expression manipulations can be done. They are called axioms because they not things that have to be proven but rather part of the definition of Boolean algebra. Many of those laws are common to both Boolean algebra and ordinary algebra. Using those laws, equations can be converted into different forms. One particular transformation known as minimization plays a crucial role in the design of logic circuits. One last thing to note before we get to the actual laws is that Boolean algebra identities come in pairs. This is known as duality principle and it is covered in much more detail later on.

Axiom AND form OR form
Identity Axiom Equation a logical-and 1 equals a Equation a logical-or 0 equals a
Inverse Axiom Equation a logical-and a overbar equals 0 Equation a logical-or a overbar equals 1
Commutative Axiom Equation a logical-and b equals b logical-and a Equation a logical-or b equals b logical-or a
Associative Axiom Equation left-parenthesis a logical-and b right-parenthesis logical-and c equals a logical-and left-parenthesis b logical-and c right-parenthesis Equation left-parenthesis a logical-or b right-parenthesis logical-or c equals a logical-or left-parenthesis b logical-or c right-parenthesis
Distributive Axiom Equation a logical-or left-parenthesis b logical-and c right-parenthesis equals left-parenthesis a logical-or b right-parenthesis logical-and left-parenthesis a logical-and c right-parenthesis Equation a logical-and left-parenthesis b logical-or c right-parenthesis equals left-parenthesis a logical-and b right-parenthesis logical-or left-parenthesis a logical-or c right-parenthesis


In addition to those five axioms, there are a number of other handful laws. Those laws can be proven using the axioms we've introduced above.

Law AND form OR form
Complement Law Equation ModifyingAbove 1 With bar equals 0 Equation ModifyingAbove 0 With bar equals 1
Dominance Law Equation a logical-and 0 equals 0 Equation a logical-or 1 equals 1
Idempotent Law Equation a logical-and a equals a Equation a logical-or a equals a
Absorption Law Equation a logical-and left-parenthesis a logical-or b right-parenthesis equals a Equation a logical-or left-parenthesis a logical-and b right-parenthesis equals a
DeMorgan's Law Equation ModifyingAbove left-parenthesis a logical-and b right-parenthesis With bar equals a overbar logical-or b overbar Equation ModifyingAbove left-parenthesis a logical-or b right-parenthesis With bar equals a overbar logical-and b overbar
Involution Law Equation ModifyingAbove left-parenthesis a overbar right-parenthesis With bar equals a

It's interesting to note that it's easy to see the divergence between Boolean algebra and ordinary algebra from those laws. For example consider Equation 1 plus 1 . From Dominance Law we know the answer is Equation 1 . This is clearly not true for ordinary algebra where Equation 1 plus 1 equals 2 . Likewise from the Absorption Law we know that Equation 1 plus left-parenthesis 1 dot 1 right-parenthesis equals 1 while in ordinary algebra this is not true either.

Axioms explanation

The Identity Axiom simply states that any expression ANDed with 1 or ORed with 0 results in the original expression. Identity elements or simply identities are elements that when used with their appropriate operator leave the original element unchanged. In the case of Boolean algebra, the identity element for AND is 1 and 0 for OR.

Example:

Equation StartLayout 1st Row 1st Column f left-parenthesis a right-parenthesis 2nd Column equals a logical-and 1 logical-or 0 2nd Row 1st Column Blank 2nd Column equals a logical-or 0 3rd Column By Identity Axiom 3rd Row 1st Column Blank 2nd Column equals a 3rd Column By Identity Axiom EndLayout

The Inverse Axiom simply states that when you AND or OR an expression with its complement results in the identity element for that operation.

Example:

Equation StartLayout 1st Row 1st Column f left-parenthesis a comma b right-parenthesis 2nd Column equals left-parenthesis a logical-and a overbar right-parenthesis logical-or ModifyingAbove left-parenthesis b logical-and b overbar right-parenthesis With bar 2nd Row 1st Column Blank 2nd Column equals 0 logical-or ModifyingAbove left-parenthesis b logical-and b overbar right-parenthesis With bar 3rd Column By Inverse Axiom 3rd Row 1st Column Blank 2nd Column equals 0 logical-or ModifyingAbove 0 With bar 3rd Column By Inverse Axiom 4th Row 1st Column Blank 2nd Column equals 1 3rd Column By Inverse Axiom EndLayout

The Commutative Axiom states that individual elements in an expressions can be reordered without affecting the meaning of the expression. For example Equation a logical-and b logical-and c equals c logical-and a logical-and b .


The Associative Axiom states that individual elements in an expression can be regrouped without affecting the meaning of the expression. For example Equation left-parenthesis a logical-and b right-parenthesis logical-and left-parenthesis c logical-and d right-parenthesis equals a logical-and left-parenthesis b logical-and c right-parenthesis logical-and d . Simply put, it makes no difference in what order you group the expressions when ANDing or ORing several expressions together.


The Distributive Axiom states that ANDing distributes over over ORing. That is, ORing several expressions and ANDing the result is equaivilent to ANDing the result with a each of the individual expressions then ORing the product. Often times the Distributive Axiom is applied in reverse in a similar way to factoring in ordinary algebra. For example, given Equation left-parenthesis a logical-and b right-parenthesis logical-or left-parenthesis a logical-and c right-parenthesis , the Equation a expression can be factored out to Equation a logical-and left-parenthesis b logical-or c right-parenthesis

Canonical Forms

a b c minterms notation
0 0 0 Equation a overbar logical-and b overbar logical-and c overbar Equation m 0
0 0 1 Equation a overbar logical-and b overbar logical-and c Equation m 1
0 1 0 Equation a overbar logical-and b logical-and c overbar Equation m 2
0 1 1 Equation a overbar logical-and b logical-and c Equation m 3
1 0 0 Equation a logical-and b overbar logical-and c overbar Equation m 4
1 0 1 Equation a logical-and b overbar logical-and c Equation m 5
1 1 0 Equation a logical-and b logical-and c overbar Equation m 6
1 1 1 Equation a logical-and b logical-and c Equation m 7

Earlier we've covered truth tables which are like signatures; there are many ways to represent the same logic, however it will always result in the very same truth table. When two Boolean functions result in the same exact truth table, the two functions are said to be logically equivalent. The different representations of a truth table are known as forms. In an attempt to eliminate confusion, a few forms were were chosen to be canonical or standard forms. Before we describe those forms we need to go over a few terms.

Sum of Products (SoP)

A minterm is the Boolean product (ANDing) of Equation n variables and contains all Equation n variables of the function just once, in either normal or complemented form. For example, for the function Equation f left-parenthesis a comma b right-parenthesis with two variables, we can have the following minterms: Equation a logical-and b , Equation a logical-and b overbar , Equation a overbar logical-and b , and Equation ModifyingAbove a logical-and b With bar . If the value assigned to a variable is 0, the variable is complemented, conversely a variable remains uncomplemented if the value assigned to it is 1. Consider the table to the right, since in the first row, the variables Equation a , Equation b , and Equation c are all Equation 0 , the minterms for them is Equation a overbar logical-and b overbar logical-and c overbar

A sum term is the Boolean sum (ORing) of variables as a subset of the possible variables or their complements. For example, for the function Equation f left-parenthesis a comma b comma c right-parenthesis , the following are a few possible sum terms: Equation c overbar , Equation a logical-or b , and Equation a overbar logical-or b .

The sum of minterms also called Sum of Product (SoP), canonical sum of products, minterm expansion, and canonical disjunctive normal form (CDNF) is a Boolean expression in which each term contains all the variables, either in normal or complemented form as sum of all the minterms. For example, consider the following Boolean functions.

Equation f left-parenthesis a comma b comma c comma d right-parenthesis equals a left-parenthesis b plus c plus d right-parenthesis

We can express that function in SoP form as follows.

Equation f left-parenthesis a comma b comma c comma d right-parenthesis equals left-parenthesis a b c d right-parenthesis plus left-parenthesis a b c d overbar right-parenthesis plus left-parenthesis a b c overbar d right-parenthesis plus left-parenthesis a b c overbar d overbar right-parenthesis plus left-parenthesis a b overbar c d right-parenthesis plus left-parenthesis a b overbar c d overbar right-parenthesis plus left-parenthesis a b overbar c overbar d right-parenthesis
Sum of Product Example
Function
Equation f left-parenthesis a comma b comma c right-parenthesis equals a logical-or left-parenthesis b logical-and c right-parenthesis
a b c minterms notation Equation f Equation f prime
0 0 0 Equation a overbar logical-and b overbar logical-and c overbar Equation m 0 0 1
0 0 1 Equation a overbar logical-and b overbar logical-and c Equation m 1 0 1
0 1 0 Equation a overbar logical-and b logical-and c overbar Equation m 2 0 1
0 1 1 Equation a overbar logical-and b logical-and c Equation m 3 1 0
1 0 0 Equation a logical-and b overbar logical-and c overbar Equation m 4 1 0
1 0 1 Equation a logical-and b overbar logical-and c Equation m 5 1 0
1 1 0 Equation a logical-and b logical-and c overbar Equation m 6 1 0
1 1 1 Equation a logical-and b logical-and c Equation m 7 1 0

The minterms for which the function produces a Equation 1 are called 1-minterms. Likewise, minterms for which the function produces a Equation 0 are called 0-minterms. Any Boolean function can be expressed as sum of its 1-minterms. For example, consider the following function:

Equation f left-parenthesis a comma b comma c right-parenthesis equals a plus left-parenthesis b c right-parenthesis

The truth table for it is on the right. We can express this function as sum of 1-minterms:

Equation f left-parenthesis a comma b comma c right-parenthesis equals a overbar b c plus a b overbar c overbar plus a b overbar c plus a b c overbar plus a b c

We can replace the individual minterms with their respective index which is also shown in the table.

Equation f left-parenthesis a comma b comma c right-parenthesis equals m 3 plus m 4 plus m 5 plus m 6 plus m 7

This function can now be more concisely written a in the following way:

Equation f left-parenthesis a comma b comma c right-parenthesis equals sigma-summation m left-parenthesis list of 1 hyphen minterm indices right-parenthesis

I.e.

Equation f left-parenthesis a comma b comma c right-parenthesis equals m 3 plus m 4 plus m 5 plus m 6 plus m 7 equals sigma-summation m left-parenthesis 3 comma 4 comma 5 comma 6 comma 7 right-parenthesis

Likewise, the inverse of the function can be expressed as the sum of 0-minterms:

Equation StartLayout 1st Row 1st Column f prime left-parenthesis a comma b comma c right-parenthesis 2nd Column equals a overbar b overbar c overbar plus a overbar b overbar c plus a overbar b c overbar 2nd Row 1st Column Blank 2nd Column equals m 0 plus m 1 plus m 2 3rd Row 1st Column Blank 2nd Column equals sigma-summation m left-parenthesis 0 comma 1 comma 2 right-parenthesis EndLayout


Product of Sum (PoS)

Sum of Product Example
Function
Equation f left-parenthesis a comma b comma c right-parenthesis equals a logical-or left-parenthesis b logical-and c right-parenthesis
a b c minterms notation Equation f Equation f prime
0 0 0 Equation a logical-or b logical-or c Equation upper M 0 0 1
0 0 1 Equation a logical-or b logical-or c overbar Equation upper M 1 0 1
0 1 0 Equation a logical-or b overbar logical-or c Equation upper M 2 0 1
0 1 1 Equation a logical-or b overbar logical-or c overbar Equation upper M 3 1 0
1 0 0 Equation a overbar logical-or b logical-or c Equation upper M 4 1 0
1 0 1 Equation a overbar logical-or b logical-or c overbar Equation upper M 5 1 0
1 1 0 Equation a overbar logical-or b overbar logical-or c Equation upper M 6 1 0
1 1 1 Equation a overbar logical-or b overbar logical-or c overbar Equation upper M 7 1 0

A maxterm is the Boolean sum (ORing) of Equation n variables and contains all Equation n variables of the function just once, in either normal or complemented form. For example, for the function Equation f left-parenthesis a comma b right-parenthesis with two variables, we can have the following maxterms: Equation a logical-or b , Equation a logical-or b overbar , Equation a overbar logical-or b , and Equation a overbar logical-or b overbar .

A product term is the Boolean product (ANDing) of variables as a subset of the possible variables or their complements. For example, for function Equation f left-parenthesis a comma b comma c right-parenthesis , the following are possible product terms: Equation c overbar , Equation a logical-and b overbar , and Equation c logical-and a .

The sum of maxterms also called Product of Sum (PoS), canonical sum of products, maxterm expansion, canonical conjunctive normal form (CCNF) is a Boolean expression in which each term contains all the variables, either in normal or complemented form as the sum of all the maxterms.

Equation f left-parenthesis a comma b comma c comma d right-parenthesis equals a left-parenthesis b plus c plus d right-parenthesis

We can express that function in PoS form as follows.

Equation multiline equation line 1 f left-parenthesis a comma b comma c comma d right-parenthesis equals left-parenthesis a plus b plus c plus d right-parenthesis dot left-parenthesis a plus b plus c plus d overbar right-parenthesis dot left-parenthesis a plus b plus c overbar plus d right-parenthesis dot left-parenthesis a plus b plus c overbar plus d overbar right-parenthesis dot line 2 left-parenthesis a plus b overbar plus c plus d right-parenthesis dot left-parenthesis a plus b overbar plus c plus d overbar right-parenthesis dot left-parenthesis a plus b overbar plus c overbar plus d right-parenthesis dot left-parenthesis a plus b overbar plus c overbar plus d overbar right-parenthesis dot line 3 left-parenthesis a overbar plus b plus c plus d right-parenthesis

The maxterms for which the function produces a Equation 1 are called 1-maxterms. Likewise, maxterms for which the function produces a Equation 0 are called 0-maxterms. Any Boolean function can be expressed as product of its 0-maxterms. For example, consider the following function:

Equation f left-parenthesis a comma b comma c right-parenthesis equals a plus left-parenthesis b c right-parenthesis

The truth table for it is on the right. We can express this function as product of 0-maxterms:

Equation f left-parenthesis a comma b comma c right-parenthesis equals left-parenthesis a plus b plus c right-parenthesis dot left-parenthesis a plus b plus c overbar right-parenthesis dot left-parenthesis a plus b overbar plus c right-parenthesis

We can replace the individual minterms with their respective index which is also shown in the table.

Equation f left-parenthesis a comma b comma c right-parenthesis equals upper M 0 plus upper M 1 plus upper M 2

This function can now be more concisely written a in the following way:

Equation f left-parenthesis a comma b comma c right-parenthesis equals product upper M left-parenthesis list of 1 hyphen minterm indices right-parenthesis

I.e.

Equation f left-parenthesis a comma b comma c right-parenthesis equals upper M 0 plus upper M 1 plus upper M 2 equals product upper M left-parenthesis 0 comma 1 comma 2 right-parenthesis

Likewise, the inverse of the function can be expressed as the product of 0-maxterms:

Equation StartLayout 1st Row 1st Column f prime left-parenthesis a comma b comma c right-parenthesis 2nd Column equals left-parenthesis a plus b overbar plus c overbar right-parenthesis dot left-parenthesis a overbar plus b plus c right-parenthesis dot left-parenthesis a overbar plus b plus c overbar right-parenthesis dot left-parenthesis a overbar plus b overbar plus c right-parenthesis dot left-parenthesis a overbar plus b overbar plus c overbar right-parenthesis 2nd Row 1st Column Blank 2nd Column equals upper M 3 plus upper M 4 plus upper M 5 plus upper M 6 plus upper M 7 3rd Row 1st Column Blank 2nd Column equals product upper M left-parenthesis 3 comma 4 comma 5 comma 6 comma 7 right-parenthesis EndLayout


Minimization

New text document.svg This section is empty; you can help add the missing info by editing this page.

Complementary Function

New text document.svg This section is empty; you can help add the missing info by editing this page.

See also

Retrieved from "https://en.wikichip.org/w/index.php?title=boolean_algebra&oldid=12922"