コンテンツへスキップ
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}} 個しかない。したがって多くの論理式が同じ関数を表し、この命題は、それらがちょうど互いに同値な論理式であると述べている。まだわかっていないのは、すべての関数が何らかの論理式で表されるのか、それとも、それを表としてもつ論理式のない表が残るのか、ということである。