[집합론] 2. 초등논리(연역적 추론, 한정규칙, 타당성 밝힘, 수학적 귀납법)

[집합론] 2. 초등논리(연역적 추론, 한정규칙, 타당성 밝힘, 수학적 귀납법)

연역적 추론

논리적 동치와 함의의 타당성을 증명하는 법칙을 추론규칙(Rules of inference)이라고 한다. 

예를 들어 대우 \(p\,\rightarrow\,q\equiv\sim q\,\rightarrow\,\sim p\)를 증명하면 다음과 같다.$$\begin{align*}p\,\rightarrow\,q&\equiv\sim(p\vee\sim q)\\&\equiv\sim(\sim q\vee p)\\&\equiv\sim(\sim q\vee\sim(\sim p))\\&\equiv\sim q\,\rightarrow\,\sim p\end{align*}$$따라서 \(\equiv\)에 관한 추이율에 따라 \(p\,\rightarrow\,q\equiv\sim q\,\rightarrow\,\sim p\)이다.

이 증명법은 연역적 추론(deductive reasoning) 또는 연역적 방법(deductive method)이다. 연역적 추론에서는 그때그때 알려진 공리, 정의, 정리, 추론규칙 등을 활용한다.

다음은 논리합의 삼단논법의 증명이다.$$\begin{align*}(p\wedge q)\vee\sim p&\equiv\sim p\vee(p\wedge q)\\&\equiv(\sim p\vee p)\wedge(\sim p\vee q)\\&\equiv c\wedge(\sim p\vee q)\\&\equiv(\sim p\vee q)\wedge c\\&\equiv\sim p\vee q\\&\Rightarrow q\end{align*}$$그러므로 \(\equiv\)에 대한 추이율에 의해 \((p\wedge q)\vee\sim p\equiv\sim p\vee q\)이고 여기서 \(\sim p\vee q\,\Rightarrow\,q\)이므로 따라서 \((p\wedge q)\vee\sim p\,\Rightarrow\,q\)이다. 

다음은 이출법칙 \((p\vee q)\,\rightarrow\,r\equiv p\,\rightarrow\,(q\,\rightarrow\,r)\)의 증명이다.$$\begin{align*}p\,\rightarrow\,(q\,\rightarrow\,r)&\equiv p\,\rightarrow\,\sim(q\vee\sim r)\\&\equiv\sim[p\vee(q\vee\sim r)]\\&\equiv\sim[(p\vee q)\vee\sim r]\\&\equiv p\vee q\,\rightarrow\,r\end{align*}$$그러므로 \(\equiv\)에 대한 추이율에 의해 \(p\,\rightarrow\,(q\,\rightarrow\,r)\equiv p\vee q\,\rightarrow\,r\)이고 따라서 \(p\vee q\,\rightarrow\,r\equiv p\,\rightarrow\,(q\,\rightarrow\,r)\)이다.

(참고: 임의의 명제 \(P,\,Q\)에 대해 \(P\equiv Q\,\Rightarrow\,Q\equiv P\)가 성립한다)     

다음은 동치명제 \((p\,\rightarrow\,r)\wedge(q\,\rightarrow\,s)\equiv(p\vee q\,\rightarrow\,r\wedge s)\)의 증명이다.$$\begin{align*}(p\,\rightarrow\,r)\wedge(q\,\rightarrow\,s)&\equiv\sim(p\vee\sim r)\wedge\sim(q\vee\sim s)\\&\equiv(\sim p\wedge r)\wedge(\sim q\wedge s)\\&\equiv(\sim p\wedge\sim q)\wedge(r\wedge s)\\&\equiv\sim[(p\vee q)\vee\sim(r\wedge s)]\\&\equiv p\vee q\,\rightarrow\,r\wedge s\end{align*}$$그러므로 \(\equiv\)에 대한 추이율에 의해 \((p\,\rightarrow\,r)\wedge(q\,\rightarrow\,s)\equiv(p\vee q\,\rightarrow\,r\wedge s)\)이다. 

*조건문 \(p\,\rightarrow\,q\)에 대하여 조건문 \(q\,\rightarrow\,p\), \(\sim p\,\rightarrow\,\sim q\), \(\sim q\,\rightarrow\,\sim p\)를 각각 역(converse), 이(reverse), 대우(contrapositive)라고 한다. 이때 다음이 성립한다.$$p\,\rightarrow\,q\equiv\sim q\,\rightarrow\,\sim p,\,q\,\rightarrow\,p\equiv\sim p\,\rightarrow\,\sim q$$

