본문 바로가기
Topos Uranos
한국어

함수적 완전성

요약

모든 논리식은 진리표 하나를 정한다. 이 수업은 그 역을 증명한다. 즉 모든 표, 곧 행에 진리값을 할당하는 모든 방식은 어떤 논리식의 표이다. 이 수업은 진리 함수를 정의하고, 인자가 nn개인 진리 함수의 개수를 세며(22n2^{2^{n}}), 논리식이 그중 하나를 언제 나타내는지를 명확히 한다. 이어서 표의 논리식으로 함수적 완전성 정리를 증명한다. 표의 논리식은 행마다 구성되는 리터럴의 연언들의 선언이며, 표준형 수업은 이것을 선언 표준형의 존재에 대한 첫 번째 증명으로 사용한다. 이 과정의 논리식은 모두 흰 원과 검은 원의 기호열이므로, 거기서 더 이상의 작업 없이 부정논리합만으로 충분하다는 것이 따라 나오며, 그것으로 임의의 함수를 어떻게 쓰는지가 드러난다. 끝으로 모든 함수를 나타내는 데 어떤 연결사 집합이면 충분한지를 연구한다. 일반적인 판정 기준을 증명하여 그것을 {¬,∧}\{\neg, \wedge\}, {¬,∨}\{\neg, \vee\}, {¬,→}\{\neg, \rightarrow\}, {↓}\{\downarrow\} 및 부정논리곱에 적용하고, {∧,∨,→,↔}\{\wedge, \vee, \rightarrow, \leftrightarrow\}에 대해서는 충분하지 않음을 증명한다. 그 논리식들은 모두 값 11을 보존하기 때문이다.

학습 목표

  1. 인자가 nn개인 진리 함수의 개수를 세고, 논리식이 나타내는 함수를 통해 두 논리식이 언제 동치인지 판정한다.
  2. 진리 함수의 표로부터 그것을 나타내는 논리식을 구성하고, 필요하면 더 짧은 동치 논리식을 찾는다.
  3. 이 과정의 언어에서는 부정논리합만으로 충분한 이유를 설명하고, 부정논리합만으로 주어진 함수를 나타내는 논리식을 쓴다.
  4. 연결사 집합이 충분함을, 그 집합의 논리식으로 부정논리합을 나타냄으로써 증명한다.
  5. 연결사 집합이 충분하지 않음을, 그 집합의 모든 논리식이 보존하는 성질을 통해 증명한다.

진리 함수

명제 논리의 의미론 수업은 각 논리식에 각 할당에서 진리값을 할당했고, 그 값이 논리식에 나타나는 변항들의 값에만 의존함을 보였다. 따라서 변항이 nn개인 논리식은 모두 행이 2n2^{n}개인 진리표를 가진다. 이 수업의 질문은 그 역이다. 임의의 표, 곧 2n2^{n}개의 행 옆에 마음대로 적은 1과 0의 열이 주어졌을 때, 그것을 표로 가지는 논리식이 있는가? 모든 표에 대해 그렇다면 언어에는 표현상의 빈틈이 없다. nn개의 진술의 진리값에 대해 그 값들에 따라 말할 수 있는 모든 것을 논리식으로 말할 수 있다. 그리고 이 과정에서는 복합 논리식이 모두 부정논리합이므로, 그 답은 단 하나의 연결사로 모든 것을 말하기에 충분한지도 알려 준다.

앞의 수업들에서 사용하는 것

진리값 할당이란 함수 vv, 곧 변항 집합 {v1,v2,…}\{v_1, v_2, \ldots\}에서 {0,1}\{0, 1\}로 가는 함수이며, 여기서 11은 참을, 00은 거짓을 나타낸다. 모든 논리식으로의 확장도 vv로 쓰며 재귀로 정의된다. v((φ↓ψ))=1v((\varphi \downarrow \psi)) = 1인 것은 v(φ)=0v(\varphi) = 0이고 v(ψ)=0v(\psi) = 0일 때, 그리고 그때에만이다. 같은 수업은 파생 연결사의 값 정리에서 공식 약어로부터 각 연결사의 값을 계산했다. 합과 곱으로 쓰면, 모든 할당 vv와 모든 논리식 φ\varphi, ψ\psi에 대해 그 값들은 다음과 같다.

v(¬φ)=1−v(φ),v((φ∧ψ))=v(φ) v(ψ),v((φ∨ψ))=v(φ)+v(ψ)−v(φ) v(ψ)v(\neg\varphi) = 1 - v(\varphi), \qquad v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi), \qquad v((\varphi \vee \psi)) = v(\varphi) + v(\psi) - v(\varphi)\,v(\psi)
v((φ→ψ))=1−v(φ)+v(φ) v(ψ),v((φ↓ψ))=(1−v(φ)) (1−v(ψ))v((\varphi \rightarrow \psi)) = 1 - v(\varphi) + v(\varphi)\,v(\psi), \qquad v((\varphi \downarrow \psi)) = (1 - v(\varphi))\,(1 - v(\psi))

