기능 완성도

논리학에서 논리 연결자 또는 부울 연산자의 기능적으로 완전한 집합은 집합의 구성원을 부울식으로 결합하여 가능한 모든 진리표를 표현하는 데 사용할 수 있는 집합이다.^[1][2] 잘 알려진 완전한 연결 장치 집합은 이진 접속사와 부정으로 구성된 { AND}이(가) 아니다. 싱글톤 세트 각각 {NAND }과(와) { NOR }이(가) 기능적으로 완전하다.

기능적으로 완성된 관문이나 관문 세트는 유니버설 관문/관문이라고도 할 수 있다.

기능적으로 완전한 관문 세트는 입력의 일부가 아니거나 시스템에 대한 출력의 일부가 아닌 '쓰레기 비트'를 계산의 일부로 사용하거나 생성할 수 있다.

명제적 논리의 맥락에서 기능적으로 완전한 커넥티브 집합은 또한 (표현적으로) 적당하다고 불린다.^[3]

디지털 전자제품의 관점에서 기능적 완전성은 가능한 모든 논리 게이트가 세트에서 규정하는 유형의 게이트 네트워크로서 실현될 수 있다는 것을 의미한다. 특히 모든 논리 게이트는 바이너리 NAND 게이트 또는 바이너리 NOR 게이트에서만 조립이 가능하다.

소개

논리에 관한 현대의 텍스트는 일반적으로 접속사의 원시적인 부분집합으로 간주된다: 접속사${\displaystyle }${\$displaystyle$$$\$land$}),$$ 분리$($$displaystyle$ \$lor }),$ 부정${\displaystyle \mathrm{}}$display $style \neg}),$ 재료 조건부$(→[displaystystystyle \왼쪽$ $화살표$ $}),$ 그리고 가능한 부분.$$원하면 이러한 원시적 관점에서 코넥티브를 정의함으로써 추가 커넥티브를 정의할 수 있다. 예를 들어 NOR(때로는 $\downarrow {\displaystyle }$ ${\displaystyle \downarrow$ $\},$ 분리 부정을 두 가지 부정의 결합으로 표현할 수 있다.

$A:=\neg A\downarrow B:=\neg A\land \neg B}$

마찬가지로, 접속사 NAND(때로는 $\uparrow {\displaystyle }$ ${\displaystyle \uparrow }$으로 표시됨)$$의 부정은 분리 및 부정의 관점에서 정의될 수 있다. 모든 이진 결합은 {$$ ,${\displaystyle \wedge }$ ,${\displaystyle \vee }$ ,${\displaystyle }$→${\displaystyle \leftrightarrow }$ ,${\displaystyle }$↔} {\$displaystyle \{\neg ,\land ,\lor ,\to ,\riftarrow$ $\backslash \}\}$의 용어로 정의될 수 있으므로 이 세트는 기능적으로 완전하다.

그러나, 그것은 여전히 일부 중복성을 포함하고 있다. 조건부와 쌍방향은 다른 연결 장치에 대해 다음과 같이 정의될 수 있기 때문에, 이 집합은 기능적으로 최소한의 완전한 집합은 아니다.

${\displaystyle {\reasoned}A\to B&:=\neg A\or B\\A\좌우타로우 B&:=(A\to B)\land(B\to A).\end{정렬}}}$

그 뒤를 이어 작은 세트 {${\displaystyle \mathrm{\neg }}$ ,${\displaystyle \wedge }$ ,${\displaystyle \vee }$}} ${\displaystyle \{\neg$,\$land$,\$lor$\}}도$$ 기능적으로 완성된다. 그러나 $\vee {\displaystyle }$ ${\displaystyle \lor$}은(는) 다음과 같이 정의될$$ 수 있으므로 여전히 최소 수준은 아니다.

$(\displaystyle A\lor B:=\neg(\neg A\land \neg B)}$

또는 $\wedge {\displaystyle }$ ${\displaystyle \land}$을(를) $\vee {\displaystyle }$ ${\displaystyle \$$lor$$}$의 관점에서 유사한 방식으로$$ 정의하거나$,{\displaystyle }$ $\vee {\displaystyle }$ ${\displaystyle \rightarrow$ $\}:$

$A\vee B:=\neg A\오른쪽 화살표 B.}$

