빌드 날짜: 2026-08-29

이 문서를 읽는 방법

이 문서는 형식 논리를 혼자 읽어 학사 과정 수준까지 도달하도록 정리한 자습서다. 명제논리와 술어논리의 문법·의미론·증명 체계를 세운 뒤, 그 체계 자체를 대상으로 삼아 무엇을 말할 수 있는지까지 간다. 건전성과 완전성, 컴팩트성, 결정불가능성, 괴델의 불완전성 정리가 그것이다.

이 과목의 목표는 기호를 외우는 것이 아니다. 어떤 논증이 왜 좋은지 말할 수 있고, 그 판단의 근거를 스스로 검사할 수 있는 것이다.

이 문서와 다른 문서의 분업

이 사이트의 Mathematics for Computer Science 문서가 이미 진리표, 명제 대수, 정규형, SAT, 한정사의 뜻과 부정을 다룬다. 그것을 여기서 다시 가르치지 않는다. 5·6장과 9·10장은 그 내용을 요약하고 지나가는 통과 지점이고, 이 문서가 새로 하는 일은 그 다음부터다.

무엇을 알고 있어야 하는가

중학교 수학까지면 된다. 이 문서는 다른 어느 문서보다 전제가 적다. 계산이 거의 없고, 필요한 도구는 나오는 자리에서 만든다.

• 집합과 원소 — 5장 "어휘" 절 끝에서 중괄호·$\in$·$\subseteq$·$\cup$·$\mathrm{\varnothing }$ 다섯을 한 문단으로 도입한다
• 함수와 관계 — 10장에서 해석을 정의할 때. 거기서 도입한다
• 수학적 귀납법 — 13장에서 처음 쓴다. 5장의 재귀적 정의가 미리 준비해 둔다
• 가산과 비가산 — 15장에서 필요하다. 그 자리에서 정의한다

프로그래밍 경험은 요구하지 않는다. 다만 6장의 지수 폭발과 16장의 판정 문제에서 알고리즘 문서와 만난다.

이 문서가 지키려는 약속

• 어떤 기호도 정의하기 전에 쓰지 않는다. 처음 나오는 자리에서 이름·뜻·읽는 법을 함께 밝힌다.
• $⊢$ 와 $\models$ 를 끝까지 구분한다. 하나는 증명 체계의 주장이고 하나는 의미론의 주장이다. 둘이 같은지는 13·14장이 답할 문제이지 가정할 것이 아니다.
• 증명은 말로 된 뼈대를 먼저 주고 형식을 뒤에 둔다. 형식만 있는 증명은 읽는 사람에게 아무것도 남기지 않는다.
• 각 장은 "이 장에서 새로 나온 것" 표로 닫는다.
• 어려운 곳은 어렵다고 말한다. 어디서 걸릴지 미리 알려 둔다.

이 문서의 짜임

열일곱 개 장이 여섯 덩어리로 묶인다. 어느 덩어리를 읽고 있는지 알면 각 장이 왜 거기 있는지가 보인다.

2부와 3부가 같은 모양으로 배열되어 있다. 문법 → 의미론 → 증명 체계 → (연습·확장) 순서가 두 번 반복된다. 두 번째가 빠르게 읽히는 것은 그 때문이고, 그렇게 되도록 일부러 배열했다.

4부가 이 문서의 정점이다. 13장이 "증명한 것은 참이다"를, 14장이 "참인 것은 증명된다"를 보인다. 두 장을 붙여 읽어야 $⊢$ 와 $\models$ 가 왜 같은 것이 되는지가 남는다.

권장 순서와 장별 난이도

총 85시간 남짓이다. 하루 2시간이면 여섯 주 정도의 분량이다.

가장 걸리는 곳을 미리 알려 둔다. 11장의 변수 조건과 14장의 완전성 증명이다. 앞의 것은 규칙이 줄의 모양만 보는 것이 아니라 도출의 다른 부분까지 살핀다는 점이 낯설어서 걸리고, 뒤의 것은 증명이 길고 여러 보조정리를 쌓아야 해서 걸린다. 14장은 한 번에 이해하려 하지 말고 "대우로 바꾼다"는 첫 걸음만 확실히 잡고 넘어가도 된다.

18·19장은 앞을 다 읽지 않아도 각각 독립적으로 읽힌다. 다만 19장은 7장의 규칙 목록을 쓴다.

이 문서의 표기 규약

여러 층의 주장이 섞이는 문서라 표기를 어긋나게 쓰면 곧바로 읽을 수 없게 된다. 아래가 전부다.

술어에 $P$ 를 쓰지 않는 것에 주의하라. 명제논리의 문장문자와 겹쳐 헷갈리기 때문에, 9장 이후 술어는 $F,G,H$ 로 통일한다.

도출은 두 가지 방식으로 적는다. 규칙 하나를 보일 때는 증명 트리를, 여러 줄짜리 도출은 줄 번호와 근거를 적는 표를 쓴다. 트리는 단이 넷을 넘으면 읽히지 않는다.

참고문서

교재

• P. D. Magnus, Tim Button 외, forall x: Calgary — 입문. CC BY 4.0 이고 연습문제 해답이 따로 제공된다
• Open Logic Project — 메타이론 중심의 중급·고급 교재. CC BY
• Peter Smith, Teach Yourself Logic — 무엇을 어떤 순서로 읽을지에 대한 안내서
• Boolos, Burgess, Jeffrey, Computability and Logic — 16·17장 이후

강의

• MIT OCW 24.241 Logic I
• MIT OCW 6.045J Automata, Computability, and Complexity — 16장 심화

도구

• Open Logic Proof Checker — 자연연역 도출을 검사한다
• Tree Proof Generator — 타당성 판정과 반례 모형

원전과 표준

• Stanford Encyclopedia of Philosophy — Gödel’s Incompleteness Theorems
• Stanford Encyclopedia of Philosophy — Modal Logic
• Stanford Encyclopedia of Philosophy — Intuitionistic Logic

논증 — 무엇이 좋은 논증인가

논리학이 하는 일은 좋은 논증과 나쁜 논증을 가르는 것이다. 그러니 맨 먼저 할 일은 논증이 무엇이고 좋다가 무슨 뜻인지 정하는 것이다. 둘 다 일상에서 쓰는 말이지만, 여기서 정할 뜻은 일상의 뜻보다 훨씬 좁다.

이 장에서 답할 질문은 넷이다.

• 논증이란 무엇인가. 어떤 말 묶음은 논증이고 어떤 것은 아닌가.
• 좋은 논증은 무엇이 좋은가. 결론이 참이면 좋은 논증인가.
• 나쁘다는 것을 어떻게 보이는가.
• 왜 논리학은 논증이 무엇에 관한 이야기인지를 보지 않는가.

이 장이 이 문서의 실질적인 출발점이다. 앞 장에서 가져오는 것은 없다. 대신 여기서 정하는 낱말 — 전제, 결론, 타당, 건전, 반례 — 은 마지막 장까지 뜻이 바뀌지 않는다.

계산은 거의 없다. 그래서 쉬워 보이지만 판단이 어려운 장이다. 특히 타당성 절에서 거의 모든 독자가 한 번 걸린다. 그 자리에는 미리 표시를 해 두었으니 급히 넘기지 않는 편이 좋다.

논증 — 전제와 결론

논증(argument)은 문장의 묶음이다. 그중 하나가 결론(conclusion)이고, 나머지는 그 결론을 받아들일 이유로 내놓은 전제(premise)다.

셋이 다 있어야 논증이다. 결론이 있어야 하고, 전제가 있어야 하고, 전제를 결론의 이유로 내놓는 의도가 있어야 한다. 문장이 여럿 있다고 논증이 되지는 않는다.

이 문서는 논증을 이렇게 줄 세워 적는다. 위가 전제, 맨 아래가 결론이다.

• 전제 — 비가 오면 길이 젖는다.
• 전제 — 비가 온다.
• 결론 — 길이 젖는다.

일상 글에서는 이렇게 정돈되어 있지 않다. "비 오잖아. 비 오면 길 젖지. 그러니까 길 젖었을 거야" 처럼 순서가 뒤섞여 나온다. 논증을 다루는 첫 작업은 늘 어느 문장이 결론인지 찾는 것이다.

찾는 데 도움이 되는 표시가 있다. '그러므로', '따라서', '그러니까', '결국' 뒤에 오는 것이 대개 결론이고, '왜냐하면', '때문이다', '-니까' 가 붙은 쪽이 대개 전제다. 표시가 아예 없을 때도 많다. 그럴 때는 "이 사람이 나를 무엇에 설득하려 하는가"를 물으면 된다.

논증이 아닌 것

논증과 자주 헷갈리는 셋을 갈라 두자.

설명과 논증의 구별이 가장 미묘하다. 둘 다 "A 이므로 B 다" 꼴이기 때문이다. 가르는 것은 B 의 지위다. 듣는 사람이 B 를 이미 받아들였으면 그 말은 설명이고, B 를 받아들이게 하려는 것이면 논증이다.

그러니 같은 문장 묶음이 자리에 따라 설명이 되기도 하고 논증이 되기도 한다. "다리가 무너졌다. 볼트가 삭았기 때문이다." 다리가 무너진 것을 모두가 아는 자리에서는 설명이고, 무너졌는지 아닌지를 다투는 자리에서는 논증이다.

타당성 — 전제가 참이면 결론이 반드시 참

좋은 논증의 첫째 조건을 정한다.

논증이 타당(valid)하다는 것은 전제가 모두 참인데 결론이 거짓인 경우가 있을 수 없다는 뜻이다.

같은 말을 뒤집으면 이렇다. 전제를 모두 참으로 만드는 상황이라면 어느 것이든 결론도 참으로 만든다. 전제가 결론을 남김없이 보증한다는 것이 타당성이다.

타당하지 않은 논증은 부당(invalid)하다고 한다. 중간은 없다. 논증은 타당하거나 부당하거나 둘 중 하나다.

여기가 이 장에서 가장 걸리는 곳이다

정의를 다시 읽어 보라. "전제가 실제로 참이다"라는 말이 어디에도 없다. 타당성은 "전제가 참이라고 치면"이라는 가정 아래에서만 따지는 성질이다. 전제가 실제로 참인지 거짓인지는 타당성과 상관이 없다.

일상어와 어긋나기 때문에 걸린다. 일상에서 "타당하다"는 대개 "맞는 말이다" 정도의 뜻이다. 여기서는 그런 뜻이 아니다. 아래 논증을 보자.

• 전제 — 모든 물고기는 날개가 있다.
• 전제 — 고등어는 물고기다.
• 결론 — 고등어는 날개가 있다.

첫 전제가 거짓이고 결론도 거짓이다. 그런데 이 논증은 타당하다. 전제가 둘 다 참인 상황을 상상해 보라. 정말로 모든 물고기에 날개가 달린 세상이라면, 고등어가 물고기인 이상 고등어에는 날개가 있다. 전제를 참으로 만들면서 결론을 거짓으로 만들 길이 없다. 그것이 타당하다는 말의 전부다.

반대쪽도 보자.

• 전제 — 모든 개는 포유류다.
• 전제 — 어떤 포유류는 헤엄친다.
• 결론 — 어떤 개는 헤엄친다.

