진리표 (Truth Table)
쉽게 풀면
진리표는 'P와 Q가 각각 참이거나 거짓일 수 있는 모든 경우의 수를 나열하고, 그때마다 'P 그리고 Q'나 'P 또는 Q' 같은 복합 명제가 참인지 거짓인지를 표로 정리한 것이다. 논증의 타당성을 기계적으로 검증하는 데 유용한 도구로 쓰인다.
왜 중요한가
명제논리에서 복합명제의 진리치를 구성요소 명제들의 진리치 조합에 따라 체계적으로 나열하는 진리표로, 논리적 타당성·동치·모순 등을 기계적으로 판별할 수 있게 해주는 기본 도구다.
논문에서는 이렇게 쓰입니다
명제논리 논증의 타당성을, 관련된 명제 변항들의 모든 가능한 참거짓 조합을 표로 만들어 전제가 모두 참인 줄에서 결론도 항상 참인지 기계적으로 확인하는 검증 방법을 설명한다.
변항이 하나 늘 때마다 따질 경우가 두 배로 늘어나 진리표가 금세 커진다는 방법상의 한계를 설명합니다.
조금 더 깊게 보면
진리표는 명제논리 수준에서는 결정절차로 완전하지만, 술어논리처럼 무한한 논의영역을 다루는 체계에서는 모든 경우를 유한한 표로 나열할 수 없어 그대로 적용되지 않는다는 한계가 있다. 진리표는 명제논리의 결정절차로서 완전하지만, 명제 변항의 수가 조금만 늘어나도 행의 수가 지수적으로 증가하므로, 실제 논리 회로 설계나 자동 정리증명에서는 카르노 맵이나 이진 결정 다이어그램 같은 더 효율적인 대안 표현이 함께 쓰인다. 이러한 대안 표현들은 진리표와 논리적으로 동등한 정보를 담으면서도, 사람이 시각적으로 단순화하거나 컴퓨터가 효율적으로 계산하기에 더 적합하도록 구조화되어 있다.
주의할 점
진리표는 명제 변항의 수가 늘어날 때마다 검토해야 할 경우의 수가 두 배씩 늘어나므로(n개의 변항에 2의 n제곱 줄), 변항이 많아지면 실용적으로 다루기 어려워진다는 한계가 있다. 진리표는 명제 변항의 수가 늘어날 때마다 검토해야 할 경우의 수가 두 배씩 늘어나므로(n개의 변항에 2의 n제곱 줄), 변항이 많아지면 실용적으로 다루기 어려워진다는 한계가 있으며, 술어논리처럼 무한한 논의영역을 다루는 체계에서는 이 방법 자체가 원리적으로 적용되지 않는다는 점도 기억해야 한다.