POST BY : NURUL ILHAM KAMALIAH BT AHMAD B031210353
3.2: COMBINATIONAL
CIRCUITS
v
Alogic block contains no memory and computes the
output given the current inputs.
v
Can be defined in three ways :
1.
Truth table
2.
Graphical symbols
3.
Boolean equations
BOOLEAN EQUATION FORMS
v
A boolean
algebra is the combinations of variables and operators.
v
All Boolean expression can be represented in two
forms:
Ø
Sum-of-products(SOP) = Combination of input values that produce 1s is convert into
equivalentvariables,ANDed
together then ORed with other
combination variable with the same output.
Example :
- The truth table :
F = A’B’+ ABC’D
A
|
B
|
C
|
D
|
F
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
SOP
expression :
Ø Product-of-sum(POS) = Input combinations that produce 0s in sum terms
(ORed variables) are ANDed together.
Convert input values that
produce 0s into equivalent variables
ORed the variables,thenANDed
with other ORed forms
Usually use if more 1s produce in output function
EXAMPLE :
F = (A+B+C)(A+B+C’)(A+B+C’)(A’+B+C’)
A
|
B
|
C
|
F
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
POS expression :
F =
(A+B+C)(A+B+C’)(A+B+C’)(A’+B+C’)
SIMPLIFICATION OF BOOLEAN EQUATION
- Two ways to simplify Boolean equation,
1.
Law Of Boolean Algebra – rules to simplify
expression
2.
Karnaugh Map – A grid-like representation of a
truth table
LAW OF BOOLEAN ALGEBRA
Table
3-2: Basic Laws of Boolean Algebra
|
AND Form
|
OR Form
|
Identity Law
|
A·1 = A
|
A + 0 = A
|
Zero and One Law
|
A·0
= 0
|
A+1 = 1
|
Inverse Law
|
A·A’ = 0
|
A+A’ = 1
|
Indempotent Law
|
A·A = A
|
A+A = A
|
Commutative Law
|
A·B = B·A
|
A+B = B+A
|
Associative Law
|
A·(B·C) = (A·B)·C
|
A+(B+C) = (A+B)+C
|
Distributive Law
|
A+(B·C) = (A+B)·(A+C)
|
A·(B+C)
= (A·B)+(A·C)
|
Absorbtion Law
|
A(A+B) = A
|
A+A·B = A
A+A’B = A+B
|
DorMorgan’s Law
|
(A·B)’ = A’+B’
|
(A+B)’ = A’·B’
|
Double Complement Law
|
=
X = X
|
De Morgan’s Law
NOTE:
If you break the line,you change the sign.
(A·B)’ = A’+ B’
(A+B)’ = A’·B’
POST BY : NUR SYAZWAN BT ABDUL MALEK B031210119
3.3 Karnaugh Map
(K-Map)
- K-Map provides a simple method on minimizing Boolean
expressions.
- However, it will be ineffective for more than four inputs.
For n inputs, there are 2n
cells needed to build the K-Map
|
Example
A
|
B
|
Minterm
|
0
|
0
|
A’B’
|
0
|
1
|
A’B
|
1
|
0
|
AB’
|
1
|
1
|
AB
|
A
B
|
A’
|
A
|
B’
|
|
|
B
|
|
|
K-Map for two
variables(A and B)
A
|
B
|
C
|
Minterm
|
0
|
0
|
0
|
A’B’C’
|
0
|
0
|
1
|
A’B’C
|
0
|
1
|
0
|
A’BC’
|
0
|
1
|
1
|
A’BC
|
1
|
0
|
0
|
AB’C’
|
1
|
0
|
1
|
AB’C
|
1
|
1
|
0
|
ABC’
|
1
|
1
|
1
|
ABC
|
BC
A
|
B’C’
|
B’C
|
BC
|
BC’
|
A’
|
|
|
|
|
A
|
|
|
|
|
K-Map for three variables(A,B and C)
A
|
B
|
C
|
D
|
Minterm
|
0
|
0
|
0
|
0
|
A’B’C’D’
|
0
|
0
|
0
|
1
|
A’B’C’D
|
0
|
0
|
1
|
0
|
A’B’CD’
|
0
|
0
|
1
|
1
|
A’B’CD
|
0
|
1
|
0
|
0
|
A’BC’D’
|
0
|
1
|
0
|
1
|
A’BC’D
|
0
|
1
|
1
|
0
|
A’BCD’
|
0
|
1
|
1
|
1
|
A’BCD
|
1
|
0
|
0
|
0
|
AB’C’D’
|
1
|
0
|
0
|
1
|
AB’C’D
|
1
|
0
|
1
|
0
|
AB’CD’
|
1
|
0
|
1
|
1
|
AB’CD
|
1
|
1
|
0
|
0
|
ABC’D’
|
1
|
1
|
0
|
1
|
ABC’D
|
1
|
1
|
1
|
0
|
ABCD’
|
1
|
1
|
1
|
1
|
ABCD
|
CD
AB
|
C’D’
|
C’D
|
CD
|
CD’
|
A’B’
|
|
|
|
|
A’B
|
|
|
|
|
AB
|
|
|
|
|
AB’
|
|
|
|
|
K-Map for four variables (A,B,C, and D)
A product term that includes all of the variables once,
either complemented or not complemented is called a minterm.
For example,
-
If there are two inputs or variables, there are
four minterms(A’B’,A’B,)
-
If there are inputs or variables,there are 8 mintermA’B’C’ , A’B’C , A’BC’ , A’BC , AB’C’ ,
AB’C , ABC’ and ABC.
Example
F = A+B
- The truth table:
|
A
|
B
|
A+B
|
A’B’
|
0
|
0
|
0
|
A’B
|
0
|
1
|
1
|
AB’
|
1
|
0
|
1
|
AB
|
1
|
1
|
1
|
- Karnaugh Map:
A
B
|
A’
|
A
|
B’
|
0
|
1
|
B
|
1
|
1
|
- Boolean Law:
F = A’B + AB’ + AB
=A’B + AB + AB’ +
AB AB + AB = AB
=B (A’+ A) + A(B’ + B)
=B + A
=A + B
GROUPING 1’s IN KARNAUGH MAP
1- The groups can ONLY contain 1s
2- Only 1s adjacent cells can be grouped ; diagonal
grouping is not allowed.
3- The number of 1s in a group must be a power of
2,means a group can contain 2,4,8, or 16 of
1s.
4- The groups must be as large as possible while still following
all rules.
5- All 1s must belong to a group, even if it is a
group of one
6- Overlapping
groups are allowed.
7- Wrap around is allowed.
8- Use the fewest number of groups possible.