📂집합론

항진 명제와 항위 명제

정의 ¹

모든 논리적 가능성에 대해 참인 명제를 항진 명제^tautology라고 한다. 모든 논리적 가능성에 대해 거짓인 명제를 항위 명제^{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}이라고도 한다.