> ts~*S(
b/0DTimes New Roman$b$b0b0TbTb0DSymbolew Roman$b$b0b0TbTb0@ @@``
@n?" dd@ @@``6.<G
S~1?@g4KdKd`b0Xb \ppp@?%O=cO 'Switching Algebra: Principle of Duality('Any theorem or identity in switching algebra remains true if 0 and 1 are swapped and . and + are swapped.
True because all the duals of all the axioms are true, so duals of all switching-algebra theorems can be proven using the duals of axioms.
Dual of a logic expression: For a fully parenthesized logic expression F(X1, X2, & ., Xn, + , . , ) then the dual expression, FD, is the same expression with +, . swapped:
FD(X1, X2, & ., Xn, +, . , ) = F(X1, X2, & ., Xn, . , + , )
The generalized DeMorgan s theorem T14 can be stated as:
[F(X1, X2, & ., Xn)] = FD(X1 , X2 , & ., Xn ) I9AkK+3Kj :bl!;
#Switching Algebra Axioms & Theorems $#p(A1) X = 0 if X 1 (A1 ) X = 1 if X 0
(A2) If X = 0, then X = 1 (A2 ) if X = 1, then, X = 0
(A3) 0 . 0 = 0 (A3 ) 1 + 1 = 1
(A4) 1 . 1 = 1 (A4 ) 0 + 0 = 0
(A5) 0 . 1 = 1 . 0 = 0 (A5 ) 1 + 0 = 0 + 1 = 1
(T1) X + 0 = X (T1 ) X . 1 = X (Identities)
(T2) X + 1 = 1 (T2 ) X . 0 = 0 (Null elements)
(T3) X + X = X (T3 ) X . X = X (Idempotency)
(T4) (X ) = X (Involution)
(T5) X + X = 1 (T5 ) X . X = 0 (Complements)
(T6) X + Y = Y + X (T6 ) X . Y = Y . X (Commutativity)
(T7) (X + Y) + Z = X + (Y + Z) (T7 ) (X . Y) . Z = X . (Y . Z) (Associativity)
(T8) X . Y + X . Z = X . (Y + Z) (T8 ) (X + Y) . (X + Z) = X + Y . Z (Distributivity)
(T9) X + X . Y = X (T9 ) X . (X + Y) = X (Covering)
(T10) X . Y + X . Y = X (T10 ) (X + Y) . (X + Y ) = X (Combining)
(T11) X . Y + X . Z + Y . Z = X . Y + X . Z
(T11 ) (X + Y) . ( X + Z) . (Y + Z) = (X + Y) . (X + Z) (Consensus)
(T12) X + X + . . . + X = X (T12 ) X . X . . . . . X = X (Generalized idempotency)
(T13) (X1 . X2 . . . . . Xn) = X1 + X2 + . . . + Xn
(T13 ) (X1 + X2 + . . . + Xn) = X1 . X2 . . . . . Xn (DeMorgan s theorems)
(T14) [F(X1, X2, . . ., Xn, +, .)] = F(X1 , X2 , . . ., Xn , . , +) (Generalized DeMorgran s theorem)
>
$
;
.N";=O<
F
M5R`
"
0Logic Expression Algebraic Manipulation Example 1/Prove that the following identity is true using Algebraic expression Manipulation : (one can also prove it using a truth table)
X .Y + X . Z = ((X + Y ) . (X + Z ))
Starting from the left hand side of the identity:
Let F = X .Y + X . Z
A = X . Y B = X . Z
Then F = A + B
Using DeMorgan s theorem T 13 on F:
F = A + B = (A . B ) (1)
Using DeMorgan s theorem T 13 on A, B:
A = X . Y = (X + Y ) (2)
B = X . Z = (X + Z ) (3)
Substituting A, B from (2), (3), back in F in (1) gives:
F = (A . B ) = ((X + Y ) . (X + Z ))
Which is equal to the right hand side of the identity.
82l$7(k9}W,8hbA
1:+Standard Representations of Logic Functions ,+-Truth table for n-variable logic function:
Input combinations are arranged in 2n rows in ascending binary order, and the output values are written in a column next to the rows.
Practical for functions with a small number of variables.
The general structure of a 3-variable truth table is given by:v+y)$
_9?)Logic Function Representation Definitions *) A literal: is a variable or a complement of a variable
Examples: X, Y, X , Y
A product term: is a single literal, or a product of two or more literals. Examples: Z W.Y.Y X.Y .Z W .Y .Z
A sum-of-products expression: is a logical sum of product terms.
Example: Z + W.X.Y + X.Y .Z + W .Y .Z
A sum term: is a single literal or logical sum of two or more literals
Examples: Z W + X + Y X + Y + Z W + Y + Z
A product-of-sums expression: is a logical product of sum terms.
Example: Z . (W + X + Y) . (X + Y + Z) . (W + Y + Z)
A normal term: is a product or sum term in which no variable appears more than once
Examples of non-normal terms: W.X.X.Y W+W+X +Y X.X .Y
Examples of normal terms: W . X . Y W + X + Y$:"3HPCAV
QWf 8)Logic Function Representation Definitions *)" Minterm
An n-variable minterm is a normal product term with n literals.
There are 2n such products terms.
Example of 4-variable minterms:
W.X .Y .Z W.X.Y .Z W .X .Y.Z
Maxterm
An n-variable maxterm is a normal sum term with n literals.
There are 2n such sum terms.
Examples of 4-variable maxterms:
W + X + Y + Z W + X + Y + Z W + X + Y + Z
A minterm can be defined as as product term that is 1 in exactly one row of the truth table.
A maxterm can similarly be defined as a sum term that is 0 in exactly one row in the truth table.U
~P
_d
C
= "X[ 7Minterms/Maxterms for A 3-variable function F(X,Y,Z) 87$'Row X Y Z F Minterm Maxterm
0 0 0 0 F(0,0,0) X .Y .Z X + Y + Z
1 0 0 1 F(0,0,1) X .Y .Z X + Y + Z
2 0 1 0 F(0,1,0) X .Y.Z X + Y + Z
3 0 1 1 F(0,1,1) X .Y.Z X + Y + Z
4 1 0 0 F(1,0,0) X.Y .Z X + Y + Z
5 1 0 1 F(1,0,1) X.Y .Z X + Y + Z
6 1 1 0 F(1,1,0) X.Y.Z X + Y + Z
7 1 1 1 F(1,1,1) X.Y.Z X + Y + Z h h&*
Canonical Sum RepresentationMinterm number:
minterm i refers to the minterm corresponding to row i of the truth table. For n-variables i is in the set
{0,1, & , 2n-1}
The canonical sum representation of a logic function is a sum of the minterms corresponding to the truth table rows for which the function produces a 1 output.
A short-hand representation of the minterm list uses the S notation and minterm numbers to indicate the sum of minterms of the function.
This representation is usually realized using 2-level AND-OR logic circuits with inverters at AND gates inputs as needed.
,
9M{Qw w Canonical Sum ExamplejThe function represented by the truth table:
has the canonical sum representation:
F = S X,Y,Z (0, 3, 4, 6, 7)
= X .Y .Z + X .Y.Z + X.Y .Z + X.Y .Z + X.Y.ZT-ZL Canonical Product Representation! Maxterm i refers to the maxterm corresponding to row i of the truth table. For n-variables i is in the set
{0,1, & , 2n-1}
The canonical product representation of a logic function is the product of the maxterms corresponding to the truth table rows for which the function produces a 0 output.
The product of such minterms is called a maxterm list
A short-hand representation of the maxterm list uses the P notation and maxterm numbers to indicate the product of maxterms of the function.
This representation is usually realized using 2-level OR-AND logic circuits with inverters at OR gates inputs as needed.
p1@
p g *#
Canonical Product ExampleVThe function represented by the truth table:
has the canonical product representation:
F = P X,Y,Z (1,2,5)
= (X + Y + Z ) . (X + Y + Z) . (X + Y + Z )T-]?(Conversion Between Minterm/Maxterm Lists)(,To convert between a minterm list and a maxterm list
take the set complement.
Examples:
S X,Y,Z(0,1,2,3) = P X,Y,Z(4,5,6,7)
S X,Y(1) = P X,Y(0,2,3)
S W,X,Y,Z(0,1,2,3,5,7,11,13) = P W,X,Y,Z(4,6,8,9,12,14,15)
H5T
>6 ` ̙33` 3` 3333f` 999MMM` f` f3` 3>?" dd@$? " dd@ " @ `" n?" dd@ @@``PR @ ` `p>>x(
`vgֳgֳ ?``v
=*
`4vgֳgֳ ?` v
?*
`vgֳgֳ ?` v
?*
ZT vgֳgֳ ?`v
T Click to edit Master title style!
!:
T vgֳgֳ ?`v
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
Sd
<8c?8^
61?|d^
61?L\4
T$Tgֳgֳ?>MK
KEECC341 - Shaaban&
`ģTgֳgֳ ?P$
&#* Lec # 5 Winter 2001 12-13-2001''
*H
0h? ? a( ppoint97
0@6(
T'vjJjJ ?P"
v
k*
Tt'vjJjJ ? "v
m*
Z'vjJjJ ?P v
k*
Z$jJjJ ? v
m*
:
Tgֳgֳ ?
@v
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
Sp
01 ?.
vH
0h? ? a(|t0(
T%vjJjJ ?P"
v
O*
T%vjJjJ ? "v
Q*
ZT&vjJjJ ?P v
O*
Z&vjJjJ ? v
Q*
H
0h? ? a(
%$P(
fgֳgֳ ?`
v
fdgֳgֳ ?@`
H
0h ? a(
4(
4l
4 CP`
P
l
4 CdP8x
H
40h ? a(
<( 5X
<l
< CP
Q
l
< CP
Q
H
<0h ? a(n
%
`( )n(:n@*L
fTgֳgֳ ?PP
P
ftTgֳgֳ ?N
TTgֳgֳ?
=
T"Row X Y Z F(X,Y,Z)
0 0 0 0 F(0,0,0)
1 0 0 1 F(0,0,1)
2 0 1 0 F(0,1,0)
3 0 1 1 F(0,1,1)
4 1 0 0 F(1,0,0)
5 1 0 1 F(1,0,1)
6 1 1 0 F(1,1,0)
7 1 1 1 F(1,1,1)##
T4Tgֳgֳ?m
zHTruth table for a specific
function:
Row X Y Z F
0 0 0 0 1
1 0 0 1 0
2 0 1 0 0
3 0 1 1 1
4 1 0 0 1
5 1 0 1 0
6 1 1 0 1
7 1 1 1 1IIH
0h ? a(
%$p(
fTTgֳgֳ ?`
R
fTgֳgֳ ? R
H
0h ? a(
%$(
ftTgֳgֳ ?
R
fTgֳgֳ ?0R
H
0h ? a(
%:2 ( ֳ
fTgֳgֳ ? `0
R
fTgֳgֳ ?d?>
R
" @`H
0h ? a(
%$$(
$
$ ftTgֳgֳ ?0
R
$ fTgֳgֳ ? R
H
$0h ? a(
%JB((
(
( f4Tgֳgֳ ?`P
R
( fTgֳgֳ ?`R
(
TTgֳgֳ?N
H
mRow X Y Z F
0 0 0 0 1
1 0 0 1 0
2 0 1 0 0
3 0 1 1 1
4 1 0 0 1
5 1 0 1 0
6 1 1 0 1
7 1 1 1 1
(
`N1?pp
Minterm list using S notation , vB
(
ND1?YJ
Z
(
`dP1?T
$Algebraic canonical sum of minterms %# vB
(
ND1?@H
(0h ? a(
%$,( 6
0
,
, f Tgֳgֳ ?8
, ft Tgֳgֳ ?pPT
H
,0h ? a(
%% 0(
0
0 f#vgֳgֳ ?0
v
0 f$vgֳgֳ ?`v
0
Tt$vgֳgֳ?~L}x
KRow X Y Z F
0 0 0 0 1
1 0 0 1 0
2 0 1 0 0
3 0 1 1 1
4 1 0 0 1
5 1 0 1 0
6 1 1 0 1
7 1 1 1 1vB
0
ND1?
0
0
`d1?v
Ml
Maxterm list using P notation.
0
`P1?T
|(Algebraic canonical product of maxterms )'
vB
0
ND1?@H
00h ? a(
8( `
8l
8 C$`
l
8 C`
H
80h ? a(rD_f2SkqLxzl}XnyopYb*S(
b/0DTimes New Roman$b$b0b0TbTb0DSymbolew Roman$b$b0b0TbTb0@ @@``
@n
Oh+'04,
0<H
T`hpCECS470Perl70ShaabanhaahaahaaWild Puppy236Microsoft PowerPoint 4.0i@ղw@@>7@ɣ@=̓
G*oM VX& &&#TNPPp0D
v
&
TNPP &&TNPP
- "-- !-- "-&G&
- &Gy& - "- )--- "-y--- "-q----v-- Times New Roman- .!2
EECC341 - Shaaban
. .!2
EECC341 - Shaaban
.--\-- Times New Roman- . 2
#. . 2
1. .2
. .2
Lec . .42
# 5 Winter 2001 12-13-2001.--QH-- Times New Roman- .B2
FW'Switching Algebra: Principle of Duality"
"
#
.--`H-- Times New Roman - .2
R.Times New Roman- .U2
v4Any theorem or identity in switching algebra remains
. .U2
v4true if 0 and 1 are swapped and . and + are swapped.
.Times New Roman - .2
R.Times New Roman- .%2
vTrue because all the . .2
duals
. .:2
" of of all the axioms are true, so
. .2
vduals . .O2
0 of all switching-algebra theorems can be proven
. .2
.v using the . .2
. duals
. .2
.C of axioms.
.Times New Roman - .2
fR.Times New Roman- .X2
fv6Dual of a logic expression: For a fully parenthesized
. .%2
vlogic expression F(X
.Times New Roman- . 2
1.Times New Roman- .2
, X.Times New Roman- . 2
2.Times New Roman- .2
, ., . .
2
X.Times New Roman- . 2
'n.Times New Roman- .32
3, + , . , ) then the dual
. .2
v
expression, F
.Times New Roman- . 2
*D.Times New Roman- .H2
9+, is the same expression with +, . swapped:
. .2
R F.Times New Roman- . 2
D.Times New Roman- .
2
(X.Times New Roman- . 2
1
.Times New Roman- .2
, X.Times New Roman- . 2
2
.Times New Roman- .2
, ., . .
2
C X.Times New Roman- . 2
bn.Times New Roman- .$2
n, +, . , ) = F(X.Times New Roman- . 2
=1.Times New Roman- .2
H, X.Times New Roman- . 2
o2.Times New Roman- .2
z, ., . .
2
X.Times New Roman- . 2
n.Times New Roman- .2
, . , + , )
.Times New Roman - .2
R.Times New Roman- .2
vThe generalized . .2
P DeMorgans. ..2
theorem T14 can be stated
. .2
?vas:
. ."2
mR [F(X.Times New Roman- . 2
u1.Times New Roman- .2
m
, X.Times New Roman- . 2
u42.Times New Roman- .2
m?, ., . .
2
m X.Times New Roman- . 2
un.Times New Roman- .2
m)] = F
.Times New Roman- . 2
d'D.Times New Roman- .
2
m7(X
.Times New Roman- . 2
uX1.Times New Roman- .
2
mc, X.Times New Roman- . 2
u2.Times New Roman- .2
m, .,
. .
2
m X.Times New Roman- . 2
u
n.Times New Roman- . 2
m. . 2
m ).--"System-&TNPP &
S~1?@g4KdKd`b0Xb \ppp@?%O=cO 'Switching Algebra: Principle of Duality('Any theorem or identity in switching algebra remains true if 0 and 1 are swapped and . and + are swapped.
True because all the duals of all the axioms are true, so duals of all switching-algebra theorems can be proven using the duals of axioms.
Dual of a logic expression: For a fully parenthesized logic expression F(X1, X2, & ., Xn, + , . , ) then the dual expression, FD, is the same expression with +, . swapped:
FD(X1, X2, & ., Xn, +, . , ) = F(X1, X2, & ., Xn, . , + , )
The generalized DeMorgan s theorem T14 can be stated as:
[F(X1, X2, & ., Xn)] = FD(X1 , X2 , & ., Xn ) I9AkK+3Kj :bl!;
#Switching Algebra Axioms & Theorems $#p(A1) X = 0 if X 1 (A1 ) X = 1 if X 0
(A2) If X = 0, then X = 1 (A2 ) if X = 1, then, X = 0
(A3) 0 . 0 = 0 (A3 ) 1 + 1 = 1
(A4) 1 . 1 = 1 (A4 ) 0 + 0 = 0
(A5) 0 . 1 = 1 . 0 = 0 (A5 ) 1 + 0 = 0 + 1 = 1
(T1) X + 0 = X (T1 ) X . 1 = X (Identities)
(T2) X + 1 = 1 (T2 ) X . 0 = 0 (Null elements)
(T3) X + X = X (T3 ) X . X = X (Idempotency)
(T4) (X ) = X (Involution)
(T5) X + X = 1 (T5 ) X . X = 0 (Complements)
(T6) X + Y = Y + X (T6 ) X . Y = Y . X (Commutativity)
(T7) (X + Y) + Z = X + (Y + Z) (T7 ) (X . Y) . Z = X . (Y . Z) (Associativity)
(T8) X . Y + X . Z = X . (Y + Z) (T8 ) (X + Y) . (X + Z) = X + Y . Z (Distributivity)
(T9) X + X . Y = X (T9 ) X . (X + Y) = X (Covering)
(T10) X . Y + X . Y = X (T10 ) (X + Y) . (X + Y ) = X (Combining)
(T11) X . Y + X . Z + Y . Z = X . Y + X . Z
(T11 ) (X + Y) . ( X + Z) . (Y + Z) = (X + Y) . (X + Z) (Consensus)
(T12) X + X + . . . + X = X (T12 ) X . X . . . . . X = X (Generalized idempotency)
(T13) (X1 . X2 . . . . . Xn) = X1 + X2 + . . . + Xn
(T13 ) (X1 + X2 + . . . + Xn) = X1 . X2 . . . . . Xn (DeMorgan s theorems)
(T14) [F(X1, X2, . . ., Xn, +, .)] = F(X1 , X2 , . . ., Xn , . , +) (Generalized DeMorgran s theorem)
>
$
;
.N";=O<
F
M5R`
"
0Logic Expression Algebraic Manipulation Example 1/Prove that the following identity is true using Algebraic expression Manipulation : (one can also prove it using a truth table)
X .Y + X . Z = ((X + Y ) . (X + Z ))
Starting from the left hand side of the identity:
Let F = X .Y + X . Z
A = X . Y B = X . Z
Then F = A + B
Using DeMorgan s theorem T 13 on F:
F = A + B = (A . B ) (1)
Using DeMorgan s theorem T 13 on A, B:
A = X . Y = (X + Y ) (2)
B = X . Z = (X +
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKvMNOPQRSTUVWXYZ[\]^_`abdefghijklmnopqruwxyz{|}Root EntrydO)=̓Current User*SummaryInformation(Ld,PowerPoint Document(=DocumentSummaryInformation8?" dd@ @@``6.<G
S~1?@g4KdKd`b0Xb \ppp@?%O=cO 'Switching Algebra: Principle of Duality('Any theorem or identity in switching algebra remains true if 0 and 1 are swapped and . and + are swapped.
True because all the duals of all the axioms are true, so duals of all switching-algebra theorems can be proven using the duals of axioms.
Dual of a logic expression: For a fully parenthesized logic expression F(X1, X2, & ., Xn, + , . , ) then the dual expression, FD, is the same expression with +, . swapped:
FD(X1, X2, & ., Xn, +, . , ) = F(X1, X2, & ., Xn, . , + , )
The generalized DeMorgan s theorem T14 can be stated as:
[F(X1, X2, & ., Xn)] = FD(X1 , X2 , & ., Xn ) I9AkK+3Kj :bl!;
#Switching Algebra Axioms & Theorems $#p(A1) X = 0 if X 1 (A1 ) X = 1 if X 0
(A2) If X = 0, then X = 1 (A2 ) if X = 1, then, X = 0
(A3) 0 . 0 = 0 (A3 ) 1 + 1 = 1
(A4) 1 . 1 = 1 (A4 ) 0 + 0 = 0
(A5) 0 . 1 = 1 . 0 = 0 (A5 ) 1 + 0 = 0 + 1 = 1
(T1) X + 0 = X (T1 ) X . 1 = X (Identities)
(T2) X + 1 = 1 (T2 ) X . 0 = 0 (Null elements)
(T3) X + X = X (T3 ) X . X = X (Idempotency)
(T4) (X ) = X (Involution)
(T5) X + X = 1 (T5 ) X . X = 0 (Complements)
(T6) X + Y = Y + X (T6c ) X . Y = Y . X (Commutativity)
(T7) (X + Y) + Z = X + (Y + Z) (T7 ) (X . Y) . Z = X . (Y . Z) (Associativity)
(T8) X . Y + X . Z = X . (Y + Z) (T8 ) (X + Y) . (X + Z) = X + Y . Z (Distributivity)
(T9) X + X . Y = X (T9 ) X . (X + Y) = X (Covering)
(T10) X . Y + X . Y = X (T10 ) (X + Y) . (X + Y ) = X (Combining)
(T11) X . Y + X . Z + Y . Z = X . Y + X . Z
(T11 ) (X + Y) . ( X + Z) . (Y + Z) = (X + Y) . (X + Z) (Consensus)
(T12) X + X + . . . + X = X (T12 ) X . X . . . . . X = X (Generalized idempotency)
(T13) (X1 . X2 . . . . . Xn) = X1 + X2 + . . . + Xn
(T13 ) (X1 + X2 + . . . + Xn) = X1 . X2 . . . . . Xn (DeMorgan s theorems)
(T14) [F(X1, X2, . . ., Xn, +, .)] = F(X1 , X2 , . . ., Xn , . , +) (Generalized DeMorgran s theorem)
>
$
;
.N";=O<
F
M5R`
"
0Logic Expression Algebraic Manipulation Example 1/Prove that the following identity is true using Algebraic expression Manipulation : (one can also prove it using a truth table)
X .Y + X . Z = ((X + Y ) . (X + Z ))
Starting from the left hand side of the identity:
Let F = X .Y + X . Z
A = X . Y B = X . Z
Then F = A + B
Using DeMorgan s theorem T 13 on F:
F = A + B = (A . B ) (1)
Using DeMorgan s theorem T 13 on A, B:
A = X . Y = (X + Y ) (2)
B = X . Z = (X + Z ) (3)
Substituting A, B from (2), (3), back in F in (1) gives:
F = (A . B ) = ((X + Y ) . (X + Z ))
Which is equal to the right hand side of the identity.
82l$7(k9}W,8hbA
1:+Standard Representations of Logic Functions ,+-Truth table for n-variable logic function:
Input combinations are arranged in 2n rows in ascending binary order, and the output values are written in a column next to the rows.
Practical for functions with a small number of variables.
The general structure of a 3-variable truth table is given by:v+y)$
_9?)Logic Function Representation Definitions *) A literal: is a variable or a complement of a variable
Examples: X, Y, X , Y
A product term: is a single literal, or a product of two or more literals. Examples: Z W.Y.Y X.Y .Z W .Y .Z
A sum-of-products expression: is a logical sum of product terms.
Example: Z + W.X.Y + X.Y .Z + W .Y .Z
A sum term: is a single literal or logical sum of two or more literals
Examples: Z W + X + Y X + Y + Z W + Y + Z
A product-of-sums expression: is a logical product of sum terms.
Example: Z . (W + X + Y) . (X + Y + Z) . (W + Y + Z)
A normal term: is a product or sum term in which no variable appears more than once
Examples of non-normal terms: W.X.X.Y W+W+X +Y X.X .Y
Examples of normal terms: W . X . Y W + X + Y$:"3HPCAV
QWf 8)Logic Function Representation Definitions *)" Minterm
An n-variable minterm is a normal product term with n literals.
There are 2n such products terms.
Example of 4-variable minterms:
W.X .Y .Z W.X.Y .Z W .X .Y.Z
Maxterm
An n-variable maxterm is a normal sum term with n literals.
There are 2n such sum terms.
Examples of 4-variable maxterms:
W + X + Y + Z W + X + Y + Z W + X + Y + Z
A minterm can be defined as as product term that is 1 in exactly one row of the truth table.
A maxterm can similarly be defined as a sum term that is 0 in exactly one row in the truth table.U
~P
_d
C
= "X[ 7Minterms/Maxterms for A 3-variable function F(X,Y,Z) 87$'Row X Y Z F Minterm Maxterm
0 0 0 0 F(0,0,0) X .Y .Z X + Y + Z
1 0 0 1 F(0,0,1) X .Y .Z X + Y + Z
2 0 1 0 F(0,1,0) X .Y.Z X + Y + Z
3 0 1 1 F(0,1,1) X .Y.Z X + Y + Z
4 1 0 0 F(1,0,0) X.Y .Z X + Y + Z
5 1 0 1 F(1,0,1) X.Y .Z X + Y + Z
6 1 1 0 F(1,1,0) X.Y.Z X + Y + Z
7 1 1 1 F(1,1,1) X.Y.Z X + Y + Z h h&*
Canonical Sum RepresentationMinterm number:
minterm i refers to the minterm corresponding to row i of the truth table. For n-variables i is in the set
{0,1, & , 2n-1}
The canonical sum representation of a logic function is a sum of the minterms corresponding to the truth table rows for which the function produces a 1 output.
A short-hand representation of the minterm list uses the S notation and minterm numbers to indicate the sum of minterms of the function.
This representation is usually realized using 2-level AND-OR logic circuits with inverters at AND gates inputs as needed.
,
9M{Qw w Canonical Sum ExamplejThe function represented by the truth table:
has the canonical sum representation:
F = S X,Y,Z (0, 3, 4, 6, 7)
= X .Y .Z + X .Y.Z + X.Y .Z + X.Y .Z + X.Y.ZT-ZL Canonical Product Representation! Maxterm i refers to the maxterm corresponding to row i of the truth table. For n-variables i is in the set
{0,1, & , 2n-1}
The canonical product representation of a logic function is the product of the maxterms corresponding to the truth table rows for which the function produces a 0 output.
The product of such minterms is called a maxterm list
A short-hand representation of the maxterm list uses the P notation and maxterm numbers to indicate the product of maxterms of the function.
This representation is usually realized using 2-level OR-AND logic circuits with inverters at OR gates inputs as needed.
p1@
p g *#
Canonical Product ExampleVThe function represented by the truth table:
has the canonical product representation:
F = P X,Y,Z (1,2,5)
= (X + Y + Z ) . (X + Y + Z) . (X + Y + Z )T-]?(Conversion Between Minterm/Maxterm Lists)(,To convert between a minterm list and a maxterm list
take the set complement.
Examples:
S X,Y,Z(0,1,2,3) = P X,Y,Z(4,5,6,7)
S X,Y(1) = P X,Y(0,2,3)
S W,X,Y,Z(0,1,2,3,5,7,11,13) = P W,X,Y,Z(4,6,8,9,12,14,15)
H5T
>6rɖpb*S(
b/0DTimes New Roman$b$b0b0TbTb0DSymbolew Roman$b$b0b0TbTb0@ @@``
@n?" dd@ @@``6.<G
՜.+,0
(On-screen Show=jTimes New RomanSymbol ppoint97(Switching Algebra: Principle of Duality$Switching Algebra Axioms & Theorems1Logic Expression Algebraic Manipulation Example ,Standard Representations of Logic Functions*Logic Function Representation Definitions*Logic Function Representation Definitions8Minterms/Maxterms for A 3-variable function F(X,Y,Z)Canonical Sum RepresentationCanonical Sum Example!Canonical Product RepresentationCanonical Product Example)Conversion Between Minterm/Maxterm ListsFonts UsedDesign Template
Slide Titles"_q=
bWild PuppyZ ) (3)
Substituting A, B from (2), (3), back in F in (1) gives:
F = (A . B ) = ((X + Y ) . (X + Z ))
Which is equal to the right hand side of the identity.
82l$7(k9}W,8hbA
1:+Standard Representations of Logic Functions ,+-Truth table for n-variable logic function:
Input combinations are arranged in 2n rows in ascending binary order, and the output values are written in a column next to the rows.
Practical for functions with a small number of variables.
The general structure of a 3-variable truth table is given by:v+y)$
_9?)Logic Function Representation Definitions *) A literal: is a variable or a complement of a variable
Examples: X, Y, X , Y
A product term: is a single literal, or a product of two or more literals. Examples: Z W.Y.Y X.Y .Z W .Y .Z
A sum-of-products expression: is a logical sum of product terms.
Example: Z + W.X.Y + X.Y .Z + W .Y .Z
A sum term: is a single literal or logical sum of two or more literals
Examples: Z W + X + Y X + Y + Z W + Y + Z
A product-of-sums expression: is a logical product of sum terms.
Example: Z . (W + X + Y) . (X + Y + Z) . (W + Y + Z)
A normal term: is a product or sum term in which no variable appears more than once
Examples of non-normal terms: W.X.X.Y W+W+X +Y X.X .Y
Examples of normal terms: W . X . Y W + X + Y$:"3HPCAV
QWf 8)Logic Function Representation Definitions *)" Minterm
An n-variable minterm is a normal product term with n literals.
There are 2n such products terms.
Example of 4-variable minterms:
W.X .Y .Z W.X.Y .Z W .X .Y.Z
Maxterm
An n-variable maxterm is a normal sum term with n literals.
There are 2n such sum terms.
Examples of 4-variable maxterms:
W + X + Y + Z W + X + Y + Z W + X + Y + Z
A minterm can be defined as as product term that is 1 in exactly one row of the truth table.
A maxterm can similarly be defined as a sum term that is 0 in exactly one row in the truth table.U
~P
_d
C
= "X[ 7Minterms/Maxterms for A 3-variable function F(X,Y,Z) 87$'Row X Y Z F Minterm Maxterm
0 0 0 0 F(0,0,0) X .Y .Z X + Y + Z
1 0 0 1 F(0,0,1) X .Y .Z X + Y + Z
2 0 1 0 F(0,1,0) X .Y.Z X + Y + Z
3 0 1 1 F(0,1,1) X .Y.Z X + Y + Z
4 1 0 0 F(1,0,0) X.Y .Z X + Y + Z
5 1 0 1 F(1,0,1) X.Y .Z X + Y + Z
6 1 1 0 F(1,1,0) X.Y.Z X + Y + Z
7 1 1 1 F(1,1,1) X.Y.Z X + Y + Z h h&*
Canonical Sum RepresentationMinterm number:
minterm i refers to the minterm corresponding to row i of the truth table. For n-variables i is in the set
{0,1, & , 2n-1}
The canonical sum representation of a logic function is a sum of the minterms corresponding to the truth table rows for which the function produces a 1 output.
A short-hand representation of the minterm list uses the S notation and minterm numbers to indicate the sum of minterms of the function.
This representation is usually realized using 2-level AND-OR logic circuits with inverters at AND gates inputs as needed.
,
9M{Qw w Canonical Sum ExamplejThe function represented by the truth table:
has the canonical sum representation:
F = S X,Y,Z (0, 3, 4, 6, 7)
= X .Y .Z + X .Y.Z + X.Y .Z + X.Y .Z + X.Y.ZT-ZL Canonical Product Representation! Maxterm i refers to the maxterm corresponding to row i of the truth table. For n-variables i is in the set
{0,1, & , 2n-1}
The canonical product representation of a logic function is the product of the maxterms corresponding to the truth table rows for which the function produces a 0 output.
The product of such minterms is called a maxterm list
A short-hand representation of the maxterm list uses the P notation and maxterm numbers to indicate the product of maxterms of the function.
This representation is usually realized using 2-level OR-AND logic circuits with inverters at OR gates inputs as needed.
p1@
p g *#
Canonical Product ExampleVThe function represented by the truth table:
has the canonical product representation:
F = P X,Y,Z (1,2,5)
= (X + Y + Z ) . (X + Y + Z) . (X + Y + Z )T-]?(Conversion Between Minterm/Maxterm Lists)(,To convert between a minterm list and a maxterm list
take the set complement.
Examples:
S X,Y,Z(0,1,2,3) = P X,Y,Z(4,5,6,7)
S X,Y(1) = P X,Y(0,2,3)
S W,X,Y,Z(0,1,2,3,5,7,11,13) = P W,X,Y,Z(4,6,8,9,12,14,15)
H5T
>6r/ pa=b