한정규칙

수학에서 전체집합(universal set)은 토론을 진행할 때 미리 염두에 둔 성질을 지닌 것들의 모임이다. 예를들어 명제 "모든 사람은 이 세상을 떠난다"의 전체집합은 인류이다. 여기서 전체집합을 감안할 때 위 명제를 "전체집합의 모든 \(x\)에 대해 \(x\)는 세상을 떠난다"로 나타낼 수 있고, "전체집합의 모든 \(x\)에 대하여"를 전칭기호(universal quantifier)라 하고 \(\forall x\)로 나타낸다. 

"\(x\)는 세상을 떠난다"라는 주장은 \(x\)에 관한 조건을 제시한다. 이것을 기호로 \(p(x)\)로 나타내고 위의 명제를 \(\forall x\,p(x)\)로 나타낼 수 있다.

한편으로 "어떤 사람은 세상을 떠난다"와 같은 명제의 전체집합도 인류이고, 이것을 앞에서처럼 "세상을 떠날 사람이 적어도 한 명 존재한다" 또는 "적어도 하나의 \(x\)가 존재함으로써 세상을 떠난다" 또는 "적어도 하나의 \(x\)가 존재함으로써 \(p(x)\)"로 나타낼 수 있다. 

이 경우 "적어도 하나의 \(x\)가 존재함으로써"를 \(\exists x\)로 나타내고 존재기호(existential quantifier)라고 하며 \(\exists x\,p(x)\)로 나타낸다. 

여기서 \(p(x)\)를 전체집합 \(U\)에서의 명제함수(propositional function)로 보면 참, 거짓은 \(x\in U\)에 따라 결정된다. 

명제함수 \(p(x)\)가 참일때의 \(x\in U\)들의 집합을 \(p(x)\)의 진리집합(truth set)이라 하고 \(\{x\,|\,p(x)\}\)로 나타낸다. 

예를들어 \(U=\{1,\,2,\,3,\,4\}\), \(p(x):\,1\leq|x|\leq4\)에 대하여 \(\{x\,|\,p(x)\}=\{1,\,2,\,3\}\)이다.

\(\forall x\,p(x)\)를 전칭명제(모든 \(x\)에 대한), \(\exists x\,p(x)\)를 특칭명제(적어도 하나의 \(x\in U\)에 대한)라고 하고, 전칭기호 \(\forall x\), 존재기호 \(\exists x\)를 모두 한정기호라고 한다.

예를들어 "\(f(x)=0\), 모든 \(x\)에 대하여"는 "\(\forall x\,f(x)=0\)"을 뜻한다. 

한정기호의 부정규칙(Rules of quantifier negation, 드 모르간 법칙의 일반화)

전체집합 \(U\)의 임의의 원소 \(x\)에 관한 명제함수 \(p(x)\)에 대해 다음이 성립한다.$$\sim\forall x\,p(x)\equiv\exists x\,\sim p(x),\,\sim\exists\,p(x)\equiv\forall x\,\sim p(x)$$명제함수 \(p(x)\)의 진리집합은 유한집합 또는 무한집합이다. 진리집합이 유한집합 \(U=\{a_{1},\,a_{2},\,\cdots,\,a_{n}\}\)일 경우, \(p(a_{1}),\,p(a_{2}),\,\cdots,\,p(a_{n})\)이 모두 참이면 그리고 그때에만 \(\forall x\,p(x)\)는 참이다. 이것은 위의 논리곱이 참이면 그리고 그때에만 \(\forall x\,p(x)\)는 참이고 따라서 \(\forall x\,p(x)\)는 \(p(a_{1})\vee p(a_{2})\vee\cdots\vee p(a_{n})\)을 뜻하고 \(\exists x\,p(x)\)는 \(p(a_{1})\wedge p(a_{2})\wedge\cdots\wedge p(a_{n})\)을 뜻한다.

예를들어 명제 "모든 뱀은 독을 지닌다"에서 모든 뱀의 모임을 전체집합 \(U\)라고 놓고 임의의 원소 \(x\)에 대한 명제함수 "\(x\)는 독을 지닌다"를 \(p(x)\)라 할 때 원명제는 \(\forall x\,p(x)\)이고 부정은 \(\exists x\,p(x)\)(독을 지니지 않은 뱀이 존재한다)이다.

타당성 밝힘

