3-Input Majority Function from 2-Input Gates

The majority-of-three function outputs 1 when at least two of its three inputs are 1, and 0 otherwise. It appears throughout hardware design: triple-redundant voting circuits in aerospace use it for fault tolerance, carry-out in full adders is a majority function, and certain error-correcting codes use majority logic for decoding. This problem tests your ability to express majority using only 2-input primitive gates.

Your task is to implement Y = majority(A, B, C) using only 2-input AND and OR gates. No 3-input gates, no XOR, no NAND. The output is 1 when two or more inputs are 1, and 0 otherwise.

| A | B | C | Y | |---|---|---|---| | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 |

The Boolean expression for majority is Y = AB + BC + AC — the OR of all three pairwise AND combinations. Implementing this directly with 2-input gates requires 3 AND gates and 2 OR gates (total 5 gates). A pair of inputs is ANDed to test whether both are 1, and the three pair results are OR-reduced. The OR of any two pair results can be computed first, then OR-ed with the third.

| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | A | input | 1 | First vote input | | B | input | 1 | Second vote input | | C | input | 1 | Third vote input | | Y | output | 1 | 1 when at least two of A, B, C are 1 |

Constraints

• Only 2-input AND and OR gates are allowed. No 3-input gates, no XOR, NAND, NOR, or NOT.
• The optimal solution uses 3 AND gates and 2 OR gates (5 components total).
• The circuit is purely combinational. No clock or state.

Topics

Related problems

• Binary to HexEasy
• 1-to-4 Demultiplexer from AND and NOT GatesEasy
• 2-to-4 Line Decoder with Active-High EnableEasy
• Hex Nibble to BinaryEasy
• Odd Parity Bit Generator for 3-bit DataEasy
• Full Adder from Half AddersEasy
• Modulo ArithmeticMedium
• Two's Complement: Encode a Negative DecimalEasy