[수학논리]귀류법, 귀류법의 예, 귀류법은 항상 옳은가?

귀류법歸謬法

 1. 귀류법의 정의

 귀류법이란,「P이면 Q이다」라는 명제에서 그 명제의 결론부분을 부정함으로써 생겨나는 새로운 귀류명제

「P이면 Q가 아니다」에서 생기는 모순을 증명하여 본명제가 참임을 증명하는 방법이다. 

 보통 귀류명제의 모순을 밝히기 위해서, 가정부분에 모순되는 점을 발견하거나 문제에 전제로 제시된 부분과 모순되는 점을 발견하여 귀류명제가 거짓임을 증명하는 경우가 많다.

※「P이면 Q이다」에서 P는 가정, Q는 결론

2. 귀류법의 예

「효용의 합을 최대로 하는 배분이면 팔레트 효율적 분배이다」라는 명제가 참임을 밝히시오.

ⅰ.조건설정

한 시장에서 A, B, C 3명이 존재하고 한 사람이 부담하는 부담액을 Gi, 부담후 남은 금액을 Xi, 공공재의 공급량 
y=GA+GB+Gc라고 한다.

ⅱ.귀류법을 통한 증명

「효용의 합을 최대로 하는 배분이면 팔레트 효율적 분배이다」라는 명제를 증명하여야하므로, 

가정 : 효용의 합을 최대로 하는 배분이면

결론 : 팔레트 효율적 분배이다

이므로, 「효용의 합을 최대로 하는 배분이면 팔레트 효율적 분배이다」라는 본명제의 귀류명제는 「효용의 합을 최대로 하는 배분이면 팔레트 효율적 분배가 아니다」이며 이에대한 모순을 증명하면 된다.

 

따라서,  「효용의 합을 최대로 하는 배분이면 팔레트 효율적 분배가 아니다」라는 귀류명제는 거짓이며 귀류법에 따라 「효용의 합을 최대로 하는 배분이면 팔레트 효율적 분배이다」라는 본명제는 참이다.

3. 귀류법은 항상 옳은가? - 진리표를 통한 귀류법의 해석

 그림1. 진리표

 

(  p  →  q  )    ⇔     [  (  p  ∧ ~q  )  →  c  ]

T   T   T       T             T   F   F       T   F                                                        T   F   F       T              T   T   T       F   F                                                        F   T   T       T              F   F   T       T   F                                                        F   T   F       T              F   F   F       T   F

ⅰ. (  p  →  q  ) 의 해석

→ 이 기호는 'imply'의 뜻을 가진 논리기호입니다. 앞 조건이 뒤 조건을 만족시킨다는 뜻입니다. 즉, p→q의 의미는 'p는 q를 만족시킨다.' 'p이면 q이다.' 가 됩니다. 이 명제의 참 거짓은 p와 q의 참거짓에 따라 다릅니다. p, q모두 참이면 명제 p→q는 참, p는 참 q가 거짓이면 명제 p→q는 거짓. 가정 p가 거짓이면 결론 q의 진위여부에 상관없이 명제 p→q는 항상참입니다.

예를 들어 아래와 같은 명제가 있다고 합시다.

지진이 나면 새들은 먼저 도망간다.(p : 지진이 난다, q : 새들은 먼저 도망간다)

지진이 났지만(p는 참) 새들이 먼저 도망갔다면(q는 참) 위명제는 참

지진이 났지만(p는 참) 새들이 먼저 도망가지 않았다면(q는 거짓) 위명제는 거짓

지진이 나지 않았지만(p는 거짓) 새들이 먼저 도망갔다면(q는 참) 위명제는 참

지진이 나지 않았지만(p는 거짓) 새들이 먼저 도망가지 않았다면(q는 거짓) 위명제는 참

지진이 일어나지 않았다면(가정 p가 거짓), 새들이 도망가던 도망가지 않던 항상 참이므로.

