연역: 종합과 도전 과제

요약

이 수업은 연역을 다루는 단원을 마무리한다. 우카시에비치 체계의 정의(세 공리 도식과 전건 긍정식)에서 연역 정리와 부정논리합의 언어에서 이 체계가 갖는 한계로, 거기서 네 가지 기본 기법과 이 강좌의 체계를 완성하는 이중 부정 대체 규칙으로, 부정논리합의 기본 보조정리에서 동치 대체와 대칭성으로, 그리고 거기서 고전 논리의 규칙과 드모르간 법칙 및 분배 법칙으로 이어지는 연역의 사슬을 다시 세우면서, 고리마다 어떤 결과가 쓰이고 그것이 어느 수업에서 증명되는지를 짚는다. 단원이 증명한 것과 받아들인 것을 구별하고, 이룬 것을 강좌 계획에 비추어 자리매김하며, 단원이 열어 둔 물음, 곧 연역 가능한 것이 참인 것과 일치하는가 하는 물음이 왜 의미론 단원으로 이어지는지 설명한다. 마무리 평가에서는 입문 평가의 기능을 되풀이하며, 각 수업의 문제보다 어렵고 여러 수업의 도구를 엮어야 하는 여섯 개의 도전 과제로 끝맺는다.

학습 목표

단원의 결과들의 논리적 순서를 다시 세우고, 각 결과가 기대는 앞선 결과들과 그것이 증명되는 수업을 밝힌다.
연역 정리, 이중 부정, 이중 부정 대체 규칙, 대우, 기본 보조정리, 동치 대체가 어떻게 이어지는지, 그리고 왜 고전적 규칙들과 드모르간 법칙 및 분배 법칙이 이것들에 달려 있는지 설명한다.
단원이 증명한 것을, 받아들인 것(공리 도식, 두 기본 규칙, 강한 귀납법, 구조적 귀납법, 유일 판독성) 및 다음 단원들로 넘긴 것, 특히 연역과 참의 관계와 구별한다.
표지, 이중 부정 대체 규칙, 연역 정리, 경우에 따른 증명, 귀류법, 동치 대체, 드모르간 법칙과 분배 법칙을 엮는 문제를 푼다.

단원에서 이룬 것

이 단원은 앞 단원의 언어에 연역 체계를, 곧 논리식들로부터 다른 논리식을 얻는 순수하게 구문론적인 방법을 마련해 주고, 그 체계로 수학이 추론할 때 쓰는 기법들을 한 행씩 증명하는 것을 목표로 삼았다. 이 목표는 몇 가지 유보와 함께 이루어졌으며, 유보는 저마다 제자리에서 밝혔다. 세 공리 도식과 두 기본 규칙은 증명되는 것이 아니라 선택되는 것이고, 그 선택이 적절한지는 단원이 제기하되 완전히 답하지는 않은 물음이다. 강한 귀납법, 구조적 귀납법, 유일 판독성, 재귀에 의한 정의는 앞 단원에서 증명되었고 여기서 쓰인다. 그리고 집합론의 필수적인 부분(부분집합, 합집합, 유한 집합)은 필요한 곳에서 상기했다. 이 유보 아래에서, 지나온 길은 네 구간으로 된 하나의 연역의 사슬로 읽을 수 있다.

우카시에비치 체계와 그 한계

형식 연역 체계에 관한 수업은 체계를 언어, 몇몇 공리, 몇몇 규칙으로 정의했으며, 이것들은 모두 기호열만 보고 확인할 수 있다. 그리고 이 강좌의 체계의 첫 단계인 우카시에비치 체계를 정했다. 도식 A1, A2, A3과 유일한 규칙으로서의 전건 긍정식이며, 유일 판독성 덕분에 이 규칙은 모호함 없이 적용된다. 이 수업은 전제 집합 $\Gamma$ 로부터의 연역과 관계 $\Gamma \vdash \varphi$ 를 정의하고, $\vdash (\varphi \rightarrow \varphi)$ 를 다섯 행으로 연역했으며, 구조적 성질, 곧 반사성, 단조성, 연역 사이의 전건 긍정식, 절단, 유한성을 증명했다. 이것들과 행 수에 관한 강한 귀납법으로 연역 정리와 그 역을 증명했는데, 연역 정리의 둘째 경우는 $(\varphi \rightarrow \varphi)$ 식을 미리 연역해 두어야 한다. 이것들로부터 반사적이고 대칭적이며 추이적인 증명 가능한 동치를 얻었다. 끝으로 이 체계의 한계를 세웠다. 값 $0$ 과 $1$ 을 갖는 표지는 기본 꼴 $(\alpha \downarrow \beta)$ 위에서 재귀로 정의되며, 부정과 함의를 늘 하던 대로 다루고, A1, A2, A3과 전건 긍정식에 의해 보존되며, $(v_{1} \downarrow v_{2})$ 같은 논리식의 값은 자유롭게 남겨 둔다. 이로부터 $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ 은 우카시에비치 체계의 정리가 아니며, $(v_{1} \downarrow v_{2})$ 에서 $(\neg\neg v_{1} \downarrow v_{2})$ 식은 연역되지 않고, 그 반대도 마찬가지이다. 모든 표지가 $\theta$ 와 $\neg\neg\theta$ 에 같은 값을 주므로, 이 수업은 이중 부정조차 증명된다 해도 이 한계를 없애지 못한다는 점도 지적했다.

