Propositional & Predicate Logic

1. Overview

명제 및 술어 논리(Propositional & Predicate Logic, PPL)는 애매모호한 인간의 언어를 참(True)과 거짓(False)이라는 단 2개의 물리적 상태(1-bit)로 압축하여, 컴퓨터가 기계적으로 계산(Compute)할 수 있도록 만드는 소프트웨어의 언어적 뼈대입니다.

학습자는 명제 간의 인과성을 통제하는 **명제 논리(Propositional Logic)**의 연결사(AND, OR, NOT, IMPLIES) 역학을 뜯어보고, 수백만 개의 데이터 집합 전체를 단 한 줄의 논리식으로 제어하는 **술어 논리(Predicate Logic)**의 한정자($\forall, \exists$) 물리를 해부합니다. 이를 통해 복잡하게 얽힌 if-else 블록을 수리적으로 완벽하게 간소화하고, 데이터베이스 SQL의 복잡한 쿼리가 논리적으로 모순이 없는지 증명하는 논리 아키텍처 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 명제 논리 역학 (Propositional Mechanics): 명제(Proposition), 진리표(Truth Table), 논리 연결사($\land, \lor, \lnot, \rightarrow, \leftrightarrow$).
• 동치와 추론 (Equivalence & Inference): 논리적 동치(Logical Equivalence), 드모르간의 법칙(De Morgan's Laws), 추론 규칙(Modus Ponens, Modus Tollens).
• 술어 논리와 한정자 (Predicate Logic): 술어(Predicate, $P(x)$), 모든($\forall$, Universal Quantifier), 어떤($\exists$, Existential Quantifier).
• 논리적 오류와 정당성 (Fallacies & Validity): 동어 반복(Tautology), 모순(Contradiction), 우연(Contingency), 전건 긍정/후건 부정.

Out-of-Scope

• 부울 대수를 이용한 트랜지스터 설계: NAND 게이트 회로도 그리기 $\rightarrow$ 01-02-02. Boolean Algebra 영역.
• 프로그램 코드의 메모리 안전성 증명: 논리학을 코드로 가져와 타입 체커(Type Checker) 만들기 $\rightarrow$ 01-02-04. Program Correctness 영역.

Boundaries

• PPL vs. Boolean Algebra (01-02-02): 부울 대수가 논리를 '수학적 방정식과 0/1 비트 물리'로 치환하는 하드웨어 친화적 영역이라면, PPL은 인간의 사고 체계와 인과관계(명제)를 어떻게 '형식화된 기호'로 맵핑할 것인가를 다루는 철학적, 언어학적 기저입니다.

3. Counterexample

• 함축(Implies)의 치명적 오해 (Implication Fallacy): "비가 오면($P$) 땅이 젖는다($Q$)"라는 $P \rightarrow Q$ 명제에서, "비가 오지 않으면($\lnot P$) 땅이 젖지 않는다($\lnot Q$)"라고 멋대로 결론 내리는 전건 부정의 오류(Denying the Antecedent). 개발자가 코드에서 if (P) return Q;를 짜놓고, $P$가 아닐 때는 당연히 $Q$가 안 일어날 것이라 착각하여 예외 처리를 누락하면, 땅이 물청소로 젖은 경우($\lnot P \land Q$)에 프로그램이 치명적 오작동을 일으킵니다.
• 한정자 순서 붕괴 (Quantifier Reversal Fallacy): $\forall x \exists y$ (모든 사람 $x$는 각자의 지문 $y$를 가진다)를 $\exists y \forall x$ (모든 사람 $x$가 공통으로 가지는 단 하나의 지문 $y$가 존재한다)로 뒤바꿔버리는 논리적 대참사. 데이터베이스 쿼리를 짤 때 한정자의 순서를 헷갈리면, 유저마다 각각 할당되어야 할 세션(Session) 키가 모든 유저에게 똑같은 1개의 키로 덮어씌워지는 보안 붕괴가 발생합니다.

4. Prerequisites

• 집합론 기초 (Basic): 술어 논리에서 "어떤 원소 $x$가 집합 $A$에 속한다($x \in A$)"를 다루기 위해 집합의 물리적 개념이 필요합니다. (01-01-01 STR)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 명제와 진리표의 물리적 역학 (Proposition & Truth Table)

• Why to Learn: 프로그램의 if 조건문에 들어가는 모든 로직이 결국 0과 1의 조합임을 깨닫고, 런타임에 발생할 수 있는 '모든 경우의 수'를 눈으로 직접 증명하기 위해서입니다.
• What to Learn:
  • Concepts: 명제(Proposition), 진리값(Truth Value).
  • Skills: 논리곱(AND, $\land$), 논리합(OR, $\lor$), 부정(NOT, $\lnot$), 진리표(Truth Table) 작성.
  • Tools: 논리 게이트 시뮬레이터.
  • Trade-offs: $N$개의 명제 변수가 있을 때, 이를 검증하는 진리표의 크기가 $2^N$으로 폭발하는 완전 탐색의 피곤함 vs 진리표를 그렸을 때 단 하나의 예외도 없이 완벽한 수학적 정당성을 얻는 무결성.
• How to Learn:
  • 1단계: "오늘은 비가 오거나(A), 눈이 온다(B)"라는 자연어를 $A \lor B$로 바꾸고, 둘 다 오는 경우(A=1, B=1)에 왜 전체 명제가 참(1)이 되는지(Inclusive OR) 포괄적 논리의 물리를 뜯어봅니다.
  • 2단계: 변수가 3개인 조건문 if(A && (B || C))가 있을 때, 8줄짜리 진리표($2^3$)를 그려 컴퓨터가 각 경우에 어떻게 CPU 브랜치(Branch)를 타는지 매핑합니다.
• Implement: 3개의 센서 값(A, B, C)을 입력받아 진리표의 $2^3 = 8$가지 경우의 수를 전부 출력하고, 특정 조건일 때 알람을 울리는 논리 회로 시뮬레이터 함수 작성.

Recommended

Core Topic 02: 조건문과 논리적 동치 (Implication & Equivalence)

• Why to Learn: 스파게티처럼 꼬인 if (!A || !(B && C)) 코드를 누구나 알아볼 수 있고 버그 없는 코드로 수리적 리팩토링을 하기 위함입니다.
• What to Learn:
  • Concepts: 함축/조건문(Implies, $\rightarrow$), 쌍조건문($\leftrightarrow$), 역(Converse), 이(Inverse), 대우(Contrapositive).
  • Skills: 논리적 동치($\equiv$), 드모르간의 법칙(De Morgan's Laws), 항진명제(Tautology).
  • Tools: 코드 리팩토링(Boolean Simplification).
  • Trade-offs: 조건문 $P \rightarrow Q$를 인간이 직관적으로 이해하기 쉬운 서술형태 vs 컴퓨터가 연산하기 편한 $\lnot P \lor Q$ 형태(Disjunctive Normal Form)로 치환할 때의 가독성 손실.
• How to Learn:
  • 1단계: $P \rightarrow Q$의 진리표를 그릴 때, 전제($P$)가 거짓(False)이면 결론($Q$)에 상관없이 무조건 명제 전체가 참(True)이 되는 '공허한 참(Vacuous Truth)'의 수리적 충격을 방어 코딩(if (!P) return true;) 물리에 대입해 봅니다.
  • 2단계: "비가 오지 않으면 땅이 젖지 않는다(이)"는 틀릴 수 있지만, "땅이 젖지 않았다면 비가 온 것이 아니다(대우)"는 언제나 참이라는 논리적 동치($P \rightarrow Q \equiv \lnot Q \rightarrow \lnot P$)를 해부합니다.
• Implement: 복잡한 조건식 !(A && (!B || C))를 입력받아 드모르간의 법칙을 재귀적으로 적용하여 !A || (B && !C) 형태로 논리를 최적화하여 반환하는 논리식 정규화 엔진 구현.

Practical

Core Topic 03: 논리적 추론 규칙과 오류 (Inference & Fallacies)

• Why to Learn: 디버깅을 할 때, 현상(Bug)으로부터 원인(Root Cause)을 찾아가는 과정이 논리적으로 100% 타당한지(Valid) 스스로 검열하여 헛다리 짚는 시간을 없애기 위해서입니다.
• What to Learn:
  • Concepts: 전제(Premise), 결론(Conclusion), 타당성(Validity).
  • Skills: 전건 긍정(Modus Ponens), 후건 부정(Modus Tollens), 삼단 논법(Syllogism).
  • Tools: 형식적 증명(Formal Proof).
  • Trade-offs: 전제가 모두 참일 때 결론이 무조건 참이 되는 '타당성(Validity)'의 완벽한 논리 구조 vs 전제 자체가 현실에서 거짓이라면 논리는 타당해도 결론은 쓰레기가 되는 GIGO(Garbage In, Garbage Out)의 물리적 한계.
• How to Learn:
  • 1단계: "서버가 죽으면($P$) 알람이 울린다($Q$)." + "알람이 울리지 않았다($\lnot Q$)." $\Rightarrow$ "고로 서버는 죽지 않았다($\lnot P$)"라는 후건 부정(Modus Tollens)이 장애 대응의 핵심 증명 논리임을 해부합니다.
  • 2단계: 알람이 울렸다고 해서($Q$) 서버가 죽었다($P$)고 단정 짓는 '후건 긍정의 오류'를 통해, 오탐지(False Alarm)가 발생하는 논리적 결함을 뜯어봅니다.
• Implement: 기호화된 전제 리스트 [P -> Q, ~Q]를 입력하면 내장된 추론 규칙 매칭을 통해 결론 ~P를 도출하거나 "추론 불가"를 뱉어내는 미니 논리 증명기 작성.

Advanced

Core Topic 04: 술어 논리와 양화사 (Predicate & Quantifiers)

• Why to Learn: "이 테이블에 있는 모든 유저는 비밀번호가 해시되어 있다"라거나, "권한이 있는 유저가 적어도 한 명은 존재한다"라는 집합적 데이터를 단 한 줄의 SQL 기호로 제어하기 위함입니다.
• What to Learn:
  • Concepts: 술어(Predicate, $P(x)$), 정의역/우주(Domain of Discourse).
  • Skills: 전칭 기호($\forall$, Universal Quantifier), 존재 기호($\exists$, Existential Quantifier), 양화사의 부정(Negation of Quantifiers).
  • Tools: SQL ALL, EXISTS, ANY.
  • Trade-offs: 데이터 $N$개를 for 문으로 싹 다 돌면서 $\forall$ 조건을 확인하는 $O(N)$의 컴퓨팅 비용 vs 인덱스나 해시를 활용해 $\exists$ 조건을 $O(1)$ 만에 뚫고 나오는 단축 평가(Short-circuit Evaluation)의 극단적 성능 최적화.
• How to Learn:
  • 1단계: $x$가 단독으로 있을 때("그는 해커다")는 참/거짓을 알 수 없지만, 한정자 $\exists$를 붙여 "해커인 누군가가 존재한다($\exists x, H(x)$)"로 묶는 순간 완벽한 명제로 굳어지는 술어 논리의 바인딩(Binding) 역학을 해부합니다.
  • 2단계: "모든 코드는 버그가 없다($\forall x, \lnot B(x)$)"의 부정이 "모든 코드는 버그가 있다($\forall x, B(x)$)"가 아니라, "버그가 있는 코드가 적어도 하나는 존재한다($\exists x, B(x)$)"로 드모르간의 법칙이 확장되는 과정을 뜯어봅니다.
• Implement: 데이터베이스 쿼리를 흉내 내어, 조건 배열 data와 한정자 타입(ALL, EXISTS)을 인자로 받아, ALL일 경우 하나라도 거짓이면 즉시 루프를 탈출(return false)하고 EXISTS일 경우 하나라도 참이면 즉시 탈출(return true)하는 단축 평가 논리 엔진.

7. Terminology

8. References

Primary

• [P1] CS2023 - DS/Basic Logic — Foundations of computing logic.
• [P2] SWEBOK v4.0 - Software Requirements / Formal Methods — Logic in specs.

Secondary

• [Logic and Structure] Dirk van Dalen — Mathematical logic standard.
• [Logic in Computer Science] Michael Huth — Practical tool-based logic.

Industry

• [SAT Solvers in Software Verification] — Industry application of logic.
• [Knowledge Representation in AI] — Predicate logic in expert systems.

9. Final Checklist

Primary

• 복잡한 명제 논리식을 '드 모르간의 법칙'과 '분배 법칙'을 사용하여 최소 연산 형태로 물리적 간소화가 가능한가? (P1)
• 서술어 논리에서 양화사가 중첩되었을 때($\forall \exists$ vs $\exists \forall$), 그 선후 관계가 명제의 의미를 어떻게 물리적으로 변화시키는지 서술 가능한가? (P1)

Secondary

• 진리표를 작성하지 않고도 특정 논리식이 '진리값 보존 추론'에 의해 참임을 대수적으로 증명할 수 있는가?
• CNF(논리곱 표준형)가 왜 컴퓨터의 자동 증명 시스템(Resolution)에서 물리적으로 효율적인 구조인지 논리적으로 소통 가능한가?

Industry

• 비즈니스 정책(Policy)이 담긴 자연어 요구사항을 논리 기호로 전사하여, 정책 간의 충돌이나 모순이 발생하는 지점을 수학적으로 탐지 가능한가? (SFIA)
• 보안 규칙 설계 시, '보편 양화사'의 필터링 조건과 '존재 양화사'의 허용 조건이 결합된 화이트리스트 논리를 무결하게 설계할 수 있는가?