bilangan 3

CHAPTER 3: BOOLEAN ALGEBRA
3.1 : Boolean Functions
3.2 : Representing Boolean Functions
3.3 : Logic Gates
3.4 : Minimization Of Circuits ( Karnaugh maps )

3.1 : BOOLEAN FUNCTIONS
3.2 : REPRESENTING BOOLEAN FUNCTIONS

Boolean Expressions
 Conjunction , ( A  B )  A B
 Disjunction , ( A  B )  A + B
 Negation , ~ A  / A’

TRUTH TABLE
 Truth table is used to show all possible outputs with all possible combination of inputs .

 In binary logic , True = ‘ 1 ‘ , False = ‘ 0 ‘

 If we have n inputs , there will be 2n possible combination of inputs and outputs .

 If we have 2 inputs / statements , there will be 22 = 4 possible combination of inputs and 4 possible outputs ( result )

p q p.q p+q ( p+q )’





 If we have 3 inputs / statements , there will be 23 = 8 possible outputs ( result )

p q r p.q ( p.q ) + r










Example 1 :
Construct a truth table for Z = A + B
Solution :













Example 2 :
Find the expression for f(x, y, z) from the truth table given below.

A B C Z
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

Solution :
















 Note : Truth table can be used to prove the logical equality of two different Boolean expressions ! ( 2 Boolean expressions are logically equivalent if they have the same output in the truth table )

Example 3 :
Show that A . ( A + B ) = A + A . B = A by using truth table .
( i ) A . ( A + B )







( ii ) A + A . B































The Laws Of Boolean Algebra

LAW
Double Complement

Idempotent laws x + x = x
x . x = x
Identity laws x + 0 = x
x . 1 = x
Domination laws x + 1 = 1
x . 0 = 0
Commutative laws x . y = y . x
x + y = y + x
Associative laws x . ( y . z ) = ( x . y ) . z
x + ( y + z ) = ( x + y ) + z
Distributive laws x . ( y + z ) = x . y + x . z
x + ( y . z ) = ( x + y ) . ( x + z )

De Morgan’s laws


Absorption laws x + xy = x
x (x + y ) = x
Unit Property x + = 1

Zero Property x . = 0


DUALITY
The dual of a Boolean expression is obtain by interchanging 0s and 1s and also sum and product.

Examples 4:
Find the duals of
( i ) x ( y + 0 )
( ii )
Solution :











Example 5:
Simplify the following Boolean expression using Boolean laws .

Solution:
















Example 6:
Simplify the following expression using Boolean algebra and De Morgan’s law.
X =
Solution:






















3.3 : LOGIC GATES

Three Basic Logic Gates

 Logic gate = hardware term refer to device usually in Integrated Circuit form used in the
computer to perform the logical operations deal with logical variable,
bit (0 or 1)

 AND gate ( AND function )

A
B Y = A . B










Series Circuit

Truth table :
A B A.B
0 0 0
0 1 0
1 0 0
1 1 1





















 OR gate ( OR function )

















Parallel Circuit

Truth table :

A B A+B
0 0 0
0 1 1
1 0 1
1 1 1


 NOT gate ( NOT function )


A




Truth table :

A

0 1
1 0




OTHER LOGICAL FUNCTIONS

 NAND Gate ( NOT – AND function )






Truth table :

A B A.B = C

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


 NOR gate ( NOT – OR function )





Truth table :

A B A+B = C

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















Combining Logic Gates

Example 1 :
Express the Boolean Expression for the logic circuits given as below :

( i )













( ii )













( iii )












Example 2 :
Draw the logic circuit diagram for the following Boolean expression :

( i ) X = A . B +













( ii ) ( using only 5 logical gates )













( iii ) + A( )













Example 3:


(i) Find the Boolean expression for the above network diagram (in terms of x, y and z).
(ii) Simplify the Boolean expression in part (i) by using the Boolean algebra and De Morgan’s law.
Solution:





























Example 4:


(i) Find the Boolean expression for the above network diagram (in terms of A, B and C).
(ii) Create a truth table for Z.
(iii) Simplify the Boolean expression in part (i) by using the Boolean algebra and De Morgan’s law.
Solution:




























Example 5:
Given that X = + B .
(a) Create a truth table for X.
(b) Draw a logic circuit for X without simplifying it (use 6 gates only).
(c) Simplify X using Boolean algebra and De Morgan’s Law.
Solution:








































Gates For Arithmetic Purposes

ADDER
 Carry out addition of two positive integers from binary expansions ( x + y )

 Input to circuit will be x and y ( the value 0 or 1 )

 Output will consist of two bits , namely , s ( sum bit ) and c ( carry bit )

 This circuit is called a multiple output circuit since it has more than one output .

 Half Adder – adds two bits ( x and y ) , without considering a carry from a previous