네 가지 기법과 새 규칙

네 가지 연역 기법에 관한 수업은 먼저 「결과에서 규칙으로」 보조정리를 증명했다. $\{\alpha_{1}, \ldots, \alpha_{n}\} \vdash \beta$ 이면, 같은 결론은 임의의 집합 $\Gamma$ 로부터도 얻어진다. 단, 그 집합이 각 $\alpha_{i}$ 식을 연역해야 한다. 나아가 $\vdash (\alpha_{1} \rightarrow (\alpha_{2} \rightarrow \cdots (\alpha_{n} \rightarrow \beta) \cdots))$ 이다. 각 기법을 세 가지 모습(전제로부터, 정리로서, 규칙으로서)으로 쓸 수 있게 해 주는 것이 바로 이 보조정리이며, 대칭성에 관한 수업과 드모르간에 관한 수업은 동치의 사슬을 절단과 엮는데, 그러기 위해 첫 수업의 증명 가능한 동치의 성질에 기댄다. 이것은 같은 생각을 하나의 전제에 적용한 것이다. 사슬에서 각 결과는 그것이 증명되는 곳에 한 번만 나온다. 이 보조정리로 이 수업은 A1과 A2로부터 일곱 행으로 가언 삼단논법을, 연역 정리로 전제 교환을, 이중 부정을(그 첫째 방향은 A1로 만든 함의에 A3을 두 번 적용하고, 둘째 방향은 첫째 방향을 $\neg\varphi$ 에 적용하고 A3을 쓴다), 그리고 세 형태의 대우를 연역했다. 세 형태는 함의의 부정들을 세 가지 방식으로 나눈다. 이 네 가지는 이미 우카시에비치 체계에서 성립한다.

이중 부정을 증명한 뒤, 이 수업은 둘째 기본 규칙인 이중 부정 대체(RDN)로 이 강좌의 체계를 완성했다. $\chi$ 식에서 $\chi'$ 식을 추론하는 것은, $\chi'$ 식이 $\chi$ 식에서 부분식 $\theta$ 의 한 출현을 $\neg\neg\theta$ 식으로, 또는 $\neg\neg\theta$ 식의 한 출현을 $\theta$ 식으로 바꾸어 얻어질 때이다. 이 규칙은 공준으로 세워야 한다. 표지 $m_{1}$ 식은 이중 부정의 정리들에 $1$ 값을 주면서도 $(v_{1} \downarrow v_{2})$ 식과 $(\neg\neg v_{1} \downarrow v_{2})$ 식을 갈라놓기 때문이다. RDN은 $m_{1}$ 식을 보존하지 않으므로 연역 가능한 것을 넓히지만, 정직한 표지는 보존하므로 지나치게 넓히지는 않는다. 규칙은 기본 언어의 기호열에 작용하며, 거기서 부정은 그 인자를 이중으로 만든다. $(\varphi \rightarrow \psi)$ 는 부분식 $\neg\varphi$ 식을 두 번 담고 있으며, 그 전건 앞에 이중 부정을 붙이려면 두 번 적용해야 한다. 같은 관찰이 연역 정리의 확장을 받쳐 준다. 어떤 행이 규칙으로 얻어지면, 귀납 가정은 후건이 바로 앞 행인 함의를 주고, 그 후건의 사본마다 한 번씩 규칙을 두 번 적용하면 구하는 함의가 나온다. 나머지 구조적 성질은 같은 증명으로 성립한다. 첫 귀결은, 논리식은 규칙에 의해 그것으로부터 얻어지는 모든 논리식과 동치라는 것, 특히 $(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi)$ 와 $(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi)$ 라는 것, 그리고 다른 체계들이 공리로 삼는 해당 함의들이 여기서는 정리라는 것이다.

연결사와 대체

