page_title: Majority function
section_title: Boolean circuits
hierarchical_section_title: Majority function / Boolean circuits
caption_attribution_description: English: A voting circuit using 4 NAND gates.
context_page_description: In Boolean logic, the majority function is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise.
  Alternatively, representing true values as 1 and false values as 0, we may use the formula
  The "−1/2" in the formula serves to break ties in favor of zeros when n is even. If the term "−1/2" is omitted, the formula can be used for a function that breaks ties in favor of ones.
  Most applications deliberately force an odd number of inputs so they don't have to deal with the question of what happens when exactly half the inputs are 0 and exactly half the inputs are 1. The few systems that calculate the majority function on an even number of inputs are often biased towards "0"—they produce "0" when exactly half the inputs are 0 -- for example, a 4-input majority gate has a 0 output only when two or more 0's appear at its inputs. In a few systems, the tie can be broken randomly.
context_section_description: 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 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 circuits of subexponential size.
caption: Three bit majority circuit
exif: {}