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

들어가며

개발자 생활을 하다보면 한 번쯤 듣게 되는 (혹은 보게 되는) 말이 있다. 바로

좋은 개발자가 되려면 수학(혹은 논리학)을 배워야지!

이다. 물론 필자가 이런 주장에 완전히 동의한다는 말은 아니다. 그러나 누군가 위 주장을 아래와 같이 조금 수정한다면, 필자는 언제 어디서든지 옹호할 생각이 있다.

함수형 개발을 잘 하는 개발자가 되려면 수학(혹은 논리학)을 배워야지!

좀 더 나아가서 필자가 좌우명으로 삼고 싶을 정도로 바꿀 수도 있다.

강한 자료형 언어로 개발을 잘 하려면 수학과 논리학을 배워야지!

그렇다. 필자는 강한 자료형 언어를 사용하는 개발자는 개발을 배우기 전이든 배운 후든 간에 적어도 언젠가는 수학을 그리고 논리학을 배워야한다고 생각한다. 특히 그 언어를 잘 하고 싶다는 생각을 가지고 있다면 더더욱 그래야한다는 의견이다.

이는 강한 자료형 언어의 고급 개념들이 수학 혹은 논리학에서 비롯했거나 십분 이용하고 있다는 점에 근거한다. 그런 언어가 기반하고 있는 자료형 이론자체가 수학에서 비롯되었다는 사실이 그 예시이다. OCaml의 함자(Functor)와 Haskell의 (악명높은) 모나드(Monad) 또한 수학에 이미 존재하는 개념으로부터 그 이름을 따왔을 뿐 아니라 원래 개념과 깊은 관련성을 가지고 있다는 점 역시 빼놓을 수 없으며, C++/Java 사용자가 익숙할 템플릿(Template)/제네릭(Generics)도 수학의 다형 람다 대수(Polymorphic lambda calculus)에 그 뿌리를 두고 있다는 것 또한 특기할만 하다. 이런 복잡한 개념뿐만이 아니라 비교적 간단하고 널리 사용되는 개념 또한 수학 혹은 논리학에서 유래했거나 깊히 관련된 것이 많은데, 자료형 검사(Type checking), 부울 연산(Bool operation)이라던가 재귀(Recursion), 변수의 유효범위(Scope)가 그런 예시이다.

이런 개념 수준의 연관성을 떠나서도 좀 더 실용적인 측면에서 역시 수학과 논리학은 개발에 영향을 미치고 있다. 유명한 C 컴파일러(Compiler) 중 하나인 GCC의 수십 개의 버그(Bug)를 수학과 Coq이라는 증명 보조도구를 사용해 잡아내는가하면, Java의 병렬 메모리 모델(Parallel memory model)이 가지고 있는 문제점을 고쳐 병렬 개발에 대한 개발자들의 이해 방식을 개선하는데에 도움을 주기도 했다.

이렇듯 수학과 논리학은 개발자에게 (적어도 강한 자료형 언어를 사용하는 개발자에게는) 더 깊은 이해와 개발에 대한 통찰을 제공한다. 그러나 안타까운 사실은 국어로 수학과 논리학을, 특히 강한 자료형을 사용하는 프로그래머가 필요로 하는 수학과 논리학을 배우는게 쉬운 일이 아니라는 점이다. 무엇보다 국어로 된 자료의 절대 수가 부족한 것이 제일의 문제이다. 더불어, 그나마 있는 자료도 질이 떨어지거나 업데이트가 이루어지지 않는 등 자잘한 문제가 있는 경우가 태반이다. 이런 상황에서 배우려는 내용 자체의 난이도와는 별개로, 배우는 과정 자체가 편할 리가 만무하다.

이 글은 이러한 현실을 조금이라도 개선하고자하는 의지를 담아 쓰였다. 이 글에 이어지는 글도 같은 정신을 이어 써 나갈 것이다. 이 글을 통해, 그리고 이 글을 읽은 독자 여러분이 앞으로 써 나아갈 글과 말을 통해 국어로 수학과 논리학을 배우는 것이 좀 더 쉬워지기를 바라며 서두를 마치도록 하겠다.

연작의 목차

• 이 글
  • 들어가며
  • 논리학을 시작하기 전에
    • 헷갈리기 쉬운 것을 구분하자! : 사용과 언급
    • 논리학은 무엇을 다루는 것일까? : 명제
  • 명제 논리(영차 논리) 기초
    • 무슨 기호로 논리를 작성할까? : 명제 논리의 문법
    • 아무런 논증이나 논리적일까? : 건전한 논증
    • 참이고 거짓이고 분간이 돼야 말이지… : 명제의 진리값
    • 뭐가 건전한건데? : 논증의 건전함 증명 체계 - 진리표
  • 첫 글을 마치며
