Digital Logic



Assalamualaikum and Good Day to you!
In this topic,we will cover the logic gate and the simplification of Boolean Algebra. You can find this topic in Lab Manual for Computer Organization and Architecture in the chapter 4.Kitorang try untuk make a simple version dalam usaha untuk terangkan kat korang pasal Digital logic ni sebab ramai yang macam blur pasal ni.So,harap korang faham la eh ? :D


1.0 Logic Gate !
  1.          The term of logic gates is used to describe a circuit that performs a basic logic operation.
  2.           It is an electronic circuit that combines digital signal according to Boolean algebra.
  3.          The logic gates also controls flow of the information that we need.
  4.          Basic logic gate with a figure and the truth table are explained for further information and   logic operation.

1.1 The AND Gate
  •  An AND gate is a logic circuit that performs the AND operation on the circuits inputs which is actually the multiplication of 0's and 1's.

  • The Boolean expression for AND operation is :-
                                           Y = AB

  • The output for AND gate is 1 if all input are 1. Otherwise it will be 0.

Truth table for AND gate :


Inputs
Outputs
A
B
Y = A B
0
0
0.0 = 0
0
1
0.1 = 0
1
0
1.0 = 0
1
1
1.1 = 1


1.2 The OR Gate
  • An OR gate is a logic circuit that performs an OR operations on the circuit's inputs.
  • The OR operation produces an output of 1 whenever any input is 1 or 0. Otherwise,if all the inputs is 0,then the outputs is 0.
  • The Boolean expression for OR gate is :-
                                                   Q = A+B


Truth table for OR gate :
           
Inputs
Outputs
A
B
Q = A + B
0
0
0 + 0 = 0
0
1
0 + 1 = 1
1
0
1 + 0 = 1
1
1
1 + 1 = 1

   
1.3 The NAND Gate
  • Combination of NOT-AND gate.
  • Implies an AND function with a complemented or inverted output.
  • The Boolean expression for the output of a 2-input NAND gate is :-
                      Y ' = ( A.B ) '




Truth table for NAND gate :


Inputs
Outputs
A'
B'
Y ' = ( AB ) '
0
0
1
0
1
1
1
0
1
1
1
0


1.4 The NOR Gate
  • The combination of NOT-OR and implies an OR function with a complemented or inverted output.
  • The Boolean expression for the output of a 2-input NOR gate is :-
                                                         Y = ( A + B ) '



Truth table for NOR gate :

Inputs
Outputs
A'
B'
Y' = ( A + B ) '
0
0
1
0
1
0
1
0
0
1
1
0


1.5 The Exclusive -OR / XOR Gate
  • The Boolean expression for XOR gate is : -
                                 Y = A (B)' + (A)'.B





Inputs
Outputs
A'
B'
Y = A.( B ) ' + (A)'.B
0
0
Y = 0.1 + 1.0 = 0+0 = 0
0
1
Y = 0.0 + 0.1 = 0+1 = 1
1
0
Y =  1.1 + 0.0 = 1+0 = 1
1
1
Y = 1.0 + 0.1 = 0+0 = 0



2.0 Simplification of Boolean Algebra !

2.1 Law's of Boolean Algebra

We use Law's of Boolean Algebra to minimize the number of logic gates or function needed to perform a particular logic operation.

The table below shows the law of Boolean Algebra in an AND form as well as OR form.
AND Form
OR Form
Identity Law
A.1 = A
A + 0 = A
Zero and One Law
A.0 = 0
A + 1 = 1
Inverse Law
A. (A)' = 0
A + (A)' = 1
Idempotent Law
A.A = A
A + A = A
Commutative Law
A.B = B.A
A +B = B + A
Associative Law
A.( B.C ) = ( A.B ).C
A + ( B + C ) = ( A + B ) + C
Distributive Law
A + (B.C) = (A +B ) . (A + C )
A.( B + C ) = ( A.B ) + ( B.C )
Absorption Law
A( A + B ) = A
A + A.B = A
A + (A)'B = A + B
DeMorgan's  Law
( A.B )' = (A)' + (B)'
( A + B ) ' = (A)'.(B)'
Double Complement Law
(X)'' = X


However,there is a slight difference in applying DeMorgan's Law.

The complement of a product of variable is equal to the sum of the complement of the variable and vice versa. In other words, the expression of the DeMorgan's law is : -

