Logic Gates
- In digital electronics, logic gate is physical device implementing a boolean function, it perform logical operation, takes one or more inputs and produce single binary output signals.
- Logic gates are implemented generally using diodes, transistors, semiconductor devices etc.
- Basic building blocks from which many kinds of logic circuits can be constructed.
Types of Logic Gate
OR gate
- An OR gate have two or more input and give single output.
- It performs logical addition of the inputs.
- It is denoted by plus (+) sign.
- Its diagram and truth table are shown below.
- Characteristics: It give 1 when there is atleast 1 in given equation otherwise it give 0.
AND gate
- An AND gate has two or more inputs and give single output.
- It multiplies the input, it is denotedd by dot (.) sign.
- Its diagram and truth table are shown below.
- Characteristics: An AND gate gives output 1 when all inputs are 1 other wise it gives 0.
NAND gate
- It is simple AND gate followed by a NOT gate.
- So the output will be low (0) if and only if all the input are high (1).
- It complements the output of AND gate.
- A NAND gate has two or more inputs and give single output.
NOR gate
- It is simple OR gate followed by a NOT gate.
- So the output will be high (1) if and only if all inputs are low (0).
XOR Gate (exclusive OR) (EX-OR)
- An X-OR gate has two or more input and give single output.
- Its symbol and circuit diagram and truth table are shown below :
- Characteristics: It gives o/p 1 when number of 1 in I/Ps is an odd number.
XNOR gate
- A XNOR gate has 2 or more I/Ps and single O/P.
- The Exclusive NOR gate is sometimes reffered to as the ‘COINCIDENCE’ or ‘EQUIVALENCE’ gate.
- Its logic diagram and truth table is shown below:
- Characteristics: It gives o/p 1 when number of 0 in I/Ps is an odd number.
Questions
Generate output for the given logic circuit ↓
Solution ↓
Implement xy + x'y' using baisc gates ↓
Implement x'(y+z) using basic gates ↓
Universal gates
- A logic gate can be an universal gate if we implement AND, OR, and NOT gate by using it.
- NAND and NOR gates are called universal gate because we can design any Boolean function using either NAND or NOR gate only.
NAND gate as universal gate
NOR gate as universal gate
Implementation of boolean expression using NAND gate
Steps ↓
- Draw logic diagram using basic gates (NOT, AND, OR)
- Applying bubbles at the output of AND gate and at the input of OR gate.
- Applying NOT gate where we have found bubbles.
- Look out for double inversion (NOT gate) and cancel it.
- Place equivalent NAND gate.
Implement x'y + y'x using only NAND gate ↓
Implement xy + x'y' using only NAND gate ↓
Implement AB'C + A'BC' using only NAND gate ↓
Implement A + A'B' using only NAND gate ↓
Implementation of boolean expression using NOR gate
Steps ↓
- Draw Logic Circuit using basic gates (OR, NOT, AND).
- Apply bubbles at the end of OR gate and at the input of AND gate.
- Apply NOT gate where we had applied bubbles.
- Look out for double inservion (NOT gate) and cancel it.
- Place equivalent NOR gate.
A' + B'.C' ↓
ab' + a'b ↓
ab + a'b' ↓
Boolean Algebra
- Boolean algebra is a branch of algebra in which the values of the variables are truth value T/F, usually denoted by 1/0.
- Main operations are negation (~), disjunction (∨)(+) and conjunction (∧)(.)
Boolean Laws
- . = intersection (⋂)
- + = union (⋃)
- Boolean algebra may be defined with a set of elements, a set of operators, and a number of unproved axioms or postulates.
- A set of elements is any collection of objets having a common property.
- If S is a set, and x and y are its objects, then x ∈ S denotes that x is a member of the set S, and Y ∉ S denotes that y is not an element of S.
The postulates of a mathematical system form the basic assumptions from which is possible to deduce the rules, theoroms, and properties of the system. The most common postulates used to formulate various algebraic structures are:
- Closure: If we apply binary operator (+, -, etc) between elements of a set S, then we get an
element that also belongs to set S.
For example, the set of natural numbers N = {1, 2, 3, 4, ...} is closed with respect to the binary operator plus (+). 2 + 3 = 5. 5 is also a member of set S. - Associative law:
(x * y) * z = x * (y * z) ∀ x, y, z ∈ S - Commutative law:
x * y = y * z ∀ x, y ∈ - Identity element:
e * x = x * e ∀ x ∈ S
here e is an identity element.
Axiomatic Definition of Boolean Algebra
- In 1854 George Boole introduced a systematic treatment of logic, called Boolean Algebra.
- In 1938 C. E Shannon introduced a two-value Boolean Algebra called switching algebra.
Postulate 2 x + 0 = x x . 1 = x
---------------------------------------------------------------------------------------------
Postulate 3 x + y = y + x xy = yx
(Commutative)
---------------------------------------------------------------------------------------------
Postulate 4 x.(y + z) = x.y + x.z x + (y.z) = (x + y) . (x + z)
(Distributive)
---------------------------------------------------------------------------------------------
Postulate 5 x + x' = 1 x . x' = 0
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
Theorem 1 x + x = x x . x = x
---------------------------------------------------------------------------------------------
Theorem 2 x + 1 = 1 x . 0 = 0
---------------------------------------------------------------------------------------------
Theorem 3 (x')' = x
(Involution)
---------------------------------------------------------------------------------------------
Theorem 4 x + (y + z) = (x + y) + z x(yz) = (xy)z
(Associative)
---------------------------------------------------------------------------------------------
Theorem 5 (x + y)' = x'y' (xy)' = x' + y'
(De Morgan)
---------------------------------------------------------------------------------------------
Theorem 6 x + xy = x x(x + y) = x
(Absorption)
some questions
(i) Prove (x+y) (x+z) = x + yz
LHS = (x+y) (x+z)
= (x.x) + (x.z) + (y.x) + (y.z)
= x + xz + yx + yz [as x.x = x]
= x(1 + z + y) + yz
= x + yz [since 1 + k = 1]
= RHS
(ii) Prove xy + xz + yz' = xz + yz'
LHS = xy + xz + yz'
= xy(z+z') + xz(y+y') + yz'(x+x') [as x+x' = 1]
= xyz + xyz' + xyz + xy'z + xyz' + x'yz'
= xyz + xyz' + xy'z + x'yz' [as xyz + xyz = xyz]
= xyz + xy'z + xyz' + x'yz' [rearranging]
= xz(y+y') + yz'(x+x')
= xz + yz' [as y+y' = 1]
(iii) Simplify F = ABCD + ABCD'
= ABCD + ABCD'
= ABC(D+D')
= ABC [as D+D' = 1]
Boolean Expression
- Boolean expression is a method using which we represent information about boolean function i.e. when it give 0 or 1.
- We convert truth table of boolean function into boolean expression which contains all information.
- Two types of boolean expression:
- Sum of product (SOP) expression
(Which remember where is 1) - Product of sum (POS) expression
(Which remember where is 0)
- Sum of product (SOP) expression
SOP
- It contains product term (AND term) which are sum (OR) together that's why called sum of product.
- Each product term consists of one or more literals (variables) appearing either in complemented
or uncomplemented form, e.g. a'b' + a'b.
Example for SOP: f(a,b) = a'b' + ab' truth table a b f ------------- 0 0 1 0 1 0 1 0 1 1 1 0 - A product term which contains all the literals (variables) either in complemented or uncomplemented for is called minterm. In a n variable function 2n minterm can be there.
- If a leteral have value 1 then ok, but if not, then we complement one which is zero.
- There is only one input sequence for any minterm on which output is 1 so it represent info.
- Function will have value 1, if atleast one of the product term is 1.
Another example with 3 variable. ↓
sequence binary minterm designation
representation
-----------------------------------------------------------------
0 000 a'b'c' m0
1 001 a'b'c m1
2 010 a'bc' m2
3 011 a'bc m3
4 100 ab'c' m4
5 101 ab'c m5
6 110 abc' m6
7 111 abc m7
- Example for minterm
- f(a,b) = a'b' + ab' ✓
- f(a,b) = a' + ab' ✗
- One more example ↓
a b c f -------------- 0 0 0 0 m0 0 0 1 1 m1 0 1 0 1 m2 0 1 1 0 m3 1 0 0 1 m4 1 0 1 0 m5 1 1 0 0 m6 1 1 1 0 m7 We know we have to remember where 1 is in the function. at m1, m2 and m4 we have 1 which is a'b'c + a'bc' + ab'c' f(a,b,c) = ∑m(1,2,4)
Canonical SOP expression
- In SOP expression if each product term (AND term) consists of all the literals appearing either in complemented or uncomplemented form.
- Example ↓
a b c f -------------- 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 f(a,b,c) = a'b'c + a'b'c + ab'c' + ab'c + abc simplifying it = a'b'(c+c') + ab'(c'+c) + abc = a'b' + ab' + abc = b'(a'+a) + abc = b' + abc we optimized it so that cost of implementation is less now b' is available in a'b'c, a'b'c, ab'c', ab'c - Example (optimized function)
f(a,b,c) = a'b + ab'c + c' convert this to canonical form so that we can identify minterm. = a'b(c'+c) + ab'c + (a'+a)(b'+b)c' = a'bc' + a'bc + ab'c + (a'b' + a'b + ab' + ab)c' = a'bc' + a'bc + ab'c + a'b'c' + a'bc' + ab'c' + abc' (canonical form) = a'bc' + a'bc + ab'c + a'b'c' + ab'c' + abc' (after uniting common terms) = ∑m(0, 2, 3, 4, 5, 6) - Pros: easy to read and understand.
- Cons: if the expression is in canonical form then its cost of implementation is more.
POS
- Contains SUM (OR) terms which are AND (product) together.
- Each sum term consist of one or more literals (variables), either in complemented or
uncomplemented form.
f(a,b,c) = (a + b') . (a' + b' + c') (a + b') = (a + b' + c) . (a + b' + c') [not optimized] - Sum term which contains all the literals is called maxterm.
- In a n-variable function there will be 2n maxterms.
- Result of a sum term must be 0, so if a literal is having value 0 then it is ok, but if not we complement the variable to make it 0. (a = 0, a' = 1)
- There is only one value sequence for every maxterm on which i will give 0.
- 3 variable representation ↓
sequence binary maxterm designation representation ----------------------------------------------------------------- 0 000 a+b+c M0 1 001 a+b+c' M1 2 010 a+b'+c M2 3 011 a+b'+c' M3 4 100 a'+b+c M4 5 101 a'+b+c' M5 6 110 a'+b'+c M6 7 111 a'+b'+c' M7 - function example ↓
a b c f ------------- 0 0 0 0 M0 0 0 1 0 M1 0 1 0 1 M2 0 1 1 1 M3 1 0 0 0 M4 1 0 1 1 M5 1 1 0 1 M6 1 1 1 0 M7 we have to remember where 0 is occuring = (a+b+c) . (a+b+c') . (a'+b+c) . (a'+b'+c') = πM(0,1,4,7)
Canonical POS form
- If each sum (OR) term consists of all the literals, either in complemented or uncomplemented form, then it is called POS form.
- Here each sum term represent a maxterm.
Converting non-canonical form to canonical form
1. (a) . (a' + b) . (a' + b' + c')
= (a + b'.b + c'.c) . (a' + b + c'.c) . (a' + b' + c')
= [(a+b').(a+b)+c'.c] . (a' + b + c') + (a' + b + c) . (a' + b' + c')
= (a+b'+c') . (a+b'+c) . (a+b+c') . (a+b+c) . (a'+b+c') . (a'+b+c) . (a'+b'+c')
= πM(0,1,2,3,4,5,7)
- pros: improve readability and understandability of expression
- cons: implementation of circuit is hard, cost increases.
Practise question
- Simplify - (P+Q'+R') . (P+Q'+R) . (P+Q+R')
- Obtain boolean eq. for:
- F(x,y,z) = ∑(4,6,7)
- F(a,b,c) = π(1,3,6)
- Convert SOP to POS
- (XY'Z' + XYZ' + XYZ)
- Convert the following to canonical form:
- f(p,q,r) = p'q + p'qr' + q'
Simplification of boolean expression
- After deriving a boolean expression from the truth table next important step is to minimize it, so that the cost of implementation into hardware is reduced because of additional gates can be reduced.
- We Karnaugh-map to reduce the boolean expression.
Karnaugh Map
- In 1953, Maurice Karnaugh developed K-map for reducing boolean equations so that we have a small logic circuit.
- The K-map is a diagram made up of squares, and each square represent one minterm/maxterm.
- Problems with other methods: The algebraic procedure using boolean laws and rule for minimizing boolean expression becomes difficult when a function becomes complex, because we have to identify where is the scope of minimization based on some boolean laws and it is difficult to understand where we reach saturation point or not.
- Karnaugh map is one of the most extensively used tool, it is a graphical representation, represents truth table by pictorial form, provides a systematic method for simplifying or minimizing a boolean expression.
- For n-variable K-map, there will be 2n cells addressed by a gray code.
- Each cell corresponds to one minterm or maxterm.
- we are using gray code here because that it is cyclic and we can easily minimize adjacent term.
K-MAP
2 Variable K-MAP
- A 2 variable K-map is used for the boolean equation that has only two binary variables. For example → xy + xy'.
- With 2 i/ps, there are 4 possible combinations, so we have 4 squares in a 2 variable K-map. Each square shows one minterm or maxterm.
3 variable K-MAP
- The number of cells in 3 variable K-map is eight, since the number of variable is three, the following figure shows 3 variable K-map.
4 variable K-MAP
- The number of cells in 4 variable K-map is sixteen, since the number of variables if four. The following figure shows 4 variable K-Map.
5 variable K-MAP
- The number of cells in 5 variable K-map is thirty two since the number of varaibles is 5. The following figure shows 5 variable K-map, we combine 2 maps of 16 boxes.
K-MAP for POS
