Boolean Algebra

Boolean Algebra

Introduction • An algebra useful in designing logic circuits of processors • Formalized by George Boole in 1854 • In 1938, Claude Shannon recognized how boolean algebra could be applied to onand off circuits , where all signals are characterized as high(1) or low(0)

Binary Logic • Variable take 2 discrete values – True & False – Yes & No – 1&0

• Operations assume logical meaning • 3 basic logical operations – AND • multiplication

– OR • addition

– NOT • inversion

LOGIC GATES

LOGIC GATES • Logic operations involved in design of digital systems are: – – – – –

AND OR NOT NAND EXCLUSIVE-OR

• Each of these operation is performed by electronic circuits known as gates. • Logic gates are basic building blocks of digital systems

Gates • Digital Circuit has two logic values: – 0 for low voltage – 1 for high voltage

• Other voltages are not permitted • Gates, tiny electronic devices can compute functions of these voltages • They form the basis of computers

Gates • Logic gates are small structures that accept 1 or more inputs and produce 1 output • Each gate has a distinct graphics symbol and it’s operation can be described by means of an algebraic expression or in a form of a table called the truth table. • Truth table • Table of all possible combination of i/ps & their corresponding o/ps

AND gate • Corresponds to multiplication • o/p=1 iff both i/p=1 A B

Y=A.B

Y

A 0 0 1 1

B 0 1 0 1

Y 0 0 0 1

OR gate • Corresponds to binary addition • o/p=1 if atleast one i/p=1 A

Y

B

Y=A+B This is read as Y equals A or B.

A 0 0 1 1

B 0 1 0 1

Y 0 1 1 1

NOT gate • Gate with a single transistor • Also called as an inverter • Symbol A

A

Y= A

Input 0 1

Output 1 0

NAND Gate • AND gate with output inverted A B

Y=A.B

Y

A 0 0 1 1

B 0 1 0 1

Y 1 1 1 0

NOR gate • OR gate with output inverted A

B

Y=A+B

A 0 0 1 1

B 0 1 0 1

Y 1 0 0 0

Exclusive OR • Output is high if inputs are at different logic levels. I.e either 0 and 1 or 1 and 0 • Output is low if inputs are same A

B

Y = A+ +B

Y

A 0 0 1 1

B 0 1 0 1

Y 0 1 1 0

Exclusive NOR

A

Y

B

Y = A +

B

A 0 0 1 1

B 0 1 0 1

Y 1 0 0 1

• To add A and A together A

A+A

• Sum of a variable and its complement A

A+A A

Universal gates • NAND and NOR are called as Universal gates because any digital circuit can be represented by using • NAND gates alone • Nor gates alone

• To prove it, we have to show that AND, OR and NOT can be implemented using NAND or NOR

NAND gate implementation X

X Y

F = X’

F= X.Y

X F=X+Y Y

COMBINATIONAL & SEQUENTIAL CIRCUITS

Combinational & Sequential circuits • Two types of digital circuits – Combinational – Sequential

• Combinational – o/p depends entirely on the i/ps present at that moment – Design requires AND, OR & NOT operations – e.g. adder/subtractor, digital comparator, multiplexers/selectors, demultiplexers, encoders, decoders, code converters

• Sequential – o/p depends on past o/p as well as the inputs present at that moment – Flip-Flops are also required for the dsesign – e.g. registers, shift registers, counters, latches, memory

Basic Identities A+0=A A+1=1 A+A=A A+A=1

0.A=0 1.A=A A.A=A A.A=0

A = A Double complementation

Boolean Algebra Rules • Commutative laws X+Y=Y+X X.Y=Y.X • Associative laws X+(Y+Z)=(X+Y)+Z X ( YZ ) = ( XY ) Z

Boolean Algebra Rules • Distributive laws X ( Y + Z ) = XY + XZ • Other rules (derived from the above) X + XZ = X X(X+Y)=X X+X’.Y = X+Y

Proof by perfect induction • Proving with the help of truth tables • Write all possible combinations for the inputs and check the truth values of the result (both left hand and right hand side)