• 다음 글
  • 프로그래머를 위한 논리학 - 1
  • [작성중…] 명제 논리(영차 논리) 심화 - 1
  • 술어 논리(일차 논리) 기초
  • 술어 논리(일차 논리) 심화
  • 논리와 프로그래밍
  • 양상 논리 기초
  • 미정…

논리학을 시작하기 전에

이 절에서는 논리학을 위해 필요한 간단한 개념을 다루어 볼 것이다. 사용(Using)과 언급(Mentioning), 그리고 명제와 지시체에 대해서 소개하고, 어떻게 이런 개념이 논리학에 등장하는지 간단한 예시를 들어 설명할 것이다.

헷갈리기 쉬운 것을 구분하자! : 사용과 언급

개념의 사용(Using)과 개념의 언급(Mentioning)은 굉장히 자주 헷갈리는 개념 중 하나지만, 논리학을 할 때에는 반드시 구분해야하는 개념이다. 이 절부터 시작하여 이 글과 이 글에 이어지는 글에서는 모두 개념의 사용과 언급을 구분할 것이기 때문에, 이 둘이 어떻게 다른지, 그리고 왜 구분해야되는지에 대해서 이 절에서 설명하고 넘어가고자 한다.

개념 전반의 사용과 언급에 대해서 처음부터 다루기는 어려우니, 우선 단어(라는 개념)에만 집중해서 둘을 구분해보도록 하자. 다음은 어떤 단어를 사용하는 경우의 예시이다.

• 자연은 아름답다.
• 1과 1을 더하면 2이다.
• 적분은 어렵다.

