6.2 경우별증명

불 _(Boole) 논리 관련 증명 방식

진리표를 이용하여 불 연결자들의 논리를 조사하는 방식은 강력한 기술이 지만 간단한 논증의 타당성을 명제의 모양새만 보고 확인하는 데에만 효율 적이다. 하지만 두 가지의 결정적인 한계가 있다.

첫째, 복함명제의 진리값을 확인하기 위해 다루어야 하는 단순명제의 수 가 증가하면, 진리표의 크기는 폭발적으로 커진다. 실제로 단순명제의 개수 가 n 이라면 다루어야 하는 경우의 수, 즉 진리표에서의 행의 수는 2ⁿ가 된 다. 즉, 다루어야 할 경우의 수가 지수함수적으로 증가한다. 따라서 경우에 따라 계산량이 많아 실용적이지 못하게 된다.

둘째, 불 연결자로 구성된 명제 해석에만 쓸 수 있으며, 다른 종류의 논 리적 해석으로의 확장이 불가능하다. 즉, 항진적 결과인지만 확인할 수 있 으며 다른 종류의 논리에 의존하는 논증은 다룰 수 없다.

이와같은 한계때문에 진리값 이상을 다룰 수 있는 방법이 필요하며, 이 를 위해증명을 사용하는 방법을 소개한다. 증명은 타당한 추론규칙들을 적 용하여 논증의 타당성을 보이는 것을 말한다. 진리표를 이용하여 보일 수 없는 타당성을 증명 방법을 이용하면 보일 수 있다. 이번 장에서는 각각의 불 연산자에 해당하는 타당한 추론규칙을 소개한다. 특히 경우별증명 추론

66

비정형증명에 사용되는 타당한 추론규칙 67

규칙과 간접증명 추론규칙의 의미와 사용법을 다룬다.

증명은 방식에 정형증명과 비정형증명이 있으며, 여기서는 비정형증명 을 다루고 다음 장에서 정형증명을 다룬다.

6.1 비정형증명에 사용되는 타당한 추론규칙

Q라는 결론이 P라는 전제의 논리적결과라는 사실을 비정형증명 방식으로 보이고자 할 때 상대가 누구인가에 따라 위 논증의 타당성을 입증하는 증명 방식이 달라진다.

먼저 위 논증의 타당함을 이미 서로 알고 있다면 P라는 전제에서 Q라 는결론을 이끌어내는 것은 정당하게 받아들여질 것이다. 반면에 논리 수업 과제를 제출할 경우에는 과제를 평가하는 교수가 논증의 타당성을 모른다 고 가정하고 위 논증의 타당성을 비정형적으로 증명해야 한다. 즉, 과제를 제출하는 학생이 논증의 타당성을 이해하고 또 타당성을 이해하지 못하는 이에게 타당성을 증명할 수 있음을 담당교수에게 설득할 수 있어야 한다.

앞서 이미 비정형증명의 타당한 논리전개를 예를 통해 알아보았다. 만약 에 Q가 논리적 진리라면 우리는 언제든지 Q를 주장할 수 있다. 예를 들어 a = a 또는 P_∨P와 같이 항상 논리적으로 진리인 명제는 증명 과정에서 언제든 사용할 수 있다.

또한 아래 세 가지 추론규칙은 논리적 동일성이나 논리적 진리와는 무 관하지만 그 의미가 너무나 자명하기 때문에 비정형증명에서는 굳이 언급 하지 않고 사용될 수 있다. 첫째, 논리곱 제거규칙 (∧ Elim): P∧Q에서 P를 유추하거나 P_∧Q에서 Q를 유추한다. 둘째, 논리곱 생성규칙 (∧ Intro): P 와Q에서 P_∧Q를 유추한다. 셋째, 논리합 생성규칙 (∨ Intro): P에서 P_∨Q 를 유추하거나 Q에서 P_∨Q를 유추한다. 논리합 생성규칙과 관련해서 생각 해볼 거리가 좀 있다. 예를 들어 Cube(b)를 증명했다고 가정하자. 그러면

Cube(a)_∨Cube(b)_∨Cube(c)가 논리적 결과로 따라온다. 그런데 이 결론이 왜 필요한가 ? b가 정육면체라면 a, b, c 중에 하나는 정육면체라는 당연한 사실을 굳이 반복할 필요가 있을까라는 질문이 들기 때문이다. 논리합 생 성규칙의 유효성을 하지만 조금 뒤에 배우게 될 것이다.

증명을 어떻게 진행할 것인가 ? 비정형증명을 사용하는 이유는 두 가지다.

