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 twoelement Boolean algebra B_{2} = ({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 fourbit binary numbers, we need to construct a four bit parallel binary adder as shown below. Such an adder requires one HalfAdder denoted by HA and three FullAdders denoted by FA. The binary numbers being added are A_{4} A_{3} A_{2} A_{1} and B_{4} B_{3} B_{2} B_{1} and the answer is:
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:
SECOND THEOREM:
PROOF OF De MORGAN’S THEOREM:
 (X+Y)’ = X’.Y’
 (X.Y)’ = X’+ Y’
PROOF OF FIRST LAW OF De Morgan’s Theorem:
[BY X+YZ = (X+Y)(X+Z)]
[BY X+Y = Y+X]
[BY X+X’ = 1]
[BY X+1 = 1]
[BY X.(Y+Z) = X.Y+X.Z ]
[BY X.Y = Y.X]
[BY X.X’ = 0]
PROOF OF SECOND LAW OF De Morgan’s Theorem:
[BY X+YZ = (X+Y)(X+Z)]
[BY X+Y = Y+X]
[BY X+X’ = 1]
[BY 1+X’ = 1]
[BY X.(Y+Z) = X.Y+X.Z]
[BY X.Y = Y.X]
[BY X.0 = 0]
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 fulladder 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 fulladder 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 exclusiveOR 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 halfadders 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 Kmap for obtaining sum output and carry output is also given below.
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

IMPLEMENTATION OF FULL ADDER USING 3TO8 LINE DECODER:
Output equation of output S (Sum output)
= F(A, B, C_{in})
= ∑_{m} (1, 2, 4, 7)
And output equation of C_{out} (Carry output)
= F(A, B, C_{in})
= ∑_{m} (3, 5, 6, 7)
Designing a full adder using Decoder can be implemented by using a 3to8 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 (C_{out}) outputs. The figure shows the logic circuit diagram of full adder using a 3to8 line Decoder and two OR gates. Here A, B, and C_{in }are three inputs to Decoder. EN is enable input which follows active high logic. Y_{0} to Y_{7 }are the eight Minterms which are from m_{0 }to m_{8}. Full adder gives the sum output 1 only when m_{1 }or m_{2 }or m_{4 }or m_{7 }is 1. So, we can write S = m_{1}+m_{2}+m_{4}+m_{7}. Similarly full adder gives the C_{out} output 1 only when m_{3} or m_{5} or m_{6} or m_{7} is 1. So, we can write C_{out} = m_{3}+m_{5}+m_{6}+m_{7.}
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.
IMPLEMENTATION OF FULL ADDER USING MUX OR MULTIPLEXER
IMPLEMENT 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 = I_{0}S’_{2}S’_{1}S’_{0} + I_{1}S’_{2}S’_{1}S_{0} + I_{2}S’_{2}S_{1}S’_{0} + I_{3}S’_{2}S_{1}S_{0} + I_{4}S_{2}S’_{1}S’_{0} + I_{5}S_{2}S’_{1}S_{0} + I_{6}S_{2}S_{1}S’_{0} + I_{7}S_{2}S_{1}S_{0} is equation number one (1).
Where Y is the output of 8X1 MUX or Multiplexer S_{2}, S_{1} and S_{0} are the selection inputs to the MUX and I_{0}, I_{1}, I_{2}, I_{3}, I_{4}, I_{5}, I_{6} and I_{7} are the inputs to the multiplexer. Now, the output equation of the sum output of Full Adder is as follows:
S
= F(A, B, C_{in})
= ∑(1, 2, 4, 7)
= m_{1} + m_{2} + m_{4} +m_{7
}= A’B’C_{in} + A’BC’_{in} + AB’C’_{in} + ABC_{in}
= 0.A’B’C’_{in} + 1.A’B’C_{in} + 1.A’BC’_{in} + 0.A’BC_{in} + 1.AB’C’_{in} + 0.AB’C_{in} 0.ABC’_{in} + 1.ABC_{in} is equation number two (2).
Now, comparing equations (1) & (2) we get
I_{0} = 0, I_{1} = 1, I_{2} = 1, I_{3} = 0, I_{4} = 1, I_{5} = 0, I_{6} = 0 and I_{7} = 1. And S_{2} = A, S_{1} = B and S_{0} = C_{in}.
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:
C_{out
}= F(A, B, C_{in})
= ∑(3, 5, 6, 7)
= m_{3} + m_{5} + m_{6} + m_{7
}= A’BC_{in} + AB’C_{in} + ABC’_{in} + ABC_{in
}= 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
I_{0} = 0, I_{1} = 0, I_{2} = 0, I_{3} = 1, I_{4} = 0, I_{5} = 1, I_{6} = 1 and I_{7} = 1. And S_{2} = A, S_{1} = B and S_{0} = C_{in}.
IMPLEMENTATION OF FULL ADDER USING 4X1 MUX OR 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 = I_{0}S’_{1}S’_{0} + I_{1}S’_{1}S_{0} + I_{2}S_{1}S’_{0} + I_{3}S_{1}S_{0} is equation number one (1).
Where Y is the output of the MUX or Multiplexer S_{1 }and S_{2} are the selection inputs. From I_{0} to I_{3 }are the inputs to the MUX or Multiplexer.
Now, the output equation of the sum of Full Adder is as follows:
S
= F(A, B, C_{in})
= ∑(1, 2, 4, 7)
= m_{1} + m_{2} + m_{4} +m_{7
}= A’B’C_{in} + A’BC’_{in} + AB’C’_{in} + ABC_{in
}= A.(B’C’_{in}) + A’.(B’C_{in}) + A’.(BC’_{in}) + A.(B’C’_{in}) is equation number (2).
Comparing equations (1) & (2) we have
I_{0} = A, I_{1} = A’, I_{2} = A’, I_{3} = A. And S_{1} = B, S_{0} = C_{in}.
Now, the output equation of carry output of Full Adder is as follows:
C_{out
}= F (A, B, C_{in})
= ∑(3, 5, 6, 7)
= m_{3} + m_{5} + m_{6} + m_{7
}= A’BC_{in} + AB’C_{in} + ABC’_{in} + ABC_{in}
= (A’ + A) BC_{in} + AB’C_{in} + ABC’_{in} + 0.AB’C’_{in
}= 0.(B’C’_{in}) + A.(B’C_{in}) + A.(BC’_{in}) + 1.(BC_{in}) is equation number (3).
Comparing equation (1) and (3) we have
I_{0} = 0, I_{1} = A, I_{2} = A, I_{3} = 1 and S_{1} = B, S_{0} = C_{in}.
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 I_{0} to I_{3}. Here, two selection inputs of each 4X1 MUX or Multiplexers are replaced by the two inputs of Full Adder B and C_{in} and the values of I_{0 }to I_{3} of each 4X1 MUX has given.
IMPLEMENTATION OF FULL ADDER USING 2X1 MUX OR MULTIPLEXER
Here, it is implemented by 2X1 MUX. The general output equation of 2X1 MUX is written as:
Y = I_{0}S’_{0} + I_{1}S_{0} is equation number one (1).
Where Y is the output to MUX, S_{0} is the selection input to the MUX and I_{0} and I_{1} are the inputs to MUX. Now, output equation of sum output Full Adder is as follows:
S
= F (A, B, C_{in})
= ∑_{m} (1,2,4,7)
= m_{1} + m_{2} + m_{4} +m_{7
}= A’B’C_{in} + A’BC’_{in} + AB’C’_{in} + ABC_{in
}= (A’B + AB’).C’_{in} + (A’B’ + AB).C_{in} is equation number two (2).
Comparing equations (1) & (2) we get
I_{0} = A’B + AB’, I_{1} = A’B’ + AB and S_{0} = C_{in}.
Now, output equation of carry out of Full Adder is as follows:
C_{out
}= F (A, B, C_{in})
= ∑_{m} (3, 5, 6, 7)
= m_{3} + m_{5} + m_{6} + m_{7
}= A’BC_{in} + AB’C_{in} + ABC’_{in} + ABC_{in
}= (AB)C_{in} + (A’B + AB’ + AB)C_{in
}= (AB)C_{in} + (A + B)C_{in} is equation number (3).
Comparing equation (1) & (3) we have
I_{0} = AB, I_{1} = A + B and S_{0} = C_{in}.
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,C_{in})
= ∑(1,2,4,7)
= m_{1} + m_{2} + m_{4} +m_{7
}= A’B’C_{in} + A’BC’_{in} + AB’C’_{in} + ABC_{in}
C_{out
}= F (A, B, C_{in})
= ∑_{m} (3, 5, 6, 7)
= m_{3} + m_{5} + m_{6} + m_{7
}= A’BC_{in} + AB’C_{in} + ABC’_{in} + ABC_{in}
= AB + AC_{in} + BC_{in}
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’C_{in} + A’BC’_{in} + AB’C’_{in} + ABC_{in })’}’_{ }S = { (A’B’C_{in})’. (A’BC’_{in})’. (AB’C’_{in})’. (ABC_{in})’}’ and
{(C_{out})’}’= {(AB + AC_{in} + BC_{in})’
C_{out} = {(AB)’. (AC_{in})’.(BC_{in})’}’_{ }
The circuit diagram of the full Adder using NAND gates is shown here.
IMPLEMENTATION OF FULL ADDER USING NOR GATES
 Change the sum output and Carry output equations into Canonical form.
 Change the sum output and carry output equations into sum of product forms.
 Take double complement of sum output equation and carry output equation.
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 exclusiveOR gate and an AND gate. A half adder logic module of an exclusiveOR 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
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.
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.
IMPLEMENTATION OF HALF ADDER USING DECODER
Here, it is a truth table of a Half adder which adds two bits A 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 2to4 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 adder 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_{0 } to m_{3 } are four minterms.
Now, decoder gives the sum output 1 only when either m_{1 }or m_{2} is 1. So we can write S = m_{1 }+ m_{2}. Similarly decoder gives the C output 1 only when m_{3} is 1. So we can write C = m_{3}.
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 HALFADDER 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 = I_{0}S’_{1}S’_{0}+ I_{1}S’_{1}S_{0} + I_{2}S_{1}S’_{0}+ I_{3}S_{1}S_{0} equation two (1)
Where Y is the output of Half adder, S_{1} and S_{0} are the selection inputs of HA and from I_{0} to I_{3} these are the inputs to Half adder. The output equation of sum output of Half adder is as follows:
S = ∑(1,2)
= m_{1} + m_{2
}= A’B + AB’
= 0.A’B’ + 1.A’B + 1.AB’ + 0.AB equation two (2)
Comparing equation (1) and (2) we have
I_{0} = 0, I_{1} = 1, I_{2} = 1, I_{3} = 0 and S_{1} = A, S_{0} = B.
Again the general output of carry out of Half adder is written as:
C = ∑(3)
= M_{3
} = AB
= 0.A’B’ + 0.A’B + 0.AB’ + 1.AB equation three (3)
Comparing equations (1) and (3) we get
I_{0} = 0, I_{1} = 0, I_{2} = 0, I_{3} = 1 and S_{1} = A, S_{0} = 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 HALFADDER 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 = I_{0}S’_{0} + I_{1}S_{0}_{ }equation one (1)
Where Y is the output of HA, S_{O} is the selection input line to HA which select a particular input at a time and I_{0} and I_{1}are the inputs to HA.
Now the general output equation of sum output of a Half adder is written as:
S
= ∑(1,2)
= m_{1} + m_{2
}= A’B + AB’ equation two (2)
Comparing equations (1) & (2) we have
I_{0}= A, I_{1} = A’ and S_{0} = B.
Next the general output equation of carry output of Half adder is as follows:
C= ∑(3)
= M_{3
}= AB
= 0.AB’ + AB equation three (3)
Comparing equations (1) and (3) we have
I_{0}= 0, I_{1} = A and S_{0} = 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. Here 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 to 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 SumofProduct form. If the given expression is not in the SumofProduct form then we have to change it into SumofProduct 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 ProductofSum form we have to change it into SumofProduct 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:
 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)
