본문 바로가기
Topos Uranos
한국어

의미론: 종합과 도전 과제

요약

이 수업은 의미론 단원을 마무리한다. 이 수업은 할당을 모든 논리식으로 확장하는 일과 일치 보조정리에서 출발하여 의미론적 귀결, 동치, 그리고 동치의 두 작업 정리(대체 정리와 균일 대입 정리)로, 거기서 임의 개수의 항에 대한 법칙, 함수적 완전성, 연결사 집합으로, 다시 거기서 표준형, 그 알고리즘, 회로로 이어지는 연역의 사슬을 다시 세우고, 각 고리에서 어떤 결과를 쓰며 어느 수업에서 증명되는지를 밝힌다. 단원이 증명한 것과 앞 단원들에서 가져온 것을 구별하고, 강좌가 첫 단원부터 지니고 온 논증을 세 가지 방법으로 판정하며, 단원이 열어 둔 물음, 곧 모든 할당에서 참인 것이 도출 가능한 것과 일치하는가라는 물음이 왜 메타이론으로 이어지는지를 설명한다. 마무리 평가에서는 입문 평가의 기능을 되풀이하고, 끝으로 여섯 개의 도전 과제를 둔다. 도전 과제는 각 수업의 연습보다 어렵고, 둘 이상의 수업의 도구를 결합할 것을 요구한다.

학습 목표

  1. 단원의 결과들의 논리적 순서를 다시 세우고, 각 결과가 기대는 앞선 결과와 그것이 증명되는 수업을 밝힌다.
  2. 재귀적 확장, 일치 보조정리, 의미론적 대체, 일반화된 법칙이 어떻게 함수적 완전성, 표준형의 존재, 그리고 그 알고리즘의 올바름과 종료성으로 이어지는지 설명한다.
  3. 단원이 증명한 것을 앞 단원들에서 가져온 것, 그리고 메타이론에 남긴 것, 특히 의미론적 귀결과 도출 가능성의 일치 및 콤팩트성과 구별한다.
  4. 값의 계산, 의미론적 귀결, 균일 대입, 연결사 집합, 표준형, 회로를 결합하는 문제를 푼다.

단원에서 이룬 것

이 단원의 목표는 첫 단원에서 구성한 언어의 논리식에, 둘째 단원의 연역 체계는 건드리지 않은 채 의미를 부여하고, 그 의미로부터 논리학이 논리식에 대해 묻는 물음들, 곧 논리식이 타당한가, 충족 가능한가, 다른 논리식들로부터 귀결되는가, 다른 논리식과 같은 것을 말하는가를 판정하는 절차를 끌어내는 것이었다. 이 목표는 몇 가지 전제만으로 이루어졌고, 각 전제는 제자리에서 밝혀 두었다. 이치성과 진리 함수성은 증명되는 것이 아니라 선택되는 것이며, 그 대가는 형식화 수업이 보여 주었다. 유일 판독성, 재귀에 의한 정의, 귀납법, 공식 약어는 첫 단원에서 증명되거나 정해졌고 여기서 쓰인다. 그리고 집합과 함수에 대해 꼭 필요한 최소한은 필요한 곳에서 상기시켰다. 이 전제들 아래에서, 지나온 길은 수업마다 하나씩, 여섯 구간으로 이루어진 하나의 연역 사슬로 읽을 수 있다.

논리식의 값

명제 논리의 의미론에 관한 수업은 할당을 변항에서 {0,1}\{0, 1\}로 가는 함수로 정의하고, 논리식에 대한 재귀적 정의의 정리를 써서, 할당이 단 하나의 조항 v((φ↓ψ))=(1−v(φ))(1−v(ψ))v((\varphi \downarrow \psi)) = (1 - v(\varphi))(1 - v(\psi))에 의해 모든 논리식으로 유일하게 확장됨을 증명했다. 공식 약어로부터, 다른 어떤 것도 공준으로 세우지 않고, 각 파생 연결사의 값을 성분의 값의 다항식으로 계산했고, 그와 함께 함의의 표를 얻었다. 함의의 표는 여기서 정리이다. 복잡도에 관한 귀납법으로 일치 보조정리를 증명했고, 이로부터 2n2^{n}개의 행을 가진 진리표가 nn개의 변항을 가진 논리식에 대해 무한히 많은 할당이 말하는 모든 것을 담고 있음이 따라 나온다. 충족, 타당성, 충족 가능성, 모순식, 우연식을 정의했고, ⊭φ\not\models \varphi의 뜻은 φ\varphi의 타당하지 않음이지 모순식임이 아니라고 분명히 했으며, ⊤:=(v1→v1)\top := (v_{1} \rightarrow v_{1})과 ⊥:=¬⊤\bot := \neg\top를 정했고, 타당성과 충족 가능성의 결정 가능성을 지수적인 대가를 치르고 얻었다. 이 대가는 반박하는 할당을 겨냥해서 찾으면 줄일 수 있지만 없앨 수는 없다.

