표준형 알고리즘과 그 응용

표준형 수업에서는 그 존재에 대해 두 가지 증명을 제시했다. 첫째 증명은 진리표를 거친다. 그 표의 행 수는 $2^n$ 이다(변항이 $n$ 개일 때). 둘째 증명은 논리식을 그 유일한 형성 규칙에 따라 변항으로부터 따라간다. 어느 쪽도 함언, 쌍조건, 중첩된 부정으로 쓰인 논리식 앞에서 어떻게 진행해야 하는지는 말하지 않는다. 그런데 논리식은 보통 그런 모습으로 나타난다. 그렇다면, 표기 자체 위에서 작동하고, 생각하지 않고도 실행할 수 있으며, 멈춘다는 것과 동치인 논리식을 준다는 것이 확실한 절차가 빠져 있는 것이다. 그것이 알고리즘이며, 그 연구가 이 수업의 첫째 대상이다. 둘째 대상은 그것으로 하는 일, 곧 장치의 동작을 논리식으로 기술하고 그것을 재현하는 회로를 구성하는 일이다.

표기와 대체

이 코스의 논리식은 흰 동그라미와 검은 동그라미의 기호열이며, $\neg$, $\vee$, $\wedge$, $\rightarrow$, $\leftrightarrow$, $\veebar$ 의 각 기호는 부정 논리합으로부터 정의된 약기였음을 떠올리자(명제 논리의 언어 수업). 식 $((p \vee q) \rightarrow (\neg q \wedge p))$ 을 쓸 때 우리는 기호열을 쓰는 것이 아니라 그 표기를 쓰는 것이다. 표기는 트리이며, 그 잎은 변항이고 노드는 결합자 $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$, $\veebar$, $\downarrow$ 의 하나이며, 각 노드는 자신의 성분을 가진다. 모든 표기는 단 하나의 논리식, 곧 그 약기를 풀어서 얻는 논리식을 가리킨다. 그리고 같은 논리식이 여러 표기를 가질 수 있다. 표준형 수업에서는 식 $\neg\neg\varphi$ 와 식 $(\varphi \vee \varphi)$ 이 같은 기호열임을 지적했다. 알고리즘이 읽는 것은 표기이지 기호열이 아니다. 그래서 둘을 구별해 두는 것이 좋다. 이 구별은 각 스텝이 어디에 작용하는지를 알기 위해서만 중요하므로, 문자 $\varphi$, $\psi$, $\chi$ 를 표기에도, 그것이 가리키는 논리식에도 사용하며, 가리켜진 논리식이 의미론적으로 동치일 때 $\varphi \eqsem \psi$ 이라고 쓴다. 표기의 부분 표기란 그 노드 하나를 뿌리로 하는 부분 트리이다.

알고리즘의 한 스텝은 어떤 부분 표기를 다른 부분 표기로 바꾼다. 이 바꿈이 의미를 바꾸지 않음을 보장하는 도구는 의미론적 귀결과 동치 수업의 의미론적 대체 정리이다. 그러나 그 정리는 기호열 안의 한 출현을 바꾸는 것이고, 하나의 부분 표기는 기호열 안의 여러 출현에 대응할 수 있다. 각 약기가 자신의 성분을 복제하기 때문이다. 식 $(\varphi \vee \psi) = ((\varphi \downarrow \psi) \downarrow (\varphi \downarrow \psi))$ 에서는 성분 $\varphi$ 가 두 번 나타난다. 다음 보조정리는 대체를 표기에 맞게 고친다.

여기서 $F_c$ 은 결합자의 진리 함수이다. 예컨대 $F_\neg(a) = 1 - a$, $F_\wedge(a, b) = ab$ 이며, 다른 결합자도 마찬가지이다. 같은 결과는 의미론적 대체 정리를 기호열 안의 $\theta$ 의 각 사본에 한 번씩 적용하고, 동치를 추이성으로 이어서도 얻을 수 있다. 표기에 의한 증명이 더 짧은 것은 사본이 아니라 쓰인 결합자를 세기 때문이다.