연결사의 대칭성에 관한 수업은 원과 원판의 언어에 고유한 어려움에 맞섰다. 우카시에비치의 공리는 부정과 함의에 대해서만 말하는데, 부정논리합은 거의 어느 것도 그 둘 중 어느 하나가 아니다. 기본 보조정리 $(\varphi \downarrow \psi) \dashv\vdash \neg(\neg\varphi \rightarrow \psi)$ 가 다리를 놓는다. $\neg(\neg\varphi \rightarrow \psi)$ 식은 $\neg\neg(\neg\neg\varphi \downarrow \psi)$ 식이므로, RDN 규칙이 안쪽 이중 부정을 붙이고 이중 부정이 바깥쪽 이중 부정을 붙인다. 반대 방향으로는 이중 부정과 규칙이 그것들을 뗀다. 이것으로 동치 대체는, 먼저 부정 아래와 함의의 양쪽에서 대우와 가언 삼단논법으로 증명된 뒤, 부정논리합의 두 인자로, 다시 거기서 선언과 연언으로 확장되었다. 규칙과 대체는 서로를 쓸모없게 만들지 않는다. 규칙은 $\theta$ 와 $\neg\neg\theta$ 를 맞바꿀 뿐이지만, 대체는 임의의 동치인 논리식을 허용한다. 그리고 기본 보조정리로 증명된 대체는 다시 규칙에 기댄다. 이 수업은 이어서, 다른 책들이 정의로 삼는 형식들이 동치라는 것을 증명했다. $(\varphi \vee \psi) \dashv\vdash (\neg\varphi \rightarrow \psi)$ 는 바깥 부정이 만드는 사본마다 한 번씩 규칙을 두 번 적용해야 하고, $(\varphi \wedge \psi) \dashv\vdash (\neg\varphi \downarrow \neg\psi)$ 는 이중 부정을 필요로 한다. 반면에 $(\varphi \wedge \psi)$ 와 $\neg(\varphi \rightarrow \neg\psi)$ 는 같은 기호열이다. 끝으로 정의가 정하는 순서대로 다섯 대칭성을 증명했다. 부정논리합의 대칭성은 기본 보조정리와 대우로, 나머지는 각각 바로 앞의 것으로 증명하고, 필요할 때는 부정 아래의 대체로 옮긴다.

고전적 규칙과 법칙

고전 논리의 기법에 관한 수업은, 모두 행에서 행으로 이어지는 전제 집합 $\Gamma$ 아래에서, 선언과 연언의 도입과 제거, 배중률과 무모순율, 폭발 원리, 두 형태의 귀류법, 그리고 논리식과 그 부정에 의한 경우에 따른 증명과 임의의 선언에 의한 경우에 따른 증명을 증명했다. 의존 순서는 엄격하다. 폭발 원리는 선언의 규칙에, 고전적 귀류법은 폭발 원리와 A3에, 경우에 따른 증명은 대우와 귀류법에 기댄다. 이 증명들 가운데 어느 것도 RDN 규칙을 직접 끌어들이지 않는다. 규칙은 동치 형식과 동치 대체를 통해 작용한다. 드모르간 법칙과 분배 법칙에 관한 수업은 이 규칙들을 함께 일하게 했다. 드모르간 제1법칙은 연언의 정의와 이중 부정에서 나온다. 제2법칙은 부정논리합 안으로 들어가야 하며, 거기서 RDN 규칙이 인자마다 한 번씩, 대칭성 없이 두 번 개입한다. 그리고 이로부터 $(\varphi \downarrow \psi)$ 식이 $(\neg\varphi \wedge \neg\psi)$ 식과 동치라는 것, 곧 앞 단원이 약속으로 정한 읽기 「 $\varphi$ 도 $\psi$ 도 아니다」가 따라 나온다. 변형에는 $\neg(\varphi \rightarrow \psi) \dashv\vdash (\varphi \wedge \neg\psi)$ 도 들어 있다. 두 분배 법칙은 경우에 따른 증명으로 두 방향 모두 증명되었으며, 방향마다 알맞은 형태의 경우에 따른 증명을 골랐다.

다음 그림은 네 구간을 하나의 사슬로 모은 것이다. 가운데 열의 각 마디는 정의나 결과이며, 논리적 순서에 따라 번호가 붙고, 그 증명이 쓰는 앞의 고리들과 호로 이어진다. 그 둘레에 떠 있는 것이 받침, 곧 사슬이 거듭 의지하는 원리와 도구이다. 각 받침은 자신에게 기대는 고리들과 실선으로, 자신이 세워지는 고리와 점선으로 이어지며, 이 사슬이 증명하지 않는 받침(받아들이는 공리 도식과 앞 단원의 도구)은 둥근 테로 그려진다. 이중 부정 대체 규칙은 역시 증명 없이 받아들이지만, 그것을 도입하는 고리와 이어져 있다. 거기서 그것을 왜 공준으로 세워야 하는지 설명하기 때문이다. 받침을 누르면 그것을 쓰는 고리가 모두 강조되고, 각 고리는 그것이 증명되는 수업으로 이어진다. 연역 정리와 이중 부정이 공리 다음으로 단원에서 가장 자주 쓰이는 받침이라는 점, 그리고 새 규칙이 단원이 부정논리합에 대해 말하는 모든 것, 곧 확장된 연역 정리, 기본 보조정리, 동치 형식, 드모르간 제2법칙을 받친다는 점에 주목하자.