세 문장이 모두 실제로 참이다. 그런데 이 논증은 부당하다. 전제가 결론을 보증하지 않기 때문이다. '개'를 '코끼리'로, '헤엄친다'를 '하늘을 난다'로 바꿔 보라. "모든 코끼리는 포유류다"도 참이고 "어떤 포유류는 하늘을 난다"도 참인데(박쥐가 있다) "어떤 코끼리는 하늘을 난다"는 거짓이다. 짜임이 같은 논증이 참에서 거짓으로 갈 수 있다면, 원래 논증에서 결론이 참인 것은 전제 덕분이 아니다.

그림이 말하는 것을 한 문장으로 줄이면 이렇다. 타당성은 전제와 결론 사이의 관계이지 전제나 결론 각각의 성질이 아니다.

건전성 — 타당함에 사실을 더한다

타당하기만 해서는 결론을 믿을 이유가 되지 못한다. 물고기 논증은 타당했지만 결론은 거짓이었다. 전제가 거짓이었기 때문이다.

그래서 조건을 하나 더 붙인다. 논증이 건전(sound)하다는 것은 타당하고, 게다가 전제가 모두 실제로 참이라는 뜻이다.

건전한 논증의 결론은 반드시 참이다. 타당성이 "전제가 참이면 결론이 참"을 보장하고 건전성이 "전제가 참이다"를 보태 주므로, 둘을 합치면 결론이 참이라는 결론이 나온다. 우리가 논증에서 실제로 얻고 싶은 것은 건전성이다.

그런데 논리학이 다룰 수 있는 것은 타당성뿐이다. "모든 물고기는 날개가 있다"가 참인지 거짓인지는 논리학이 답할 수 있는 물음이 아니다. 그것은 생물학의 몫이다. 건전성은 두 조각으로 나뉘고 논리학은 그중 한 조각만 맡는다.

낱말이 겹친다 — 건전은 세 곳에서 쓰인다

여기서 미리 밝혀 둘 것이 있다. '건전(sound)'이라는 낱말이 이 문서와 이웃 문서에서 서로 다른 것에 붙는다. 모르고 지나가면 뒤에서 반드시 걸린다.

가장 조심할 곳은 가운데 줄이다. Mathematics for Computer Science 3장은 추론 규칙 하나를 두고 ‘건전하다’고 말한다. 그 뜻은 ‘전제를 참으로 만드는 배정이면 결론도 참으로 만든다’이다. 이 장의 낱말로 옮기면 그것은 건전이 아니라 타당이다. 전제가 실제로 참인지는 묻지 않기 때문이다. 같은 낱말을 보고 같은 뜻이라고 넘기면 뒤에서 계산이 어긋난다.

낱말이 겹치는 것은 우연이 아니다. 세 뜻이 모두 "참을 잃지 않는다"는 하나의 생각을 서로 다른 대상에 적용한 것이다. 그래도 대상이 다르므로 무엇이 건전한지를 늘 함께 말하는 습관을 들이는 편이 안전하다. 이 문서는 논증에 붙일 때만 아무 말 없이 '건전'이라 쓰고, 나머지 둘은 '규칙의 건전성', '체계의 건전성'이라고 적는다.

반례 — 부당함을 보이는 방법

앞에서 부당하다고 판정할 때마다 같은 일을 했다. 전제를 모두 참으로 만들면서 결론을 거짓으로 만드는 상황을 하나 내놓았다. 그 상황에 이름을 붙인다.

반례(counterexample)는 전제를 모두 참으로 만들면서 결론을 거짓으로 만드는 상황이다. 반례가 하나라도 있으면 그 논증은 부당하고, 하나도 없으면 타당하다. 타당성의 정의를 뒤집어 읽은 것뿐이다.

여기서 비대칭이 생긴다. 부당함을 보이는 데는 상황 하나면 충분하다. 타당함을 보이려면 상황 전체를 확인해야 한다. 상황이 무한히 많으면 하나씩 확인할 수 없으므로 타당함을 보이는 데는 다른 도구가 필요하다. 6장의 진리표와 7장의 자연연역이 그 도구다.

반례는 이 문서 전체를 관통하는 방법이다. 10장에서는 반례가 되는 상황을 반례 모형이라 부르고, 15장에서는 반례가 되는 세상을 아예 만들어 낸다. 하는 일은 지금 세우는 것과 같다. 무엇을 참으로 만들고 무엇을 거짓으로 만들지를 정한 상황 하나를 내놓는 것이다.

반례를 만드는 두 가지 길

첫째, 상황을 직접 상상한다. 반례는 실제로 일어난 일일 필요가 없다. 앞뒤가 맞기만 하면 된다. 이것을 잊으면 "그런 일은 없었다"는 말로 반례를 물리치려 들게 된다.

둘째, 짜임이 같은 다른 논증을 만든다. '개'를 '코끼리'로 바꿨던 것이 그것이다. 짜임이 같은데 전제가 참이고 결론이 거짓인 논증을 하나 찾으면 된다.

둘째 길이 정확히 무엇을 보이는지는 조심해서 말해야 한다. 그것이 보이는 것은 그 짜임이 결론을 보증하지 못한다는 것이다. 왜 그것으로 충분한지는 다음 절에서 다시 본다.

연역과 귀납 — 이 문서가 다루는 것

타당성 잣대로 재면 부당한데도 나쁘다고 하기 어려운 논증이 있다.

• 전제 — 지금까지 관찰한 백조는 모두 희었다.
• 결론 — 다음에 볼 백조도 흴 것이다.

부당하다. 전제가 참인데 다음 백조가 검은 상황을 상상할 수 있기 때문이다. 그런데 이 논증은 애초에 결론을 보증한다고 주장한 적이 없다. 보증하지 않겠다고 한 것을 보증하지 않는다고 나무라는 셈이다.

여기서 논증이 두 갈래로 갈린다.

마지막 줄을 단조성(monotonicity)이라 한다. 연역은 단조적이다. 타당한 논증에 아무 전제나 더 붙여도 여전히 타당하다. 귀납은 그렇지 않다. "다음에 볼 백조도 흴 것이다" 라는 추론은 "오스트레일리아에는 검은 백조가 산다" 라는 전제 하나가 붙는 순간 무너진다.

셋째 줄도 눈여겨볼 만하다. 연역 논증의 결론은 전제에 이미 들어 있던 것을 다시 꺼낸 것이다. 그래서 새 정보를 주지 못한다고 말하기도 한다. 그러나 "들어 있다"와 "보인다"는 다르다. 수학의 정리는 전부 공리에 들어 있지만 아무도 그것을 미리 보지 못한다.

이 문서는 연역만 다룬다. 앞으로 ‘논증’이라고 쓰면 연역 논증을 뜻하고, ‘좋다’는 타당하다는 뜻이다. 귀납이 덜 중요해서가 아니다. 귀납의 강도를 재는 도구는 논리가 아니라 확률이고, 그것은 통계학 문서의 몫이다.

형식이 판단을 이끈다

지금까지 타당한지 아닌지를 판정할 때 우리가 실제로 본 것은 무엇이었나. 물고기도 아니고 소수도 아니었다. 짜임이었다. 이제 그 짜임에 이름과 기호를 준다.

논증 형식과 대입례

문장이 들어갈 자리에 빈칸을 뚫는다. 빈칸은 $\phi$, $\psi$, $\chi$ 로 적는다. 이것들은 명제가 아니다. 아무 논리식이나 들어갈 수 있는 자리를 가리키는 기호이고, 이런 기호를 메타변수라 부른다. 원자 명제를 적는 $P$, $Q$, $R$ 와 섞지 않도록 조심하자. $P$ 는 문장 하나이고 $\phi$ 는 문장이 들어갈 구멍이다.

문장을 잇는 데 쓰는 기호도 둘만 미리 쓴다. $\phi \to \psi$ 는 "$\phi$ 이면 $\psi$ 다"이고, $\mathrm{\neg }\phi$ 는 "$\phi$ 가 아니다"이다. 나머지 기호와 정확한 뜻은 5장과 6장에서 세운다.

앞에서 여러 번 나온 짜임을 이렇게 적을 수 있다. 가로선 위가 전제, 아래가 결론이다.

${\displaystyle \frac{\phi \to \psi ,\phi }{\psi }}$

이것이 논증 형식(argument form)이다. 빈칸에 실제 문장을 채워 만든 논증을 그 형식의 대입례(substitution instance)라 한다. 이 장 첫머리의 비와 길 논증이 $\phi$ 에 "비가 온다"를, $\psi$ 에 "길이 젖는다"를 넣은 대입례다.

규칙은 이렇다. 어떤 논증이 타당한 형식의 대입례이면 그 논증은 타당하다. 빈칸에 무엇을 넣든 상관없다. 형식이 타당하다는 것이 곧 어떤 대입에서도 반례가 없다는 뜻이기 때문이다. 논리학이 내용을 보지 않는 이유가 여기 있다. 내용을 보지 않아도 되는 만큼만 논리학이 답한다.

거꾸로는 성립하지 않는다. 부당한 형식의 대입례라고 해서 그 논증이 부당한 것은 아니다. 논증 하나는 여러 형식의 대입례일 수 있고, 그중 타당한 형식이 하나라도 있으면 타당하다. 곧 볼 부당한 형식 ${\displaystyle \frac{\phi \to \psi ,\psi }{\phi }}$ 에 $\phi$ 와 $\psi$ 를 둘 다 $P$ 로 놓아 보라. 전제가 $P\to P$ 와 $P$, 결론이 $P$ 인 논증이 되는데 이것은 타당하다.

흔한 형식적 오류 — 후건 긍정과 전건 부정

$\phi \to \psi$ 를 전제로 쓰는 형식은 네 가지가 있다. 둘은 타당하고 둘은 부당하다. 부당한 둘에는 따로 이름이 붙어 있을 만큼 자주 나온다.

부당한 두 형식은 반례가 같다. $\phi$ 가 거짓이고 $\psi$ 가 참인 상황이다. 그때 $\phi \to \psi$ 는 참이 된다 — 조건문은 앞부분이 거짓이면 참으로 친다. 이 규약이 어디서 오는지는 6장에서 다룬다. 지금은 "일어나지 않은 일에 대한 약속은 어긴 것으로 치지 않는다" 정도로 받아들이면 된다.

후건 긍정에서는 그 상황에서 전제 $\phi \to \psi$ 와 $\psi$ 가 둘 다 참이고 결론 $\phi$ 는 거짓이다. 전건 부정에서는 전제 $\phi \to \psi$ 와 $\mathrm{\neg }\phi$ 가 둘 다 참이고 결론 $\mathrm{\neg }\psi$ 는 거짓이다. 반례 하나가 둘을 함께 무너뜨린다.

비형식 오류는 이름만 적어 둔다

형식이 아니라 내용과 맥락 때문에 나쁜 논증도 많다. 상대의 주장을 약하게 고쳐 놓고 그것을 공격하기(허수아비), 주장 대신 사람을 공격하기(인신공격), 결론을 전제 안에 몰래 넣기(선결문제 요구), 몇 사례로 전체를 단정하기(성급한 일반화), 선택지가 둘뿐인 것처럼 내놓기(거짓 딜레마), 권위에 호소하기, 작은 양보가 파국으로 이어진다고 몰기(미끄러운 비탈).

