UNIT 3 – Boolean Algebra (continued)
This chapter in the book includes:
Objectives
Study Guide
3.1 Multiplying Out and Factoring Expressions
3.2 Exclusive-OR and Equivalence Operations
3.3 The Consensus Theorem
3.4 Algebraic Simplification of Switching Expressions
3.5 Proving the Validity of an Equation
Programmed Exercises
Problems
Prof. Hyoung Won Baac
Objectives
Topics introduced in this chapter:
• Apply Boolean laws and theorems to manipulation of expression
• Simplifying
• Finding the complement
• Multiplying out and factoring
• Exclusive-OR and Equivalence operation (Exclusive-NOR)
• Consensus theorem
3.1 Multiplying Out and Factoring Expressions
To obtain a sum-of-product form è Multiplying out using distributive laws
X (Y + Z ) = XY + XZ
( X + Y )( X + Z ) = X + YZ
'&%
Useful theorem for multiplying: ( X + Y )( X ' + Z ) = XZ + X ' Y (3-3)
$!!#!! "
L.H.S. = (X + Y) (X’ + Z) = XZ + X’Y + YZ
(1) You can use a truth table for comparison Therefore,
or XZ + X’Y + YZ = XZ + X’Y
(2) If Y = Z = 1, for all possible
then L.H.S. = XZ + X’Y + YZ = X + X’ + 1 = 1 = R.H.S. combinations of Y and Z
If Y or Z = 0, (i.e. YZ in the L.H.S. is
then L.H.S. = XZ + X’Y + YZ = XZ + X’Y = R.H.S. redundant)
3.1 Multiplying Out and Factoring Expressions
The following example illustrates the use of Theorem (3 - 3) for factoring :
'&%
The theorem used for factoring: $A!
B#+A! 'C = ( A + C )( A'+ B )
"
Note: In real problems, when we find A and A’ together shown in factored or
multiplied forms, we can use this theorem for simplification.
Example: (Q + AB ' )(C ' D + Q ' ) = QC ' D + Q ' AB '
If we expand directly (Q + AB' )(C ' D + Q' ) = QC ' D + QQ'+ AB ' C ' D + AB' Q'
(by multiplying out à Redundant terms
using distributive laws)
3.1 Multiplying Out and Factoring Expressions
Example (multiplying out using distributive laws & theorem (3-3)): POS to SOP
( A + B +C' )( A + B + D)( A + B + E)( A + D' +E)( A' +C)
= (A + B + C 'D )(A + B + E )(AC + A'(D '+E ))
= (A + B + C 'DE )(AC + A'(D '+E ))
= AC + ABC + A'B (D '+E ) + A'C 'DE (D '+E )
= AC + A'BD '+ A'BE + A'C 'DE
Note:
(X + Y )(X + Z ) = X + YZ
(X + Y )(X '+Z ) = XZ + X 'Y
3.1 Multiplying Out and Factoring Expressions
Example of factoring: SOP to POS
AC + A' BD ' + A' BE + A' C ' DE
= AC + A' ( BD ' +BE + C ' DE )
XZ X' Y
=
3.2 Exclusive-OR and Equivalence Operations
Exclusive-OR 0Å0 = 0 0 Å1 = 1
1Å 0 = 1 1Å1 = 0
Truth Table XY XÅY X+Y (XY)’
0 0 0
XY=11 does not produce
the output of 1 in Exclusive-OR 0 1 1
(i.e. excluded from OR). 1 0 1
1 1 0
Symbol
Equivalence equation
(Exclusive-OR) X Å Y = X'Y + XY'
3.2 Exclusive-OR and Equivalence Operations
X¹ Y à XÅ Y =1 The exclusive-OR gate checks whether two
X= Y à XÅ Y =0 inputs are different (then, output=1).
Theorems for Exclusive-OR: X Å0 = X X Å X '=1
X Å1 = X ' X ÅX =0
X ÅY = Y Å X Commutative law
(X ÅY ) Å Z = X Å (Y Å Z ) = X ÅY Å Z Associative law
X (Y Å Z ) = XY Å XZ Distributive law
( X Å Y )' = X Å Y' = X' Å Y = XY + X'Y'
= [(X+Y) (XY)’]’=
3.2 Exclusive-OR and Equivalence Operations
Exclusive-NOR (0 º 0) = 1 (0 º 1) = 0
(also called Equivalence operation)
(1 º 0) = 0 (1 º 1) = 1
Truth Table XY XºY
0 0 1
(X ÅY )'
XY=11 does not produce 0 1 0
the output of 0. 1 0 0
1 1 1
Symbol
The ex-NOR gate checks
the equality of two inputs.
Boolean algebra
expression (X º Y ) = (X ÅY )' = XY + X'Y'
3.2 Exclusive-OR and Equivalence Operations
Exclusive-NOR
( XY '+ X ' Y )' = XY + X ' Y ' (3-19)
Example of X-OR and X-NOR: F = ( A' B º C) + ( B Å AC' )
F = [(A'B )C + (A'B )'C '] + [B '(AC ' ) + B (AC ' )']
= A'BC + (A + B ' )C '+ AB 'C '+B (A'+C )
= B (A'C + A'+C ) + C '(A + B '+ AB ' ) = B (A'+C ) + C '(A + B ' )
Example: A'Å B Å C = [ A' B '+ ( A' )' B ] Å C
= ( A' B '+ AB )C '+ ( A' B '+ AB )' C (by (3-6))
= ( A' B '+ AB )C '+ ( A' B + AB ' )C (by (3-19))
= A' B ' C '+ ABC '+ A' BC + AB ' C
3.2 Exclusive-OR and Equivalence Operations
Problem 3.10 – Write an expression for F and simplify into the form of .
3.3 The Consensus Theorem
Consensus Theorem XY + X ' Z + YZ = XY + X ' Z
Proof : XY + X ' Z + YZ = XY + X ' Z + ( X + X ' )YZ
= ( XY + XYZ ) + ( X ' Z + X ' YZ )
= XY (1 + Z ) + X ' Z (1 + Y ) = XY + X ' Z
Example: consensus
Take ‘dual’
a' b'+ ac + bc'+b' c + ab = a' b'+ ac + bc' in each side
consensus
Dual form of consensus theorem ( X + Y )( X '+ Z )(Y + Z ) = ( X + Y )( X '+ Z )
1) Complement the entire form Consensus theorem in a product form
2) Complement each variable
= Replace AND with OR (OR with AND)
Example: (a + b + c' )(a + b + d ' )(b + c + d ' ) = (a + b + c' )(b + c + d ' )
3.3 The Consensus Theorem
Example: eliminate BCD A' C ' D + A' BD + BCD + ABC + ACD'
Example: eliminate A’BD, ABC A' C ' D + A' BD + BCD + ABC + ACD'
à Elimination depends on your choice
Example: elimination by
intentionally adding a term F = ABCD + B ' CDE + A' B '+ BCE '
F = ABCD + B ' CDE + A' B '+ BCE '+ ACDE
Intentional addition
of consensus term
Final expression: F = A' B '+ BCE '+ ACDE
3.4 Algebraic Simplification of Switching Expressions
- Review and summary of simplification methods -
1. Combining terms
XY + XY ' = X
Example1: abc' d '+ abcd ' = abd ' [ X = abd ' , Y = c]
Example2: (a + bc )(d + e' ) + a' (b'+c' )(d + e' ) = d + e'
[ X = d + e' , Y = a + bc, Y ' = a' (b'+c' )]
X +X =X
Example: ab' c + abc + a ' bc = ab' c + abc + abc + a ' bc = ac + bc
intentional addition
3.4 Algebraic Simplification of Switching Expressions
2. Eliminating terms
X + XY = X
Example: a ' b + a ' bc = a ' b [ X = a ' b]
XY + X ' Z +YZ = XY + X ' Z
Example: a ' bc'+bcd + a ' bd = a ' bc'+bcd [ X = c, Y = bd , Z = a' b]
3. Eliminating literals
X + X 'Y = X +Y
Example: A' B + A' B ' C ' D '+ ABCD ' = A' ( B + B ' C ' D ' ) + ABCD '
= A' ( B + C ' D ' ) + ABCD '
= B ( A'+ ACD ' ) + A' C ' D '
= B ( A'+CD ' ) + A' C ' D '
= A' B + BCD '+ A' C ' D ' 10 to 8 literals
3.4 Algebraic Simplification of Switching Expressions
4. Adding redundant terms
If the previous approaches don’t work, then we can consider the addition of redundant terms.
For example:
Adding XX’ (=0)
Multiplying (X+X’) (=1) Before addition,
Adding YZ to XY+X’Z (to use the consensus theorem) we should determine a target
Adding XY to X (X+XY=X) term for elimination
Example: WX + XY + X ' Z '+WY ' Z ' (WZ’ can be added by consensus theorem)
= WX + XY + X ' Z '+WY ' Z '+WZ '
= WX + XY + X ' Z '+WZ ' (3-27)
= WX + XY + X ' Z '
à Any product expression with the consensus-redundant term WZ’
is also redundant (i.e. WZ’ABCDE...)
3.4 Algebraic Simplification of Switching Expressions
Example: (3-29) Simplify the following POS with 5 terms into a POS with 2 terms
(A'+B '+C ' )(A'+B '+C )(B '+C )(A + C )(A + B + C )
=
= (A'+B '+C ' )(B '+C )(A + C )
= (B '+C (A'+C ' ))(A + C )
= (B '+ A'C )(A + C )
= (A'+B ' )(B '+C )(A + C )
Solve an example (eq. 3-28) by yourself. Check your understanding for various theorems.
A'B'C'D' + A'BC'D' + A'BD + A'BC'D + ABCD + ACD' + B'CD'
= A'C'D' + A'BD + B'CD' + ABC
Note: There is no simple way to determine whether a given Boolean expression has
a minimum number of terms.
à We will find advanced systematic approaches using Karnaugh maps (UNIT5) and
Quine-McCluskey method (UNIT6).
3.5 Proving Validity of an Equation
Proving an equation valid
1. Construct a truth table and evaluate both sides – tedious, not elegant method
2. Manipulate one side by applying theorems until it is the same as the other side
3. Reduce both sides of the equation independently
4. Apply the same operation simultaneously on both sides only when the operation is ‘reversible’
- Take complement on both sides (à reversible)
- But multiplication and addition are not reversible (one way works but not the other)
3.5 Proving Validity of an Equation
Example:
Prove that à A'BD' + BCD + ABC' + AB'D = BC'D' + AD + A'BC
(by applying
consensus = A'BD '+BCD + ABC '+ AB 'D + BC 'D '+ A'BC + ABD
theorem)
(add consensus of A’BD’ and ABC’)
(add consensus of A’BD’ and BCD)
(add consensus of BCD and ABC’)
= AD + A'BD '+BCD + ABC '+BC 'D '+ A'BC
(eliminate consensus of BC’D’ and AD)
(eliminate consensus of AD and A’BC)
(eliminate consensus of BC’D’ and A’BC)
= BC 'D '+ AD + A'BC
3.5 Proving Validity of an Equation
Some of Boolean Algebra are not true for ordinary algebra
Example: If x + y = x + z, then y=z True in ordinary algebra
1+ 0 = 1+ 1 but y ¹ z Not true in Boolean algebra
Example: If xy = xz , then y=z True in Boolean algebra when x¹0
Not true in Boolean algebra when x=0
Example: If y = z , then x +y =x +z
(Reverse True in Boolean algebra
cases) If y = z , then xy = xz
Note: Multiplication and addition are not reversible in Boolean algebra
(Not proper to prove validity of an equation)