10.3 진리표를 통한 동치 판정
1. 절의 학술적 목표
본 절은 진리표 방법을 이용하여 두 명제의 논리적 동치를 판정하는 절차를 학술적으로 검토하는 것을 목표로 한다. 진리표 방법은 명제 논리에서 동치 관계를 기계적으로 판정할 수 있는 가장 기본적인 절차이며, 명제 논리의 결정 가능성의 한 사례이다. 본 절은 동치 판정의 원리, 표준 절차, 두 가지 판정 방법, 예시, 한계를 체계적으로 정리한다.
2. 동치 판정의 일반 원리
진리표 방법에 의한 동치 판정의 일반 원리는 다음과 같다. 두 명제 A와 B가 논리적으로 동치이기 위한 필요충분조건은 모든 진리값 할당에서 두 명제의 진리값이 일치하는 것이다. 따라서 진리표를 작성하여 모든 행에서 A와 B의 진리값을 비교하면, 두 명제의 동치 여부를 결정할 수 있다(Mendelson, 2015).
3. 첫째 판정 방법: 직접 비교
첫째 판정 방법은 두 명제의 진리값을 직접 비교하는 것이다. 절차는 다음과 같다. 첫째, 두 명제에 포함된 모든 원자 명제를 식별한다. 둘째, 모든 진리값 할당을 행으로 나열한다. 셋째, 각 명제에 대한 열을 추가하고 진리값을 계산한다. 넷째, 모든 행에서 두 명제의 진리값을 비교한다. 다섯째, 모든 행에서 진리값이 일치하면 동치이고, 하나라도 일치하지 않으면 동치가 아니다(Copi, Cohen, & McMahon, 2014).
4. 둘째 판정 방법: 쌍조건의 항진성 검사
둘째 판정 방법은 두 명제의 쌍조건이 항진명제인지 검사하는 것이다. 절차는 다음과 같다. 첫째, “A ↔ B” 공식을 구성한다. 둘째, 이 공식의 진리표를 작성한다. 셋째, 마지막 열의 모든 행이 T이면 항진명제이고, 따라서 두 명제는 동치이다. 이 방법은 환원 정리에 기반하며, 동치 판정을 항진성 판정으로 환원한다(Mendelson, 2015).
5. 두 방법의 동등성
첫째 방법과 둘째 방법은 동등하다. 즉, 한 방법으로 동치임을 보일 수 있으면 다른 방법으로도 보일 수 있으며, 그 역도 성립한다. 이러한 동등성은 환원 정리에 의하여 보장된다. 두 방법의 선택은 편의에 따라 이루어지며, 일반적으로 첫째 방법이 더 직접적이고 둘째 방법이 더 통합적이다(Enderton, 2001).
6. 판정 예시: 교환 법칙
연언의 교환 법칙 “P ∧ Q ≡ Q ∧ P“를 진리표로 판정한다. P와 Q 두 원자 명제에 대하여 4행의 진리표를 작성한다.
| P | Q | P ∧ Q | Q ∧ P |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | F | F |
| F | F | F | F |
모든 행에서 두 명제의 진리값이 일치하므로 두 명제는 동치이다(Mendelson, 2015).
7. 판정 예시: 드 모르간의 법칙
드 모르간 법칙의 한 형태 “¬(P ∧ Q) ≡ ¬P ∨ ¬Q“를 진리표로 판정한다.
| P | Q | ¬(P ∧ Q) | ¬P ∨ ¬Q |
|---|---|---|---|
| T | T | F | F |
| T | F | T | T |
| F | T | T | T |
| F | F | T | T |
모든 행에서 두 명제의 진리값이 일치하므로 두 명제는 동치이다(De Morgan, 1847).
8. 판정 예시: 조건의 변형
조건의 동치 변형 “P → Q ≡ ¬P ∨ Q“를 진리표로 판정한다.
| P | Q | P → Q | ¬P ∨ Q |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
모든 행에서 두 명제의 진리값이 일치하므로 두 명제는 동치이다. 이 동치는 조건이 부정과 선언만으로 표현될 수 있음을 보여 준다(Enderton, 2001).
9. 비동치의 판정 예시
두 명제가 동치가 아닌 사례로 “P → Q“와 “Q → P“를 진리표로 비교한다.
| P | Q | P → Q | Q → P |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | T | F |
| F | F | T | T |
둘째 행과 셋째 행에서 두 명제의 진리값이 다르므로 두 명제는 동치가 아니다. 이 결과는 조건과 그 역이 일반적으로 동치가 아님을 보여 준다(Copi, Cohen, & McMahon, 2014).
10. 동치 판정의 효율성
진리표를 통한 동치 판정의 효율성은 원자 명제의 수에 의하여 결정된다. n개의 원자 명제에 대하여 진리표는 2^n개의 행을 가지므로, 원자 명제의 수가 증가할 때 작업량이 기하급수적으로 증가한다. 예를 들어 5개의 원자 명제에 대하여 진리표는 32행을 가진다. 이러한 한계는 진리표 방법이 작은 공식의 동치 판정에 가장 적합함을 보여 준다(Mendelson, 2015).
11. 동치 판정의 학술적 의의
진리표를 통한 동치 판정은 다음과 같은 학술적 의의를 가진다. 첫째, 그것은 명제 논리의 동치 관계를 기계적으로 결정할 수 있게 한다. 둘째, 그것은 명제 논리의 결정 가능성의 구체적 사례이다. 셋째, 그것은 논리 법칙의 형식적 검증의 기본 도구이다. 넷째, 그것은 공식의 변형과 단순화의 정당성을 검증할 수 있게 한다(Enderton, 2001).
12. 본 절의 결론적 정리
진리표를 통한 동치 판정은 두 명제의 진리값을 모든 가능한 진리값 할당에 대하여 비교함으로써 동치 여부를 결정하는 절차이다. 두 가지 판정 방법이 가능하다. 첫째는 두 명제의 진리값을 직접 비교하는 방법이고, 둘째는 두 명제의 쌍조건이 항진명제인지 검사하는 방법이다. 두 방법은 환원 정리에 의하여 동등하다. 진리표 방법은 교환 법칙, 드 모르간 법칙, 조건의 변형 등의 동치 관계를 명확히 검증하며, 명제 논리의 동치 관계 분석의 기본 도구를 제공한다. 학습자는 진리표 방법의 원리와 절차를 정확히 이해하고, 다양한 동치 관계의 검증에 적용할 수 있어야 한다.
13. 출처
- De Morgan, A. (1847). Formal Logic: or, The Calculus of Inference, Necessary and Probable. London: Taylor and Walton.
- Enderton, H. B. (2001). A Mathematical Introduction to Logic (2nd ed.). San Diego: Academic Press.
- Copi, I. M., Cohen, C., & McMahon, K. (2014). Introduction to Logic (14th ed.). London: Routledge.
- Mendelson, E. (2015). Introduction to Mathematical Logic (6th ed.). Boca Raton: CRC Press.
14. 버전
- 문서 버전: 1.0
- 작성 기준일: 2026-04-15