📂집합론

삼단논법의 수리논리적 증명

법칙 ¹

다음의 함의명제를 삼단논법^syllogism이라 한다. $$ ( p \to q ) \land ( q \to r ) \implies p \to r $$

설명

삼단논법을 모르는 사람은 없고 굳이 설명해줄 것도 없다고 본다. 고대의 철학적 논쟁이 아닌 이상에야 굳이 ‘삼단논법에 의해’라는 말을 쓰는 경우는 흔치 않다. 그만큼 우리들에게는 익숙한 논법이자 보편타당한 원리기 때문이다.

하지만 삼단논법이 증명이 되는 것이고 증명을 해야하는 것이라고 생각하는 사람은 별로 없었을 것이다. 수학에서 사용하는 논리 기호들을 이용해 삼단논법을 증명해보자.

증명

조건부의 논리적 동치: $$ p \to q \equiv \left( \lnot p \lor q \right) \qquad \cdots \star $$

여러가지 항진명제:

• [2] 단순화 법칙: $$ p \land q \implies p \\ p \land q \implies q $$
• [7] 결합 법칙: $$ (p \land q) \land r \iff p \land (q \land r) \\ (p \lor q) \lor r \iff p \lor (q \lor r) $$
• [8] 분배 법칙: $$ p \land (q \lor r) \iff (p \land q) \lor (p \land r) \\ p \lor (q \land r) \iff (p \lor q) \land (p \lor r) $$

$( p \to q ) \iff (\lnot p \lor q)$ 이므로 $$ \begin{align*} & ( p \to q ) \land ( q \to r ) \\ \iff & (\lnot p \lor q) \land (\lnot q \lor r) & \because \star \\ \iff & (\lnot p \land \lnot q) \lor (\lnot p \land r) \lor (q \land \lnot q) \lor (q \land r) & \because [7], [8] \\ \implies& \lnot p \lor \lnot p \lor c \lor r & \because [2] \\ \implies& \lnot p \lor r \\ \implies& p \to r & \because \star \end{align*} $$ 여기서 $c$ 는 모순을 의미한다.

■