Home » BOOLEAN ALGEBRA

Category Archives: BOOLEAN ALGEBRA

BOOLEAN ALGEBRA

Long ago Aristotle constructed a complete system of formal logic and wrote six famous works on the subject, contributing greatly to the organization of man’s reasoning. For centuries afterward, mathematician kept on trying to solve these logic problems using conventional algebra but only George Boole could manipulate these symbols successfully to arrive at a solution with his own mathematical system of logic. Boole’s revolutionary paper “An Investigation of the laws of the though” was published in 1854 which led to the development of new system, the algebra of logic, “BOOLEAN ALGEBRA”. Boole’s work remained confined to paper only until 1938 when Claude E. Shannon wrote a paper titled ‘A Symbolic Analysis of Relay Switching Circuit’. In this paper he applied Boolean algebra to solve relay logic problems. As logic problems are binary decisions and Boolean algebra effectively deals with these binary values. Thus it is also called ‘Switching Algebra’.

DEFINITION OF BOOLEAN ALGEBRA

A Boolean Algebra is an algebra (set, operation, elements) consisting of a set B with ≥2 elements, together with three operations –the AND operation (Boolean Product), the OR operation (Boolean Sum), and the NOT operation (complement) –defined on the set. Let us consider the two-element Boolean algebra B2 = ({0, 1}; ., +,’ ;0, 1).The three operations . (AND), + (OR), ‘(NOT) are defined as follows: (more…)

PARALLEL BINARY ADDER

FOUR BIT PARALLEL BINARY ADDER

Parallel binary adder is used to add two binary numbers. As for example, if we want to add two four-bit binary numbers, we need to construct a four bit parallel binary adder as shown below. Such an adder requires one Half-Adder denoted by HA and three Full-Adders denoted by FA. The binary numbers being added are A4 A3 A2 A1 and B4 B3 B2 B1 and the answer is:

                          A4 A3 A2 A1
                       + B4 B3 B2 B1
                     S5 S4 S3 S2 S1
BLOCK DIAGRAM OF FOUR BIT PARALLEL BINARY ADDER
The first column requires only a Half-Adder. For any column above the first, there may be a carry from the preceding column. Therefore, we must use a Full-Adder for each column above the first. To illustrate how parallel binary adder of the above picture works, let us take an example. If we want to add two numbers say 9 and 11. The binary equivalent of decimal 9 is 1001 and that of decimal 11 is 1011. The given block diagram shown below shows how the binary adder works with these inputs.
 EXAMPLE OF ADDING TWO FOUR-BIT NUMBER USING A PARALLEL BINARY ADDER
As shown in the above picture, the Half-Adder adds the binary bits 1 + 1 to give a sum of 0 and a carry 1. This carry goes into the first Full-Adder which adds 0 + 1 + 1 to get a sum of 0 and a carry of 1. Now, this carry goes into the next Full-Adder that adds 0 + 0 + 1 to get a sum of 1 and a carry of 0. The last Full-Adder adds 1 + 1 + 0 to get a sum of 0 and a carry of 1. The final input of the system is 10100. The decimal equivalent of binary 10100 is 20 which is the correct decimal sum of 9 and 11. The parallel binary adder of above figure has limited capacity. The largest binary numbers that can be added using it are 1111 and 1111.
   15    1111
+ 15 + 1111
    30 11110
In order to increase the capacity, more Full-Adders can be connected to the left end of the system. For instances, to add six bit numbers, two more Full-Adders must be connected and for adding eight bit numbers, four more Full-Adders must be connected to the left end of the system given above.

De Morgan’s Theorem AND Proof

In connection with AND Gate and OR Gate De Morgan suggested the two following theorems which are known as De Morgan’s Theorem. Definition and proof of these two theorems are explained.

FIRST THEOREM:

The complement of the sum of two or more variables is equal to the product of the complements of the variables. If X and Y are the two logical variables, then according to the De Morgan’s Theorem we can write: (X + Y)’ = X’.Y’.
For n number of logical variables say X1, X2, ………………., Xn it can be written as: (X1 + X2 + …………+ Xn)’ = X’1.X’2…………….X’n.

SECOND THEOREM:

The complement of the product of two or more logical variables is equal to the sum of the complements of the variables. If Z and Y are the two logical variables, the according to the second law of De Morgan’s theorem we can write: (X.Y)’ = X’ + Y’.
For n numbers of variables say X1, X2, ………………, Xn the second theorem can be written as: (X1.X2……………Xn)’ = X’1 + X’2 + ……………….. + X’n.

PROOF OF De MORGAN’S THEOREM:

There are two De Morgan’s theorems:
  1.  (X+Y)’ = X’.Y’
  2.  (X.Y)’ = X’+ Y’

PROOF OF FIRST LAW OF De Morgan’s Theorem:

First we will prove the first law of the De Morgan’s theorem (X+Y)’ = X’.Y’ as: To prove this theorem, we will use complementarity laws that are as follows:  X+X’ = 1 and, X.X’ = 0. Now, let P = X+Y where, P,X,Y are three logical variables, then according to the complementarity laws we can write :
            P+P’ =1 and,
P.P’ = 0, if P = X+Y, then P’ = (X+Y)’.
If we take (X+Y)’ = X’.Y’, Therefore to prove the first law we have to prove that,
(X+Y)+(X’.Y’) should be equal to 1 and,
(X+Y).(X’.Y’) should be equal to 0.
    (X+Y)+(X’.Y’)
