boolean algebra simplification examples and solutions , what is boolean expression with example.
Simplification of Boolean Expression
To reduce the requirement of hardware, it is necessary to simplify the boolean expression. boolean expression can be simplifed using
- Algebric simplification.
- Karnaugh map method.
- Quine-MC Cluskey method.
Algebric Method
In algebric method, booleam theorems are used to simplify the expression.
For example
Y (A, B, D) = (A + B) (A + B + D) D
= (A + B) (AD + BD + DD)
= (A + B) (AD + BD) [DD = 0]
= (AAD + ABD + BAD + BBD)
= ABD + ABD + BD [AA = 0 and BB = B]
= ABD + (1 + A) BD [1 + A = 1]
= ABD + BD
= BD (1 + A) 1 + A = 1
= BD
Karnaugh Map Simplification
K-map is a graphical technique to simplify boolean expression. it provides a systematic method for simpliiying and manipulating boolean expressions.
cells, for-variable maps contains 16 cells and n-variable map contains 2n cells.
Representation of K-map
The logic function can be represented by input and output conditions or boolean functions. each cell of K-map is assigned a cell number; the cell number is calculated from columns and rows.
Representation of Truth Table on K-map
The truth table defines, how the inputs and outputs are related. the representation of truth table in k-map marks the output state of a digital system in cells of k-map corresponding to input conditions.
For example The truth table of three variable digital systems is given as
Its k-map reresentation is shown below.
Representation of SOP on k-map
Boolean expression in SOP may or may not be in a standard form. firstly the expression is converted into standard SOP and then 1’s are marked in each cell corresponding to the minterm and remaining cells are filled with 0’s.
For example Let us take a boolean expression
Y (A, B, C) = AB + BC + ABC
The standard SOP form will be
Y (A, B, C) = AB (C + C) + (A + A) BC + ABC
Y (A, B, C) = ABC )+ ABC + ABC + ABC
AB (111) = m7 ABC (110) = m6
ABC (010) = m2 ABC (001) = 1
The boolean can also be represented as
Y (A, B, C) = m (1, 2, 6, 7).
Representation of POS on K-map
Firstly converted POS form into standard POS form and then 0’s are entered in each cell corresponding to the maxterms of expression and then remaining cells are filled with 1’s.
For example Let us take a boolean expression
Y (A, B, C) = (A + B) (B + C) (A + B + C)
= (A + B + CC) (AA + B + C) (A + BC)
Y (A, B, C) = (A + B + C) (A + B + C)
(A + B + C) (A + B + C) (A + B + C)
A + B + C (000) = me A + B + C (010) = m2
A + B + C (001) = m1 A + B + C = (110) = m6
The boolean expression can be writen as
Y (A, B, C) = m (0, 1 , 2, 6)
The k-map representation of the above expression is shown.
Grouping the Adjacent cell
Two cells are said to be adjacent if
- these are vertically above each other or are in the top and bottom cells of a column.
- these are horizontally side by side or in the left and right most cells of a row.
In combining adjacent cells these differ in one variable only because of the use of gray code.
Types of Combination for Simplification
The following terms can be defined with respect to K-map simplification :
pair Group of two adjacent minterms A pair eliminates one variable in output expression.
For example let Y = ABCD + ABCD. Its k-map representation is
After solving with the help of k-map we get
Y = BCD
Quad
Group of four adjacent minterms. a quad eliminates two variables in output expression it can appear in various ways as shown below.
Octer Group of eight adjacent minterms. an octet eliminates three variables in output expression. it can appear in the given ways
Redundant Group A redundant group is a group in which all the elements in this group are covered by some other groups.
Consider the example shown, here m5m7m13m15 form a quad (G1). However all elements of this group are covered by the adjacent groups. hence G1 becomes a redundant group and
Example 13. simplify the boolean function
F (w, x, y, z) = [0, 1, 2 , 4, 5, , 6, 8, 9, 12, 13, 14]
Sol. the k-map representation is shown in figure.
Don’t Care Condition
In some logic circuits, certain input conditions never occur therefore the corresponding output never appears. the outputs coresponding to these inputs are indicated by ‘x’ [cross] and called as don’t care condition.
The boolean function can be specified in one of the following ways ;
- in terms of minterms and don’t care conditions
Y (A, B, C, D) = m (0, 1, 2, 4, 8, 10) + d (5, 7)
- In terms of maxterms and don’t care conditions
Y (A, B, C, D) = IIM (0, 4, 5, 14, 15). d (1, 2, 7)
Example 14. Simplify the following boolean expression.
F (A, B, C, D) = (1, 3, 7, 11, 15)
which has the don’t care conditions
d (A, B, C,D) = (0, 2, 5)
Sol. k-map representation of the given function is shown
Example 15. Y = IIM (4, 5, 6, 7, 8, 12) + d (1, 2, 3, 9, 11, 14)
Sol. The k-map representation of given function is
Quine-MC Cluskey Method
As number of variables becomes more than six, it becomes difficult to form the group and simplify the boolean expression. for reducing this problem another method is used for simplifying the boolean expression. this method is known as Quine-MC cluskey method. it is also known as tabular method.
The steps used to simplify the boolean function using Quine-MC cluskey method are
- list all the given minterms in their binary equivalent
- arrange the minterms according to the number of 1’s
- compare each binary number with every term in the adjacent next higher category. if they differ by one position put a check mark and write in the next column.
- repenat step 3 for the resultant column and continue these cycles until no further elimination of variables takes place.
- list the primary implicants.
- selsct the minimum number of primes that must cover all the minterms.
For example consider the example :
Y = m (0, 2, 3, 6, 7, 8, 10, 12, 13)
- the given minterms in binary equivalent are
0-0000 2-0010 3-0011 6-0110 10-1010
7-0111 8-1000 12-1100 13-1101
Minterms Binary representation
m0 0000
m2 0010
m3 0011
m6 0110
m7 0111
m8 1000
m10 1010
m12 1100
m13 1101
- Arrangement of minterms according to number of 1’s
Minterms Binary
m0 0000
m2 0010
m8 1000
m3 0011
m6 0110
m10 1010
m12 1100
m7 0111
m13 1101
- Compare each binary number with every term in the abjacent next higher category and if they differ by one position put a check mark.
- list the prime implicants the group of minterms in the above table without check marks are known as prime implicants and is given by
prime implicants Binary representation
8, 12 1-00
12, 13 110-
0, 2, 8, 10 -0-0
2, 3, 6, 7 0-1-
- Select the minimum number of primes that must cover all the minterms. the prime implicants selsction chart is shown below.
prime implicants m0 m2 m3 m6 m7 m8 m10 m12 m13
8, 12 . .
12, 13 . .
0, 2, 8, 10 . . . .
2, 3, 6, 7 . . . .
it is clear from selection chart that it is sufficient to select the prime implicants (2, 3, 6, 7) and (0, 2, 8, 10) and (12, 13)
it is not necessary to select the prime implicants (8, 12) because 8 is present in (0, 2, 8, 10) and 12 is present in (12, 13) and hence,
Y (A, B, C, D) = (110-) + (-0-0) + (0-1-)
Y (A, B, C, D) = ABC + BD +AC
Multilevel NAND Circuits
The general procedure for converting a multilevel AND-OR diagram into an all NAND diagram using mixed notation is as follows
- convert all AND gate to NAND gates with AND invert graphic symbols.
- convert all OR gates to NAND gates with invert OR graphic symbol.
- check all the bubbles in the diagram for every bubble that is not compensayed by another small circle along the same line insert an inverter (a one input NAND gate) or complement the input lateral.
For example C osider the multilevel boolean function
F = (AB’ + A’B) (C + D)
Step 1. Draw logic diagram using AND, OR and NOT gates.
Step 2. AND gates are replaced by NAND gate and OR gates are replaced by invert OR gates.
step 3. Replacing
NOR Implementation
The NOR opertion is the dual of the NAND operation. therefore, all the procedures and rules for NOR logic are the duals of the corresponding procedures and rules the duals of the corresponding procedures and rules developed for NAND logic. the following steps are followed to implement multilevel NOR implementation.
- draw logic diagram using AND-OR gate for the given boolean function.
- replace AND gate by invert AND gate and OR gate is replaced by NOR gate.
- check all bubbles in the diagram. for every bubble that is not compensated by another bubble along the same line insert an inverter equivalent NOR gate.the invert AND gate is replaced by NOR gate.
For example Consider the multilevel boolean function.
F = A (BC + D) + AB
Step 1. Draw logic diagram using AND, OR and NOT only.
Step 2. OR gates are replaced by NOR gate and AND gate is replaced by invert AND gate.
Example 16. If the x and y iogic inputs are available and their complements x and y are not available, then what will be the minimum number of two input NAND required to implement x y
Sol. F = XY + XY
So, minimum four NAND gates are required to implement XOR gate.
Intro Exercise – 1
- A number expressed in binary 2’s complement as 11011. it’s decimal equivalent value is
(a) 4
(b) 5
(c) -4
(d) -5
- Given (125)g = (203)5. the value of radix R will be
(a) 16
(b) 10
(c) 8
(d) 6
- The minimum number of NOR gates requied to implement A (A + B) (A + B + C) is equal to
(a) 0
(b) 3
(c) 4
(d) 7
- Consider the boolean expression
Z = ABCD + ABCD + ABCD.
The simplified form of Z is
(a) C + D
(b) BC
(c) CD
(d) BC
- Consider the following signed binary number A = 01101101 and B = 10110110, where B is the 1’s complement and MSB is the sign bit. in list l operation is given and in list ll resultant binary number is given and find the correct answer using the codes given below the lists,
List l List ll
- A + B 1. 00100100
- A – B 2. 01001001
- B – A 3. 11001001
- -A – B 4. 00100011
- 11011011
- 10110110
- 00100100
- 01001000
Codes
P Q R S
(a) 3 6 8 7
(b) 1 6 2 5
(c) 3 4 2 5
(d) 1 4 8 7
- Consider the signed binary number A = 00101110 and B = 1101001 1, where B is in 2’s complement and MSB is the sibn bit. in list l, operation is given and in list ll, resultant binary number is given and find the correct answer using the codes given below the lists.
List l List ll
- A + B 1. 10100101
- A – B 2. 00000010
- B – A 3. 01011011
- -A – B 4. 10100101
- 11111111
- 00000001
- 11110101
- 11011011
Codes
P Q R S
(a) 5 7 4 2
(b) 5 3 4 2
(c) 6 3 4 5
(d) 6 7 1 5
- In the network of figure, y can be written as
(a) X0X1X3X5 + X2X4X5 ……..Xn – 1 + ………Xn -1xn
(b) X0X1X3X5 + X2X3X4…….Xn + ……Xn – 1 Xn
(c) X0X1X3X5 + Xn – 1 + X2X3X5 …….X0 + Xn – 1 Xn – 2 + Xn
(d) X0X1X3X5……..Xn + X2X3X5……..Xn + ……+ Xn – 1 Xn
- In the figure shown the imput condition, needed to peoduce X = 1, is
(a) A = 1, B = 1, C = 1
(B) A = 1, B = 1, C = 0
(c) A = 1, B = 0, C = 0
(d) A = 0, B = 1, C = 1
- What is dual of A + [b + (AC) + D?
(a) A + [B(A + C)] + D
(b) A [B + AC] + D
(c) A+ [B(A + C)] D
(d) A. [B(A + C)] D
- Consider the following gate nehwork
Which one of the following gates is redundant?
(a) gate no. 1
(b) gate no. 2
(c) gate no. 3
(d) gate no. 4
- A boolean function f of two variables x and y is defined as follows
f(0 , 0) = f(0 , 1) = f(1 , 1) = f(1 ,0) = 0
Assuming componenents of x and y are not available a minimum cost solution for realizing f using only two input NOR gates and 2 input OR gates (each having unit cost) would have a total cost of
(a) 1 unit
(b) 4 unit
(c) 3 unit
(d) 2 unit
- The boolean expression for the truth table shown is
(a) B (A + C) (A + C)
(b) B (A + C) (A + C)
(c) B (A + C) (A + C)
(d) B (A + C) (A + C)
A B C D
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
- A new binary coded pentary (BCP) number system is proposed in which every digit of a base-5 number is represented by its corresponding 3 bit binary code. for example, the base-5 number 24 will be represented by its BCP code 010100. in this numbering system the BCP code 100010011001 conrresponds to the following number in base-5 system.
(a) 423
(b) 1324
(c) 2201
(d) 4231
- With 2’s complement representation, the range of values that can be represented on the data bus of an 8 bit micrprocessor is given by
(a) – 128 to + 127
(b) – 128 to + 128
(c) – 127 to + 128
(d) – 256 to + 256
- The number of distinct boolean expression of 4 variable is
(a) 16
(b) 256
(c) 1024
(d) 65536
- The range of signed decimal number that can be represented by 6 bit 1’s complement number is
(a) – 64 to + 63
(b) – 32 to + 31
(c) – 63 to + 64
(d) – 31 to + 31
- The point p in the following figure is stuck at 1. the output will be
(a) ABC
(b) A
(c) ABC
(d) A
- The simplified boolean expression from the karnaugh map given in the figure is
(a) AC + AD + AB
(b) AC + AD + ABC
(c) AB + CD + AD
(d) AC + ACD + ABC + BCD
Answers with Solutions
- (d) 2’s complement number MSB is 1 so, its equivalent decimal number
= – (2’s complement of 11011)
= – (0010) = – 5
- (d) (125)R = (203)5
1 x R2 + 2 x R1 + 5 x R0 = 2 x (5)2 + 0 x (5)1 + 3 x (5)0
R2 + 2R + 5 = 50 + 3
R2 + 2R – 48 = 0
R = 6, – 8
So, the value of radix R is 6.
- (a) Given function
F = A (A + B) (A + B + C)
Simplify this
F = (A + AB) (A + B + C)
= (A + AB + AC + AB + AB + ABC)
= A + AB + AC + ABC
= A + AB + AC (1 + B)
= A (1 + B) + AC [ (1 + B) = 1]
= A + AC
= A (1 + C) [ (1 + C) = 1]
= A
So, there is no NOR gate is required to implement the above boolean function.
- (a) Given boolean expression
Z = ABCD + ABCD + ACBD
Z = ACD + BCD
- (b) A = 01101101 and B = 10110110
(i) A + B
01101101 A
+ 10110110 B
100100011
00100100
(ii) A – B = A + B
01101101 A
+ 01001001 B (1’s complement of B)
10110110
(iii) B – A = A + B
10010010 A (1’s complement of A)
10110110 B
101001000
1
01001001
(iv) – A – B = A + B
10010010 A (1’s complement of A)
+ 01001001 B (1’s complement of B)
- (c) A = 00101110 and B = 11010011
(i) A + B
00101110 A
11010011 B
1 00000001
Discard carry
A + B = 00000001
(ii) A – B = A + B
00101110 A
00101101 B (2’s complement of B)
01011011
(iii) B – A = A + B
11010010 A (2’s complement of A)
11010011
1 10100101
Discard carry
(iv) – A – B = A + B
11010010 A (2’s complement of A)
00101101 B (2’S complement of B)
- (d) Output of gate 1 is X0X1
Output of gate 2 is X0X1+X2
Output of gate 3 is (X0X1+X2) X3 = X0X1X3 + X2X3
output of gate 4 is X0X1X3 + X2X3 + X4
output of is 5 is X0X1X3X5 + X2X3X5 + X4X5
So, output of gate n would be
X0X1X3X5…..Xn + X2X3X5 …… Xn + X4X5X7.………. Xn + Xn – 1Xn
- (d) Output of the circuit
X = (A . B) . (B . C) . C
For X = 1 C = 1
B . C = 1 for this B = 1 C = 1
and A . B = 1 for this A = 0, B = 1
Thus, for X =1
A = 0, B = 1, C = 1
- (d) Given funetion = A + [ B + AC] + D
Dual can be obtained by replacing
AND – OR and OR – AND
So, dual of function = A . [B. (A + C)] D
- (b) Output of the given gate network can be written as
F = W + WZ + Z x y
w (1 + Z) + Z x y
= w + Z x y
so, gate 2 is redundant.
- (a) X – NOR logic is called coinidence logic.
- (b)
- (d)
- (a) f = ABC + ABC = B(AC + AC)
= B (A + C) (A + C)
SOP of XOR = POS of NOR
- (d) Given BCD code
- (a) For an n-bit number the maximum negative number which can be represented in 2’s complement form is -2n-1 and maximum positive number 2n-1 – 1. so, the range of 2’s complement representation
– 2n-1to 2n-1 – 1
For n = 8 bit, range will be
= – 2n-1to 28-1 – 1 =- 128 to 127
- (d) Number of boolean expression = 22n
for n = 4
Number of boolean expression = 224 = 216 = 65536
- (d) The maximum positive number that can be represented by 1’s complement number is +2n-1 – 1 and maximum negative number is – (2n-1 -1) so, range
+26-1 – 1 to – (26-1 – 1)
+ 31 to – 31
- (d) The point p in stuck 1 means the input of gate 5 is high, the output of gate 5 will be low, this low output make the output of gate 7 high. because of high and A input of gate 8, it will pass A which becomes A after passing gate 9. so the output will be A.
- (b) Y = AC + AD + ABC
Combinational logic Circuit
Combinational logic Circuit A combinational logic circuit consists of logic gates whose outputs at any time are determined from only the present combination of inputs.
Arithmetic Circuits
Arithmetic circuits are used to perform addition and subtraction. binary adder performs binary addition. adders and subtractors are classified into two categories.
Classification of adder
- Half adder
- Full adder
Classification of subtractor
- Half subtractor
- Full subtractor
Half Adder
It is used to perform the addition of single bit. half adder contains two input lines for input data and two output lines for sum output and carry output.
Logic Diagram
We obtain the logic circuits as shown for the sum and carry expression
sum (s) = AB + AB = A .B
Carry (c) = AB
Full Adder
A full adder is a combinational logic circuit that performs the arithmetic sum of three input bits. it consists of three inputs and two outputs.
Truth Table
Form the truth table
S = ABC i + ABC + ABC + ABC = A . B . C
CO = AB + BC + AC
Logic Diagram
Implementation of full adder in sum of produrcts form
It can also be implemented with two half adders and one OR gate as shown below :
Half Subtractor
A half subtractor is a combinational logic circuit that subtracts two bit and produces their differebce and borrow.
Difference (D) = AB + AB
Borrow (B) = AB
Logic Diagram
Full subtractor
A full subtractor is a combinational logic circuit that performs subtraction involving three bit namely minuend bit, subtrahens bit and borrow from the previous stage.
Binary Adder
A binary adder is digital circuit that produces the sum of two binary numbers. it can be condtructed with full adders connected in cascade with output carry from each full adder connected to the input carry of next full adder in chain. As n bit adder requires n full adders.
For example 4 bit adder can be mabe by using four full adder in cascade form.
The bits are adder with full adders, starting from the least significant position (subscript 0) to form the sum bit and carry bit.
Binary Subtractor
The subtractor of unsigned binary numbers can be done most conveniently by means of complements.
Decimal Adder
A decimal adder requires a minimum of nine inputs and five outputs. a variety of decimal adders are possible based on the code used to represent the decimal digits.
The addition and subtraction operations can combined into one circuit with one common binary adder by includig an XOR gate with each full adder. to achieve this a control input M is used . the resulting expressions are
xi = A
YI = BI . M
and CI = M
These expressions are implemented to obtain an order-subtractor circuit.
BCD Adder
A BCD adder is a circuit that adds two BCD digits in parallel and produces a sum digit which is also BCD.
BCD number uses 10 symbols (0000 to 1001). a BCD adder circuit must be able to do the following:
- Add two, 4 bit BCD number using straight binary addition.
- If 4 bit sum is equal to or less than 9, the sum is a valid BCD number and no correction is needed.
- If the 4 bit sum is greater than 9 or if carry is generated from the sum the sum of invalid BCD number. then the digit 6 (0110) should be added to the sum to produce the valid BCD symbols.
From the truth table
F = S3S2 + S3S1
Logic diagram of BCD Adder
Code Converter
A code converter is a circuit which accepts the input information in one binary code, converts it and produces an output in another binary code..