Boolean Algebra, Logic Gates and Minimization Techniques: Two Marks Important Questions and Answers

Digital Principles and Computer Organization:

Chapter 2: Boolean Algebra, Logic Gates and Minimization Techniques

Two Marks Questions with Answers

 

1. What do you mean by literal ?

 Answer:

Definition: In Boolean function, the total number of variables in complemented or uncomplemented form are called literals.

For example : The function F (A, B, C, D) =  contains 4 literals.

2. Distinguish between Boolean addition and binary addition.

 Answer: Boolean addition refers the logical ORing between two literals. On the other hand, in binary addition the two binary bits are added mathematically.

Boolean addition       Binary addition

0 + 0 → 0                    0 + 0 → 0

0 + 1 →1                     0 + 1→ 1

1 + 0 → 1                    1 + 0 →1

1 + 1 → 1                    1 + 1 = 10

3. What are basic properties of Boolean algebra ?

 Answer: The basic properties of Boolean algebra are commutative property, associative property and distributive property.

4. State the associative law of Boolean algebra.

 Answer:  Associative laws are as follows :

1. Law 1 (The associative law of addition) : In the Oring of several variables, the result is the same regardless of the grouping of the variables. For three variables, A ORed with B OR C is the same as A OR B ORed with C.

i.e.     A + (B + C) = (A + B) + C

2. Law 2 (The associative law of multiplication) : It makes no difference in what order the variables are grouped when ANDing several variables. For three variables, A AND B ANDed with C is the same as A ANDed with B and C.

i.e. (AB) C = A(BC).

5. State the commutative property of Boolean algebra.

 Answer: The commutative property states that the order in which the variables are ORed makes no difference. The commutative property is :

A+B = B+A.

6. State the distributive property of Boolean algebra or state distributive law.

 Answer: The distributive property states that ANDing several variables and ORing the result with a single variable is equivalent to ORing the single variable with each of the several variables and then ANDing the sums. The distributive property is :

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

7. Explain the De Morgan's theorem in Boolean algebra.

DeMorgan suggested two theorems that form an important part of Boolean algebra. In the equation form, they are: 

1.

2.

1.  : The complement of a product is equal to the sum of the complements. This is illustrated by truth Table 2.2.1.

2. : The complement of a sum is equal to the product of the complements. The truth Table 2.2.2 illustrates this law.

8. State two absorption properties of Boolean algebra.

 Answer: 1. A+ AB = A and

2. A (A + B) = A

9. Explain the principle of duality with the help of example.

 Answer: The duality theorem says that, starting with a Boolean relation, you can derive another Boolean relation by –

1. Changing each OR sign to an AND sign

2. Changing each AND sign to an OR sign and

3. Complementing any 0 to 1 appearing in the expression.

For example : A+ 0 = A. Using duality theorem, we can say that, A.1 = A.

10. State and prove the consensus theorem in Boolean algebra.

 Answer: Definition : In simplification of Boolean expression, the redundant term in an expression can be eliminated to form the equivalent expression. The theorem used for this simplification is called consensus theorem. For example, in expression of the AB+ĀC+BC, the term BC is redundant and can be eliminated using consensus theorem.

Proof :

AB+ ĀC+BC = AB+ ĀC+ (A+Ā) BC = AB+ ĀC+ AB+ ĀC = AB+ ĀC

11. Define binary logic.

 Answer: Binary logic consists of binary variables and logical operations. The variables are designated by the alphabets such as A, B, C, x, y, z, etc., with each variable having only two distinct values: 1 and 0. There are three basic logic operations: AND, OR and NOT.

12. What is a logic gate ?

 Answer: The logic gate is an electronic circuit that has one or more input binary variables but only one output. It is called logic gate because of it ability to operate on a number of binary inputs to perform a logical function, i.e. its output is a logical function of inputs.

13. What are the basic digital logic gates?

 Answer: The three basic logic gates are

• AND gate

• OR gate

• NOT gate.

14. Which gate is equal to AND–inverter gate ?

 Answer: NAND gate.

15. Which gate is equal to OR–inverter gate?

 Answer: NOR gate.

16. Bubbled OR gate is equal to  –––––––––––––.

 Answer: NAND gate.

17. Bubbled AND gate is equal to –––––––––––––––.

 Answer: NOR gate.

18. Draw the logic symbol and construct the truth table of the following gates :

a) Three input OR gate b) Three input EX–NOR gate

 Answer: a) Three input OR gate :

b) Three input EX–NOR gate :

 [Hint : For even number of ones output is one]

19. Give the Boolean expression used for following gates

a) AND b) NOR c) EX–OR d) OR e) NOT

 Answer:

20. Sketch the waveform of each inverter output in the given diagram.

 Answer: 

21. Write the names of universal gates.

 Answer:

Universal gates are : NAND gate and NOR gate.

22. Why are NAND and NOR gates known as universal gates ?

 Answer: NAND and NOR are the gates that can be used alone to generate remaining gates such as NOT, AND and OR. Thus, with only any of the two gates, we can implement the logic circuit. Hence, they are called Universal gates.

