MODULE 1

BOOLEAN ALGEBRA
 BOOLEAN ALGEBRA

 Mathematician George Boole invented new kind of algebra –algebra of logic

in 1854 known as boolean algebra or switching algebra
 Boolean algebra differ from conventional algebra and binary number system
In Boolean algebra, Eg: A+ A= A; A.A= A
Here variable A has only logical value, does not have any numerical
significance
In ordinary algebra, Eg. A+ A= 2A; A.A= A2, variable A has numerical
value.
 Boolean algebra deals with rules by which logical operations are carried
out.
 Used to simplify the design of logical circuits to reduce the hardware
required to design a specific system
 BOOLEAN LOGIC EXPRESSIONS

• Three basic operations performed in Boolean algebra are

AND, OR and NOT
• In addition, NAND, NOR ,XOR and X-NOR are also
performed

LOCIGAL AND OPEARTION

• Two variables A and B, given as Y= A.B
• Common symbol for this operation is Multiplication sign (.)
Inputs Output
A B Y= A.B
0 0 0
0 1 0
1 0 0
1 1 1
LOCIGAL OR OPEARTION

•Two variables A and B, given as Y= A+B

•Common symbol for this operation is Addition sign (+)

Inputs Output
A B Y= A+B

0 0 0
0 1 1
1 0 1
1 1 1

LOCIGAL NOT OPEARTION

•The logical NOT operation convert logical 1 to logical 0 and
vice versa

•Represent NOT operation by A and

 BASIC LAWS OF BOOLEAN ALGEBRA
AND LAWS
A.0 =0
A. 1= A

A.A=A
OR LAWS
A+0=A
A+1=A

A+A=A
COMMUTATIVE LAWS
Boolean addition is commutative, given by
Law 1: A + B = B+ A

Boolean multiplication is commutative, given by

Law 2 : A . B = B. A
ASSOCIATIVE LAWS

Associative law of addition is given by

law 1 : A+(B+C)= (A+B)+C

Associative law of multiplication is given by

Law 2 : A.(B.C) =(A.B).C

DISTRIBUTIVE LAWS

Boolean Addition is distributive over Boolean multiplication

Law 1:A+BC = (A+B)(A+C)

Boolean Multiplication is distributive over boolean addition

Law 2: A.(B+C)= A.B+A.C
List of postulates and theorems
Proof
 DEMORGANS THEOREM
• Two important theorems which are part of Boolean
algebra were proposed by De Morgan.
• Theorem 5:
1. (x.y)’ = x’+y’
2. (x+y)’ = x’. y’
PROOF:
 EXERCISE

 Simplify the Boolean function using boolean laws and

theorems.

1. F= AB+BC+B’C

2. A+A’B
 BOOLEAN FUNCTION
 Binary variables has two values, 0 or 1.
 Boolean function is an expression formed with binary
variables, two binary operators, one unary operator NOT,
parentheses and equal sign.
 Function value may be 0 or 1 depending on values of
variables present in boolean function.
 Consider Boolean function, F1=XYZ’
 Function F1 =1 if x=1, y=1 and Z’=1, otherwise F1=0.
 CONTD.
 Boolean function can represented in truth table.
 Number of rows in truth table: 2n combinations of 1’s and 0’s
of n variables.
 Column represents function values according to different
combinations.
EXERCISE

 Consider a Boolean Function:

F=X+Y’Z. Represent the boolean
function in form of truth table and
implement with basic gates.
 CANONICAL AND STANDATRD FORM
MIN TERM AND MAX TERM
 A binary variable may appear either in its normal form (x) or in its
complement form (x).
 Now consider two binary variables x and y combined with an AND
operation.
 four possible combinations: x’y’, xy’, x’y and xy.
 Each of these four AND terms is called a minterm, or a standard product.
 Each variable being primed if the corresponding bit of the
binary number is a 0 and unprimed if a 1.
 In a similar manner, n variables can be combined to form 2n minterms
 Similarly, n variables forming an OR term, provide 2n possible
combinations, called maxterms, or standard sums
 Each variable being primed if the corresponding bit of the
binary number is a 1 and unprimed if a 0.
MINTERMS AND MAXTERMS FOR THREE
BINARY VARIABLES
MINTERM

MAXTERM

Any Boolean functions expressed as a sum of minterms or product of

maxterms are said to be in canonical form.
 EXAMPLE PROBLEMS
EX: Express the Boolean function F=A+B’C in a sumof minterms
EX: Express the Boolean function F=xy+x’z in a product of maxterms
 EXERCISE

CANONICAL SUM OF MIN TERMS(SOP)

1. Y=A+B

CANONICAL SUM OF MAX TERMS(POS)

1. Y= (A+B’)(B+C)(A+C’)
 LOGIC GATES

 Fundamental building blocks of digital systems

 Logic gate is an electronic circuit makes logical decisions
 Most common logic gates are AND, OR, NOT, NAND and NOR
 NAND and NOR are universal gates
 Exclusive OR gate is also a logic gate constructed using AND, OR and
NOT gates
 Each gate has distinct symbol and its operation can be described by