논리학에서 중요한 과제 중 하나는 논증(arguments)을 점검하는 일이다. 논증은 가정(hypothesis) 또는 전제(premises)라 불리는 명제로부터 결론(conclusion)이라고 불리는 명제를 논리적으로 유도화는 과정이다. 여기서 가정들의 논리곱이 결론을 함이하면 그 논증은 타당(valid)한 것으로 간주한다. 다음은 처음 네 명제  \(\text{H}_{1}\,\sim\,\text{H}_{4}\)가 모두 가정이고 마지막 명제가 결론인 논증을 나타낸다.

\(\text{H}_{1}\): 현수가 의학공부를 한다면 부유한 생활을 하게 될 것이다.

\(\text{H}_{2}\): 현수가 예술공부를 한다면 멋진 생애를 보낼 것이다.

\(\text{H}_{3}\): 현수가 부유한 생활 또는 멋진 생애를 보내려면 대학등록금을 낭비해서는 안된다.

\(\text{H}_{4}\): 현수는 대학등록금을 낭비하고 있다. 따라서 현수는 의학과 예술을 공부하지 않는다.

위의 논증에 대한 가정과 결론을 각각 다음과 같은 문자로 나타내면 다음과 같다.

M: 현수는 의학공부를 한다, E: 현수는 부유한 생활을 할 것이다, A: 현수는 예술공부를 한다. L: 현수는 멋진 생애를 보낼 것이다. 

W: 현수는 대학등록금을 낭비한다.

       

위의 것들을 이용하여 \(\text{H}_{1}\,\sim\,H_{4}\)를 다음과 같이 나타낼 수 있다.  

\(\text{H}_{1}:\,M\,\rightarrow\,E\)  

\(\text{H}_{2}:\,A\,\rightarrow\,L\) 

\(\text{H}_{3}:\,(E\wedge L)\,\rightarrow\,\sim W\) 

\(\text{H}_{4}:\,W\)

C. 그러므로(따라서) \(\sim M\vee\sim A\)     

다음은 위의 논증에 대한 타당성을 형식적 과정으로 나타낸 것이다.

1. \(M\,\rightarrow\,E\)(가정) 

2. \(A\,\rightarrow\,L\)(가정)

3. \((E\vee L)\,\rightarrow\,\sim W\)(가정)

4. \(W\)/그러므로 \(\sim M\wedge\sim A\)(가정/결론)

5. \(\sim(\sim W)\)(4에서 이중부정) 

6. \(\sim(E\vee L)\)(3, 5와 부정식 삼단논법)

7. \(\sim E\wedge\sim L\)(6에 대한 드 모르간의 법칙)

8. \(\sim E\)(7에 대한 단순화 법칙)

9. \(\sim L\)(7에 대한 단순화 법칙)

10. \(\sim M\)(1, 8과 부정식 삼단논법)

11. \(\sim A\)(2, 9와 부정식 삼단논법)

12. \(\sim M\wedge\sim A\)(10, 11과 논리곱)

논증의 형식적 밝힘(formal proof of validity)은 논증에서 결론을 이끌어 낼 수 있는 일련의 명제를 가르키며 그 각각은 전제이거나 아니면 앞선 명제로부터 이미 알려진 타당한 논증을 거쳐 유도된 명제이다.

직접증명(direct proof)은 논증의 타당성을 (직접) 밝히는 방법이고, 간접증명(indirect proof)은 논증의 결론의 부정을 하나의 새로운 전제로 세워 주어진 가정에 덧붙여 모순을 이끌어내는 방법이다.

다음의 논증에서

\(p\wedge q\,\rightarrow\,r\)

\(s\,\rightarrow\,p\vee u\)

\(q\wedge s\)/그러므로 \(r\)

간접증명으로 이 논증의 타당성을 밝히면

1. \(p\wedge q\,\rightarrow\,r\)(가정) 

2. \(s\,\rightarrow\,p\vee u\)(가정)

3. \(q\wedge s\)/그러므로 \(r\)(가정/결론)

4. \(\sim r\)(간접증명(결론부정))

5. \(\sim(p\vee q)\)(1, 4와 부정식 삼단논법)

6. \(\sim p\wedge\sim q\)(5에 대한 드 모르간 법칙)

7. \(\sim p\)(6에 대한 단순화 법칙)

8. \(\sim q\)(6에 대한 단순화 법칙)

9. \(s\)(3, 8과 논리합의 삼단논법)

10. \(p\wedge u\)(2, 9와 긍정식 삼단논법)

11. \(p\)(10에 대한 단순화법칙)

