다수결 함수

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

불 논리에서 다수결 함수(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>는 다음을 만족한다:

  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>>

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

참고 문헌[편집]

같이 보기[편집]