프로그래머를 위한 논리학 - 1

4 years ago

두번째 글을 열면서

이전 글에서 명제 논리를 위해 필요한 기본적인 정의들과 진리표를 이용한 논증의 건전함 증명에 대해서 알아보았다. 이 글에서는 진리표를 이용한 증명이 언제 어려워지는지(혹은 불가능해지는지)에 대해서 알아보고, 진리표와는 다른 방법이 무엇이 있는지에 대해서 알아볼 것이다.

안내의 글

이 글은 '프로그래머를 위한 논리학' 연작의 두번째 글이다. 필자는 이 글 안에서 첫번째 글에서 언급한 개념을 사용하거나 인용하려고 하고 있으므로, 만일 첫번째 글을 읽지 않은 독자가 있다면 부디 먼저 읽어주기를 바란다.

연작의 목차

명제 논리(영차 논리) 심화 - 0

이걸 언제 다 써? : 진리표의 문제

다음 논증의 건전함을 증명하는 상황을 한 번 생각해보자.

  • ¬P,QR,Q(ST)(RU)((SV)((TV)((¬P)(UV)))){\lnot P},\allowbreak{Q \land R},\allowbreak{Q \to (S \lor T)}\allowbreak\vdash\nobreak{(R \to U)}\allowbreak\to\nobreak({(S \to V)}\allowbreak\to\nobreak({(T \to V)}\allowbreak\to\nobreak({(\lnot P)}\allowbreak\to\nobreak{(U \land V))}))

너무 길어서 읽기도 힘든 논증이다. 이 논증의 진리표를 그리려면 우선 PP, QQ, RR, SS, TT, UU, VV가 참/거짓인 경우를 각각 나눠야 하고, ¬P\lnot P, QRQ \land R, Q(ST)Q \to (S \lor T)(RU)((SV)((TV)((¬P)(UV)))){(R \to U)}\allowbreak\to\nobreak({(S \to V)}\allowbreak\to\nobreak({(T \to V)}\allowbreak\to\nobreak({(\lnot P)}\allowbreak\to\nobreak{(U \land V)})))이 각 경우에 참인지 거짓인지 계산해야 한다. 그러려면 무려 가로줄이 128 줄에 세로줄이 11 줄인 진리표를 그려야하고, 거기에 써야하는 진리값은 총 1508 개에 계산해야하는 진리값만 가로줄당 4 개씩 총 512 개가 된다. 말만 해도 끔찍하지 않은가?

물론 개발자들은

뭐하러 그걸 계산해… 프로그램을 하나 개발해서 전제가 참인 경우를 모두 확인하게 만들면 되는 거 아냐?

라고 생각할 수도 있고, 이게 어느정도 말이 되는 해결책이기도 하다. 진리값 하나당 1 비트(bit)의 저장공간을 차지한다고 하면 지금 생각하고 있는 논증은 512 비트, 즉 64 바이트(byte)를 소비하고 이는 64 비트 정수형이나 배정밀도 부동소수점형(Double-precision floating-point type)의 값 8 개어치밖에 안 된다. 단위식이 두세 개 정도 늘어도 정수 16 개, 32 개에 해당하는 공간이니 감당할 수 있고, 단위식이 수십 개가 되는 상황은 잘 다루지 않을테니 그건 프로그램이 다루지 못하는 한계라고 얘기해버리면 된다.

근데 정말 우리가

단위식이 수십 개가 되는 상황은 잘 다루지 않을

것일까? 다음과 같은 국어 논증을 명제 논리의 논증으로 번역하려고 시도해보자.

  • (전제) 모든 사람은 결국엔 죽는다.
  • (결론) 따라서 (사람 중 한 명인) 철수는 결국엔 죽는다.

각각의 명제를 단위식 PP, QQ로 번역하면 위 논증을 다음과 같이 번역할 수 있다.

  • PQP \vdash Q

흠? 뭔가 이상하다. 국어로 쓰인 논증은 말이 되는 논증인 것 같은데, 번역해보니 건전하지 못한 논증이 나와버렸다. 이건 이상한 번역으로 인해 두 명제가 모두 '결국엔 죽는다'의 지시체를 포함한다는 공통점이 사라졌기 때문이다. 그렇다면 어떻게 위 논증을 제대로 번역할 수 있을까? 한 번 '모든 사람'의 지시체를 풀어서 써 보자.

  • (전제) 철수는 결국엔 죽는다.
  • (전제) 영희는 결국엔 죽는다.
  • (전제) 명주는 결국엔 죽는다.
  • (전제) 호경은 결국엔 죽는다.
  • (전제) …
  • (결론) 철수는 결국엔 죽는다.

각각의 전제를 단위식 PChulSooP_{ChulSoo}와 같은 식으로 번역하면, 다음과 같은 논증을 얻는다.

  • PChulSoo,PYeongHui,PMyeongJoo,PHoGyeong,PChulSooP_{ChulSoo},\allowbreak P_{YeongHui},\allowbreak P_{MyeongJoo},\allowbreak P_{HoGyeong},\allowbreak\ldots\allowbreak\allowbreak\vdash\nobreak P_{ChulSoo}

이제 논증이 건전한 것 같다! 정말 그런지 증명하기 위해 이 논증에 해당하는 진리표를 쓰려고 해 보자. 현재 지구에 살아있는 모든 사람으로 '모든 사람'이라는 표현의 지시체를 한정하더라도 이 논증은 적어도 70억 개의 전제를 가지고 있고, 따라서 우리는 27,000,000,0002^{7,000,000,000} 줄의 가로줄을 나열(혹은 프로그램을 쓸 경우, 계산)해야한다. 이 우주의 모든 원자 수가 22662^{266} 개보다도 적으니 각 원자당 가로줄 한 개를 쓸 수 있다고 하더라도 우주가 26,999,999,7442^{6,999,999,744} 개는 있어야 이 진리표를 쓸 수 있다. 이 말인 즉슨 단순히 진리표를 사용하는 방법으로는 이 논증이 건전한지 아닌지를 현실적으로 증명할 수 없다는 것이다. (물론 지금의 예시에서 이 사단을 일으킨 가장 궁극적인 원인은 '모든'이라는 표현이다. 이런 표현을 제대로 다루는 방법은 이후 술어 논리(일차 논리)에서 다룰 것이다.) 물론 이건 약간 극단적인 예시이지만, 이 정도까지는 아니더라도 수십/수백 개의 전제를 가진 상황은 얼마든지 맞닥뜨릴 수 있다. 그리고 아마 독자들도 이런 상황에서는 진리표를 쓰는 것이 쉽지 않다는 것을 이제 이해했으리라 믿는다. 그렇다면 이런 생각을 하는 독자도 있을지 모르겠다.

논리학이라며… 그러면 이런 노가다말고 좀 더 막 수식쓰고 수학적이고 논리적인 그런 방법이 있을 거 아냐? 그런 거 없어?

다행인지 불행인지 그런 방법이 있다. 뿐만이 아니라 앞으로 더 복잡한 논리(술어 논리(일차 논리)나 고차 논리, 양상 논리 등)를 다루기 위해서는 그런 방법을 알아야만 한다. 그렇다면 어쩔 도리가 없으니 대체 무슨 방법인지 한 번 살펴나 보자.

논증 퍼즐 맞추기 : 공리와 추론 규칙

진리표를 사용하지 않는 새로운 방식은 우리가 일상에서 무언가를 논리적으로 따질 때 쓰는 방식과 비슷하다. 이 방법을 한 번 좀 더 일상적인 방식으로 묘사해보자. 우리가 다음과 같은 논증이 건전하다는 걸 증명하고 싶다고 해 보자.

  • 만일 철수가 게임기를 가지고 있다면 철수는 하루종일 게임을 한다.
  • 만일 철수가 하루종일 게임을 한다면 철수의 논리학 성적은 10점이 떨어질 것이다.
  • 따라서 만일 철수가 게임기를 가지고 있다면 철수의 논리학 성적은 10점이 떨어질 것이다.