addition
- carry bit , c = xy ; sum bit , s = xy’ + x’y = ( x + y ) (














Input and Output for the Half Adder
Input Output
x y S C
1 1 0 1
1 0 1 0
0 1 1 0
0 0 0 0











 Full Adder – adds two bits and a carry bit ( x , y and ci ) are added
- carry bit ( ci+1 = xyci + xyci’ + xy’ci + x’yci )
sum bit ( s = xyci + xy’ci’ + x’ y ci ‘ + x’y’ci )
- Instead of designing the full adder from scratch , we will use half
adders to produce the desired output .











Input and Output for the Full Adder
Input Output
x y ci s Ci+1
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 0
0 1 1 0 1
0 1 0 1 0
0 0 1 1 0
0 0 0 0 0


















3.4 : MINIMAZATION OF CIRCUITS ( KARNAUGH MAPS )

 Boolean expression, E (x1, x2, … xn) is an expression built up form the variables x1, x2, … xn using the operations AND ( . ) . OR ( + ) and NOT ( ‘ )

 Examples :
E ( x , y ) = xy + x’y
E ( x , y , z ) = ( x + y’z )’ + ( xyz’ + x’y )’

 LITERAL = a variable / a complemented variable
Examples : x , x’ , y , y’

 FUNDAMENTAL PRODUCT = a literal / product of two or more literal
( No two literals involve the same variable ) .
Examples :
xz’ , xy’z , x , y’ , yz’ , x’yz ( fundamental products )
xyzy , xyx’z ( NOT fundamental products )

 A Boolean Expression is said to be in “ sum of product “ form if it is a fundamental product / the sum of two or more fundamental products none of which is included in another .
Examples :
E = xz’ + y’z + xyz’ ( NOT in sum of product form ! )
E = xz’ + x’yz’ + y’z

 Minimal Sum Of Products Form
A Boolean expression E is in a minimal sum of product form (minimal sum form) if it is in sum of products form and there is no other equivalent expression in
sum – of – products form that is simpler than E .

 Karnaugh Map
A pictorial devices for finding the minimal sum form of Boolean expression involving at most six variables .
- identify the largest possible blocks
- cover all the 1s with the fewest blocks











I ) Two Variables

- Find the minimal sum form of E ( x , y ) .

- 4 possible fundamental products with 2 literals .
xy xy’ x’y x’y’

- Represent by Karnaugh Map of 2 x 2 squares ,

y y’
xy xy’
x’y x’y’
x
x’

- To find the minimal sum – form :
( i ) Put a thick for each of the fundamental products of E .
( ii ) Draw a loop for :
1 square  2 literals
2 squares  1 literal

Example 1 :
Find the minimal sum form for the following Boolean expressions :
( i ) E = xy + xy’








( ii ) E = xy + x’y + x’y’








( iii ) E = xy + x’y’






II ) Three Variable

- Find the minimal sum form of E ( A , B , C )

- 8 fundamental products with 3 literals :
ABC

- Represent by Karnaugh Maps of 2 x 4 squares

BC



A ABC











- Draw loops for :
1 square  3 literals
2 squares  2 literals
4 squares  1 literal

- Consider the map as a cylinder ! ( identify the right edge and the left edge as a loop )
























Example 2 :
Find the minimal sums for the following Boolean Expression :
( i ) E = xyz + xyz’ + x’yz’ + x’y’z









( ii ) E = xyz + xyz’ + xy’z + x’yz + x’y’z










( iii ) E = xyz + xyz’ + x’yz’ + x’y’z’ + x’y’z










( iv ) E = xyz + xyz’ + xy’z + xy’z’ + x’yz + x’y’z + x’y’z’











III ) Four Variable

- Find the minimal sums for E ( A , B , C , D )

- 16 fundamental products represent by 4 x 4 squares Karnaugh map




























- Draw loops for :
1 square  4 literals
2 squares  3 literals
4 squares  2 literals
8 squares  1 literal

- Identify the left edge and the right edge as a loop !

- Identify the top edge and the bottom edge as a loop !


Example 3 :
Find the minimal sum for the following Boolean Expression :
( i ) E = w’x’y’z’ + wx’yz’ + w’x’yz’ + wx’y’z’














( ii ) E = w’xy’z’ + wxy’z’ + w’x’y’z’ + w’x’yz + wx’y’z + wx’yz + w’xyz’ + wxyz’









( iii ) E = xyzt + xyz’t + xy’zt’ + x’y’zt + x’y’zt’ + x’y’z’t + x’y’z’t’ + x’yzt + x’yz’t









( iv ) E = xy’ + xyz + x’y’z’ + x’yzt’








( v ) K = xyzt +









( vi ) E = wxyz’ + wxy’z’ + wx’yz + wx’yz’ + wx’y’z’ + w’xyz + w’xyz’ + w’xy’z’ + w’xy’z
+ w’x’yz’ + w’x’y’z’





Example 4:
Given A = x (
(i) Create a truth table for A and produce a Boolean expression from this table.
(ii) Simplify the above expression in part (i) by using the Karnaugh Map.
(iii) Draw a logic circuit for the simplified expression.
Solution:








































Example 5:
Given that T (A, B, C) = T (00001111, 00110011, 01010101) = 01111101.
(i) Find the Boolean expression for T in terms of A, B and C.
(ii) Simplify the expression in part (i) by using a Karnaugh map.
(iii) Draw a logic network diagram for the simplified expression in part (ii).
Solution: