표준형

이 단원의 앞선 수업들에서는 논리식에 의미를 부여했다. 명제 논리의 의미론 수업은 각 진리값 할당을 모든 논리식으로 확장했고, 의미론적 귀결과 동치 수업은 동치 $\varphi \eqsem \psi$를 정의하고 의미론적 대체를 증명했으며, 일반화된 드모르간 법칙과 분배 법칙 수업은 그 법칙들을 $n$개 논리식의 연언과 선언으로 확장했고, 함수적 완전성 수업은 모든 진리 함수가 어떤 논리식으로 표현됨을 보였다. 그런데 하나의 진리 함수는 무한히 많은 논리식으로 표현되며, 그것들은 서로 매우 다를 수 있다. $(v_1 \rightarrow v_2)$, $\neg(v_1 \wedge \neg v_2)$, $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$는 같은 것의 세 이름이다. 그렇다면 각 동치류에서 정해진 형태의 대표를 고르는 것이 좋다. 그 대표는 수고 없이 읽히고, 어떤 물음들은 보기만 해도 답할 수 있다. 그것이 표준형이다.

리터럴, 절, 표준형

일반화된 법칙 수업에서 정한 $n$개 논리식의 연언과 선언의 표기법을 떠올리자. 그것은 재귀로 정의되며 왼쪽부터 묶는다. 논리식 하나의 연언과 선언은 그 논리식 자신이다.

같은 수업에서 항의 순서와 묶는 방식은 동치를 무시하면 논리식을 바꾸지 않음(일반화된 결합 법칙, 그리고 순서와 반복에 대한 무관성)이 증명되었다. 그래서 괄호 없이 $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$라고도 쓰며, 왼쪽부터 묶는 것으로 이해한다.

리터럴은 변항 $v_n$(양 리터럴이라 한다)이거나 변항의 부정 $\neg v_n$(음 리터럴이라 한다)이다. 리터럴 $\ell$의 반대 리터럴은 $\ell^{*}$으로 쓰며, 같은 변항의 부호가 반대인 리터럴이다.

정의로부터 $(\ell^{*})^{*} = \ell$가 따라 나온다. 두 리터럴은 하나가 다른 하나의 반대 리터럴일 때 상보 쌍을 이룬다. 예를 들어 $v_3$과 $\neg v_3$이다.

절은 리터럴의 선언 $\bigvee_{j=1}^{k} \ell_j$이고, 기본 연언은 리터럴의 연언 $\bigwedge_{j=1}^{k} \ell_j$이며, 두 경우 모두 $k \geq 1$이다. 따라서 리터럴 하나는 절이자 기본 연언이다. 리터럴이 절이나 기본 연언의 $\ell_j$ 가운데 하나일 때, 그 리터럴은 거기에 나타난다고 한다.

논리식이 기본 연언들의 선언이면 선언 표준형에 있고, 절들의 연언이면 연언 표준형에 있다. 곧 각각 다음 두 형태 중 하나일 때이다. 여기서 $m$과 $k_1, \ldots, k_m$은 자연수이고 각 $\ell_{i,j}$는 리터럴이다.

$\Phi$를 $\varphi$ 의 선언 표준형이라 하는 것은, 그것이 선언 표준형에 있고 $\varphi \eqsem \Phi$일 때이다. 연언 표준형도 마찬가지이다. 길이 $k_i$는 연언(또는 절)마다 달라도 된다. 모두에 같은 개수의 리터럴을 요구하면 반복으로 채워야 하고, 아무것도 더해지지 않는다.

“표준형에 있다”는 것이 무엇을 뜻하는지 잠시 생각해 볼 만하다. 그것은 원과 원판의 기호열의 성질이지 그 의미의 성질이 아니다. 자연수와 논리식에 관한 귀납법 수업이 유일 판독성을 증명했으므로, 논리식이 선언인지, 그리고 무엇의 선언인지라는 물음에는 답이 하나뿐이다. 그런데 공식 약어 때문에 어떤 논리식은 표준형처럼 보이지 않는데도 표준형에 있다. 함의 $(v_1 \rightarrow v_2)$는 $(\neg v_1 \vee v_2)$로 정의된다. 그것이 이 절과 동치인 것이 아니라 바로 같은 기호열이며, 따라서 이미 표준형에 있다. 더 놀라운 것은 이중 부정이다. $\neg$과 $\vee$의 정의에 따라 기호열 $(\varphi \vee \varphi)$는 $\neg(\varphi \downarrow \varphi)$, 곧 $\neg\neg\varphi$이다. 그러므로 $\neg\neg v_1$은 리터럴이 아니지만, 글자 그대로 절 $(v_1 \vee v_1)$이다.

연언과 선언의 값

의미론 수업에서 파생 연결사의 값을 가져온다. $v(\neg\varphi) = 1 - v(\varphi)$. $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$는 값 $1$을 가지며, 그것은 둘 다 값 $1$을 가질 때 그리고 그때에만이다. $v(\varphi \vee \psi) = 0$는 둘 다 값 $0$을 가질 때 그리고 그때에만이다. 일반화된 드모르간 법칙과 분배 법칙 수업은 항의 개수에 관한 귀납법으로 이것들을 $n$개 논리식으로 확장했는데, 그것이 값 보조정리이다. 모든 진리값 할당 $v$에 대해, 연언 $\bigwedge_{i=1}^{n} \varphi_i$가 값 $1$을 $v$에서 가지는 것은 각 $\varphi_i$가 값 $1$을 $v$에서 가질 때 그리고 그때에만이고, 선언 $\bigvee_{i=1}^{n} \varphi_i$가 값 $1$을 $v$에서 가지는 것은 어떤 $\varphi_i$가 값 $1$을 $v$에서 가질 때 그리고 그때에만이다. 여기서 증명을 되풀이하지 않고 인용하는 이 보조정리가 임의의 표준형의 값을 계산하는 도구이다.

두 번째 경우는 놓치기 쉽다. 표준형을 부정할 때 리터럴 대신 $\neg\ell_{i,j}$를 쓰고 싶어지는데, $\neg\neg v_n$은 리터럴이 아니다. 결과를 틀로 되돌리는 것은 이중 부정이다.