이 논증의 건전함을 보이기 위해서 사람들은 아마도 다음과 같이 생각할 것이다.

  1. 철수가 게임기를 가지고 있다고 해보자.
  2. 그러면 첫번째 전제가 말하는 대로 철수는 하루종일 게임을 할 것이다.
  3. 그러면 두번째 전제가 말하는 대로 철수의 논리학 성적은 10점이 떨어질 것이다.
  4. 앞의 세 단계를 통해 철수가 게임기를 가지고 있다면 철수의 논리학 성적이 10점 떨어진다는 것을 보였다.
  5. 따라서 위 논증은 건전하다.

논증에서 앞으로 사용하려는 좀 더 수학적인 방식은 이런 생각의 흐름을 좀 더 체계화한 것일 뿐이다. 한번 위 논증을 다음과 같이 번역한 뒤에 좀 더 체계적으로 증명해 보도록 하자.

  • PQ,QRPR{P \to Q},\allowbreak{Q \to R}\allowbreak\vdash\nobreak{P \to R}

그러면 다음과 같은 연역 과정(Deduction process)을 따를 수 있다.

  1. PQP \to Q를 가정한다.
  2. QRQ \to R를 가정한다.
  3. PP를 가정한다.
  4. 3 번의 결론(PP)에 의해 1 번의 결론(PQP \to Q)의 조건이 만족되므로 QQ가 참이다. (1, 3 번을 전제로 한 결론)
  5. 4 번의 결론(QQ)에 의해 2 번의 결론(QRQ \to R)의 조건이 만족되므로 RR이 참이다. (1, 2, 3 번을 전제로 한 결론)
  6. 5 번의 결론은 1, 2, 3 번의 전제를 가정해야 유도할 수 있다. 여기서 3 번의 전제를 조건으로 바꾸어 PRP \to R을 얻는다. (1, 2 번을 전제로 한 결론)
  7. 6 번의 전제와 결론에 따라서 PQ,QRPR{P \to Q},\allowbreak{Q \to R}\allowbreak\vdash\nobreak{P \to R}이 건전하다.

여기서 처음의 두 단계는 일상적인 생각의 흐름에서는 보통 생략되며, 위의 연역 과정을 좀 더 엄밀하게 만들기 위해 추가된 것일 뿐이다. 이후의 단계는 생각의 흐름의 각 단계에 거의 그대로 대응된다.

그렇다면 이런 방식을 쓰기 위해서는 무슨 도구가 필요할까? 여기서 '공리(Axiom)'와 '추론 규칙(Inference rule)'이라는 두 도구가 등장한다. 각각이 무엇인지 한번 알아보자.

먼저, 공리란 너무 당연하기에 우리가 참으로 받아들일 명제를 말한다. 이를테면

  • PPP \to P
    (PP이면 PP이다)
  • P(¬P)P \lor (\lnot P)
    (PP이거나 PP가 아니다)

등을 들 수 있겠다.

이어서, 추론 규칙이란 이미 알고있는 하나 이상의 논증을 사용해서 새로운 논증을 추론(Infer)해내는 규칙들을 말한다. 여기서 새롭게 만들어진 논증은 이미 알고있는 논증이 모두 건전하다면 당연히 건전하다고 받아들일 수 있는 논증이어야 한다. 이를테면

  •   PQ    PQ  \begin{gathered} \;P \vdash Q\;\\ \hline \;\vdash P \to Q\; \end{gathered}
    (PP를 전제로 QQ를 건전하게 이끌어낼 수 있다는 걸 안다면, 전제없이 PQP \to Q를 건전하게 이끌어낼 수 있다는 것도 안다.)
  •   P        Q    PQ  \begin{gathered} \;\vdash P\; \;\; \;\vdash Q\;\\ \hline \;\vdash P \land Q\; \end{gathered}
    (PPQQ를 각각 전제 없이 건전하게 이끌어낼 수 있다는 걸 안다면, PQP \land Q를 건전하게 이끌어낼 수 있다는 것도 안다.)

등을 들 수 있겠다. 여기서 가로줄 위에 있는 논증이 이미 알고있는 논증이고, 가로줄 밑에 있는 논증이 새롭게 만들어진 논증이다.

앞서서 공리와 추론 규칙을 설명할 때 '당연하다'라는 표현을 썼다. 그러면 우리가 당연하게 생각하는 아무 명제/규칙이나 다 공리/추론 규칙으로 사용해서 논증의 건전함을 보여도 괜찮을까? 안타깝게도 그렇지는 않다. 우리가 당연하다고 생각하는 명제 중에서도 서로 모순을 일으키는 명제가 있을 수 있고, 우리가 당연하다고 생각하는 규칙도 비슷한 문제를 일으킬 수 있다. 이런 식으로 모순이 발생하는 것을 피하기 위해서는 공리와 추론 규칙을 세심히 선택하고 선택된 공리와 추론 규칙만을 잘 사용해서 논증의 건전함을 보여야 한다.

이 글과 글에서는 널리 사용되는 세심히 선택된 공리와 추론 규칙의 모음을 몇 소개하고 사용해 볼 것이다. 이렇게 선택된 공리와 추론 규칙들을 모아놓은 것을 논리 체계라고 부른다. 바로 다음 절에서 가장 쉽고 유명한 논리 체계를 먼저 알아볼 것이고, 다음 글에서 약간 난해한 논리 체계에 대해서도 한번 다뤄볼 것이다.

자연스럽게 논증의 건전함 증명하기 : 고전 자연 연역 체계

이 글에서는 '고전 자연 연역 체계' 혹은 간단히 '자연 연역 체계'라고 불리는 논리 체계를 소개하려고 한다. 왜 이 체계를 소개하는가? 이유는 단순하다. 고전 자연 연역 체계가 다른 체계에 비해서 이해하기에도 사용하기에도 쉽기 때문이다. 이는 다음의 두 특징 때문이다.

  1. 고전 자연 연역 체계에는 공리가 아예 없다.
  2. 고전 자연 연역 체계는 그 이름대로 자연스럽다고 할 만한 추론 규칙만 포함한다.

그럼 이 자연스러운 추론 규칙에 대해 이야기해 보자.

고전 자연 연역 체계의 추론 규칙 - 0

자연 연역 체계는 다음 14 개의 추론 규칙을 가진다.

  1. 전제 규칙 (prepre 규칙)
  2. \to 추가 규칙 (I\to_{I} 규칙)
  3. \to 제거 규칙 (E\to_{E} 규칙)
  4. \land 추가 규칙 (I\land_{I} 규칙)
  5. \land 제거 규칙 1번 (E1\land_{E1} 규칙)
  6. \land 제거 규칙 2번 (E2\land_{E2} 규칙)
  7. \lor 추가 규칙 1번 (I1\lor_{I1} 규칙)
  8. \lor 추가 규칙 2번 (I2\lor_{I2} 규칙)
  9. \lor 제거 규칙 (E\lor_{E} 규칙)
  10. ¬\lnot 추가 규칙 (¬I\lnot_{I} 규칙)
  11. ¬\lnot 제거 규칙 (¬E\lnot_{E} 규칙)
  12. 이중 ¬\lnot 제거 규칙 (¬¬E\lnot\lnot_{E} 규칙)
  13. \leftrightarrow 추가 규칙 (I\leftrightarrow_{I} 규칙)
  14. \leftrightarrow 제거 규칙 (E\leftrightarrow_{E} 규칙)

어떤 독자들이 이름을 보고 이미 예상하고 있을 것처럼, 대부분의 규칙은 어떤 논리연산자를 논증에 추가하거나 논증에서 제거하는 방법에 대해서만 다루는 간단한 규칙이다. 그러면 1 번 규칙부터 차례대로 알아보자.

고전 자연 연역 체계의 추론 규칙 - 1

이 절에서는 위 목록의 1 번부터 6 번까지에 해당하는 규칙을 자세히 설명할 것이다. 이렇게 일부만 따로 자세히 소개하는 것은 (추론 규칙은 당연한 추론에 대해 다루는 규칙이므로) 모든 규칙을 자세히 설명하는 것은 필자에게도 독자에게도 지루한 일이 될 것이라고 생각하기 때문이다. 1~6 번의 규칙을 이해하고 나면 나머지 규칙은 규칙의 모양과 사용 예시 정도만 보아도 독자 여러분들이 받아들일 수 있으리라 믿는다.