23. Why digital circuits are more frequently constructed with NAND or NOR gates than with AND and OR gates ?

 Answer: Digital circuits are frequently constructed with NAND or NOR gates due to following reasons,

• If any simple combinational circuit we want to build and we are not using universal gates then we want several AND, OR and NOT gates. This demands number of ICs, one for each type of gate. For example, IC 7408 is for 2–input AND gate, IC 7432 is for 2–input OR gate. Hence, there is possibility that all gates in each IC are not used and IC utility factor will be poor.

• By using universal gates it is possible to reduce number of ICs required to implement combinational circuit.

24. Name the two basic types of Boolean expressions.

 Answer:

The two basic types of Boolean expressions are :

• Sum of Product form (SOP) and

• Product of Sum form (POS)

25. Name the two canonical forms for Boolean algebra.

 Answer: Sum of minterms and product of maxterms forms.

26. Define : minterm and maxterm.

Each individual term in canonical SOP form is called minterm and each individual term in canonical POS form is called maxterm. The concept of minterms and maxterms allows us to introduce a very convenient shorthand notations to express logical functions. Table 2.6.1 gives the minterms and maxterms for a three literal/variable logical function where the number of minterms as well as maxterms is 2³ = 8. In general, for an n–variable logical function there are 2ⁿ minterms and an equal number of maxterms.

27. Express F = BC' + AC in a canonical SOP form.

 Answer:

28. How many inputs are required for  ?

 Answer: 6 – inputs.

29. Simplify the following Boolean expressions to a minimum number of literals :

 Answer:

30. Simplify the following Boolean expression.

 Answer: 

31. Simplify: x + x'y.

 Answer:

32. Show that

a) x + x'y.

b) x'y' z + x' yz + xy' = x'z + xy'.

 Answer: 

a) 

33. Express the following switching circuit in binary logic notation.

 Answer:

34. What are the methods adopted to reduce Boolean function ?

 Answer:  i) Boolean function simplification using Boolean laws and theorems

ii) Karnaug map

iii) Tabular method or Quine Mc–Cluskey method

iv) Variable entered map technique.

35. What is variable mapping ?

 Answer: Representing the minterms of the sum of of product expression in the Karnaugh–map of appropriate variables is known as variable mapping.

36. What code is used to label the row headings and column heading of K–map and why ?

 Answer: • Gray code is used to label the rows and columns of K–map.

• In case of Gray code, only one variable changes between two consecutive number. This is useful in grouping pair, quad or octets in k–maps and thus eliminating variables in the final expression. Hence, Gray code is used to label the rows and columns of K–map.

37. What is a Karnaugh map ?

 Answer: A Karnaugh map or K–map is a pictorial form of truth table, in which the map diagram is made up of squares, with each squares representing one minterm of the function.

38. Show the Karnaugh map with the encircled groups for the Boolean function, .

 Answer:

39. What are don't care conditions and incompletely specified functions ?

 Answer: Sometimes, while designing a digital circuit, certain conditions of input are of no use. Consider an example of BCD input for a seven segment display. In this case, inputs from 0 through 9 are valid inputs. Thus, rest of the inputs from 10 through 15 do not signify anything at the output side. The outputs for which inputs are not specified are called don't care outputs. The Boolean function in which don't care outputs exists is called incomplete Boolean function or incompletely specified functions.

40. Distinguish between completely specified function and incompletely specified function.

 Answer:

Completely specified function

1. All input conditions occur.

2. Each output corresponding to input conditions is defined,

3. Each output has certain logical value, either 0 or 1.

4. In expression,

f(A, B, C) = Σ m (0, 1, 3,5, 6)

                 = π M (1, 4, 7)

Incompletely specified function

1. Certain input conditions never occur.

2. Outputs corresponding to non–occurring input conditions are undefined.

3. Undefined output doesn't have certain logical value, but it is indicated by 'x' or 'd' in truth tables.

4. In expression,

f(A, B, C) = Σ m(0, 1, 3) + d (5, 6)

                 = πM (2, 4, 7) + d (5, 6)

Here outputs corresponding to terms 5 and 6 are assumed to be undefined ('x' or 'd') called as 'don't care'.

41. What are prime implicants ?

 Answer:  All the implicants of a function determined using a Karnaugh map are called prime implicants.

42. What is an essential implicant?

After grouping the cells, the sum terms which appear in the K–map are called prime implicants groups. It is observed that some cells may appear in only one prime implicants group; while other cells may appear in more than one prime implicants group. In Fig. 2.9.4 (b), cells 1, 6, 11 and 12 appear in only one prime implicants group. These cells are called essential cells and corresponding prime implicants are called essential prime implicants.

43. State the limitations of Karnaugh map.

The map method of simplification is convenient as long as the number of variables does not exceed five or six. As the number of variables increases it is difficult to make judgements about which combinations form the minimum expression. In case of complex problem with 7, 8 or even 10 variables it is almost an impossible task to simplify expression by the mapping method. Another important point is that the K–map simplification is manual technique and simplification process is heavily depends on the human abilities. To meet this need, W. V. Quine and E. J. McCluskey developed an exact tabular method to simplify the Boolean expression. This method is called the Quine McCluskey or tabular method.