[BY X+YZ = (X+Y)(X+Z)]
= ((X+Y)+X’).((X+Y)+Y’)
= (X+Y+X’).(X+Y+Y’)
[BY X+Y = Y+X]
= (X+X’+Y).(X+Y+Y’)
[BY X+X’ = 1]
= (1+Y).(X+1)
[BY X+1 = 1]
= 1.1
= 1
So, the first part is proved. Now, we have to prove the second part
   (X+Y).(X’.Y’)
[BY X.(Y+Z) = X.Y+X.Z ]
= X.X’.Y’ + Y.X’.Y’
[BY X.Y = Y.X]
= X.X’.Y’ + X.Y.Y’
[BY X.X’ = 0]
= 0.Y’ + X.0
= 0 + 0
= 0
So, the second part is also proved. Therefore, we can say that (X+Y)’ = X’.Y’

PROOF OF SECOND LAW OF De Morgan’s Theorem:

Second law of the De Morgan’s theorem (X.Y)’ = X’+ Y’ is proved in same way by letting P = X.Y. Here, we again use the complementarity laws.
X+X’ = 1 and,
X.X’ = 0. If we take P = X.Y, then P’ = (X.Y)’.
If we assume that P’ = (X.Y)’ = X’+Y’ then We have to prove,
(X.Y)+(X’+Y’) should be equal to 1.
(X.Y).(X’+Y’) should be equal to 0.
   (X.Y)+(X’+Y’)
[BY X+YZ = (X+Y)(X+Z)]
= (X+X’+Y’).(Y+X’+Y’)
[BY X+Y = Y+X]
= (X+X’+Y’).(X’+Y+Y’)
[BY X+X’ = 1]
= (1+Y’).(X’+1)
[BY 1+X’ = 1]
= 1.1
= 1
So, the first part is proved. Now, we have to prove the second part as:
   (X.Y).(X’+Y’)
[BY X.(Y+Z) = X.Y+X.Z]
= X.Y.X’ + X.Y.Y’
[BY X.Y = Y.X]
= X.X’.Y + X.Y.Y’
[BY X.0 = 0]
= 0.Y + X.0
= 0+0
= 0
So, the second part is also proved. Therefore, we can write (X.Y)’ = X’+ Y’

FULL ADDER

A full adder is a combinational circuit that forms the arithmetic sum of three input bits. A full adder consists of three inputs and two outputs. Two of the input variables full adder, denoted by x and y, represent the two significant bits to be added. The third input, z, represents the carry from the previous lower significant position. Two outputs of full adder are necessary because the arithmetic sum of three binary digits ranges in value from 0 to 3, and binary 2 or 3 needs two digits. The two output of full adder are designated by the symbols S (for sum) and C (for carry). The binary variable S gives the value of the least significant bits of the sum. The binary variable C gives the output carry. The truth table of the full adder is shown below. The eight rows under the input variables designate all possible combinations that the binary variables may have. The values of the output variables are determined from the arithmetic sum of the input bits. When all input bits of full-adder are 0, the output is 0. The S output is equal to 1 when only one input is equal to 1 or when all three inputs are equal to 1. The C output of the full adder has a carry of 1 if two or three inputs are equal to 1. The K maps for full-adder are used to find algebraic expressions for the two output variables. The 1’s in the squares for the maps of S and C are determined directly from the minterms in the truth table. The squares with 1’s for the S output do not combine in groups of adjacent squares. But since the output is 1 when an odd number of inputs are 1, S is an odd function and represents the exclusive-OR relation of the variables. The squares with 1’s for the C output may be combined in a variety of ways. One possible expression for C is xy + (x’y +xy’)z. And including the expression for output S, we obtain the two Boolean expressions for the full adder:S = x’y’z +x’yz’ +xy’z’ +xyz the logic diagram of the full adder is given below. Note that the full adder circuit consists of two half-adders and an OR gate.

The logic diagram, block diagram and truth table is shown below. The logic diagram is implemented by two XOR gates, two AND gates and OR gate. The given XOR gates are used to obtain the sum output of the full adder and other logic gates are used to get the carry output of the full adder. The K-map for obtaining sum output and carry output is also given below.

TRUTH TABLE OF FULL ADDER
INPUT
OUTPUT
X
Y
Z
C
S
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
LOGIC DIAGRAM AND BLOCK DIAGRAM OF FULL ADDER
K-MAP FOR FULL ADDER OUTPUTS

K-MAP REPRESENTATION OF A FULL ADDER

IMPLEMENTATION OF FULL ADDER USING 3-TO-8 LINE DECODER:

FULL ADDER USING DECODER AND LOGIC GATESThe truth table for a full adder which adds 3 input bits A, B, and Cin simultaneously, where A and B are addend and augend bits respectively and Cin is the carry bit from the previous bits (if any) is shown above. Here S, Coutare the outputs where S is the sum of the full adder and cout is the carry output of the full adder. Now from truth table we can write output equations as:

Output equation of output S (Sum output)
= F(A, B, Cin)
= ∑m (1, 2, 4, 7)
And output equation of Cout (Carry output)
= F(A, B, Cin)
= ∑m (3, 5, 6, 7)

