[집합론] 1. 초등논리(1: 명제, 항진, 함의, 동치, 모순)

[집합론] 1. 초등논리(1: 명제, 항진, 함의, 동치, 모순)

참 또는 거짓을 구분할 수 있는 문장을 명제(statement)라고 한다. 다음은 명제인 것과 명제가 아닌 것의 예시들이다.

명제인 예:

1. 2019년을 기준으로 마산은 창원시의 일부이다.(참)

2. 2+2는 5와 같다.(거짓)

3. OO역에 KTX가 오고 있다.(상황에 따라 참 또는 거짓)

명제가 아닌 것의 예:

1. 이 참치초밥은 맛있다.(한 개인의 주관)

2. 좋은 아침이야.(한 개인의 주관)

3. x+1=3.(x에 대한 언급이 없다.)

문장을 더 이상 분해할 수 없는 하나의 문장으로 이루어진 명제를 단순명제(simple statement), 둘 이상의 단순명제들로 결합된 명제를 합성명제(compound statement)라고 한다. 

합성명제의 예: 2+2는 5와 같고, \(\sqrt{3}\)을 십진법으로 전개할 때 105번째 자릿수는 7이다.

명제를 나타낼 때는 \(p,\,q,\,r,\,\cdots\)로 나타내고, 소문자는 단순명제를, 대문자는 합성명제를 나타낸다.

명제 \(p,\,q,\,r,\,\cdots\)들을 연결하여 합성명제를 구성하는 도구를 결합자(connectives)라 한다. 다음은 주로 사용되는 결합자들이다.

"아니다(not)":\(\sim\) 

"이고(and)":\(\vee\) 

"또는(or)":\(\wedge\) 

"...이면...(if)":\(...\rightarrow...\) 

"...이면 그리고 그때에만...(if and only if)":\(...\leftrightarrow...\) 

명제의 참, 거짓의 관계를 다음과 같이 진리표(truth table)에 나타내면 편리하다.

\(p\)	\(\sim p\)
T	F
F	T

임의의 명제 \(p,\,q\)사이에 결합자 \(\vee\)를 붙여서 정의한 합성명제 \(p\vee q\)의 진리표는 다음과 같다.

\(p\)	\(q\)	\(p\vee q\)
T	T	T
T	F	F
F	T	F
F	F	F

기호 \(p\vee q\)는 "p이고(and) q" 또는 "p와 q의 논리곱(conjuction)"이라고 한다. \(p\vee q\)와 같은 합성명제에 대해 각각의 명제 \(p,\,q\)를 성분(components)이라고 한다. 이때 \(p\vee q\)의 논리적 가능성(logical possibilities)은 다음의 \(2\times2=4\)가지 이다. 

1. p:참, q:참

2. p:거짓, q:참

3. p:참, q:거짓

4. p:거짓, q:거짓

예를 들어 \(\sim[(\sim p)\vee(\sim q)]\)의 진리표는 다음과 같다.

\(p\)	\(q\)	\(\sim p\)	\(\sim q\)	\((\sim p)\vee(\sim q)\)	\(\sim[(\sim p)\vee(\sim q)]\)
T	T	F	F	F	T
T	F	F	T	F	T
F	T	T	F	F	T
F	F	T	T	T	F
단계		1	1	2	3

   

임의의 두 명제 \(p,\,q\)사이에 결합자 \(\wedge\)를 붙인 합성명제 \(p\wedge q\)는 "p 또는(or) q" 또는 "p와 q의 논리합(disjunction)"이라고 하고, 진리표는 다음과 같다.

\(p\)	\(q\)	\(p\wedge q\)
T	T	T
T	F	T
F	T	T
F	F	F

논리곱과 논리합의 차이는 \(p,\,q\)가 모두 참일때만 \(p\vee q\)는 참이 되지만 \(p,\,q\)가 모두 거짓일때만 \(p\wedge q\)는 거짓이 된다.