( X.Y )' = ( X) ' + ( Y ) '

( X + Y ) ' = ( X.Y ) '



Examples of application Boolean algebra's law.

Question

Simplify the following expression.

1 - A ' B + ABC' + ABC

    A'B + ABC' + ABC
   = A'B + AB ( C' + C )      -   inverse law
   = A'B + AB (1)
   = ( A' + A ) B                   -    inverse law
   = B

2 - ( AB' + C'D ) ( A'C + BD' )

( AB' + C'D ) ( A'C + BD' )
= AB'AC + AB'BD' + C'DA'C + C'DBD'       -   distributive law
= AA'B'C + B'BAD' + C'CA'D + DD'BC'      -    inverse law
= 0 ( B'C ) + 0 ( AD' ) + 0 ( BC' )
= 0

3 - A'BC + A'BC + AB'C + ABC' + AB'C' + A'BC' + A'B'C' 

A'BC + A'BC + AB'C + ABC' + AB'C' + A'BC' + A'B'C'
= ( A'BC + A'BC ) + AB'C + ABC' + AB'C' + A'BC' + A'B'C'           -  idempotent law
=   A'BC + AB'C + ABC' + AB'C' + A'BC' + A'B'C'
= AB'( C' + C ) + A'B ( C' + C ) + AC' ( B + B' ) + A'C' ( B + B' )      -   inverse law
= AB' + A'B + AC' + A'C'
= AB' + A'B + C' (A + A' )                                                                      -    inverse law
= AB' + A'B + C'

4 - ( AB' + B'C ) ( AB' + C' )

( AB' + B'C ) ( AB' + C' )
= AAB'B' + AB'C' + B'B'AC + CC'B'
= AB' + AB'C' + B'AC + B( 0 )              -   inverse law, idempotent law , 
= AB ' + AB' ( C' + C )                           -    inverse law
= AB'                                                       -    idempotent law

5 - AB + A( B + C ) + B ( B + C )

 AB + A( B + C ) + B ( B + C )
= AB + AB + AC + BB + BC               -  idempotent law
= AB + AC + B + BC                           
= AB + AC + B ( 1 + C )                      - absorption law
= AB + AC + B
= B ( 1 + A ) + AC                                - absorption law
= B + AC


2.2 Karnaugh Map


Karnaugh Map provide a simplest way to express Boolean expression. It is also similar like truth table where it represent all the possible value of input and output.Using a K-map, expressions with two to four variables are easily minimized.

The following diagram shows how to input K-Map for 2 and 3 variables. A,B and C will be the input while F, is the output. 
K-Map for 2 inputs.
K-Map for 3 inputs.

Take note that there is a difference in the arrangement for the possible outputs of the 3 variables. The arrangement that we known is 0 0, 0 1,1 0 and 1 1 but then it is actually arranged in order of 0 0, 0 1 , 1 1 and 1 0. 
The input values is arranged like that so that it only differ in only one variable from each side of the cell.



To make it easier for us to draw K-Map,we have to draw the truth table first. Then,transfer the output in the K-Map as shown below.The number of cells for the K-Map depends on the number on the variables(n)  that is 2n . For an example,if the variables is 2 ( A and B) thus the number of cells is 4.
K-Map for 2 inputs.

Then,there are few rules in grouping the 1's .
  1. The group can only contain digit 1's only.
  2. We can group the 1's in vertical and horizontal shape only,no diagonal shape is allowed.
  3. The group must be as large as it can be but use fewest number of group as it can be.
  4. The group must be in power of 2,meaning it can contain 2,4,6 or 8 of 1's.
  5. We must include all 1's.
  6. Overlapping group is allowed.
You see,when we want to write the output for the circled grouped,we have to look at the number at the uppermost row and at the leftmost column. Write down the number, if the number doesn't change . Take the diagram above as an example. 
For the above expression to be produced, we look up at the vertical first. Noticed that only A is not changing numbers whereas B changed from 0 to 1.Thus we only write A. 
Then take a look at  the horizontal one..B's is not changing any numbers but A changed from 0 to 1...so, we write B.
Thus the simplified version of the Boolean expression for the K-Map above is A+B














By Nurul Fatimah Abd. Samad.


No comments:

Post a Comment

Subscribe to: Posts (Atom)