Designing a full adder using Decoder can be implemented by using a 3-to-8 line decoder. Since, a Decoder is a Minterm generator, we can use those Minterms of Decoder to represent the Boolean functions of sum (S) and carry out (Cout) outputs. The figure shows the logic circuit diagram of full adder using a 3-to-8 line Decoder and two OR gates. Here A, B, and Cin are three inputs to Decoder. EN is enable input which follows active high logic. Y0 to Yare the eight Minterms which are from mto m8. Full adder gives the sum output 1 only when mor mor mor m7  is 1. So, we can write S = m1+m2+m4+m7. Similarly full adder gives the Cout output 1 only when m3 or m5 or m6 or m7 is 1. So, we can write Cout = m3+m5+m6+m7.

IMPLEMENTATION OF FULL ADDER USING HALF ADDERS AND LOGIC GATES

A Full Adder can be made using Half Adders and logic gates like AND gates, OR gate. To implement this circuit two Half Adders, one OR gate, and two AND gates are used. These two Half Adders are named by HA1 and HA2. First Half Adder HA1 has two inputs X and Y respectively, S (for sum) and C (for carry) are the two outputs of the HA1, where S = X’Y+XY’ and C = XY, where S and C are the sum output and carry output of HA1. The output S of first HA1 is the first input of HA2, Z is the second input to the HA2, S’ is the sum output of the second HA2 that is equal to XY’Z’+X’YZ’+X’Y’Z+XYZ   and it is the sum output of a Full Adder. To get carry output of the Full Adder logic gates are used. The carry output of a Full Adder is XY + XZ + YZ, where X, Y, and Z are the inputs. To get this output two AND gates and one OR gate is used, the first AND gate has the inputs X and Z and generates the output XZ, similarly the second AND gate has two inputs Y and Z and produces the output YZ. These two outputs XZ and YZ as well as the output XY of the HA1 is used as three inputs for the OR gate. This OR gate generates the output XY+YZ+XZ that is equivalent to the carry output of a Full Adder. The logic diagram of the Full Adder using Half Adder and logic gates is given below.

LOGIC DIAGRAM OF FULL ADDER USING HALF ADDERS AND LOGIC GATESIMPLEMENTATION OF FULL ADDER USING MUX OR MULTIPLEXER

From the above truth table of Full Adder and information supplied we know that the sum output and carry output of a Full Adder is as written: S = F (A, B, Cin) = ∑(1, 2, 4, 7) and Cout = F (A, B, Cin) = ∑(3, 5, 6, 7). Where A, B, Cin are the inputs to the Full Adder. S and Cout are the sum output and carry output respectively. Now, the given requirement of designing a Full Adder using MUX (Multiplexer) can be implemented by 2X1 MUX or 4X1 MUX or 8X1 MUX.

IMPLEMENT OF FULL ADDER USING 8X1 MUX OR MULTIPLEXER

LOGIC DIAGRAM OF FULL ADDER USING 8X1 MUX OR MULTIPLEXER

At first we are going to implement this Full Adder by 8X1 Multiplexer. To implement this circuit we need two 8X1 Multiplexers the first one gives the output for sum output of Full Adder and second gives output for carry output of Full Adder. The general output equation of a 8X1 MUX or Multiplexer is as follows:

Y = I0S’2S’1S’0 + I1S’2S’1S0 + I2S’2S1S’0 + I3S’2S1S0 + I4S2S’1S’0 + I5S2S’1S0 + I6S2S1S’0 + I7S2S1S0 is equation number one (1).

Where Y is the output of 8X1 MUX or Multiplexer S2, S1 and S0 are the selection inputs to the MUX and I0, I1, I2, I3, I4, I5, I6 and I7 are the inputs to the multiplexer. Now, the output equation of the sum output of Full Adder is as follows:

S
= F(A, B, Cin)
= ∑(1, 2, 4, 7)
= m1 + m2 + m4 +m7
= A’B’Cin + A’BC’in + AB’C’in + ABCin
= 0.A’B’C’in + 1.A’B’Cin + 1.A’BC’in + 0.A’BCin + 1.AB’C’in + 0.AB’Cin 0.ABC’in + 1.ABCin is equation number two (2).

Now, comparing equations (1) & (2) we get

I0 = 0, I1 = 1, I2 = 1, I3 = 0, I4 = 1, I5 = 0, I6 = 0 and I7 = 1. And S2 = A, S1 = B and S0 = Cin.

These values are for first multiplexer for sum output of Full Adder. Now, we will find all values for second MUX for carry output of Full Adder. The general output equation of carry output is as follows:

Cout
= F(A, B, Cin)
= ∑(3, 5, 6, 7)
= m3 + m5 + m6 + m7
= A’BCin + AB’Cin + ABC’in + ABCin
= 0.A’B’C’in + 0.A’B’Cin + 0.A’BC’in + 1.A’BCin + 0.AB’C’in + 1.AB’Cin + 1.ABC’in  + 1.ABCin is equation number three (3).

Comparing the equations (1) & (3) we have

I0 = 0, I1 = 0, I2 = 0, I3 = 1, I4 = 0, I5 = 1, I6 = 1 and I7 = 1. And S2 = A, S1 = B and S0 = Cin.

These values are for second multiplexer for carry output of Full Adder. Now, we have all the values of the two multiplexers therefore the circuit of the Full Adder can be implemented. The block diagram of Full Adder is shown here.

IMPLEMENTATION OF FULL ADDER USING 4X1 MUX OR MULTIPLEXER

LOGIC DIAGRAM OF FULL ADDER USING 4X1 OR 4-TO-1 MULTIPLEXER

We already know the sum output and carry output of a Full Adder. Now, we have to write the general output equation of a 4X1 MUX or Multiplexer and it is as follows:

