ZeePedia

Boolean Addition, Multiplication, Commutative Law, Associative Law, Distributive Law, Demorgan’s Theorems

<< DC Supply Voltage, TTL Logic Levels, Noise Margin, Power Dissipation
Simplification of Boolean Expression, Standard POS form, Minterms and Maxterms >>
img
CS302 - Digital Logic & Design
Lesson No. 08
BOOLEAN ALGEBRA AND LOGIC SIMPLIFICATION
Any digital circuit no matter how complex can be described by Boolean Expressions.
Boolean algebra is the mathematics of Digital Systems. Knowledge of Boolean algebra is
indispensable to the study and analysis of logic gates. AND, OR, NOT, NAND and NOR gates
perform simple Boolean operations and Boolean expressions represent the Boolean
operations performed by the logic gates.
·  AND gate
F = A.B
·  OR gate
F=A+B
F=A
·  NOT gate
F = A.B
·  NAND gate
F=A+B
·
NOR gate
Boolean expressions which represent Boolean functions help in two ways. The function
and operation of a Logic Circuit can be determined by Boolean expressions without
implementing the Logic Circuit. Secondly, Logic circuits can be very large and complex. Such
large circuits having many gates can be simplified and implemented using fewer gates.
Determining a simpler Logic circuit having fewer gates which is identical to the original logic
circuit in terms of the function it performs can be easily done by evaluating and simplifying
Boolean expressions.
Boolean Algebra expressions are written in terms of variables and literals using laws,
rules and theorems of Boolean Algebra. Simplification of Boolean expressions is also based
on the Boolean laws, rules and theiorems.
Boolean Algebra Definitions
1. Variable
A variable is a symbol usually an uppercase letter used to represent a logical quantity.
A variable can have a 0 or 1 value.
2. Complement
A complement is the inverse of a variable and is indicated by a bar over the variable.
Complement of variable X is X . If X = 0 then X = 1 and if X = 1 then X = 0.
3. Literal
A Literal is a variable or the complement of a variable.
Boolean Addition
Boolean Addition operation is performed by an OR gate. In Boolean algebra the
expression defining Boolean Addition is a sum term which is the sum of literals.
A + B, A + B, A + B + C
·
A sum term is 1 when any one literal is a 1
·
A sum term is 0 when all literals are a 0.
71
img
CS302 - Digital Logic & Design
Boolean Multiplication
Boolean Multiplication operation is performed by an AND gate. In Boolean algebra the
expression defining Boolean Multiplication is a product term which is the product of literals.
A.B , A.B , A.B.C
·
A product term is 1 when all literal terms are a 1
·
A product term is 0 when any one literal is a 0.
Laws of Boolean Algebra
The basic laws of Boolean Algebra are the same as ordinary algebra and hold true for
any number of variables.
1. Commutative Law for addition and multiplication
2. Associative Law for addition and multiplication
3. Distributive Law
1. Commutative Law for Addition and Multiplication
·  Commutative Law for Addition
A+B=B+A
·  Commutative Law for Multiplication
A.B = B.A
Figure 8.1
Implementation of Commutative Laws
In terms of implementation, the Boolean Addition and Multiplication of two or more
literals is the same no matter how they are ordered at the input of an OR and AND Gates
respectively. Commutative law for Addition and Multiplication holds true for n number of
literals.
2. Associative Law for Addition and Multiplication
·  Associative Law for Addition
A + (B + C) = (A + B) + C
·  Associative Law for MultiplicationA.(B.C) = (A.B).C
72
img
CS302 - Digital Logic & Design
A
A
A.(B.C)
A.B
B
B
(A.B).C
B.C
C
C
Figure 8.2
Implementation of Associative Laws
In terms of implementation, the Associative ordering of literals for Boolean Addition and
Multiplication is the same at the input of an OR and AND gates. Commutative law for Addition
and Multiplication holds true for n number of literals. The addition of literals B and C followed
by the addition of literal A with the result of B+C is the same as adding literals A and B
followed by the addition of literal C.
The multiplication of literals B and C followed by the multiplication of the result of B.C
with literal A is the same as multiplying literals A and B followed by the multiplication of literal
C.
3. Distributive Law
·  Distributive Law
A.(B + C) = A.B + A.C
Figure 8.3
Implementation of Distributive Law
Distributive law holds true for any number of literals. Adding literals B and C followed
by multiplying the result with literal A is the same as multiplying literal A with literal B and
adding the result to the product of literals A and C.
Rules of Boolean Algebra
Rules of Boolean Algebra can be proved by replacing the literals with Boolean values 0
and 1.
1.
A+0=A
2.
A+1=1
3.
A.0 = 0
4.
A.1 = A
5.
A+A=A
A+ A=1
6.
7.
A.A = A
A. A = 0
8.
73
img
CS302 - Digital Logic & Design
9. A = A
10. A + A.B = A
= A.(1 + B)
where (1+B) according to Rule 2 is equal to 1
=A
11. A + A.B = A + B
= A(B+1) + A.B
according to Rule 2 (B+1) = 1
= AB +A + A.B
= B(A+ A ) +A
according to Rule 6 A + A = 1
=B+A
12. (A+B).(A+C) = A+B.C
= AA+AC+AB+BC applying the Distributive Law
= A(1+C+B) +BC
according to Rule 2 (1+B+C) = 1
= A+BC
Demorgan's Theorems
Demorgan's First Theorem states: The complement of a product of variables is equal
to the sum of the complements of the variables.
A.B = A + B
Demorgan;s Second Theorem states: The complement of sum of variables is equal to
the product of the complements of the variables.
A + B = A.B
Demorgan's two theorems prove the equivalency of the NAND and negative-OR gates
and the NOR and negative-AND gates respectively. Figure 8.4
A +B
A.B
A +B
A.B
Figure 8.4
Implementation of Demorgan's Theorems
Demorgan's Theorems can be applied to expressions having any number of variables
·  X.Y.Z = X + Y + Z
X + Y + Z = X.Y.Z
·
74
img
CS302 - Digital Logic & Design
Demorgan's Theorem can be applied to a combination of other variables
(A + B.C).(A.C + B) = (A + B.C) + (A.C + B)
·
= A.(B.C) + (A.C).B
·
= A.(B + C) + (A + C).B
·
= A.B + A.C + A.B + B.C
·
= A.B + A.C + B.C
·
Boolean Analysis of Logic Circuits
Boolean algebra provides a concise way to represent the operation of a logic circuit.
The complete function of the logic circuit can be determined by evaluating the Boolean
expression using different input combinations.
AB + C
C
(AB + C)D
Figure 8.5
Boolean expression representing a Logic Circuit
The expression (AB + C)D can be derived from the circuit by starting from the left
hand, input side of the Logic Circuit. The AND gate provides the output AB. The OR gate adds
the product term AB and the complement C to result in (AB + C) term. The AND gate on the
right hand side of the circuit performs a multiplication operation between the term
(AB + C) and the literal D resulting in (AB + C)D .
There are four variables, therefore the function table or truth table for the logic circuit
has 16 possible input combinations. The expression can be evaluated by trying out the 16
combinations. Alternately, the input combinations A, B, C and D that set the output of the
expression (AB + C)D to 1 can be easily determined.
From the expression, the output is a 1 if both variable D = 1 and term (AB + C) =1.
The term (AB + C) =1 only if AB=1 or C=0.
Thus expression (AB + C)D =1
if D=1 AND (C=0 OR AB=1)
75
img
CS302 - Digital Logic & Design
Inputs
Output
A
B
C
D
F
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
1
0
1
1
0
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
1
0
1
1
1
1
0
0
1
1
1
1
1
Function table for expression (AB + C)D
Table 8.1
In the function table the input conditions for variables A, B, C and D that satisfy the
condition D=1 AND C=0 are 0001, 0101, 1001. The condition D=1 AND AB=1 are satisfied by
input combination 1111. The condition D=1 AND (C=0 OR AB=1) is satisfied by the input
combination 1101.
Simplification using Boolean Algebra
Many times a Boolean expression has to be simplified using laws, rules and theorems
of Boolean Algebra. The simplified expression results in fewer variables and a simpler circuit.
Consider the Boolean expression AB + A(B+C) + B(B+C) and the Logic Circuit represented by
the expression. Figure 8.6. The simplification of the expression results in an expression B +
AC represented by a simpler circuit having fewer gates. Figure 8.7
= AB + A(B+C) + B(B+C)
= AB + AB + AC + BB +BC
using Distributive Law
= AB + AC + B + BC
BB = B using rule 7
= AB + AC + B
(B+BC) = B using rule 10
= B + AC
(B+AB) = B using rule 10
Figure 8.6
Logic Circuit represented by Boolean expression AB + A(B+C) + B(B+C)
76
img
CS302 - Digital Logic & Design
Figure 8.7
Simplified Logic Circuit represented by Boolean expression B+AC
Standard Form of Boolean Expressions
All Boolean expressions can be converted into and represented in one of the two
standard forms
·
Sum-of-Products form
·
Product-of-Sums form
1. Sum of Product form
When two or more product terms are summed by Boolean addition, the result is a
Sum-of-Product or SOP expression.
·
AB + ABC
·
ABC + CDE + BCD
AB + ABC + AC
·
The Domain of an SOP expression is the set of variables contained in the expression,
both complemented and un-complemented. A SOP expression can have a single variable term
such as A. A SOP expression can not have a term of more than one variable having an over
bar extending over the entire term, such as AB + C .
2. Product of Sums form
When two or more sum terms are multiplied by Boolean multiplication, the result is a
Product-of-Sum or POS expression.
(A + B)(A + B + C)
·
(A + B + C)(C + D + E)(B + C + D)
·
(A + B)(A + B + C)(A + C)
·
The Domain of a POS expression is the set of variables contained in the expression,
both complemented and un-complemented. A POS expression can have a single variable term
such as A. A POS expression can not have a term of more than one variable having an over
bar extending over the entire term such as (A + B)(A + B + C) .
77
img
CS302 - Digital Logic & Design
Implementation of an SOP and POS expression
A SOP expression can be implemented by an AND-OR combination of gates. The
product terms are implemented by an AND gate and the SOP expression is implemented by
OR gate connected to the outputs of the AND gates. Figure 8.8
Figure 8.8
SOP Implementation of Boolean expression B+AC+AD
A POS expression can be implemented by an OR-AND combination of gates. The sum
terms are implemented by OR gates and the POS expression is implemented by AND gate
connected to the outputs of the OR gates.
Figure 8.9
POS Implementation of Boolean expression (A+B)(B+C+D)(A+C)
Conversion of a general expression to SOP form
Any logical expression can be converted into SOP form by applying techniques of
Boolean Algebra
AB + B(CD + EF) = AB + BCD + BEF
·
(A + B)(B + C + D) = AB + AC + AD + B + BC + BD = AC + AD + B
·
(A + B) + C = (A + B)C = (A + B)C = AC + BC
·
78
Table of Contents:
  1. AN OVERVIEW & NUMBER SYSTEMS
  2. Binary to Decimal to Binary conversion, Binary Arithmetic, 1’s & 2’s complement
  3. Range of Numbers and Overflow, Floating-Point, Hexadecimal Numbers
  4. Octal Numbers, Octal to Binary Decimal to Octal Conversion
  5. LOGIC GATES: AND Gate, OR Gate, NOT Gate, NAND Gate
  6. AND OR NAND XOR XNOR Gate Implementation and Applications
  7. DC Supply Voltage, TTL Logic Levels, Noise Margin, Power Dissipation
  8. Boolean Addition, Multiplication, Commutative Law, Associative Law, Distributive Law, Demorgan’s Theorems
  9. Simplification of Boolean Expression, Standard POS form, Minterms and Maxterms
  10. KARNAUGH MAP, Mapping a non-standard SOP Expression
  11. Converting between POS and SOP using the K-map
  12. COMPARATOR: Quine-McCluskey Simplification Method
  13. ODD-PRIME NUMBER DETECTOR, Combinational Circuit Implementation
  14. IMPLEMENTATION OF AN ODD-PARITY GENERATOR CIRCUIT
  15. BCD ADDER: 2-digit BCD Adder, A 4-bit Adder Subtracter Unit
  16. 16-BIT ALU, MSI 4-bit Comparator, Decoders
  17. BCD to 7-Segment Decoder, Decimal-to-BCD Encoder
  18. 2-INPUT 4-BIT MULTIPLEXER, 8, 16-Input Multiplexer, Logic Function Generator
  19. Applications of Demultiplexer, PROM, PLA, PAL, GAL
  20. OLMC Combinational Mode, Tri-State Buffers, The GAL16V8, Introduction to ABEL
  21. OLMC for GAL16V8, Tri-state Buffer and OLMC output pin
  22. Implementation of Quad MUX, Latches and Flip-Flops
  23. APPLICATION OF S-R LATCH, Edge-Triggered D Flip-Flop, J-K Flip-flop
  24. Data Storage using D-flip-flop, Synchronizing Asynchronous inputs using D flip-flop
  25. Dual Positive-Edge triggered D flip-flop, J-K flip-flop, Master-Slave Flip-Flops
  26. THE 555 TIMER: Race Conditions, Asynchronous, Ripple Counters
  27. Down Counter with truncated sequence, 4-bit Synchronous Decade Counter
  28. Mod-n Synchronous Counter, Cascading Counters, Up-Down Counter
  29. Integrated Circuit Up Down Decade Counter Design and Applications
  30. DIGITAL CLOCK: Clocked Synchronous State Machines
  31. NEXT-STATE TABLE: Flip-flop Transition Table, Karnaugh Maps
  32. D FLIP-FLOP BASED IMPLEMENTATION
  33. Moore Machine State Diagram, Mealy Machine State Diagram, Karnaugh Maps
  34. SHIFT REGISTERS: Serial In/Shift Left,Right/Serial Out Operation
  35. APPLICATIONS OF SHIFT REGISTERS: Serial-to-Parallel Converter
  36. Elevator Control System: Elevator State Diagram, State Table, Input and Output Signals, Input Latches
  37. Traffic Signal Control System: Switching of Traffic Lights, Inputs and Outputs, State Machine
  38. Traffic Signal Control System: EQUATION DEFINITION
  39. Memory Organization, Capacity, Density, Signals and Basic Operations, Read, Write, Address, data Signals
  40. Memory Read, Write Cycle, Synchronous Burst SRAM, Dynamic RAM
  41. Burst, Distributed Refresh, Types of DRAMs, ROM Read-Only Memory, Mask ROM
  42. First In-First Out (FIFO) Memory
  43. LAST IN-FIRST OUT (LIFO) MEMORY
  44. THE LOGIC BLOCK: Analogue to Digital Conversion, Logic Element, Look-Up Table
  45. SUCCESSIVE –APPROXIMATION ANALOGUE TO DIGITAL CONVERTER