Boolean switching algebra
布尔开关代数
Chapter 2
Basic concept & Binary logic function
Basic Concept
Boolean algebra (Logic algebra) is a closure
mathematical system that defines a series of
logic operation (and,or,not) performed on set
k of variables (a,b,c …) which can only have
two values of 0 or 1.
Notated as L={k,+,?,-,0,1}
Closure(封闭）
A set is closed with respect to a operator if,the
operation is applied to members of the set,the
result is also a member of the set.
Basic Concept
Commutative properties (交换律）
A+B=B+A ; AB=BA
Associative properties （结合律）
(A?B)?C=A?(B?C) ; (A+B)+C=A+(B+C)
Distributive properties（分配率）
A?(B+C)=A?B+A?C ; A+B?C=(A+B)?(A+C)
Complement properties（互补律）
A?A’=0 ; A+A’=1
Identity properties （ 0－ 1 律）
A+0=A ; A?1=A ; A+1=1 ; A?0=0
Idempotency property （等幂律）
A+A=A ; A?A=A
Absorption property（吸收律）
A+A?B=A ; A?(A+B)=A
Basic Concept
Duality property
Duals are opposites or mirror images
of original operators or constants.
Operator and dual or
Operator or dual and
Constant 1 dual 0
Constant 0 dual 1
Basic Concept
Some more important Boolean identities and
theorems for convenient referral
A+A’B=A+B ; A(A’+B)=AB
A’’=A;
(A+B)’=A’B’ ; (AB)’=A’+B’
Demorgan’s theorems
(A1+A2+…+Ai…+An)’= A1’?A2’?…?Ai’?…?An’
( A1?A2?…?Ai?…?An )’=A1’+A2’+…+Ai’+…+An’
AB+AB’=A ; (A+B)(A+B’)=A
AB+A’C+BC=AB+A’C ;
(A+B)(A’+C)(B+C)=(A+B)(A’+C)
Basic Concept
A+A’B=A+B
A+A’B
=A1+A’B (Identity)
=A(1+B)+A’B (Identity)
=A1+AB+A’B (Distributive)
=A+B(A’+A) (Distributive)
=A+B1 (identity)
=A+B
Basic Concept
AB+A’C+BC=AB+A’C ;
AB+A’C+BC
=AB+A’C+BC(A+A’)
=AB+ABC+A’C+A’CB
=AB(1+C)+A’C(1+B)
=AB1+A’C1
=AB+A’C
Basic Concept
Substitute theorems
If replacing all variable A in a logic
equation with a logic function F,the equation
would keep in equivalent,
F1(a1,a2……am)= F2(a1,a2……am) substitute
f(x1…xn) for ai,F1(a1,a2…,f,…am)=
F2(a1,a2…,f,…am)
Ex,A(B+C)=AB+AC
substitute A+D for A:
(A+D)(B+C)=(A+D)B+(A+D)C
Basic Concept
Inverse theorems
The complement of any switching function can
be found by replacing every variable with its
complement,each And with Or,and each Or with
And; constants are replaced by their complement
(0 is replaced by 1 and 1 by 0) ;the original logic
operation order should be retained.
F=G ; F’=G’
Ex,F=AB+AC
Demorgan’s theorems
F’=(AB+AC)’=(AB)’(AC)’
=(A’+B’)?(A’+C’)
Ex,F=AB+AC
Inverse theorems:
F’=A’+B’?A’+C’?
F’=(A’+B’)?(A’+C’)
Basic Concept
Dual theorems
The dual of any switching function can
be found by replacing each And with Or,and
each Or with And; constants are replaced by
their complement (0 is replaced by 1 and 1
by 0) ;and the logic operation order should
hold in original.
F=G; Fd=Gd
Ex,F=AB+AC
Fd=(A+B)?(A+C)
Basic Conceptinary logic function
AND(?)
all input variables must be true(1) for the
output to be ture(1) ; otherwise the output is
false
A two-input AND truth table
0
0
1
1
0
1
0
1
0
0
0
1
Input output
A B Z=AB &A
B
Z
A
B
Z&
Basic Conceptinary logic function
Or(+)
one input variables must be true(1) for the
output to be ture(1) ;otherwise the output is
false
A two-input Or truth table
0
0
1
1
0
1
0
1
0
1
1
1
Input output
A B Z=A+B
≥1
A
B
Z
A
B
Z
+
A
B
Z
Basic Conceptinary logic function
Not(’,-)(apostrophe,bar symbol )
inverse a variable,if the input variable,x,
is 0,the output x’ is 1;if x=1 then x’=0
A Not truth table
0
1
1
0
Input output
A Z=A’
A A’
A A’
A A’
Basic Conceptinary logic function
Nand
Function is derived from the Not and the And
A two-input Nand truth table
0
0
1
1
0
1
0
1
1
1
1
0
Input output
A B Z=(AB)’
&
A
B
Z
A
B
Z&
Basic Conceptinary logic function
Nor (Not Or)
Function is derived from the Not and the Or
A two-input Nor truth table
0
0
1
1
0
1
0
1
1
0
0
0
Input output
A B Z=(A+B)’
A
B
Z
+
A
B
Z
≥1
A
B
Z
Basic Conceptinary logic function
Ex-Or(⊕ )
An exclusive or function produce a true
output when a odd number of input variable
are true( any odd combination of 1 inputs
causes the output to be a 1)
A two-input Ex-Or truth table
0
0
1
1
0
1
0
1
0
1
1
0
Input output
A B Z=A⊕ B =1
A
B
Z
A
B Z
Z=A⊕ B=AB’+A’B
Basic Conceptinary logic function
Ex-Nor(⊙ )
An exclusive nor function produce a true
output when a even number of input variable
are true( any even combination of 0 input
cause the output to be a 1)
A two-input Ex-Nor truth table
0
0
1
1
0
1
0
1
1
0
0
1
Input output
A B Z=A⊙ B
Z=A⊙ B=AB+A’B’
=1
A
B
Z
A
B Z
Basic ConceptBinary logic function
Ex-Or vs Ex-Nor
An Ex-Nor is the
inverse of an Ex-Or
(X⊕ Y)’=X⊙ Y= X’⊙ Y’
X⊕ Y=X⊙ Y’=X’⊙ Y
(X⊕ Y⊕ Z)’
=? X⊙ Y⊙ Z
LET A=X⊕ Y,A’=X⊙ Y
(X⊕ Y⊕ Z)’=(A⊕ Z)’=A⊙ Z
=AZ+A’Z’=(A’)’(Z’)’+A’Z’
=A’ ⊙ Z’
= X⊙ Y⊙ Z’≠ X⊙ Y⊙ Z
A= X⊕ Y⊕ Z
B= X⊙ Y⊙ Z
C= X⊙ Y⊙ Z’
0
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
0
1
Input output
X Y Z A B C
0
0
1
1
0
0
1
1
0
1
1
0
1
0
0
1
1
0
0
1
0
1
1
0
Basic ConceptBinary logic function
(X1⊕ X2⊕ X3⊕ X4)’ =? X1⊙ X2⊙ X3⊙ X4
LET A1=X1⊕ X2,A2=X3⊕ X4
(X1⊕ X2⊕ X3⊕ X4)’= A1⊙ A2
= (X1’⊙ X2) ⊙ (X3’⊙ X4)
= X1’⊙ X2⊙ X3’⊙ X4
= (X1’⊙ X3’)⊙ X2 ⊙ X4
= X1⊙ X3⊙ X2 ⊙ X4= X1⊙ X2⊙ X3 ⊙ X4
In what condition
(X1⊕ X2⊕ ……⊕ Xn)’ = X1⊙ X2⊙ ……⊙ Xn
X1⊕ X2⊕ ……⊕ Xn = X1⊙ X2⊙ ……⊙ Xn