귀결과 동치

의미론적 귀결과 동치에 관한 수업은 유한하거나 무한한 전제 집합으로부터의 귀결을 정의하고, 그것이 연역의 구조적 성질(반사성, 단조성, 절단, 추이성)을 가짐을 증명했다. 그 증명들은 행을 다루는 대신 할당을 하나하나 살핀다. 의미론적 연역 정리 Γ∪{φ}⊨ψ⇔Γ⊨(φ→ψ)\Gamma \cup \{\varphi\} \models \psi \Leftrightarrow \Gamma \models (\varphi \rightarrow \psi)는 함의의 유일한 거짓 행으로 귀착되었고, 귀결은 충족 불가능성으로 귀착되었다. 곧 Γ⊨φ⇔Γ∪{¬φ}\Gamma \models \varphi \Leftrightarrow \Gamma \cup \{\neg\varphi\}가 충족 불가능하다. 값의 같음으로 정의된 의미론적 동치는 상호 귀결과도, 쌍조건의 타당성과도 일치함이 드러났다. 그 두 작업 정리는 복잡도에 관한 귀납법으로 증명되었다. 하나는 부분식의 한 출현을 그것과 동치인 논리식으로 바꾸는 대체이며, 빠뜨려서는 안 되는 전체 출현의 경우를 포함한다. 다른 하나는 변항 자리에 임의의 논리식을 균일하게 대입하는 균일 대입이며, 타당성, 동치, 귀결을 보존한다. 이것들 덕분에 다항식의 항등식으로 확인된 법칙 목록의 법칙들은 어떤 논리식의 어떤 자리에든 적용되고, 사슬로 이어진다.

임의 개수의 항에 대한 법칙

일반화된 드모르간 법칙과 분배 법칙에 관한 수업은 nn개 논리식의 연언과 선언을 왼쪽 결합으로 재귀적으로 정의하고, 항의 개수에 관한 귀납법으로 값 보조정리를 증명했다. 값 보조정리는 연언이 참일 필요충분조건은 모든 항이 참인 것이고, 선언이 참일 필요충분조건은 어떤 항이 참인 것이라고 말한다. 이것과 연결사의 동치와의 양립성으로 일반화된 결합 법칙을 얻었는데, 이는 증명 가능한 동치에 대해서도 성립하도록 동치의 사슬로 증명되었다. 또한 순서와 반복에 대한 독립성, 일반화된 드모르간 법칙, 일반화된 분배 법칙을 얻었다. 분배 법칙의 두 첨자에 관한 귀납법은 귀납 가정이 둘째 목록의 모든 길이를 덮도록 짜였다. 쌍대 법칙은 이중 귀납법을 되풀이하지 않고 드모르간 법칙으로 얻었다.

진리 함수

함수적 완전성에 관한 수업은 표에서 논리식으로 가는 반대 방향의 길을 걸었다. 인자가 nn개인 진리 함수를 세고(22n2^{2^{n}}개가 있다), 각 논리식이 그중 정확히 하나를 나타내며 두 논리식이 동치일 필요충분조건은 같은 함수를 나타내는 것임을 보였고, 함수적 완전성 정리를 증명했다. 한 행의 연언은 정확히 자기 행에서 참이고, 함수가 11의 값을 갖는 행들의 연언의 선언이 그 함수를 나타낸다. 이 논리식은 원과 원판의 기호열이므로 부정논리합 하나만으로 충분하다. 부정논리합의 판정 기준에 따라 {¬,∧}\{\neg, \wedge\}, {¬,∨}\{\neg, \vee\}, {¬,→}\{\neg, \rightarrow\}, 그리고 부정논리곱도 충분하다. 그리고 닫힘 원리에 따라 {∧,∨,→,↔}\{\wedge, \vee, \rightarrow, \leftrightarrow\}의 논리식은 모두 11의 값을 보존하므로, 이 집합은 충분하지 않다.

