Transcript BOOLEAN ALGEBRA

BOOLEAN ALGEBRA
LOGIC GATES
Introduction
British mathematician George Boole(1815-1864)
was successful in finding the link between logic
and mathematics. Boolean Algebra is
fundamentally important in the design of circuits
used in computers.
•
•
•
•
Boolean Algebra
In Boolean Algebra , elements have one
of two values –True or False.
The circuits in a computer are also
designed for two-state operations.
That is input and output of a circuit is
either low(0) or high(1).
The circuits are called logic circuits.
BOOLEAN VARIABLES
• The variables in Boolean Algebra
can take only two values- True or
false.
• The variables are called Boolean
variables.
Boolean Operators
•
There are three basic operators in Boolean
Algebra which are called logical operators or
Boolean operators.
OR - logical addition
AND – logical multiplication
NOT – Logical negation
• The Boolean operators are used to combine
Boolean variables and Boolean constants to
form Boolean Expressions.
TRUTH TABLES
• A truth table is a table that represents
the possible values of the operands and
corresponding values of a Boolean
operation or a Boolean expressions.
• Boolean expression with ‘n’ number of
variables , the truth table will have 2n
rows.
LOGIC GATES
• A logic gate is an electronic circuit
which makes logic decisions.
• A logic gate takes one or more inputs
and will produce only one output.
• Logic gates are the building blocks
from which most of the digital
systems are built up.
• The three basic logical operators are
OR,AND and NOT
• They are said to be logically complete as
any Boolean function can be realized in
terms of these connectives .
• Gate used to implement these logical
operators are known as basic logic
gates.
OR Operation
• Boolean expression for the OR
operation:
x =A + B
• The above expression is read as
“x equals A OR B”
OR Gate
• An OR gate is a gate that has two or
more inputs and whose output is equal
to the OR combination of the inputs.
AND Gate
• The and gate is a logic circuit which
accepts two or more input signals but
produces only one output signal.
• The output signal produced will be 1
only if all input signals are 1
otherwise it will be 0.
AND Operation
• Boolean expression for the AND
operation:
x =A B
• The above expression is read as
“x equals A AND B”
AND Gate
• An AND gate is a gate that has two
or more inputs and whose output is
equal to the AND product of the
inputs.
NOT Gate
• The NOT gate is a logic circuit which
will accept only one input signal .
• The output state produced by NOT
gate will be always the opposite of
the input signal
• Hence it is called the inverter.
NOT Operation
• The NOT operation is an unary operation,
taking only one input variable.
• Boolean expression for the NOT operation:
x= A
• The above expression is read as “x equals the
inverse of A
• Also known as inversion or complementation.
• Can also be expressed as: A’
Boolean Theorems
(Single-Variable)
•
•
•
•
•
•
•
•
x* 0 =0
x* 1 =x
x*x=x
x*x’=0
x+0=x
x+1=1
x+x=x
x+x’=1
Boolean theorems
(multivariable)
•
•
•
•
•
X Y=YX
X+(Y+Z)=(X+Y)+Z
X(YZ)=(XY)Z
X(Y+Z)=XY+XZ
(X’)’=X
DeMorgans law
1
(A.B)’= A’+ B’
2
(A+B)’= A’. B’
• DeMorgan’s law can be extended to any
number of variables.
• Replace each variable by its complement and
change all AND to OR and all OR to AND.
• Thus, we find the complement of:
is:
Chapter 3: Digital Logic
20
ADVANCED GATES
NAND Gate
• The name NAND is the short form of
“NOT AND” .
• As the name implies NAND gate can be
formed by inverting the output of AND
gate.
• NAND gate can be represented by using
AND and NOT gate
NAND Gate
• Boolean expression for the NAND
operation:
x=AB
NOR Gate
• The NOR gate is the short form of
“NOT OR”.
• As the name implies NOR gate can be
implemented by inverting the output
of OR gate.
Logic symbol
UNIVERSAL GATES
• The NAND and NOR gates can be
easily used to implement all the basic
logic gates such as AND,OR and NOT.
• Actually NAND and NOR gates are
more popular as they are less
expensive and easier to design.
• Due to their versatility they are often
referred to as Universal gates.
Universality of NAND
Gates
Universality of NOR
Gates
XOR Gate
The exclusive operation produces
a high logical output when the two
inputs are at opposite logic levels.
Note the special symbol 
for the XOR operation.
Boolean Algebra
• Through our exercises in simplifying
Boolean expressions, we see that there are
numerous ways of stating the same Boolean
expression.
– These “synonymous” forms are logically
equivalent.
– Logically equivalent expressions have
identical truth tables.
• In order to eliminate as much confusion as
possible, designers express Boolean
functions in standardized or canonical
form.
Boolean Algebra
• There are two canonical forms for Boolean
expressions: sum-of-products and product-ofsums.
– Recall the Boolean product is the AND
operation and the Boolean sum is the OR
operation.
• In the sum-of-products form, ANDed variables
are ORed together.
– For example:
• In the product-of-sums form, ORed variables
are ANDed together:
– For example:
Boolean Algebra
• It is easy to convert a
function to sum-of-products
form using its truth table.
• We are interested in the
values of the variables that
make the function true (=1).
• Using the truth table, we list
the values of the variables
that result in a true function
value.
• Each group of variables is
then ORed together.
Boolean Algebra
• The sum-of-products
form for our function is:
We note that this function is not
in simplest terms. Our aim is
only to rewrite our function in
canonical sum-of-products form.
MAP
SIMPLIFICATION
Two methods of simplifying
algebraic expressions are the map
method and tabular method. The map
method is used for functions upto six
variable. To manipulate functions of a
large number of variables , the
tabular method is also known as the
Quine-McCluskey method is used. The
map method is also known as the
karnaugh map or k-map.
Each combination of the
variable in a truth table is called a
minterm .When expressed in a
truth table a function of n
variable will have 2n minterms.
A Boolean function represented by
a truth table is plotted into the map
by inserting 1’s in those squares
where the function is 1. The squares
containing 1’s are combined groups of
adjacent squares that is an integral
power of 2. Groups of combined
adjacent squares with one or more
groups. Each group of squares
represents an algebraic term , and or
of those terms terms gives the
simplified algebraic expression for
the function.
Two variable k-map
B
A
B
0
0
A
1
2
1
1
3
Three variable k-map
B
A
0
A
1
BC
00
0
4
01
11
1
5
3
7
C
10
2
6
4 VARIABLE K-MAP
C
CD
AB
00
01
A
00
11
01
10
0
1
3
2
4
5
7
6
11
12
13
15
14
10
8
9
11
10
D
B
F= (3,4,6,7)
Simplify the Boolean function using map
method.
B
11
A
11
1
C
1
1
There are four squares marked with
1’s,one for each minterm that produces
1 for the function. Two adjacent
squares are combined in the third
column .the column belongs to both B
and C, and produces the term BC. The
remaining square produce term AC’.
F=BC+AC’
Product of sum
simplification
1
1
0
1
0
1
0
0
0
0
0
0
1
1
0
1
If the squares marked with
o’s are combined , as shown in
the diagram we obtain the given
formula.
F’=AB+CD+BD’
Taking the complement of f’,
we obtain the simplified
function in product-of-sums
form
F=(A’+B’)(C’+D’)(B’+D)