BOOLEAN ALGEBRA
OBJECTIVES
1.
To understand the use of switching circuits,
and boolean algebra
2.
To obtain Karnaugh
maps from logical function and vice versa.
BOOLEAN ALGEBRA
BOOLE
is one of the persons in a long historical chain who were concerned with formalizing
and mechanizing the process of logical thinking.
BOOLEAN
ALGEBRA is a generalization of set algebra and the algebra of propositions.
Boolean
Algebra is a tool for studying and applying logic.
. We learn how
BOOLEAN algebra is used to construct and simplify electric
circuits. Switching circuits, which are used in the design of computer chips,
are introduced with
a discussion of the techniques needed to simplify their design.
. We also show
how a purely algebraic approach to some parts of logic is possible by using
BOOLEAN Algebras and how this technique can also be used to study set theory.
Definition:
Boolean
Algebra is an algebraic structure defined on a set
of elements is together with two binary operations, the product (or meet)
and the sum (or join) provided the following Hunthington
postulates are satisfied:
1. a. Closure with respect to the operator
+
b. Closure with respect to the operator
x
2. a. An identity
element with respect to + is 0
x + 0 = 0 + x
b. An identity element with respect
to . is 1
x .
1 = 1 . x = x
3. a. Commutative with respect to +
x + y = y + x
b. Commutative
with respect to .
x .
y = y . x
4.
a. .
is distributive over +
x(y + z) =
xy + xz
b. + is distributive over .
x + (yz)
= (x + y)(x + z)
5.
For every element x
B, there exists an element x'
B (complement of x) such that:
a. x + x' = 1
b. x . x' = 0
6.
There exists at least two elements
x, y
B such that x = y.
Example:
Show
that the algebra of subsets of a set and the algebra of propositions are Boolean
algebras.
Solution:
* let S be any set and K = P(S) be the power set ( and the set
of all subsets ) of S. Then K is the Boolean algebra, where the meet
is the intersection of two sets; the join is the union of two sets;
the Boolean complement is the complement of a set
; the zero element is the empty se; the unit is S.
* Let L be the
set of all propositions. Then L is a boolean algebra,
where the meet is the conjuction of two propositions;
the join is the disjunction of two propositions; the boolean complement is the
negation of a proposition; the zero element is a proposition F that
is always false; the unit element is a propostion
T that is always true.
Two Valued Boolean
Algebra:
A
two valued Boolean Algebra is defined on a set of two elements, B = { 0, 1 }, with rules for the two binary operators + and .
|
x
|
y
|
xy
|
|
0
|
0
|
0
|
|
0
|
1
|
0
|
|
1
|
0
|
0
|
|
1
|
1
|
1
|
|
x
|
y
|
x+y
|
|
0
|
0
|
0
|
|
0
|
1
|
1
|
|
1
|
0
|
1
|
|
1
|
1
|
1
|
These
rules are exactly the same as the AND, OR, & NOT operations, respectively.
Now
show that the Hunthington postulates are valid for
the set B
= { 0, 1 } and the two binary operators defined above.
1. Closure
The
result of each operation is 1 or 0 and 1, 0
B.
2. From the table
an identity element with respect
to + is 0, since 0 + 0 = 0
0 + 1 = 1 + 0 = 1
An
identity element with respect to . is
1,
since 1.1
= 1
1.0 = 0.1 = 0
3. Commutative law
0 + 1 = 1 + 0 = 1 (
for + )
0 . 1 = 1 . 0 = 0 ( for . )
4. Distributive law
a. . is distributive over + : x ( y
+ z ) = xy + xz
b. + is distributive
over . : x + ( y. z) = (x
+ y) . (x + z)
|
x
|
y
|
z
|
y+z
|
x.(y+z)
|
x.y
|
x.z
|
xy + xz
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
5. From the complement table,
a. x + x' = 1 since
0 + 0' = 0 + 1 = 1
1
+ 1' = 1 + 0 = 1
b. x . x' = 0 since 0 . 0'
= 0 . 1 = 0
1 . 1 ' = 1. 0 = 0
6. Two valued boolean algebra has two distinct
elements 1 and 0.
Theorems and
Properties of Boolean Algebra:
Theorem 1:
a. x + x = x
proof:
x
+ x =
( x + x ) . 1 by
postulate (2b)
= ( x + x ) (x + x')
= (x + xx')
= x + 0
= x
b. x . x = x
proof:
x . x = x. x + 0
=
x .
x + x . x'
= x (x + x')
= x . 1
= x
Theorem 2:
a. x + 1 = 1
proof:
x
+ 1 =
1 . ( x + 1)
=
( x + x' )( x + 1)
=
x + x' . 1
=
x + x'
=
1
b.
x.0 = 0 by duality
Theorem 3:
(x')' = x
Theorem 4:
a. x + ( y + z ) = ( x + y ) + z associative
b. x ( yz ) = ( xy ) z associative
Theorem 5: ( De Morgan )
a. ( x + y )' = x' y'
b. ( xy )' = x' + y'
proof:
|
x
|
y
|
x+y
|
(x+y)'
|
x'
|
y'
|
x'y'
|
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
Theorem 6: (Absorption)
a. x + xy = x
proof:
x
+ xy = x.1 + xy by postulate 2 (b)
= x (1 + y) by
postulate 4 (a)
= x ( y + 1 ) by postulate 3 (a)
= x . 1 by theorem 2 (a)
= x by
postulate 2(b)
b. x ( x + y ) = x
proof:
|
x
|
y
|
xy
|
x+xy
|
|
0
|
0
|
0
|
0
|
|
0
|
1
|
0
|
0
|
|
1
|
0
|
0
|
1
|
|
1
|
1
|
1
|
1
|
Operator
precedence for evaluating the boolean
expression is:
1. First the expressions
inside parentheses must be evaluated.
2. Complement ( NOT )
3. AND
4. OR
BOOLEAN FUNCTIONS:
A
binary variable can take the value of 0 and 1.
A
boolean function is an expression formed with binary
variables, the two binary operators OR and AND, the
unary operator NOT, parentheses, equal sign.
For
a given value of the variables, the function can be either 0 or 1.
Example:
F1
= xyz'
F1
= 1 if x = 1 and y = 1 and z' = 1;
otherwise F1 = 0
A
Boolean function may also be represented in a truth table.
to represent a function in a truth table, we need 2n combimations of 1's and 0's of the n binary variables.
F2
= x + y'z
F2
= 1 if x = 1 or if y = 0, while z = 1
F3
= x'y'z + x'yz + xy'
F4
= xy' + x'z
|
x
|
y
|
z
|
F1
|
F2
|
F3
|
F4
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
The
number of rows : 2n ( n = number of binary
variables)
A
boolean function may be
transformed from an algebraic expression into a logic diagram composed of
AND, OR, NOT gates.
Example:
Simplify
the boolean functions to
a minimum number of literals.
1. x + x'y = ( x + x' ) ( x + y ) =
1.( x + y ) = x + y
2. x ( x' + y ) = xx' + xy = 0 + xy = xy
3. x'y'z + x'yz
+ xy' = x'z (y' + y) +
xy' = x'z + xy'
4. xy + x'z
+ yz = xy + x'z + yz ( x + x' )
= xy + x'z + xyz + x'yz
= xy ( 1 + z ) + x'z ( 1 + y )
= xy + x'z
5. ( x + y ) (
x'z ) ( y + z ) = ( x + y ) ( x' + z )
Complement of
a Function:
( A + B + C )' = ( A + X )' let B + C = X
= A' X ' De
Morgan thm 5a
= A' ( B + C )'
= A' . ( B'
C' ) De Morgan
thm. 5a
= A ' B ' C '
Example:
Find
the complement of the functions.
F1
= x' yz' + x'y'z and F2
= x ( y'z' + yz
)
F1' =
( x' y z' + x' y' z )'
=
( x' y z' )' ( x' y' z )'
=
( x + y' + z ) ( x + y + z' )
F2'
=
[ x ( y' z' + yz ) ]'
=
x' + ( y'z' + yz )'
=
x' + ( y'z' )' .
( yz )'
=
x' + ( y + z )
( y' + z' )
Example:
Find
the complement of the functions F1 and F2 by taking their duals and complementing
each literal.
F1
= x'yz' + x' y' z
The
dual of F1 is : ( x' + y + z' ) ( x' + y' + z )
Complement
each literal : F1' = ( x + y' + z ) ( x + y + z'
)
F2
= x ( y' z' + yz )
The
dual of F2 is x + ( y' + z' ) ( y + z )
Complement
each literal: F2' = x' + ( y + z ) ( y' + z' )
CANONICAL AND
STANDARD FORMS:
Minterms and Maxterms:
A
binary variable may appear in its normal form(x)
or in its
complement form ( x' )
Two
binary variables x and y combined with an AND operation.
.
Four possible combinations : x'y'
x'y