첫째, 주어진 정보로부터 새로운 정보를 추출해내기 위해서다. 둘째, 새로 이 얻어진 정보를 전달하기 위해서다. 따라서 전달을 제대로 하기 위해서 비정형증명을 제대로 하는 법을 배워야 한다.

잘 작성된 증명은 첫째, 이해하기 쉬워야 한다. 증명을 읽는 독자가 복 잡한 추리 없이 논리 전개를 따라갈 수 있어야 한다. 둘째, 함축적이어야 한다. 증명을 읽는 독자가 논리 전개에서 시간 허비 없이 정보를 많이 얻을 수 있어야 한다.

이 두 기준은 서로 상반되는 성질을 가지고 있다. 즉, 너무 함축적이면 이해하기 어렵고, 너무 이해하기 쉽게 쓰려다 보면 장황하게 된다. 따라서 증명을 읽는 독자층의 숙련도를 고려 하여 적절하게 균형을 맞추는 일이 중 요하다.

6.2 경우별증명

앞서 설명한 추론규칙들은 쉽게 이해할 수 있으면서 비정형증명에서 간단 하게 적용할 수 있는 규칙들이다. 하지만 불 연결자와 관련된 추론규칙에 는 경우별증명과 간접증명이라는 매우 중요한 두 개의 규칙이 더 있다. 본 절에서는 경우별증명을 다루고 간접증명은 다음 절에서 다룬다. 경우별증 명에 해당하는 정형증명에서의 추론규칙은 논리합 제거규칙 (∨ Elim)이다.

경우별증명을 알아보기 위해 먼제 다음 예를 살펴보자.

경우별증명 69

예제 6.1. b^c이 유리수가 되는 두 개의 무리수 b 와 c 가 존재한다.

Proof. b^c이 유리수가 되는 두 개의 무리수 b 와 c 가 존재함을 보이기 위해 p2

p2

라는 숫자를 이용할 것이다. 먼저 이 숫자는 유리수이거나 무리수임 에 주의한다.

만약 p 2

p2

가 유리수이면 b = c = p

2 로 선택하면 원하는 결과는 얻 는다.

반면에 p 2

p2

가 무리수라면 b=p 2

p2

로 c=p

2 로 선택한 후 아래와 b^c 를 계산해보자.

b^c = p 2

p2‹^p2

= p 2⁽

p2·p 2)

= p 2²

= 2

즉, 이 경우에도 b^c는 유리수이다.

결과적으로 p 2

p2

가 유리수이건 무리수이건 b^c이 유리수가 되는 두 개 의 무리수 b 와 c 가 존재한다는 사실을 알게 되었다.

위예제에서 주목해야할 것은 결과가 아니라 결과를 이끌어내는 논거 방 식이다. 논거의 출발점은 우리가 이미 알고 있는 P_∨Q에서 S를 증명해야 하는 목표이다. 그리고 두 가지를 보인다. 하나는P로부터 S가 논리적으로 유추될 수 있음을 증명하는 것이고, 다른 하나는 Q로부터 S가 논리적으로 유추될 수 있음을 증명하는 것이다. P나 Q 중에 하나는 참일 것이므로 S 또한 참일 수밖에 없게 된다.

앞서의 경우별증명에 대한 설명을 일반화하면 다음과 같다. P_{1∨ · · · ∨}P_n 라는 전제에서 결론 S를 논리적으로 유추하려면 n 개의 경우를 다루어야

한다. 즉, P₁에서 S를 증명하고, P₂에서 S를 증명하고, 등등. 만약에 모든 경우에 S를 논리적으로 유추할 수 있다면 전제 P_{1∨ · · · ∨}P_n에서 결론 S를 논리적으로 유추할 수 있다고, 즉 해당 논증이 타당하다고 말할 수 있다.

좀 더 쉬운 예제를 살펴보자.

예제 6.2. Small(c)^는 (Cube(c)_∧Small(c))_∨(Tet(c)_∧Small(c))의 논리적 결과이다.

Proof. 전제가 아래 명제이다.

(Cube(c)_∧Small(c))_∨(Tet(c)_∧Small(c)) 따라서 두 경우를 다루어야 한다.

첫째, Cube(c)_∧Small(c)가 참이라고 가정한다. 그런데 그러면 (논리곱 제거 규칙에 의해) Small(c) 또한 참이다.

둘째, Tet(c)_∧Small(c)가 참이라고 가정한다. 그러면 또한 (논리곱 제거 규칙에 의해) Small(c)_{가 참이된다.}

