(D) is the correct choice!

The Gateway to Computer Science Excellence

+23 votes

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,

- XOR, AND
- XOR, XOR
- OR, OR
- OR, AND

+52 votes

Best answer

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\\ \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$

$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\\ \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$

+22 votes

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.

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.

+8

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,492 answers

195,439 comments

100,711 users