사슬의 받침

A유일 판독성과 재귀. $\sigI\varphi\psi = \sigI\varphi'\psi'$ 이고 네 기호열이 모두 논리식이면, $\varphi = \varphi'$ 이고 $\psi = \psi'$ 이다. 따라서 $\sigI\varphi\psi$ 식의 값을 $\varphi$ , $\psi$ 와 그 값들로부터 계산하는 규칙은 논리식 위의 단 하나의 함수를 정의한다. 앞 단원에서 증명했다. 이 단원에서는 증명 없이 받아들인다.
B강한 귀납법. 어떤 성질이, 한 자연수보다 작은 모든 자연수에 대해 성립할 때마다 그 자연수에 대해 성립하면, 그 성질은 모든 자연수에 대해 성립한다. 앞 단원에서 단순한 귀납법으로부터 연역했으며, 여기서는 연역의 행 수에 적용한다. 이 단원에서는 증명 없이 받아들인다.
C우카시에비치의 공리. 도식 A1은 $(\varphi \rightarrow (\psi \rightarrow \varphi))$ , A2는 $((\varphi \rightarrow (\psi \rightarrow \chi)) \rightarrow ((\varphi \rightarrow \psi) \rightarrow (\varphi \rightarrow \chi)))$ , A3은 $((\neg\psi \rightarrow \neg\varphi) \rightarrow (\varphi \rightarrow \psi))$ 이다. 받아들인다. 이 단원에서는 증명 없이 받아들인다.
D이중 부정 대체. 이 강좌의 체계의 둘째 기본 규칙. $\chi$ 식에서 $\chi'$ 식을 추론하는 것은, $\chi'$ 식이 $\chi$ 식에서 부분식 $\theta$ 의 한 출현을 $\neg\neg\theta$ 식으로, 또는 $\neg\neg\theta$ 식의 한 출현을 $\theta$ 식으로 바꾸어 얻어질 때이다. 이중 부정을 증명한 뒤에 공준으로 세운다. 확립되는 곳: 8. 이중 부정 대체.
E연역 정리. $\Gamma \cup \{\varphi\} \vdash \psi$ 일 때 그리고 그때에만 $\Gamma \vdash (\varphi \rightarrow \psi)$ 이다. 우카시에비치 체계에서 증명되며, 이 강좌의 체계에서도 경우를 하나 더하여 성립한다. 확립되는 곳: 3. 연역 정리와 증명 가능한 동치.
F결과에서 규칙으로. $\{\alpha_{1}, \ldots, \alpha_{n}\} \vdash \beta$ 이고 $\Gamma \vdash \alpha_{i}$ 식이 각 $i$ 에 대해 성립하면, $\Gamma \vdash \beta$ 이다. 전제로부터 증명된 모든 기법은 임의의 전제 집합 아래에서 적용된다. 확립되는 곳: 5. 결과에서 규칙으로.
G이중 부정. $\varphi \dashv\vdash \neg\neg\varphi$ . 정리 $\vdash (\neg\neg\varphi \rightarrow \varphi)$ 와 $\vdash (\varphi \rightarrow \neg\neg\varphi)$ 를 함께 갖는다. 확립되는 곳: 7. 이중 부정.
H동치 대체. $\varphi \dashv\vdash \varphi'$ 식이 성립하면, $\varphi'$ 식을 $\varphi$ 대신 놓을 수 있다. 부정 아래에서, 그리고 함의, 부정논리합, 선언, 연언의 양쪽에서, 동치를 해치지 않고 그렇게 할 수 있다. 확립되는 곳: 12. 동치 대체.

제1구간 우카시에비치 체계와 그 한계
- 도식의 대입례를 알아보고, 논리식의 나열이 어떤 전제 집합으로부터의 연역인지 판정한다.
- 연역의 구조적 성질과 연역 정리를 행 수에 관한 강한 귀납법으로 증명한다.
- 반사성, 단조성, 절단, 연역 정리와 그 역으로 연역에 관한 연역을 세운다.
- 공리와 전건 긍정식이 보존하는 표지로 어떤 논리식이 연역되지 않음을 증명하고, 그것으로 우카시에비치 체계의 한계를 설명한다.
1. 체계, 연역, 동일률. 우카시에비치 체계의 공리는 A1부터 A3까지의 균일 대입례이며, 유일한 규칙은 전건 긍정식이다. $\Gamma \vdash \varphi$ 라는 것은, $\varphi$ 로 끝나는 논리식들의 유한한 나열이 있어서 그 각 논리식이 공리이거나, $\Gamma$ 의 원소이거나, 앞의 두 논리식에서 전건 긍정식으로 얻은 것이라는 뜻이다. 첫 정리 $\vdash (\varphi \rightarrow \varphi)$ 는 A1과 A2로 다섯 행에 연역된다.
  받침: A (유일 판독성과 재귀), C (우카시에비치의 공리). 증명된 수업: 형식 연역 체계.
