다수결 함수 문서 원본 보기

{{위키데이터 속성 추적}}
[[불 논리]]에서 '''다수결 함수'''(majority function), 혹은 '''중앙값 연산자'''(median operator)는 입력되는 참의 개수가 ''n/2''보다 크면 참, 아니면 거짓을 반환하는 ''n''[[대수 구조|항 연산]]이다. 참을 1, 거짓을 0으로 표현한다면 다음과 같이 나타낼 수 있다.

:<math>\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. </math>

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

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

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

== 성질 ==
3진 다수결 함수 &lt;x, y, z&gt;는 다음을 만족한다:
# &lt;x, y, y&gt; = y
# &lt;x, y, z&gt; = &lt;z, x, y&gt;
# &lt;x, y, z&gt; = &lt;x, z, y&gt;
# &lt;&lt;x, w, y&gt;, w, z&gt; = &lt;x, w, &lt;y, w, z&gt;&gt;

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

== 참고 문헌 ==
* {{저널 인용
 | first = L. | last = Valiant | authorlink = 레슬리 밸리언트
 | title = Short monotone formulae for the majority function
 | journal = Journal of Algorithms
 | volume = 5
 | issue = 3 | year = 1984 | pages = 363–366
 | doi = 10.1016/0196-6774(84)90016-6
 | ref = harv
 | postscript = <!--None-->}}.
* {{서적 인용| last=Knuth | first=Donald E. | authorlink=도널드 커누스| title=Introduction to combinatorial algorithms and Boolean functions | series=[[The Art of Computer Programming]] | volume=4.0 | date=2008 | isbn=0-321-53496-4 | pages=64–74 | publisher=Addison-Wesley | location=Upper Saddle River, NJ }}

== 같이 보기 ==
{{위키공용분류|Majority functions}}
* [[불 대수]]

{{전거 통제}}

[[분류:회로 복잡도]]
[[분류:불 대수]]