Y = I0S’1S’0 + I1S’1S0 + I2S1S’0 + I3S1S0 is equation number one (1).

Where Y is the output of the MUX or Multiplexer Sand S2 are the selection inputs. From I0 to Iare the inputs to the MUX or Multiplexer.

Now, the output equation of the sum of Full Adder is as follows:

S
= F(A, B, Cin)
= ∑(1, 2, 4, 7)
= m1 + m2 + m4 +m7
= A’B’Cin + A’BC’in + AB’C’in + ABCin
= A.(B’C’in) + A’.(B’Cin) + A’.(BC’in) + A.(B’C’in) is equation number (2).

Comparing equations (1) & (2) we have

I0 = A, I1 = A’, I2 = A’, I3 = A. And S1 = B, S0 = Cin.

Now, the output equation of carry output of Full Adder is as follows:

Cout
= F (A, B, Cin)
= ∑(3, 5, 6, 7)
= m3 + m5 + m6 + m7
= A’BCin + AB’Cin + ABC’in + ABCin
= (A’ + A) BCin + AB’Cin + ABC’in + 0.AB’C’in
= 0.(B’C’in) + A.(B’Cin) + A.(BC’in) + 1.(BCin) is equation number (3).

Comparing equation (1) and (3) we have

I0 = 0, I1 = A, I2 = A, I3 = 1 and S1 = B, S0 = Cin.

The logic diagram of Full Adder using 4X1 MUX or Multiplexer is shown above. From the above picture, it can be shown that a Full Adder can be implemented by two 4X1 MUX or Multiplexers. One MUX or Multiplexer is used to find the sum of the FA (Full Adder) and other is used to get the carry output of FA. Each 4X1 MUX has two selection input lines which are used to select one of the inputs from I0 to I3. Here, two selection inputs of each 4X1 MUX or Multiplexers are replaced by the two inputs of Full Adder B and Cin and the values of Ito I3 of each 4X1 MUX has given.

IMPLEMENTATION OF FULL ADDER USING 2X1 MUX OR MULTIPLEXER

LOGIC DIAGRAM OF FULL ADDER USING 2X1 MULTIPLEXERHere, it is implemented by 2X1 MUX. The general output equation of 2X1 MUX is written as:

Y = I0S’0 + I1S0 is equation number one (1).

Where Y is the output to MUX, S0 is the selection input to the MUX and I0 and I1 are the inputs to MUX. Now, output equation of sum output Full Adder is as follows:

S
= F (A, B, Cin)
= ∑m (1,2,4,7)
= m1 + m2 + m4 +m7
= A’B’Cin + A’BC’in + AB’C’in + ABCin
= (A’B + AB’).C’in + (A’B’ + AB).Cin is equation number two (2).

Comparing equations (1) & (2) we get

I0 = A’B + AB’, I1 = A’B’ + AB and S0 = Cin.

Now, output equation of carry out of Full Adder is as follows:

Cout
= F (A, B, Cin)
= ∑m (3, 5, 6, 7)
= m3 + m5 + m6 + m7
= A’BCin + AB’Cin + ABC’in + ABCin
= (AB)Cin + (A’B + AB’ + AB)Cin
= (AB)Cin + (A + B)Cin is equation number (3).

Comparing equation (1) & (3) we have

I0 = AB, I1 = A + B and S0 = Cin.

IMPLEMENTATION OF FULL ADDER USING NAND GATE

The circuit diagram of a Full Adder can be implemented by using only NAND gates because we know that NAND gates are called universal logic gates. A universal gate means a gate which is alone sufficient to implement any circuit. Hence, the circuit of the Full Adder using NAND gates is shown below. We know that the sum output of Full Adder and the carry output is as follows:

S
= F(A,B,Cin)
= ∑(1,2,4,7)
= m1 + m2 + m4 +m7
= A’B’Cin + A’BC’in + AB’C’in + ABCin

Cout
= F (A, B, Cin)
= ∑m (3, 5, 6, 7)
= m3 + m5 + m6 + m7
= A’BCin + AB’Cin + ABC’in + ABCin
= AB + ACin + BCin

To implement the circuit by NAND gates first we have to take the double complement of the sum output and carry output. After complementing two times the sum output and carry output, the terms of the obtained output equations are the output of each NAND gates and all these output are directed as input to a NAND gate which gives the final outputs.

{(S)’}’ = {( A’B’Cin + A’BC’in + AB’C’in + ABCin )’}’
S = { (A’B’Cin)’. (A’BC’in)’. (AB’C’in)’. (ABCin)’}’   and