따라서 모든 경우에 Small(c)_{가 성립한다.}

다음 예제는 논리합 생성규칙 (∨ Elim) 이 왜 필요한가를 잘 설명해준다.

예제 6.3. Max 가 집에 있고 Carl 이 행복하거나 또는 Claire 가 집에 있고 Scruffy 가 행복하다고 가정하자. 즉,

(Home(max)_∧Happy(carl))_∨(Home(claire)_∧Happy(scruffy))

그러면 Carl 또는 Scruffy 가 행복함을 증명하라. 즉, Happy(carl)_∨Happy(scruffy)

경우별증명 71

Proof. 전제가 참이라고 가정하자.

(Home(max)_∧Happy(carl))_∨(Home(claire)_∧Happy(scruffy)) 전제가 논리합의 형태이므로 두 가지 경우가 가능하다.

(Home(max)_∧Happy(carl))

이거나

(Home(claire)_∧Happy(scruffy)). 첫 번째 경우 Happy(carl)이 성립하므로

Happy(carl)_∨Happy(scruffy) 또한 성립한다.

두 번째 경우 Happy(scruffy)가 성립하므로 또한 Happy(carl)_∨Happy(scruffy) 가 성립한다.

두 가지 경우 모두 원하는 결과가 성립하므로 Carl 또는 Scruffy 가 행복 함을 증명하였다.

경우별증명은 일상에서도 매우 유용하게 활용될 수 있다. 다음 예를 살 펴보자.

예제 6.4. 쇼핑하느라 정신이 팔려서 쇼핑센터 앞에 불법주차해 둔 사실을 몇 시간 지나서야 비로소 깨달은 논리학자 부부가 있다고 하자.

남편은 다음과 같은 증명을 들면서 굳이 급하게 주차해둔 차로 돌아갈 필요가 없다고 주장하였다.

증명 : 우리 차에 이미 벌금 딱지가 붙어있거나, 아니면 아직 안 붙어 있겠지. 만약에 딱지가 이미 붙어 있다면 한 차에 두 장 을 떼지는 않지. 따라서 급하게 뛰어 돌아갈 필요가 없어. 그리 고 만약에 몇 시간이 지난 지금까지도 딱지가 떼이지 않았다면 앞으로 몇 분 안에 딱찌를 떼일 가능성은 거의 없지. 그래서 마 찬가지로 지금 뛰어갈 필요는 없어.

이에 대해 부인이 다음과 같은 증명을 들면서 주차해둔 차로 급히 돌아 가야한다고 주장하였다.

증명 : 앞으로 몇 분 이내에 벌금딱지를 받거나, 그렇지 않을 수 있겠지. 만약 몇 분 이내에 딱지를 받는다면, 빨리 뛰어 가면 피할 수 있어서 좋지 그리고 만약에 몇 분 이내에 딱지를 받지 않더라도, 뛰어 가면 운동도 되고 준법정신도 보여줄 수 있어 좋 지 그러니까 빨리 뛰어 가자.

누가 더 논리적인 설득을 하였다고 생각되는가 ?

참고사항 6.5. 경우별증명과 같은 논거는 진리표를 이용해서는 불가능함을 확인할 수 있다. 예를 들어 S가 P_∨Q의 논리적 결과임을 보이기 위해서는 S가 P의 논리적 결과임을 보이고 또한 S가 Q의 논리적 결과도 됨을 보여 야 하기 때문이다.

간접증명 : 모순유도증명 73

6.3 간접증명 : 모순유도증명

증명을 할 때 가장 중요한 수단 중의 하나가 모순유도증명이며 간접증명 또 는 귀류법이라 불리기도 한다.

예를 들어 ¬S가 P₁, . . . ,P_n들로부터의 논리적 결과임을 증명하는 것이 목표라 하자. 이 목표를 달성하기 위한 방법 중의 하나가 다음과 같이 모 순유도증명을 적용하는 것이다. 즉, S가 참이라고 가정할 경우 어떤 모순- 절대 일어날 수 없는 경우-이 발생함을 보이기만 하면 된다. 왜냐하면 이는 S,P₁, . . . ,P_n가 어떤 상황에서라도 동시에 성립할 수 없음을 의미하기 때문 이다. 따라서 P₁, . . . ,P_n가 모두 참이면 S는 절대 참이 될 수 없다.

예제 6.6. Cube(c)_∨Dodec(c)와 Tet(b)의 두 개이 전제로부터 ¬(b=c)가 논리적으로 따라온다.

