Latest revision as of 20:04, 15 December 2015

Majority function (sometimes quorum function) is a threshold function that produces a 1 if and only if the majority of the inputs are 1. Otherwise, the output is 0. This function is only defined for three or more odd inputs. The majority function can be found in various applications such as adders, subtractors, hash functions, and Muller C-element.

3-input Majority Function[edit]

A 3-input majority function is defined as:

In the field of cryptography, the XOR version is also common.

properties[edit]

The majority function is a unate function, symmetric, monotone increasing, and self-dual. It therefore, with the addition of just an inverter it can satisfy all the conditions needed to be functionally complete (i.e. {NOT, MAJ} is a complete set). Being self-dual means that which could yields various hardware implementation optimization - such as floating the inversion point to a more desired location.

median algebra[edit]

Main article: median algebra

By treating the majority function conjunction and disjunction as min and max functions respectively, then it's easy to see how the majority function can serve as the median - i.e. . Median algebra is a generalized idea based on the majority function, algebra with axioms on a set of truth values.

Majority gate[edit]

Main article: majority gate

The majority gate is a logic gate that implements the majority function as a circuit.

See also[edit]

• threshold function