이 문서는 이것들을 다루지 않는다. 중요하지 않아서가 아니라 형식으로 잡히지 않기 때문이다. 앞 절의 오류에 호소하기도 같은 부류다. 빈칸에 무엇을 넣었느냐를 봐야만 나쁜지 알 수 있으므로, 빈칸만 보는 도구로는 잡을 수 없다.

그리고 형식을 보려면 형식이 눈에 보여야 한다. 자연어 문장은 형식을 감춘다. "비가 오지 않으면 소풍을 간다" 와 "소풍을 가려면 비가 오지 않아야 한다" 는 같은 형식인가 다른 형식인가. 한국어만 들여다봐서는 답이 갈린다. 다음 장이 그 일을 한다. 자연어를 기호로 옮겨 형식을 드러내고, 그 과정에서 무엇을 잃고 무엇을 얻는지 따진다.

이 장에서 새로 나온 것

다음 장은 이 장이 남긴 숙제를 받는다. 형식을 보고 판정하기로 했는데, 자연어 문장에서 형식을 어떻게 읽어 낼 것인가. 그리고 기호로 옮기는 동안 무엇이 사라지는가.

논증의 형태를 드러내기

3장은 타당성이 내용의 문제가 아니라 형식의 문제라고 결론지었다. 그렇다면 형식을 꺼내 보여야 한다. 이 장이 하는 일이 그것이다.

이 장에서 답할 질문은 셋이다. 서로 다른 이야기를 하는 두 논증이 같은 형식이라는 말은 무슨 뜻인가. 한국어 문장에서 무엇을 기호로 바꾸고 무엇을 남기는가. 그리고 옮기면서 무엇을 잃는가. 이 장의 제목에 쓴 ‘형태’ 는 3장이 논증 형식이라 부른 것과 같은 것을 가리킨다. 아래에서는 3장의 이름을 그대로 쓴다.

3장에서 가져오는 것은 넷이다. 타당성의 뜻 — 전제가 모두 참인데 결론이 거짓인 경우가 있을 수 없다는 것. 타당성과 건전성의 구별. 논증 형식과 대입례, 그리고 빈칸을 가리키는 메타변수 $\phi$, $\psi$, $\chi$ 와 원자 명제 $P$, $Q$, $R$ 의 구별. 마지막으로 타당한 형식의 대입례는 타당하지만 거꾸로는 아니라는 규칙이다.

미리 밝혀 둘 것이 있다. 이 장에서 $\mathrm{\neg }$, $\wedge$, $\vee$, $\to$ 같은 기호를 쓴다. 그러나 그 기호의 문법은 5장에서, 뜻은 6장에서 정한다. 여기서는 속기로 쓸 뿐이다. 그래서 이 장의 몇 대목은 '지금은 어긋나 보이지만 6장에서 결말이 난다' 는 모양으로 남는다. 그 어긋남을 미리 느껴 두는 것이 이 장의 목적 가운데 하나다.

진리표로 계산하는 연습을 이미 해 본 독자도 있을 것이다. Mathematics for Computer Science 5장이 그것을 다룬다. 이 장은 그 계산 앞에 놓인 단계, 곧 계산할 대상을 한국어에서 만들어 내는 단계를 다룬다.

같은 형식을 공유하는 논증들

아래 두 논증을 보자.

• 비가 오면 길이 젖는다. 비가 온다. 따라서 길이 젖는다.
• 이 수가 4의 배수이면 짝수다. 이 수는 4의 배수다. 따라서 이 수는 짝수다.

하나는 날씨 이야기고 하나는 수 이야기다. 겹치는 낱말이 하나도 없다. 그런데 낱말을 지우고 짜임만 남기면 남는 것이 같다.

$\phi \to \psi$, $\phi$, 따라서 $\psi$

3장에서 이름을 얻은 것들이다. 빈칸이 뚫린 이 짜임이 논증 형식(argument form)이고, 빈칸을 채워 만든 논증이 그 형식의 대입례(substitution instance)다. 위의 두 논증은 같은 형식의 서로 다른 대입례다. 그런데 3장은 형식을 이미 드러난 것으로 놓고 이야기했다. 한국어 문장을 앞에 두고 어디를 지우고 어디를 남길지 정하는 일 — 그것이 이 장의 몫이다.

형식을 꺼내는 이득은 분명하다. 타당성 판정을 형식에서 한 번만 하면 그 형식의 대입례 전부가 판정을 물려받는다. 세상의 문장은 끝이 없지만 형식은 셀 수 있을 만큼 적다. 논리학이 논증을 하나씩 상대하지 않고 다룰 수 있는 이유가 여기 있다.

3장에서 본 대로 방향은 한쪽뿐이다. 형식이 타당하면 대입례는 모두 타당하지만 형식이 타당하지 않다고 해서 그 대입례가 부당한 것은 아니다. 3장은 $\phi$ 와 $\psi$ 에 같은 문장을 넣는 예로 그것을 보였다. 이 절의 둘째 예제는 같은 일이 훨씬 넓게 벌어지는 자리를 보인다.

논리 상항과 비논리 상항

형식을 꺼낸다는 것은 어떤 낱말은 지우고 어떤 낱말은 남긴다는 뜻이다. 남기는 낱말을 논리 상항(logical constant), 지우는 낱말을 비논리 상항(non-logical constant)이라 한다. 기준은 이렇다. 비논리 상항은 무엇으로 갈아끼워도 타당성이 변하지 않는 낱말이고, 논리 상항은 갈아끼우면 타당성이 변할 수 있어 고정해 두는 낱말이다.

이 문서가 논리 상항으로 삼는 것은 아래가 전부다. 늘리지 않는다.

나머지 낱말은 전부 비논리 상항이다. 이름, 술어, 관계, 부사, 그리고 '반드시' 나 '아마' 같은 말까지 모두 그렇다.

5장부터 8장까지 쓰는 언어에서는 자르는 자리가 더 거칠다. 위의 연결자만 남기고 그 사이에 낀 문장 조각을 통째로 글자 하나로 잡는다. 그 글자를 원자 명제(atomic proposition)라 하고 $P$, $Q$, $R$ 로 적는다. 문장 안이 어떻게 생겼는지는 보지 않는다.

원자를 고르는 규칙은 넷이다.

1. 더 쪼갤 수 없을 때까지 쪼갠다. 조각 안에 논리 상항이 하나라도 남아 있으면 아직 원자가 아니다.
2. 긍정형으로 잡는다. '비가 오지 않는다' 를 $Q$ 로 세우지 말고 $\mathrm{\neg }P$ 로 적는다.
3. 참·거짓을 물을 수 있는 문장으로 잡는다. '철수가' 나 '달린다' 같은 조각은 원자가 될 수 없다.
4. 사전을 적는다. $P$ 가 무슨 문장인지 밝히지 않은 기호식은 읽을 수 없다.

아니다, 그리고, 또는

이제 연결자를 하나씩 옮겨 본다. 셋은 비교적 순하고, 다음 절의 '이면' 이 말썽이다.

아니다

$\mathrm{\neg }P$ 로 적는다. 가장 안전한 풀이는 '$P$ 인 것은 사실이 아니다' 다. 한국어에서 부정은 따로 선 낱말이 아니라 어미와 접사로 붙는다. '-지 않다', '안-', '못-', '-지 못하다', '아니다' 가 모두 부정이다.

함정이 둘 있다. 첫째, 반대말은 부정이 아니다. '행복하지 않다' 와 '불행하다' 는 다르다. 둘 다 아닌 중간이 있기 때문이다. 반대말을 만나면 원자를 따로 세워야 한다. 둘째, 이중부정을 함부로 줄이지 않는다. $\mathrm{\neg }\mathrm{\neg }P$ 를 $P$ 로 바꿔도 되는지는 6장에서 판정하고, 19장에서는 그 바꿈을 허락하지 않는 논리를 본다. 옮기는 단계에서는 원문의 모양을 그대로 남긴다. 줄이는 일은 옮긴 다음의 일이다.

그리고

$P\wedge Q$ 로 적는다. '그리고' 만이 아니라 '그러나, 하지만, -지만, -고, -며, 동시에, 게다가' 가 모두 논리곱이 된다. 이 낱말들이 나르던 대조와 기대 어긋남은 버려진다.

주어를 아낀 문장은 펴서 옮긴다. '철수는 키가 크고 마르다' 는 '철수는 키가 크다' 와 '철수는 말랐다' 의 논리곱이다. 다만 앞 절에서 본 대로 '와/과' 는 논리곱이 아닐 수 있다. 관계를 말하는 문장은 쪼개지지 않는다.

또는

$P\vee Q$ 로 적는다. '또는, 혹은, -거나, -든지, -이나' 가 여기 든다. 여기서 한국어와 갈라지는 자리가 처음 나온다. '또는' 에는 두 가지 읽기가 있다.

• 포함적(inclusive) — 적어도 하나가 참이면 참. 둘 다 참이어도 참이다.
• 배타적(exclusive) — 정확히 하나가 참일 때만 참. 둘 다 참이면 거짓이다.

논리학은 $\vee$ 를 포함적 쪽으로 정한다. 배타적으로 읽어야 하는 문장은 기호를 새로 만들지 않고 $(P\vee Q)\wedge \mathrm{\neg }(P\wedge Q)$ 처럼 조립해서 적는다.

그림에서 보듯 판별 물음은 하나로 줄어든다. 둘 다 참일 때도 참인가. 참이면 포함적이고 거짓이면 배타적이다. 그런데 왜 포함적 쪽을 기본으로 삼는가. 자연어의 '또는' 이 배타적으로 들리는 것은 대개 낱말의 뜻 때문이 아니라 말하는 상황 때문이라는 관찰이 있다. 이를 가리는 방법이 취소 시험(cancellability test)이다. 뒤에 말을 덧붙여 그 읽기를 취소해도 모순이 되지 않으면, 그 읽기는 낱말의 뜻이 아니다.

'커피나 차를 드릴게요. 사실 둘 다 드려도 됩니다.' 이 말은 이상하게 들릴 수 있어도 자기모순은 아니다. 배타성이 '또는' 의 뜻이었다면 앞뒤가 맞지 않는 말이 됐을 것이다. 그러므로 배타성은 뜻이 아니라 상황이 얹은 것이고, 필요할 때 위의 꼴로 덧붙여 적으면 된다.

부정과 섞이는 자리도 조심해야 한다. '커피도 차도 마시지 않았다' 는 '마시지 않았다' 가 둘 모두에 걸리므로 $\mathrm{\neg }P\wedge \mathrm{\neg }Q$ 다. 이것이 $\mathrm{\neg }(P\vee Q)$ 와 같은 것인지는 6장에서 확인한다.

이면 — 이 장에서 가장 걸리는 곳

$P\to Q$ 로 적고, 앞을 전건(antecedent), 뒤를 후건(consequent)이라 한다. 여기가 이 장에서 가장 걸리는 곳이다. 다른 연결자는 한국어와 대체로 맞는데 조건문은 그렇지 않다.

진리조건은 6장에서 정하지만 결말을 미리 말해 두는 편이 낫다. 6장은 $P\to Q$ 를 실질함의(material implication)로 정한다. 즉 전건이 참인데 후건이 거짓인 경우에만 거짓이고 나머지 경우는 모두 참이다. 특히 전건이 거짓이면 후건이 무엇이든 전체가 참이 된다. 이 대목이 불편해야 정상이다. 불편한 자리를 지금 짚어 두면 6장에서 무엇이 해결되고 무엇이 해결되지 않는지 알아볼 수 있다.