44. State two significant features of tabular method of minimization of Boolean functions.

 Answer: 1. It is an exact method to simplify the Boolean expression.

2. It can be used to simplify expression with 7, 8 or even 10 variables.

45. Why we go in for tabulation method?

 Answer: This method can be applied to problems with many variables and has the advantage of being suitable for machine computation.

46. Explain or list out the advantages and disadvantages of K–map method.

 Answer: The advantages of the K–map method are :

i. It is a fast method for simplifying expression up to four variables.

ii. It gives a visual method of logic simplification.

iii. Prime implicants and essential prime implicants are identified fast.

iv. Suitable for both SOP and POS forms of reduction.

v. It is more suitable for class room teachings on logic simplification.

For the disadvantages of the K–map method:

The map method of simplification is convenient as long as the number of variables does not exceed five or six. As the number of variables increases it is difficult to make judgements about which combinations form the minimum expression. In case of complex problem with 7, 8 or even 10 variables it is almost an impossible task to simplify expression by the mapping method. Another important point is that the K–map simplification is manual technique and simplification process is heavily depends on the human abilities. To meet this need, W. V. Quine and E. J. McCluskey developed an exact tabular method to simplify the Boolean expression. This method is called the Quine McCluskey or tabular method.

47. What theorem is used when two terms in adjacent squares of K–map are combined?

Once the Boolean function is plotted on the Karnaugh map we have to use grouping technique to simplify the Boolean function. The grouping is nothing but combining terms in adjacent cells. Two cells are said to be adjacent if they conform the single change rule. i.e. there is only one variable difference between co–ordinates of two cells.

48. What is meant by map method ?

 Answer: The map method provides a simple straightforward procedure for minimizing Boolean function.

49. What is meant by two variable map ?

 Answer: Two variable map have four minterms for two variables, hence the map consists of four squares, one for each minterm.

50. What is meant by three variable map?

 Answer: Three variable map have 8 minterms for three variables, hence the map consists of 8 squares, one for each minterm.

51. What is tabulation method ?

 Answer: A method involving an exhaustive tabular search method for the minimum expression to solve a Boolean equation is called a tabulation method.

52. Implement EX–OR gate using only NAND gate.

The Boolean expression for EX–OR gate is : A+B. We can implement AND–OR logic by using NAND–NAND logic as shown in Fig. 2.13.6 (b).

Another way of implementing EX–OR gate using NAND gates is as shown in Fig. 2.13.6 (b). It needs only four NAND gates.

 53. How can a NAND gate be used as an inverter ?

 Answer:

54. Realize the function  by using only NAND gates.

55. How will you use a 4 input NAND gate as a 2 input NAND gate ?

 Answer:

56. Implement AND gate and OR gate using NAND gate.

AND function :

An AND function can be generated using only NAND gates. It is generated by simply inverting output of NAND gate i.e.  = AB. Fig. 2.5.2 shows the two input AND gate using NAND gates.

OR function :

OR function is generated using only NAND gates as follows: We know that Boolean expression for OR gate is

Y = A + B

The above equation is implemented using only NAND gates as shown in Fig. 2.5.3.

Note : Bubble at the input of NAND gate indicates inverted input.

 57. Show that the NAND connection is not associative.

 Answer:

NAND connection is not associative.

58. Show that a bubbled AND gate works like a NOR gate.

 Answer:

Here, output Y presents the output of NOR gate.

59. How will you use a 4 input NOR gate as a 2 input NOR gate ?

 Answer:

60. What is an Integrated Circuit (IC) ?

 Answer: An Integrated Circuit (IC) is a tiny electronic circuit in which many components like transistors, resistors and capacitors are fabricated on a small silicon chip. It integrates complete circuits on a single wafer using processes like photolithography, enabling compact size and high performance.

61. What are the main types of integrated circuits based on function ?

 Answer: ICs are classified into :

• Digital ICs – Work on binary logic (0 and 1), e.g., microprocessors, memory chips.

• Analog ICs – Process continuous signals, e.g., amplifiers and sensors.

• Mixed–signal ICs – Combine analog and digital circuits on one chip, e.g., used in smartphones.

62. What are SSI, MSI, LSI, VLSI, and ULSI ?

 Answer:

These are classifications of ICs based on the number of components on a chip :

 • SSI : 1 – 100 components

• MSI : 100 – 1,000 components

• LSI : 1,000 – 10,000 components

• VLSI : 10,000 – 1,000,000 components

• ULSI : Above 1 million components.

63. State any two advantages of integrated circuits.

 Answer:

• Miniaturization : Devices become smaller and portable.

• High performance : Short distances between components increase speed.

64. What is Moore's law ?

 Answer: Moore's Law states that the number of transistors on an IC doubles approximately every two years, leading to continuous improvement in performance and reduction in size.