이어서, 어떤 단어를 언급하는 경우의 예시도 보도록 하자. 보통 언급된 단어는 작은 따옴표(')로 둘러싸 표시한다.

• '아름답다'는 한 단어이다.
• '1'과 '1', '+'에 '='를 합치면 창문이 된다.
• '자연'은 두 음절로 읽힌다.

대략적으로 어떤 차이인지 이해한 독자도 있을 것이다. 좀 더 분명히 설명해보면 사용된 단어는 단어가 가리키는 것을 말하기 위해 사용하는 것이고, 언급된 단어는 그 단어 자체를 말하기 위해서 사용된 것이다. C 나 C++ 등의 개발 언어에서 볼 수 있는 포인터(Pointer)와 비슷한 방식으로 이해할 수 있다. 단어를 단어의 의미를 가리키는 포인터 p로 생각하면, 사용된 단어는 *p를 말하는 것이고, 언급된 단어는 p라는 포인터 자체를 말하는 것이다. 다시 예를 들어

• 그 책은 200 장의 종이로 만들어졌다.

는 '책'이라는 단어를 사용하여 불리는 종이 위에 글씨가 쓰여진 물체 중 하나의 구성이 어떻게 되어있는지 설명하고 있기 때문에 평범하게 말이 되는 문장이지만

• '그 책'은 200 장의 종이로 만들어졌다.

는 '그 책'이라는 두 단어가 200 장의 종이로 만들어졌다는 걸 의미하고, 단어는 종이로 만들어진 것이 아니므로 이상한 문장이 된다. 다시

• 그 책은 두 단어로 되어있다.

는 단어가 두 개밖에 안 쓰여져 있는 무언가 이상한 책에 대한 이야기를 하는 문장이지만

• '그 책'은 두 단어로 되어있다.

는 평범하게 '그 책'이라는 표현이 단어 두 개로 구성되어있다는 이야기이니, 이상할 것 없이 맞는 문장이다.

일반적인 개념의 경우에도 단어와 비슷한 방식으로 이해할 수 있다. 물론 개념을 글로 설명하기 위해서는 항상 단어가 필요하다는 문제 때문에 예시를 설명하기가 좀 더 난해해진다는 것은 어쩔 수 없는 난점이다. 다음의 예시를 보자.

• 자연은 아름답다.

에서 '자연'이라는 단어는 '자연'이 가리키는 개념(자연)을 언급하기 위해서 사용된 것이고,

• '자연'은 두 음절로 읽힌다.

에서 ''자연''이라는 작은 따옴표로 둘러싸인 표현은 '자연'이라는 단어 자체를 언급하기 위해서 사용된 것이다.

이런 구분이 왜 필요한가? 그것은 $P$와 '$P$'를 구분하지 못하면 다음과 같은 설명을 올바르게 받아들일 수 없기 때문이다. (아래 예시의 정확한 뜻을 이해할 필요는 없다. 예시는 예시일 뿐이다.)

• $P$는 참이다.
• '$\to$'는 조건문을 쓰기 위한 기호다.
• $P \land Q$ 는 $P$와 $Q$가 모두 참일 때에만 참이다.
• '$P \lor Q$'는 '$P$'가 가리키는 명제와 '$Q$'가 가리키는 명제 중 하나 이상이 참일 때에만 참인 명제를 쓰는 방법이다.
• $P$가 참이라면 MP 법칙에 의해 $Q$도 참이다.
• MP 규칙은 '$P \vdash P \to Q$' 꼴의 명제로부터 '$P \vdash Q$' 꼴의 명제를 유도하는 규칙이다.

사용/언급 연습문제

1. '1은 수이다.'라는 문장은 '1'을 올바르게 사용하고 있을까?

   답 보기

   올바르게 사용하고 있다. 위 문장에서 '1'이라는 표현은 1이라는 수를 가리키기 위해서 사용되었다.

2. ''1'은 수이다.'라는 문장은 ''1''을 올바르게 사용하고 있을까?

   답 보기

   올바르지 않게 사용하고 있다. 위 문장에서 ''1''이라는 표현은 단어 '1'을 가리키기 위해서 사용되었다. 문장 안에서 언급된 '1'은 수가 아니고 수를 쓰기 위해서 사용하는 숫자(혹은 글자)이다.

3. 다음 문장에서, 사용/언급이 구분되지 않은 단어인 '베토벤'은 사용되고 있는 것일까 아니면 언급되고 있는 것일까? 그리고 올바르게 구분하여 표기하려면 어떻게 표기해야할까?

   '베토벤은 운명 교향곡을 작곡한 사람의 이름이다.'

   답 보기

   올바른 표기는 ''베토벤'은 운명교향곡을 작곡한 사람의 이름이다.'이고, 여기서 '베토벤'은 작곡가 베토벤의 한글로 적힌 이름 '베토벤'을 언급하는 단어이다.

논리학은 무엇을 다루는 것일까? : 명제

모든 학문은 특정한 대상을 다루고 있다. 경제학은 각종 재화의 흐름과 그 흐름을 예측할 이론을 대상으로 삼는다. 물리학은 물리적으로 존재하는 물질이 어떻게 상호작용하는지를 대상으로 삼는다. 컴퓨터 공학은 컴퓨터의 구조와 프로그램의 구조를 그 대상으로 삼는다. 그렇다면 논리학이 다루는 대상은 무엇일까? 바로 명제와 명제를 증명하는 논증이다. 이 절에서는 명제가 무엇인지 다루고, 이후 세부적인 논리학에 대해 다루면서 논증이 어떻게 이루어지는지에 대해서 이야기 할 것이다.

명제란 무엇인가? 명제는 논리학의 역사가 긴 만큼 다양한 정의를 가지고 있기 때문에 한마디로 답하기 쉽지 않은 질문이다. 아리스토텔레스의 정의인 '명제란 자연에서부터 얻어진 것과 그것을 설명하는 서술어의 조합으로 이루어져 있고, 그 조합이 옳거나 틀렸다는 것을 보여주는 문장'부터 시작하여 스토아 학파(Stoicism)의 정의, 고틀롭 프레게(Gottlob Frege)의 정의, 버트런드 러셀(Bertrand Russell)의 정의 등 여러 사람이 다양한 방식으로 명제를 정의해왔다.

이 절에서는 러셀의 정의에 대해서 간략하게 설명하고, 이후 절에서는 이 정의를 채용해 명제를 이해하도록 할 것이다. 러셀의 정의는 프레게가 명제를 설명하기 위해 도입한 뜻(Meaning)과 지시체(Reference) 구분에 기반하고 있다. 그러니 그의 정의를 이해하기 위해서는 개념의 뜻과 지시체에 대해서 먼저 간단히 설명할 필요성이 있을 것이다. 지시체란 개념이 가리키는 대상을 말한다. 예를 들어 '태양'이라는 단어는 '태양'이라고 이름붙은 별을 가리키고 있으므로, '태양'이라는 단어의 지시체는 (지구가 돌고 있는 별인) 태양이다. 여러 개념이 동일한 지시체를 가질 수 있다. 예를 들면

• 운명 교향곡의 작곡자
• 베토벤

의 두 표현은 동일한 지시체를 가진다. 반면, 뜻이란 개념이 지시체를 가리키는 방식을 말한다. 앞서 말한 '운명 교향곡의 작곡자'라는 표현은 베토벤을 지시하기 위해 운명 교향곡을 언급하고 있으며, 운명 교향곡이 누구에게 작곡되었는지 모르고 있는 사람도 지시체가 어떤 일을 했는지 이해할 수 있는 표현이다. 반면에, '베토벤'이라는 표현은 베토벤을 지시하기 위해 본인의 이름 외에 어떤 다른 개념도 언급하고 있지 않으며, '베토벤'이라고 이름붙은 사람이 어떤 이인지 모르는 사람에게 그 지시체가 무슨 일을 했는지 어떤 정보도 주지 않는다.

이 부분이 약간 난해할 수 있기에, 개발자들의 이해를 돕기 위해 개발할 때 사용하는 함수로 비유를 해보겠다. 피보나치 수열(Fibonacci sequence)의 5 번째 항을 계산하는 함수를 만든다고 해보자. 계산 결과 값은 함수를 어떻게 만들든 (올바르게만 만들었다면) 다 똑같을테지만, 계산에 걸리는 시간, 메모리, 구현의 가독성 등 여러가지 측면이 다른 여러 함수를 만들 수 있을 것이다. 여기서 피보나치 수열의 5 번째 항을 지시체(계산된/가리키는 것)라고 생각하면, 각각의 함수가 구현된 방식이 바로 뜻(계산하는/가리키는 방식)이다.

러셀은 프레게의 이런 구분을 비판하면서 명제를 설명하기 위해 뜻 같은 혼란스러운 개념을 도입할 필요가 없다고 주장했다. 프레게는 문장의 지시체는 참/거짓 값이고 문장의 뜻이 명제라고 정의하였지만, 러셀은 문장의 지시체가 바로 명제라고 정의했다. 또한 러셀은 문장이 단어를 모아서 만들어지는 것처럼 명제도 단어의 지시체를 모아서 만들어진다고 생각했다. 러셀의 입장에서 다음 문장

• 지구는 태양을 중심으로 돈다.

는 '지구는 태양을 중심으로 돈다'는 표현을 통해 지구가 태양을 중심으로 돈다는 명제를 가리키고 있는 것이고, 이 명제는 '지구'라는 단어의 지시체인 지구, '태양'이라는 단어의 지시체인 태양, '중심'라는 단어의 지시체인 중심, '돈다'라는 단어의 지시체인 돈다 등으로 구성되어 있는 것이다.

이후의 논의가 러셀의 정의를 기준으로 삼는 것은 러셀의 정의를 사용하면 철학적으로 복잡한 개념을 소개할 필요가 없고, 논리학의 문제에 집중하기 더 용이하기 때문이다. (물론 러셀의 정의도 여러 철학적인 문제를 가지고 있기는 하나, 그 정의 자체의 간결함은 변하지 않기 때문에 철학적인 논의를 너무 깊게해버리는 사태를 피할 수 있으리라 생각한다.)

명제/지시체 연습문제

1. 다음 두 표현은 같은 지시체를 가지고 있을까?

   • 이 글의 원본이 쓰여진 블로그
   • Valhalla of Valkyrie 블로그
   답 보기

   두 표현의 지시체는 같다. 두 표현 모두 https://ailrun.github.io/ko를 가리키고 있기 때문이다.

2. 다음 두 문장은 같은 지시체를 가지고 있을까? (참고: 이 문제는 러셀의 정의에 기초하고 있다.)

   • 회중시계는 하루에 두 번 2시를 가리킨다.
   • 회중시계는 하루에 두 번 8시를 가리킨다.
   답 보기

   두 표현의 지시체는 같지 않다. 첫번째 문장은 '2시'라는 단어를 통해 시계에서 '2'가 써져있는 부분을 가리키고 있으며, 두번째 문장은 '8시'라는 단어를 통해 시계에서 '8'이 써져있는 부분을 가리키고 있다. 두 단어의 지시체가 서로 다르므로, 각각의 단어를 사용하고 있는 각각의 문장의 지시체 역시 서로 다르다.

3. 다음 두 문장은 같은 지시체를 가지고 있을까? (참고: 역시 러셀의 정의를 따르고 있다.)

   • 오후 1시는 정오로부터 3시간 뒤이다.
   • 13시는 정오로부터 3시간 뒤이다.
   답 보기

   두 표현의 지시체는 같다. 첫번째 문장은 '오후 1시'라는 표현을 통해서, 두번째 문장은 '13시'라는 표현을 통해서 정오로부터 1시간이 지난 시간을 가리키고 있다. 두 표현의 지시체가 같으므로, 두 표현 외에는 모든 곳이 같은 두 문장은 서로 같은 지시체를 가진다. 여기의 두 명제는 모두 거짓이지만, 명제가 거짓이냐 아니냐와 두 문장의 지시체가 같은지 다른지는 서로 상관이 없다는 점을 주의해야한다.

영차 논리 - 명제 논리

이제 가장 기본적인 논리부터 시작해 보도록 하자. 명제 논리(Propositional logic) 혹은 영차 논리(0차 논리, Zeroth-order logic)가 우리의 목표이다.(왜 영차 논리라고 부르는 지에 대해서는 일차 논리 및 고차 논리에 대해 다루면서 설명하도록 할 것이다.)

무슨 기호로 논리를 작성할까? : 명제 논리의 문법

명제 논리를 다루기 위해서는 우선 명제 논리에서 사용하는 언어의 문법을 이해해야만 할 것이다. 이 문법에서 가장 기본적인 구조는 단위식(Atomic formula)이다. 단위식은 별개의 언급이 없는 경우 보통 다음과 같이 '$P$'에서부터 시작하는 영문 대문자로 표기한다.

• $P$
• $Q$
• $R$
• ...

또한, 단위식을 조합하여 식(Formula)을 만들기 위해 다음과 같은 (개발자라면 친숙할 수도 있는) 논리 연산을 사용할 수 있다.

• $\lnot$ (…가 아니다, Not)
• $\land$ (… 그리고 …, And)
• $\lor$ (… 또는 …, Or)
• $\to$ (…이면 …, If)
• $\leftrightarrow$ (…이면 그리고 오직 그 때만 …, If and only if)

단위식은 논리연산을 포함하지 않은 문장의 지시체(명제)를 표현하고 식은 논리 연산을 포함한 복잡한 문장의 지시체(명제)를 표현한다. 예를 들어 $P$가 '철수가 잔다'의 지시체 그리고 $Q$가 '철수가 누워있다'의 지시체일 때, 다음의 식

• $P \land Q$

는 '철수가 자고있고 철수가 누워있다'의 지시체를 표현하고 있으며,

• $P \lor Q$

는 '철수가 자고 있거나 철수가 누워있다'의 지시체를 표현하고 있다. (이후의 논의에서는 간결한 표기를 위해 혼란의 여지가 없는 곳에서는 '$P$가 표현하는 명제'대신 '$P$라는 명제' 혹은 그냥 '$P$'라는 다소 엄밀하지 못한 표현을 사용하도록 하겠다. 혹시나 표현으로 인해 이해가 어렵다면 댓글을 남겨주길 바란다.)

논리학에서 명제를 통해서 하고 싶은 것은 바로 논증(Argument)이다. 논증이란 결론(Conclusion)과 전제(Premise)라고 불리는 여러 명제로 구성된 논리학의 개념이다. 논증은 주로 $\vdash$(턴스타일, Turnstile)이라는 기호를 사용해 표기한다. 예를 들면

• $P \vdash Q$

는 '$P$를 전제로 삼았을 때 $Q$가 결론으로 따라나온다'가 언급하고 있는 논증이고,

• $P, Q \land R \vdash S$

는 '$P$와 $Q \land R$을 전제로 삼았을 때 $S$가 결론으로 따라나온다'가 언급하고 있는 논증이다.

문법 연습문제

1. 단위식 $P$가 '영희는 밥을 먹고 있다' 그리고 단위식 $Q$가 '영희는 식탁에 앉아 있다'라는 문장이 나타내는 명제일 때, 다음 명제들을 식으로 나타내보자.

   • 영희는 밥을 먹고 있거나 식탁에 앉아 있다.
   • 영희가 식탁에 앉아 있으면 영희는 밥을 먹고 있다.
   • 영희는 밥을 먹지 않고 있고 식탁에 앉아 있지도 않다.
   • 영희가 식탁에 앉아 있지 않다면 영희는 밥을 먹고 있지 않다.
   • 영희가 식탁에 앉아있을 때 그리고 오직 그 때에만 영희는 식탁에 앉아있다.
   답 보기

   • $P \lor Q$
   • $Q \to P$
   • $(\lnot P) \land (\lnot Q)$
   • $(\lnot Q) \to (\lnot P)$
   • $Q \leftrightarrow Q$

2. 단위식 $P$가 '짜장면에는 춘장이 들어간다' 그리고 단위식 $Q$가 '탕수육에는 돼지고기가 들어간다'라는 문장이 나타내는 명제일 때, 다음 식들을 한국어 문장으로 번역해보자.

   • $P \land P$
   • $P \leftrightarrow Q$
   • $(\lnot Q) \to Q$
   • $(\lnot P) \lor Q$
   • $(P \lor Q) \to (\lnot Q)$
   답 보기

   • 짜장면에는 춘장이 들어가고 짜장면에는 춘장이 들어간다.
   • 탕수육에 돼지고기가 들어갈 때 그리고 오직 그 때에만 짜장면에 춘장이 들어간다.
   • 탕수육에 돼지고기가 안 들어가면 짜장면에 춘장이 들어간다.
   • 짜장면에 춘장이 안 들어가거나 탕수육에 돼지고기가 들어갔다.
   • 짜장면에 춘장이 들어갔거나 탕수육에 돼지고기가 들어갔다면 탕수육에는 돼지고기가 들어가지 않는다.

아무런 논증이나 논리적일까? : 건전한 논증

어떤 독자는 앞서 나열된 예시에서 무언가 이상한 점을 눈치챘을 것이다. 바로 단순히 논증을 쓰는 것만으로는 논리적인 사고와 별로 상관이 없어 보인다는 것이다. 논증만을 쓰는 것은 어떤 단계도 설명도 없이 그냥 '그것을 전제로 삼으면 이것이 따라나온다'라고 쓰는 것이니, 이런 우격다짐의 어디에 논리적인 구석이 있겠는가? 그래서 사실 우리가 논리학을 사용해 분석하는 것은 건전함(Soundness)이라는 조건이 붙는 논증이다. 논증이 건전하다는 것은 논증의 종류에 따라 다르게 정의되지만, 지금 우리가 다루고 있는 수준의 논리학에서 이야기 할 때에는 다음과 같이 정의할 수 있다.

논증은 나열된 모든 전제가 참인 어떤 가상의 상황에서든 결론이 참일 때에만 그리고 오직 그 때에만 건전하다.

예를 들어

• $P \vdash P$

는 나열된 모든 전제가 참인($P$가 참인) 어느 상황에서든 결론이 참이기($P$가 참이기) 때문에 건전한 논증이지만,

• $P \vdash Q$

는 나열된 모든 전제가 참인($P$가 참인) 상황 중 $Q$가 거짓인 상황에서는 결론이 거짓이기($Q$가 거짓이기) 때문에 건전한 논증이 아니다.

참이고 거짓이고 분간이 돼야 말이지… : 명제의 진리값

잠깐, 방금 전 건전한 논증을 정의할 때 '전제가 참'이라거나 '결론이 참'이라는 표현을 사용했다. 그러면 어떤 명제가 참이고 어떤 명제가 거짓이란 말인가? 이를테면

• $\lnot P$
• $P \land Q$
• $P \lor Q$
• $P \to Q$
• $P \leftrightarrow Q$

같은 것들은 대체 언제 참이고 언제 거짓인지 어떻게 알 수 있단 말인가? 안타깝게도 식이 표현하는 명제들의 참/거짓 값의 엄밀한 정의는 건전함을 증명하기 위해 사용하는 체계에 따라 조금씩 다르다. 다행히도, 이 글에서 다룰 방법에 한정하면 식이 표현하는 명제들의 참/거짓 값은 간단한 규칙으로 정의할 수 있다.

• $\lnot P$는 $P$가 거짓일 때에는 참이고, $P$가 참이면 거짓이다.
• $P \land Q$는 $P$와 $Q$가 모두 참일 때에는 참이고, $P$나 $Q$ 중 하나 이상이 거짓이면 거짓이다.
• $P \lor Q$는 $P$나 $Q$ 중 하나 이상이 참일 때에는 참이고, $P$와 $Q$가 모두 거짓이면 거짓이다.
• $P \to Q$는 $P$가 거짓이거나 $Q$가 참일 때에는 참이고, $P$가 참이면서 $Q$가 거짓이면 거짓이다.
• $P \leftrightarrow Q$는 $P$와 $Q$가 모두 거짓이거나 모두 참일 때에는 참이고, 둘 중 하나만 거짓일 때에는 거짓이다.

네번째 규칙을 제외한 규칙들은 많은 독자들에게 어색하지 않을 것이다. 이 네번째 규칙은 논리학을 처음 접하는 사람들 중 상당수가 헷갈려하는 규칙이다. 특히 $P$가 거짓이고 $Q$가 거짓일 때 $P \to Q$가 참이 된다는 사실에 혼란을 겪는 사람들이 많다. 이 규칙을 이해하기 편하게 하기 위해 필자는 다음과 같은 예시를 즐겨 사용한다.

만일 철수 엄마가 철수에게 '시험 100점 맞으면 최신 Playstation을 사 줄게'라고 말했다고 하자. 철수가 시험에서 80점을 맞은 뒤, 철수 엄마가 Playstation을 사주지 않았다면 철수 엄마는 거짓말을 한 것인가?

여기서

물론 거짓말을 한 게 아니지!

라고 생각하는 독자는 네번째 규칙을 이미 받아들인 것이나 다름없다. 왜 그런지 모르겠거든 한번 곰곰히 생각해보자. 만일

거짓말을 한 것 아닌가?

라는 생각이 드는 독자가 있고, 본인이 개발자라면, $P \to Q$가 if (P) { return Q } else { return true }라는 유사 코드(수도 코드, Psuedo code)와 같은 것이라고 생각하고 넘어가자. 왜 if (P) { return Q } else { return false }가 아닌지는 '그건 P && Q랑 같으니까, 즉 이미 $\land$가 하고있는 역할이니까'정도로 설명할 수는 있다. 개발자가 아닌 독자를 포함해 이해가 하고 싶은데 이해가 가지 않는 독자가 있다면 댓글을 달아주기 바란다. 필자가 답변할 수 있는 한 궁금증을 풀어줄 수 있도록 노력하겠다.

이제 위 규칙의 더 많은 예시를 살펴보자. $P$와 $Q$는 참이고 $R$과 $S$는 거짓이라고 할 때,

• $(\lnot R) \land P$
• $(\lnot S) \leftrightarrow Q$
• $Q \to P$
• $R \to Q$
• $R \to S$
• $((\lnot S) \land R) \leftrightarrow ((P \lor \lnot Q) \to \lnot Q)$

는 모두 참이고

• $\lnot P$
• $R \land (\lnot S)$
• $P \to S$
• $\lnot (\lnot R)$
• $(\lnot S) \leftrightarrow (\lnot P)$
• $P \to (Q \to (\lnot (P \lor R)))$

은 모두 거짓이다.

이런 참/거짓 값을 **'진리값'**이라고 부른다. 이후에는 '참/거짓 값' 대신 '진리값'이라는 표현을 사용할 것이고, '$P$가 참이다' 대신 '$P$의 진리값이 참이다' 또는 '$P$가 참을 진리값으로 가진다' 등의 동등한 표현들을 혼용할 것이니 기억해두면 좋을 것이다.

진리값 연습문제

1. $P$가 거짓이고 $Q$가 참일 때 다음 명제들의 진리값은 무엇일까?

   • $(\lnot P) \to Q$
   • $Q \land Q$
   • $P \lor (\lnot P)$
   • $(\lnot Q) \land (\lnot P)$
   • $(\lnot Q) \leftrightarrow (\lnot P)$
   • $(P \to P) \leftrightarrow (Q \to Q)$
   답 보기

   • 참
   • 참
   • 참
   • 거짓
   • 거짓
   • 참

2. $P$, $Q$, $R$의 진리값이 참이고 $S$, $T$의 진리값이 거짓일 때, 다음 명제의 진리값은 무엇일까?

   $((P \land Q) \lor S) \to ((\lnot R \land T) \to (\lnot Q \lor (S \land T)))$

   답 보기

   참이다. $\lnot R \land T$의 진리값이 거짓이므로, $(\lnot R \land T) \to (\lnot Q \lor (S \land T))$의 진리값은 참이고, 따라서 $((P \land Q) \lor S) \to ((\lnot R \land T) \to (\lnot Q \lor (S \land T)))$ 전체의 진리값은 참이 된다.

뭐가 건전한건데? : 논증의 건전함 증명 체계 - 진리표

이제 드디어 논리학다운 논리학을 시작해보도록 하자. 어떤 논증이 건전한지 아닌지는 어떻게 파악할 수 있을까? 예를 들어 다음의 논증을 보자.

• $\vdash P \to (Q \to P)$

흠? 전제가 아예 없다. 대체 이런 논증이 건전한지 아닌지 어떻게 파악한단 말인가? 나열된 전제가 애초에 있지를 않으니 '나열된 모든 전제가 참이다'라는 조건은 항상 성립할 것이고, 따라서 논증이 건전하려면 어떤 상황에서든 결론이 참이어야한다. 근데 (결론인) $P \to (Q \to P)$가 어떤 상황에서든 참인지 아닌지 대체 어떻게 안단 말인가?

가장 쉬운 방법이자 가장 오래된 방법은 **'진리표'**라고 불리는 기술이다. 진리표는 다음과 같이 쓸 수 있다.

• 논증에 등장하는 모든 단위식을 찾는다.
• 위에서 찾은 모든 단위식을 가로로 나열하고 뒤이어 모든 전제 그리고 마지막으로 결론을 마찬가지로 나열한다.
• 각각의 단위식이 참인 경우와 거짓인 경우를 세로로 나열하고, 각각의 경우에 전제와 결론이 참인지 거짓인지 확인한다.
• 전제가 참인 모든 가로줄에서 결론의 진리값이 참이라면 지금 분석하고 있는 논증은 건전하다.

이렇게 작성법을 문장으로만 나열하면 이해가 힘들 수 있으니, 예시와 함께 살펴보도록 하자. 처음의 예시는 위에서 얘기하고 있었던

• $\vdash P \to (Q \to P)$

이다. 이제 작성법을 차례대로 따라가보자.

• 논증에 등장하는 모든 단위식을 찾는다.

위 논증에는 $P$, $Q$만이 등장한다.

• 위에서 찾은 모든 단위식을 가로로 나열하고 뒤이어 모든 전제 그리고 마지막으로 결론을 마찬가지로 나열한다.

$P$, $Q$를 찾았고 전제는 하나도 없으며 결론은 $P \to (Q \to P)$이니 다음과 같이 나열하면 된다.

• 각각의 단위식이 참인 경우와 거짓인 경우를 세로로 나열하고, 각각의 경우에 전제와 결론이 참인지 거짓인지 확인한다.

$P$가 참인 경우와 거짓인 경우, $Q$가 참인 경우와 거짓인 경우를 모두 나열하면 (참은 T로, 거짓은 F로 작성하였다)

이제 마지막으로,

• 전제가 참인 모든 가로줄에서 결론의 진리값이 참이라면 지금 분석하고 있는 논증은 건전하다.

이 경우에는 전제가 없으니 모든 가로줄을 확인하면 된다. 모든 가로줄에서 결론($P \to (Q \to P)$)에 해당하는 부분(굵은 글씨로 표시된 부분)의 진리값이 모두 참이므로,

• $\vdash P \to (Q \to P)$

는 건전한 논증임을 알 수 있다. 이번에는 전제가 있는 경우의 예시를 살펴보도록 하자. 다음

• $P, Q \lor R \vdash (P \land Q) \lor (P \land R)$

은 $P$와 $Q \lor R$를 전제로 가지고 $(P \land Q) \lor (P \land R)$를 결론으로 가지는 논증이다. 이 논증에는 $P$, $Q$, $R$이 등장하므로 다음과 같은 진리표를 만들 수 있다.

위 표의 가로줄 중 마지막 세 줄에서만 두 전제($P$, $Q \lor R$)가 모두 참인데, 그 세 줄에서는 결론도 모두 참이니 위 논증은 건전하다. 마지막으로 건전하지 않은 논증의 예시를 살펴보고 진리표에 대한 논의를 마치도록 하자.

• $P \lor Q \vdash P \to (P \to (\lnot Q))$

이 논증은 $P \lor Q$를 전제로 가지고 $P \to (P \to (\lnot Q))$를 결론으로 가지는 논증이다. 이 논증에는 $P$, $Q$가 등장하니 만들어진 진리표는

이다. 첫 줄을 제외하고서 모든 줄에서 전제가 참인데, 마지막 줄에서 결론은 거짓이니 이 논증은 건전하지 못하다.

진리표 연습문제

1. 다음 논증을 진리표를 사용해 증명해 보자

   • $P \vdash Q \to P$
   • $\vdash P \lor (\lnot P)$
   • $P \land Q \vdash P$
   • $Q \vdash P \lor Q$
   • $\vdash (P \to Q) \to ((Q \to R) \to (P \to R))$
   답 보기

   • $P \vdash Q \to P$

     $P$	$Q$	$P$	$Q \to P$
     F	F	F	T
     F	T	F	F
     T	F	T	T
     T	T	T	T

   • $\vdash P \lor (\lnot P)$

     $P$	$P \lor (\lnot P)$
     F	T
     T	T

   • $P \land Q \vdash P$

     $P$	$Q$	$P \land Q$	$P$
     F	F	F	F
     F	T	F	F
     T	F	F	T
     T	T	T	T

   • $Q \vdash P \lor Q$

     $P$	$Q$	$Q$	$P \lor Q$
     F	F	F	F
     F	T	T	T
     T	F	F	T
     T	T	T	T

   • $\vdash (P \to Q) \to ((Q \to R) \to (P \to R))$

     $P$	$Q$	$R$	$(P \to Q) \to ((Q \to R) \to (P \to R))$
     F	F	F	T
     F	T	F	T
     T	F	T	T
     T	T	T	T

2. 단위식 $P$가 '명호는 졸리다' 그리고 단위식 $Q$가 '명호는 잠을 잔다'라는 문장이 나타내는 명제일 때 다음의 명제를 전제가 없는 논증으로 표현하고 진리표를 사용해 증명해보자.

   • 명호는 졸리거나 졸리지 않다
   • 명호가 잠을 잔다면 명호는 잠을 잔다
   • 명호가 졸리면서 잠을 잔다면 명호는 졸리다.
   • 명호가 졸리다고 할 때, 또 명호가 졸리면 명호가 잠을 잔다고 할 때, 명호는 잠을 잔다.
   답 보기

   • $\vdash P \lor (\lnot P)$
     증명은 바로 윗 문제에 쓰여있는 것과 동일하다.

   • $\vdash Q \to Q$

     $Q$	$Q \to Q$
     F	T
     T	T

   • $\vdash (P \land Q) \to P$ 혹은 $\vdash P \to (Q \to P)$

     $P$	$Q$	$P \land Q \to P$
     F	F	T
     F	T	T
     T	F	T
     T	T	T

     혹은

     $P$	$Q$	$P \to (Q \to P)$
     F	F	T
     F	T	T
     T	F	T
     T	T	T

   • $\vdash (P \land (P \to Q)) \to Q$ 또는 $\vdash P \to ((P \to Q) \to Q)$

     $P$	$Q$	$(P \land (P \to Q)) \to Q$
     F	F	T
     F	T	T
     T	F	T
     T	T	T

     또는

     $P$	$Q$	$P \to ((P \to Q) \to Q)$
     F	F	T
     F	T	T
     T	F	T
     T	T	T

첫 글을 마치며

혹자는 진리표를 사용하는 방법을 보면서 약간 미심쩍다는 생각이 들었을지도 모르겠다.

그냥 모든 경우를 일일히 따져야한다고? 좀 그렇지 않아?

사실 위 방법은 단순하고 오래된 것이니 만큼 여러 문제점을 가지고 있다. 이어지는 글에서는 진리표에 어떤 문제점이 있는지, 그리고 명제논리에서 논증을 증명하는 다른 접근 방법들이 무엇이 있는지 알아볼 것이다.

이어지는 글

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