2. 구조적 성질. $\varphi \in \Gamma$ 이면 $\Gamma \vdash \varphi$ 이다. $\Gamma \subseteq \Delta$ 이고 $\Gamma \vdash \varphi$ 이면 $\Delta \vdash \varphi$ 이다. $\Gamma \vdash \varphi$ 와 $\Gamma \vdash (\varphi \rightarrow \psi)$ 에서 $\Gamma \vdash \psi$ 가 따라 나온다. $\Gamma \vdash \varphi_{i}$ 식이 각 $i$ 에 대해 성립하고 $\Gamma \cup \{\varphi_{1}, \ldots, \varphi_{r}\} \vdash \psi$ 이면 $\Gamma \vdash \psi$ 이다. 그리고 $\Gamma \vdash \varphi$ 이면 $\Gamma$ 의 어떤 유한 부분집합으로 충분하다.
  사용: 1. 체계, 연역, 동일률. 증명된 수업: 형식 연역 체계.
3. 연역 정리와 증명 가능한 동치. $\Gamma \cup \{\varphi\} \vdash \psi$ 일 때 그리고 그때에만 $\Gamma \vdash (\varphi \rightarrow \psi)$ 이며, 행 수에 관한 강한 귀납법으로 A1, A2와 동일률을 써서 증명한다. 이로부터 증명 가능한 동치 $\varphi \dashv\vdash \psi$ 는 반사적이고 대칭적이며 추이적이고, 동치인 두 논리식은 같은 집합들로부터 연역된다.
  사용: 1. 체계, 연역, 동일률, 2. 구조적 성질. 받침: B (강한 귀납법), C (우카시에비치의 공리). 증명된 수업: 형식 연역 체계.
4. 우카시에비치 체계의 한계. 재귀로 정의된, 값 $0$ 과 $1$ 을 갖는 표지는 $m(\neg\varphi) = 1 - m(\varphi)$ 식과 $m((\varphi \rightarrow \psi)) = 1 - m(\varphi) \left( 1 - m(\psi) \right)$ 식을 만족하며, A1, A2, A3과 전건 긍정식은 표지 $1$ 값을 보존한다. 따라서 $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ 은 우카시에비치 체계의 정리가 아니고, $\{(v_{1} \downarrow v_{2})\} \nvdash (\neg\neg v_{1} \downarrow v_{2})$ 이며, 그 반대도 성립하지 않는다. 모든 표지가 이중 부정에 $1$ 값을 주므로, 대체는 공준으로 세워야 한다.
  사용: 1. 체계, 연역, 동일률. 받침: A (유일 판독성과 재귀), B (강한 귀납법), C (우카시에비치의 공리). 증명된 수업: 형식 연역 체계.
제2구간 네 가지 기법과 새 규칙
- 전제로부터의 결과를 정리로, 그리고 임의의 전제 집합 아래에서 적용되는 규칙으로 바꾼다.
- 함의를 잇고, 전건의 순서를 바꾸고, 이중 부정을 붙이거나 떼고, 각 함의에 맞는 대우의 형태를 고른다.
- 이중 부정 대체 규칙을 적용하되, 약어가 감추는 출현을 찾아내고 부정이 만드는 사본마다 되풀이한다.
- 규칙을 왜 공준으로 세우는지 표지로 설명하고, 연역 정리가 그 규칙과 함께 성립함을 증명한다.
1. 결과에서 규칙으로. $\{\alpha_{1}, \ldots, \alpha_{n}\} \vdash \beta$ 이면, $\Gamma \vdash \alpha_{1}$ , $\ldots$ , $\Gamma \vdash \alpha_{n}$ 에서 $\Gamma \vdash \beta$ 가 따라 나오고, 또 $\vdash (\alpha_{1} \rightarrow (\alpha_{2} \rightarrow \cdots (\alpha_{n} \rightarrow \beta) \cdots))$ 이다. 특히 $\alpha \dashv\vdash \alpha'$ 이면, $\Gamma \vdash \alpha$ 일 때 그리고 그때에만 $\Gamma \vdash \alpha'$ 이다.
  사용: 2. 구조적 성질. 받침: E (연역 정리). 증명된 수업: 네 가지 연역 기법.
2. 가언 삼단논법과 교환. $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\} \vdash (\varphi \rightarrow \chi)$ . A1과 A2로부터의 일곱 행의 연역에 의한다. 그리고 $\{(\varphi \rightarrow (\psi \rightarrow \chi))\} \vdash (\psi \rightarrow (\varphi \rightarrow \chi))$ .
  사용: 1. 체계, 연역, 동일률. 받침: C (우카시에비치의 공리), E (연역 정리), F (결과에서 규칙으로). 증명된 수업: 네 가지 연역 기법.