De Morgan’s Theorem • Useful in simplifying expressions in which a product or sum of variables is inverted (X + Y)‘ = X’ . Y’ (X. Y)’ = X’ + Y’ • To get the complement of any expression – Replace + by . and . by + – Each of the terms in the expression is complemented

Canonical & Standard Forms

MINTERM • Binary variable can appear in – Normal form (x) – Complement form (x’)

• Binary variables x and y combined with an AND operation

MINTERM • 4 possible combination – x’y’ – x’y – xy’ – xy

• Each of these is called a minterm or standard product. • n variables can be combined to form 2n minterms

MAXTERM • n variables forming an OR term • 2n possible combination called maxterm or standard sums.

CANONICAL FORM • Any boolean function can be expressed as a product of maxterms or as sum of minterms. • Such a form is called as canonical form.

STANDARD FORMS • 2 types of standard forms: – Sum of products – Product of sums

• Sum of products – F1= y’+ xy+ x’yz’

• Product of sums – F2= x (y’ + z) (x’ + y + z’)

Karnaugh Map

Karnaugh map • Simple, straightforward procedure for simplifying boolean expressions • Pictorial arrangement of truth table which chooses the minimum number of terms needed to express the function algebraically

• The rows and columns of the K-map correspond to the possible values of the function's input • Each cell in the K-map represents a minterm (i.e. a three variables function has: x’y’z’, x’y’z, x’yz’, x’yz, xy’z’, xy’z, xyz’ and xyz) • Boolean functions having upto six variables can be minimized

• K-maps consists of squares where each square represents a minterm. • Each combination of variables in a truth table is called a minterm. • A function of n variables will have 2n minterms • Minterm is a product term of the variables • Eg: 011 is written as A’BC

Labeling Karnaugh map • Incorrectly labeled K-maps will not lead to correct minimization • The sequence used is 00, 01, 11, 10 • This is an example of gray coding where adjacent values differ by only one bit • In terms of minterms, correct labeling is A’B’ , A’B, AB, AB’

Minimization Procedure • Develop the minterm form from the truth table • Plot 1’s in the Karnaugh map for each minterm in the expression • Loop adjacent groups of 2, 4 or 8 one’s together

Minimization procedure • Write one minterm per loop, eliminating variables where possible When a variable and its complement are contained inside a loop then that variable can be eliminated. Write the variables that are left.

• Logically OR the remaining minterms together to give simplified minterm expression

Looping in K-maps • Loops must contain 2n cells set to 1 • A single cell cannot be simplified • A loop of 2n cells is independent of n variables • Using the largest loops possible will give the smallest or simplest function

Looping (contd…) • All cells in K-map set to 1 must be included in atleast one loop • Loops may overlap if they contain atleast one other unlooped cell • Any loop that has all of its cells included in other loops is redundant • Loops must be square or rectangular Diagonal or L-shaped loops are invalid

• Edges of K-map are considered adjacent A loop can leave at the top of a K-map and re-enter at the bottom. Similarly for the two sides. • There may be different ways of looping a K-map since for any given circuit there may not be a unique minimal form

f(A,B,C,D) = A’B’C’D’+A’BC’D’+A’BC’D+ A’BCD+AB’C’D’+ABC’D’+ABC’D+ABCD ABCD

f(A,B,C,D)

0000

1

0001

0

0010

0

0011

0

0100

1

0101

1

0110

0

0111

1

1000

1

1001

0

1010

0

1011

0

1100

1

1101

1

1110

0

1111

1

• Grouping – Largest Group First • BD

– Next Largest • C’D’ • Determine Final Expression

– BD + C’D’

Don’t Care condition • Two reasons for don't-care: – It does not matter whether the output is 0 or 1; – The corresponding combinations of inputs are impossible, therefore they never occur.

• denoted by ‘d’ or a ‘X’ in Karnaugh maps • Need not be covered by subcubes, but used to enlarge subcubes

Don’t Care example •

Product-of-sums • Each sum in a product-of sums expression is called a maxterm. • Simplification – Solve for 0’s – Complement the resulting expression