표준형

표준형에 관한 수업은 동치인 논리식의 각 부류에서 정해진 모양의 대표를 골랐다. 리터럴, 절, 기본 연언을 정의하고, 표준형의 부정이 그 쌍대와 동치임을 증명했다. 쌍대는 각 연언을 선언으로, 각 리터럴을 반대 리터럴로 바꾼다. 표에서 완전 표준형을 구성했는데, 이는 변항을 고정하면 유일하다. 그리고 두 표준형의 존재를 두 가지 방법으로 증명했다. 하나는 표로부터, 함수적 완전성의 따름정리로서이다. 다른 하나는 복잡도에 관한 귀납법으로서, 유일한 경우는 부정논리합이며, 이는 성분들의 부정의 연언과 동치이다. 귀납 가정은 두 형태를 동시에 요구하는데, 부정이 그것들을 맞바꾸기 때문이다. 끝으로, 연언 표준형의 타당성과 선언 표준형의 충족 가능성은 그 상보 쌍을 보면 한눈에 알 수 있음을 보였다.

알고리즘과 회로

표준형 알고리즘과 그 응용에 관한 수업은 둘째 존재 증명을 표기에 작용하는 절차로 바꾸었다. ¬\neg, ∧\wedge, ∨\vee 이외의 연결사를 제거하고, 부정을 변항까지 내리고, 분배한다. 표기 안에서의 대체로 알고리즘의 올바름을 증명했는데, 이 대체는 대체 정리를 약어에 맞게 고친 것이다. 또 단계마다 줄어드는 세 측도로 종료성을 증명했는데, 그 마지막 측도는 연언을 곱으로 읽는다. 나아가 ⋁i=1n(pi∧qi)\bigvee_{i=1}^{n} (p_i \wedge q_i)의 연언 표준형은 반드시 2n2^{n}개의 절을 가짐을 증명했으므로, 증가는 알고리즘의 결함이 아니다. 이어서 블랙박스의 표준형을 그 표로부터 구하고, 이웃한 행을 합쳐 간단히 하고, 스위치 회로로 바꾸었다. 회로의 도통은 그 논리식의 값이다.

다음 그림은 여섯 구간을 하나의 사슬로 모은 것이다. 가운데 열의 각 마디는 정의나 결과이며, 논리적 순서에 따라 번호가 붙고, 그 증명이 쓰는 앞의 고리들과 호로 이어진다. 그 둘레에 떠 있는 것이 받침, 곧 사슬이 거듭 의지하는 원리와 도구이다. 각 받침은 자신에게 기대는 고리들과 실선으로, 자신이 세워지는 고리와 점선으로 이어지며, 이 사슬이 증명하지 않는 받침(재귀와 함께하는 유일 판독성, 귀납법, 공식 약어로, 모두 첫 단원의 것)은 둥근 테로 그려진다. 받침을 누르면 그것을 쓰는 고리가 모두 강조되고, 각 고리는 그것이 증명되는 수업으로 이어진다. 귀납법과 연결사의 값이 단원에서 가장 자주 쓰이는 받침이라는 점, 그리고 값 보조정리는 셋째 수업에서 증명되지만 마지막 세 수업이 연언과 선언에 대해 말하는 것의 거의 전부를 받친다는 점에 주목하자.

