多数決機能

ブール論理において、多数決関数(中央値 演算子とも呼ばれる) は、引数の半分以上が false の場合は false と評価され、それ以外の場合は true と評価されるブール関数です。つまり、関数の値は入力の過半数の値と等しくなります。

多数決ゲートは、回路の複雑さやブール回路のその他のアプリケーションで使用される論理ゲートです。多数決ゲートは、入力の 50% 以上が true の場合にのみ true を返します。

たとえば、全加算器では、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 ⟩⟩

これらを公理として満たす抽象システムは中位代数です。

ほとんどのアプリケーションでは、意図的に奇数個の入力を強制することで、入力のちょうど半分が 0 で、ちょうど半分が 1 の場合に何が起こるかという問題に対処する必要がありません。偶数個の入力で多数決関数を計算する少数のシステムは、多くの場合「0」に偏っています。つまり、入力のちょうど半分が 0 の場合に「0」を生成します。たとえば、4 入力の多数決ゲートでは、入力に 0 が 2 つ以上出現した場合にのみ 0 出力になります。^[1]いくつかのシステムでは、同点がランダムに決着することがあります。^[2]

n = 1の場合、中央値演算子は単なる単項恒等演算xです。n = 3 の場合、三項中央値演算子は、論理積と論理和を使用して xy + yz + zxのように表すことができます。

任意のnに対して、サイズO( n ^5.3 )の多数決の単調な公式が存在する。これは確率的方法を用いて証明される。したがって、この公式は非構成的である。^[3]

多項式サイズの過半数に関する明示的な式を求めるアプローチが存在します。

• ソートネットワークから中央値を取得します。ここで、各比較およびスワップ「ワイヤ」は、単なる OR ゲートと AND ゲートです。Ajtai – Komlós – Szemerédi (AKS) 構造がその一例です。
• より小さな多数決回路の出力を結合する。^[4]
• 単調な式のValiant証明を非ランダム化する。^[5]

• ブール代数（構造）
• ブール代数の標準的な定義
• ボイヤー・ムーア多数決アルゴリズム
• 多数決問題（セルオートマトン）

• Knuth, Donald E. (2008)。組み合わせアルゴリズムとブール関数の紹介。コンピュータプログラミングの芸術。第 4a 巻。アッパーサドルリバー、ニュージャージー州: Addison-Wesley。pp. 64–74。ISBN 978-0-321-53496-5。

ウィキメディア・コモンズの多数派機能に関連するメディア