2.4 Universal Gates

NAND gate (Negated AND or NOT AND) is a logic gate which produces an output that is false only if all its inputs are true.  

NOR Gate

NOR gate (Negated OR or NOT OR) is a logic gate which produces a 1 output if both the inputs to the gate are 0; a 0 output if one or both input is 1.

2.3 Simplication of Boolean Equation

There are two ways to simplify Boolean equation, Laws of Boolean Algebra and Karnaugh Map:

Laws of Boolean Algebra

Operations on Constants
X.1 = X
X.0 = 0
X+1 = 1
X+0 = 0

Idempotent Law
X.X = X
X+X=X

Absorption Law
X.(Y.Z) = (X.Y).Z

Double Complement Law

Laws of Commutativity
X.Y = Y.X
X+Y = Y+X

Laws of Associativity
X.(Y.Z) = (X.Y).Z
X+(Y+Z) = (X+Y)+Z

Laws of Distributivity
X.(Y+Z) = (X.Y)+(X.Z)
X+(Y.Z) = (X+Y).(X.Z)

Inverse laws
X.~X = 0
X+~X = 1
~~X = X

DeMorgan’s laws
~(X.Y) = ~X+~Y
~(X+Y) = ~X.~Y


Karnaugh Map

Karnaugh map (K-map) is a convenient way to represent Boolean function, the only limitation is that it will be ineffective for > 4 inputs. It is essential for later purposes to list the combinations in the order 00, 01, 11 10. Because the squares corresponding to the combinations are to be used for recording information, the combinations are customarily written above the squares.

K-map can be used to represent any Boolean function in the following way.

Each square corresponds to a unique product in the sum-of-products (SOP) form, with a 1 value corresponding to the variable and a 0 value corresponding to the NOT of that variable. For each such product in the function, 1 is placed in the corresponding square.

Once the map of a function is created, we can often write a simple algebraic expression for it by noting the arrangement of the 1s on the map.The principle is as follows. Any two squares that are adjacent differ in only one of the variables. If two adjacent squares both have an entry of one, then the corresponding product terms differ in only one variable. In such a case, the two terms can be merged by eliminating that variable. For example, A'BC'D + A'BCD = A'BD. This process can be extended in several ways.

2.2 Combinational Circuit

Combination Circuits

•      A combinational circuit or logic block is an interconnected set of gates and contains no memory whose computes the output at any time is a function only of the given current inputs.
•   Gates can be defined in three ways:

o   Truth Table 

For each of the 2n possible combinations of input signals, the binary value of each of the F output signals is listed.

o   Boolean equations

Each output signal is expressed as a Boolean function that consist possible combination of inputs.

                                o    Graphical symbols

 

 

The interconnected layout of gates is depicted.

Boolean Equation Forms

Any Boolean function can be implemented in electronic form as a network of gates.

For any given function, there are a number of alternative realizations.

All Boolean equation can be represented in two forms:

-          Sum of products (SOP)

o   Equivalent variables, ANDed together then ORed with other combination variables with the same output are converted from the combination of input values that produce 1s, 

o   Truth table is easier to be derived by SOP.

-          Product of sums (POS)

o   0s in sum terms (ORed variables) that produced by input combinations are ANDed together.

o   Convert input values that produce 0s into equivalent variables, ORed the variables, then ANDed with other ORed forms.

o   If more 1s produce in output function, POS usually used.

Example:

F = C’D’ + A’BCD

The truth table:

A	B	C	D	F
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	1
1	1	1	0	0
1	1	1	1	0

     Product term

     A’B’C’D’

     A’BC’D’

     A’BCD

     AB’C’D’

     ABC’D’

SOP expression:

F = (A’B’C’D’) + (A’B’C’D’)+(A’BCD)+(AB’C’D’)+(ABC’D’)

2．

F = (X+Y+Z)(X+Y+Z’)(Z+Y’+Z)(X’+Y+Z’)

The truth table:

 

X	Y	Z	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Product term:

            X+Y+Z

            X+Y+Z’

            X+Y’+Z

            X’+Y+Z’

          

POS expression:

F = (X+Y+Z)(X+Y+Z’)(X+Y’+Z)(X’+Y+Z’)