단순명제(p, q) 또는 합성명제(P, Q)에 대한 모든 논리적 가능성에 대한 진리값이 모두 같으면 P와 Q는 논리적 동치(logically equivalent) 또는 간단히 동치(equivalent)라 하고 \(P\equiv Q\)로 나타낸다. 앞에서 다루었던 \(p\wedge q\)와 \(\sim(\sim p\vee\sim q)\)의 진리표는 동일하므로 \(p\wedge q\equiv\sim(\sim p\vee\sim q)\)이다.

임의의 명제 \(p,\,q\)사이에 조건부(conditional) 결합자 \(\rightarrow\)를 붙여서 조건문 \(p\,\rightarrow\,q\)(p이면 q)를 구성한다. 이때 다음의 표와 같이 \(p\,\rightarrow\,q\)는 \(\sim(\sim p\vee\sim q)\)와 동치인 명제로 정의한다.

\(p\)	\(q\)	\(\sim q\)	\(p\vee\sim q\)	\(p\,\rightarrow\,q\equiv\sim p\wedge q\)
T	T	F	F	T
T	F	T	T	F
F	T	F	F	T
F	F	T	F	T

이것은 p이면 q이고 p인데 q가 아닐 수 없다라는 의미이다. 따라서 이 조건문의 진리값은 p가 참이고 q가 거짓인 경우에만 거짓이고 나머지 경우는 모두 참이다.

예를들어 p:햇빛이 빛나고 있다, q: 나는 테니스를 치고 있다, 일 때 \(p\,\rightarrow\,q\)는 "햇빛이 빛나고 있으면 나는 테니스를 치고 있다"이다. 

임의의 명제 \(p,\,q\) 사이에 쌍조건부(biconditional) 결합자 \(\leftrightarrow\)를 붙여서 합성명제 \(p\leftrightarrow q\)를 구성한다. 이 명제는 다음의 표와 같이 합성명제 \((p\,\rightarrow\,q)\vee(q\,\rightarrow\,p)\)와 동치인 것으로 정의한다.

\(p\)	\(q\)	\(p\,\rightarrow\,q\)	\(q\,\rightarrow\,p\)	\(p\,\leftrightarrow\,q\equiv(p\,\rightarrow\,q)\vee(q\,\rightarrow\,p)\)
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T
단계		1	1	2

 

모든 논리적 가능성에 대해 참인 명제를 항진(tautology) 또는 항진명제라고 한다.

단순명제 또는 합성명제인 P, Q에 대한 조건문 \(P\,\rightarrow\,Q\)가 항진일 때 이것을 함의(implication) 또는 함의명제라 하고 \(P\,\Rightarrow\,Q\)(P는 Q를 함의한다)와 같이 나타낸다. 예를들어 다음 조건문들은 모두 함의이다.

(1) \(p\,\rightarrow\,p\) 

(2) \(p\vee q\,\rightarrow\,q\vee p\)

(3) \(p\,\rightarrow\,p\vee p\)

(4) \(p\vee q\,\rightarrow\,q\)

수학 또는 논리의 명제 중 참인 것을 정리(theorem), 정리의 타당성 여부를 밝히는 과정을 증명(proof)이라고 한다.

임의의 명제 \(p,\,q\)에 대해 다음이 성립하고 증명은 진리표를 이용한다.

(a) 합의 법칙(law of addition) \(p\,\Rightarrow\,p\wedge q\) 

(b) 단순화법칙(laws of simplification) \(p\vee q\,\Rightarrow\,q,\,p\vee q\,\Rightarrow\,p\)

(c) 논리합의 삼단논법(disjunctive syllogism) \((p\wedge q)\vee\sim q\,\Rightarrow\,q\)     

쌍조건문 \(P\,\leftrightarrow\,Q\)가 항진일 때 P, Q는 동치(equivalent)라 하고 \(P\,\Leftrightarrow\,Q\)로 나타낸다. 즉 P, Q에 대한 모든 논리적 가능성의 각 경우마다 이 두 명제의 진리값이 같으면 그리고 그때에만 \(P\,\Leftrightarrow\,Q\)이다. 

