4.
Reference - Machine
Logic
Combinational Logic Review
Logic
Logic variable: A variable which can only has two states ‘True’
or ‘False’. The states are usually represented by
the values ‘1’ and ‘0’
e.g. - a lamp, as a logic variable, which has two states, either
‘On (1)’ or ‘Off (0)’
- a switch as a logic variable, which has two states, either
‘Close (1)’ or ‘Open (0)’
- a motor as a logic variable, which has two states, either
‘Rotate (1)’ or ‘Stop (0)’
Logic expression: A mathematical expression which consists of
logic variables and logic operations, to describe the behavior of a
system
Boolean Algebra
➢ Boolean algebra is the algebraic operations on logic expressions. It
differs in a major way from ordinary algebra in that Boolean constants
and variables are allowed to have only two possible values, 0 or 1
Logic 0 Logic 1
False True
Off On
Low High
No Yes
Open switch Closed switch
➢ In Boolean algebra there are THREE basic operations:
AND, OR, NOT
➢ The operations are called logic operations
Logic Operations
➢ Logic AND operation AND
➢ if (A=1) and (B=1) then ....
➢ it is like TWO switches connected in
serial, the lamp is turned ON only
when both switches are turned ON.
➢ Logic OR operation
OR
➢ if (A=1) or (B=1) then ....
➢ it is like TWO switches connected in
parallel, the lamp is turned ON when
either one switch is turned ON.
Boolean Algebra
➢ Boolean algebra is a mathematical process for simplifying Boolean
Expressions, e.g. F = (A+B)(B)
=B
Logical algebra deals with Boolean variables only. Any Boolean variables
will only involve logic ‘0’ and ‘1’. Never put 2, 3, 4 ... into a boolean
variable.
➢ Some basic boolean algebra are;
➢AB (sometimes as AB) means A AND B
➢A + B means A OR B
➢A or A’ (A bar, or A NOT) means the logical complement of A,
i.e. if A = 1, A’ = 0
➢A B = A’B + AB’ is a special case of logical combination called
Exclusive OR (XOR)
Boolean Algebra
➢ Fundamental Laws ;
➢ OR : (X+0) = X ; (X+1) = 1 ; (X+X) = X ; (X+X’) = 1
➢ AND : (X)(0) = 0 ; (X)(1) = X ; (X)(X) = X ; (X)(X’) = 0
➢ Associative Law
➢ (X + Y) + Z = X + (Y + Z) ; (XY)Z = X(YZ)
➢ Commutative Law
➢ X + Y = Y + X ; X.Y = Y.X
➢ Distributive Law
➢ X(Y + Z) = XY + XZ;
➢ X + YZ = (X + Y)(X + Z)
Boolean Algebra -
DeMorgan’s Theorems
➢ The two theorems are:
X •Y = X + Y …………………… Equation 1
X + Y = X •Y …………………… Equation 2
May also involve more than 2 variables, so generally,
A • B • C • • • N = A + B + C + ... + N
A + B + C + ... + N = A • B • C • • • N
➢ The L.H.S. of Equation 1 involve the NOT and AND logic operations
➢ The L.H.S. of Equation 2 involve the NOT and OR logic operations
➢ The theorems provide conversions between AND operations and OR operations
Examples of use of
DeMorgan’s theorems
➢ Ex 1: Simplify x + x’y
= x + x’y = (x + x’) (x + y)
= 1 . (x+y)
= x+y
➢ Ex 2: Simplify (A’ + B + C + D)’ + (AB’C’D)
= AB’C’D’ + AB’C’D
= AB’C’ (D’ + D)
= AB’C’
➢ Ex 3: Simplify (q + r) (q’ + r’)
= qq’ + rq’ + qr’ + rr’
= 0 + rq’ + qr’ + 0
= rq’ + qr’
Examples of DeMorgan’s
theorems
➢ Ex 4: Simplify F = A’C + A’B + AB’C + BC
➢ F = A’B + A’C + AB’C + BC
= A’B + C ( A’ + AB’ + B)
= A’B + C [ ( A’+ B ) + AB’ ]
= A’B + C [ ( A’ +B ) + ( A’ +B )’ ] by DeMorgan’s theorem
= A’B + C (1)
= A’B + C
Truth Tables
➢ A Truth Table is a means for describing how a logic circuit’s output depends
on the logic levels of all possible input combinations
➢ The number of rows is equal to the number of possible input combinations,
i.e. 2N, where N is the number of input variables.
➢ The following truth tables describe the logic AND, OR and NOT operations
with two inputs A, B and one output F
LogicAND LogicOR LogicNOT
A B F=AB A B F=A+B A F=A'
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
Logic Gates
Logic device symbol
AND gate OR gate NOT gate
A (AB) A (A+B) A A’
B B
Logic AND Logic OR Logic NOT
A B F = AB A B F = A+ B A F = A'
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
Logic Gate - IC
1 Vcc 14
➢ Devices which perform logic operations, an 2
3
13
12
TWO-input AND gate produces a logic ‘1’ 4
5
11
10
at its output when both inputs are logic ‘1’ 6 9
7 GND 8
➢ Logic gates are usually embedded in top view of a logic gate IC
Integrated Circuits ICs, sometimes referred
as Chips
➢ Logic gates ICs may be TTLs type or
CMOS type, both require a positive power
supply and a ‘ground’ in addition to the
logic inputs
Example 1
Show that A + B = AB using truth table.
Truth Table:
A B A B A+B AB
0 0 1 1 1 1
0 1 1 0 1 1
1 0 0 1 1 1
1 1 0 0 0 0
Example 2
Complete the truth table for the circuit
F = AB( BC + A )
A B C A BC BC + A AB( BC + A )
0 0 0 1 0 0 0
0 0 1 1 0 0 0
0 1 0 1 0 0 0
0 1 1 1 1 0 0
1 0 0 0 0 1 0
1 0 1 0 0 1 0
1 1 0 0 0 1 1
1 1 1 0 1 0 0
Example 3
Prove that A (A + B) = A B
A B A A +B A (A + B) AB
0 0 1 1 0 0
0 1 1 1 0 0
1 0 0 0 0 0
1 1 0 1 1 1
Example 4
Prove A B = A + B
A B A B AB AB A+B
0 0 1 1 0 1 1
0 1 1 0 0 1 1
1 0 0 1 0 1 1
1 1 0 0 1 0 0
Logic Gates
➢ By applying a NOT gate at the output of the AND gate and OR gate, we get
TWO commonly used logic gates
NAND gate NOR gate
A A
(AB)’ (A+B)’
B B
Logic NAND Logic NOR
A B AB F = (AB)' A B A+ B F = (A+B)'
0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0
1 0 0 1 1 0 1 0
1 1 1 0 1 1 1 0
Exclusive-OR Gate
➢ An Exclusive-OR (XOR) gate provides a boolean
expression (A B + A B) with inputs A and B.
➢ The expression is (A B + A B) is represented by A
XOR gate
A
AB
B
Logic XOR
A B A'B AB' F = A'B + AB'
0 0 0 0 0
0 1 1 0 1
1 0 0 1 1
1 1 0 0 0
Example 5
Draw the logic circuit of the Boolean function
F = (A + B) C.
A
B
C F
Example 6
➢ Obtain the logic function for the following logic circuit
A X
F
B
Y
X = AB
Y = A’B’
F =X+Y
= AB + A’B’
Example 7
➢ Obtain the logic function for the following logic circuit
A X F
B
Y
X=A+B
Y = A’ + B’
F = XY
= (A+B)(A’+ B’)