12. \(p\wedge\sim p\)(7, 11과 논리곱)->모순이 도출됨

수학적 귀납법 

수학적 귀납법(mathematical induction)은 다음과 같다.

자연수 \(n\)에 관한 명제함수 \(p(n)\)에 대해

(1) \(n=1\)일 때 \(p(1)\)이 참이다. 

(2) 임의의 자연수 \(k\)에 대하여 \(p(k)\,\Rightarrow\,p(k+1)\)

이들 두 가정하에 모든 자연수 \(n\)에 대한 \(p(n)\)은 참이다.

여기서 (2)를 밝히려면 하나의 보조정리로써 "\(n=k\)에 대하여 \(p(k)\)는 참이다"라는 가정하에 "\(p(k+1)\)은 참이다"를 유도해야 한다. 여기서 가정 "\(p(k)\)는 참이다"를 귀납적 가정이라고 한다. 

모든 자연수 \(n\)에 대하여 다음의 등식이 성립한다.$$1+2+\cdots+n=\frac{n(n+1)}{2}$$이것을 다음과 같이 수학적 귀납법으로 증명할 수 있다.

(1) \(n=1\)일 때 \(p(1)\), 즉 이 등식의 좌변은 \(1\), 우변은 \(\displaystyle\frac{1\cdot(1+1)}{2}=1\)이다. 그러므로 \(\displaystyle1=\frac{1\cdot(1+1)}{2}\)이고, 따라서 \(p(1)\)은 참이다. 

(2) \(n=k\)에 대하여 \(p(k)\), 즉 \(\displaystyle 1+2+\cdots+k=\frac{k(k+1)}{2}\)이 참이라고 가정한다. 이 등식의 양변에 \(k+1\)을 더하면$$\begin{align*}1+2+3+\cdots+k+(k+1)&=\frac{k(k+1)}{2}+(k+1)\\&=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}\\&=\frac{(k+1)\{(k+1)+1\}}{2}\end{align*}$$이므로$$1+2+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2}$$이고 그러므로 \(p(k+1)\)은 참이다.

따라서 수학적 귀납법에서의 전제 (1), (2)는 모두 성립하고 임의의 자연수 \(n\)에 관한 등식이 성립한다. 

거듭제곱(power)의 정의는 임의의 자연수 \(n\)에 대하여 \(x^{n+1}=x^{n}\cdot x\)이다. 

자연수 \(n\)과 정수 \(r(r\geq0)\)에 관한 기호 \(C(n,\,r)\)을 다음과 같이 정의한다.$$C(n+1,\,r)=C(n,\,r)+C(n,\,r-1)$$

*참고: \(C(n,\,r)\)은 조합(combination)에 관한 수로 이항계수(binomial coefficients)라고 하고 정식으로 사용되는 기호는 \(\displaystyle\binom{n}{r}\)이다.  

 

정수 \(n,\,r(0\leq r\leq n)\)에 대하여 다음의 등식이 성립한다.(수학적 귀납법으로 증명)$$C(n,\,r)=\frac{n}{r!(n-r)!}$$

이항정리(binomial theorem)

임의의 자연수 \(n\)과 두 문자 \(x,\,y\)에 대하여 다음 등식이 성립한다.$$(x+y)^{n}=C(n,\,0)x^{n}+C(n,\,1)x^{n-1}y+\cdots+C(n,\,r)x^{n-r}y^{r}+\cdots+C(n,\,n)y^{n}$$증명: 수학적 귀납법으로 증명한다.

(i) \(n=1\)일 때$$(x+y)^{1}=x+y=C(1,\,0)x+C(1,\,1)y=x+y$$이므로 \(n=1\)일 때 성립한다.      

(ii) \(n=k\)일 때$$(x+y)^{k}=C(k,\,0)x^{k}+C(k,\,1)x^{k-1}y+\cdots+C(k,\,r)x^{k-r}y^{r}+\cdots+C(k,\,k)y^{k}$$가 성립한다고 가정하자. 

이 등식의 양변에 각각 \(x+y\)를 곱하면$$(x+y)^{k+1}=C(k+1,\,0)x^{k+1}+C(k+1,\,1)x^{(k+1)-1}y+\cdots+C(k+1,\,r)x^{(k+1)-r}y^{r}+\cdots+C(k+1,\,k+1)y^{k+1}$$이다. 그러므로 \(n=k+1\)에 대해서도 성립하고 따라서 수학적 귀납법에 따라 성립한다.

참고자료:

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