what is boolean expression with example | boolean algebra simplification examples and solutions

By   July 15, 2020

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

  1. Algebric simplification.
  2. Karnaugh map method.
  3. 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) = m 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

  1. these are vertically above each other or are in the top and bottom cells of a column.
  2. 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 ;

  1. in terms of minterms and don’t care conditions

Y (A, B, C, D) = m (0, 1, 2, 4, 8, 10) + d (5, 7)

  1. 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

  1. list all the given minterms in their binary equivalent
  2. arrange the minterms according to the number of 1’s
  3. 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.
  4. repenat step 3 for the resultant column and continue these cycles until no further elimination of variables takes place.
  5. list the primary implicants.
  6. 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)

  1. 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

  1. 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

  1. Compare each binary number with every term in the abjacent next higher category and if they differ by one position put a check mark.
  2. 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-

  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

  1. convert all AND gate to NAND gates with AND invert graphic symbols.
  2. convert all OR gates to NAND gates with invert OR graphic symbol.
  3. 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.

  1. draw logic diagram using AND-OR gate for the given boolean function.
  2. replace AND gate by invert AND gate and OR gate is replaced by NOR gate.
  3. 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

  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

  1. Given (125)g = (203)5. the value of radix R will be

(a) 16

(b) 10

(c) 8

(d) 6

  1. 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

  1. Consider the boolean expression

Z = ABCD + ABCD + ABCD.

The simplified form of Z is

(a) C + D

(b) BC

(c) CD

(d) BC

  1. 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

  1. A + B 1. 00100100
  2. A – B 2. 01001001
  3. B – A 3. 11001001
  4. -A – B 4. 00100011
  5. 11011011
  6. 10110110
  7. 00100100
  8. 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

  1. 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

  1. A + B                                                      1. 10100101
  2. A – B                                                       2. 00000010
  3. B – A 3. 01011011
  4. -A – B 4. 10100101
  5. 11111111
  6. 00000001
  7. 11110101
  8. 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

  1. In the network of figure, y can be written as

(a) X0X1X3X5 + X2X4X5 ……..Xn1 + ………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

  1. 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

  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

  1. 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

  1. 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

  1. 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

  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

  1. 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

  1. The number of distinct boolean expression of 4 variable is

(a) 16

(b) 256

(c) 1024

(d) 65536

  1. 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

  1. The point p in the following figure is stuck at 1. the output will be

(a) ABC

(b) A

(c) ABC

(d) A

  1. 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

  1. (d) 2’s complement number MSB is 1 so, its equivalent decimal number

= – (2’s complement of 11011)

= – (0010) = – 5

  1. (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.

  1. (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.

  1. (a) Given boolean expression

Z = ABCD + ABCD + ACBD

Z = ACD + BCD

  1. (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)

  1. (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)

  1. (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

  1. (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

  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

  1. (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.

  1. (a) X – NOR logic is called coinidence logic.
  2. (b)
  3. (d)
  4. (a) f = ABC + ABC = B(AC + AC)

= B (A + C) (A + C)

SOP of XOR = POS of NOR

  1. (d) Given BCD code
  2. (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

  1. (d) Number of boolean expression = 22n

for n = 4

Number of boolean expression = 224 = 216 = 65536

  1. (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

  1. (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.
  2. (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

  1. Half adder
  2. Full adder

Classification of subtractor

  1. Half subtractor
  2. 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:

  1. Add two, 4 bit BCD number using straight binary addition.
  2. If 4 bit sum is equal to or less than 9, the sum is a valid BCD number and no correction is needed.
  3. 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..

Leave a Reply

Your email address will not be published. Required fields are marked *