다수결 함수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

\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이 짝수일 때 참과 거짓이 같은 경우를 깨는 역할을 한다. 회로복잡도의 주 결과는 이 함수가 준 지수함수꼴의 AC0 회로로 계산할 수 없음을 보여준다.다수결 게이트(majority gate)는 회로복잡도나 다른 불린 회로에 사용되는 논리 회로로 50% 이상의 입력이 참인 경우에만 참을 반환한다.

다수결 함수의 일반화[편집]

n = 1일 때에는 다수결 함수는 항등함수 x가 된다. n = 3인 경우 xy + yz + zx와 같이 표현될 수 있다. (이 때 +는 논리합이나 배타적 논리합이나 같은 결과를 도출한다.) 임의의 n에 대해서는 O(n5.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 > >

이 공리들을 만족하는 추상계를 중앙값 대수라 한다.

참고 문헌[편집]

같이 보기[편집]