Editing Majority function (section)

== Boolean circuits ==
[[File:Majority Logic.png|thumb|right|Three-bit majority circuit]]
[[File:Four-Bit Majority Circuit.png|thumb|Four-bit majority circuit]]

A ''majority gate'' is a [[logical gate]] used in [[circuit complexity]] and other applications of [[Boolean circuits]]. A majority gate returns true if and only if more than 50% of its inputs are true.

For instance, in a [[Adder (electronics)|full adder]], the carry output is found by applying a majority function to the three inputs, although frequently this part of the adder is broken down into several simpler logical gates.

Many systems have [[triple modular redundancy]]; they use the majority function for [[majority logic decoding]] to implement [[error correction]].

A major result in [[circuit complexity]] asserts that the majority function cannot be computed by [[AC0|AC0 circuits]] of subexponential size.