가장 처음 소개할 추론 규칙은 전제 규칙이다. 이 규칙은 다른 체계에서도 매우 중요한 규칙 중 하나이기도 하다. 우선 이 규칙과 비슷한 생각의 흐름을 살펴보자.

  1. 철수가 잔다고 가정하자. 그러면 철수가 잔다.

이런 생각은 일부러 써놓기에도 이상할 정도로 당연해보인다. 약간 연역 과정답게 바꾸면

  1. PPP \vdash P는 건전하다.

가 되고, 이 과정 또한 당연한 것으로 보인다. 이제 이 당연한 과정을 추론 규칙의 형식에 맞춰 쓰면

  •   PP  \begin{gathered} \hline \;P \vdash P\; \end{gathered}

를 얻는다. 즉, 알고 있는 논증이 아무것도 없는 상황일지라도 PPP \vdash P가 건전한 논증이라는 사실을 우리가 당연히 받아들인다는 이야기이다. 위 추론 규칙을 좀 더 일반적으로 변형하면 우리가 '전제 규칙'(혹은 'prepre 규칙')이라고 부르는 규칙을 얻는다.

  •   Γ,PP  \begin{gathered} \hline \;\Gamma, P \vdash P\; \end{gathered}

여기서 Γ\GammaPP를 제외한 다른 전제들 모두를 뭉뚱그려 표기하기 위한 기호이다. (이후에도 Γ\GammaΔ\Delta를 이런 방식으로 사용할 것이므로 기억해두면 좋다.) Γ\Gamma가 왜 추가되었는지를 다시 생각의 흐름으로 예시를 들어보자.

  1. 영희가 잔다고 가정하자. 또 철수가 잔다고 가정하자. 그러면 철수가 잔다.

Γ\Gamma가 다른 아무 전제('영희가 잔다')를 모두 포함하므로, 여전히 위의 추론 규칙을 사용해서 위 생각에 대응되는 논증(Q,PPQ, P \vdash P)이 건전하다는 걸 증명할 수 있다.

이어서 소개할 추론 규칙은 \to를 추가하기 위한 규칙이다. 마찬가지로 생각의 흐름에 해당하는 예시를 먼저 살펴보자.

  1. 호준이 앉아 있다고 가정하자. 그러면 설미가 화장실에 간다.
  2. 따라서 호준이 앉아 있다면 설미가 화장실에 간다.

같은 말을 반복하는 것 같기도 하고 위의 전제 규칙과도 구분이 잘 안 되는 것 같다. 조금 더 엄밀하게 보기 위해서 연역 과정답게 바꿔보자.

  1. PQP \vdash Q가 건전하다.
  2. 그렇다면 PQ\vdash P \to Q가 건전하다.

즉 우리가 PP를 전제로 QQ를 이끌어 낼 수 있다는 걸 안다면, 전제 없이 PQP \to Q를 이끌어 낼 수 있다는 걸 받아들인다는 이야기이다. 이걸 추론 규칙의 형식으로 쓰면

  •   Γ,PQ    ΓPQ  \begin{gathered} \;\Gamma, P \vdash Q\;\\ \hline \;\Gamma \vdash P \to Q\; \end{gathered}

를 얻는다. 이 규칙이 우리가 '\to 추가 규칙'(혹은 'I\to_{I} 규칙')이라고 부르는 규칙이다. 이렇게 추가한 \to를 다시 논증으로부터 없애고 싶다면 어떻게 해야할까? 역시 자연스럽게 생각하는 방식부터 보도록 하자.

  1. 준기가 밥을 먹는다면 준기는 식탁에 앉아있다.
  2. 준기는 밥을 먹는다.
  3. 따라서 준기는 식탁에 앉아있다.

이를 조금 더 엄밀하게 바꾸면

  1. PQ\vdash P \to Q가 건전하다.
  2. P\vdash P가 건전하다.
  3. 따라서 Q\vdash Q가 건전하다.

PQP \to Q를 이끌어낼 수 있다고도, 또 PP를 이끌어낼 수 있다고도 알고 있다면, QQ도 이끌어낼 수 있다고 받아들인다는 것이다. 이 역시 추론 규칙의 형식으로 쓰면

  •   ΓPQ        ΔP    Γ,ΔQ  \begin{gathered} \;\Gamma \vdash P \to Q\; \;\; \;\Delta \vdash P\;\\ \hline \;\Gamma, \Delta \vdash Q\; \end{gathered}

가 된다. 이 규칙은 '\to 제거 규칙'(혹은 'E\to_{E} 규칙')이라고 부른다.

이제 \land에 대한 규칙으로 넘어가자. \land를 추가하기 위한 규칙의 예시를 생각의 흐름으로 표현하면 다음과 같다.

  1. 미예가 자고 있다.
  2. 수영은 책을 읽고 있다.
  3. 그렇다면 미예는 자고 있고 수영은 책을 읽고 있다.

역시 당연한 흐름인 것 같다. 연역 과정답게 바꾸면

  1. P\vdash P이 건전하다.
  2. Q\vdash Q이 건전하다.
  3. 그렇다면 PQ\vdash P \land Q이 건전하다.

이 된다. 이걸 다음과 같이 일반화해서 추론 규칙의 형식에 맞춰 쓰면 '\land 추가 규칙'이라고 부르는 규칙을 얻는다.

  •   ΓP        ΔQ    Γ,ΔPQ  \begin{gathered} \;\Gamma \vdash P\; \;\; \;\Delta \vdash Q\;\\ \hline \;\Gamma, \Delta \vdash P \land Q\; \end{gathered}

그러면 \land를 제거하려면 어떻게 해야할까? 마찬가지로 예시부터 보도록 하자.

  1. 미예는 자고 있고 수영은 책을 읽고 있다.
  2. 그렇다면 미예는 자고 있다.

바로 일반화된 추론 규칙으로 옮겨 쓰면 다음과 같이 \land 제거 규칙 1번을 얻는다.

  •   ΓPQ    ΓP  \begin{gathered} \;\Gamma \vdash P \land Q\;\\ \hline \;\Gamma \vdash P\; \end{gathered}

이 규칙은 PQP \land Q에서 PP를 이끌어내는 규칙이다. PQP \land Q에서 QQ를 이끌어내도록 바꿔쓰기만 하면 다음의 \land 제거 규칙 2번도 만들 수 있다.

  •   ΓPQ    ΓQ  \begin{gathered} \;\Gamma \vdash P \land Q\;\\ \hline \;\Gamma \vdash Q\; \end{gathered}

여기까지 6 개의 규칙들에 대해서 지루하게 알아보았으니, 규칙을 한번 사용해보도록 하자. 이 절에서 알아본 규칙들로 증명하려고 하는 것은 다음 논증의 건전함이다.

  • (PQ)(QP)\vdash (P \land Q) \to (Q \land P)

무슨 말인가하면 '문주가 화장실에 가고 또 구승이 의자에 앉아있다면 구승이 의자에 앉아있고 문주가 화장실에 간다'가 가리키는 명제처럼, '\land' 혹은 '그리고'가 가리키는 논리연산자는 좌/우에 오는 항들(혹은 앞/뒤에 오는 항들)의 순서를 따지지 않는다는 얘기이다. 이 논증의 건전함을 보이기위해서 다음과 같이 추론 규칙을 사용할 수 있다. (우측 괄호 안에 사용된 추론 규칙을 써 놓았다.)

  1. PQPQP \land Q \vdash P \land Q (pre)
  2. PQPP \land Q \vdash P (1번에 E1\land_{E1})
  3. PQQP \land Q \vdash Q (1번에 E2\land_{E2})
  4. PQQPP \land Q \vdash Q \land P (2, 3번에 I\land_{I})
  5. (PQ)(QP)\vdash (P \land Q) \to (Q \land P) (4번에서 PQP \land Q에 대해 I\to_{I})

위 단계를 약간 풀어쓰면 다음과 같은 연역 과정으로 쓸 수 있다.

  1. PQP \land Q를 가정하자.
  2. 1번에서부터 PP를 얻는다. (1번 가정)
  3. 1번에서부터 QQ를 얻는다. (1번 가정)
  4. 2, 3번에서부터 QPQ \land P를 얻는다. (1번 가정)
  5. 4번의 가정을 조건으로 바꿔서 (PQ)(QP)(P \land Q) \to (Q \land P)를 얻는다.
  6. 5번에 의해 (PQ)(QP)\vdash (P \land Q) \to (Q \land P)가 건전하다.

