Switching Algebra
Logic
What is a logical argument?
an argument that is true by virtue of its form; i.e. if
premises true conclusion must be true
Positive example
P1) All men are mortal
P2) Harry is a man
------
C) Therefore, Harry is mortal
Negative examples
P1) If I study hard in 200, I will get an A.
P2) I got an A in 200.
------
C) Therefore, I studied hard.
P1) Katz believes that 200 is easy.
P2) Katz is a dufus.
------
C) Therefore, 200 is difficult.
In the mid-19th century, Boole formalized logic.
We will be studying a subset of formal logic known as
the propositional calculus.
Switching Algebra
Axioms of the propositional calculus
(1) All variables must take one of the values 0 or 1
(2) Rules for not
X X’
------
01
10
(3) Rules for and
X YX · Y
------
000
010
100
111
(4) Rules for or
X YX + Y
------
000
011
101
111
Switching Algebra
Theorems of the propositional calculus
theoremdualname
(T1)X + 0 = XX · 1 = Xidentity
(T2)X + 1 = 1X · 0 = 0null elements
(T3)X + X = XX · X = Xidempotency
(T4) (X’)’ = X(X’)’ = Xinvolution
(T5) X + X’ = 1X · X’ = 0complement
(T6) X + Y = Y + XX · Y = Y · X commutativity
(T7) (X + Y) + Z = X + (Y + Z)(X + Y) + Z = X + (Y + Z)associativity
(T8) X · Y + X · Z = X · (Y + Z)(X + Y) · (X + Z) = X + Y · Zdistributivity
(T9)(X · Y)’ = X’ + Y’(X + Y)’ = X’ · Y’DeMorgan’s
Proof by truth table
Fact
All theorems of the pc can be proven with a truth table, i.e., by
systematically examining every case and showing that the
theorem hold for these cases (this method also is known as
perfect induction).
Examples
Prove (T5):
XX’X + X’
011
101
Prove the dual of (T9):
XYX + Y(X + Y)’X’Y’X’ · Y’
0001111
0110100
1010010
1110000
Switching Algebra
Proof by simplification
Method
Successive application of previously proven theorems to produce
a shorter expression
Example
Prove T9:X + X · Y = X
X + X · Y = X · 1 + X · Y(T1 dual)
= X · (1 + Y)(T8)
= X · 1(T2)
= X(T1 dual)
Advantages and disadvantages
advantage - no need to provide destination
disadvantage - need to choose among existing theorems
Duality
Principle
Any theorem or identity remains true if 0 and 1 are swapped and
· and + are swapped throughout.
Generalized DeMorgan
[F(X1, X2, .... Xn)]’ = FD(X1’, X2’, .... Xn’)
Switching Algebra
Minterm and Maxterm representations of a function
row#XYZmintermmaxterm
0000X’Y’Z’X+Y+Z
1001X’Y’ZX+Y+Z’
2010X’YZ’X+Y’+Z
301 1X’YZX+Y’+Z’
4100XY’Z’X’+Y+Z
5101X’YZ’X+Y’+Z
6110XYZ’X’+Y’+Z
7111XYZX’+Y’+Z’
Principle
A function can be represented as
a) the sum of the minterms where the function is true, OR
b) the product of the maxterms where the function is false
Example
F = X’ + YZ
row#XYZmintermmaxtermF
0000X’Y’Z’X+Y+Z1
1001X’Y’ZX+Y+Z’1
2010X’YZ’X+Y’+Z1
301 1X’YZX+Y’+Z’1
4100XY’Z’X’+Y+Z0
5101X’YZ’X+Y’+Z0
6110XYZ’X’+Y’+Z0
7111XYZX’+Y’+Z’1
minterm representation
X,Y,Z(0,1,2,3,7) = X’Y’Z’ + X’Y’Z + X’YZ’ + X’YZ + XYZ
maxterm representation
X,Y,Z(4,5,6) = (X’+Y+Z) (X+Y’+Z) (X’+Y’+Z)
Switching Algebra
Why are minterm and maxterm representations equivalent?
a) [X,Y,Z(i,j...n)]’ = X,Y,Z(i,j...n)
b) but, X,Y,Z(i,j...n) is just the inverse of X,Y,Z(p,q,..r),
where p,q,..r are the complement of i,j,..n
c) therefore, by the principle of double negation,
X,Y,Z(i,j...n) = X,Y,Z(p,q,..r)
Terminology review
There are two equivalent representations of a function:
i)X,Y,Z
sum of minterms
sum of products (SOP)
ii) X,Y,Z
product of maxterms
product of sums (POS)
Combinational-Circuit Analysis
Basic gates
And gate
Or gate
Not gate
Combinational-Circuit Analysis
Truth Table from Circuit
Examples
easy
harder