ⅱ. (  p  ∧ ~q  ) 의 해석

∧  이 기호는 'and'의 뜻을 가진 논리기호입니다. 두 조건을 모두 만족한다는 뜻이죠. 예를 들어 p∧q라는 것은 p이고 q, 즉 두 조건 p,q를 모두 만족하는 경우를 말합니다.

 

ⅲ. 논리기호(∧, →) 아래에 있는 T, F의 해석

논리기호(∧, →) 아래에 있는 T, F는 양쪽 조건에 따라 결정됩니다. 예를 들어, p∧q 의 진위여부는 p와 q 에 따라 결정되는데 p,q모두 참(T)이면 p∧q도 참(T)이죠? 그외 p, q 둘 중 하나라도 거짓(F)이면 ∧기호는 두조건을 모두 만족한다는 뜻이므로 p∧q가 거짓(F)이죠? 그 결과를 기호 ∧밑에 나타내는 것입니다. 그래서 p∧q의 결과가 4개입니다. TTT, TFF, FFT, FFF

 

ⅳ. (  p  ∧ ~q  )  →  c 의 해석

귀류법은 결론을 부정하여 가정에 모순됨을 보여 원래의 명제가 참임을 보이는 증명법입니다. 이것을 진리표에 나타내기 위해서 조건 c를 추가합니다. 즉, 명제 p→q에서 결론 부분인 q를 부정해버린 상황을 'p이고 ~q'로 나타낼 수 있겠죠. p∧~q로 표시됩니다. 이제  p∧~q 전체가 가정이 됩니다. 해석하면 p인데 ~q라고 가정하자입니다. 

귀류법이라는 건 결론을 부정했을 때 그에 반하는 반대 논리를 찾아내어 기존 명제가 맞는 것을 증명하는 방법이므로 (  p  ∧ ~q  )  →  c 의 의미는 '(  p  ∧ ~q  ) 일때 어떤 조건에 관해서도 항상 옳다(c)는 것은 거짓이다'라는 얘기를 하고 싶은거죠. 그래서 '어떤 조건에 대해서도 항상 옳다(c)'라는 결론은 항상 F가 됩니다.

(p∧~q)→c

이때, (  p  ∧ ~q  )  →  c에서 →의 진위여부는 ⅰ. (  p  →  q  ) 의 해석에서 설명한 바와 같이 ∧와 c의 진위여부에 따라 결정되는데, 

∧가 참이고 c가 참이면 명제 →는 참

∧가 참이고 c가 거짓이면 명제 →는 거짓

∧가 거짓이고 c가 참이면 명제 →는 참

∧가 거짓이고 c가 거짓이면 명제 →는 참

ⅴ. 전체적인 해석

 논리기호 ⇔(양쪽 화살표)는 양쪽이 동치라는 것입니다. 그래서 양쪽 모두 진위결과가 같으면 기호 ⇔아래로 T(참)로 나타내고 양쪽 진위결과가 다르면 F(거짓)으로 나타냅니다. 문제의 진리표에서 왼쪽 명제 p→q의 진위결과는 기호 →밑에 있는 TFTT이고, 오른쪽 명제 (p∧~q)→c의 진위결과는 기호 →밑에 있는 TFTT이네요. 보니까 진위결과가 같죠? 그래서 두 명제가 동치, 진위결과가 같습니다.

따라서, 귀류법은 항상 옳다.

(출처 : 진위표를 해석하는 부분은 

http://kin.naver.com/qna/detail.nhn?d1id=11&dirId=110403&docId=106770832&qb=6reA66WY67KV7J2AIO2VreyDgQ==&enc=utf8&section=kin&rank=2&search_sort=0&spq=0&pid=STEFBlpySEhsstWbXq4sssssstZ-462742&sid=ny4dI3EJ4r%2BjOU7X4I7e3g%3D%3D

을 개인적으로 부분수정