Boolean switching algebra
Chapter 2
Describe switching function
A function is a term used in mathematics
and logic to denote a relationship
between input and output variables.
Each variable is restricted to binary (0,1)
values
The relationship is the complex of three
primitive functions (And\Not\Or)
Describe a switching function
Truth table
Switching equation (logic equation)
Logic diagram
Karnaugh maps
They are equivalent in function.
Truth table
A tabular representation of the
combinations that a group of binary
input and output variables can assume
It illustrates all of the input variable
combination values and the output
variables values.
Number of combinations = 2input
0
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
1
1
Input output
A B C F
0
0
1
1
0
0
1
1
Input A,B,C ;
Output F
F=1
(0,1,1)
(1,0,0)
(1,1,0)
(1,1,1)
Switching equation
A switching equation defines the relationship
between an output variable and a set of input
variables
The expression composed of logic variables
and the three primitive operator [and,or,not]
F(A,B,C)=AB+AB’C’+A’BC
F(A,B,C)=AB+AB’C’+A’BC00
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
1
1
Input output
A B C F
0
0
1
1
0
0
1
1
Literal
A literal is a Boolean variable or its complement
Product term
A product term is a literal or the logical product
(AND) of multiple literals
Sum term
A sum term is a literal or the logical OR of
multiple literals
Sum of products (SOP)
A SOP is the logical OR of multiple product terms,
Each product term is the AND of binary literal
Product of sums (POS)
A POS is the logical AND of multiple product
terms,Each sum term is the OR of binary literal,
Minterms
A minterm is a special case product
terms that contains all of the input
variables (each literal no more than once)
that make up a Boolean expression.
A more concise format for writing a minterm
is mi.
Subscript i is a decimal number produced by
encoding the minterm to a binary sequence,‘1’
represents the original variable,and ‘0’ is
the complement.
Minterm
Each minterm has one and only one input variable
combination meeting the its value 1,And the
combinations is different by the minterms.
The product of mi and mj is 0,if the subscript i
is not equal to j.
One n-variable minterm has n adjacent minterms,
where only one variable changes between them,
The sum of all minterms consisting of the common
n literals is constant 1.
1
12
=∑
－
i=0 i
n
m
Maxterms
A maxterm is a special case sum terms
that contains all of the input variables
(each literal no more than once) that
make up a Boolean expression
A more concise format for writing a maxterm
is Mi.
Subscript i is a decimal number produced by
encoding the maxterm to a binary sequence,‘0’
represents the original variable,and ‘1’ is the
complement,
Maxterm
Each maxterm has one and only one input
variable combination meeting the its value 0,And
the combinations is different by the maxterms.
The sum of Mi and Mj is 1,if the subscript i is
not equal to j.
One n-variable maxterm has n adjacent maxterms,
where only one variable changes between them,
The product of all maxterms constructed by the
common n literals is constant 0.
0
12
=∏
－
i=0 i
n
M
Mi vs mi
A Maxterm is the complement
of a Minterm with the same
subscript and literals.
Mi = mi’
Canonical forms
Canonical sum of products
It is a complete set of minterms that
defines when a output variable is a
logic 1,
Each minterm corresponds to the row
in the truth table where the output is
a 1,
Canonical forms
Canonical product of sums
It is a complete set of maxterms
that defines when a output variable is
a logic 0,
Each maxterm corresponds to the
row in the truth table where the
output is a 0,
Ex,F(A,B,C)=AB+AB’C’+A’BC
F=Σm(3,4,6,7)
=A’BC+AB’C’+ABC’+ABC
F=ΠM(0,1,2,5)
=(A+B+C)(A+B+C’)(A+B’+C)(A’+B+C’)
Place a equation into canonical form
0
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
1
1
Input output
A B C F
0
0
1
1
0
0
1
1
Each maxterm corresponds to the row in
the truth table where the output is a 0.
Each minterm corresponds to the row in
the truth table where the output is a 1.
Place a SOP equation into canonical form
1,Identify the missing variable(s) in each AND term
2,AND the missing term and its complement with
the original AND term,xy=xy(z+z’)
3,Expand the term by application of the property
of distribution,xy(z+z’)=xyz+xyz’
Ex,F(A,B,C)=AB+AB’C’+A’BC
=AB(C+C’)+AB’C’+A’BC
=ABC+ABC’+AB’C’+A’BC
Place a POS equation into canonical form
1,Identify the missing variable(s) in each OR term
2,OR the missing term and its complement with
the original OR term,x+y=x+y+zz’
3,Expand the term by application of the property
of distribution,x+y+zz’ =(x+y+z)(x+y+z’)
Ex,F(A,B,C)=(A+C)(B+C’)
=(A+C+BB’)(AA’+B+C’)
=(A+B+C)(A+B’+C)(A+B+C’)(A’+B+C’)
Logic diagram
F(A,B,C)=AB+AB’C’+A’BC
&
A
F
B
C
&
&
+
Inverting bubbles on the
inputs of logic gate indicate
the inversion of the input
variable
Reduction of switching
equations
using Boolean algebra
F(A,B,C)=AB+AB’C’+A’BC
&
A
F
B
C
&
&
+
Any variables or terms in a switching
equation that a redundant should be
eliminated,Because they add cost to the
circuit.
Absorption properties
AB+A’B=A ; (A+B)(A’+B)=A
A+A’B=A+B ; A(A’+B)=AB
AB+A’C+BC=AB+A’C ;
(A+B)(A’+C)(B+C)=(A+B)(A’+C)
Ex,
F=(AB+BC+CA)’+ABC’
=(AB)’(BC)’(AC)’+ABC’
=((AB)’+ABC’)(B’+C’+ABC’)(A’+C’+ABC’)
=((AB)’+C’)(B’+C’)(A’+C’)
=(A’+B’+C’)(B’+C’)(A’+C’)
=(B’+C’)(A’+C’)
=A’B’+C’
Chapter 2
Describe switching function
A function is a term used in mathematics
and logic to denote a relationship
between input and output variables.
Each variable is restricted to binary (0,1)
values
The relationship is the complex of three
primitive functions (And\Not\Or)
Describe a switching function
Truth table
Switching equation (logic equation)
Logic diagram
Karnaugh maps
They are equivalent in function.
Truth table
A tabular representation of the
combinations that a group of binary
input and output variables can assume
It illustrates all of the input variable
combination values and the output
variables values.
Number of combinations = 2input
0
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
1
1
Input output
A B C F
0
0
1
1
0
0
1
1
Input A,B,C ;
Output F
F=1
(0,1,1)
(1,0,0)
(1,1,0)
(1,1,1)
Switching equation
A switching equation defines the relationship
between an output variable and a set of input
variables
The expression composed of logic variables
and the three primitive operator [and,or,not]
F(A,B,C)=AB+AB’C’+A’BC
F(A,B,C)=AB+AB’C’+A’BC00
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
1
1
Input output
A B C F
0
0
1
1
0
0
1
1
Literal
A literal is a Boolean variable or its complement
Product term
A product term is a literal or the logical product
(AND) of multiple literals
Sum term
A sum term is a literal or the logical OR of
multiple literals
Sum of products (SOP)
A SOP is the logical OR of multiple product terms,
Each product term is the AND of binary literal
Product of sums (POS)
A POS is the logical AND of multiple product
terms,Each sum term is the OR of binary literal,
Minterms
A minterm is a special case product
terms that contains all of the input
variables (each literal no more than once)
that make up a Boolean expression.
A more concise format for writing a minterm
is mi.
Subscript i is a decimal number produced by
encoding the minterm to a binary sequence,‘1’
represents the original variable,and ‘0’ is
the complement.
Minterm
Each minterm has one and only one input variable
combination meeting the its value 1,And the
combinations is different by the minterms.
The product of mi and mj is 0,if the subscript i
is not equal to j.
One n-variable minterm has n adjacent minterms,
where only one variable changes between them,
The sum of all minterms consisting of the common
n literals is constant 1.
1
12
=∑
－
i=0 i
n
m
Maxterms
A maxterm is a special case sum terms
that contains all of the input variables
(each literal no more than once) that
make up a Boolean expression
A more concise format for writing a maxterm
is Mi.
Subscript i is a decimal number produced by
encoding the maxterm to a binary sequence,‘0’
represents the original variable,and ‘1’ is the
complement,
Maxterm
Each maxterm has one and only one input
variable combination meeting the its value 0,And
the combinations is different by the maxterms.
The sum of Mi and Mj is 1,if the subscript i is
not equal to j.
One n-variable maxterm has n adjacent maxterms,
where only one variable changes between them,
The product of all maxterms constructed by the
common n literals is constant 0.
0
12
=∏
－
i=0 i
n
M
Mi vs mi
A Maxterm is the complement
of a Minterm with the same
subscript and literals.
Mi = mi’
Canonical forms
Canonical sum of products
It is a complete set of minterms that
defines when a output variable is a
logic 1,
Each minterm corresponds to the row
in the truth table where the output is
a 1,
Canonical forms
Canonical product of sums
It is a complete set of maxterms
that defines when a output variable is
a logic 0,
Each maxterm corresponds to the
row in the truth table where the
output is a 0,
Ex,F(A,B,C)=AB+AB’C’+A’BC
F=Σm(3,4,6,7)
=A’BC+AB’C’+ABC’+ABC
F=ΠM(0,1,2,5)
=(A+B+C)(A+B+C’)(A+B’+C)(A’+B+C’)
Place a equation into canonical form
0
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
1
1
Input output
A B C F
0
0
1
1
0
0
1
1
Each maxterm corresponds to the row in
the truth table where the output is a 0.
Each minterm corresponds to the row in
the truth table where the output is a 1.
Place a SOP equation into canonical form
1,Identify the missing variable(s) in each AND term
2,AND the missing term and its complement with
the original AND term,xy=xy(z+z’)
3,Expand the term by application of the property
of distribution,xy(z+z’)=xyz+xyz’
Ex,F(A,B,C)=AB+AB’C’+A’BC
=AB(C+C’)+AB’C’+A’BC
=ABC+ABC’+AB’C’+A’BC
Place a POS equation into canonical form
1,Identify the missing variable(s) in each OR term
2,OR the missing term and its complement with
the original OR term,x+y=x+y+zz’
3,Expand the term by application of the property
of distribution,x+y+zz’ =(x+y+z)(x+y+z’)
Ex,F(A,B,C)=(A+C)(B+C’)
=(A+C+BB’)(AA’+B+C’)
=(A+B+C)(A+B’+C)(A+B+C’)(A’+B+C’)
Logic diagram
F(A,B,C)=AB+AB’C’+A’BC
&
A
F
B
C
&
&
+
Inverting bubbles on the
inputs of logic gate indicate
the inversion of the input
variable
Reduction of switching
equations
using Boolean algebra
F(A,B,C)=AB+AB’C’+A’BC
&
A
F
B
C
&
&
+
Any variables or terms in a switching
equation that a redundant should be
eliminated,Because they add cost to the
circuit.
Absorption properties
AB+A’B=A ; (A+B)(A’+B)=A
A+A’B=A+B ; A(A’+B)=AB
AB+A’C+BC=AB+A’C ;
(A+B)(A’+C)(B+C)=(A+B)(A’+C)
Ex,
F=(AB+BC+CA)’+ABC’
=(AB)’(BC)’(AC)’+ABC’
=((AB)’+ABC’)(B’+C’+ABC’)(A’+C’+ABC’)
=((AB)’+C’)(B’+C’)(A’+C’)
=(A’+B’+C’)(B’+C’)(A’+C’)
=(B’+C’)(A’+C’)
=A’B’+C’
