From WikiChip
Majority Function (Maj) - Boolean Algebra
< boolean algebra

3-input Majority
Inputs Output
X Y Z Q
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

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.

Equation MAJ left-parenthesis x 1 comma x 2 comma period period period comma x Subscript n Baseline right-parenthesis equals StartLayout Enlarged left-brace 1st Row 1st Column 1 comma 2nd Column if sigma-summation Underscript i equals 1 Overscript n Endscripts x Subscript i Baseline greater-than-or-equal-to StartFraction n Over 2 EndFraction 2nd Row 1st Column 0 comma 2nd Column otherwise period EndLayout

3-input Majority Function[edit]

A 3-input majority function is defined as:

Equation f colon double-struck upper B cubed right-arrow double-struck upper B comma is MAJ 3 left-parenthesis x comma y comma z right-parenthesis equals left-parenthesis x logical-and y right-parenthesis logical-or left-parenthesis x logical-and z right-parenthesis logical-or left-parenthesis y logical-and z right-parenthesis

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

Equation MAJ 3 left-parenthesis x comma y comma z right-parenthesis equals left-parenthesis x logical-and y right-parenthesis circled-plus left-parenthesis x logical-and z right-parenthesis circled-plus left-parenthesis y logical-and z right-parenthesis

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 Equation MAJ left-parenthesis a overbar comma b overbar comma c overbar right-parenthesis equals ModifyingAbove MAJ left-parenthesis a comma b comma c right-parenthesis With bar 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. Equation MAJ 3 left-parenthesis x comma y comma z right-parenthesis equals y if x less-than-or-equal-to y less-than-or-equal-to z . 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]