다수결 함수

불 논리에서 다수결 함수(majority function), 혹은 중앙값 연산자(median operator)는 입력되는 참의 개수가 n/2보다 크면 참, 아니면 거짓을 반환하는 n항 연산이다. 참을 1, 거짓을 0으로 표현한다면 다음과 같이 나타낼 수 있다.

${\displaystyle \operatorname {Majority} \left(p_{1},\dots ,p_{n}\right)=\left\lfloor {\frac {1}{2}}+{\frac {\sum _{i=1}^{n}p_{i}-1/2}{n}}\right\rfloor .}$

"−1/2"는 n이 짝수일 때 입력되는 참의 개수가 n/2이면 거짓을 반환하게 하는 역할을 한다.

다수결 게이트는 전가산기에서 자리올림수 출력이나 오류 교정을 구현할 때 다수결 논리 디코딩에 사용되며, 더 간단한 논리적 게이트로 나타낼 수 있다. 회로 복잡도 이론에 따르면 이 함수는 AC0 회로에서 ${\displaystyle 2^{o(n)}}$으로 계산할 수 없다.

n = 1일 때에는 항등함수 x가 되고, n = 3일 때에는 xy + yz + zx가 된다. 이때 +는 논리합이나 배타적 논리합이나 같은 결과를 도출한다. O(n^5.3)을 만족하는 일반화된 공식이 존재하지만 이는 확률적 방법에 의한 비구성적 증명이다. 정렬 네트워크를 사용하면 다항식 수준의 다수결 함수일 때에는 명시적 공식을 구할 수 있다.

3진 다수결 함수 <x, y, z>는 다음을 만족한다:

1. <x, y, y> = y
2. <x, y, z> = <z, x, y>
3. <x, y, z> = <x, z, y>
4. <<x, w, y>, w, z> = <x, w, <y, w, z>>

이러한 대수 구조를 중앙값 대수라 한다.

• Valiant, L. (1984). “Short monotone formulae for the majority function”. 《Journal of Algorithms》 5 (3): 363–366. doi:10.1016/0196-6774(84)90016-6. .
• Knuth, Donald E. (2008). 《Introduction to combinatorial algorithms and Boolean functions》. The Art of Computer Programming 4.0. Upper Saddle River, NJ: Addison-Wesley. 64–74쪽. ISBN 0-321-53496-4. 

위키미디어 공용에 다수결 함수 주제와 관련된 미디어 분류가 있습니다.

• 불 대수