📂집합론

항진 명제와 항위 명제

Tautology and contradiction

정의 ¹

모든 논리적 가능성에 대해 참인 명제를 항진 명제^TTautology라고 한다. 모든 논리적 가능성에 대해 거짓인 명제를 항위 명제^{Contradiction}라고 한다.

1. $p$, $q$ 에 대해 조건문 $p \to q$ 가 항진 명제면 함의 명제^Implication라 하고 다음과 같이 나타낸다. $$ p \implies q $$
2. $p$, $q$ 에 대해 쌍조건문 $p \leftrightarrow q$ 가 항진 명제면 동치^Equivalence라 하고 다음과 같이 나타낸다. $$ p \iff q $$

설명

실제로 항위 명제라는 단어는 거의 쓰이지 않으며, 그 대신 모순이라는 말을 많이 사용한다. 기호로는 항진 Tautology과 모순 Contradiction의 앞글자를 따서 항진 $t$, 모순 $c$ 와 같이 나타낸다.

위의 진리표에 따르면 $p$ 가 참이든 거짓이든 $p \lor \lnot p$ 는 참이다. 명제의 정의를 생각해보면 $p$ 가 참이거나 거짓이면 참이라는 말이므로 당연한 말이다. 항진 명제란 이렇듯 ‘사실’과 관계 없이 그 형식만 보아도 참일수밖에 없는 명제를 말한다.

수학에 관심 없는 사람들은 수학이 복잡하다고 어렵다고 하지만, 수학을 공부할수록 깨닫게 되는 것은 수학자들이 ‘생각’을 안하기 위해서 이 악물고 발버둥친다는 것이다. 인류에겐 너무나도 많은 조합의 ‘말’이 있는데, 그 말을 하나하나 따져가면서 옳고 그른 것을 파악할 엄두가 나지 않는다. 그래서 적어도 형식만으로도 파악할 수 있는 것은 딱 그정도만큼의 노력만 해서 파악하고 싶어하는 것이다. 논리를 공부하는 게 띠껍다면 이것이 결국 편해질 것이라는 생각을 하면서 공부하도록 하자.

함의含意 란 뜻意을 포함含하고 있다는 말이므로 Imply의 순화로써 찰떡같긴 하지만, 사실 한국어 화자가 Imply를 함의라고 해석하는 경우는 몹시 드물다. 고상한 분들이 써낸 옛날 전공 서적에는 드문드문 쓰이는 정도로만 알아두자. 함의와 동치의 표현을 사용한 다음 몇가지 법칙들을 소개한다.

법칙 ¹

임의의 명제 $p$, $q$, $r$ 에 대해 다음이 성립한다.

• [1] 합의 법칙: $$ p \implies p \lor q $$
• [2] 단순화 법칙: $$ p \land q \implies p \\ p \land q \implies q $$
• [3] 흡수 법칙: $$ p \land ( p \lor q) \iff p \\ p \lor ( p \land q ) \iff p $$
• [4] 이중부정 법칙: $$ \lnot ( \lnot p) \iff p $$
• [5] 교환 법칙: $$ p \land q \iff q \land p \\ p \lor q \iff q \lor p $$
• [6] 멱등 법칙: $$ p \land p \iff p \\ p \lor p \iff p $$
• [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) $$

위의 법칙들은 논리적인 사고를 하는 인간에겐 숨쉬듯이 당연해야하며, 이공계라면 특별히 네임드라고 할만한 아래의 법칙들도 자유자재로 구사할 수 있어야한다. 본인의 전공이 형식 과학―컴퓨터 공학, 통계학, 수학에 가까울수록 많이 쓰므로 가능한 한 빨리 익숙해지는 것이 좋다.

• [9] 드 모르간의 법칙: $$ \lnot (p \land q) \iff \lnot p \lor \lnot q \\ \lnot(p \lor q) \iff \lnot p \land \lnot q $$
• [10] 대우법: $$ (p \to q) \iff (\lnot q \to \lnot p) $$
• [11] 귀류법: $$ (p \land \lnot q) \to c \iff p \to q $$
• [12] 삼단논법: $$ (p \to q) \land (q \to r) \implies (p \to r) $$

영문표기

해당 포스트에서 소개된 정리들의 영문 표기는 다음과 같다:

• [1] 합의 법칙Law of Addition
• [2] 단순화 법칙Laws of Simplification
• [3] 흡수 법칙Laws of Absorption
• [4] 이중부정 법칙Law of Double Negation
• [5] 교환 법칙Laws of Commutativity
• [6] 멱등 법칙Laws of Idempotency
• [7] 결합 법칙Laws of Associativity
• [8] 분배 법칙Laws of Distributivity
• [9] 드 모르간의 법칙De Morgan’s Laws
• [10] 대우법Contrapositive Law
• [11] 귀류법Reductio ad Absurdum
• [12] 삼단논법Syllogism

특히 [11] 귀류법은 배리법이라고도 하고, [12] 삼단 논법은 추이 법칙^{Law of Transitivity}이라고도 한다.