Proof. 두 전제가 성립한다고 가정하자. ¬(b=c)를 보이기 위해 먼저 (b=c) 라고 가정하자. 이제 이로부터 어떤 모순이 발생함을 보여야 한다. 우선 첫 번째 전제로부터Cube(c)또는 Dodec(c)가 성립함에 주목한다. 만약Cube(c) 가 참이라면Cube(b)도 되어야 하는데 그러면 두번째 전제와 모순이다. 그 리고 만약Dodec(c)가 참이라고 역시나Dodec(b)도 되어야 하는데 또한 두 번째 전제와 모순이다. 따라서 어떤 경우든 항상 모순이 발생하며 따라서 두전제가 모두 참이라면 (b=c)가 절대로 성립할 수 없다.즉, ¬(b=c)가 성 립한다.

예제 6.7. p

2 는 무리수이다.

모순유도증명을 이용하여 p

2 가 무리수임을 보이기 위해서는 두 가지 사실에 주목해야 한다. 첫째, 어떤 유리수도 p/q 형태의 분수로 나타낼 수 있으며 p, q 둘 중 하나는 반드시 홀수이다. 왜냐하면 둘 다 짝수이면 2 로 약분하는 과정을 반복해서 적용하면 원하는 분수를 얻을 수 있기 때문이다.

둘째, 홀수의 제곱은 항상 홀수이다. 따라서 어떤 자연수 n 이 있어서 n²가 짝수이면, n 도 짝수이다. 그리고 n²이 짝수이면 이 수는 4 로 나뉘어지게 된다.

Proof. p

2 가 유리수라고 가정하고 모순을 유도해보자. 우선 앞서 살펴본대 로p

2= p/q 이면서 p 나 q 중에서 최소한 하나는 홀수라고 가정할 수 있다.

이제 양변을 제곱하면, 2= p²/q², 즉 p²= 2q²가 성립한다. 근데 이것은 p² 은 짝수라는 의미이며 따라서 p 도 짝수이다. 그러므로 p²는 4 로 나뉘어진 다. 그러면 2q²도 4 로 나뉘어지고, 따라서 q², q 둘 모두 짝수이다. 그런데 p 와 q 가 모두 짝수라는 사실은 p 나 q 중에서 최소한 하나는 홀수라는 사 실과 모순이다. 결국 p

2 가 유리수라는 가정이 잘못되었다. 따라서 p 2 는 무리수이다.

앞서 살펴본 두 예제에서는 논리역 (¬) 으로 시작하는 명제를 논리적으 로 유도하기 위해 간접증명을 사용하였다. (무리수는 유리수가 아닌 것으 로 정의됨에 주의한다.) 하지만 간접증명이 논리역으로 시작하는 명제에만 적용되는 것은 아니다. 예를 들어 명제S를 증명하기 위해서 먼저 ¬S가 성 립한다고 가정한 후 모순이 발생함을 보이면 ¬¬S가 성립함을 증명한 것이 다. 그런데 ¬¬S와 S가 논리적으로 동일하므로 S를 증명하게 된 것이다.

모순유도증명을 활용하기 위해서는 “모순” 이라는 것이 무엇인지를 이해 해야 한다. 직관적으로 말해서 모순은 어떤 경우에도 참이될 수 없는 주장 이거나 어떤 경우에도 동시에 참이될 수 없는 주장들이 집합이다. 예를 들 어 Q_{와 ¬}Q의 쌍으로 이루어진 집합, Cube(c)와 Tet(c)의 상으로 이루어 진 집합, x < y 와 y < x 의 쌍으로 이루어진 집합, 또는 명제 a ̸= a 등이 모두 모순이며, 경우에 따라 적당한 모순을 찾을 수 있어야 한다.

⊥ 라는 기호가 어떤 모순이 발생했음을 의미로 사용된다. 즉, 논리적으 로 절대로 불가능한 결론이 도출된다거나 또는 동시에 성립할 수 없는 결 론들이 도출되었음을 의미하는 기호로 사용된다.

간접증명 : 모순유도증명 75

명제 S가 논리적으로 절대 불가능하다는 말과 명제 ¬S가 논리적 필연 (진리) 라는 말은 동일한 말이라는 사실에 주목할 필요가 있다. 즉, 어떤 명 제가 논리적 진리라는 것을 증명하였다면 우리는 동시에 그 명제의 부정이 논리적으로 절대 불가능함, 즉 모순을 보인 것이된다. 따라서 만약에 ¬S가 항진명제이면 S는 모순이 된다. 통합진리표를 이용하여 명제들의 집합이 항진적으로 모순임을 보일 수 있다. 즉, P₁,P₂, . . . ,P_n가 TT-모순이라 함은 통합진리표의 모든 행에서 P₁,P₂, . . . ,P_n 중 최소한 한 명제의 최종 진리값 이 거짓 (F) 임을 의미한다. 즉, 전체가 모두 동시에 참이 되는 경우는 없다.

