1.13 진리표(Truth Table)를 통한 논리식 평가 방법
1. 진리표의 정의와 역사
진리표(Truth Table)는 논리식(Logical Formula)에 포함된 모든 명제 변수의 가능한 진리값 조합에 대해 해당 논리식의 진리값을 체계적으로 나열한 표이다. 진리표는 논리식의 의미론적(Semantic) 분석을 위한 기본 도구이며, 논리식의 진리 함수적(Truth-Functional) 성질을 완전하게 결정한다.
진리표의 체계적 사용은 비트겐슈타인(Ludwig Wittgenstein)의 “Tractatus Logico-Philosophicus”(1921)와 포스트(Emil Post)의 “Introduction to a General Theory of Elementary Propositions”(1921)에서 독립적으로 도입되었다. 두 학자 모두 명제 논리의 의미론을 진리값의 체계적 열거로 정의하는 방법론을 개발하였다.
2. 진리표의 구조
n개의 명제 변수 p_1, p_2, \ldots, p_n을 포함하는 논리식 \Phi(p_1, p_2, \ldots, p_n)에 대한 진리표는 다음과 같이 구성된다:
- 입력열(Input Columns): n개의 명제 변수 각각에 대한 열이다.
- 중간열(Intermediate Columns): 논리식의 부분식(Subformula)에 대한 열이다(선택적).
- 출력열(Output Column): 전체 논리식의 진리값에 대한 열이다.
- 행(Rows): 명제 변수의 가능한 모든 진리값 조합에 대응하는 행이다.
n개의 명제 변수에 대해 가능한 진리값 조합의 수는 2^n이다. 따라서 진리표의 행의 수는 2^n이다.
2.1 표준 순서
진리표의 행을 나열하는 표준적 순서는 이진 계수(Binary Counting) 순서를 따른다. n개의 변수에 대해, 각 행은 0부터 2^n - 1까지의 이진수에 대응하며, 첫 번째 변수가 최상위 비트(Most Significant Bit)에 해당한다.
예를 들어, 두 변수 p, q에 대한 표준 순서는:
| 행 번호 | p | q |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
3. 진리표 구성 절차
논리식의 진리표를 구성하는 체계적 절차는 다음과 같다.
3.1 절차 1: 변수와 부분식의 식별
주어진 논리식에서 명제 변수를 식별하고, 연산자 우선순위(Operator Precedence)에 따라 부분식을 안쪽에서 바깥쪽으로 나열한다. 표준적인 연산자 우선순위는:
- \neg (부정) — 최고 우선순위
- \wedge (논리곱)
- \vee (논리합)
- \rightarrow (조건문)
- \leftrightarrow (쌍조건문) — 최저 우선순위
3.2 절차 2: 행의 열거
n개의 변수에 대해 2^n개의 행을 표준 순서에 따라 나열한다.
3.3 절차 3: 부분식의 순차적 평가
각 행에서, 가장 안쪽의 부분식부터 순차적으로 진리값을 계산하여, 최종적으로 전체 논리식의 진리값을 도출한다.
4. 진리표의 구성 예시
4.1 예시 1: (p \rightarrow q) \wedge (q \rightarrow p)
이 논리식은 쌍조건문 p \leftrightarrow q와 동치이다. 이를 진리표로 검증한다.
| p | q | p \rightarrow q | q \rightarrow p | (p \rightarrow q) \wedge (q \rightarrow p) |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
출력열이 p \leftrightarrow q의 진리표와 일치함을 확인할 수 있다.
4.2 예시 2: \neg(p \wedge q) \leftrightarrow (\neg p \vee \neg q)
드모르간 제1법칙의 진리표 검증이다.
| p | q | p \wedge q | \neg(p \wedge q) | \neg p | \neg q | \neg p \vee \neg q | \neg(p \wedge q) \leftrightarrow (\neg p \vee \neg q) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
최종 열이 모든 행에서 1이므로, 이 논리식은 항진(Tautology)이다. 이는 드모르간 법칙이 논리적 진리임을 의미론적으로 확인한 것이다.
5. 진리표에 의한 논리식의 분류
진리표를 통해 논리식은 다음의 세 범주로 분류된다:
5.1 항진(Tautology)
모든 행에서 진리값이 1인 논리식이다. 항진은 변수의 진리값 할당에 무관하게 항상 참이다. 항진은 논리적 진리(Logical Truth)에 해당한다.
예: p \vee \neg p (배중률)
| p | \neg p | p \vee \neg p |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 1 |
5.2 모순(Contradiction)
모든 행에서 진리값이 0인 논리식이다. 모순은 변수의 진리값 할당에 무관하게 항상 거짓이다.
예: p \wedge \neg p
| p | \neg p | p \wedge \neg p |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 0 |
5.3 우연(Contingency)
항진도 모순도 아닌 논리식이다. 일부 진리값 할당에서는 참이고 다른 할당에서는 거짓이다. 경험적 명제의 대부분은 우연에 해당한다.
6. 논리적 동치의 진리표 판정
두 논리식 \Phi와 \Psi가 논리적으로 동치(Logically Equivalent)인 것은 \Phi \leftrightarrow \Psi가 항진인 것과 동치이다. 실용적으로는 \Phi와 \Psi의 진리표에서 출력열이 모든 행에서 일치하는지를 확인하면 된다.
7. 논리적 귀결의 진리표 판정
전제 집합 \{P_1, P_2, \ldots, P_k\}로부터 결론 C가 논리적으로 귀결(Logically Entailed)되는 것은 (P_1 \wedge P_2 \wedge \cdots \wedge P_k) \rightarrow C가 항진인 것과 동치이다.
이를 진리표로 판정하려면, P_1 \wedge P_2 \wedge \cdots \wedge P_k가 참인 모든 행에서 C도 참인지를 확인한다. 전제가 모두 참인 행에서 결론이 거짓인 행이 하나라도 존재하면, 그 행은 반례(Counterexample)이며 논리적 귀결이 성립하지 않는다.
8. 진리표의 완전성과 결정 가능성
진리표 방법은 명제 논리(Propositional Logic)에 대해 완전한 결정 절차(Decision Procedure)를 제공한다. 임의의 명제 논리 논리식이 항진인지, 모순인지, 또는 우연인지를 진리표를 구성하여 유한 단계 안에 판정할 수 있다. 이는 명제 논리가 결정 가능(Decidable)한 논리 체계임을 의미한다.
이 완전성은 명제 논리의 의미론이 진리값의 유한 집합 \{0, 1\} 위에서 정의되며, 변수의 수가 유한할 때 가능한 진리값 조합의 수도 유한하다는 사실에 기인한다.
9. 계산 복잡도와 한계
진리표 방법의 주된 한계는 계산 복잡도(Computational Complexity)에 있다. n개의 변수를 포함하는 논리식에 대해 진리표의 행 수는 2^n이므로, 진리표의 구성과 평가에 소요되는 시간은 O(2^n)이다. 이는 지수적(Exponential) 시간 복잡도이며, 변수의 수가 증가함에 따라 실용적 적용이 급격히 어려워진다.
| 변수 수 n | 행 수 2^n |
|---|---|
| 5 | 32 |
| 10 | 1,024 |
| 20 | 1,048,576 |
| 30 | \approx 1.07 \times 10^9 |
| 50 | \approx 1.13 \times 10^{15} |
이 지수적 복잡도는 명제 논리의 충족 가능성 문제(Satisfiability Problem, SAT)가 NP-완전(NP-Complete) 문제임을 반영한다. 쿡(Stephen Cook)은 1971년 “The Complexity of Theorem-Proving Procedures“에서 SAT 문제가 NP-완전임을 증명하였다. 이 결과는 (P ≠ NP 가정 하에서) 일반적인 명제 논리 논리식의 항진 여부를 다항 시간(Polynomial Time) 내에 판정하는 알고리즘이 존재하지 않음을 시사한다.
10. 진리표와 불 함수의 동등성
n개의 변수를 가진 불 함수(Boolean Function)의 수는 2^{2^n}이다. 이는 2^n개의 행으로 구성된 진리표의 출력열이 취할 수 있는 서로 다른 이진 패턴의 수와 일치한다. 따라서 n-변수 불 함수와 n-변수 진리표 사이에는 일대일 대응(Bijection)이 존재하며, 진리표는 불 함수의 완전한 외연적(Extensional) 표현이다.
| 변수 수 n | 불 함수 수 2^{2^n} |
|---|---|
| 1 | 4 |
| 2 | 16 |
| 3 | 256 |
| 4 | 65,536 |
| 5 | \approx 4.29 \times 10^9 |
11. 진리표로부터 논리식의 도출
진리표가 주어졌을 때, 해당 진리표에 대응하는 논리식을 체계적으로 도출할 수 있다.
11.1 논리합 정규형(DNF) 도출
진리표에서 출력이 1인 각 행에 대해, 해당 행의 입력 조합에 대응하는 최소항(Minterm)을 구성하고, 이들 최소항의 논리합을 취한다.
예를 들어, 다음 진리표가 주어졌을 때:
| p | q | f(p,q) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
출력이 1인 행은 (0,1)과 (1,0)이다. 대응하는 최소항은 \neg p \wedge q와 p \wedge \neg q이다. 따라서:
f(p,q) = (\neg p \wedge q) \vee (p \wedge \neg q) = p \oplus q
논리곱 정규형(CNF) 도출
진리표에서 출력이 0인 각 행에 대해, 해당 행의 입력 조합에 대응하는 최대항(Maxterm)을 구성하고, 이들 최대항의 논리곱을 취한다.
위의 예에서 출력이 0인 행은 (0,0)과 (1,1)이다. 대응하는 최대항은 p \vee q와 \neg p \vee \neg q이다. 따라서:
f(p,q) = (p \vee q) \wedge (\neg p \vee \neg q)
이 결과는 DNF에서 도출한 p \oplus q와 논리적으로 동치이다.
진리표는 명제 논리의 의미론적 분석을 위한 근본적 도구이며, 논리식의 평가, 분류, 동치 판정, 귀결 판정, 그리고 정규형 도출을 위한 체계적이고 기계적인 방법을 제공한다.