## Introduction

Minimization is the process of simplifying a boolean function's algebraic form. Minimization is significant since it minimises the associated circuit's cost and complexity.

**Question 1: Which one of the following expressions does NOT represent the exclusive NOR of x and y?**

GATE CS 2013

- xy+x'y'
- x⊕y'
- x'⊕y
- x'⊕y'

**Solution**: (D) x'⊕y'

**Explanation**

x'⊕y' = x''y' + x'y'' = xy' + x'y = x⊕y ≠ x⊙y

Therefore option (D) is false.

**Question 2: What is the minimum number of gates required to implement the Boolean function (AB+C)if we have to use only 2-input NOR gates?**

GATE CS 2009

- 2
- 3
- 4
- 5

**Solution**: (B) 3

**Explanation**

(A+C)(B+C) = ((A+C) + (B+C))'=AB + C.

As a result, '3' 2-input NOR gates are needed.

**Question 3: If P, Q, R are Boolean variables, then (P + Q’)(PQ’ + PR)(P’R’ + Q’) simplifies**

- PQ’
- PR’
- PQ’ + R
- PR’’ + Q

**Solution**: (A) PQ’

**Explanation**

Step by step explanation :

= (P + Q’)(PQ’ + PR)(P’R’ + Q’)

= (PPQ’ + PPR + PQ’Q’ + PQ’R) (P’R’ + Q’)

= (PQ’ + PR + PQ’ + PQ’R) (P’R’ + Q’)

= (PP’Q’R’ + PP’R’R + PP’Q’R’ + PP’Q’RR’ + PQ’Q’ + PQ’R + PQ’Q’ + PQ’Q’R)

= (0 + 0 + 0 + 0 + PQ’ + PQ’R + PQ’ + PQ’R)

= PQ’ + PQ’R

= PQ'(1 + R)

= PQ’

**Question 4: Consider the following Boolean expression for F:**

**F(P, Q, R, S) = PQ + P'QR + P'QR'S**

**The minimal sum-of-products form of F is**

GATE CS 2014

- PQ + QR + QS
- P + Q + R + S
- P’ + Q’ + R’ + S’
- P’R + P’R’S + p

**Solution**: (A) PQ + QR + QS

**Explanation**

Given,

F(P, Q, R, S) = PQ + P'QR + P'QR'S

