ブール論理において、多数決関数（たすうけつかんすう、、中央値演算子とも呼ばれる）とは、入力の半数以上が偽であるときに偽と評価され、それ以外では真と評価されるブール関数である。すなわちこの関数の値は、入力の多数決の値に等しい。
ブール回路
多数決ゲートとは、回路計算量およびブール回路の他の応用で用いられる論理ゲートである。多数決ゲートは、入力の50%を超える部分が真であるとき、かつそのときに限り真を返す。
例えば全加算器では、桁上げ出力は3つの入力に多数決関数を適用することによって求められるが、加算器のこの部分はより単純ないくつかの論理ゲートに分解されることが多い。
多くのシステムは三重モジュール冗長性を持ち、誤り訂正を実装するために多数決論理復号に多数決関数を用いる。
回路計算量における主要な結果の一つは、多数決関数は準指数サイズのAC0回路では計算できないと主張する。
性質
任意のx、y、zについて、三項中央値演算子〈x, y, z〉は次の等式を満たす。 〈x, y, y〉 = y 〈x, y, z〉 = 〈z, x, y〉 〈x, y, z〉 = 〈x, z, y〉 〈〈x, w, y〉, w, z〉 = 〈x, w, 〈y, w, z〉〉
これらを公理として満たす抽象的な系は中央値代数である。
三項中央値演算子関数の他の有用な性質には次のものがある。 〈x, y, z〉 = w が与えられたとき、〈x, y, w〉 = z 〈¬x, ¬y, ¬z〉 = ¬〈x, y, z〉 〈x, y, x ⊕ y ⊕ z〉 = 〈x, y, ¬z〉 〈¬x, y, x ⊕ y ⊕ z〉 = 〈¬x, y, z〉
同数の場合 ほとんどの応用では、入力のちょうど半分が0でちょうど半分が1であるときに何が起こるかという問題に対処しなくて済むように、意図的に入力の数を奇数にしている。偶数個の入力に対して多数決関数を計算するわずかなシステムでは、「0」に偏っていることが多い。すなわち、入力のちょうど半分が0であるときに「0」を出力する。例えば4入力の多数決ゲートは、2つ以上の0がその入力に現れたときにのみ0を出力する。いくつかのシステムでは、同数の場合はランダムに解消されることがある。
多数決に対する単調論理式
n = 1のとき、中央値演算子は単に単項の恒等演算xである。n = 3のとき、三項中央値演算子は論理積と論理和を用いてxy + yz + zxとして表すことができる。
任意のnに対して、サイズO(n5.3)の多数決に対する単調論理式が存在する。これは確率的手法を用いて証明される。したがって、この論理式は非構成的である。
多項式サイズの多数決に対する明示的な論理式のためのアプローチも存在する。 ソーティングネットワークから中央値を取る方法。ここで各比較・交換の「配線」は単純にORゲートとANDゲートである。––セメレディ（AKS）構成はその一例である。 より小さな多数決回路の出力を組み合わせる方法。 Valiantによる単調論理式の証明を脱ランダム化する方法。
関連項目
注
参考文献
外部リンク