INTRODUCTION
INTRODUCTION
Developed by English
Mathematician George Boole in
between 1815 - 1864.
It is described as an algebra of
logic or an algebra of two values
i.e True or False.
The term logic means a
statement having binary
decisions i.e True/Yes or False/No.
APPLICATION OF BOOLEAN
ALGEBRA
APPLICATION OF BOOLEAN
ALGEBRA
• It is used to perform the logical
operations in digital computer.
• In digital computer True represent by
‘1’ (high volt) and False represent by
‘0’ (low volt)
• Logical operations are performed by
logical operators. The fundamental
logical operators are:
1. AND (conjunction)
2. OR (disjunction)
3. NOT (negation/complement)
AND operator
It performs logical multiplication
and denoted by (.) dot.
XY X.Y
00 0
01 0
10 0
11 1
OR operator
It performs logical addition
and denoted by (+) plus.
XY X+Y
0 0 0
0 1 1
1 0 1
1 1 1
NOT operator
It performs logical
negation and denoted by (-)
bar. It operates on single
variable.
X X (means complement of x)
0 1
1 0
Truth Table
• Truth table is a table that
contains all possible values of
logical variables/statements in a
Boolean expression.
No. of possible combination =
2n, where n=number of variables
used in a Boolean expression.
Truth Table
The truth table for XY + Z is as
follows:
Dec X Y Z XY XY+Z
0 0 0 0 0 0
1 0 0 1 0 1
2 0 1 0 0 0
3 0 1 1 0 1
4 1 0 0 0 0
5 1 0 1 0 1
6 1 1 0 1 1
7 1 1 1 1 1
Tautology & Fallacy
If the output of
Boolean expression is
always True or 1 is called
Tautology.
If the output of Boolean
expression is always False
or 0 is called Fallacy.
Exercise
1. Evaluate the following
Boolean expression using
Truth Table.
(a) X’Y’+X’Y (b) X’YZ’+XY’
(c) XY’(Z+YZ’)+Z’
2. Verify that P+(PQ)’ is a
Tautology.
3. Verify that (X+Y)’=X’Y’
Implementation
Boolean Algebra applied in
computers electronic circuits.
These circuits perform Boolean
operations and these are called
logic circuits or logic gates.
Logic Gate
Logic Gate
A gate is an digital circuit
which operates on one or more
signals and produce single
output.
Gates are digital circuits
because the input and output
signals are denoted by either
1(high voltage) or 0(low
voltage).
Logic Gate
There are three basic gates
and are:
[Link] gate [Link] gate
[Link] gate
AND gate
AND gate
• The AND gate is an electronic
circuit that gives a high output
(1) only if all its inputs are high.
• AND gate takes two or more
input signals and produce only
one output signal.
Input Input Outp
A B ut
AB
0 0 0
0 1 0
1 0 0
1 1 1
OR gate
OR gate
• The OR gate is an electronic circuit
that gives a high output (1) if one or
more of its inputs are high.
• OR gate also takes two or more input
signals and produce only one output
signal.
Input Input Outp
A B ut
A+B
0 0 0
0 1 1
1 0 1
NOT gate
NOT gate
• The NOT gate is an electronic
circuit that gives a high output
(1) if its input is low .
• NOT gate takes only one input
signal and produce only one
output signal.
• The output of NOT gate is
complement of its input.
• It is also called inverter.
• NOT gate
Input A Output
A
0 1
1 0
PRACTICAL APPLICATIONS OF LOGIC
GATES
PRACTICAL APPLICATIONS OF LOGIC GATES
AND Gate
So while going out of the house
you set the "Alarm Switch" and if
the burglar enters he will set the
"Person switch", and the alarm
PRACTICAL APPLICATIONS OF LOGIC
GATES
AND Gate
Electronic door will only
open if it detects a person
and the switch is set to
unlocked.
Microwave will only start if
the start button is pressed
and the door close switch is
closed.
PRACTICAL APPLICATIONS OF LOGIC GATES
OR Gate
You would of course want your
doorbell to ring when someone
presses either the front door
PRACTICAL APPLICATIONS OF LOGIC GATES
NOT Gate
When the temperature falls below
20c the Not gate will set on the
central heating system (cool huh).
NAND, NOR XOR, XNOR
GATES
NAND Gate
Known as a “universal”
gate because ANY digital
circuit can be implemented
with NAND gates alone.
NAND Gate
NAND
X Y Z
X 0 0 1
Z 0 1 1
Y 1 0 1
1 1 0
Z = ~(X & Y)
nand(Z,X,Y)
NAND Gate
F = (X•X)’ X F = X’
X
= X’+X’
= X’
X X F
F= ((X•Y)’)’
Y Y X•Y
= (X’+Y’)’
= X’’•Y’’
= X•Y
X X
F = (X’•Y’)’ F=
= X’’+Y’’ X+Y
Y Y
= X+Y
NOR Gate
NOR Gate
NOR
X Y Z
X 0 0 1
Z
Y 0 1 0
1 0 0
Z = ~(X | Y)
1 1 0
nor(Z,X,Y)
Exclusive-OR Gate
Exclusive-OR Gate
XOR X Y Z
X Z
Y 0 0 0
Z=X^Y 0 1 1
1 0 1
xor(Z,X,Y) 1 1 0
Exclusive-NOR Gate
Exclusive-NOR Gate
XNOR X Y Z
X Z
Y 0 0 1
0 1 0
Z = ~(X ^ Y) 1 0 0
Z = X ~^ Y 1 1 1
xnor(Z,X,Y)
Basic Theorem of Boolean Algebra
T1 : Properties of 0
(a) 0 + A = A
(b) 0 A = 0
T2 : Properties of 1
(a) 1 + A = 1
(b) 1 A = A
Basic Theorem of Boolean Algebra
T3 : Commutative Law
(a) A + B = B + A
(b) A B = B A
T4 : Associate Law
(a) (A + B) + C = A + (B + C)
(b) (A B) C = A (B C)
T5 : Distributive Law
(a) A (B + C) = A B + A C
(b) A + (B C) = (A + B) (A + C)
(c) A+A’B = A+B
Basic Theorem of Boolean Algebra
T6 : Indempotence (Identity )
Law
(a) A + A = A
(b) A A = A
T7 : Absorption
(Redundance) Law
(a) A + A B = A
(b) A (A + B) = A
Basic Theorem of Boolean Algebra
T8 : Complementary Law
(a) X+X’=1
(b) X.X’=0
T9 : Involution
(a) x’’ = x
T10 : De Morgan's Theorem
(a) (X+Y)’=X’.Y’
(b) (X.Y)’=X’+Y’
Examples
:
(a) a + ab = a(1+b)=a
(b) a(a + b) = a.a +ab=a+ab=a(1+b)=a.
(c) a + a'b = (a + a')(a + b)=1(a + b) =a+b
(d) a(a' + b) = a. a' +ab=0+ab=ab
Show that;
1. ab + ab' = a
2. (a + b)(a + b') = a
3. XY + YZ + Y’ Z = XY + Z
Find the complement of the expression: X + YZ
Find the complement of A’ B + C D’ ,
(b) AB +CD = 0
Simplify the Boolean expressions:
(X +Y) ( X+ Y’ ) ( X’ +Z)
XYZ + X Y’ Z + XY Z’
Minimize the following expression by use of Boolean
rules.
X = A B C + A’ B + A B C’
X = A’ B C’ + A B’ C’ + A’ B’ C’ + A’ B’ C’
AB + A’ C + B C = AB + A’ C
(A + B) ( A’ + C) (B + C) =(A + B) ( A’ + C)
X = AB + ABC + A B’ C’ + A C’
(a) Draw the logic diagram for the expression.
(b) Minimize the expression.
(c) Draw the logic diagram for the reduced expression.
X = AB + ABC + A B’ C’ + A C’
(a) Draw the logic diagram for the expression.
(b) Minimize the expression.
(c) Draw the logic diagram for the reduced expression.
Show that;
1- ab + ab' = a
2- (a + b)(a + b') = a
1- ab + ab' = a(b+b') = a.1=a
2- (a + b)(a + b') = a.a +a.b' +a.b+b.b'
= a + a.b' +a.b + 0
= a + a.(b' +b) + 0
= a + a.1 + 0
= a +a=a
Function Minimization using Boolean
Algebra
Examples:
(a) a + ab = a(1+b)=a
(b) a(a + b) = a.a +ab=a+ab=a(1+b)=a.
(c) a + a'b = (a + a')(a + b)=1(a + b) =a+b
(d) a(a' + b) = a. a' +ab=0+ab=ab
De Morgan's Theorem
De Morgan's Theorem 1
Theorem 1 A . B = A + B
De Morgan's Theorem 1
Theorem 1 A . B = A + B
De Morgan's Theorem 1
Theorem 1 A . B = A + B
De Morgan's Theorem 2
Theorem 1 A + B = A . B
De Morgan's Theorem 2
Theorem 2 A + B = A . B
De Morgan's Theorem 2
Theorem 2 A + B = A . B
De Morgan's Theorem 2
Theorem 2 A + B = A . B
Thank You