여기서 전제 규칙과 \to 추가 규칙이 사용되는 방식을 유심히 봐 두도록 하자. 이어질 연습문제를 포함해 앞으로 건전함을 증명할 대부분의 논증들이 이 두 규칙을 이런 방식으로 사용하기 때문이다. 다른 논증을 통해서 이 방식을 한번 더 살펴보도록 하자.

  • P(PP)\vdash P \to (P \land P)

이번 논증은 '철민이 잔다면 철민은 자고 철민은 잔다'가 가리키는 명제처럼 \land를 무의미하게 반복하는 것이 괜찮다는 걸 보여주는 논증이다. 이 논증의 건전함은 다음과 같이 보일 수 있다.

  1. PPP \vdash P (pre)
  2. PPPP \vdash P \land P (1번과 1번에 I\land_{I})
  3. P(PP)\vdash P \to (P \land P) (2번에서 PP에 대해 I\to_{I})

이 단계들도 한 번 풀어서 써 보자.

  1. PP를 가정하자.
  2. 1번과 1번에서부터 PPP \land P를 얻는다. (1번 가정)
  3. 2번의 가정을 조건으로 바꿔서 P(PP)P \to (P \land P)를 얻는다.
  4. 3번에 의해 P(PP)\vdash P \to (P \land P)가 건전하다.

아마 이해를 할듯 말듯한 독자들이 꽤 있으리라 생각한다. 그렇다면 다음의 연습문제를 풀면서 감을 잡아보도록 하자.

자연 연역 체계 연습문제 - 1

이 문제들에는 모두 여러 답이 있을 수가 있다. 본인이 푼 결과가 해답과 다르다고 반드시 틀린 것은 아니니, 다른 결과를 얻었을 경우에는 자신의 풀이가 맞는지 곰곰히 생각해보도록 하자. 만일 그래도 올바른지 모를 경우에는 해답을 댓글에 남기면 필자가 확인해보도록 하겠다.

  1. PP\vdash P \to P가 건전함을 증명해보자.

    답 보기
    1. PPP \vdash P (pre)
    2. PP\vdash P \to P (1번에 I\to_{I})
  2. P(QP)\vdash P \to (Q \to P)가 건전함을 증명해보자.

    답 보기
    1. P,QPP, Q \vdash P (pre)
    2. PQPP \vdash Q \to P (1번에서 QQ에 대해 I\to_{I})
    3. P(QP)\vdash P \to (Q \to P) (2번에서 PP에 대해 I\to_{I})
  3. (P(QR))R\vdash (P \land (Q \land R)) \to R가 건전함을 증명해보자.

    답 보기
    1. P(QR)P(QR)P \land (Q \land R) \vdash P \land (Q \land R) (pre)
    2. P(QR)QRP \land (Q \land R) \vdash Q \land R (1번에 E2\land_{E2})
    3. P(QR)RP \land (Q \land R) \vdash R (2번에 E2\land_{E2})
    4. (P(QR))R\vdash (P \land (Q \land R)) \to R (3번에서 P(QR)P \land (Q \land R)에 대해 I\to_{I})
  4. (P(PQ))Q\vdash (P \land (P \to Q)) \to Q가 건전함을 증명해보자.

    답 보기
    1. P(PQ)P(PQ)P \land (P \to Q) \vdash P \land (P \to Q) (pre)
    2. P(PQ)PP \land (P \to Q) \vdash P (1번에 E1\land_{E1})
    3. P(PQ)PQP \land (P \to Q) \vdash P \to Q (1번에 E2\land_{E2})
    4. P(PQ)QP \land (P \to Q) \vdash Q (2, 3번에 E\to_{E})
    5. (P(PQ))Q\vdash (P \land (P \to Q)) \to Q (4번에서 P(PQ)P \land (P \to Q)에 대해 I\to_{I})
  5. ((PR)(PQ))(QR)\vdash ((P \to R) \land (P \land Q)) \to (Q \land R)가 건전함을 증명해보자.

    답 보기
    1. (PR)(PQ)(PR)(PQ)(P \to R) \land (P \land Q) \vdash (P \to R) \land (P \land Q) (pre)
    2. (PR)(PQ)PQ(P \to R) \land (P \land Q) \vdash P \land Q (1번에 E2\land_{E2})
    3. (PR)(PQ)Q(P \to R) \land (P \land Q) \vdash Q (2번에 E2\land_{E2})
    4. (PR)(PQ)P(P \to R) \land (P \land Q) \vdash P (2번에 E1\land_{E1})
    5. (PR)(PQ)PR(P \to R) \land (P \land Q) \vdash P \to R (1번에 E1\land_{E1})
    6. (PR)(PQ)R(P \to R) \land (P \land Q) \vdash R (4, 5번에 E\to_{E})
    7. (PR)(PQ)QR(P \to R) \land (P \land Q) \vdash Q \land R (3, 6번에 I\land_{I})
    8. ((PR)(PQ))(QR)\vdash ((P \to R) \land (P \land Q)) \to (Q \land R) (7번에서 (PR)(PQ)(P \to R) \land (P \land Q)에 대해 I\to_{I})
  6. (PQ)((QR)(PR))\vdash (P \to Q) \to ((Q \to R) \to (P \to R))가 건전함을 증명해보자.

    답 보기
    1. PQPQP \to Q \vdash P \to Q (pre)
    2. QRQRQ \to R \vdash Q \to R (pre)
    3. PPP \vdash P (pre)
    4. PQ,PQP \to Q, P \vdash Q (1, 3번에 E\to_{E})
    5. PQ,QR,PRP \to Q, Q \to R, P \vdash R (2, 4번에 E\to_{E})
    6. PQ,QRPRP \to Q, Q \to R \vdash P \to R (5번에서 PP에 대해 I\to_{I})
    7. PQ(QR)(PR)P \to Q \vdash (Q \to R) \to (P \to R) (6번에서 QRQ \to R에 대해 I\to_{I})
    8. (PQ)((QR)(PR))\vdash (P \to Q) \to ((Q \to R) \to (P \to R)) (7번에서 PQP \to Q에 대해 I\to_{I})

고전 자연 연역 체계의 추론 규칙 - 2

이번 절에서는 나머지 추론 규칙들을 소개하도록 하겠다. 우선 \lor을 위한 규칙이다.

  • \lor 추가 규칙 1번 (I1\lor_{I1})
      ΓP    ΓPQ  \begin{gathered} \;\Gamma \vdash P\;\\ \hline \;\Gamma \vdash P \lor Q\; \end{gathered}
  • \lor 추가 규칙 2번 (I2\lor_{I2})
      ΓQ    ΓPQ  \begin{gathered} \;\Gamma \vdash Q\;\\ \hline \;\Gamma \vdash P \lor Q\; \end{gathered}
  • \lor 제거 규칙 (E\lor_{E})
      ΓPQ        Δ0,PR        Δ1,QR    Γ,Δ0,Δ1R  \begin{gathered} \;\Gamma \vdash P \lor Q\; \;\; \;\Delta_0, P \vdash R\; \;\; \;\Delta_1, Q \vdash R\;\\ \hline \;\Gamma, \Delta_0, \Delta_1 \vdash R\; \end{gathered}

이 규칙들은 PP를 이끌어낼 수 있거나 QQ를 이끌어낼 수 있을 때에만 PP 또는 QQ를 이끌어낼 수 있다는 것, 그리고 PPQQ로부터 동일한 결론 RR에 도달할 수 있을 때에만 PP 또는 QQ에서 RR에 도달할 수 있다는 것을 설명하는 규칙들이다.

그 다음 소개할 추론 규칙은 ¬\lnot을 위한 규칙이다.

  • ¬\lnot 추가 규칙 (¬I\lnot_{I})
      Γ,PQ        Δ,P¬Q    Γ,Δ¬P  \begin{gathered} \;\Gamma, P \vdash Q\; \;\; \;\Delta, P \vdash \lnot Q\;\\ \hline \;\Gamma, \Delta \vdash \lnot P\; \end{gathered}
  • ¬\lnot 제거 규칙 (¬E\lnot_{E})
      ΓP        Δ¬P    Γ,ΔQ  \begin{gathered} \;\Gamma \vdash P\; \;\; \;\Delta \vdash \lnot P\;\\ \hline \;\Gamma, \Delta \vdash Q\; \end{gathered}
  • 이중 ¬\lnot 제거 규칙 (¬¬E\lnot\lnot_{E})
      Γ¬¬P    ΓP  \begin{gathered} \;\Gamma \vdash \lnot\lnot P\;\\ \hline \;\Gamma \vdash P\; \end{gathered}