또한 v((φ↔ψ))=v(φ) v(ψ)+(1−v(φ)) (1−v(ψ))v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))이며 이것이 11과 같은 것은 v(φ)=v(ψ)v(\varphi) = v(\psi)일 때, 그리고 그때에만이고, v((φ⊻ψ))=v(φ)+v(ψ)−2 v(φ) v(ψ)v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)이며 이것이 11과 같은 것은 v(φ)≠v(ψ)v(\varphi) \neq v(\psi)일 때, 그리고 그때에만이다. 값은 00 아니면 11이므로, 값의 제곱은 그 값 자신이며(v(φ) v(φ)=v(φ)v(\varphi)\,v(\varphi) = v(\varphi)), 값들의 곱이 11과 같은 것은 각 인수가 11과 같을 때, 그리고 그때에만이다. 이 두 관찰은 다시 언급하지 않고 사용한다. 일치 보조정리도 사용한다. 두 할당이 φ\varphi의 변항들, 곧 φ\varphi의 부분식인 변항들에서 일치하면, 두 할당은 φ\varphi에 같은 값을 준다. 의미론적 귀결과 동치 수업에서는 의미론적 동치를 빌려 온다. φ≡ψ\varphi \eqsem \psi는 모든 할당 v(φ)=v(ψ)v(\varphi) = v(\psi)에 대해 vv가 성립한다는 뜻이다. 끝으로 형식화 수업의 문자 약속이 유효하다. pp, qq, rr은 각각 변항 v1v_1, v2v_2, v3v_3을 나타낸다.

진리 함수와 그 개수

nn을 자연수라 하자. 값이 nn개인 행이란 열 a=(a1,…,an)a = (a_1, \ldots, a_n)로서 각 aia_i가 00이거나 11인 것이다. 그러한 모든 행의 집합을 {0,1}n\{0, 1\}^{n}으로 쓴다. 인자가 nn개인 진리 함수란 함수

f ⁣:{0,1}n→{0,1}f\colon \{0, 1\}^{n} \to \{0, 1\}

로서 각 행에 진리값을 할당하는 것이다. 이것은 표로 제시된다. 행들은 모든 값이 11인 행에서 시작하여 표의 순서대로 쓰고(인자가 둘이면 1 11\,1, 1 01\,0, 0 10\,1, 0 00\,0), 각 행 옆에 그 값을 쓴다. 따라서 진리 함수란 논리식이 없는 진리표, 곧 머리에 아무것도 적히지 않은 맨 오른쪽 열이다.

명제진리 함수는 22n2^{2^{n}}개이다(인자가 nn개일 때)

모든 자연수 nn에 대해, 행은 정확히 2n2^{n}개(각 행의 값은 nn개), 진리 함수는 22n2^{2^{n}}개(인자는 nn개)이다.

증명

  1. 1 0 1    ⟼    ∙∘∙\dato{filas}{1\,0\,1 \;\; \longmapsto \;\; \sigI\sigO\sigI}

    행이란 nn개의 기호의 열이며, 각 기호는 11 또는 00이다. 11 대신 검은 원을, 00 대신 흰 원을 쓰면, 행들은 두 기호로 된 알파벳 위의 길이 nn의 기호열과 일대일로 대응한다. 그 개수는 2n2^{n}이며, 이는 귀납법 수업의 첫 번째 예제에 따른 것으로, 거기서 nn에 대한 귀납법으로 증명되었다.

  2. f    ⟼    f(1,…,1)    …    f(0,…,0)f \;\; \longmapsto \;\; f(1, \ldots, 1) \;\; \ldots \;\; f(0, \ldots, 0)

    진리 함수는 행들 위에서의 값으로 정해지며, 그 값들을 어떻게 고르든 함수가 하나 얻어진다. 값을 표의 순서대로 쓰면, 함수들은 2n2^{n}개의 기호로 된 열로서 각 기호가 11 또는 00인 것과 일대일로 대응한다.

  3. 22n2^{\resaltar{2^{n}}}

    같은 셈을 이번에는 길이 2n2^{n}의 열에 적용하면, 함수는 22의 2n2^{n} 제곱 개이다.

  4. 22=4,24=16,28=256,216=65 5362^{2} = 4, \quad 2^{4} = 16, \quad 2^{8} = 256, \quad 2^{16} = 65\,536

    처음 몇 값은 이 수가 얼마나 빨리 커지는지 보여 준다. 인자가 다섯이 되면 함수는 이미 사십억 개가 넘는다.

예시인자가 하나인 함수와 둘인 함수

