GATE IT 2006 | Question: 36

Question

The majority function is a Boolean function $f(x, y, z)$ that takes the value $1$ whenever a majority of the variables $x,y,z$ are $1.$ In the circuit diagram for the majority function shown below, the logic gates for the boxes labeled $P$ and $Q$ are, respectively,

• A. $\textsf{XOR}, \textsf{AND}$
• B. $\textsf{XOR}, \textsf{XOR}$
• C. $\textsf{OR}, \textsf{OR}$
• D. $\textsf{OR}, \textsf{AND}$

Comments

Aren’t the multiplexer assignments wrong here, when x is high the upper line is selected and when it is low the lower line is selected but it should be the other way round

---

P NEEDS TO BE OR GATE. Q CAN BE EITHER OR GATE or AND GATE.

---

@raja11sep

NO, Q cannot be OR gate here , otherwise the eqn will be independent of x.

Answer 1

Given expression:

$xP+\bar{x}Q=f$

Or, $x(y \: op_1 \: z) + \bar{x}(y \: op_2 \: z) = f \quad \to (1)$ $${\begin{array}{|c|c|c|c|}\hline
\textbf{X}&    \textbf{Y}&  \textbf{Z}&\bf{ Output(f)}\\\hline
0&0&0&0 \\\hline 0&0&1&0\\ \hline    0&1&0&0 \\ \hline   0&1&1&1\\ \hline   1&0&0& 0 \\ \hline   1&0&1&1  \\ \hline   1&1&0& 1 \\ \hline   1&1&1&1\\ \hline
\end{array}}\qquad{\begin{array}{|c|c|c|c|c|}\hline
\textbf{x\\yz}&    \textbf{00}&  \textbf{01}&\bf{ 11}& \textbf{10} \\\hline
0&...&...&1&... \\\hline 1&...&1&1&1\\ \hline
\end{array}}$$ $f \implies xz+xy+yz$

$\quad \implies xz+xy+(x+\bar{x})yz $

$\quad \implies xz+xy+xyz+\bar{x}yz$

$\quad \implies x(z+y+yz)+\bar{x}yz$

$\quad \implies x[z+y(1+z)]+\bar{x}(y \bullet z)$

$\quad \implies x(z+y) + \bar{x}(y \bullet z) \quad \to (2)$

Comparing $(1)$ and $(2)$ we get,

$OP_1 = + (OR)$

$OP_2 = \bullet (AND)$

Correct Answer: $D$

Comments

@raja11sep Because the equation comes out to be : $x(y+z) + x’yz$ which matches only with option D.

---

Key of the q: $f$ outputs $1$ only when majority (i.e. atleast $2$) of $x,y,z$ have value $1$.

---

@Abhrajyoti00

can’t this be the reason , that in option C , the resulting eqn is independent of x whether its 0 or 1 , it will always result 1 only,

eqn = z+y  , even for  001 it will output 1.

Answer 2

Ans : D) OR,AND

This is because the value of 'f' should be 1 whenever a majority of the variables is 1. If we select x as '1' , the either of z or y or both z& y needs to be 1 for the output 'f' to be '1'

The output can be low only if less than 2 variables are high. ie.atleast 2 variables are low. hence z & y should be 0. therefore AND gates can be used.

Comments

can anyone explain it please?

---

The simplest method, no need to go for wasting time in k-map.

The function is 1 only when the majority is one, it means in function f(x,y,z) at least two var. must be 1.

X	Y	Z	f(x,y,z)
0	1	1	1
1	0	1	1
1	1	0	1
1	1	1	1

now observe from the given mux and the above table:

when x = 1, in order to get f(x,y,z) = 1, there must be OR between y and z.

when x == 0, in order to get f(x,y,z) = 1, there must be AND between y and z.  

Answer 3

Here when x=0 we get Q operator and when x=1 we get P operator.

So looking to the truth table in below image:
 

we can see when x=0 yz do AND operation and when x=1 yz do OR operation.
So P is OR gate and Q is AND gate.