첫번째 규칙은 PP를 전제로 삼아서 QQ 그리고 (QQ와 모순되는) ¬Q\lnot Q를 모두 이끌어낼 수 있을 때, ¬P\lnot P를 이끌어낼 수 있다는 규칙이다. 다시 말해 PP를 전제로 삼으면 모순이 발생할 때, PP가 거짓임을 이끌어내는 것이다. 두번째 규칙은 PPPP가 아니란 사실을 이끌어낼 수 있다면 아무런 명제(QQ)나 이끌어낼 수 있다는 것이다. 이 규칙은 지난 글에서 설명했단 \to의 진리값 규칙과 연관된다. 지난 글을 읽으면서

PQP \to QPP가 거짓이거나 QQ가 참일 때에는 참이고, PP가 참이면서 QQ가 거짓이면 거짓이다.

라는 규칙에 의문을 품은 사람은 ¬E\lnot_{E} 규칙의 뜻이 헷갈릴 수 있다. 이는 이 진리값 규칙과 ¬E\lnot_E 규칙이 비슷한 생각을 요구하는 규칙이기 때문이다. 그 경우에는 이전 글에서 언급했던 것처럼 댓글로 질문을 남겨주기를 바란다. 필자가 최대한 답변할 수 있도록 노력하겠다. 마지막 규칙은 ¬\lnot이 두 개가 연달아 있을 때, 즉 PP가 아닌 것이 아닌 때에는 PP가 참이라는 규칙이다. 이 규칙 또한 굉장히 중요한 규칙 중 하나이고, 많은 증명에서 사용된다.

\leftrightarrow을 추가하고 제거하기 위한 규칙 역시 존재한다. 역시 간략화된 규칙을 먼저 보자.

  • \leftrightarrow 추가 규칙 (I\leftrightarrow_{I})
      Γ(PQ)(QP)    Γ,ΔPQ  \begin{gathered} \;\Gamma \vdash (P \to Q) \land (Q \to P)\;\\ \hline \;\Gamma, \Delta \vdash P \leftrightarrow Q\; \end{gathered}
  • \leftrightarrow 제거 규칙 (E\leftrightarrow_{E})
      ΓPQ    Γ(PQ)(QP)  \begin{gathered} \;\Gamma \vdash P \leftrightarrow Q\;\\ \hline \;\Gamma \vdash (P \to Q) \land (Q \to P)\; \end{gathered}

이 규칙들은 PQP \leftrightarrow Q(PQ)(QP)(P \to Q) \land (Q \to P)로 해석하는 규칙들이라고 이해하면 된다.

지금까지 고전 자연 연역 체계의 추론 규칙에 대해서 알아보았다. 이제 이 추론 규칙들을 사용해보도록 하자. 첫번째 예시는 다음과 같다.

  • (PQ)(QP)\vdash (P \lor Q) \to (Q \lor P)

아까 살펴본 \land가 좌/우를 따지지 않는다는 명제의 \lor 버전을 위한 논증이다. 한번 증명해보자.

  1. PPP \vdash P (pre)
  2. PQPP \vdash Q \lor P (1번에 I2\lor_{I2})
  3. QQQ \vdash Q (pre)
  4. QQPQ \vdash Q \lor P (1번에 I1\lor_{I1})
  5. PQPQP \lor Q \vdash P \lor Q (pre)
  6. PQQPP \lor Q \vdash Q \lor P (2, 4, 5번에 E\lor_{E})
  7. (PQ)(QP)\vdash (P \lor Q) \to (Q \lor P) (6번에서 PQP \lor Q에 대해 I\to_{I})

이 증명을 조건에 있는 E\lor_{E} 규칙을 활용하는 방식에 주의해서 살펴보도록 하자. E\lor_{E} 규칙을 사용하기 위해서는 \lor의 각 경우에 해당하는 증명을 각각 해야한다는 것이 요점이다. 다른 예시를 통해서 복습해보도록 하자.

  • (PP)P\vdash (P \lor P) \to P

이 논증의 건전함은 다음과 같이 증명할 수 있다.

  1. PPP \vdash P (pre)
  2. PPPPP \lor P \vdash P \lor P (pre)
  3. PPPP \lor P \vdash P (1번과 1번, 그리고 2번에 E\lor_{E})
  4. (PP)P\vdash (P \lor P) \to P (3번에서 PPP \lor P에 대해 I\to_{I})

위 논증에서는 E\lor_{E} 규칙을 사용하기 위해 필요한 \lor의 두 경우에 대한 논증을 모두 1번에서 얻었다는 점에 유의하자. 이어서 이번에는 \lor을 포함한 (증명하기에) 조금 어려운 논증이다.

  • ((PQ)(PQ))Q\vdash ((P \lor Q) \land (P \to Q)) \to Q

이 논증의 건전함은 이렇게 보인다.

  1. PPP \vdash P (pre)
  2. PQPQP \to Q \vdash P \to Q (pre)
  3. P,PQQP, P \to Q \vdash Q (1, 2번에 E\to_{E})
  4. P(PQ)QP \vdash (P \to Q) \to Q (3번에서 PQP \to Q에 대해 I\to_{I})
  5. QQQ \vdash Q (pre)
  6. (PQ)(PQ)(PQ)(PQ)(P \lor Q) \land (P \to Q) \vdash (P \lor Q) \land (P \to Q) (pre)
  7. (PQ)(PQ)PQ(P \lor Q) \land (P \to Q) \vdash P \to Q (6번에 E2\land_{E2})
  8. (PQ)(PQ),PQ(P \lor Q) \land (P \to Q), P \vdash Q (4, 7번에 E\to_{E})
  9. (PQ)(PQ)PQ(P \lor Q) \land (P \to Q) \vdash P \lor Q (6번에 E1\land_{E1})
  10. (PQ)(PQ)Q(P \lor Q) \land (P \to Q) \vdash Q (5, 8, 9번에 E\lor_{E})
  11. ((PQ)(PQ))Q\vdash ((P \lor Q) \land (P \to Q)) \to Q (10번에서 (PQ)(PQ)(P \lor Q) \land (P \to Q)에 대해 I\to_{I})

약간 복잡한 과정이기는 하지만 앞서 제시된 연습문제를 풀어본 독자들은 이해할 수 있으리라 믿는다.

이제는 \leftrightarrow를 사용하는 예시를 살펴보자.

  • (P(QR))((PQ)(PR))\vdash (P \lor (Q \land R)) \leftrightarrow ((P \lor Q) \land (P \lor R))

\leftrightarrow를 포함하는 결론을 이끌어내려고 할 때는 \to의 경우와 \leftarrow의 경우, 즉

  • (P(QR))((PQ)(PR))\vdash (P \lor (Q \land R)) \to ((P \lor Q) \land (P \lor R))
  • ((PQ)(PR))(P(QR))\vdash ((P \lor Q) \land (P \lor R)) \to (P \lor (Q \land R))

의 건전함을 모두 증명하면 된다. 우선 첫번째 논증의 건전함부터 증명해보자.

  1. PPP \vdash P (pre)
  2. PPQP \vdash P \lor Q (1번에 I1\lor_{I1})
  3. PPRP \vdash P \lor R (1번에 I1\lor_{I1})
  4. P(PQ)(PR)P \vdash (P \lor Q) \land (P \lor R) (2, 3번에 I\land_{I})
  5. QRQRQ \land R \vdash Q \land R (pre)
  6. QRQQ \land R \vdash Q (5번에 E1\land_{E1})
  7. QRPQQ \land R \vdash P \lor Q (6번에 I2\lor_{I2})
  8. QRRQ \land R \vdash R (5번에 E2\land_{E2})
  9. QRPRQ \land R \vdash P \lor R (8번에 I2\lor_{I2})
  10. QR(PQ)(PR)Q \land R \vdash (P \lor Q) \land (P \lor R) (7, 9번에 I\land_{I})
  11. P(QR)P(QR)P \lor (Q \land R) \vdash P \lor (Q \land R) (pre)
  12. P(QR)(PQ)(PR)P \lor (Q \land R) \vdash (P \lor Q) \land (P \lor R) (4, 10, 11번에 E\lor_{E})
  13. (P(QR))((PQ)(PR))\vdash (P \lor (Q \land R)) \to ((P \lor Q) \land (P \lor R)) (12번에서 P(QR)P \lor (Q \land R)에 대해 I\to_{I})