3. 이중 부정. $\vdash (\neg\neg\varphi \rightarrow \varphi)$ 는 A1이 $\neg\neg\varphi$ 식으로부터 만드는 함의에 A3을 두 번 적용하여 얻고, $\vdash (\varphi \rightarrow \neg\neg\varphi)$ 는 앞의 결과를 $\neg\varphi$ 식에 적용하고 A3을 써서 얻는다. 따라서 $\varphi \dashv\vdash \neg\neg\varphi$ 는 이미 우카시에비치 체계에서 성립한다.
  받침: C (우카시에비치의 공리), E (연역 정리). 증명된 수업: 네 가지 연역 기법.
4. 이중 부정 대체. RDN 규칙을 공준으로 세운다. 표지는 이중 부정에는 $1$ 값을 주지만, 부정논리합 안에서의 대체에는 그렇게 하지 않기 때문이다. $\chi'$ 식이 $\chi$ 식에서 규칙으로 얻어지면 $\chi \dashv\vdash \chi'$ 이다. 특히 $(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi)$ 와 $(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi)$ 이다.
  사용: 3. 연역 정리와 증명 가능한 동치, 4. 우카시에비치 체계의 한계. 받침: G (이중 부정). 증명된 수업: 네 가지 연역 기법.
5. 이 강좌의 체계에서의 연역 정리. 반사성, 단조성, 절단, 유한성은 새 규칙과 함께 성립하며, $\Gamma \cup \{\varphi\} \vdash \psi$ 일 때 그리고 그때에만 $\Gamma \vdash (\varphi \rightarrow \psi)$ 라는 것도 성립한다. 새 경우에서 $(\varphi \rightarrow \chi)$ 는 $((\neg\varphi \downarrow \chi) \downarrow (\neg\varphi \downarrow \chi))$ 이므로, 규칙은 $\chi$ 의 사본마다 한 번씩 두 번 적용된다. 이로부터 $\vdash ((\varphi \downarrow \psi) \rightarrow (\neg\neg\varphi \downarrow \psi))$ 와 그 역은 정리이다.
  사용: 2. 구조적 성질, 3. 연역 정리와 증명 가능한 동치. 받침: B (강한 귀납법), D (이중 부정 대체). 증명된 수업: 네 가지 연역 기법.
6. 대우. $(\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \neg\varphi)$ , $(\neg\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \varphi)$ , $(\varphi \rightarrow \neg\psi) \dashv\vdash (\psi \rightarrow \neg\varphi)$ . 항들은 자리를 바꾸고, 넘어가면서 각각 부호를 바꾼다.
  사용: 6. 가언 삼단논법과 교환. 받침: C (우카시에비치의 공리), E (연역 정리), G (이중 부정), F (결과에서 규칙으로). 증명된 수업: 네 가지 연역 기법.
제3구간 연결사와 대체
- 약어를 펼쳐, 두 표현이 같은 기호열을 가리키는지, 아니면 동치임을 보이는 데 연역이 필요한 논리식들을 가리키는지 판정한다.
- 기본 보조정리로 부정논리합을 부정과 함의로 옮긴다.
- 동치 대체로 동치를 논리식의 내부로 옮기고, 그것을 이중 부정 대체 규칙과 구별하며, 동치들을 잇는다.
- 정의가 정하는 순서대로 다섯 대칭성을 증명한다.
1. 기본 보조정리. $(\varphi \downarrow \psi) \dashv\vdash \neg(\neg\varphi \rightarrow \psi)$ . $\neg(\neg\varphi \rightarrow \psi)$ 식은 $\neg\neg(\neg\neg\varphi \downarrow \psi)$ 식이므로, RDN 규칙이 안쪽 이중 부정을 붙이고 이중 부정이 바깥쪽 이중 부정을 붙인다. 반대 방향으로는 이중 부정과 규칙이 그것들을 뗀다.
  받침: D (이중 부정 대체), G (이중 부정). 증명된 수업: 연결사의 대칭성.
2. 동치 대체. $\varphi \dashv\vdash \varphi'$ 식이 성립하면 $\neg\varphi \dashv\vdash \neg\varphi'$ , $(\varphi \rightarrow \psi) \dashv\vdash (\varphi' \rightarrow \psi)$ , $(\psi \rightarrow \varphi) \dashv\vdash (\psi \rightarrow \varphi')$ 이다. 기본 보조정리를 쓰면 부정논리합의 양쪽에서도 같고, 거기서 선언과 연언에서도 같다. RDN 규칙과 달리, 임의의 동치인 논리식을 허용한다.
  사용: 6. 가언 삼단논법과 교환, 10. 대우, 11. 기본 보조정리. 받침: E (연역 정리). 증명된 수업: 연결사의 대칭성.