{(Cout)’}’= {(AB + ACin + BCin)’
Cout = {(AB)’. (ACin)’.(BCin)’}’   

The circuit diagram of the full Adder using NAND gates is shown here.

CIRCUIT DIAGRAM OF FULL ADDER USING NAND GATES

IMPLEMENTATION OF FULL ADDER USING NOR GATES

Designing the circuit diagram of a Full Adder using NOR Gates can be done by as we done above with NAND Gates. There a few steps we need to take to construct the circuit and these steps are listed below.
  1. Change the sum output and Carry output equations into Canonical form.
  2. Change the sum output and carry output equations into sum of product forms.
  3. Take double complement of sum output equation and carry output equation.
Sum output of Full Adder is X = A’B’C+A’BC’+AB’C’+ABC and carry output of Full Adder is Y = AB+BC+AC where A, B and C are three inputs and X and Y are outputs of the Full Adder.
Since the Sum output of the Full Adder is in canonical form and also in product of sum form so we have to execute the second step. Here we will use K-Map to convert the output equations into SOP form.
X (A, B, C)
= A’B’C+A’BC’+AB’C’+ABC
= ∑m (1, 2, 4, 7)
Here K-Map for Sum output is shown. To find the SOP form we have to cover the all zeros as the combinations of them should be minimum. One thing we need to know that the covering is done either horizontally or vertically with adjacent same value. Since in the above map there are no adjacent zeros either vertically or horizontally. By covering zeros we find the complement of the sum output. Thus we get
X’ = A’B’C’+A’BC+AB’C+ABC’
Now take Complement of X’, we obtain the simplified function in product of sum form:
(X’)’ = (A+B+C)(A+B’+C’)(A’+B+C’)(A’+B’+C)
X = (A+B+C)(A+B’+C’)(A’+B+C’)(A’+B’+C)
Similarly we can change the carry output equation into product of sum form. The carry output equation is Y = AB+BC+AC. Since the equation is not in canonical form so at first we will change it in canonical form.
Y = AB+BC+AC
= AB.1+BC.1+AC.1
= AB(C+C’)+BC(A+A’)+AC(B+B’)
= ABC+ABC’+ABC+A’BC+ABC+AB’C
= ABC+ABC+ABC+A’BC+AB’C+ABC’
= ABC+ A’BC+AB’C+ABC’
Now the carry output equation has been changed into canonical form. Thus perform the second step.
Y (A, B, C)
= ABC+ A’BC+AB’C+ABC’
= ∑m (3, 5, 6, 7)
K-Map for carry output is shown above. From the above K-Map we can write:
= A’B’+B’C’+A’C’
Taking complement of Y’ we obtain the product of sum form of carry output:
(Y’)’ = (A+B)(B+C)(A+C)
Y = (A+B)(B+C)(A+C)
Now we will take last step,
X = (A+B+C)(A+B’+C’)(A’+B+C’)(A’+B’+C)
(X’)’ = [{(A+B+C)(A+B’+C’)(A’+B+C’)(A’+B’+C)}’]’
X = [(A+B+C)’+(A+B’+C’)’+(A’+B+C’)’+(A’+B’+C)’]’
Similarly
Y = (A+B)(B+C)(A+C)
(Y’)’ = [{(A+B)(B+C)(A+C)}’]’
Y = [(A+B)’+(B+C)’+(A+C)’]’
Using X = [(A+B+C)’+(A+B’+C’)’+(A’+B+C’)’+(A’+B’+C)’]’ and
Y = [(A+B)’+(B+C)’+(A+C)’]’
We will design the circuit. The circuit of Full Adder using NOR Gates is shown below.
CIRCUIT DIAGRAM OF FULL ADDER USING NOR GATES

SEE MORE: 

HALF ADDER

The most basic digital arithmetic circuit is the addition of two binary numbers. A combinational circuit that performs the addition of two bits is called a half adder. One that performs the addition of three bits (two significant bits and a previous carry) is called a full adder. The name of the former terms from the fact that two half adders are needed to implement a full adder. The input variables of a half adder are called the augend and addend bits. The output variables the sum and carry. It is necessary to specify two output variables because the sum of 1+1 is 10, which has two digits. We assign two symbols x and y to the two input variables, and S (for sum) and C (for carry) to the two output variable.

LOGIC DIAGRAM AND TRUTH TABLE OF HALF ADDER

The logic diagram of the Half adder is shown below. It consists of an exclusive-OR gate and an AND gate. A half adder logic module of an exclusive-OR gate and an AND gate can be used to implement universal logic gates NAND and NOR. The truth table for the half adder is given below. The C output is 0 unless both inputs are 1. The S output represents the least significant bit of the sum. The Boolean functions for the two outputs can be obtained directly from the truth table.
S=x’y+xy’ and C=xy

LOGIC DIAGRAM AND TRUTH TABLE OF HALF ADDER

NAND GATE REALISATION USING HALF ADDER

A NAND Gate can be implemented using Half adder. To implement a NAND Gate we need two Half adders. The block diagram is shown below. There are two Half adders namely HA1 and HA2. The first half adder (HA1) has two inputs x and y. C is the carry output of the HA1 which is equal to xy. Now, output C generated by HA1 is the first input for second Half adder (HA2) and the second input to the HA2 is 1. S1 and C1 are the outputs of HA2 where S1 is sum output and C1 is carry output. Now, sum output S1 is the xor of 1 and xy  which finally gives (xy)’ and this is equivalent to the output of a NAND Gate.

NAND GATE USING HALF ADDER

NOR GATE REALISATION USING HALF ADDER

A NOR Gate realisation can be implemented using Half adders, the block diagram of NOR Gate using Half adder is shown below. We require three Half adders to implement which are named as HA1, HA2 and HA3. HA1 and HA2 produced the complement of the inputs x and y. HA1 has input 1 and x and produced the sum output (S) x’. Similarly HA2 has inputs 1 and y and gives the sum output(S’) y’, these two sum output are the two inputs for HA3 and the carry output of this Half adder gives the output of a NOR Gate.

LOGIC DIAGRAM OF NOR GATE USING HALF ADDER

IMPLEMENTATION OF HALF ADDER USING DECODER

Here, it is a truth table of a Half adder which adds two bits TRUTH TABLE OF HALF ADDERA and B, where A and B are addend and augend respectively. S and C are the outputs of the Half adder where S is the sum of the Half adder and C is the carry output of Half adder. From the truth table of Half–Adder we can write:
S = F (A, B) = ∑(1,2) and,
C = F (A, B) = ∑(3)Now, to implement the circuit of Half adder we use 2-to-4 line decoder. Since, a decoder is a minterm generator we can use those minterms of Decoder which represent  the Boolean function of sum (S) and carry output (C).

The picture shows the logic circuit diagram of Half addeLOGIC DIAGRAM OF HALF ADDER USING DECODER AND OTHER LOGIC GATESr using decoder and one OR Gate and one buffer gate. Here A and B are the inputs to decoder EN is the enable input which follows active high logic (mean decoder gets active when enable input is 1). m to m are four minterms.

 Now, decoder gives the sum output 1 only when either mor m2 is 1. So we can write S = m+ m2. Similarly decoder gives the C output 1 only when m3 is 1. So we can write C = m3.

IMPLEMENTATION OF HALF ADDER USING MUX OR MULTIPLEXERS

In the above topic we have implemented a circuit by the use of a decoder that generates the outputs of a Half adder in the same manner we can implement a circuit by the use of Multiplexers and that will produce the outputs of a Half adder. A Half adder can be implemented by 4X1 MUX as well as by 2X1 MUX.

IMPLEMENTATION OF HALF-ADDER USING 4X1 MUX

LOGIC DIAGRAM OF HALF ADDER USING 4X1 MUX

As we have stated above a Half adder can be implemented by a 4X1 MUX. Now we are going to implement this circuit. The truth table of a Half adder is shown in the above topic from the truth table we can have:

S = F (A, B) = ∑(1,2) and, C = F (A, B) = ∑(3) Where S is the sum output and C is the carry output of the Half Adder. Now the general output equation of a 4X1 multiplexer is as written:

Y = I0S’1S’0+ I1S’1S0 + I2S1S’0+ I3S1S0 equation two (1)

Where Y is the output of Half adder, S1 and S0 are the selection inputs of HA and from I0 to I3 these are the inputs to Half adder. The output equation of sum output of Half adder is as follows:
S = ∑(1,2)
= m1 + m2
= A’B + AB’
= 0.A’B’ + 1.A’B + 1.AB’ + 0.AB equation two (2)
Comparing equation (1) and (2) we have
I0 = 0, I1 = 1, I2 = 1, I3 = 0 and S1 = A, S0 = B.
Again the general output of carry out of Half adder is written as:
C = ∑(3)
= M3
                   = AB
= 0.A’B’ + 0.A’B + 0.AB’ + 1.AB equation three (3)
Comparing equations (1) and (3) we get
I0 = 0, I1 = 0, I2 = 0, I3 = 1 and S1 = A, S0 = B.

From the above picture it can be stated that to implement the logic diagram of a Half adder we need two multiplexers the first multiplexer produces sum output (S) of Half adder and the second MUX generates the carry output (C) of the Half adder, A and B are the two selection inputs to the both multiplexers to select a particular input. The values of inputs of both multiplexers are obtained by comparing equations (1) & (2) and equations (1) & (3). This is the required logic diagram of Half adder 4X1 using multiplexers is shown above.

IMPLEMENTATION OF HALF-ADDER USING 2X1 MUX

LOGIC DIAGRAM OF HALF ADDER USING 2X1 MUX

Here we will implement the logic diagram of a Half adder using 2X1 multiplexer. The general output equation of a 2X1 multiplexer is as follows:

Y = I0S’0 + I1S0 equation one (1)

Where Y is the output of HA, SO is the selection input line to HA which select a particular input at a time and I0 and I1are the inputs to HA.

Now the general output equation of sum output of a Half adder is written as:
S
= ∑(1,2)
= m1 + m2
= A’B + AB’ equation two (2)
Comparing equations (1) & (2) we have
I0= A, I1 = A’ and S0 = B.
Next the general output equation of carry output of Half adder is as follows:
C= ∑(3)
= M3
= AB
= 0.AB’ + AB equation three (3)
Comparing equations (1) and (3) we have
I0= 0, I1 = A and S0 = B.

IMPLEMENTATION OF HALF ADDER USING NAND GATES

Since NAND Gate is a universal Gate because it is alone sufficient to implement any logical circuit. Here we are going to realise a Half adder logic circuit with the sole use of NAND Gates only. The output equations, the Sum output equation and Carry output equation, of a Half adder are as: S = AB’+A’B and C = AB. CIRCUIT DIAGRAM OF HALF ADDER USING NAND GATESHere A and B are inputs. To design any Boolean circuit by NAND Gates only, the Boolean expression must satisfy a condition. The condition is as follows: the Boolean expression must be in Product of Sum form. If this condition satisfies then we can proceed further else we try to change the Boolean function in a new expression which is in Product of Sum form. Now we take double complement of each output expressions of Half adder of both sides. Thus the above output expressions of Half adder become:

S = AB’+A’B
(S’)’ = [(AB’+A’B)’]’
(S’)’ = [(AB’)’.(A’B)’]’
S = [(AB’)’.(A’B)’]’

Since the double complement of any variable is the variable itself. So (S’)’ = S.

The above Sum output equation is the equation of Sum output when the circuit is designed by using NAND Gates.

Similarly we can write for Carry output of the Half adder as using NAND Gates.

C = AB
(C’)’ = [(AB)’]’
C = [(AB)’]’

One thing it is to be note here that in each final output equations there is no OR operator (+). Finally design the circuit using the output equations: S = [(AB’)’.(A’B)’] and C = [(AB)’]’.

IMPLEMENTATION OF HALF ADDER USING NOR GATES

As a NOR Gate is basic building block any logical circuit can be realized by it. A NOR Gate is treated as a universal gate because it can be used to design the primary logic gates AND, OR and NOT gates. If A and B are to inputs CIRCUIT DIAGRAM OF HALF ADDER USING NOR GATESto a half adder and S and C are the Sum output and Carry output respectively of the half adder then: S = AB’+A’B and C = AB.

As in the above case of there is a condition to realize any circuit by NAND Gates thus there is also a condition that is as follows: the given Boolean expression or Boolean expressions must be in Sum-of-Product form. If the given expression is not in the Sum-of-Product form then we have to change it into Sum-of-Product form. Once the above condition is satisfied we can ahead further as in case of NAND Gate by taking double complement of each expression.

Since S = AB’+A’B, the sum output is in Product-of-Sum form we have to change it into Sum-of-Product form.

S = AB’+A’B
S = AB’+A’B+0+0
S = AB’+A’B+AA’+BB’
S = AB’+AA’+A’B+BB’
S = A(B’+A’)+B(A’+B’)
S = A(A’+B’)+B(A’+B’)
S = (A+B)(A’+B’)

Now the sum output of the half adder is in Sum of Product form. Thus we can take double complement of the sum output. So it becomes as:

(S’)’ = [{(A+B)(A’+B’)}’]’
(S’)’ = [(A+B)’+(A’+B’)’]’
S = [(A+B)’+(A’+B’)’]’

Since double complement of S is S. It is to be noticed here that in the final expression there is no AND operator (.) or we can say it is free from AND operator.

Similarly we can do the same operation for carry output by taking double complement.

(C’)’ = [(AB)’]’
(C’)’ = [(A)’+(B)’]’
C = [(A)’+(B)’]’

Now we have the desired expression for NOR Gate. Thus we use the expressions S = [(A+B)’+(A’+B’)’]’ and C = [(A)’+(B)’]’ to implement the circuit of half adder using NOR Gates.

WHAT IS PRODUCT OF SUM

A product of sum expression is a sum term (maxterm) or several maxterms logically multiplied (ANDed) together. For example, the expression (X’+Y).(X+Y’) is a product of sum expression.

The following steps are used to express a Boolean function in its product of sum form:

  1. Construct a truth table for the given Boolean function.
  2. Form a maxterm for each combination of the variables which produces a 0 in the function.
  3. The desired expression is the sum (AND) of all the maxterms obtained in step 2.
  4. For example, 000, 010, 011, 101, 110. The following five combinations of the variable produce a 0.

Their corresponding maxterms are:

(X+Y+Z), (X+Y’+Z), (X+Y’+Z’), (X’+Y+Z’), and (X’+Y’+Z)

If taking the product (AND) of all these maxterms, we can write them as

F
= (X+Y+Z).(X+Y’+Z).(X+Y’+Z’).(X’+Y+Z’).(X’+Y’+Z)
= M0.M2.M3.M5.M6

Let us take an example: Express the Boolean function in the product-of-sum form.

F = X.Y+X’.Y
At first convert the function into OR term using the distributive law;
F
= X.Y+X’.Z
= (X.Y+X’).(X.Y+Z)
= (X+X’).(Y+X’).(X+Z).(Y+Z)
= (X+Y’).(X+Z).(Y+Z)

The function has three variables X, Y, and Z. Each OR term is missing one variable, therefor:

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

Combining all the terms and removing those that appear more than one, we finally obtain:

F = (X+Y+Z).(X+Y’+Z).(X’+Y+Z).(X’+Y+Z’)
F = M0.M2.M4.M5
F (X,Y,Z) = π(0,2,4,5)

The product symbol π denotes the ANDing of the maxterms. The numbers following it are the maxterms of the function.

CANONICAL FORMS FOR BOOLEAN FUNCTION

A Boolean function specified by a truth table can be expressed algebraically in many different ways. Two ways of forming Boolean expression are canonical and non canonical forms.

Canonical Forms:

Canonical forms express all binary variables in every product (AND) or sum (OR) term of the Boolean function. There are two types of canonical forms of a Boolean function. The first one is called sum of product and the second one is called product of sum. A’BC+A’BC’+ABC’+AB’C’+A’B’C’+ABC is a canonical sum of product form of a Boolean function, the given function has contained three inputs that means three binary variables. In each term of the given function has contained three variables.  (X’+Y+Z).(X+Y’+Z).(X’+Y+Z).(X’+Y+Z’) is a canonical product of sum form of a Boolean function.

Non Canonical Forms:

Non canonical forms do not express all binary variables in every product or sum term of the Boolean function.

Minterms and Maxterms

A binary variable may appear either in its normal form (X) OR in its complement form (X’). Now consider two binary variables X and Y combined with an AND operation. Since each variable may appear in either form, these are four possible combinations ( X’.Y’, X’.Y, X.Y’, X.Y). Each of these four AND terms is called a minterm or a standard product. In a similar manner, n variables can be combined to form 2n minterm. The 2different minterms may be determined by a method similar to the one shown below for three variables. The binary numbers from 0 to 2n – 1 are listed under the n variable. Each minterm is obtained from an AND term of the n variables, with each variable being primed if the corresponding bit of the binary number is 0 and unprimed if a 1. In a similar fashion, n variables forming an OR term, with each variable being primed or unprimed, provide 2n possible combinations called maxterms or standard sums. The eight maxterms for three variables, together with their symbolic designation, are listed below. Any 2n maxterms for n variables may be determined similarly. Each maxterm is obtained from an OR term of the n variables, with each variable being unprimed if the corresponding bit is 0 and primed if it is a 1.

MINTERMS AND MAXTERMS FOR THREE VARIABLES

VARIABLES MINTERMS MAXTERMS
X Y Z TERM DESIGNATION TERM DESIGNATION
0 0 0 X’. Y’. Z’ m0 X+Y+Z M0
0 0 1 X’. Y’. Z m1 X+Y+Z’` M1
0 1 0 X’. Y. Z’ m2 X+Y’+Z M2
0 1 1 X’. Y. Z m3 X+Y’+Z’ M3
1 0 0 X. Y’. Z’ m4 X’+X+Z M4
1 0 1 X. Y’. Z m5 X’+Y+Z’ M5
1 1 0 X. Y. Z’ m6 X’+Y’+Z M6
1 1 1 X. Y. Z m7 X’+Y’+Z’ M7

SUM OF PRODUCT

A sum of product expression is a product term (minterm) or several product terms (minterms) logically added (ORed) together. The following steps are used to express a Boolean function in its sum-of –product form:

Construct a truth table for the given Boolean function.

Form a minterm for each combination of the variables which produces a 1 in the function.

The desired expression is the sum (OR) of all the minterms obtained in step 2.

For example: 011, 100 and 111 their corresponding minterms are X’.Y.Z, X.Y’.Z’, X.Y.Z. Hence, taking the sum of all these minterms, the given function can be expressed in its sum of product form as:

F1 = X’.Y.Z + X.Y’.Z’ + X.Y.Z
F1 = m3+m4+m7

Similarly, F2 = X’.Y.Z + X.Y’.Z + X.Y.Z’ + X.Y.Z can be easily expressed in its sum of product form:

F2 = X’.Y.Z + X.Y’.Z + X.Y.Z’ + X.Y.Z
F2 = m3+m5+m6+m7

X Y Z F1 F2
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 1 1 1 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

This is the truth table for F1 and F2. It is sometimes convenient to express a Boolean function in its sum of product form. If not in this form, it can be made. So by first expanding the expression into a sum of AND terms. Each term is then inspected to see if it contains all the variables. If it misses one or more variables, it is ANDed with an expression of the form (X+X’), where X is one of the missing variable. Let us take an example, express the given Boolean function into its sum of product form.

F = A’.(B+C’)
F = A’.B+A’.C’

The given function has three variables A, B, and C. The first term of the function A’B is missing one variable, therefore

A’B = A’.B.(C+C’)
A’B = A’.B.C+A’B.C’

Similarly, the second term of the function A’C’ is missing one variable, therefore

A’.C’= A’.C’.(B+B’)
A’.C’ = A’.C’.B+A’.C’.B’

So by combining all the terms we get

F = A’.B.C+A’.B.C’+A’.C’.B+A’.B’.C’
F = A’.B.C+A’.B.C’+A’.B.C’+A’.B’.C’

But in the above expression, the term A’.B.C’ appears twice and according to Boolean postulate we have X+X’ = X. Hence it is possible to remove one of them.

F = A’.B.C+A’.B.C’+A’.B’.C’

Rearranging the minterms in ascending order, we finally obtain:

F = A’.B’.C’+A’.B.C’+A’.B.C
F = m0+m2+m3
F (A, B, C) = ∑ (0, 2, 3)

The summation symbol ‘∑’ stands for the ORing of terms. The numbers following it are the minterm of the function.

PRODUCT OF SUM

A product of sum expression is a sum term (maxterm) or several maxterms logically multiplied (ANDed) together. For example, the expression (X’+Y)(X+Y’) is a product of sum expression. The following steps are used to express a Boolean function in its product of sum form:

Construct a truth table for the given Boolean function.

Form a maxterm for each combination of the variables which produces a 0 in the function.

The desired expression is the sum (AND) of all the maxterms obtained in step 2.

For example: 000, 010, 011, 101, 110. The following five combinations of the variable produce a 0.

Their corresponding maxterms are: (X+Y+Z), (X+Y’+Z), (X+Y’+Z’), (X’+Y+Z’), and (X’+Y’+Z). If taking the product (AND) of all these maxterms, we can write them as

F = (X+Y+Z).(X+Y’+Z).(X+Y’+Z’).(X’+Y+Z’).(X’+Y’+Z)
F = M0.M2.M3.M5.M6

Let us take an example:-Express the Boolean function in the product of sum form.

F = X.Y+X’.Y
Atfirst convert the function into OR term using the distributive law;
F = X.Y+X’.Z
= (X.Y+X’).(X.Y+Z)
= (X+X’).(Y+X’).(X+Z).(Y+Z)
= (X+Y’).(X+Z).(Y+Z)
The function has three variables X, Y, and Z. Each OR term is missing one variable, therefor:

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

Combining all the terms and removing those that appear more than one, we finally obtain:

F = (X+Y+Z).(X+Y’+Z).(X’+Y+Z).(X’+Y+Z’)
F = M0.M2.M4.M5
F (X,Y,Z) = π (0,2,4,5)

The product symbol π denotes the ANDing of the maxterms. The numbers following it are the maxterms of the function.