이제 두번째 논증의 건전함을 증명해보자

  1. PPP \vdash P (pre)
  2. PP(QR)P \vdash P \lor (Q \land R) (1번에 I1\lor_{I1})
  3. QQQ \vdash Q (pre)
  4. RRR \vdash R (pre)
  5. Q,RQRQ, R \vdash Q \land R (3, 4번에 I\land_{I})
  6. Q,RP(QR)Q, R \vdash P \lor (Q \land R) (5번에 I2\lor_{I2})
  7. (PQ)(PR)(PQ)(PR)(P \lor Q) \land (P \lor R) \vdash (P \lor Q) \land (P \lor R) (pre)
  8. (PQ)(PR)PQ(P \lor Q) \land (P \lor R) \vdash P \lor Q (7번에 E1\land_{E1})
  9. (PQ)(PR),RP(QR)(P \lor Q) \land (P \lor R), R \vdash P \lor (Q \land R) (2, 6, 8번에 E\lor_{E})
  10. (PQ)(PR)PR(P \lor Q) \land (P \lor R) \vdash P \lor R (7번에 E2\land_{E2})
  11. (PQ)(PR)P(QR)(P \lor Q) \land (P \lor R) \vdash P \lor (Q \land R) (2, 9, 10번에 E\lor_{E})
  12. (PQ)(PR)(P(QR))\vdash (P \lor Q) \land (P \lor R) \to (P \lor (Q \land R)) (11번에서 (PQ)(PR)(P \lor Q) \land (P \lor R)에 대해 I\to_{I})

이 두 증명을 하나로 합치고 중복되는 PPP \vdash P를 없애면 다음의 기다란 증명이 된다.

  1. PPP \vdash P (pre)
  2. PPQP \vdash P \lor Q (1번에 I1\lor_{I1})
  3. PPRP \vdash P \lor R (1번에 I1\lor_{I1})
  4. P(PQ)(PR)P \vdash (P \lor Q) \land (P \lor R) (2, 3번에 I\land_{I})
  5. QRQRQ \land R \vdash Q \land R (pre)
  6. QRQQ \land R \vdash Q (5번에 E1\land_{E1})
  7. QRPQQ \land R \vdash P \lor Q (6번에 I2\lor_{I2})
  8. QRRQ \land R \vdash R (5번에 E2\land_{E2})
  9. QRPRQ \land R \vdash P \lor R (8번에 I2\lor_{I2})
  10. QR(PQ)(PR)Q \land R \vdash (P \lor Q) \land (P \lor R) (7, 9번에 I\land_{I})
  11. P(QR)P(QR)P \lor (Q \land R) \vdash P \lor (Q \land R) (pre)
  12. P(QR)(PQ)(PR)P \lor (Q \land R) \vdash (P \lor Q) \land (P \lor R) (4, 10, 11번에 E\lor_{E})
  13. (P(QR))((PQ)(PR))\vdash (P \lor (Q \land R)) \to ((P \lor Q) \land (P \lor R)) (12번에서 P(QR)P \lor (Q \land R)에 대해 I\to_{I})
  14. PP(QR)P \vdash P \lor (Q \land R) (1번에 I1\lor_{I1})
  15. QQQ \vdash Q (pre)
  16. RRR \vdash R (pre)
  17. Q,RQRQ, R \vdash Q \land R (15, 16번에 I\land_{I})
  18. Q,RP(QR)Q, R \vdash P \lor (Q \land R) (17번에 I2\lor_{I2})
  19. (PQ)(PR)(PQ)(PR)(P \lor Q) \land (P \lor R) \vdash (P \lor Q) \land (P \lor R) (pre)
  20. (PQ)(PR)PQ(P \lor Q) \land (P \lor R) \vdash P \lor Q (19번에 E1\land_{E1})
  21. (PQ)(PR),RP(QR)(P \lor Q) \land (P \lor R), R \vdash P \lor (Q \land R) (14, 18, 20번에 E\lor_{E})
  22. (PQ)(PR)PR(P \lor Q) \land (P \lor R) \vdash P \lor R (19번에 E2\land_{E2})
  23. (PQ)(PR)P(QR)(P \lor Q) \land (P \lor R) \vdash P \lor (Q \land R) (14, 21, 22번에 E\lor_{E})
  24. (PQ)(PR)(P(QR))\vdash (P \lor Q) \land (P \lor R) \to (P \lor (Q \land R)) (23번에서 (PQ)(PR)(P \lor Q) \land (P \lor R)에 대해 I\to_{I})
  25. ((P(QR))((PQ)(PR)))((PQ)(PR)(P(QR)))\vdash ((P \lor (Q \land R)) \to ((P \lor Q) \land (P \lor R))) \land ((P \lor Q) \land (P \lor R) \to (P \lor (Q \land R))) (13, 24번에 I\land_{I})
  26. (P(QR))((PQ)(PR))\vdash (P \lor (Q \land R)) \leftrightarrow ((P \lor Q) \land (P \lor R)) (25번에 I\leftrightarrow_{I})

엄청난 길이의 증명이다. 그렇지만 앞서의 두 증명을 이해했다면 이 긴 증명은 단순히 두 증명을 합치고 25, 26번 줄을 추가한 것에 지나지 않는다. 마지막으로 ¬\lnot을 사용하는 간단한 논증을 살펴보고, 연습문제로 넘어가도록 하자.

  • ¬(P(¬P))\vdash \lnot (P \land (\lnot P))

이 논증의 결론은 모순율(Law of Contradiction)이라고 불리는 유명한 명제다. 어떤 명제 P가 있을 때 그 P가 참이면서 동시에 거짓일 수는 없다는 걸 말하고 있다. 이 논증의 건전함을 증명해보자.

  1. P(¬P)P(¬P)P \land (\lnot P) \vdash P \land (\lnot P) (pre)
  2. P(¬P)PP \land (\lnot P) \vdash P (1번에 E1\land_{E1})
  3. P(¬P)¬PP \land (\lnot P) \vdash \lnot P (1번에 E2\land_{E2})
  4. ¬(P(¬P))\vdash \lnot (P \land (\lnot P)) (2, 3번에서 PP에 대해 ¬I\lnot_{I})

이제 연습문제를 풀면서 자연 연역 체계를 사용해 추론하는 방법을 손에 익혀보도록 하자.

