Arithmetic and logic: Logic operations and gates, Boolean function, Boolean algebra, Half adder and full
adder. Half
subtractor and full subtractor
Binary logic gates
OR gate AND gate NOR gate NAND gate XOR gate NOT gate
A B Y A B Y A B Y A B Y A B Y A Y
0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1
0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0
1 0 1 1 0 0 1 0 0 1 0 1 1 0 1
1 1 1 1 1 1 1 1 0 1 1 0 1 1 0
A
A A Y A A A
B Y B Y B Y
B Y B Y
OR, AND, NOT are the primary logic gates. The minimum number of inputs for all the logic gates except the NOT gate is two.
NOT gate has only one input.
A, B and Y are binary variables. A and B are input, and Y is output.
In OR gate, Y=A+B and Y is high if at least one input is high.
In NOR gate, Y = complement of (A + B) and Y is low if at least one input is high.
In AND gate, Y = A . B and Y is high if all the inputs are high.
In NAND gate, Y = complement of (A . B) and Y is high if at least one input is low.
In XOR gate, Y =A ⊕ B = A.(complement of B)+B.(complement of A) and Y is high if the inputs are not equal.
In NOT gate, Y = complement of A and Y is high if A is low
Boolean functions
•An expression formed with binary variables, two binary operators OR and AND, unary
operator NOT, parentheses and equal sign
•For a given value of the variables, function can be either 0 or 1
Ex. F1=xyz´ is 1 if x=1, y=1, z=0; otherwise F1=0
• May also be represented in a truth table
Ex.
x y z F1 •Number of rows in the truth table is 2n where n is the number
0 0 0 0 of binary variables in the function
•Boolean function may be transformed from an algebric
0 0 1 0 expression into a logic diagram composed of AND, OR, NOT
0 1 0 0 gates
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
xy′
yz′
(xyz)′
x y z
x y z
xy′+yz′+(xyz)′ = xy′+yz′+x′+y′+z′=y′(1+x)+z′(1+y)+x′=x′+y′+z′
Algebric manipulation
•Literal is a primed or unprimed variable
•Each literal in the Boolean function designates an input to a gate
•Each term in the Boolean function is implemented with a gate
•Minimization of the number of literals and number of terms reduces number of
equipment in a circuit
Boolean algebra: Use to simplify the Boolean functions to minimum number of literals
Laws and theorems of Boolean algebra
Duality: (a) (i) x+x=x (ii) x+1=1 (iii) x+0=x (iv) x+x′=1
(b) (i) x.x=x (ii) x.0=0 (iii) x.1=x (iv) x.x′=0
Commutative law: (i) x+y=y+x (ii) x.y=y.x
Associative law: (i) x+(y+z)=(x+y)+z (ii) x.(y.z)=(x.y).z
Distributive law: (i) x+y.z=(x+y).(x+z) (ii) x.(y+z)=x.y+x.z
Involution: (x′)′ = x
De-Morgans theorems: (i) (x+y)′=x′y′ (ii) (xy)′=x′+y′
Absorption: (i) x+xy=x (ii) x.(x+y)=x
Operator precedence for evaluating boolean expression
(1) Parentheses (2) NOT (3) AND (4) OR
Example
(x+y)′ → Expression inside the parentheses is evaluated first and the result is then
complemented
x′. y′ → Complement of x and complement of y are evaluated first, the result is then ANDed
Ex. Simplify the following Boolean functions to minimum number of literals
1. x+x´y =(x+x´)(x+y) = 1.(x+y)=x+y
2. x(x´+y) = xx´+xy=0+xy=xy
3. x´y´z+x´yz+xy´=x´z(y´+y)+xy´=x´z+xy´
4. xy+x´z+yz = xy+x´z+yz(x+x´) = xy+x´z+xyz+x´yz = xy(1+z)+x´z(1+y) = xy+x´z
5. F1=x′y′z+x′yz+xyz′ =x′z(y+y′)+xyz′ = x′z+xyz′
6. F1=(x+y+z).(x+y′+z).(x′+y+z).(x′+y+z′).(x′+y′+z′)=(x+z+yy′).(x′+y+zz′).(x′+y′+z′)
= (x+z).(x′+y).(x′+y′+z′) = (xx′+zx′+xy+yz).(x′+y′+z′) = (0+ zx′+xy+yz).(x′+y′+z′)
= zx′+xyx′+yzx′+zx′y′+xyy′+yzy′+zx′z′+xyz′+yzz′ = zx′+0+yzx′+zx′y′+0+0+0+xyz′+0
= zx′(1+y+y′)+xyz′ = zx′(1+1)+xyz′ = zx′+xyz′
Universal logic gate: NAND and NOR are universal logic gate as all the other logic gates
can be designed using NAND and NOR (A.A)′=A′
AND by NAND: AB = ((AB)′)′ NOT by NAND: A A′
AB
XOR by NAND: A.B′ +A′.B=((A.B′ +A′.B )′)′= ((A.B′)′.(A′.B)′)′
A B
OR by NAND: A+B =
((A+B)′)′ = ((A′).(B′))′
A B (A.(AB)′)′=(A.(A′+B′))′=(A.A′+AB′)′
A B =(0+AB′)′=(AB′)′
(AB)′
(B.(AB)′)′=(B.(A′+B′))′=(B.A′+BB′)′ ((A.B′)′.(A′.B)′)′ ((A.B′)′.(A′.B)′)
=(A′B+0)′=(A′B)′ → XOR → XNOR
AND by NOR: A.B = ((A.B)′)′= OR by NOR: A+B = ((A+B)′)′ NOT by NOR:
((A′)+(B′))′
A B (A+B)′
(A+A)′=A′
A B ((A+B)′)′
A′
A A′
B′ ((A′)+(B′))′
(A+(A+B)′)′=(A+A′.B′)′=((A+A′).(A+B′))′
XOR by NOR =(1.(A+B′))′=(A+B′)′
AB
((B+A′)′+(A+B′)′)′=(A.B′+A′B)′ → XNOR
(A+B)′
(A.B′+A′B) → XOR
(B+(A+B)′)′=(B+A′.B′)′=((B+A′).(B+B′))′
=((B+A′).1)′=(B+A′)′
Complement of a function
F1 = x´yz´+x´y´z and F2 = x(y´z´+yz). Find F1´ and F2´
F1´ = (x´yz´+x´y´z)´ = (x´yz´)´ (x´y´z)´ = (x+y´+z)(x+y+z´)
F2´ = [x(y´z´+yz)]´ = x´+(y´z´+yz)´ = x´+(y´z´)´. (yz)´ = x´+(y+z)(y´+z´)
Take the dual of the function and complement each literal to find complement of a
function
Ex. Dual of F1 is (x´+y+z´)(x´+y´+z)
Complement each literal: (x+y´+z)(x+y+z´) = F1´
Dual of F2 is x+(y´+z´)(y+z)
Complement each literal: x´+(y+z)(y´+z´) = F2´
Product Sum x y z F1 F2
term term
0 0 0 0 0
x y z Term Term
0 0 1 1 0
0 0 0 x′y′z′ x+y+z
0 1 0 0 0
0 0 1 x′y′z x+y+z′
0 1 1 0 1
0 1 0 x′yz′ x+y′+z
0 1 1 x′yz x+y′+z′ 1 0 0 1 0
1 0 0 xy′z′ x′+y+z 1 0 1 0 1
1 0 1 xy′z x′+y+z′
1 1 0 0 1
1 1 0 xyz′ x′+y′+z
1 1 1 xyz x′+y′+z′ 1 1 1 1 1
Boolean function representation in Sum of product form
Boolean function may be expressed algebraically from a given truth table as sum of product (SOP)
F1 = x´y´z+xy´z´+xyz
F2 = x´yz+xy´z+xyz´+xyz
Boolean function representation in Product of sum form
Boolean function may be expressed algebraically from a given truth table as product
of sum (POS)
F1 = (x+y+z).(x+y´+z).(x+y´+z´).(x´+y+z´).(x´+y´+z)
F2 = (x+y+z).(x+y+z´).(x+y´+z).(x´+y+z)
x y z F1 F2
0 0 0 0 0
0 0 1 1 0
0 1 0 0 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
Half adder (HA)
A Sum
Half adder has two inputs (A, B) and two A B Sum Carry HA
B Carry
outputs (Sum, Carry). 0 0 0 0
Sum = A.B′+ A′.B and Carry = A .B 0 1 1 0 A B
So Sum is obtained from the output of 1 0 1 0 Carry
1 1 0 1
XOR gate and Carry is obtained from the Sum
output of AND gate.
Full adder (FA): Full adder Full adder (FA) using Full adder (FA)
has three inputs (A, B, C) and two half adders using logic gates
Sum A BC
two outputs (Sum, Carry). C HA2 Carry1
B Carry2
A Sum A HA1 Sum1
B FA Sum1 Carry
C Carry OR
Carry1 Carry
Carry2
Sum1 and Carry1 are the outputs of HA1 Sum
Sum and Carry2 are the outputs of HA2
Sum and Carry are the outputs of FA
A B C Sum Minterms Maxterms Carry Minterms Maxterms
0 0 0 0 A+B+C 0 A+B+C
0 0 1 1 A′B′C 0 A+B+C′
0 1 0 1 A′BC′ 0 A+B′+C
0 1 1 0 A+B′ +C′ 1 A′BC
1 0 0 1 AB′C′ 0 A′+B+C
1 0 1 0 A ′+B+C′ 1 AB′C
1 1 0 0 A ′+B′+C 1 ABC′
1 1 1 1 ABC 1 ABC
Sum=A′B′C+A′BC′+AB′C ′+ABC in SOP
Sum = (A+B+C).(A+B′+C′).(A′+B+C′).(A′+B′+C) in POS
Carry=A′BC+AB′C+ABC′+ABC in SOP
Carry = (A+B+C).(A+B+C′).(A+B′+C).(A′+B+C) in POS
Simplify Sum and Carry
Sum=A′B′C+A′BC′+AB′C ′+ABC=A′(B′C+BC′)+A(BC+B′C′)=A′(B′C+BC ′)+
A(BC′+B′C)′=A′(B xor C)+A(B xor C)′=A xor B xor C
Sum = (A+B+C).(A+B′+C′).(A′+B+C′).(A′+B′+C)
= (A.A+A.B+A.C+AB′+BB′+CB′+AC′+BC′+CC′).(A′A′+A′B+A′C′+A′B′+BB′+C′ B′+
A′C+BC+C′C)
= (A+AB+AC+AB′+0+CB′+AC′+BC′+0).(A′+A′B+A′C′+A′B′+0+C′B′+A′C+BC+0)
= (A.(1+B+C+B′+C′)+B′C+BC′).(A′.(1+B+C′+B′+C)+BC+B′C′)
= (A+B′C+BC′).(A′+BC+B′C′) = AA′+A′B′C+A′BC′+ABC+AB′C′
= A′B′C+A′BC′+ABC+AB′C′ = A xor B xor C
Carry=A′BC+AB′C+ABC′+ABC=BC(A+A′)+AB′C+ABC′=BC+AB′C+ABC′
=C(B+AB′)+ABC′=C(B+A)(B+B′)+ABC′=BC+AC+ABC′=B(C+AC′)+AC
=B(C+A)(C+C′)+AC=AB+BC+CA
Carry = (A+B+C).(A+B+C′).(A+B′+C).(A′+B+C)
= (A+B+CC′).(AA′+A′B′+A′C+AB+BB′+BC+AC+B′C+CC)
= (A+B).(0+A′B′+A′C+AB+0+BC+AC+B′C+C)
= (A+B).(C(1+B′+A+B+A′)+AB+A′B′) = (A+B).(C+ AB+A′B′) =
AC+BC+AAB+BAB+AA′B′+BA′B′=AC+BC+AB+AB+0+0=AC+BC+AB
Half subtractor (HS)
A Difference
Half subtractor has two inputs (A, B) and A B Difference Borrow HS
B Borrow
two outputs (Difference, Borrow).
0 0 0 0
Difference = A.B′+ A′.B A B
0 1 1 1
Borrow = A′.B 1 0 1 0 Borrow
So Difference is obtained from the output 1 1 0 0
of XOR gate and Borrow is obtained from Difference
the output of AND gate.
A′
Full subtractor (FS)
A B C Difference Minterms Maxterms Borrow Min1terms Maxterms
0 0 0 0 A+B+C 0 A+B+C
0 0 1 1 A′B′C 1 A′B′C
0 1 0 1 A′BC′ 1 A′BC′
0 1 1 0 A+B′ +C′ 1 A′BC
1 0 0 1 AB′C′ 0 A′+B+C
1 0 1 0 A ′+B+C′ 0 A′+B+C′
1 1 0 0 A ′+B′+C 0 A′+B′+C
1 1 1 1 ABC 1 ABC
Difference=A′B′C+A′BC′+AB′C ′+ABC in SOP
Difference = (A+B+C).(A+B′+C′).(A′+B+C′).(A′+B′+C) in POS
Borrow=A′B′C+A′BC′+A′BC+ABC in SOP
Borrow = (A+B+C).(A′+B+C).(A′+B+C′).(A′+B′+C) in POS
Simplify Difference and borrow
Difference=A′B′C+A′BC′+AB′C ′+ABC=A′(B′C+BC′)+A(BC+B′C′)=A′(B′C+BC ′)+
A(BC′+B′C)′=A′(B xor C)+A(B xor C)′=A xor B xor C
Difference = (A+B+C).(A+B′+C′).(A′+B+C′).(A′+B′+C)
= (A.A+A.B+A.C+AB′+BB′+CB′+AC′+BC′+CC′).(A′A′+A′B+A′C′+A′B′+BB′+C′ B′+
A′C+BC+C′C)
= (A+AB+AC+AB′+0+CB′+AC′+BC′+0).(A′+A′B+A′C′+A′B′+0+C′B′+A′C+BC+0)
= (A.(1+B+C+B′+C′)+B′C+BC′).(A′.(1+B+C′+B′+C)+BC+B′C′)
= (A+B′C+BC′).(A′+BC+B′C′) = AA′+A′B′C+A′BC′+ABC+AB′C′
= A′B′C+A′BC′+ABC+AB′C′ = A xor B xor C
Borrow =A′B′C+A′BC′+A′BC+ABC =A′B′C+A′BC′+BC=A′B′C+B(C+A′)
=A′B′C+BC+A′B=A′(B+C)+BC=A′B+A′C+BC
Borrow= (A+B+C).(A′+B+C).(A′+B+C′).(A′+B′+C)
=(B+C+AA′)(A′+A′B+A′C′+A′B′+BB′+B′C′+A′C+BC+CC′)=(B+C)(A′+B′C′+BC)
=A′B+A′C+BC
Borrow=A′B+A′C+BC=((A′B+A′C+BC)′)′=((A′B)′.(A′C)′.(BC)′)′ by De-Morgans theorem
A A′ B C
Borrow
A B C
A xor B
Difference = A xor B xor C