인자가 하나인 네 함수는 상수 11, 항등함수, 값을 맞바꾸는 함수, 상수 00이다. 논리식 ⊤\top, pp, ¬p\neg p, ⊥\bot은 각각 이 함수들의 표를 가진다. 여기서 ⊤:=(p→p)\top := (p \rightarrow p), ⊥:=¬⊤\bot := \neg\top 두 정의는 의미론 수업에서 고정한 것이다. 인자가 둘인 열여섯 함수 가운데에는 이 과정의 여섯 연결사, 곧 부정논리합, 선언, 연언, 함의, 쌍조건, 배타적 선언의 함수가 있다. 나머지는 열 개이며, 그중에는 두 상수, 한 인자에만 의존하는 함수들, 그리고 부정논리곱이 있다. 부정논리곱은 두 인자가 모두 00일 때에만 11이 된다. 예제 1이 이것들을 모두 분류한다.

함수를 나타내는 논리식

논리식과 진리 함수는 다음과 같이 연결된다. φ\varphi가 논리식이고 그 변항들이 v1,…,vnv_1, \ldots, v_n 가운데 있을 때, φ\varphi가 진리 함수 ff(인자는 nn개)를 나타낸다는 것은 모든 할당 vv에 대해 다음이 성립한다는 뜻이다.

v(φ)=f(v(v1),…,v(vn))v(\varphi) = f(v(v_1), \ldots, v(v_n))

즉 변항 φ\varphi로 쓴 v1,…,vnv_1, \ldots, v_n의 표가 ff의 표이다. 변항에 대한 조건은 사소하지 않다. 논리식 (p∧q)(p \wedge q)는 인자가 하나인 어떤 함수도 나타내지 않는다. 그 값이 pp의 값에만 의존하지 않기 때문이다.

명제논리식의 함수

φ\varphi를 논리식이라 하고 그 변항들이 v1,…,vnv_1, \ldots, v_n 가운데 있다고 하자. 그러면 φ\varphi는 인자가 nn개인 진리 함수를 정확히 하나 나타내며, 그것을 fφf_\varphi로 쓴다. ψ\psi가 변항들이 v1,…,vnv_1, \ldots, v_n 가운데 있는 또 다른 논리식이면, φ≡ψ\varphi \eqsem \psi인 것은 fφ=fψf_\varphi = f_\psi일 때, 그리고 그때에만이다.

증명

  1. va(vi)=ai(i≤n),va(vk)=0(k>n)\dato{va}{v_a(v_i) = a_i \quad (i \leq n), \qquad v_a(v_k) = 0 \quad (k > n)}

    각 행 aa에 대해, 각 viv_i에 값 aia_i를 주는 할당이 존재한다. 나머지 변항에는 값 00을 주면 된다.

  2. v(vi)=v′(vi)=ai(i≤n)    ⇒    v(φ)=v′(φ)=fφ(a)v(v_i) = v'(v_i) = a_i \quad (i \leq n) \;\; \Rightarrow \;\; v(\varphi) = v'(\varphi) = \resaltar{f_\varphi(a)}

    두 할당이 v1,…,vnv_1, \ldots, v_n에 행 aa의 값을 주면, 두 할당은 φ\varphi의 변항들에서 일치하고, 일치 보조정리에 의해 φ\varphi에 같은 값을 준다. 이 공통의 값을 fφ(a)f_\varphi(a)라 하자. 구성에 의해 φ\varphi는 fφf_\varphi를 나타낸다.

  3. g(a)=va(φ)=fφ(a)g(a) = v_a(\varphi) = f_\varphi(a)

    φ\varphi가 함수 gg도 나타낸다면, 각 행 aa에서 g(a)=va(φ)=fφ(a)g(a) = v_a(\varphi) = f_\varphi(a)이다. 나타나는 함수는 유일하다.

  4. v(φ)=fφ(v(v1),…,v(vn))=fψ(v(v1),…,v(vn))=v(ψ)v(\varphi) = f_\varphi(v(v_1), \ldots, v(v_n)) = f_\psi(v(v_1), \ldots, v(v_n)) = v(\psi)

    fφ=fψf_\varphi = f_\psi이면, 모든 할당 vv에 대해 φ\varphi와 ψ\psi의 값은 같은 함수의 같은 행에서의 값이다. 따라서 φ≡ψ\varphi \eqsem \psi이다.

  5. fφ(a)=va(φ)=va(ψ)=fψ(a)f_\varphi(a) = v_a(\varphi) = v_a(\psi) = f_\psi(a)

    거꾸로 φ≡ψ\varphi \eqsem \psi이면, 각 행 aa에서 할당 vav_a는 두 논리식에 같은 값을 주고, 따라서 fφ(a)=fψ(a)f_\varphi(a) = f_\psi(a)이다.

변항들이 v1,…,vnv_1, \ldots, v_n 가운데 있는 논리식은 무한히 많고 함수는 22n2^{2^{n}}개뿐이다. 따라서 많은 논리식이 같은 함수를 나타내며, 이 명제는 그것들이 바로 서로 동치인 논리식들이라고 말한다. 아직 모르는 것은 모든 함수가 어떤 논리식으로 나타나는지, 아니면 그것을 표로 가지는 논리식이 없는 표가 남는지이다.