자연 연역 체계 연습문제 - 2

  1. P(¬(¬P)))\vdash P \to (\lnot (\lnot P)))가 건전함을 증명해보자.

    답 보기
    1. P,¬PPP, \lnot P \vdash P (pre)
    2. P,¬P¬PP, \lnot P \vdash \lnot P (pre)
    3. P¬(¬P)P \vdash \lnot (\lnot P) (1, 2번에 ¬I\lnot_{I})
    4. P(¬(¬P))\vdash P \to (\lnot (\lnot P)) (3번에서 PP에 대해 I\to_{I})
  2. (PQ)((¬Q)(¬P))\vdash (P \to Q) \to ((\lnot Q) \to (\lnot P))가 건전함을 증명해보자.

    답 보기
    1. PQPQP \to Q \vdash P \to Q (pre)
    2. ¬Q¬Q\lnot Q \vdash \lnot Q (pre)
    3. PPP \vdash P (pre)
    4. PQ,PQP \to Q, P \vdash Q (1, 3번에 E\to_{E})
    5. PQ,¬Q,P¬PP \to Q, \lnot Q, P \vdash \lnot P (2, 4번에 ¬E\lnot_{E})
    6. PQ,¬Q¬PP \to Q, \lnot Q \vdash \lnot P (3, 5번에 ¬I\lnot_{I})
    7. PQ(¬Q)(¬P)P \to Q \vdash (\lnot Q) \to (\lnot P) (6번에서 ¬Q\lnot Q에 대해 I\to_{I})
    8. (PQ)((¬Q)(¬P))\vdash (P \to Q) \to ((\lnot Q) \to (\lnot P)) (7번에서 PQP \to Q에 대해 I\to_{I})
  3. ((¬Q)(¬P))(PQ)\vdash ((\lnot Q) \to (\lnot P)) \to (P \to Q)가 건전함을 증명해보자.
    (바로 윗 문제의 결론과 이 문제의 결론을 합쳐서 고등학교에서 '대우'라고 부르는 개념에 대한 법칙을 얻는다.)

    답 보기
    1. (¬Q)(¬P)(¬Q)(¬P)(\lnot Q) \to (\lnot P) \vdash (\lnot Q) \to (\lnot P) (pre)
    2. P,¬QPP, \lnot Q \vdash P (pre)
    3. P,¬Q¬QP, \lnot Q \vdash \lnot Q (pre)
    4. (¬Q)(¬P),P,¬Q¬P(\lnot Q) \to (\lnot P), P, \lnot Q \vdash \lnot P (1, 3번에 E\to_{E})
    5. (¬Q)(¬P),P¬(¬Q)(\lnot Q) \to (\lnot P), P \vdash \lnot (\lnot Q) (2, 4번에 ¬I\lnot_{I})
    6. (¬Q)(¬P),PQ(\lnot Q) \to (\lnot P), P \vdash Q (5번에 ¬¬E\lnot\lnot_{E})
    7. (¬Q)(¬P)PQ(\lnot Q) \to (\lnot P) \vdash P \to Q (6번에서 PP에 대해 I\to_{I})
    8. ((¬Q)(¬P))(PQ)\vdash ((\lnot Q) \to (\lnot P)) \to (P \to Q) (7번에서 (¬Q)(¬P)(\lnot Q) \to (\lnot P)에 대해 I\to_{I})
  4. P(¬P)\vdash P \lor (\lnot P)가 건전함을 증명해보자.
    (이 논증의 결론을 배중률(Law of Excluded Middle)이라고 부른다. 굉장히 중요한 법칙 중 하나이며, 이후의 글에서도 이 법칙을 언급할 것이다.)

    답 보기
    1. ¬(P(¬P))¬(P(¬P))\lnot (P \lor (\lnot P)) \vdash \lnot (P \lor (\lnot P)) (pre)
    2. ¬(P(¬P)),PP\lnot (P \lor (\lnot P)), P \vdash P (pre)
    3. ¬(P(¬P)),PP(¬P)\lnot (P \lor (\lnot P)), P \vdash P \lor (\lnot P) (2번에 I1\lor_{I1})
    4. ¬(P(¬P)),P¬P\lnot (P \lor (\lnot P)), P \vdash \lnot P (1, 3번에 ¬E\lnot_{E})
    5. ¬(P(¬P))¬P\lnot (P \lor (\lnot P)) \vdash \lnot P (2, 4번에 ¬I\lnot_{I})
    6. ¬(P(¬P)),¬P¬P\lnot (P \lor (\lnot P)), \lnot P \vdash \lnot P (pre)
    7. ¬(P(¬P)),¬PP(¬P)\lnot (P \lor (\lnot P)), \lnot P \vdash P \lor (\lnot P) (6번에 I2\lor_{I2})
    8. ¬(P(¬P)),¬PP\lnot (P \lor (\lnot P)), \lnot P \vdash P (1, 7번에 ¬E\lnot_{E})
    9. ¬(P(¬P))¬(¬P)\lnot (P \lor (\lnot P)) \vdash \lnot (\lnot P) (6, 8번에 ¬I\lnot_{I})
    10. ¬(¬(P(¬P)))\vdash \lnot (\lnot (P \lor (\lnot P))) (5, 9번에 ¬I\lnot_{I})
    11. P(¬P)\vdash P \lor (\lnot P) (10번에 ¬¬E\lnot\lnot_{E})
  5. ((¬(¬P))(¬(¬Q)))(¬((¬P)(¬Q)))\vdash ((\lnot (\lnot P)) \land (\lnot (\lnot Q))) \leftrightarrow (\lnot ((\lnot P) \lor (\lnot Q)))가 건전함을 증명해보자.

    답 보기
    1. (¬(¬P))(¬(¬Q))(¬(¬P))(¬(¬Q))(\lnot (\lnot P)) \land (\lnot (\lnot Q)) \vdash (\lnot (\lnot P)) \land (\lnot (\lnot Q)) (pre)
    2. (¬(¬P))(¬(¬Q))¬(¬P)(\lnot (\lnot P)) \land (\lnot (\lnot Q)) \vdash \lnot (\lnot P) (1번에 E1\land_{E1})
    3. ¬P¬P\lnot P \vdash \lnot P (pre)
    4. (¬(¬P))(¬(¬Q)),¬PP(\lnot (\lnot P)) \land (\lnot (\lnot Q)), \lnot P \vdash P (2, 3번에 ¬E\lnot_{E})
    5. (¬(¬P))(¬(¬Q))¬(¬Q)(\lnot (\lnot P)) \land (\lnot (\lnot Q)) \vdash \lnot (\lnot Q) (1번에 E2\land_{E2})
    6. ¬Q¬Q\lnot Q \vdash \lnot Q (pre)
    7. (¬(¬P))(¬(¬Q)),¬QP(\lnot (\lnot P)) \land (\lnot (\lnot Q)), \lnot Q \vdash P (5, 6번에 ¬E\lnot_{E})
    8. (¬P)(¬Q)(¬P)(¬Q)(\lnot P) \lor (\lnot Q) \vdash (\lnot P) \lor (\lnot Q) (pre)
    9. (¬(¬P))(¬(¬Q)),(¬P)(¬Q)P(\lnot (\lnot P)) \land (\lnot (\lnot Q)), (\lnot P) \lor (\lnot Q) \vdash P (4, 7, 8번에 E\lor_{E})
    10. (¬(¬P))(¬(¬Q)),¬Q¬P(\lnot (\lnot P)) \land (\lnot (\lnot Q)), \lnot Q \vdash \lnot P (5, 6번에 ¬E\lnot_{E})
    11. (¬(¬P))(¬(¬Q)),(¬P)(¬Q)¬P(\lnot (\lnot P)) \land (\lnot (\lnot Q)), (\lnot P) \lor (\lnot Q) \vdash \lnot P
      (3, 8, 10번에 E\lor_{E})
    12. (¬(¬P))(¬(¬Q))¬((¬P)(¬Q))(\lnot (\lnot P)) \land (\lnot (\lnot Q)) \vdash \lnot ((\lnot P) \lor (\lnot Q))
      (9, 11번에서 (¬P)(¬Q)(\lnot P) \lor (\lnot Q)에 대해 ¬I\lnot_{I})
    13. ((¬(¬P))(¬(¬Q)))(¬((¬P)(¬Q)))\vdash ((\lnot (\lnot P)) \land (\lnot (\lnot Q))) \to (\lnot ((\lnot P) \lor (\lnot Q)))
      (12번에서 (¬(¬P))(¬(¬Q))(\lnot (\lnot P)) \land (\lnot (\lnot Q))에 대해 I\to_{I})
    14. ¬((¬P)(¬Q))¬((¬P)(¬Q))\lnot ((\lnot P) \lor (\lnot Q)) \vdash \lnot ((\lnot P) \lor (\lnot Q)) (pre)
    15. ¬P(¬P)(¬Q)\lnot P \vdash (\lnot P) \lor (\lnot Q) (3번에 I1\lor_{I1})
    16. ¬((¬P)(¬Q)),¬PP\lnot ((\lnot P) \lor (\lnot Q)), \lnot P \vdash P (14, 15번에 ¬E\lnot_{E})
    17. ¬((¬P)(¬Q))¬(¬P)\lnot ((\lnot P) \lor (\lnot Q)) \vdash \lnot (\lnot P) (3, 16번에 ¬I\lnot_{I})
    18. ¬Q(¬P)(¬Q)\lnot Q \vdash (\lnot P) \lor (\lnot Q) (6번에 I1\lor_{I1})
    19. ¬((¬P)(¬Q)),¬QQ\lnot ((\lnot P) \lor (\lnot Q)), \lnot Q \vdash Q (14, 18번에 ¬E\lnot_{E})
    20. ¬((¬P)(¬Q))¬(¬Q)\lnot ((\lnot P) \lor (\lnot Q)) \vdash \lnot (\lnot Q) (6, 19번에 ¬I\lnot_{I})
    21. ¬((¬P)(¬Q))(¬(¬P))(¬(¬Q))\lnot ((\lnot P) \lor (\lnot Q)) \vdash (\lnot (\lnot P)) \land (\lnot (\lnot Q))
      (17, 20번에 I\land_{I})
    22. (¬((¬P)(¬Q)))((¬(¬P))(¬(¬Q)))\vdash (\lnot ((\lnot P) \lor (\lnot Q))) \to ((\lnot (\lnot P)) \land (\lnot (\lnot Q)))
      (21번에서 ¬((¬P)(¬Q))\lnot ((\lnot P) \lor (\lnot Q))에 대해 I\to_{I})
    23. (((¬(¬P))(¬(¬Q)))(¬((¬P)(¬Q))))((¬((¬P)(¬Q)))((¬(¬P))(¬(¬Q))))\vdash (((\lnot (\lnot P)) \land (\lnot (\lnot Q))) \to (\lnot ((\lnot P) \lor (\lnot Q)))) \land ((\lnot ((\lnot P) \lor (\lnot Q))) \to ((\lnot (\lnot P)) \land (\lnot (\lnot Q))))
      (13, 22번에 I\land_{I})
    24. ((¬(¬P))(¬(¬Q)))(¬((¬P)(¬Q)))\vdash ((\lnot (\lnot P)) \land (\lnot (\lnot Q))) \leftrightarrow (\lnot ((\lnot P) \lor (\lnot Q)))
      (23번에 I\leftrightarrow_{I})
  6. (PQ)(¬((¬P)(¬Q)))\vdash (P \land Q) \leftrightarrow (\lnot ((\lnot P) \lor (\lnot Q)))가 건전함을 증명해보자.
    (이 식은 '드 모르간의 법칙'('De Morgan's laws')이라고 불리는 네 식 중의 하나이다. 고등학교에서 집합론을 배웠던 사람들은 아마 같은 이름의 법칙을 들어본 기억이 있을 것이다.)

    답 보기
    1. PQPQP \land Q \vdash P \land Q (pre)
    2. PQPP \land Q \vdash P (1번에 E1\land_{E1})
    3. ¬P¬P\lnot P \vdash \lnot P (pre)
    4. PQ,¬PPP \land Q, \lnot P \vdash P (2, 3번에 ¬E\lnot_{E})
    5. PQQP \land Q \vdash Q (1번에 E2\land_{E2})
    6. ¬Q¬Q\lnot Q \vdash \lnot Q (pre)
    7. PQ,¬QPP \land Q, \lnot Q \vdash P (5, 6번에 ¬E\lnot_{E})
    8. (¬P)(¬Q)(¬P)(¬Q)(\lnot P) \lor (\lnot Q) \vdash (\lnot P) \lor (\lnot Q) (pre)
    9. PQ,(¬P)(¬Q)PP \land Q, (\lnot P) \lor (\lnot Q) \vdash P (4, 7, 8번에 E\lor_{E})
    10. PQ,¬Q¬PP \land Q, \lnot Q \vdash \lnot P (5, 6번에 ¬E\lnot_{E})
    11. PQ,(¬P)(¬Q)¬PP \land Q, (\lnot P) \lor (\lnot Q) \vdash \lnot P (3, 8, 10번에 E\lor_{E})
    12. PQ¬((¬P)(¬Q))P \land Q \vdash \lnot ((\lnot P) \lor (\lnot Q)) (9, 11번에 ¬E\lnot_{E})
    13. (PQ)(¬((¬P)(¬Q)))\vdash (P \land Q) \to (\lnot ((\lnot P) \lor (\lnot Q))) (12번에서 PQP \land Q에 대해 I\to_{I})
    14. ¬((¬P)(¬Q))¬((¬P)(¬Q))\lnot ((\lnot P) \lor (\lnot Q)) \vdash \lnot ((\lnot P) \lor (\lnot Q)) (pre)
    15. ¬P(¬P)(¬Q)\lnot P \vdash (\lnot P) \lor (\lnot Q) (3번에 I1\lor_{I1})
    16. ¬((¬P)(¬Q)),¬PP\lnot ((\lnot P) \lor (\lnot Q)), \lnot P \vdash P (14, 15번에 ¬E\lnot_{E})
    17. ¬((¬P)(¬Q))¬(¬P)\lnot ((\lnot P) \lor (\lnot Q)) \vdash \lnot (\lnot P) (3, 16번에 ¬I\lnot_{I})
    18. ¬((¬P)(¬Q))P\lnot ((\lnot P) \lor (\lnot Q)) \vdash P (17번에 ¬¬E\lnot\lnot_{E})
    19. ¬Q(¬P)(¬Q)\lnot Q \vdash (\lnot P) \lor (\lnot Q) (6번에 I2\lor_{I2})
    20. ¬((¬P)(¬Q)),¬QQ\lnot ((\lnot P) \lor (\lnot Q)), \lnot Q \vdash Q (14, 19번에 ¬E\lnot_{E})
    21. ¬((¬P)(¬Q))¬(¬Q)\lnot ((\lnot P) \lor (\lnot Q)) \vdash \lnot (\lnot Q) (6, 20번에 ¬I\lnot_{I})
    22. ¬((¬P)(¬Q))Q\lnot ((\lnot P) \lor (\lnot Q)) \vdash Q (21번에 ¬¬E\lnot\lnot_{E})
    23. ¬((¬P)(¬Q))PQ\lnot ((\lnot P) \lor (\lnot Q)) \vdash P \land Q (18, 22번에 I\land_{I})
    24. (¬((¬P)(¬Q)))(PQ)\vdash (\lnot ((\lnot P) \lor (\lnot Q))) \to (P \land Q)
      (23번에서 ¬((¬P)(¬Q))\lnot ((\lnot P) \lor (\lnot Q))에 대해 I\to_{I})
    25. ((PQ)(¬((¬P)(¬Q))))((¬((¬P)(¬Q)))(PQ))\vdash ((P \land Q) \to (\lnot ((\lnot P) \lor (\lnot Q)))) \land ((\lnot ((\lnot P) \lor (\lnot Q))) \to (P \land Q))
      (13, 24번에 I\land_{I})
    26. (PQ)(¬((¬P)(¬Q)))\vdash (P \land Q) \leftrightarrow (\lnot ((\lnot P) \lor (\lnot Q)))
      (25번에 I\leftrightarrow_{I})

두번째 글을 마치며

첫 글을 끝내고서 바로 이 글을 시작했음에도 이 글을 마치기까지 꽤 오랜 시간이 걸렸다. 대략 3달 정도가 걸린 것 같다. 여러가지 이유가 있겠지만 첫째의 이유는 설명해야하는 내용이 다소 어려웠기 때문이다. 첫 글에서 다루던 내용에 비해 난이도가 많이 올라갔고, 어떻게 하면 이 내용을 간단하고 친절하게 설명할 수 있을까 많은 고민을 했다. 이 글을 마치면서도 아직 '설명이 어려운 것 같은데...'라는 생각이 머리를 떠나지 않는다. 그래서 독자 여러분이 의견 공유가 더더욱 절실하다. 어디가 어려운지, (대략적으로) 왜 어려운지에 대해 의견을 공유해준다면 정말 감사하겠다.

다음 글은 고전 자연 연역 체계를 더 간편하게 쓸 몇몇 방법들에 대해서 먼저 알아보고, 고전 자연 연역 체계에 비해 조금 더 난해한 체계에 대해서 알아볼 것이다. 다행히도 여기서 '난해하다'라는 것은 체계를 사용하기가 난해하다는 것이지 체계에 대한 설명이 더 난해해진다는 것은 아니고, 따라서 다음 글이 이 글보다 어렵지는 않을 것이다. 다음 글은 더 빨리 내놓을 수 있기를 바라며 이만 마치도록 하겠다.


Unable to Access Network...
Cannot Load Disqus Comments