= M_{0}.M_{2}.M_{3}.M_{5}.M_{6}
Let us take an example: Express the Boolean function in the productofsum 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 = M_{0}.M_{2}.M_{4}.M_{5}
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 2^{n} minterm. The 2^{n }different minterms may be determined by a method similar to the one shown below for three variables. The binary numbers from 0 to 2^{n} – 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 2^{n} possible combinations called maxterms or standard sums. The eight maxterms for three variables, together with their symbolic designation, are listed below. Any 2^{n} 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’  m_{0}  X+Y+Z  M_{0} 
0  0  1  X’. Y’. Z  m_{1}  X+Y+Z’`  M_{1} 
0  1  0  X’. Y. Z’  m_{2}  X+Y’+Z  M_{2} 
0  1  1  X’. Y. Z  m_{3}  X+Y’+Z’  M_{3} 
1  0  0  X. Y’. Z’  m_{4}  X’+X+Z  M_{4} 
1  0  1  X. Y’. Z  m_{5}  X’+Y+Z’  M_{5} 
1  1  0  X. Y. Z’  m_{6}  X’+Y’+Z  M_{6} 
1  1  1  X. Y. Z  m_{7}  X’+Y’+Z’  M_{7} 
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 sumof –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:
F_{1} = X’.Y.Z + X.Y’.Z’ + X.Y.Z
F_{1} = m_{3}+m_{4}+m_{7}
Similarly, F_{2} = X’.Y.Z + X.Y’.Z + X.Y.Z’ + X.Y.Z can be easily expressed in its sum of product form:
F_{2} = X’.Y.Z + X.Y’.Z + X.Y.Z’ + X.Y.Z
F_{2} = m_{3}+m_{5}+m_{6}+m_{7}
X  Y  Z  F_{1}  F_{2} 
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 F_{1} and F_{2}. 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 = m_{0}+m_{2}+m_{3
}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 = M_{0}.M_{2}.M_{3}.M_{5}.M_{6}
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 = M_{0}.M_{2}.M_{4}.M_{5
}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.