= Q(P + P'R + P'R'S)

= Q(P + R + R'S)

= Q(P + R + S)

= PQ + QR + QS

Note that A + AB = A and A + A'B = A + B. So, option (A) is correct.

**Question 5: Let X denote the Exclusive OR (XOR) operation. Let ‘1’ and ‘0’ denote the binary constants. Consider the following Boolean expression for F over two variables P and Q:**

**F(P, Q) = ( ( 1 X P) X (P X Q) ) X ( (P X Q) X (Q X 0) )**

**The equivalent expression for F is:**

- P + Q
- (P+Q)’
- (P X Q)
- (P X Q)’

**Solution**: (D) (P X Q)’

**Explanation**

We need to simplify the above expression. As the given operation is XOR, we shall see the property of XOR. Let A and B be boolean variables. In A XOR B, the result is 1 if both the bits/inputs are different, else 0. Now,

( ( 1 X P) X (P X Q) ) X ( (P X Q) X (Q X 0) )

( P' X P X Q ) X ( P X Q X Q ) ( as 1 X P = P' and Q X 0 = Q )

(1 X Q) X ( P X 0) ( as P' X P = 1 , and Q X Q = 0 )

Q' X P ( as 1 X Q = Q' and P X 0 = P )

PQ + P'Q' ( XOR Expansion, A X B = AB' + A'B )

This is the final simplified expression.

Now we need to check for the options.

If we simplify option D expression.

( P X Q )' = ( PQ' + P'Q )' ( XOR Expansion, A X B = AB' + A'B )

((PQ')'.(P'Q)') ( De Morgan's law )

( P'+ Q).(P + Q') ( De Morgan's law )

P'P + PQ + P'Q' + QQ'

PQ + P'Q' ( as PP' = 0 and QQ' = 0 )

Hence both the equations are the same. Therefore Option D.

**Question 6: The Boolean function x'y' + xy + x'y is equivalent to**

GATE CS 2004

- x’ + y’
- x + y
- x + y’
- x’ + y

**Solution**: (D) x’ + y

**Explanation**

x’y’+xy+xy’ =(x’y’+y(x+x’)) = x'y’+y =x'+y

Answer is (D)

**Question 7: Which are the essential prime implicants of the following Boolean function? **

**f(a, b, c) = a'c + ac' + b'c**

GATE CS 2004

- a’c and ac’
- a’c and b’c
- a’c only
- ac’ and bc’

**Solution**: (A) a’c and ac’

**Explanation**

Essential prime implicants are prime implicants that cover an output of the function that no combination of other prime implicants is able to cover i.e., if we delete such elements then the property of group, quad, octet is destroyed. By drawing k map and by putting c on the left side and a, b on the right side we can find that a'c and ac' are essential prime implicants.

**Question 8: Let f(A, B) = A' + B. Simplified expression for function f(f(x + y, y)z) is :**

GATE CS 2002

- x’ + z
- xyz
- xy’ + z
- None of above

**Solution**: (C ) xy’ + z

**Explanation**

Simplified expression for given function 'g' is :

g = f( f(x + y, y), z) g = f( ((x + y)’ + y), z) g = f( (x’y’ + y), z) g = f( ((y + y’) * (x’ + y)), z) g = f( (1 * (x’ + y)), z) g = f( (x’ + y), z) g = (x’ + y)’ + z) g = xy’ + z

Thus, option (C) is correct.

**Question 9: Consider the following given operations **

**f(X, Y, Z) = X'YZ + XY' + Y'Z' & g(X, Y, Z) = X′YZ + X′YZ′ + XY. **

**Which of the following is correct?**

GATE CS 2015

- Both {f} and {g} are functionally complete
- Only {f} is functionally complete
- Only {g} is functionally complete
- Neither {f} nor {g} is functionally complete

**Solution**: (B) Only {f} is functionally complete

**Explanation**

If a function does not belong to T0,T1,L,M,S, it is deemed functionally complete. Property 1: We say that a boolean function f preserves zero if it yields 0 on the 0-input. We refer to a 0-input as one in which all of the input variables are zero (this input usually corresponds to the first row of the truth table). T0 stands for zero-preserving boolean functions, and f T0 stands for f T0. Property 2: In the same way that T0 preserves one, we say that boolean function f preserves one if it generates 1 on a single input. The 1-input is an input in which all of the input variables are equal to one (this input usually corresponds to the last row of the truth table). T1 denotes the class of one-preserving boolean functions, and f T1 denotes one-preserving boolean functions. Property 3: A boolean function f is said to be linear if one of the following two propositions is true about it:

- The number of 1s in the corresponding input is odd for every 1-value of f, while the number of 1s in the corresponding input is even for every 0-value of f.
- The number of 1s in the corresponding input is even for every 1-value of f, while the number of 1s in the corresponding input is odd for every 0-value of f.

We say f is linear1 if one of these propositions holds for it. The class of linear boolean functions is denoted by the letter L, and we write f L. Property 4: A boolean function is said to be monotone if moving any input variable from 0 to 1 can only result in the function's value changing from 0 to 1, and never from 1 to 0. We write f M to represent the class of monotone boolean functions. Property 5: A boolean function f(x1,...,xn) is said to be self-dual if it equals f(x1,...,xn). The dual of f is the function on the right in the equality above (the one containing negations). The class of self-dual boolean functions will be referred to as S, and the function f S will be written. As we can see in our example, setting all i/p to 0 (g)produces 0 and hence cannot be functionally complete. However, neither 0 nor 1 are preserved by f.

- F is not a linear function (see defn. of linear above)
- F isn't one-dimensional (see defn. of monotone above)
- f(x,y,z) is not equivalent to –f, hence F is not self dual (-x,-y,-z)

As a result, f is fully functioning. As a result, the answer is (B) portion.

**Question 10: The number of min-terms after minimising the following Boolean expression is _________.**

** [D′ + AB′ + A′C + AC′D + A′C′D]′**

GATE CS 2015

- 1
- 2
- 3
- 4

**Solution**: (A) 1

**Explanation**

Given Boolean expression is:

[D′ + AB′ + A′C + AC′D + A′C′D]′

Step 1 : [D′ + AB′ + A′C + C′D ( A + A')]′

( taking C'D as common )

Step 2 : [D′ + AB′ + A′C + C′D]′

( as, A + A' = 1 )

: [D' + DC' + AB' + A'C]' (Rearrange)

Step 3 : [D' + C' + AB' + A'C]'

( Rule of Duality, A + A'B = A + B )

: [D' + C' + CA' + AB']' (Rearrange)

Step 4 : [D' + C' + A' + AB']'

(Rule of Duality)

: [D' + C' + A' + AB']' (Rearrange)

Step 5 : [D' + C' + A' + B']'

(Rule of Duality)

:[( D' + C' )'.( A' + B')']

(Demorgan's law, (A + B)'=(A'. B'))

:[(D''.C'').( A''.B'')] (Demorgan's law)

:[(D.C).(A.B)] (Idempotent law, A'' = A)

: ABCD

Hence only 1 min-term after minimization.

**Question 11: Given the function F = P′ + QR, where F is a function in three Boolean variables P, Q and R and P′ = !P, consider the following statements.**

** S1: F = Σ (4, 5, 6)**

** S2: F = Σ (0, 1, 2, 3, 7)**

** S3: F = Π (4, 5, 6)**

** S4: F = Π (0, 1, 2, 3, 7)**

**Which of the following is true?**

GATE CS 2015

- S1-False, S2-True, S3-True, S4-False
- S1-True, S2-False, S3-False, S4-True
- S1-False, S2-False, S3-True, S4-True
- S1-True, S2-True, S3-False, S4-False

**Solution**: (A) S1-False, S2-True, S3-True, S4-False

**Explanation**

After drawing the K map of F = P` + QR ,we can find out S2 and S3 are TRUE. Alternate Explanation :

P Q R = (!P + QR)

0 => 0 0 0 => 1+0.0 =1 =>Σ

1 => 0 0 1 => 1+0.1 =1 =>Σ

2 => 0 1 0 => 1+1.0 =1 =>Σ

3 => 0 1 1 => 1+1.1 =1 =>Σ

4 => 1 0 0 => 0+0.0=0 =>Π

5 => 1 0 1 => 0+0.1=0 =>Π

6 => 1 1 0 => 0+1.0=0 =>Π

7 => 1 1 1 => 0+1.1=1 =>Σ

as sigma means 1 and pi means 0

therefore Σ = (0,1,2,3,7)

Π = (4,5,6)

**Question 12: The function AB’C + A’BC + ABC’ + A’B’C + AB’C’ is equivalent to**

GATE IT 2004

- AC’+AB+A’C
- AB’+AC’+A’C
- A’B+AC’+AB’
- A’B+AC+AB’

**Solution**: (B) AB’+AC’+A’C

**Explanation**

(A'BC + A'B'C) + (ABC' + AB'C') + AB'C A'C(B + B') + AC'(B + B') + AB'C A'C * 1 + AC' * 1 + AB'C A'C + AC' + AB'C A'C + A(C' + B'C) A'C + A(C' + B') A'C + AC' + AB'

Thus, option (B) is correct.

**Question 13: Which expressions is equivalent to (A⊕B)⊕C**

GATE IT 2005

- (A+B+C)(A’+B’+C’)
- (A+B+C)(A’+B’+C)
- ABC+A’(B⊕C)+B’(A⊕C)
- None of the Above

**Solution**: (C ) ABC+A’(B⊕C)+B’(A⊕C)

**Explanation**

(A ⊕ B) ⊕ C

By Solving, We get

= (A ⊕ B)′ C + (A ⊕ B) C′

The above expression can be written as:

= (A ⊙ B) C + (A ⊕ B) C′

Now,

= (AB + A′B′) C + (A ⊕ B) C′

= ABC + A′B′C + AB′C′ + A′BC′ [As: X + X = X]

[So, A′B′C + A′B′C = A′B′C]

= ABC + (A′B′C + A′B′C) + AB′C′ + A′BC′

This can be written as:

ABC + A′ (B ⊕ C) + B′ (A ⊕ C)

**Question 14: Let, x1⊕x2⊕x3⊕x4 = 0 where x1, x2, x3, x4 are Boolean variables, and ⊕ is the XOR operator. Tick the correct answer.**

GATE CS 2016

- x1x2x3x4 = 0
- x1x3+x2 = 0
- x′1⊕x′3=x′2⊕x′4
- x1+x2+x3+x4 = 0

**Solution**: (C ) x′1⊕x′3=x′2⊕x′4

**Explanation**

First we rearrange the terms,

x1⊕x2⊕x3⊕x4 = 0

x1⊕x3⊕x2⊕x4 = 0

x1⊕x3 = x2⊕x4

Then use the a⊕b=a′⊕b′a⊕b=a′⊕b′ to get the (C)

x′1⊕x′3=x′2⊕x′4.

Only option (C) is correct.

**Question 15: Which of the following is false:**

GATE 2013 Mock

- Digital signature is used to verify a message's authenticity.
- Digital certificate is issued by a third party.
- Digital certificate ensures integrity of the message.
- Digital signature ensures non-repudiation.

**Solution**: (C ) Digital certificate ensures integrity of the message.

**Explanation**

Digital certificates only verify the identity of the user for whom the digital certificate is issued.

**Question 16: What happens when a bit-string is XORed with itself n-times as shown: [ B⊕ (B⊕ (B⊕ (B........ n times) ] **

GATE CS 1998

- complements when n is even
- complements when n is odd
- divides by 2^n always
- remains unchanged when n is even

**Solution**: (D) remains unchanged when n is even

**Explanation**

Here n refers to the number of times XOR operation is triggered.

For example,

A⊕A⊕A = A (Number of the XOR operation is 2 ,i.e., Even)

A⊕A⊕A⊕A = 0 (Number of XOR operation is 3 ,i.e., Odd)

A⊕A⊕A⊕A⊕A = A (Number of XOR operation is 4 ,i.e., Even)

A⊕A⊕A⊕A⊕A⊕A = 0 (Number of XOR operation is 5 ,i.e., Odd)

In general, the output remains constant when the number of XOR operations is Even, but the output is 0 when the number of XOR operations is Odd.

**Question 17: Suppose the domain set of an attribute consists of signed four digit numbers. What is the percentage rate of reduction in storage space of this attribute if it is stored as an integer rather than in character form?**

GATE CS 1998

- 80%
- 20%
- 60%
- 40%

**Solution**: (C ) 60%

**Explanation**

I assume byte-addressable memory- nothing smaller than a byte can be used. We have four digits. So, to represent signed 4 digit numbers we need 5 bytes- 4 for four digits and 1 for the sign (like -7354). So, required memory = 5 bytes Now, if we use integers, the largest number needed to represent is 9999 and this requires 2 bytes of memory for signed representation (one byte can represent only 256 unique integers). So, memory savings while using integer is,

= (5−2)/5

= 3/5

= 60 %

So, option (C) is correct.

**Question 18: If w, x, y, z are boolean variables, then which of the following in CORRECT?**

GATE CS Mock 2018

- wx + w(x+y) + x(x+y) = w + xy
- (wx'(y + z'))' + w'x = w' + x + y'z
- (wx'(y + xz') + w'x')y = xy'
- (w + y)(wxy + wyz) = wxy + xyz

**Solution**: (B) (wx'(y + z'))' + w'x = w' + x + y'z

**Explanation**

(wx’(y + z’))’ + w’x

= w’ + w’x + y’z

= w’ + x + y’z

Hence, the correct option is (B).

**Question 19: Which of the following set of components is sufficient to implement any arbitrary Boolean function?**

**a) XOR gates, NOT gates**

**b) 2 to 1 multiplexers**

**c) AND gates, XOR gates, 1**

**d) Three-input gates that output (A.B)+C for the inputs A, B and C.**

ISRO CS 2017

- a and d
- b and c
- c
- All

**Solution **(B) b and d

**Explanation**

Using implementation of logic gates of 2x1 Multiplexers. 2x1 Multiplexers are sufficient to implement any Boolean function. Similarly, we can also use {∧,⊕,⊤} (i.e., AND, XOR, and 1) to implement any Boolean functions. So, option (B) is correct.

**Question 20: Quadrature Amplitude Modulation means changing both:**

UGC NET CS 2017

- Frequency and phase of the carrier.
- Frequency and Amplitude of the carrier.
- Amplitude and phase of the carrier.
- Amplitude and Wavelength of the carrier.

**Solution**: (C ) Amplitude and phase of the carrier.

**Explanation**

Quadrature Amplitude Modulation means changing both the amplitude and phase of the carrier. So, option (C) is correct.

## FAQs

**What are the benefits of logic design minimization, and why is it necessary?**

Minimization is significant since it minimizes the associated circuit's cost and complexity. As can be seen in the diagram above, the reduced version of the expression uses fewer logic gates and decreases the circuit's complexity significantly.

**Which tool performs logic optimization?**

The synthesis tool performs RTL logic optimization by turning a high-level design circuit description into an optimal gate-level representation using fundamental logic gates such as and, or, nor, and so on.

**What is meant by Boolean function?**

A Boolean function is one in which the arguments and results are taken from a two-element set (often true, false, 0/1, or -1/1). Alternative names are switching function (or logical function), which is used in logic, and truth function (or logical function), which is used in earlier computer science literature.

**What are the advantages of simplification of Boolean functions?**

There are numerous advantages to simplifying Boolean functions before implementing them in hardware. A smaller number of gates lowers the cost of the hardware, lowers the amount of heat created by the chip, and, most crucially, enhances the speed.

**What is K-map and why is it used?**

The Karnaugh map (K-map) is a visual method for minimizing Boolean expressions without the need for Boolean algebra theorems or equation manipulations. A K-map can be compared to a more advanced version of a truth table. Expressions with two to four variables can be easily reduced using a K-map.