실질함의와 어긋나는 세 자리

첫째, 연관이 없어도 참이 된다. '달이 치즈로 되어 있으면 2 더하기 2는 4다' 는 전건이 거짓이므로 실질함의로는 참이다. 한국어로는 말이 안 되는 문장이다. 자연어의 '이면' 은 전건과 후건 사이의 연결을 주장하는데 실질함의는 진리값 조합만 본다.

둘째, 반사실 조건문을 담지 못한다. '내가 그때 뛰었더라면 버스를 탔을 것이다' 는 뛰지 않았다는 것을 전제로 하는 문장이다. 전건이 거짓이므로 실질함의로는 무조건 참이 된다. 그러나 이 문장은 거짓일 수 있다 — 버스가 이미 떠났다면 그렇다. 반사실 조건문은 $\to$ 로 옮길 수 없다. 18장의 도구가 필요하다.

셋째, 법칙과 인과를 담지 못한다. '쇠를 가열하면 팽창한다' 는 어떤 한 번의 일이 아니라 규칙성을 주장한다. $P\to Q$ 하나로는 그 '늘' 이 담기지 않는다. 9장의 한정사가 그 일부를 맡는다.

그렇다면 왜 실질함의를 쓰는가. 첫째, 논증에 쓰이는 조건문의 많은 부분이 정확히 '전건이 참인데 후건이 거짓인 일은 없다' 만 주장한다. 수학의 조건문이 거의 다 그렇고, 그 자리에서는 실질함의가 모자라지도 넘치지도 않는다.

둘째, 진리값만 보고 정하기로 마음먹으면 고를 여지가 거의 없다. 다르게 정하면 조건문이 이미 있는 다른 연결자와 같은 것이 되어 버린다. 정말 그런지는 6장에서 확인한다. 지금은 어긋남을 기억해 두는 것으로 충분하다.

뒤집히는 표현

조건문에서 실수가 가장 많이 나는 곳은 진리조건이 아니라 방향이다. 한국어의 여러 표현이 전건과 후건을 뒤집는다.

3장이 이 장에 넘긴 물음이 여기서 풀린다. '비가 오지 않으면 소풍을 간다' 와 '소풍을 가려면 비가 오지 않아야 한다' 는 같은 형식인가. $P$: 비가 온다. $Q$: 소풍을 간다 로 잡으면 앞의 것은 $\mathrm{\neg }P\to Q$ 이고 뒤의 것은 $Q\to \mathrm{\neg }P$ 다. 서로 다른 형식이고 어느 쪽도 다른 쪽을 함의하지 않는다. 한국어만 들여다봐서는 갈리던 물음이 기호로 옮기자마자 결말이 난다.

표를 외우는 것보다 요령 하나를 익히는 편이 낫다. 화살표는 언제나 충분조건에서 필요조건으로 간다. 없어서는 안 되는 쪽을 찾아 화살촉 자리에 놓으면 된다. 표 마지막 줄의 $\leftrightarrow$ 는 새 연결자가 아니라 두 방향의 조건문을 함께 주장하는 줄임이고, '필요충분조건' 과 '서로 같다' 가 모두 이 꼴로 간다.

옮기면서 잃는 것

앞의 절들에서 잃은 것들을 한자리에 모으자. 옮기기는 손실 압축이다. 무엇을 버릴지는 무엇을 판정하려는가가 정한다.

표의 넷째 줄을 정리해 두자. 문장이 말한 것(what is said)과 함축한 것(implicature)은 다르다. '커피나 차를 드릴게요' 는 둘 중 하나만 준다고 말하지 않았지만 그렇게 들린다. 이런 것을 화용적 함축(pragmatic implicature)이라 하고, 앞에서 본 취소 시험이 둘을 가른다. 논리는 말한 것만 옮긴다. 그러니 옮긴 뒤에 반드시 물어야 할 것이 있다. 버린 것이 이 판정에 영향을 주는가. 영향이 없으면 옮기기가 성공한 것이고, 영향이 있으면 원자를 다시 잡거나 더 센 도구로 옮겨야 한다.

괄호가 없으면 문장이 갈라진다

아래 문장을 읽어 보자 — 비가 오고 바람이 불거나 눈이 온다.

이 문장은 두 가지로 읽힌다. $P$: 비가 온다. $Q$: 바람이 분다. $R$: 눈이 온다 로 잡으면 이렇다.

• $P\wedge (Q\vee R)$ — 비는 반드시 오고, 거기에 바람이나 눈이 더해진다.
• $(P\wedge Q)\vee R$ — 비와 바람이 함께 오거나, 아니면 눈이 온다.

두 읽기는 서로 다른 문장이다. 비가 오지 않고 눈만 오는 상황을 생각하면 앞의 것은 거짓이고 뒤의 것은 참이다. 답이 갈리므로 같은 문장일 수 없다.

그림에서 두 읽기를 나무로 그렸다. 꼭대기에 선 연결자가 문장을 마지막으로 하나로 묶는 연결자이고, 그것을 주연결자(main connective)라 한다. 주연결자가 무엇이냐가 문장의 종류를 정한다 — 앞의 것은 논리곱 문장이고 뒤의 것은 논리합 문장이다. 이 이름을 따로 두는 까닭은 뒤에서 계속 쓰기 때문이다. 6장에서 진리값을 마지막에 계산하는 것이 주연결자이고, 7장에서 어떤 규칙을 쓸지 고를 때 보는 것도 주연결자다. 정확한 정의는 5장에서 한다.

자연어에는 괄호가 없다. 억양과 쉼표와 문맥이 그 일을 대신하지만 확실하지 않다. 그래서 형식 언어는 괄호를 강제한다. 애매하게 적을 방법을 아예 없애는 것이 5장 문법의 목적 가운데 하나다. 옮기는 사람이 지킬 원칙은 이것이다. 애매성은 없애지 말고 드러내라. 두 읽기를 다 적은 뒤 문맥으로 고르고, 골랐다는 사실을 밝혀 둔다. 조용히 하나를 고르면 나중에 그 선택이 어디서 왔는지 아무도 모른다.

옮기는 절차

지금까지의 규칙을 절차로 묶으면 이렇게 된다. 익숙해지기 전에는 여섯 단계를 눈으로 밟는 편이 빠르다.

1. 문장을 따로 떼어 적는다. 논증이면 전제와 결론을 줄줄이 늘어놓는다.
2. 논리 상항을 찾아 표시한다. 어미와 접사로 숨어 있는 것까지 찾는다.
3. 남은 조각을 원자로 잡고 사전을 적는다. 긍정형으로, 참·거짓을 물을 수 있는 문장으로.
4. 뼈대를 만든다. 조각만 글자로 바꾸고 연결은 아직 한국어로 둔다. '$P$ 가 아니면 $Q$ 가 아니다' 처럼.
5. 기호로 바꾸고 괄호를 넣는다. 애매하면 두 읽기를 다 적는다.
6. 되읽어 원문과 견준다. 어긋나면 세 번째 단계로 돌아간다.

네 번째 단계를 건너뛰고 싶어지지만 건너뛰지 않는 편이 좋다. 한국어 연결을 남긴 채 조각만 글자로 바꿔 놓으면 방향이 뒤집히는지 애매한지가 이 단계에서 눈에 들어온다. 여섯 번째 단계가 유일한 검사다. 기호식을 한국어로 되읽어 원문과 견주는 것이고, 이것 말고는 옮기기가 맞았는지 확인할 방법이 없다. 사전을 적어 두지 않으면 되읽을 수조차 없다.

이 장에서 새로 나온 것

용어와 기호부터 모은다.

판단 규칙으로는 아래를 얻었다.

이 장에서 기호를 썼지만 그 기호들이 무엇인지는 아직 정하지 않았다. 어떤 글자열이 문장이고 어떤 것이 아닌지, 괄호를 어떻게 붙이는지, 주연결자가 무엇인지 — 이것을 정하는 것이 5장이다. 그리고 이 장에서 미뤄 둔 불편함, 곧 조건문의 진리조건은 6장에서 결말이 난다.

명제논리의 문법

4장에서 우리는 자연어 문장을 기호로 옮겼다. 그 작업에는 늘 판단이 끼어들었다. 이 "그리고"는 $\wedge$ 인가 아니면 시간 순서를 말하는가, 이 문장은 어디까지가 가정인가, 이 대명사는 무엇을 가리키는가. 판단이 끼어든다는 것은 같은 문장을 두 사람이 다르게 옮길 수 있다는 뜻이다.

이 장은 방향을 뒤집는다. 옮겨 가는 쪽 — 목적지 언어 — 을 먼저 못 박는다. 어떤 기호열이 이 언어의 문장이고 어떤 것이 아닌지를, 뜻을 전혀 보지 않고 모양만으로 정한다. 그렇게 정하고 나면 옮기는 일에 여전히 판단이 남더라도, 옮겨 간 결과물에는 판단이 남지 않는다.

답할 질문은 셋이다. 어떤 기호열이 논리식인가, 그것을 애매함 없이 정할 수 있는가. 논리식 하나를 읽는 방법이 왜 정확히 하나뿐인가. 그리고 $P$ 와 $\phi$ 는 무엇이 다른가.

4장에서 가져오는 것은 연결자 다섯 개와 그 읽는 법뿐이다. 4장에서는 어느 연결자를 고를지를 뜻으로 판단했다. 이 장에서는 그 뜻을 한 번도 쓰지 않는다.

그래서 이 장에는 규율이 하나 있다. 어떤 논리식에 대해서도 참이라거나 거짓이라고 말하지 않는다. 진리값은 6장의 몫이고, 증명 가능성은 7장의 몫이다. 문법·의미론·증명 체계라는 세 층을 따로 세우고 나중에 그 사이의 관계를 정리로 증명하는 것이 이 문서 전체의 설계이며, 13장부터 17장까지가 그 정리들이다. 지금은 맨 아래층을 짓는다.

이 문서를 읽기 전에 Mathematics for Computer Science 를 읽은 사람이라면 진리표와 명제 대수를 이미 안다. 그 문서는 논리식을 ‘이미 있는 것’으로 놓고 그 뜻을 따졌다. 이 장은 그 앞자리를 채운다 — 논리식이라는 것이 애초에 무엇인지를 정한다.

왜 문법을 따로 정하는가

다음 한국어 문장을 보자. "비가 오고 바람이 불면 경기가 취소된다."

두 가지로 읽힌다. 비와 바람이 둘 다 있어야 취소되는 것일 수도 있고, 비가 오고 있는데 거기에 더해 바람이 불면 취소된다는 뜻일 수도 있다. 후자는 사실상 전자와 같지만, 문장 구조로 보면 "비가 온다"가 가정 안에 있는지 밖에 있는지가 다르다. 기호로 옮기면 그 차이가 드러난다. $P$ 를 "비가 온다", $Q$ 를 "바람이 분다", $R$ 을 "경기가 취소된다"로 두면 후보가 둘이다. 글자를 $P$, $Q$, $R$ 로 고른 것은 다음 절에서 문장문자를 그렇게 정하기 때문이고, 낱말의 머리글자를 따다 쓰지 않는 것이 이 문서의 약속이다.

