진리표

문자가 세 개이면 2 × 2 × 2 = 8줄이 나오고, 진리표는 그 여덟 줄을 빠짐없이 적어서 짐작에 맡기는 경우를 남기지 않습니다.

가능한 상황마다 한 줄

앞의 두 단원에서 본 연결어에는 쓸모 있는 성질이 하나 있습니다. 각 단순 명제가 참인지 거짓인지만 알면, 그것들로 만든 합성 명제 전체의 진릿값이 하나로 정해진다는 성질입니다. 진리표는 바로 이 성질을 이용합니다. 진리표에는 단순 명제들이 가질 수 있는 참거짓 조합을 한 줄에 하나씩 빠짐없이 적습니다. 그리고 줄마다 합성 명제의 값을 계산해 적습니다. 이때 문장이 무슨 뜻인지는 전혀 필요 없고, T와 F 값만 있으면 됩니다.

그러면 줄은 몇 개가 필요할까요? 단순 명제 하나는 T 아니면 F 둘 중 하나이므로, 문자가 하나 늘어날 때마다 줄 수가 두 배가 됩니다. 문자가 하나면 2줄, 둘이면 4줄, 셋이면 8줄이고, n개면 2의 n제곱 줄이 필요합니다. 문자가 다섯 개만 되어도 진리표는 벌써 32줄입니다. 그래서 진리표를 자주 쓰는 사람들은 식을 되도록 짧게 유지합니다. 줄을 적는 순서도 정해져 있습니다. forall x 를 비롯한 대부분의 교재는 첫째 열의 위쪽 절반을 T로, 아래쪽 절반을 F로 채웁니다. 둘째 열은 4분의 1씩 나누어 채우고, 이런 식으로 계속 나누어 가서 마지막 열에서는 T, F, T, F가 번갈아 나오게 씁니다. 이 순서를 지키기만 하면 빠지는 조합도, 두 번 적히는 조합도 생기지 않습니다.

안쪽부터 바깥쪽으로

명제 (p ∨ q) ∧ ¬r를 예로 들어 봅시다. p, q, r 세 입력 열을 적은 다음, 산수에서 괄호를 계산하는 것과 같은 순서로 식의 조각마다 열을 하나씩 더합니다. 먼저 p ∨ q를 계산하고, 다음에 ¬r을 계산하고, 마지막으로 이 둘을 잇는 주 연결어 ∧를 계산합니다. 어느 줄에서든 한 번에 앞 단원에서 배운 작은 규칙 하나만 적용하면 됩니다. 그렇게 채운 그렇게 채운 마지막 열이 우리가 구하려던 답입니다. 이 예에서는 명제 전체가 여덟 줄 가운데 3줄에서 참입니다. 그 세 줄은 r이 거짓이면서 p와 q 가운데 적어도 하나가 참인 줄입니다.

항진명제, 모순, 동치

어떤 명제는 마지막 열이 전부 T로 나옵니다. 예를 들어 p ∨ ¬p(「비가 오거나 비가 오지 않는다」)는 날씨가 어떻든 상관없이 모든 줄에서 참입니다. 이런 명제를 항진명제, 또는 논리적 참이라고 합니다. 반대로 p ∧ ¬p처럼 마지막 열이 전부 F로 나오는 명제도 있는데, 이런 명제를 모순이라고 합니다. 대부분의 명제는 어떤 줄에서는 참이고 어떤 줄에서는 거짓입니다. 이런 명제를 우연 명제(contingent)라고 합니다. 우연 명제가 참인지 아닌지는 세상이 실제로 어떤지에 달려 있다는 뜻입니다.

두 명제의 마지막 열이 한 줄 한 줄 모두 같으면 두 명제는 동치라고 합니다. 드모르간의 법칙이 맞는지, 「조건문은 그 대우와 같다」는 주장이 맞는지 확인하는 방법이 바로 이것입니다. 같은 입력 열 위에 두 명제의 열을 각각 만들고 서로 비교하면 됩니다. 진리표를 만들어 보면 p → q는 ¬p ∨ q와 열이 같다는 것도 알 수 있습니다. 문제에서 「아니다」, 「그리고」, 「또는」만 쓰라고 할 때, 이 사실을 이용하면 조건문을 쉽게 고쳐 쓸 수 있습니다.