논리적 동치

* 다음은 총 50 장으로 구성된 <사고 훈련 과정>의 한 장이다. 다음 사고 훈련 자료를 저자 이상하의 허락 없이 상업적 목적으로 사용하는 것을 금한다. (추론학교 031-422-1977)

 

 

 

사고 훈련 20

- 논리적 동치 -

 

 

일상어에서 어떤 진술을 이중 부정한 것을 긍정하면, 그 진술은 반드시 긍정해야 하는 것일까요? 그렇다고 보기 힘든 경우가 많습니다. 다음 두 진술을 살펴봅시다.

 

• 이 꽃은 노랗다.

• 이 꽃이 노랗지 않은 것은 아니야.

 

첫 번째 진술을 P로 나타내는 경우, 두 번째 진술에서 ￢￢P의 형식을 생각해 볼 수 있습니다. 논리적 연결사의 기능 방식에 대한 정의만을 고려하는 경우, P가 참일 때 ￢￢P도 참이며, 이에 대한 역도 성립합니다. 또한 P가 거짓일 때 ￢￢P도 거짓이며, 이에 대한 역도 성립합니다. 이렇게 항상 동일한 진리치를 갖는 두 진술은 ‘논리적 동치 관계(logical equivalence)’를 맺는다고 합니다.

 

그런데 ‘이 꽃은 노랗다’라는 진술을 긍정하는 모든 사람은 ‘이 꽃이 노랗지 않은 것은 아니다’에 대해서도 긍정할까요? 그렇다고 단정할 수 없습니다. 왜냐하면 두 진술이 내용적으로 동일하다고 보기 힘들기 때문입니다. 내용적으로 동일한 두 진술은 ‘의미적으로 동치 관계(meaningful equivalence)’를 맺는다고 합니다.

 

 

[예제 1] 부정 연결사의 기능 방식에 따라 ‘P가 참일 때 ￢￢P도 참임’을 설명해 본다면?

 

 

[예제 2] 부정 연결사의 기능 방식에 따라 ‘P가 거짓일 때 ￢￢P도 거짓임’을 설명해 본다면?

 

 

 

위에서 살펴보았듯이, ‘논리적 동치’와 ‘의미적 동치’가 반드시 일치하는 것은 아닙니다. 왜냐하면 논리적 동치는 진술의 내용을 무시하고 진리치의 계산 방식에만 근거하는 반면, 의미적 동치는 진술의 내용에 근거하기 때문입니다. 여기서 잊지 말아야 하는 중요한 것이 있습니다.

 

• 두 진술 형식이 논리적 동치라면, 그 두 진술 형식은 항상 동일한 진리치를 갖는다. 다시 말해, 한 진술 형식이 참일 때 다른 진술 형식도 참이며, 이에 대한 역도 성립한다. 또한 한 진술 형식이 거짓일 때 다른 진술 형식도 거짓이어야 하며, 이에 대한 역도 성립한다.

 

• 두 진술의 논리적 동치 관계가 두 진술의 의미적 동치 관계를 보장해주지는 않는다. 즉, 논리적 동치 관계를 맺는 두 진술이 의미적 동치 관계를 맺는다고 볼 수 없는 경우가 있다.

 

‘￢’, ‘∧’, ‘∨’라는 논리적 연결사의 기능 방식에 대한 정의에 따를 때, 다음의 왼쪽과 오른쪽의 두 진술 형식은 항상 논리적 동치입니다.

 

• P, ￢￢P

• ￢(P∧Q), ￢P∨￢Q

• ￢(P∨Q), ￢P∧￢Q

 