임의의 명제 \(p,\,q\)에 대해 다음이 성립하고 증명은 진리표를 이용한다.

(a) 이중부정법칙(이중부정, law of double negation) \(\sim(\sim p)\equiv p\) 

(b) 교환법칙(commutative laws) \(p\vee q\equiv q\vee p,\,p\wedge q\equiv q\wedge p\)

(c) 멱등법칙(laws of idempotency) \(p\vee p\equiv p,\,p\wedge p\equiv p\)

(d) 대우법칙(대우, contrapositive law) \((p\,\rightarrow\,q)\equiv(\sim q\,\rightarrow\,\sim p)\)

드 모르간의 법칙(De Morgan's law)

임의의 명제 \(p,\,q\)에 대하여 다음이 성립하고 증명은 진리표를 이용한다.

\(\sim(p\wedge q)\equiv\sim p\vee\sim q,\,\sim(p\vee q)\equiv\sim p\wedge\sim q\)   

임의의 명제 \(p,\,q,\,r,\,s\)에 대하여 다음이 성립하고 증명은 진리표를 이용한다.

(a) 결합법칙(associative laws) \((p\vee q)\vee r\equiv p\vee(q\vee r),\,(p\wedge q)\wedge r\equiv p\wedge(q\wedge r)\)

(b) 분배법칙(distributive laws) \(p\vee(q\wedge r)\equiv(p\vee q)\wedge(p\vee r),\,p\wedge(q\vee r)\equiv(p\wedge q)\vee(p\wedge r)\)

(c) 추이법칙(추이율, transitive law) \((p\,\rightarrow\,q)\vee(q\,\rightarrow\,r)\Rightarrow(p\,\rightarrow\,r)\)

(d) 구성적 양도논법(constructive dilemmas)

\((p\,\rightarrow\,q)\vee(r\,\rightarrow\,s)\Rightarrow(p\wedge r\,\rightarrow\,q\wedge s),\,(p\,\rightarrow\,q)\vee(r\,\rightarrow\,s)\Rightarrow\,(p\vee r)\,\rightarrow\,(q\vee s)\)

(e) 파괴적 양도논법(destructive dilemmas)

\((p\,\rightarrow\,q)\vee(r\,\rightarrow\,s)\Rightarrow(\sim q\vee\sim s\,\rightarrow\sim p\vee\sim r),\,(p\,\rightarrow\,q)\vee(r\,\rightarrow\,s)\Rightarrow(\sim q\vee\sim s\,\rightarrow\,\sim p\vee\sim r)\)

(f) 긍정식 삼단논법(modus ponens) \((p\,\rightarrow\,q)\vee p\,\Rightarrow\,q\)

(g) 부정식 삼단논법(modus tollens) \((p\,\rightarrow\,q)\vee\sim q\,\Rightarrow\,\sim p\)

(h) 귀류법(배리법, reductio ad absurdum) \((p\,\rightarrow\,q)\Leftrightarrow(p\vee\sim q\,\rightarrow\,q\vee\sim q)\)

(i) 흡수법칙(absorption laws) \(p\vee(p\wedge q)\equiv p,\,p\wedge(p\vee q)\equiv p\)

모든 논리적 가능성의 각 경우마다 진리값이 거짓인 명제를 모순(항위명제, contradiction)이라고 한다. 예를들어 \(p\vee\sim p\)는 모순이다.

항진명제 \(t\), 모순명제 \(c\), 임의의 명제 \(p\)에 대하여 다음이 성립한다.

(a) \(p\vee t\,\Leftrightarrow\,p\) 

(b) \(p\wedge t\,\Leftrightarrow\,t,\,p\vee c\,\Leftrightarrow\,c\)

(c) \(c\,\Rightarrow\,p,\,p\,\Rightarrow\,t\)

참고자료:

집합론, You-Feng Lin, Shwu-Yeng T. Lin 저, 이흥천 옮김, 경문사

집합론, 한상언, 경문사