$((P\wedge Q)\to R)\text{그리고}(P\wedge (Q\to R))$

이 둘은 서로 다른 기호열이다. 괄호의 자리가 다르다. 자연어에서는 이 차이가 억양이나 문맥에 숨지만, 기호에서는 숨을 곳이 없다.

그런데 여기서 한 걸음 더 나가야 한다. 괄호를 아예 빼고 $P\wedge Q\to R$ 라고만 적으면 어떻게 되는가. 이 기호열은 위의 두 식 중 어느 쪽인가. 이 물음에 답하려면 "무엇이 논리식인가"를 먼저 정해야 한다. 그것을 정하는 규칙의 모음을 그 언어의 문법(syntax)이라 한다.

문법이 갖춰야 할 조건은 둘이다. 첫째, 규칙이 유한해야 한다. 논리식은 무한히 많으므로 목록으로는 줄 수 없다. 둘째, 판정이 기계적이어야 한다. 어떤 기호열을 들고 왔을 때 논리식인지 아닌지를, 그 기호열의 뜻을 이해하지 않고도 정할 수 있어야 한다.

두 조건을 만족하는 언어를 형식 언어(formal language)라 한다. 어휘의 목록과 결합 규칙만으로 무엇이 문장인지가 정해지고, 뜻은 그 위에 따로 얹는 언어다. 프로그래밍 언어가 그렇고, 이제 세울 명제논리의 언어도 그렇다.

뜻을 따로 얹는 것이 왜 이득인가. 층을 나누면 층 사이의 관계를 정리로 물을 수 있기 때문이다. 이 문서가 세울 층은 셋이다.

아래 두 층은 같은 문법 위에 따로 세워진다. 한쪽이 다른 쪽을 참고하지 않는다. 그래서 "증명 체계로 얻을 수 있는 것과 의미론이 인정하는 것이 같은가"라는 물음이 뜻을 갖게 되고, 그 답이 13장(건전성)과 14장(완전성)이다. 층을 나누지 않았다면 물을 것이 없었을 것이다.

어휘 — 이 언어에 있는 기호

언어를 세우는 첫걸음은 쓸 수 있는 기호를 남김없이 적는 일이다. 그 목록을 어휘(vocabulary)라 한다. 명제논리의 어휘는 세 무리다.

첫째, 문장문자(sentence letter) $P,Q,R,P_1,P_2,P_3,\dots$ 다. 더 쪼개지 않는 원자 문장을 가리키는 기호이고, 무한히 많다. 아래첨자 번호를 쓰는 것은 필요하면 얼마든지 더 쓸 수 있게 하기 위해서다.

둘째, 연결자(connective) 다섯이다. $\mathrm{\neg }$ (부정), $\wedge$ (논리곱), $\vee$ (논리합), $\to$ (함의), $\leftrightarrow$ (동치). 각 연결자에는 항수(arity) — 재료로 받는 논리식의 개수 — 가 정해져 있다. $\mathrm{\neg }$ 만 1항이고 나머지 넷은 2항이다.

셋째, 괄호 $($ 와 $)$ 다. 괄호는 뜻을 가진 기호가 아니다. 뒤에서 보듯 어느 규칙이 어디에 쓰였는지를 종이에 남기는 구두점일 뿐이다.

이것이 전부다. 쉼표도 마침표도 빈칸도 어휘가 아니다.

어휘에 없는 것 가운데 셋만 미리 짚어 둔다.

• $\mathrm{\perp }$ (모순)은 지금 어휘에 없다. 7장에서 필요해지면 그때 어휘에 더한다. 어휘를 늘리는 일이 무엇인지는 다음 절의 정의를 보면 분명해진다 — 조항 하나를 더하는 일이다.
• $\mathrm{\forall }$ 와 $\mathrm{\exists }$ 는 9장에서 다른 언어를 세울 때 쓴다. 명제논리의 언어에는 없다.
• $\phi$, $\psi$, $\mathrm{\Gamma }$ 는 이 장에서 계속 쓰겠지만 어휘가 아니다. 논리식 안에 이 글자가 적히는 일은 없다. 왜 그런지가 이 장 마지막 절이다.

집합 기호 — 여기서 한 문단으로 정해 둔다

방금 예제에 $\{P,Q\}$ 가 나왔다. 이 중괄호 표기는 앞으로 계속 쓰인다 — 6장이 귀결을 정의할 때, 7장이 $\mathrm{\Gamma }⊢\phi$ 를 정의할 때, 10장이 해석을 정의할 때 모두 쓴다. 어려운 것이 아니므로 처음 쓰이는 자리인 여기서 정하고 넘어간다. 아래 기호들은 전부 메타언어의 표기이고 논리식 안에 들어가는 기호가 아니다.

집합(set)이란 무엇이 그 안에 있는지만으로 정해지는 모임이다. 안에 든 것 하나하나를 원소(element)라 한다. 원소를 다 적을 수 있으면 중괄호 안에 쉼표로 늘어놓는다. $\{P,Q\}$ 는 $P$ 와 $Q$ 를 원소로 갖는 집합이다. 논리식들의 집합에는 그리스 대문자 $\mathrm{\Gamma }$(감마)와 $\mathrm{\Delta }$(델타)를 이름으로 즐겨 쓴다. 필요한 기호는 넷뿐이다.

• $\in$ — 원소. $P\in \mathrm{\Gamma }$ 는 "$P$ 가 $\mathrm{\Gamma }$ 의 원소다"이고, 아니면 $P\notin \mathrm{\Gamma }$ 라 적는다
• $\subseteq$ — 부분집합. $\mathrm{\Gamma }\subseteq \mathrm{\Delta }$ 는 "$\mathrm{\Gamma }$ 의 원소가 전부 $\mathrm{\Delta }$ 의 원소다". 두 집합이 같아도 성립한다
• $\cup$ — 합집합. $\mathrm{\Gamma }\cup \mathrm{\Delta }$ 는 둘 중 어느 한쪽에라도 든 것을 모은 집합이다. $\mathrm{\Gamma }\cup \{\phi \}$ 처럼 원소 하나를 붙이는 데 특히 자주 쓴다
• $\mathrm{\varnothing }$ — 빈 집합. 원소가 하나도 없는 집합. $\{\}$ 라고 적어도 같은 것이다

덧붙일 것이 셋이다. 첫째, 순서와 되풀이는 셈하지 않는다. $\{P,Q\}$ 와 $\{Q,P\}$ 와 $\{P,Q,P\}$ 는 같은 집합이다. "무엇이 들어 있는지만으로 정해진다"는 말이 그 뜻이다. 둘째, 원소가 무한히 많아도 된다. 문장문자 전체의 모임도 집합이고, 그때는 원소를 다 적는 대신 말로 적는다. 셋째, 이 문서에 필요한 집합 기호는 위 넷이 전부다. 교집합이나 멱집합 같은 것은 나오지 않는다.

집합 말고도 수학의 도구가 몇 개 더 필요해지는데 전부 쓰이는 자리에서 꺼낸다. 함수는 6장이 배당을 정의할 때, 순서쌍과 관계는 10장이 해석을 정의할 때, 가산과 비가산은 15장이 모형의 크기를 셀 때 각각 그 자리에서 도입한다.

적형식 — 정의를 재귀로 세운다

