Digital Logic : Logic Functions and Minimisation GATE Previous Years Questions Solved

Ques 21: The switching expression corresponding to f(A,B,C,D) =Σ(1,4,5,9,11,12) is:

GATE 2005

(A) BC′D′+A′C′D+AB′D

(B) ABC′+ACD+B′C′D

(C) ACD′+A′BC′+AC′D′

(D) A′BD+ACD′+BCD′

Ans: (A) BC′D′+A′C′D+AB′D

Solution:

Ques 22: Given two three bit numbers a₂a₁a₀ and b₂b₁b₀ and c the carry in, the function that represents the carry generate function when these two numbers are added is: 

GATE 2006

(A) a₂b₂+a₂a₁b₁+a₂a₁a₀b₀+a₂a₀b₁b₀+a₁b₂b₁+a₁a₀b₂b₀+a₀b₂b₁b₀

(B) a₂b₂+a₂b₁b₀+a₂a₁b₁b₀+a₁a₀b₂b₁+a₁a₀b₂+a₁a₀b₂b₀+a₂a₀b₁b₀

(C) a₂+b₂+(a₂⊕b₂)(a₁+b₁+(a₁⊕b₁)+(a₀+b₀))

(D) a₂b₂+a₂‘a₁b₁+(a₂a₁)’a₀b₀+a₂‘a₀b₁‘b₀+a₁b₂‘b₁+a₁‘a₀b₂‘b₀+a₀(b₂b₁)’b₀

Ans: A) a₂b₂+a₂a₁b₁+a₂a₁a₀b₀+a₂a₀b₁b₀+a₁b₂b₁+a₁a₀b₂b₀+a₀b₂b₁b₀

Solution: c₁=a₀b₀

c₂=a₁b₁+a₁c₁+b₁c₁

c3=a₂b₂+a₂c₂+b₂c₂
=a₂b₂+a₂a₁b₁+a₂a₁c₁+a₂b₁c₁+b₂a₁b₁+b₂a₁c₁+b₂b₁c₁
=a₂b₂+a₂a₁b₁+a₂a₁a₀b₀+a₂b₁a₀b₀+b₂a₁b₁+b₂a₁a₀b₀+b₂b₁a₀b₀

Option is A.

Ques 23: Consider a Boolean function f(w,x,y,z). Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors i1=⟨w1,x1,y1,z1⟩ and i2=⟨w2,x2,y2,z2⟩ , we would like the function to remain true as the input changes from i1 to i2 (i1 and i2 differ in exactly one bit position) without becoming false momentarily. Let f(w,x,y,z)= ∑(5,7,11,12,13,15). Which of the following cube covers of f will ensure that the required property is satisfied? 

GATE 2006

(A) w’xz, wxy’, xy’z, xyz, wyz

(B) wxy, w’xz, wyz

(C) wx(yz)’, xz, wx’yz

(D) wxy’, wyz, wxz, w’xz, xy’z, xyz

Ans: (A) w’xz, wxy’, xy’z, xyz, wyz

Solution:

Ques 24: We consider the addition of two 2′s complement numbers b_n−1b_n−2…b₀ and a_n−1a_n−2…a₀. A binary adder for adding unsigned binary numbers is used to add  the two numbers. The sum is denoted by c_n−1c_n−2…c₀ and the carry-out by c_out. Which one of the following options correctly identifies the overflow condition?

GATE 2006

(A) c_out(a_n−1⊕b_n−1)’

(B) a_n−1b_n−1c’_n−1+(a_n−1b_n−1)’c_n−1

(C) c_out⊕c_n−1

(D) a_n−1⊕b_n−1⊕c_n−1

Ans: (B) a_n−1b_n−1c’_n−1+(a_n−1b_n−1)’c_n−1

Solution: Number representation in 2’s complement representation:

• Positive numbers as it is
• Negative numbers in 2′s complement form.

So, the overflow conditions are

1. When we add two positive numbers (sign bit 0) and we get a sign bit 1
2. When we add two negative numbers (sign bit 1) and we get sign bit 0
3. Overflow is relevant only for signed numbers and carry is used for unsigned numbers
4. When the carryout bit and the carryin to the most significant bit differs

When we add one positive and one negative number we won’t get a carry. Also,points 1 and 2 are leading to point 4. So, if we see the options, B is the correct one here as the first part takes care of case 2 (negative numbers) and the second part takes care of case 1 (positive numbers) – point 4.  We can see counter examples for other options:

A – Let n=4 and we do 0111+0111=1110. This overflows as in 2′s complement representation we can store only up to 7. But the overflow condition in A returns false as c_out=0

C – This works for the above example. But fails for   1001+0001=1010 where there is no actual overflow (−7+1=−6), but the given condition gives an overflow as c_out=0 and c_n−1=1

D – This works for both the above examples, but fails for 1111+1111=1110 (−1+−1=−2) where there is no actual overflow but the given condition says so.

Ques 25: Consider numbers represented in 4-bit Gray code. Let h₃h₂h₁h₀  be the Gray code  representation of a number n and let g₃g₂g₁g₀ be the Gray code of (n+1)(modulo16)  value of the number. Which one of the following functions is correct?

GATE 2006

(A) g₀(h₃h₂h₁h₀)=∑(1,2,3,6,10,13,14,15)

(B) g₁(h₃h₂h₁h₀)=∑(4,9,10,11,12,13,14,15)

(C) g₂(h₃h₂h₁h₀)=∑(2,4,5,6,7,12,13,15)

(D) g₃(h₃h₂h₁h₀)=∑(0,1,6,7,10,11,12,13)

Ans: (C) g₂(h₃h₂h₁h₀)=∑(2,4,5,6,7,12,13,15)

Solution: We need to map min terms of  g₃g₂g₁g₀ with respect to h₃h₂h₁h₀.

Hence  g₂ matches with option C.