P와 ￢￢P가 논리적 동치임은 앞서 살펴보았습니다. ‘￢(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∨￢Q’는 P와 항상 동일한 진리치를 갖습니다. 즉, 그 두 진술 형식은 P와 Q가 참이든 거짓이든 그 어떤 경우에나 논리적 동치 관계를 맺습니다.

 

 

[예제 3] ‘￢(P∨Q)’와 ‘￢P∧￢Q’는 서로 논리적 동치임을 증명해 본다면?

 

 

 

함의 연결사 ‘→’와 관련된 논리적 동치 관계로 다음과 같은 것을 들 수 있습니다.

 

• ￢(P→Q), P∧￢Q

 

‘￢(P→Q)’가 참이라고 해 봅시다. 이때 ‘P→Q’는 거짓이어야 합니다. ‘P→Q’가 거짓인 경우는 ‘P가 참이지만 Q는 거짓인 경우’입니다. ￢Q는 참이 됩니다. 따라서 연접 연결사 ‘∧’에 따라 ‘P∧￢Q’도 참입니다. 이번에는 ‘￢(P→Q)’가 거짓이라고 해 봅시다. 이때 ‘P→Q’는 참이어야 합니다. P가 참이지만 Q는 거짓인 경우를 제외한 모든 경우들에 대해서 ‘P→Q’는 참입니다. P가 참일 때 Q는 참이어야 하므로, ￢Q는 거짓이 됩니다. 이때 ‘P∧￢Q’도 거짓입니다. ‘P→Q’가 참이고 P가 거짓인 경우, Q는 참이거나 거짓입니다. P가 거짓이므로 Q의 진위 여부와 무관하게 ‘P∧￢Q’는 거짓입니다. 따라서 ‘￢(P→Q)’가 거짓이라고 할 때 ‘P∧￢Q’도 거짓입니다.

 

다음 두 진술 형식은 논리적 동치입니다.

 

• P→Q, ￢P∨Q

 

 

 

[예제 4] 다음은 ‘P→Q’와 ‘￢P∨Q’가 논리적 동치임을 증명한 과정입니다. 다음 증명 과정에서 빈 칸에 들어가야 하는 것은?

 

1. ‘P→Q’는 ‘￢￢(P→Q)’와 논리적 동치이다.

2. ‘￢(P→Q)’는 (      A      )와 논리적 동치이다.

3. (       A       )는 ‘￢(￢P∨Q)’와 논리적 동치이다.

4. ‘￢(P→Q)’는 (      B       )와 논리적 동치이다. - 2, 3

5. ‘￢￢(P→Q)’는 ‘￢￢(￢P∨Q)’와 논리적 동치이다.

6. ‘￢￢(￢P∨Q)’는 ‘￢P∨Q’와 논리적 동치이다.

7, ‘￢￢(P→Q)’는 ‘￢P∨Q’와 논리적 동치이다. - 5, 6

8. ‘P→Q’는 ‘￢P∨Q’와 논리적 동치이다. - 1, 7

 

(A)                                            

(B)                                           

 

 

[예제 5] [예제 4]의 증명 과정에서 2와 3을 근거로 4를 이끌어낸 방식, 혹은 5, 6을 근거로 8을 이끌어낸 방식에 반영된 타당한 형식은?

 

① 이중 부정은 긍정 형식

② 단순화 형식

③ 전건 긍정 형식

④ 가언 삼단 논법 형식

⑤ 선언지 첨가 형식

 

 

[예제 6] [예제 5]의 각 선택지에 해당하는 타당한 형식을 써 본다면?

 

 

 

근거와 결론으로 구성된 어떤 주장 C가 있다고 합시다. 근거들을 바탕으로 결론을 부정할 수 없는 경우, C는 내용적으로 타당한 주장입니다. 이때 C를 구성하는 특정 진술을 마음대로 다른 진술로 바꿀 수 없습니다. 오로지 그 진술과 의미적으로 동치인 진술만 그렇게 바꿀 수 있습니다. 한 진술을 그것과 동치인 진술로 바꾸어도, C가 내용적으로 타당하다는 점은 그대로 유지되기 때문입니다.

 

위 생각을 어떤 타당한 형식에 대해 적용해 봅시다. 실례로 <전건 긍정 형식>에 적용해 봅시다.

 

<전건 긍정 형식>

P

P→Q

Q

 

‘P→Q’는 ‘￢P∨Q’와 논리적 동치입니다. ‘P→Q’를 ‘￢P∨Q’와 바꿔치기 하면, 다음 형식을 얻을 수 있습니다.

 

P

￢P∨Q

Q

 

위 형식은 타당합니다. 왜냐하면 P와 ‘￢P∨Q’를 참으로 가정할 때, Q는 참일 수밖에 없기 때문입니다.

 

 

 

[예제 7~9] 다음 글을 읽고 물음에 답해 봅시다.

 

논리적 연결사의 기능 방식에만 국한해 얻어진 타당한 형식들은 진술들이 전제로 주어지는 순서와 무관합니다. 따라서 다음의 두 형식은 동일한 것으로 취급할 수 있습니다.

 

(A)          (B) ￢P∨Q

                        P      

                        Q

 

 

[예제 7] (A)에 들어가야 하는 타당한 형식을 써 본다면?

 

 

[예제 8] (B)는 무슨 형식으로 볼 수 있을까요?

 

① 선언지 제거 형식

② 단순 양도 형식

③ 복합 양도 형식

④ 전건 긍정 형식

⑤ 선언지 첨가 형식

 

 

[예제 9] (B)가 타당한 형식임을 설명해 본다면?

 

 

[예제 10] ‘P→Q’와 ‘￢P∨Q’는 논리적 동치입니다. 이에 근거하여 다음 두 진술 형식이 논리적 동치임을 설명해 본다면?

 

• P→(Q→R), (P∧Q)→R

 

 

[예제 11] 논리적 연결사들의 정의 방식에 따라 다음 두 진술 형식들이 논리적 동치임을 설명해 본다면?

 

• P→(Q∨R), (P→Q)∧(P→R)

• (P∨Q)→R, (P→R)∧(Q→R)

 

 

 

‘P→Q’와 논리적 동치인 것으로 다음을 들 수 있습니다.

 

• ￢Q→￢P

 

‘￢Q→￢P’는 ‘P→Q’의 대우(contrapositive)라고 합니다. 이러한 대우 형식은 수학적 증명에서 많이 사용됩니다. 실례로 임의의 두 자연수 m, n에 대해 다음을 증명한다고 해 봅시다.

 

• (m×n은 홀수이다.)→[(m은 홀수이다.)∧(n은 홀수이다.)]

 

위 수학적 진술을 직접 증명할 수도 있지만, 다음과 같이 그것의 대우를 증명하는 것이 더 편합니다.

 

• (                                                                             )

 

 

[예제 13] 위 글에서 빈 칸 ( )을 채워 본다면?

 

 

[예제 14] 위 글의 빈 칸 ( )에 해당하는 진술은?

 

① 임의의 두 자연수 m, n에 대해, m×n은 홀수인 경우 m과 n 중 적어도 하나는 짝수이다.

② 임의의 두 자연수 m, n에 대해, m과 n 모두 홀수인 경우는 m×n이 홀수인 경우이다.

③ 임의의 두 자연수 m, n에 대해, m과 n 중 하나만 짝수인 경우는 m×n이 짝수인 경우에 대한 필요조건이다.

④ 임의의 두 자연수 m, n에 대해, m과 n 중 적어도 하나가 짝수이면 m×n은 짝수이다.

⑤ 임의의 두 자연수 m, n에 대해, m과 n 모두 짝수인 경우는 m×n이 짝수이기 위한 충분조건이다.

 

 

[예제 15] [예제 14]의 선택지 중 ①이 거짓임을 보여주는 보기를 하나 든다면?

 

 

[예제 16] [예제 14]의 선택지 중 ① 이외에 거짓인 진술은? 그리고 그것이 거짓인 이유를 보기를 들어 설명해 본다면?

 

 

 

‘P→Q’에 대한 역(converse)은 다음과 같이 표현됩니다.

 

• ‘Q→P’

 

‘P→Q’와 그 역인 ‘Q→P’는 논리적 동치 관계를 맺지 않습니다. ‘P→Q’가 거짓일 때 그 역인 ‘Q→P’는 참이 됩니다. (A) 반면에 ‘P→Q’가 참일 때 그 역인 ‘Q→P’는 참일 수도 있고, 거짓일 수도 있습니다.

 

 

[예제 17] (A)에 대한 이유를 설명해 본다면?

 

 

[예제 18] 임의의 자연수 m, n에 대해 다음 조건문의 역을 써 본다면?

 

• (m×n은 홀수이다.)→[(m은 홀수이다.)∧(n은 홀수이다.)]

 

 

[예제 19] 다음은 [예제 18]의 답이 참임을 증명한 과정입니다. 다음 증명 과정에서 빈 칸을 채워 본다면?

 

1. m과 n을 홀수라고 하자.

2. ‘m=2k+1’과 (   )을 만족하는 어떤 자연수 k, k'가 있다. - 1

3. m×n=(   ) - 2

4. (   )은 홀수이다.     

5. m×n은 홀수이다.

 

 

[예제 20] 다음 조건문의 역을 쓰고, 그 역이 참이 아님을 보기를 들어 설명해 본다면?

 

• 임의의 자연수 m, n에 대해, m과 n 모두 짝수이면 m×n도 짝수이다.

 

 

 

임의의 두 진술 P, Q에 대해 ‘상호 함의(mutual implication)’라 부를 수 있는 논리적 연결사 ‘↔’는 다음과 같이 정의됩니다.

 

• ‘P↔Q’는 ‘P→Q’가 참이고 ‘Q→P’가 참일 때 참이다.

 

 

[예제 21] ‘P↔Q’를 다른 논리적 연결사들에 근거해 정의한 것으로 가장 적절한 것은?

 

① (P→Q)∧(Q→R)

② (P→Q)∨(Q→P)

③ (P∧Q)→(P∨R)

④ (￢P→￢Q)∧(￢Q→￢P)

⑤ (P→Q)∧(Q→P)

 

 

 

‘P↔Q’가 참일 때, ‘P→Q’와 ‘Q→P’ 모두 참입니다. 이 경우는 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와 Q는 동시에 동일한 진리치를 가질 수 없습니다. 역시 ￢P와 ￢Q도 동일한 진리치를 가질 수 없기 때문에, ‘￢P↔￢Q’는 거짓입니다. ‘P↔Q’와 ‘￢P↔￢Q’는 P와 Q의 참 거짓 여부와 무관하게 항상 동일한 진리치를 갖는다는 점에서 논리적 동치입니다.

 

 

[예제 22] 다음 도표의 A와 B는 서로 논리적 동치 관계를 맺는 진술 형식들입니다. 도표의 빈 칸을 채워 본다면?

 

A	B
P ￢(P∧Q) ( ) P→Q ￢(P→Q)	(           ) (           ) ￢P∧￢Q ￢P∨Q (           )

 

 

[예제 22]의 도표에 제시된 것 이외에도 다음의 논리적 동치들도 알아두면 좋습니다.

 

• P→Q, ￢Q→￢P

• P→(Q→R), (P∧Q)→R

• P→(Q∨R), (P→Q)∧(P→R)

• (P∨Q)→R, (P→R)∧(Q→R)

• P↔Q, ￢P↔￢Q

 

 

 

논리적 동치 관계를 맺는 두 진술 형식 A와 B는 ‘A↔B’로 나타낼 수 있습니다. 왜냐하면 상호 함의 연결사 ‘↔’의 기능 방식에 따르면, ‘A↔B’는 A와 B가 동일한 진리치를 갖는 경우에 참이기 때문입니다.

 

 

[예제 23] 위 글에 근거해 판단할 때, <보기> 중 잘못된 것을 모두 고른 것은?

 

<보기>

(가) A에는 P, Q, ￢P, P∨Q, P→R 등이 들어갈 수 있군. (나) A에 ‘P→R’이 들어간 경우, B는 ‘￢P→￢R’과 같은 것이 되어야 하는군. (다) ‘￢(￢P∨Q)’는 A에 들어갈 수 없겠군.

 

① (가) ② (나) ③ (다) ④ (가), (다) ⑤ (나), (다)

 

 

 

여기서 우리는 매우 흥미로운 점을 발견할 수 있습니다. A와 B를 임의의 진술 P, Q, R 및 논리적 연결사들로 구성된 진술 형식들이라고 합시다. 이때 A와 B가 논리적 동치 관계를 맺는다면, A와 B를 상호 함의 연결사로 결합한 ‘A↔B’는 A와 B를 구성하는 진술들의 참 거짓 여부와 무관하게 항상 참입니다.

 

논리적 동치인 P와 ￢￢P를 상호 함의 연결사로 결합한 ‘P↔￢￢P’를 살펴봅시다. P가 참일 때 ‘P↔￢￢P’는 참이며, 또한 P가 거짓일 때에도 ‘P↔￢￢P’는 참입니다.

 

• ‘P↔￢￢P’는 P가 참이든 거짓이든 그 어떤 경우에나 항상 참이다.

 

밑줄 친 부분을 ‘P의 참 거짓 여부와 무관하게’로 해석하면 다음을 얻을 수 있습니다.

 

• ‘P↔￢￢P’는 P의 참 거짓 여부와 무관하게 항상 참이다.

 

이번에는 서로 논리적 동치인 ‘￢(P∧Q)’와 ‘￢P∨￢Q’를 상호 함의 연결사로 결합한 ‘￢(P∧Q)↔(￢P∨￢Q)’를 분석해 봅시다. P와 Q 모두 참이든, 모두 거짓이든, 아니면 둘 중 하나만 참이든, 그 어떤 경우에나 ‘￢(P∧Q)’와 ‘￢P∨￢Q’는 항상 동일한 진리치를 갖게 됩니다. 따라서 ‘￢(P∧Q)↔(￢P∨￢Q)’는 P와 Q의 참 거짓 여부와 무관하게 항상 참입니다. 이러한 식으로 생각해 보면, 다음과 같이 일반화된 주장을 얻을 수 있습니다.

 

• 임의의 두 진술 형식을 나타내는 A와 B가 논리적 연결사들의 정의 방식에 따라 논리적 동치 관계를 맺는 경우, ‘A↔B’는 A와 B를 구성하는 것들의 참 거짓 여부와 무관하게 항상 참이다.

 

 

[예제 24] A를 ‘P→(Q→R)’, 그리고 B를 ‘(P∧Q)→R’라고 할 때, 이에 대한 판단으로 잘못된 것은?

 

① A와 B는 참 거짓 판단 가능한 진술들을 나타내는 P, Q, R로 구성된 진술 형식들이군.

② A와 B는 서로 논리적 동치이군.

③ A와 B는 항상 동일한 진리치를 갖는군.

④ ‘A↔B’는 P, Q, R의 참 거짓 여부와 무관하게 항상 참이군.

⑤ ‘A→B’는 P, Q, R의 참 거짓 여부와 무관하게 항상 참이지만, ‘B→A’는 그렇지 않군.

 

 

 

‘P→Q’와 그 대우 형식인 ‘￢Q→￢P’는 서로 논리적 동치입니다. 이때 ‘(P→Q)↔(￢Q→￢P)’는 P와 Q의 참 거짓 여부와 무관하게 항상 참입니다.

 

‘P→Q’의 P와 Q는 경험 등에 근거해 참 또는 거짓으로 판단되는 진술들을 나타냅니다. 실례로 비가 오면 참으로, 그리고 비가 오지 않으면 거짓으로 판단되는 진술 ‘비가 온다’와 같은 진술이 P에 들어갑니다. 또 땅이 축축해지면 참으로, 그리고 땅이 축축해지지 않으면 거짓으로 판단되는 진술 ‘땅이 축축해진다’와 같은 진술이 Q에 들어갑니다. 이때 ‘P→Q’는 ‘비가 오면, 땅이 축축해진다’라는 진술을 나타냅니다. 여기서 P, Q는 경험에 근거해 참 또는 거짓으로 판단되고, ‘P→Q’는 이와 함께 함의 연결사의 정의 방식에 따라 참 또는 거짓으로 판단됩니다.

 

반면에 ‘(P→Q)↔(￢Q→￢P)’는 P와 Q에 들어갈 진술의 참 거짓 여부와 무관하게 항상 참입니다. P와 Q가 어떻게 판단되든, ‘(P→Q)↔(￢Q→￢P)’는 부정 연결사와 함의 연결사의 정의 방식에 따라 항상 참이 되도록 구성되어 있습니다. 이렇게 항상 참인 진술 형식들에 함축된 참을 ‘논리적 참(logical truth)’이라고 하며, 논리적 동치 관계를 맺는 두 진술 형식을 상호 함의 연결사로 결합한 것은 논리적 참인 형식을 대표합니다.

‘논리적 참’이 무엇인지 더 깊게 알려면, ‘진리표(truth tables)’와 ‘동어반복(tautology)’이라는 것을 알아야 합니다. 진리표와 동어반복에 대해서는 이어지는 사고훈련에서 살펴볼 것입니다.