3. 동치 형식. $(\varphi \vee \psi) \dashv\vdash (\neg\varphi \rightarrow \psi)$ 는 바깥 부정이 만드는 사본마다 한 번씩 RDN 규칙을 두 번 적용하여 얻고, $(\varphi \wedge \psi) \dashv\vdash (\neg\varphi \downarrow \neg\psi)$ 는 이중 부정으로 얻는다. 그리고 $(\varphi \wedge \psi)$ 는 $\neg(\varphi \rightarrow \neg\psi)$ 와 같은 기호열이다.
  받침: D (이중 부정 대체), G (이중 부정). 증명된 수업: 연결사의 대칭성.
4. 다섯 대칭성. $(\varphi \downarrow \psi) \dashv\vdash (\psi \downarrow \varphi)$ 는 기본 보조정리와 대우에 의한다. 그로부터 차례로 $\vee$ , $\wedge$ , $\leftrightarrow$ , $\veebar$ 의 대칭성이 각각 바로 앞의 것으로 얻어지며, 필요할 때는 부정 아래의 대체로 옮긴다.
  사용: 11. 기본 보조정리, 10. 대우. 받침: H (동치 대체). 증명된 수업: 연결사의 대칭성.
제4구간 고전적 규칙과 법칙
- 전제와 함께 선언과 연언의 도입과 제거, 배중률, 무모순율을 증명한다.
- 폭발 원리, 귀류법, 경우에 따른 증명을 전제와 함께 증명하고, 전제 없이는 왜 충분하지 않은지 설명한다.
- 드모르간 법칙, 그 변형, 분배 법칙을 두 방향 모두 연역으로 증명한다.
- 근거를 밝힌 동치의 사슬로 논리식을 간단한 표준형으로 바꾼다.
1. 연결사의 규칙. 임의의 $\Gamma$ 에 대해, $\varphi$ 식에서 $(\varphi \vee \psi)$ 식이 따라 나온다. $(\varphi \vee \psi)$ 식과 $\neg\varphi$ 식에서 $\psi$ 식, $\varphi$ 식과 $\psi$ 식에서 $(\varphi \wedge \psi)$ 식, $(\varphi \wedge \psi)$ 식에서 $\varphi$ 식과 $\psi$ 식이 따라 나온다. 또 $\vdash (\varphi \vee \neg\varphi)$ 이고 $\vdash \neg(\varphi \wedge \neg\varphi)$ 이다.
  사용: 1. 체계, 연역, 동일률, 2. 구조적 성질, 6. 가언 삼단논법과 교환, 10. 대우, 13. 동치 형식, 14. 다섯 대칭성. 받침: C (우카시에비치의 공리), E (연역 정리), F (결과에서 규칙으로), G (이중 부정). 증명된 수업: 고전 논리의 기법.
2. 폭발 원리와 귀류법. $\Gamma \vdash \varphi$ 이고 $\Gamma \vdash \neg\varphi$ 이면, $\Gamma \vdash \psi$ 식이 모든 $\psi$ 에 대해 성립한다. $\Gamma \cup \{\neg\varphi\}$ 집합에서 $\psi$ 식과 $\neg\psi$ 식이 연역되면 $\Gamma \vdash \varphi$ 이다. 그리고 $\Gamma \cup \{\varphi\}$ 집합에서 그것들이 연역되면 $\Gamma \vdash \neg\varphi$ 이다.
  사용: 1. 체계, 연역, 동일률, 2. 구조적 성질, 15. 연결사의 규칙. 받침: C (우카시에비치의 공리), E (연역 정리), G (이중 부정). 증명된 수업: 고전 논리의 기법.
3. 경우에 따른 증명. $\Gamma \cup \{\varphi\} \vdash \psi$ 이고 $\Gamma \cup \{\neg\varphi\} \vdash \psi$ 이면 $\Gamma \vdash \psi$ 이다. 그리고 $\Gamma \cup \{\varphi\} \vdash \chi$ , $\Gamma \cup \{\psi\} \vdash \chi$ , $\Gamma \vdash (\varphi \vee \psi)$ 이면 $\Gamma \vdash \chi$ 이다.
  사용: 2. 구조적 성질, 10. 대우, 15. 연결사의 규칙, 16. 폭발 원리와 귀류법. 받침: E (연역 정리). 증명된 수업: 고전 논리의 기법.
4. 드모르간 법칙. $\neg(\varphi \wedge \psi) \dashv\vdash (\neg\varphi \vee \neg\psi)$ 는 정의와 이중 부정에 의하고, $\neg(\varphi \vee \psi) \dashv\vdash (\neg\varphi \wedge \neg\psi)$ 는 부정논리합의 인자마다 RDN 규칙을 한 번씩 적용하여 얻는다. 따라서 $(\varphi \downarrow \psi) \dashv\vdash (\neg\varphi \wedge \neg\psi)$ 이고 $\neg(\varphi \rightarrow \psi) \dashv\vdash (\varphi \wedge \neg\psi)$ 이다.
  받침: D (이중 부정 대체), G (이중 부정), H (동치 대체). 증명된 수업: 드모르간 법칙과 분배 법칙.