어휘로 만들 수 있는 기호열은 무한히 많고, 그 대부분은 쓸모없다. $)\mathrm{\neg }(\wedge$ 도 어휘 안의 기호로만 이루어진 기호열이다. 우리는 그중 문장 노릇을 하는 것만 골라내야 한다. 골라낸 것을 적형식(well-formed formula, wff)이라 한다. 줄여서 논리식이라고도 부르겠다.

목록으로 줄 수는 없다. 적형식은 무한히 많기 때문이다. 그래서 만드는 방법을 준다. 정의는 세 조항이다.

• 기저. 모든 문장문자는 적형식이다.
• 재귀. $\phi$ 가 적형식이면 $\mathrm{\neg }\phi$ 도 적형식이다. $\phi$ 와 $\psi$ 가 적형식이면 $(\phi \wedge \psi )$, $(\phi \vee \psi )$, $(\phi \to \psi )$, $(\phi \leftrightarrow \psi )$ 도 적형식이다.
• 폐포. 위 두 조항을 유한 번 적용해 얻어지는 기호열만이 적형식이다.

여기서 $\phi$ 와 $\psi$ 는 "아무 적형식이나"라고 읽으면 된다. 이 글자들의 정확한 신분은 마지막 절에서 밝힌다.

괄호가 붙는 자리를 확인해 두자. 이항 조항은 결과 전체에 괄호를 한 쌍 두르고, $\mathrm{\neg }$ 조항은 두르지 않는다. $(\phi \wedge \psi )$ 이지 $\phi \wedge \psi$ 가 아니며, $\mathrm{\neg }\phi$ 이지 $(\mathrm{\neg }\phi )$ 가 아니다.

같은 정의를 한 줄로 압축해 적는 표기도 널리 쓰인다. 다른 책이나 프로그래밍 언어 명세에서 만나게 되므로 읽는 법만 익혀 두자.

$\phi ::=P\mid \mathrm{\neg }\phi \mid (\phi \wedge \phi )\mid (\phi \vee \phi )\mid (\phi \to \phi )\mid (\phi \leftrightarrow \phi )$

$::=$ 는 "다음 중 하나로 만들어진다"로, 세로줄은 "또는"으로 읽는다. 첫 갈래가 기저 조항이고 나머지 다섯이 재귀 조항이다. 한 갈래 안에 $\phi$ 가 두 번 나와도 두 자리를 같은 식으로 채우라는 뜻은 아니다. 각 자리를 따로 채운다. 그리고 폐포 조항은 이 표기에 적히지 않고 약속으로 숨어 있다 — 이 표기를 쓸 때는 늘 폐포가 함께 붙어 있다고 읽는다. 이 문서는 조항 이름을 부를 일이 많으므로 앞의 세 줄짜리 정의를 계속 쓴다.

이 정의가 왜 이런 모양인가

세 조항이 각각 다른 일을 한다. 하나씩 빼 보면 무슨 일을 하는지 드러난다.

기저를 빼면 아무것도 만들 수 없다. 재귀 조항은 "적형식이 있으면"으로 시작하므로, 처음부터 하나도 없으면 영원히 아무것도 나오지 않는다. 기저는 출발점을 준다.

재귀를 빼면 문장문자만 남는다. 재귀 조항은 유한한 규칙 다섯 개로 무한히 많은 대상을 덮는 장치다. 규칙이 다섯인 것은 연결자가 다섯이기 때문이고, 그중 하나만 모양이 다른 것은 $\mathrm{\neg }$ 만 1항이기 때문이다. 정의의 조항 개수는 어휘의 항수 표가 정한다.

폐포를 빼면 정의가 아무것도 배제하지 못한다. 이것이 가장 미묘한 자리다. 앞의 두 조항은 "이것들은 적형식이다"라고만 말하고 "저것은 적형식이 아니다"라고는 한 마디도 하지 않는다. 그러니 누군가 "$P\wedge \vee Q$ 도 적형식이다"라고 우겨도 두 조항 중 어느 것과도 충돌하지 않는다. 폐포 조항이 있어야 "두 조항으로 만들어지지 않았으므로 적형식이 아니다"라고 말할 수 있다.

그런데 폐포 조항의 값어치는 배제에 있지 않다. 진짜 값어치는 증명에 있다. 폐포 조항은 모든 적형식이 유한 번의 단계로 만들어졌다고 말한다. 그러면 적형식 전체에 대한 주장을 이렇게 증명할 수 있다 — 문장문자에서 성립하고, 재귀 조항 다섯 각각이 그 성질을 재료에서 결과로 물려준다는 것만 보이면 된다. 확인할 것이 여섯 가지로 끝나고, 그것으로 무한히 많은 식을 전부 덮는다.

이 증명 방법을 구조적 귀납법이라 하고, 13장에서 정식으로 세운다. 이 장에서는 그 증명을 하지 않는다. 다만 정의가 그 모양으로 서 있다는 것만 기억해 두자. 13장에서 건전성을 증명할 때, 14장에서 완전성을 증명할 때, 그 증명들의 뼈대는 전부 위의 세 조항을 그대로 베낀 것이 된다. 재귀적 정의를 잘 세우는 일이 나중 증명의 절반이다.

구성열 — 만들어 온 이력을 적는다

어떤 기호열이 적형식임을 보이려면 무엇을 내놓아야 하는가. 폐포 조항이 답을 준다. 기저에서 출발해 조항을 유한 번 적용한 이력을 내놓으면 된다.

정확히 적자. 기호열의 유한한 목록 ${\phi }_1,{\phi }_2,\dots ,{\phi }_n$ 이 구성열(construction sequence)이라는 것은, 각 ${\phi }_i$ 가 문장문자이거나 앞선 항들에 재귀 조항 하나를 적용한 결과라는 뜻이다. 목록의 마지막 항이 우리가 보이려던 기호열이면 증명이 끝난다.

논리식은 유한하고, 전부 세어 나갈 수 있다

폐포 조항에서 곧바로 따라 나오는 사실이 하나 더 있다. 모든 적형식은 유한한 기호열이다. 조항을 유한 번 적용해 만든 것이고, 조항 하나가 붙이는 기호는 많아야 세 개(연결자 하나와 괄호 둘)이기 때문이다. 그래서 이 언어에는 무한히 긴 연언 $P_1\wedge P_2\wedge P_3\wedge \cdots$ 같은 것이 아예 없다.

여기에 하나를 더 얹으면 15장에서 쓸 사실이 된다. 문장문자에 번호가 붙어 있으므로 기호 수가 같은 적형식들을 번호 순으로 늘어놓을 수 있고, 기호 수 자체도 $1,2,3,\dots$ 으로 늘어놓을 수 있다. 두 줄 세우기를 겹치면 적형식 전체에 $1,2,3,\dots$ 을 빠짐없이 붙일 수 있다. 이런 성질을 가진 모임을 셀 수 있다(가산, countable)고 한다. 이 장에서는 이 말을 딱 그 뜻으로만 쓴다. 정확한 정의는 15장에서 세우고, 익숙한 독자를 위해 덧붙이면 Mathematics for Computer Science 의 무한집합 장에 같은 논법이 있다.

주연결자와 부분식

적형식 하나를 손에 들었다고 하자. 그것을 만든 마지막 조항이 무엇이었는지 알 수 있는가. 알 수 있다. 그리고 그 답이 하나뿐이라는 것이 이 절의 핵심이다.

유일 가독성(unique readability). 모든 적형식은 정확히 한 가지 방식으로 만들어진다. 즉 마지막에 쓰인 조항과 그 조항이 쓴 재료가 하나로 정해진다.

이것은 정의에서 곧바로 나오는 것이 아니라 증명해야 하는 정리다. 정의는 "이렇게 만들면 적형식이다"라고만 말했지 "만드는 방법이 하나뿐이다"라고는 말하지 않았다. 증명에는 13장의 도구가 필요하므로 여기서는 결과만 쓴다. 다만 이 정리가 성립하는 이유가 괄호라는 것은 지금 확인해 둘 수 있다. 아래 그림이 그것이다.

마지막 조항이 쓴 연결자를 그 식의 주연결자(main connective)라 한다. 주연결자를 찾는 절차는 기계적이다. 맨 바깥 괄호가 있으면 그 안쪽에서, 왼쪽부터 괄호 깊이를 세며 — 여는 괄호에서 하나 올리고 닫는 괄호에서 하나 내린다 — 깊이 0인 자리에 있는 이항 연결자를 찾는다. 없고 맨 앞이 $\mathrm{\neg }$ 이면 그 $\mathrm{\neg }$ 가 주연결자다.

주연결자가 왜 중요한지는 뒤에서 계속 드러난다. 6장에서 식의 뜻을 계산할 때 어느 규칙을 쓸지 고르는 기준이 주연결자이고, 7장에서 증명 규칙을 고르는 기준도 주연결자다. 식을 보고 가장 먼저 해야 할 일이 주연결자를 찾는 일이라고 생각해도 좋다.

이 나무를 파스 트리(parse tree)라 한다. 마디마다 적형식이 하나씩 붙어 있고, 그 적형식들을 부분식(subformula)이라 한다. 정의도 재귀로 준다. $\phi$ 자신은 $\phi$ 의 부분식이고, $\phi$ 가 $\mathrm{\neg }\psi$ 꼴이면 $\psi$ 의 부분식이 모두 $\phi$ 의 부분식이며, $\phi$ 가 이항 조항으로 만들어졌으면 두 재료의 부분식이 모두 $\phi$ 의 부분식이다.

정의가 재귀면 그 위에 얹는 개념도 재귀가 된다. 이 패턴은 이 문서에서 계속 반복된다. 9장의 자유변수, 10장의 만족 관계, 13장의 건전성 증명이 모두 같은 모양으로 적힌다.

같은 방식으로 식의 복잡도도 정할 수 있다. 문장문자의 복잡도를 $0$ 이라 하고, 조항을 한 번 쓸 때마다 $1$ 을 올린다고 하면 — $\mathrm{\neg }\phi$ 의 복잡도는 $\phi$ 의 복잡도에 $1$ 을 더한 것이고, $(\phi \wedge \psi )$ 의 복잡도는 두 재료의 복잡도 중 큰 쪽에 $1$ 을 더한 것이다. 이 수는 파스 트리의 높이와 같다. 13장에서 "복잡도가 작은 식에서 성립하면 큰 식에서도 성립한다" 꼴로 증명을 꾸릴 때 이 수를 센다. 지금은 재귀적 정의 위에 이런 수를 얹을 수 있다는 것만 확인해 두면 된다.

괄호 생략 규약

정의를 곧이곧대로 지키면 괄호가 빨리 늘어난다. $(((P\wedge Q)\wedge R)\to S)$ 를 읽어 보면 알 수 있다. 그래서 종이 위에서는 괄호를 줄여 쓰는 관습을 함께 쓴다. 관습은 셋이다.

• 맨 바깥 괄호를 지운다. $(P\wedge Q)$ 를 $P\wedge Q$ 로 적는다.
• 결합 우선순위를 정한다. $\mathrm{\neg }$ 가 가장 세게 묶고, 다음이 $\wedge$, 그다음이 $\vee$, 그다음이 $\to$, $\leftrightarrow$ 가 가장 약하게 묶는다. 세게 묶는 것이 먼저 괄호를 갖는다.
• 같은 연결자가 이어지면 묶는 방향을 정한다. $\wedge$ 와 $\vee$ 는 왼쪽으로 묶고, $\to$ 와 $\leftrightarrow$ 는 오른쪽으로 묶는다.

여기서 반드시 짚어야 할 것이 있다. 이 셋은 문법이 아니다. 앞 절의 정의 어디에도 우선순위라는 조항이 없다. 정의는 이항 조항마다 괄호를 두르라고만 말한다. 그러므로

$P\wedge Q$ 는 적형식이 아니다. 그것은 적형식 $(P\wedge Q)$ 를 가리키는 줄임말이다.

이 구분을 흐리면 나중에 비싼 값을 치른다. 13장 이후에서 "모든 적형식에 대하여" 꼴의 주장을 증명할 때 확인할 조항이 여섯 개(기저 하나와 연결자 다섯)로 끝나는 것은 정의에 그것뿐이기 때문이다. 우선순위까지 조항으로 치면 확인할 것이 늘어나고, 늘어난 것들은 서로 겹쳐서 증명이 지저분해진다. 관습은 종이 위의 편의이고, 정의는 증명의 뼈대다.

결합 방향을 우리가 골랐다는 사실도 눈여겨보자. $\wedge$ 를 왼쪽으로 묶기로 한 것은 약속일 뿐이고, 오른쪽으로 묶기로 정한 책도 있다. 그래도 큰 탈이 없는 이유는 6장에서 밝혀진다 — 두 방식이 가리키는 두 적형식은 서로 다른 식이지만 뜻이 같다. 모양은 다르고 뜻은 같은 대표적인 자리다.

$\to$ 는 사정이 다르다. $(P\to (Q\to R))$ 와 $((P\to Q)\to R)$ 는 뜻도 다르다. 그래서 $\to$ 가 이어질 때는 규약이 정한 오른쪽 결합을 정확히 기억하고 있어야 하고, 조금이라도 헷갈리면 괄호를 남겨 두는 편이 낫다. 6장에서 두 식이 실제로 갈리는 배당을 보게 된다.

앞으로 이 문서는 이 규약을 줄곧 쓴다. 6장 이후 본문에 나오는 식들은 대부분 줄임말이고, 필요할 때만 괄호를 다 채워 적는다. 규약을 쓰는 것과 규약을 정의로 착각하는 것은 다른 일이다.

대상언어와 메타언어

이 장 내내 두 종류의 언어가 섞여 있었다. 이제 갈라 놓는다.

대상언어(object language)는 우리가 연구 대상으로 삼는 언어다. 여기서는 명제논리의 언어이고, 그 어휘는 앞에서 못 박은 것이 전부다 — 문장문자, 연결자 다섯, 괄호 둘.

메타언어(metalanguage)는 그 언어에 대해 말하는 데 쓰는 언어다. 여기서는 한국어이고, 거기에 몇 개의 기호를 보탰다. $\phi$, $\psi$, $\chi$ 는 적형식 하나를 가리키는 변수이고, $\mathrm{\Gamma }$, $\mathrm{\Delta }$ 는 적형식들의 집합을 가리키는 변수다. 이 다섯 글자를 메타변수라 부른다.

이제 자주 틀리는 세 가지를 짚는다.

첫째, $\phi$ 는 논리식이 아니다. 논리식을 가리키는 이름이다. $P$ 는 대상언어의 기호이므로 논리식 안에 실제로 적히지만, $\phi$ 라는 글자가 논리식 안에 적히는 일은 없다. 앞의 정의에서 "$\phi$ 가 적형식이면 $\mathrm{\neg }\phi$ 도 적형식이다"라고 적은 것은, 어떤 적형식을 가져오든 그 앞에 $\mathrm{\neg }$ 를 붙인 것이 적형식이라는 한국어 문장이었다.

둘째, $(\phi \wedge \psi )$ 는 적형식이 아니다. 적형식의 모양을 가리키는 표현이고, 이런 것을 도식(schema)이라 한다. 이 도식에 해당하는 적형식은 무한히 많다. $(P\wedge Q)$ 도, $(\mathrm{\neg }R\wedge (P\to Q))$ 도 그렇다. "주연결자가 $\wedge$ 인 적형식"이라고 길게 말하는 대신 도식으로 짧게 적는 것이다.

셋째, "$(P\wedge Q)$ 는 적형식이다"라는 문장은 대상언어의 문장이 아니다. 대상언어에는 "적형식"이라는 낱말이 없다. 어휘를 다시 보라 — 문장문자와 연결자와 괄호뿐이다. 그러니 이 문장은 한국어 문장, 곧 메타언어의 문장이다.

일상어에도 같은 구분이 있다. "서울"은 두 글자이고 서울은 도시다. 앞쪽은 낱말에 대한 말이고 뒤쪽은 도시에 대한 말이다. 논리식에서도 마찬가지다. $(P\wedge Q)$ 는 기호 다섯 개짜리 문자열이고, 그것이 무엇을 말하는지는 6장에서 따진다.

왜 이 구분이 13장부터 17장까지를 떠받치는가. 그 장들에서 증명하는 것이 전부 이 언어에 대한 주장이기 때문이다. 13장의 건전성은 "증명 체계로 얻을 수 있는 것은 의미론이 인정하는 것이다"라는 주장이고, 14장의 완전성은 그 역이다. 이 주장들은 대상언어로는 한 글자도 적을 수 없다. 대상언어에 "증명"이라는 표현도 "의미"라는 표현도 없기 때문이다. 그래서 이런 정리를 메타정리(metatheorem)라 부른다.

그리고 17장이 특별한 이유가 여기서 나온다. 괴델은 대상언어가 메타언어의 말을 흉내 내게 만든다. 산술의 언어 안에서 "이 식은 증명 가능하다"에 해당하는 논리식을 실제로 만들어 내는 것이 그 정리의 기술적 핵심이다. 두 층이 원래 갈라져 있다는 것을 지금 확실히 해 두어야 그때 무슨 일이 벌어지는지 보인다.

이 장에서 새로 나온 것

챙겨 갈 것은 넷이다.

• 적형식은 세 조항으로 정해진다. 기저가 출발점을 주고, 재귀가 유한한 규칙으로 무한을 덮고, 폐포가 밖을 잘라낸다. 판정의 근거로 늘 조항 이름을 대라.
• 괄호는 뜻이 없고 구조를 표시한다. 이항 조항이 두른 괄호 덕에 파스 트리가 하나로 정해진다. 괄호를 지운 것은 줄임말이고 적형식이 아니다.
• $P$ 는 대상언어이고 $\phi$ 는 메타언어다. 이 구분을 흐리면 13장 이후의 정리들이 무슨 주장인지 알 수 없게 된다.
• 모든 적형식은 유한하고, 적형식 전체는 셀 수 있다. 15장이 이 두 사실 위에 선다.

다음 장에서는 이 기호열들에 뜻을 준다. 문장문자마다 진리값을 하나씩 배당하고, 그 배당이 식 전체의 진리값을 어떻게 정하는지를 파스 트리를 따라 잎에서 뿌리로 올라가며 계산한다. 이 장에서 세운 재귀적 정의가 그 계산의 뼈대가 된다 — 조항마다 규칙을 하나씩 붙이면 그것이 의미론이다.

진리표와 진리함수적 의미론

5장은 어떤 기호열이 논리식인지를 정했다. 문법만 정한 것이라, 지금까지 $(P\wedge Q)\to \mathrm{\neg }R$ 은 규칙에 맞게 조립된 모양일 뿐 참도 거짓도 아니다. 이 장이 그 모양에 뜻을 준다. 문법에 뜻을 주는 부분을 의미론(semantics)이라 하고, 명제논리의 의미론은 놀랄 만큼 단순하다. 참과 거짓 두 값, 그리고 그 값을 어떻게 물려주는지에 관한 규칙 다섯 개가 전부다.

이 장에서 답할 질문은 넷이다.

• 논리식이 참이라거나 거짓이라는 말은 정확히 무슨 뜻인가
• 4장에서 억지 같다고 남겨 둔 $\mathrm{F}\to \mathrm{T}$ 가 왜 참인가
• 3장이 "상상할 수 있는 모든 상황"이라고만 말한 것을 어떻게 셀 수 있는 것으로 바꾸는가
• 진리표로 다 판정되는데 왜 7장의 증명 체계가 따로 필요한가

5장에서 가져오는 것은 셋이다. 문장문자 $P,Q,R$ 과 다섯 연결자 $\mathrm{\neg }\wedge \vee \to \leftrightarrow$, 괄호 생략 규약, 그리고 재귀적 정의다. 셋째가 이 장의 뼈대다. 5장이 "식을 어떻게 만드는가"를 재귀로 정했으니, 이 장은 "그렇게 만든 식의 값을 어떻게 정하는가"를 같은 재귀로 정한다. 5장의 조항 하나마다 값 계산 규칙 하나가 짝지어 붙는다.

진리표 자체는 처음이 아니다. Mathematics for Computer Science 5장이 진리표 채우기, 동치와 타당성과 만족가능성, 명제 대수 열두 규칙, DNF·CNF, SAT 를 이미 다룬다. 그것들을 다시 가르치지 않는다. 여기서 하는 일은 그 계산 절차 밑에 정의를 놓는 일이다. mcs 는 진리표를 계산 방법으로 다뤘지 진리표의 한 줄이 무엇인지는 정의하지 않았고, 논리식들 사이의 귀결 관계에 이름과 기호를 붙이지도 않았다. 그 둘이 이 장의 몫이다.

진리값 배당 — 진리표의 한 줄은 함수다

$P$ 가 참인지 거짓인지는 $P$ 만 보아서는 알 수 없다. 5장에서 정한 대로 문장문자는 속이 비어 있고, 무엇을 뜻하는지는 사전이 정한다. 그러니 의미론은 이렇게 출발할 수밖에 없다. 참·거짓을 밖에서 넣어 준다.

여기서 함수라는 말을 딱 필요한 만큼만 쓴다. 함수란 들어오는 것마다 나가는 것을 정확히 하나씩 짝지어 주는 규칙이다. 들어올 수 있는 것들의 모임을 정의역, 나갈 수 있는 것들의 모임을 공역이라 한다. 지금 필요한 것은 이 세 낱말뿐이고, 10장에서 훨씬 큰 함수를 다룰 때 제대로 다시 세운다.

정의를 적는다. 진리값 배당(valuation)이란 문장문자 전체의 집합을 정의역으로 하고 $\{\mathrm{T},\mathrm{F}\}$ 를 공역으로 하는 함수다. 배당을 $v$ 로 적고, $v$ 가 문장문자 $P$ 에 배정한 값을 $v(P)$ 로 적는다.

왜 하필 함수인가. 함수는 "하나마다 정확히 하나"를 요구한다. 그것이 우리가 원하는 것과 정확히 같다. 한 배당 안에서 $P$ 가 참이면서 동시에 거짓일 수는 없고(값이 둘일 수 없다), 값이 정해지지 않은 문자가 남아 있어서도 안 된다(값이 없을 수 없다). 진리표의 한 줄이 지켜야 할 규칙이 함수의 조건 그대로다.

그림의 오른쪽이 이 절의 요점이다. 진리표의 한 줄이 배당 하나다. 표를 채운다는 것은 여러 함수를 차례로 훑는 일이고, 문장문자가 $n$ 개면 배당은 $2^n$ 개다. 문자마다 두 가지 선택이 있고 선택끼리 서로 얽히지 않으니 곱해진다.

하나 더 밝혀 둘 것이 있다. 배당은 문장문자 전체에 값을 준다. 문장문자는 5장에서 $P,Q,R,P_1,P_2,\dots$ 로 끝없이 만들 수 있게 해 두었으므로 배당 하나가 정하는 값은 무한히 많다. 그런데 진리표는 몇 줄로 끝난다. 모순이 아니다. 어떤 식의 값은 그 식에 실제로 나오는 문장문자의 값에만 달려 있기 때문이다. 이 사실은 당연해 보이지만 증명이 필요한 사실이고, 그 증명은 식의 구조에 대한 귀납이라 13장의 도구를 쓴다. 여기서는 쓰기만 하고 갚는 것은 13장에서 한다.

연결자는 진리함수다 — 값은 구조를 따라 올라간다

배당은 문장문자에만 값을 준다. 나머지 식의 값을 정하려면 연결자가 값을 어떻게 물려주는지 정해야 한다. 진리함수(truth function)란 진리값 몇 개를 받아 진리값 하나를 내놓는 함수다. $\mathrm{\neg }$ 은 값 하나를 받아 하나를 내놓는 1항 진리함수, 나머지 넷은 값 둘을 받아 하나를 내놓는 2항 진리함수다. 각 연결자를 진리함수로 못 박는 것이 아래 표다. 이 표는 성질이 아니라 정의다.

$\mathrm{\neg }\phi$ 열은 $\psi$ 와 상관없으므로 위 두 줄과 아래 두 줄이 각각 같은 값이다.

확장 배당 — 5장의 조항마다 규칙 하나

이제 배당 $v$ 를 논리식 전체로 넓힌다. 넓힌 함수를 $\overline{v}$ 로 적고 확장 배당이라 부른다. 정의는 5장의 재귀적 문법을 그대로 따라간다.

• 기저 — 문장문자 $P$ 에 대해 $\overline{v}(P)=v(P)$
• $\mathrm{\neg }$ 조항 — $\overline{v}(\mathrm{\neg }\phi )$ 는 $\overline{v}(\phi )=\mathrm{F}$ 이면 $\mathrm{T}$, 아니면 $\mathrm{F}$
• $\wedge$ 조항 — $\overline{v}(\phi \wedge \psi )$ 는 $\overline{v}(\phi )$ 와 $\overline{v}(\psi )$ 가 둘 다 $\mathrm{T}$ 이면 $\mathrm{T}$, 아니면 $\mathrm{F}$
• $\vee$ 조항 — $\overline{v}(\phi \vee \psi )$ 는 둘 중 하나라도 $\mathrm{T}$ 이면 $\mathrm{T}$, 아니면 $\mathrm{F}$
• $\to$ 조항 — $\overline{v}(\phi \to \psi )$ 는 $\overline{v}(\phi )=\mathrm{T}$ 이고 $\overline{v}(\psi )=\mathrm{F}$ 이면 $\mathrm{F}$, 아니면 $\mathrm{T}$
• $\leftrightarrow$ 조항 — $\overline{v}(\phi \leftrightarrow \psi )$ 는 $\overline{v}(\phi )$ 와 $\overline{v}(\psi )$ 가 같으면 $\mathrm{T}$, 다르면 $\mathrm{F}$

5장의 문법 정의와 나란히 놓고 보라. 조항의 개수도 같고 순서도 같다. 문법이 식을 조립한 경로를 값 계산이 그대로 되짚는다. 5장이 "모든 적형식에는 그것을 만든 구성열이 있다"고 했으므로, 이 정의는 모든 적형식에 값을 하나씩 준다. 그리고 5장이 "괄호 덕분에 파스 트리가 하나로 정해진다"고 했으므로, 그 값도 하나로 정해진다. 문법에서 한 일이 여기서 값을 받는다.

이제 기호를 하나 도입한다. $\overline{v}(\phi )=\mathrm{T}$ 일 때 배당 $v$ 가 $\phi$ 를 만족한다고 말하고

$v\models \phi$

라고 적는다. 이 기호를 만족 관계라 부른다. 읽기는 "$v$ 는 $\phi$ 를 만족한다" 또는 "$\phi$ 는 $v$ 에서 참이다"다. $\models$ 는 5장의 낱말로 말하면 메타언어의 기호다. 논리식 안에 들어가는 기호가 아니라 논리식에 대해 우리가 하는 말을 줄여 적는 기호다. $\phi \to \psi$ 는 논리식이지만 $v\models \phi$ 는 논리식이 아니라 문장이다. 이 구분을 놓치면 이 문서의 나머지가 전부 흐려진다.

$\mathrm{F}\to \mathrm{T}$ 가 왜 참인가 — 이 장에서 가장 걸리는 곳

앞 표의 $\to$ 열이 유일하게 직관과 부딪히는 자리다. 4장에서 자연어 조건문을 화살표로 옮길 때 이 불편함을 남겨 두었다. 여기서 갚는다. 각도를 넷으로 나눠 본다.

각도 하나 — 진리함수로 쓰기로 한 이상 빈칸을 둘 수 없다

먼저 무엇을 이미 정했는지 확인하자. 우리는 $\to$ 를 진리함수로 쓰기로 했다. 그 말은 $\phi \to \psi$ 의 값이 $\phi$ 와 $\psi$ 의 진리값만으로 정해진다는 뜻이다. 두 값의 조합은 넷뿐이고, 넷 모두에 값을 정해야 정의가 끝난다. "전건이 거짓일 때는 말할 것이 없다"고 비워 두면 그것은 진리함수가 아니고, 그러면 $\to$ 가 든 식은 배당이 주어져도 값이 없는 식이 된다. 이 장 전체가 무너진다.

각도 둘 — 남은 칸을 다르게 채우면 이미 이름이 있는 것이 된다

다툼이 없는 줄이 둘 있다. $\mathrm{T}\to \mathrm{T}$ 는 $\mathrm{T}$, $\mathrm{T}\to \mathrm{F}$ 는 $\mathrm{F}$. 약속을 어긴 경우는 뒤쪽 하나뿐이라는 데는 누구도 반대하지 않는다. 그러면 고를 수 있는 자리는 전건이 거짓인 두 줄뿐이고, 채우는 방법은 네 가지다. 넷을 다 해 보면 답이 나온다.

그림이 말하는 바를 글로 옮기면 이렇다. 두 줄을 모두 $\mathrm{F}$ 로 채우면 그 연결자는 $\wedge$ 와 진리표가 똑같아진다. 그러면 $\phi \to \psi$ 를 주장하는 것이 $\phi$ 를 주장하는 것을 포함하게 되어, "지금 비는 안 오지만 비가 오면 땅이 젖는다" 같은 말을 아예 할 수 없다. 엇갈리게 채우면 $\leftrightarrow$ 가 되어 방향이 사라지거나, $\psi$ 자체가 되어 전건이 아무 구실도 하지 못한다. 새로운 연결자가 되는 채움은 하나뿐이다.

각도 셋 — 조건문은 "이 일은 일어나지 않는다"는 주장이다

$\phi \to \psi$ 가 무엇을 주장하는지 표에서 거꾸로 읽어 보자. 거짓이 되는 줄이 하나뿐이므로, 이 식은 정확히 이렇게 말한다. $\phi$ 가 참인데 $\psi$ 가 거짓인 일은 없다. 그 이상도 이하도 아니다. 그러면 전건이 거짓인 경우는 저절로 풀린다. 금지된 일이 일어나지 않았으므로 주장이 어겨지지 않았고, 어겨지지 않은 주장은 참이다. 이런 참을 공허하게 참(vacuously true)이라 한다. 공허하다는 것은 흠이 아니라 정확히 그만큼만 말했다는 뜻이다.

각도 넷 — 규칙과 사례

실무의 예가 이 채움을 강제한다. 어떤 시스템의 명세가 "조건 $i$ 이면 동작 $i$ 를 한다"는 규칙 열두 줄이라 하자. 명세 전체를 하나의 식으로 묶으려면 열두 조건문을 $\wedge$ 로 이어야 하는데, 지금 조건이 성립한 규칙이 둘뿐이라면 나머지 열 개도 참이 되어야 전체가 참이 된다. mcs 5장이 이 논증을 자세히 편다. 여기서는 결론만 가져온다 — 조건이 발동하지 않은 규칙을 "어기지 않은 것"으로 세지 않으면 규칙 여러 개를 한 식으로 묶는 일 자체가 안 된다.

마지막으로 잃은 것을 정직하게 적어 둔다. 실질함의에는 인과도 관련성도 들어 있지 않다. $\phi$ 가 거짓이기만 하면 $\phi \to \psi$ 는 $\psi$ 가 무엇이든 참이다. 억지라고 느끼는 것이 옳다. 그것을 담으려면 진리함수라는 틀 자체를 버려야 하고, 그 길이 18장의 양상논리와 19장의 관련성 논리다. 이 문서는 17장까지 진리함수의 틀 안에 머문다.

항진명제·모순·우연, 그리고 의미론적 귀결

한 논리식은 배당마다 값을 갖는다. 그러면 "모든 배당에서 어떤가"를 물을 수 있고, 그 물음의 답이 세 갈래로 갈린다.

• 항진명제(tautology) — 모든 배당에서 참인 식. $P\vee \mathrm{\neg }P$ 가 그렇다
• 모순(contradiction) — 모든 배당에서 거짓인 식. $P\wedge \mathrm{\neg }P$ 가 그렇다
• 우연(contingent) — 참인 배당도 있고 거짓인 배당도 있는 식. $P\to Q$ 가 그렇다

그리고 만족가능하다는 것은 참으로 만드는 배당이 하나라도 있다는 뜻이다. 항진명제와 우연인 식이 만족가능하고 모순은 아니다. 논리식의 집합에 대해서도 같은 말을 쓴다. $\mathrm{\Gamma }$ 가 만족가능하다는 것은 $\mathrm{\Gamma }$ 의 원소를 전부 한꺼번에 참으로 만드는 배당이 있다는 뜻이다. 하나씩 따로 참으로 만들 수 있는 것과는 다른 요구다.

두 식 $\phi$ 와 $\psi$ 가 모든 배당에서 같은 값을 가지면 논리적으로 동치라 한다. 동치인지 묻는 것은 $\phi \leftrightarrow \psi$ 가 항진명제인지 묻는 것과 같다. 값이 같다는 것이 곧 $\leftrightarrow$ 조항의 조건이기 때문이다. 4장이 판정을 미뤄 둔 두 물음이 여기서 끝난다. $\mathrm{\neg }\mathrm{\neg }P$ 와 $P$ 는 배당 두 개에서 값이 같으므로 동치이고, $\mathrm{\neg }(P\vee Q)$ 와 $\mathrm{\neg }P\wedge \mathrm{\neg }Q$ 도 배당 네 개에서 값이 같으므로 동치다(드모르간 법칙). 둘 다 표를 채우면 그 자리에서 확인된다.

여기서 낱말이 겹치는 것을 짚어 두어야 한다. mcs 5장은 모든 배정에서 참인 식을 "타당한 식"이라 부른다. 이 문서는 그렇게 하지 않는다. 3장이 논증에 대해 타당이라는 낱말을 이미 썼고, 논증과 식은 다른 것이기 때문이다. 이 문서에서 타당한 것은 논증이고, 식은 항진명제다. 마찬가지로 mcs 의 "일관적"은 여기서 "만족가능한 집합"이라 부른다. 일관성이라는 낱말은 7장 이후 증명 체계 쪽에 쓸 자리가 따로 있어 비워 둔다.

의미론적 귀결 $\mathrm{\Gamma }\models \phi$

이제 이 장의 중심 정의다. 3장은 좋은 논증을 "전제가 모두 참인데 결론이 거짓인 상황이 없는 것"이라 했고, 그때 상황이 무엇인지는 상상에 맡겼다. 명제논리 안에서는 상황이 곧 배당이다. 그러니 이렇게 적을 수 있다.

정의. $\mathrm{\Gamma }$ 를 논리식들의 집합, $\phi$ 를 논리식이라 하자. $\mathrm{\Gamma }$ 의 원소를 모두 참으로 만드는 배당이 전부 $\phi$ 도 참으로 만들면, $\phi$ 는 $\mathrm{\Gamma }$ 의 의미론적 귀결이라 하고

$\mathrm{\Gamma }\models \phi$

라고 적는다. 그렇지 않으면 $\mathrm{\Gamma }\models \phi$ 가 아니라고 한다. $\{{\phi }_1,{\phi }_2\}\models \psi$ 는 중괄호를 생략해 ${\phi }_1,{\phi }_2\models \psi$ 로도 적는다.

앞 절의 $v\models \phi$ 와 같은 기호를 쓴다. 헷갈릴 일은 없다. 왼쪽에 배당이 오면 만족이고 논리식 집합이 오면 귀결이다. 두 뜻이 이어져 있기도 하다 — $\mathrm{\Gamma }\models \phi$ 는 "$\mathrm{\Gamma }$ 를 만족하는 모든 $v$ 가 $\phi$ 도 만족한다"는 말이니, 귀결은 만족을 모든 배당에 대해 한 번 훑은 것이다.

그림 아래쪽이 중요하다. 귀결은 포함 관계다. 전제를 참으로 만드는 배당의 모임이 결론을 참으로 만드는 배당의 모임 안에 들어 있으면 귀결이고, 밖으로 삐져나온 칸이 하나라도 있으면 귀결이 아니다.

$\mathrm{\Gamma }$ 가 빈 집합인 경우를 따로 보자. 이때는 왼쪽을 아예 비워 $\models \phi$ 라고 적는다. 정의를 그대로 읽으면 "빈 집합의 원소를 모두 참으로 만드는 배당은 전부 $\phi$ 도 참으로 만든다"가 되는데, 빈 집합에는 원소가 없으므로 어떤 배당이든 그 조건을 공허하게 만족한다. 앞 절의 공허한 참이 여기서 다시 나온 것이다. 따라서 $\models \phi$ 는 "모든 배당이 $\phi$ 를 참으로 만든다"는 말, 즉 $\phi$ 가 항진명제다와 같은 말이다.

마지막으로 $\to$ 와 $\models$ 를 잇는 다리를 하나 놓는다. $\mathrm{\Gamma }\cup \{\phi \}\models \psi$ 인 것과 $\mathrm{\Gamma }\models \phi \to \psi$ 인 것은 같은 말이다. 이유는 짧다. $\mathrm{\Gamma }$ 를 만족하는 배당을 아무거나 잡았을 때, "$\phi$ 도 만족하면 $\psi$ 도 만족한다"는 것과 "$\phi \to \psi$ 를 만족한다"는 것이 $\to$ 조항에 의해 똑같은 조건이기 때문이다. 전제를 하나 왼쪽에서 오른쪽으로 옮겨 화살표로 바꿔도 되고 그 반대도 된다. 두 층을 잇는 이 다리는 7장에서 $\to$ 도입 규칙의 모습으로 다시 나타난다.