예를 들어, S,¬S가 대표적인 TT-모순이다.

일상에서도 사람들은 종종 어떤 주장을 사실이라고 가정하였을 때 모순 이 발생함을 보이는 방식을 이용해서 원래의 주장이 잘못되었음을 증명하 곤 하는데, 이것이 바로 모순유도증명이다.

판사에게 다음과 같은 변론을 하는 변호사의 예를 통해 일상에서의 모 순유도증명을 살펴보도록 하자.

검찰은 피고가 해장국집 주인을 죽였다고 주장하고 있습니 다. 검찰측 주장이 맞다고 가정합시다. 살해 사건이 오후 5 시 15 분에 일어났다는 검찰측 감식반 증언을 들으셨지요 ? 그런데 5 명의 직장 동료의 증언에 의하면 피고는 4 시 45 분에도 피고인 의 직장인 안산시청에서 일을 하고 있었다는 사실을 아시지요 ? 그렇다면 피고가 직장에서 사건현장으로 30 분 이내에 갈 수 있 었다는 이야기가 됩니다. 그렇지만 교통 상황이 좋아도 35 분 거 리인데, 경찰의 교통 기록에 의하면 마침 그날 그 길이 심하게 막혔습니다. 따라서 피고는 무죄라고 주장합니다.

일상에서의 모순유도증명은 반드시 모순을 유도하는 방식이 아닐 수도 있다. 예를 들어, 하와이로 여름휴가를 떠나고 싶은데 여행비용과 여행을 다 녀왔을 때 처리해야 할 밀린 일들을 떠올리고 나서는 하와이로 여행을 떠

나는 것은 불가능하다는 결론을 내린다면, 이와 같은 유도과정이 바로 간 접증명 방식을 이용한 것이다.

6.4 전제가 모순인 논증

P₁, . . . , P_n의 전제들이 모순이라면, 이런 전제들은 일관성이 없다라고 한다.

일관성이 없는 전제들로 만들어진 논증은 항상 타당하다. 왜냐하면 타당한 논증이라 함은 전제가 모두 참일 때 결론도 참이되는 논증인데 전제들이 일관성이 없다면 전제들이 동시에 참이되는 경우가 존재하지 않게 되기 때 문이다. 따라서 결론이 무엇이건 그 논증은 타당하게 된다. 특히, 전제들로 부터 모순 (⊥) 이 발생한다면 어떤 결론로 논리적으로 이끌어낼 수 있게 된 다. 즉, 일관성이 없는 전제들로부터는 어떤 결론도 논리적으로 유도될 수 있다.

반면에 일관성이 없는 전제들을 갖는 논증은 전제가 전제들이 절대로 동 시에 참일 수 없기 때문에 건전하지 않다. 그리고 그러한 논증은 주요 관심 대상이 아니다. 우리가 논증의 타당성에 관심을 갖는 이유는 궁극적으로는 논증의 결론이 참인지 아닌지를 판단하고자 하기 때문인데, 일관성이 없는 전제들을 갖는 논증의 결론은 참일 수도, 거짓일 수도 있는데 그중 어떤 경 우가 성립하는지 알 수 없기 때문이다.

일반적으로 우리가 다루는 증명 방법으로는 논증의 비건전성을 보일 수 는 없다. 이미 언급한대로 논증의 전제들이 참인지 아닌지는 논리의 관심 사가 아니며, 명제의 참· 거짓은 어떤 세상이 주어져야만 판단할 수 있기 때 문이다. 그럼에도 불구하고 논증의 전제들이 일관적이지 않다는 것은 그 비 록 어떤 전제인지는 모르지만 전제들 중에 하나는 언제나 거짓이 됨을 의 미한다.

전제가 모순인 논증 77

예를 들어 아래의 논증은 타당하다. 경우별증명을 이용하여 전제들로부 터 모순을 유도할 수 있다. 즉, 전제들이 일관적이 않으며 따라서 논증이 타당하다.

Home(max) _∨ Home(claire)

¬Home(max)

¬Home(claire

Home(max) _∧ Happy(carl)

위 논증이 타당하므로결론이 전제들의 논리적 결과이다. 그런데 결론이 옳 다고 믿을 수 있는가 ? 아니다. 결론을 믿을 이유가 전혀 존재하지 않는다.