사슬의 받침

  • A유일 판독성과 재귀. ∙φψ=∙φ′ψ′\sigI\varphi\psi = \sigI\varphi'\psi'이고 네 기호열이 모두 논리식이면 φ=φ′\varphi = \varphi'이고 ψ=ψ′\psi = \psi'이다. 따라서 ∙φψ\sigI\varphi\psi의 값을 φ\varphi, ψ\psi와 그 값들로부터 계산하는 규칙은 논리식 위의 유일한 함수를 정의한다. 첫 단원에서 증명된다. 이 단원에서는 증명 없이 받아들인다.
  • B귀납법. 자연수에 관한 단순한 귀납법과 강한 귀납법, 그리고 논리식의 복잡도에 관한 귀납법. 후자의 경우는 변항과 부정논리합 (φ↓ψ)(\varphi \downarrow \psi)뿐이다. 첫 단원에서 증명된다. 이 단원에서는 증명 없이 받아들인다.
  • C공식 약어. ¬φ:=(φ↓φ)\neg\varphi := (\varphi \downarrow \varphi), (φ∨ψ):=¬(φ↓ψ)(\varphi \vee \psi) := \neg(\varphi \downarrow \psi), (φ∧ψ):=¬(¬φ∨¬ψ)(\varphi \wedge \psi) := \neg(\neg\varphi \vee \neg\psi), (φ→ψ):=(¬φ∨ψ)(\varphi \rightarrow \psi) := (\neg\varphi \vee \psi), (φ↔ψ):=((φ→ψ)∧(ψ→φ))(\varphi \leftrightarrow \psi) := ((\varphi \rightarrow \psi) \wedge (\psi \rightarrow \varphi)), (φ⊻ψ):=¬(φ↔ψ)(\varphi \veebar \psi) := \neg(\varphi \leftrightarrow \psi). 첫 단원에서 정해진다. 이 단원에서는 증명 없이 받아들인다.
  • D연결사의 값. a=v(φ)a = v(\varphi), b=v(ψ)b = v(\psi)일 때: v(¬φ)=1−av(\neg\varphi) = 1 - a, v((φ∨ψ))=a+b−abv((\varphi \vee \psi)) = a + b - ab, v((φ∧ψ))=abv((\varphi \wedge \psi)) = ab, v((φ→ψ))=1−a(1−b)v((\varphi \rightarrow \psi)) = 1 - a(1 - b), v((φ↔ψ))=ab+(1−a)(1−b)v((\varphi \leftrightarrow \psi)) = ab + (1 - a)(1 - b), v((φ⊻ψ))=a+b−2abv((\varphi \veebar \psi)) = a + b - 2ab. 여기서 a2=aa^{2} = a. 확립되는 곳: 1. 할당의 확장.
  • E일치 보조정리. 두 할당이 φ\varphi의 변항에서 일치하면, 두 할당은 φ\varphi에 같은 값을 준다. 그래서 2n2^{n}개 행의 표가 모든 것을 말한다. 확립되는 곳: 2. 일치 보조정리와 표.
  • F의미론적 대체. θ≡θ′\theta \eqsem \theta'이고 χ′\chi'이 χ\chi에서 θ\theta의 한 출현을 θ′\theta'으로 바꾸어 얻어지면, χ≡χ′\chi \eqsem \chi'이다. 확립되는 곳: 7. 의미론적 대체 정리.
  • G동치 법칙. 임의의 논리식에 대한 이중 부정, 멱등 법칙, 교환 법칙, 결합 법칙, 분배 법칙, 드모르간 법칙, 흡수 법칙, 항등 법칙, 지배 법칙, 배중률, 무모순율. 확립되는 곳: 9. 동치 법칙.
  • H값 보조정리. v(⋀i=1nφi)=1v\left( \bigwedge_{i=1}^{n} \varphi_i \right) = 1일 필요충분조건은 v(φi)=1v(\varphi_i) = 1이 모든 ii에 대해 성립하는 것이다. v(⋁i=1nφi)=1v\left( \bigvee_{i=1}^{n} \varphi_i \right) = 1일 필요충분조건은 v(φi)=1v(\varphi_i) = 1이 어떤 ii에 대해 성립하는 것이다. 확립되는 곳: 10. 값 보조정리와 양립성.

  1. 제1구간 논리식의 값

    • 부정논리합의 조항으로 논리식의 값을 계산하고, 약어로부터 각 파생 연결사의 값을 이끌어 낸다.
    • 일치 보조정리를 증명하고, 그것으로 2n2^{n}개 행의 표면 충분함을 정당화한다.
    • ⊭φ\not\models \varphi의 뜻을 모순식과 혼동하지 않고 논리식과 집합을 분류하며, 반박하는 할당을 찾아 타당성을 판정한다.

    1. 할당의 확장. 각 할당 vv는 조항 v((φ↓ψ))=(1−v(φ))(1−v(ψ))v((\varphi \downarrow \psi)) = (1 - v(\varphi))(1 - v(\psi))에 의해 모든 논리식으로 유일하게 확장된다. 약어를 풀면 ¬\neg, ∨\vee, ∧\wedge, →\rightarrow, ↔\leftrightarrow, ⊻\veebar의 값이 계산된다.

      받침: A (유일 판독성과 재귀), C (공식 약어). 증명된 수업: 명제 논리의 의미론.

    2. 일치 보조정리와 표. vv와 v′v'이 V(φ)V(\varphi)에서 일치하면 v(φ)=v′(φ)v(\varphi) = v'(\varphi)이다. 이는 복잡도에 관한 귀납법으로 증명된다. 따라서 모든 할당에서의 φ\varphi의 값은 그 표의 2n2^{n}개 행에서의 값과 정확히 같다.

      사용: 1. 할당의 확장. 받침: B (귀납법). 증명된 수업: 명제 논리의 의미론.

    3. 분류와 판정. 각 논리식은 타당식, 우연식, 모순식 가운데 정확히 하나이다. φ\varphi가 타당할 필요충분조건은 ¬φ\neg\varphi가 모순식인 것이고, 모순식일 필요충분조건은 ⊨¬φ\models \neg\varphi인 것이다. ⊤\top와 배중률은 타당하고, ⊥\bot은 모순식이며, 타당성과 충족 가능성은 행을 하나하나 살펴 판정된다.

      받침: D (연결사의 값), E (일치 보조정리). 증명된 수업: 명제 논리의 의미론.

  2. 제2구간 귀결과 동치

    • 유한하거나 무한한 집합으로부터의 귀결을, 반례 모형을 제시하거나 그것이 없음을 증명하여 판정한다.
    • 의미론적 연역 정리와, 귀결을 충족 불가능성으로 귀착시키는 방법을 적용한다.
    • 한 출현의 대체와 균일 대입을 구별하고, 둘 다 복잡도에 관한 귀납법으로 증명한다.
    • 각 법칙의 이름을 바르게 대면서 동치를 사슬로 세운다.

    1. 귀결과 그 성질. Γ⊨φ\Gamma \models \varphi이란 Γ\Gamma를 충족하는 모든 할당이 φ\varphi를 충족한다는 것이다. ∅⊨φ\emptyset \models \varphi일 필요충분조건은 ⊨φ\models \varphi인 것이다. 반사성, 단조성, 절단, 추이성이 성립하고, 충족 불가능한 집합은 모든 논리식을 귀결로 갖는다.

      사용: 3. 분류와 판정. 증명된 수업: 의미론적 귀결과 동치.

    2. 의미론적 연역과 충족 불가능성. Γ∪{φ}⊨ψ⇔Γ⊨(φ→ψ)\Gamma \cup \{\varphi\} \models \psi \Leftrightarrow \Gamma \models (\varphi \rightarrow \psi)는 함의의 유일한 거짓 행에 의한다. {φ1,…,φn}⊨ψ⇔  ⊨(φ1→(φ2→⋯(φn→ψ)⋯ ))\{\varphi_1, \ldots, \varphi_n\} \models \psi \Leftrightarrow\; \models (\varphi_1 \rightarrow (\varphi_2 \rightarrow \cdots (\varphi_n \rightarrow \psi) \cdots))이다. 그리고 Γ⊨φ\Gamma \models \varphi일 필요충분조건은 Γ∪{¬φ}\Gamma \cup \{\neg\varphi\}가 충족 불가능한 것이다.

      사용: 4. 귀결과 그 성질. 받침: D (연결사의 값). 증명된 수업: 의미론적 귀결과 동치.

    3. 의미론적 동치. φ≡ψ\varphi \eqsem \psi일 필요충분조건은 φ⊨ψ\varphi \models \psi이고 ψ⊨φ\psi \models \varphi인 것이며, 또한 ⊨(φ↔ψ)\models (\varphi \leftrightarrow \psi)인 것이다. 동치는 반사적이고 대칭적이며 추이적이고, 동치인 두 논리식은 전제로서도 결론으로서도 서로 바꿀 수 있다.

      사용: 4. 귀결과 그 성질. 받침: D (연결사의 값). 증명된 수업: 의미론적 귀결과 동치.

    4. 의미론적 대체 정리. θ≡θ′\theta \eqsem \theta'이면, χ\chi에서 θ\theta의 한 출현(전체 출현을 포함하여)을 θ′\theta'으로 바꾸면 χ\chi와 동치인 논리식이 얻어진다. 모든 출현을 동시에 바꾸어도 마찬가지이다.

      사용: 1. 할당의 확장, 6. 의미론적 동치. 받침: A (유일 판독성과 재귀), B (귀납법). 증명된 수업: 의미론적 귀결과 동치.

    5. 균일 대입. w(vn)=v(σ(vn))w(v_n) = v(\sigma(v_n))이면 v(σ(χ))=w(χ)v(\sigma(\chi)) = w(\chi)이다. 따라서 ⊨χ\models \chi이면 ⊨σ(χ)\models \sigma(\chi)이기도 하며, 대입은 동치와 귀결을 보존하지만 충족 가능성도, 우연식임도 보존하지 않는다.

      사용: 1. 할당의 확장, 4. 귀결과 그 성질, 6. 의미론적 동치. 받침: A (유일 판독성과 재귀), B (귀납법). 증명된 수업: 의미론적 귀결과 동치.

    6. 동치 법칙. 목록의 법칙들은 a2=aa^{2} = a일 때 다항식의 항등식으로 확인된다. 대체와 추이성으로 그것들은 부분식에 적용되고 사슬로 이어진다.

      사용: 3. 분류와 판정, 6. 의미론적 동치. 받침: D (연결사의 값), F (의미론적 대체). 증명된 수업: 의미론적 귀결과 동치.

  3. 제3구간 임의 개수의 항에 대한 법칙

    • nn개 항의 연언과 선언을 왼쪽 결합의 기호열로 풀어 쓰고, 그 값을 계산한다.
    • 항의 개수에 관한 귀납법으로 일반화된 결합 법칙, 순서에 대한 독립성, 일반화된 드모르간 법칙을 증명한다.
    • 일반화된 분배 법칙을 두 첨자에 관한 귀납법으로 증명하고, 그것이 만드는 항을 센다.

    1. 값 보조정리와 양립성. α≡α′\alpha \eqsem \alpha'이고 β≡β′\beta \eqsem \beta'이면, ¬α≡¬α′\neg\alpha \eqsem \neg\alpha', (α∧β)≡(α′∧β′)(\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta'), (α∨β)≡(α′∨β′)(\alpha \vee \beta) \eqsem (\alpha' \vee \beta')이다. nn개 항의 연언이 11의 값을 가질 필요충분조건은 모든 항이 11의 값을 갖는 것이고, 선언은 어떤 항이 11의 값을 갖는 것이며, 동치인 항들은 동치인 연언과 선언을 준다.

      사용: 6. 의미론적 동치. 받침: D (연결사의 값), B (귀납법). 증명된 수업: 일반화된 드모르간 법칙과 분배 법칙.

    2. 결합 법칙과 순서. 두 목록의 연언들의 연언은 두 목록을 이어 붙인 목록의 연언과 동치이고, 어떤 묶는 방식도 왼쪽 결합의 것과 동치이다. 같은 항을 가진 두 목록은 순서와 반복에 관계없이 동치인 연언과 선언을 준다.

      받침: H (값 보조정리), G (동치 법칙), B (귀납법). 증명된 수업: 일반화된 드모르간 법칙과 분배 법칙.

    3. 일반화된 드모르간 법칙. ¬⋀i=1nφi≡⋁i=1n¬φi\neg \bigwedge_{i=1}^{n} \varphi_i \eqsem \bigvee_{i=1}^{n} \neg\varphi_i, 그리고 ¬⋁i=1nφi≡⋀i=1n¬φi\neg \bigvee_{i=1}^{n} \varphi_i \eqsem \bigwedge_{i=1}^{n} \neg\varphi_i. 두 항의 법칙을 마지막 결합에 적용하고, 귀납 가정을 안쪽에 남은 것에 적용한다.

      받침: H (값 보조정리), G (동치 법칙), B (귀납법). 증명된 수업: 일반화된 드모르간 법칙과 분배 법칙.

    4. 일반화된 분배 법칙. (⋁i=1nφi)∧(⋁j=1mψj)≡⋁i,j(φi∧ψj)\left( \bigvee_{i=1}^{n} \varphi_i \right) \wedge \left( \bigvee_{j=1}^{m} \psi_j \right) \eqsem \bigvee_{i,j} (\varphi_i \wedge \psi_j). 여기서 항은 nmnm개이며 사전식 순서로 놓인다. 또한 두 연언의 선언을 분배하는 쌍대 법칙은 드모르간 법칙에 의한다.

      사용: 11. 결합 법칙과 순서, 12. 일반화된 드모르간 법칙. 받침: H (값 보조정리), G (동치 법칙), B (귀납법). 증명된 수업: 일반화된 드모르간 법칙과 분배 법칙.

  4. 제4구간 진리 함수

    • 진리 함수를 세고, 두 논리식이 나타내는 함수를 비교하여 동치를 판정한다.
    • 표의 논리식을 구성하고, 임의의 함수를 부정논리합만으로 쓴다.
    • 연결사 집합이 충분함을 부정논리합의 판정 기준으로, 또는 충분하지 않음을 그 논리식들이 보존하는 성질로 증명한다.

    1. 진리 함수. 진리 함수는 22n2^{2^{n}}개 있으며, 인자는 nn개이다. 변항이 v1,…,vnv_1, \ldots, v_n 가운데 있는 논리식은 그중 정확히 하나, 곧 fφf_\varphi를 나타내며, φ≡ψ⇔fφ=fψ\varphi \eqsem \psi \Leftrightarrow f_\varphi = f_\psi이다.

      사용: 6. 의미론적 동치. 받침: E (일치 보조정리). 증명된 수업: 함수적 완전성.

    2. 함수적 완전성. 한 행의 연언은 정확히 자기 행에서 11의 값을 갖는다. ff가 11의 값을 갖는 행들의 연언의 선언은(그런 행이 없으면 (v1∧¬v1)(v_{1} \wedge \neg v_{1})은) ff를 나타낸다. 그리고 모든 논리식은 그 표의 논리식과 동치이다.

      사용: 14. 진리 함수. 받침: H (값 보조정리), D (연결사의 값). 증명된 수업: 함수적 완전성.

    3. 충분한 집합과 충분하지 않은 집합. 부정논리합은 약어가 풀리므로 충분하다. KK의 논리식이 (1−a)(1−b)(1 - a)(1 - b)의 값을 나타내면 집합 KK는 충분하며, {¬,∧}\{\neg, \wedge\}, {¬,∨}\{\neg, \vee\}, {¬,→}\{\neg, \rightarrow\}, {↑}\{\uparrow\}도 그렇다. {∧,∨,→,↔}\{\wedge, \vee, \rightarrow, \leftrightarrow\}의 논리식은 11의 값을 갖는다. 모든 변항이 11의 값을 가질 때는 언제나 그렇다. 따라서 이 집합은 충분하지 않다.

      사용: 15. 함수적 완전성. 받침: C (공식 약어), B (귀납법), D (연결사의 값). 증명된 수업: 함수적 완전성.

  5. 제5구간 표준형

    • 리터럴, 절, 표준형을 알아보고, 기호열의 모양을 그 값과 구별한다.
    • 표로부터 완전 표준형을 구성하고, 그 유일성을 증명한다.
    • 두 형태를 모두 요구하는 귀납 가정으로 표준형의 존재를 귀납법으로 증명한다.
    • 연언 표준형의 타당성과 선언 표준형의 충족 가능성을 한눈에 판정한다.

    1. 리터럴과 쌍대성. ¬ℓ≡ℓ∗\neg\ell \eqsem \ell^{*}. 기본 연언이 충족 가능할 필요충분조건은 상보 쌍을 포함하지 않는 것이고, 절이 타당할 필요충분조건은 상보 쌍을 포함하는 것이다. 표준형의 부정은 그 쌍대와 동치이며, 따라서 φ\varphi의 연언 표준형은 ¬φ\neg\varphi의 선언 표준형의 쌍대이다.

      사용: 12. 일반화된 드모르간 법칙. 받침: G (동치 법칙), F (의미론적 대체), H (값 보조정리). 증명된 수업: 표준형.

    2. 완전 표준형. φ\varphi가 충족 가능하면 그 완전 선언 표준형과 동치이고, 타당하지 않으면 그 완전 연언 표준형과 동치이다. 변항 v1,…,vnv_1, \ldots, v_n을 고정하면, 두 완전 표준형이 동치일 필요충분조건은 같은 기호열인 것이고, 충족 가능한 두 논리식이 동치일 필요충분조건은 같은 완전 선언 표준형을 갖는 것이다.

      사용: 15. 함수적 완전성, 17. 리터럴과 쌍대성. 받침: H (값 보조정리), E (일치 보조정리). 증명된 수업: 표준형.

    3. 귀납법에 의한 존재. (φ↓ψ)≡(¬φ∧¬ψ)(\varphi \downarrow \psi) \eqsem (\neg\varphi \wedge \neg\psi). 표준형은 연언과 선언에 대해 닫혀 있다. 연언의 선언 표준형과 선언의 연언 표준형은 일반화된 분배 법칙에 의한다. 두 형태에 관한 귀납 가정을 둔 귀납법으로, 모든 논리식은 선언 표준형과 연언 표준형을 갖는다.

      사용: 17. 리터럴과 쌍대성, 11. 결합 법칙과 순서, 13. 일반화된 분배 법칙. 받침: B (귀납법), F (의미론적 대체). 증명된 수업: 표준형.

    4. 한눈에 보이는 것. 연언 표준형이 타당할 필요충분조건은 그 모든 절이 상보 쌍을 포함하는 것이다. 선언 표준형이 충족 가능할 필요충분조건은 상보 쌍을 하나도 포함하지 않는 기본 연언이 있는 것이다.

      사용: 17. 리터럴과 쌍대성. 받침: H (값 보조정리). 증명된 수업: 표준형.

  6. 제6구간 알고리즘과 회로

    • 다시 쓰기 알고리즘을 적용하고, 쌍조건을 제거하는 알맞은 방법을 고른다.
    • 알고리즘의 올바름과 종료성을 증명하고, 연언 표준형이 지수적으로 커질 수 있는 이유를 설명한다.
    • 블랙박스의 표준형을 구하여 간단히 하고, 그것들로부터 스위치 회로를 구성한다.

    1. 알고리즘의 올바름과 종료성. 부분 표기를 동치인 것으로 바꾸면 동치인 표기가 얻어진다. 각 규칙은 동치이며, 기약인 표기는 어떤 묶는 방식의 표준형이다. 측도 M1M_1, M2M_2(M2(¬φ)=2M2(φ)M_2(\neg\varphi) = 2^{M_2(\varphi)}으로 두고), M3M_3(M3(φ∧ψ)=M3(φ) M3(ψ)M_3(\varphi \wedge \psi) = M_3(\varphi)\,M_3(\psi)로 두고)는 단계마다 줄어든다.

      사용: 19. 귀납법에 의한 존재, 11. 결합 법칙과 순서. 받침: G (동치 법칙), D (연결사의 값), B (귀납법). 증명된 수업: 표준형 알고리즘과 그 응용.

    2. 지수적 증가. ⋁i=1n(pi∧qi)\bigvee_{i=1}^{n} (p_i \wedge q_i)는 절이 2n2^{n}개인 연언 표준형과 동치이며, 그것과 동치인 연언 표준형은 모두 타당하지 않은 절을 적어도 2n2^{n}개 갖는다.

      사용: 19. 귀납법에 의한 존재, 17. 리터럴과 쌍대성. 받침: H (값 보조정리). 증명된 수업: 표준형 알고리즘과 그 응용.

    3. 이웃한 행과 회로. (κ∧ℓ)∨(κ∧ℓ∗)≡κ(\kappa \wedge \ell) \vee (\kappa \wedge \ell^{*}) \eqsem \kappa, 그리고 쌍대 동치. 직병렬 회로가 상태 vv에서 도통할 필요충분조건은 v(φC)=1v(\varphi_C) = 1인 것이며, 모든 진리 함수는 어떤 회로로 구현된다.

      사용: 15. 함수적 완전성, 18. 완전 표준형, 17. 리터럴과 쌍대성, 11. 결합 법칙과 순서. 받침: G (동치 법칙), F (의미론적 대체), D (연결사의 값), B (귀납법). 증명된 수업: 표준형 알고리즘과 그 응용.

메타이론을 향하여. 사슬은 의미론이 논리식에 관한 각 물음에 대해 절차를 가진 곳에서 멈춘다. 남은 일은 모든 할당에서 참인 것이 체계에서 도출되는 것과 정확히 일치하는지 아는 것이다. 다음 단원이 두 개념을 비교한다.