더 이상의 단순화는 불가능하다. Hence, every two-element set of connectives containing ${\displaystyle \neg }$ and one of ${\displaystyle \{\land ,\lor ,\rightarrow \}}$ is a minimal functionally complete subset of ${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$.

형식 정의

부울 영역 B = {0,1}을(를) 고려할 때, 기본 함수 ƒ에inii 의해 생성된 B의 클론이 모든 함수 ƒn: B → B를 포함하면 모든 엄격히 양의 정수 n ≥에 대해 기능적으로 완전하다. 즉, 하나 이상의 변수를 갖는 모든 부울 함수를 함수 ƒ의i 관점에서 표현할 수 있다면 세트는 기능적으로 완전하다. 적어도 하나의 변수의 모든 부울함수는 이진 부울함수의 관점에서 표현될 수 있기 때문에, F는 모든 이항 부울함수가 F의 함수의 관점에서 표현될 수 있는 경우에만 기능적으로 완전하다.

보다 자연스러운 조건은 F에 의해 생성된 클론이 모든 정수 n n에 대해 모든 함수 ƒⁿ: B → B로 구성되는 것이다. 그러나 F자체가 적어도 하나의 귀무함수를 포함하지 않으면 F의 관점에서 귀무함수, 즉 상수표현을 쓸 수 없기 때문에 위의 예들은 이러한 강한 의미에서는 기능적으로 완전하지 않다. 이 더 강력한 정의로, 기능적으로 가장 작은 완성 세트는 2개의 원소를 가질 것이다.

또 다른 자연 조건은 F에 의해 생성된 클론이 두 개의 무효 상수 기능과 함께 기능적으로 완전하거나 동등하게 전항의 강한 의미에서 기능적으로 완전하다는 것이다. S(x, y, z) = z if x = y 및 S(x, y, z) = x가 부여한 부울 함수의 예는 이 조건이 기능 완전성보다 엄격히 약하다는 것을 보여준다.^[4][5][6]

기능 완성도 특성화

Emil Post는 다음과 같은 연결 장치 집합의 하위 집합이 아닌 경우에만 논리 연결 장치 집합이 기능적으로 완전하다는 것을 증명했다.

• 단조로운 연결 장치; T에서 F로 변경하지 않고 연결된 변수의 진실 값을 F에서 T로 변경하면 이러한 연결 장치가 반환 값을 T에서 F로 변경하지 않는다. 예: $\vee ,{\displaystyle \wedge ,\mathrm{}}$⊤,${\displaystyle }$⊥, ${\displaystyle \mathrm{\{,}}${, {\$displaystyle \ve,\top,\bot$ $\}.$
• 각 연결된 변수가 항상 또는 결코 반환되는 진리 값에 영향을 미치지 않는 연결부호(예:${\displaystyle \mathrm{}\mathrm{,,}}$ ↔,${\displaystyle }$↔,${\displaystyle \mathrm{\leftrightarrow ,}\leftrightarrow ,}$↔, $displaystyle \neg,\top,\bot,\weftarrow,\nleftrightarrow$ $\}).$
• 자체 de Morgan 이중과 동일한 자체 이중 연결부. 모든 변수의 진실 값이 역전된 경우 이 연결부가 반환하는 진리 값(예: ¬${\displaystyle\neg$ MAZ(p,q,r))도 반환된다.
• 진리를 보존하는 연결고리들; 그들은 T를 모든 변수에 할당하는 해석 하에서 진리 값 T를 돌려준다. 예를 들어,${\displaystyle ,,,,\mathrm{},,}$ ,,${\displaystyle }$,, ↔, ↔, ↔, {,${\displaystyle }${, ${\displaystyle \leftrightarrow ,}$ ↔, ↔, \,$top,$ $top, \displaystystystyty,$
• 거짓을 보존하는 연결고리들; 그들은 모든 변수에 F를 할당하는 해석 하에서 진실 값 F를 반환한다. 예를 들어, $\vee ,{\displaystyle \wedge ,}${,$\displaystyle \ve$,\$wedge,\bot,\nrightarrow$

실제로 Post는 현재 Post의 격자라고 불리는 2개 요소 집합 {T, F}에 있는 모든 클론의 격자(구성 중 폐쇄되고 모든 투영을 포함하는 작업 집합)에 대한 완전한 설명을 해 주었는데, 이는 위의 결과를 단순한 귀공으로서 내포하고 있다: 언급된 5개의 커넥티브 집합이 정확히 최대 클론이다.

최소 기능적으로 완료된 연산자 세트

단일 논리 결합 연산자 또는 부울 연산자가 그 자체로 기능적으로 완성되었을 때, 셰퍼 함수^[7] 또는 때로는 단독적으로 충분한 연산자라고 한다. 이 자산을 가진 단일한 운영자는 없다. 서로 이중인격인 낸드와 NOR는 유일하게 2진 셰퍼 기능이다. 이것들은 1880년경 찰스 샌더스 피르스에 의해 발견되었지만 출판되지는 않았고, 독립적으로 재발견되어 헨리 M에 의해 출판되었다. 1913년 ^[8]셰퍼 디지털 전자공학 용어로는 바이너리 낸드 게이트와 바이너리 NOR 게이트가 유일한 바이너리 범용 논리 게이트다.

다음은 arity complete 2를 가진 최소 기능적으로 완전한 논리적 연결장치 집합이다.^[9]

원소

{↑}, {↓}.

두 원소

${\displaystyle \{\vee ,\neg \}}$, ${\displaystyle \{\wedge ,\neg \}}$, ${\displaystyle \{\to ,\neg \}}$, ${\displaystyle \{\gets ,\neg \}}$, ${\displaystyle \{\to ,\bot \}}$, ${\displaystyle \{\gets ,\bot \}}$, ${\displaystyle \{\to ,\nle$$ftrightarrow \}}$, ${\displaystyle \{\gets ,\nleftrightarrow \}}$, ${\displaystyle \{\to ,\nrightarrow \}}$, ${\displaystyle \{\to ,\nleftarrow \}}$, ${\displaystyle \{\gets ,\nrightarrow \}}$, ${\displaystyle \{\gets ,\nleftarrow \}}$, ${\displaystyle \$${\nrightarrow ,\neg \}}$, ${\displaystyle \{\nleftarrow ,\neg \}}$, ${\displaystyle \{\nrightarrow ,\top \}}$, ${\displaystyle \{\nleftarrow ,\top \}}$, ${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$, ${\displaystyle \{\nleftarrow ,\leftrightarrow \}.$$}$

삼원소

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$, ${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$, ${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$, ${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$, ${\displaystyle \{\land ,\lef$$triightarrow ,\nfrightarrow$ $\backslash \}\},$${\displaystyle }${${\displaystyle }$∧,${\displaystyle }$↮,${\displaystyle \mathrm{\top }}$ }${\displaystyle \}.}$ ${\displaystyle$\{\$land,\nfrightarrow,\top$\}.$}$

기능적으로 3개 이상의 완전한 세트는 거의 이진 논리 커넥티브에서 찾아볼 수 없다.^[9] 위의 목록을 읽을 수 있도록 하기 위해, 하나 이상의 입력을 무시하는 연산자는 생략했다. 예를 들어, 첫 번째 입력을 무시하고 두 번째 입력을 출력하는 연산자는 단항 부정으로 대체될 수 있다.

예

• 사용 예제: NAND완전성. 에 의해 예시된 바와 같이,^[10]
  • A a A a A
  • A ∧ B ≡ (A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B) ↑ (A ↑ B)
  • A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
• 사용 예제: NOR완전성. 에 의해 예시된 바와 같이,^[11]
  • A a A a A
  • A ∨ B ≡ (A ↓ B) ≡ (A ↓ B) ↓ (A ↓ B) ↓ (A ↓ B)
  • A ∧ B ≡ (A ↓ A) ↓ (B ↓ B)

전자 회로나 소프트웨어 기능은 재사용에 의해 최적화되어 게이트 수를 줄일 수 있다는 점에 유의하십시오. 예를 들어, "A ∧ B" 운영은 ↑ 게이트로 표현될 때 "A ↑ B"를 재사용하여 실행된다.

X ≡ (A ↑ B); A b B x X x X

다른 도메인에서

논리적 커넥티브(Boolean 연산자)와는 별도로 다른 도메인에서 기능 완성도를 도입할 수 있다. 예를 들어, 모든 가역 연산자를 표현할 수 있다면 가역 가능한 관문 세트를 기능적으로 완전하다고 한다.

3입력 Fredkin 게이트는 그 자체로 기능적으로 완전한 가역성 게이트로, 유일한 충분한 운영자. 토폴리 게이트와 같은 다른 3인치의 보편적 논리 관문이 많이 있다.

양자 컴퓨팅에서, 비록 기능적 완전성의 그것보다 약간 더 제한적인 정의를 가지고 있지만, Hadamard 게이트와 T 게이트는 보편적이다.

세트 이론

집합의 대수학과 부울 대수 사이에는 이형성이 있는데, 즉 그들은 같은 구조를 가지고 있다. 그런 다음 부울 연산자를 세트 연산자로 매핑하면 위의 "번역된" 텍스트도 세트에도 유효하다. 즉, 다른 세트 관계를 생성할 수 있는 "최소 집합의 집합 집합"이 많다. 가장 인기 있는 "최소 연산자 집합"은 {¬, ∩} 및 {¬, ∪}이다. 범용 집합이 금지된 경우, 설정 연산자는 거짓- (OW) 보존으로 제한되며 기능적으로 완전한 부울 대수와 같을 수 없다.

참고 항목

• 완전성(로직)
• 집합 대수
• 부울 대수
• 낸드 논리
• NOR 논리학
• 명령 집합 컴퓨터 1대

참조