5. 분배 법칙. $(\varphi \wedge (\psi \vee \chi)) \dashv\vdash ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$ 와 $(\varphi \vee (\psi \wedge \chi)) \dashv\vdash ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$ 는 각각 두 방향 모두 경우에 따른 증명으로 얻는다. 대칭성을 쓰면 오른쪽으로부터도 성립한다.
  사용: 14. 다섯 대칭성, 15. 연결사의 규칙, 17. 경우에 따른 증명. 받침: H (동치 대체). 증명된 수업: 드모르간 법칙과 분배 법칙.

의미론을 향하여. 사슬은 연역이 수학이 추론할 때 쓰는 모든 기법에 이르는 곳에서 멈춘다. 남은 것은, 연역되는 것이 모든 진리값 할당에서 참인 것과 정확히 일치하는지 아는 일이다. 다음 단원은 참을 정의하고, 마지막 단원은 두 개념을 비교한다.

근거의 약어

단원의 연역은 각 행의 근거를 약어로 밝히며, 그 약어는 모든 수업에서 같다. 여기서는 그것들을, 그것을 도입한 수업의 순서대로 모은다. 「전제」는 문제의 가정을 가리키며, 연역에 관한 연역에서는 증명하는 규칙의 가정을 가리킨다. 괄호 안의 수는 규칙을 적용하는 행을 가리킨다. 이미 증명된 동치는 한 행으로 쓸 때는 번호 없이 인용하고, 어떤 행에 적용할 때는 변형되는 행의 번호와 함께 인용하며, 그 행의 한 부분에 적용할 때도 마찬가지인데, 이때는 「Repl」을 쓴다.

첫째 수업: A1, A2, A3(공리 도식). MP $(i, j)$ (전건 긍정식). Def(정의: 약어의 전개 또는 환원, 전개하는 연결사를 덧붙인다. 「Def $\vee$ 」, 「Def $\dashv\vdash$ 」). Id(동일률, 정리 $\vdash (\varphi \rightarrow \varphi)$ ). Refl(반사성: $\varphi \in \Gamma$ 이면 $\Gamma \vdash \varphi$ ). Mon(단조성). Cut(절단: 연역된 것은 전제로 쓸 수 있다). Fin(유한성). DT(연역 정리)와 CDT(그 역).
둘째 수업: HS(가언 삼단논법). IP(전제 교환). DN(이중 부정). RDN $(i)$ (행 $i$ 에서의 이중 부정 대체. 번호 없는 RDN은 논리식과, 규칙에 의해 그것으로부터 얻어지는 논리식 사이의 동치를 가리킨다). CP(대우, 세 형태 가운데 어느 것이든). 「예제 $n$ 」(같은 수업의 예제 $n$ 의 결과를 한 행으로 쓴 것).
셋째 수업: FL(기본 보조정리, $(\varphi \downarrow \psi) \dashv\vdash \neg(\neg\varphi \rightarrow \psi)$ ). Repl(동치 대체, 그 형태 가운데 어느 것이든, 뒤에 적용하는 동치를 덧붙인다. 「Repl, DM $(i)$ 」). Eq(선언과 연언의 동치 형식, $(\varphi \vee \psi) \dashv\vdash (\neg\varphi \rightarrow \psi)$ 와 $(\varphi \wedge \psi) \dashv\vdash (\neg\varphi \downarrow \neg\psi)$ ). Sym(연결사의 대칭성).
넷째 수업: $\vee$ I와 $\vee$ E(선언의 도입과 제거). $\wedge$ I와 $\wedge$ E(연언의 도입과 제거). EM(배중률). NC(무모순율. 이 약어는 정리의 이름일 뿐, 단원의 어떤 행의 근거도 되지 않는다). Exp(폭발 원리). 경우 $(i, j)$ 와 경우 $(i, j, k)$ (경우에 따른 증명, 논리식과 그 부정에 의한 것 또는 선언에 의한 것). 「전제 없는 경우」(집합 $\Gamma$ 없이 하는 경우에 따른 증명으로, 한 문제에만 나온다). RAA(귀류법, 두 형태).
다섯째 수업: DM(드모르간 법칙). Dist(분배 법칙). Assoc(선언의 결합 법칙). 대입례 $(i)$ (임의의 논리식에 대해 성립하는 행 $i$ 를, 그 메타변항 대신 다른 논리식을 넣어 다시 쓴 것. 대입한 내용을 밝힌다).
이 수업의 도전 과제: M3(셋째 도전 과제가 A3 대신 놓는 도식).