algebraic function
 Relationship between input and output variable of each gate represent
in form of truth table.
AND GATE TRUTH TABLE
Inputs Output
A B Y= A.B
A
Y= A.B 0 0 0
B
0 1 0
1 0 0
1 1 1

OR GATE TRUTH TABLE

Inputs Output
A B Y= A+B
A
Y= A+B 0 0 0
B 0 1 1
1 0 1
1 1 1
 TRUTH TABLE
NOT GATE
Inputs A Output

A 0 1
1 0

UNIVERSAL GATES
NANDGATE TRUTH TABLE

Inputs Output
A
A B
B 0 0 1
0 1 1
1 0 1
A 1 1 0

B
NOR GATE TRUTH TABLE

Inputs Output
A A B
B 0 0 1
0 1 0
1 0 0
1 1 0
A

Both NAND and NOR gates perform all three basic logic functions (AND, NOT,
OR)
 TRUTH TABLE

Exclusive-OR (EX-OR)GATE Inputs Output

A B
A 0 0 0
0 1 1
B
Y=AB’+A’B 1 0 1
1 1 0

Exclusive-NOR (EX-NOR)GATE TRUTH TABLE

Inputs Output
A B Y=
A 0 0 1
Y= 0 1 0
B 1 0 0
Y=AB+A’B’
1 1 1
Implement AND, NOT and OR gate using NAND GATE
Implement AND, NOT and OR gate using NOR GATE
Realize the following function by NAND gates only, F = B(A + CD) + AC′.

Realization by OR, NOT and AND gates

Realization by NAND gates

only
 REALISATION OF BOOLEAN EXPRESSION USING LOGIC GATES

TRUTH TABLE
Inputs
Intermediate Output
Output
A A B C Y
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 1 1 0 0 0
A
1 0 0 1 1 1
1 0 1 1 0 1
1 1 0 0 1 1
1 1 1 0 0 0
 Simplification of Boolean equations using Karnaugh maps

 The complexity of the digital logic gates that implement a Boolean

function is directly related to the complexity of the algebraic
expression.

 Increase in variable results in increase of complexity.

 The map method, first proposed by Veitch and slightly improvised

by Karnaugh, provides a simple, straightforward procedure for the
simplification of Boolean functions.

 The method is called Veitch diagram or Karnaugh map, which may

be regarded either as a pictorial representation of a truth table.
 The Karnaugh map provides a systematic method for simplification
and manipulation of a Boolean expression.
 The map is a diagram consisting of squares.
 For n variables on a Karnaugh map there are 2n numbers of squares.
 Each square or cell represents one of the minterms.
 The simplified expression produced by the map are always in one of
the two standard forms: sum of products or product of sums.
 Assumed that the simplest algebraic expression is an algebraic
expression with a minimum number of terms and with the smallest
possible number of literals in each term.
 Two-Variable Karnaugh Maps
 A two-variable system can form four minterms, the map consists of four cells
or squares—one for each minterm.
 Each of these combinations, x’y’, x’y, xy’ and xy is called minterm.
 Minterm may be represented in decimal designations
m0:x’y’ m1: x’y, m2 : xy’, m3 : xy
 Relationship between squares and two variables x and y.

• 0 and 1 marked in each row and column

designate the values of variables.
• Variable x appears primed in row 0 and unprimed
in row 1.
• Similarly, y appears primed in column 0 and
unprimed in column 1
 Representation of function in map

• Function F= xy is equal to m3 , a 1 is placed inside the square that belongs to m3 shown in

fig. a
• Similarly, the function x + y is represented in the map of Fig. (b) by three squares marked
with 1’s.
• These squares are found from the minterms of the function:
 Three-Variable Karnaugh Maps
 There are eight minterms for three binary variables: therefore, the map
consists of eight squares.
 The minterms are arranged, not in a binary sequence.
 The characteristic of this sequence is that only one bit changes in value
from one adjacent column to the next.
• Two rows are assigned to 0 and 1, and four
column to 00, 01,11,10.

• From the postulates of Boolean algebra, it

follows that the sum of two minterms in
adjacent squares can be simplified to a
single product term consisting of only
two literals.

• Hence, any two minterms in adjacent squares

(vertically or horizontally) that are ORed
together will cause a removal the dissimilar
variable.
 Problems
 Simplify the boolean expression

• First, a three-variable Karnaugh map

is drawn and 1s are placed at the
squares according to the minterms of
the function.
• Now two 1’s of adjacent squares are
grouped together.
Simplify the boolean expression
Simplify the boolean expression
 Exercise problems

Simplify the boolean function

Simplify the boolean function
Four-Variable Karnaugh Maps
 Four-variable Karnaugh maps may be constructed with 16 squares consisting of
16 minterms.
• Two, four, or eight adjacent squares can be combined to reduce the number of
literals in a function.
• The squares of the top and bottom rows as well as leftmost and rightmost
columns may be combined
• Similarly, the four squares of the corners can also be combined.
Exerxise Problems

Simplify the boolean function

F(A,B,C,D)= m7 + m9 + m10+ m11+ m12+ m13 + m14 + m15