다수결 함수
보이기
불 논리에서 다수결 함수(majority function), 혹은 중앙값 연산자(median operator)는 입력되는 참의 개수가 n/2보다 크면 참, 아니면 거짓을 반환하는 n항 연산이다. 참을 1, 거짓을 0으로 표현한다면 다음과 같이 나타낼 수 있다.
"−1/2"는 n이 짝수일 때 입력되는 참의 개수가 n/2이면 거짓을 반환하게 하는 역할을 한다.
다수결 게이트
[편집]다수결 게이트는 전가산기에서 자리올림수 출력이나 오류 교정을 구현할 때 다수결 논리 디코딩에 사용되며, 더 간단한 논리적 게이트로 나타낼 수 있다. 회로 복잡도 이론에 따르면 이 함수는 AC0 회로에서 으로 계산할 수 없다.
다수결 함수의 일반화
[편집]n = 1일 때에는 항등함수 x가 되고, n = 3일 때에는 xy + yz + zx가 된다. 이때 +는 논리합이나 배타적 논리합이나 같은 결과를 도출한다. O(n5.3)을 만족하는 일반화된 공식이 존재하지만 이는 확률적 방법에 의한 비구성적 증명이다. 정렬 네트워크를 사용하면 다항식 수준의 다수결 함수일 때에는 명시적 공식을 구할 수 있다.
성질
[편집]3진 다수결 함수 <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>>
참고 문헌
[편집]- 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.