コンテンツへスキップ
Topos Uranos
日本語

意味論的帰結と同値

要約

この課は、論理式の真理値から論理式どうしの関係へと進む。有限または無限の前提集合からの意味論的帰結を定義し、帰結の記号の読み方を明確にする。その否定の読み方も含めてであり、否定は、何かが恒真でないことをいうのであって、それが矛盾していることをいうのではない。多項式として書かれた結合子の値を用い、これによって法則の検証は計算に変わる。そして、帰結の構造的性質（反射性、単調性、カット、推移性）、意味論的演繹定理、帰結の充足不能性への帰着を証明する。この帰着は融合法の土台となる。次に意味論的同値を定義し、それが同値関係であって、相互の帰結とも双条件の恒真性とも一致することを証明し、複雑さに関する帰納法によって、それを扱うための二つの定理を証明する。部分論理式の一つの出現をそれと同値な別の論理式で置換すること、そして変数に論理式を一様に代入することである。これらを用いて、正しい名称をもつ法則の一覧を確立し、真理値表を使わずに、同値の連鎖によって論理式を簡約する。

学習目標

  1. 論理式が、有限または無限の論理式の集合の意味論的帰結であるかどうかを、それを反駁する付値を示すか、そのような付値が存在しないことを証明することによって判定する。
  2. 帰結の性質、意味論的演繹定理、帰結の充足不能性への帰着を証明し、適用する。
  3. 真理値表、値による計算、同値の連鎖によって意味論的同値を確立し、各法則を正しく名づける。
  4. 複雑さに関する帰納法によって意味論的置換定理と一様代入定理を証明し、それぞれがいつ適用されるかを区別する。

前の課から用いること

命題論理の意味論の課は論理式に意味を与えた。この課はそれを既知とする。付値とは関数 v ⁣:V→{0,1}v\colon V \to \{0, 1\} のことであり、各変数に真理値 11（真）または 00（偽）を割り当てる。帰納法の課の論理式上の再帰による定義の定理により、各付値は否定論理和の条項によってただ一通りにすべての論理式へと延長される。必要なのはこの条項だけである。この言語には結合子が一つしかないからである。

v((φ↓ψ))=1  ⇔  v(φ)=0,    v(ψ)=0v((\varphi \downarrow \psi)) = 1 \;\Leftrightarrow\; v(\varphi) = 0, \;\; v(\psi) = 0

延長の一意性により、延長の値も v(φ)v(\varphi) と書く。添字のない文字 vv はつねに付値を表し（v′v'、ww、uu はほかの付値を表す）、変数はつねに添字をもつ。形式化の課と同様に、pp、qq、rr、ss、tt は変数 v1v_1 から v5v_5 を表し、V(φ)V(\varphi) は φ\varphi の変数の集合である。vv は φ\varphi を充足するといい、v⊨φv \models \varphi と書く。これは v(φ)=1v(\varphi) = 1 のときである。また、その付値はこの論理式を反駁するといい、v⊭φv \not\models \varphi と書く。これは v(φ)=0v(\varphi) = 0 のときである。論理式が恒真（またはトートロジー）であるとは、すべての付値がそれを充足することであり、このとき ⊨φ\models \varphi と書く。充足可能であるとは、ある付値がそれを充足することであり、充足不能（または矛盾式）であるとは、どの付値もそれを充足しないことであり、偶然式であるとは、充足可能であって恒真でないことである。付値が論理式の集合 Γ\Gamma を充足する（v⊨Γv \models \Gamma）とは、その各要素を充足することであり、Γ\Gamma は、ある付値がそれを充足するとき充足可能、そうでないとき充足不能であるという。最後に、⊤:=(v1→v1)\top := (v_1 \rightarrow v_1)、⊥:=¬⊤\bot := \neg\top とおく。したがって、すべての付値について v(⊤)=1v(\top) = 1 かつ v(⊥)=0v(\bot) = 0 である。

その課からは、さらに二つの結果を用いる。第一は一致補題である。二つの付値が φ\varphi の変数で一致すれば、それらは φ\varphi で一致する。これにより、nn 個の変数をもつ論理式の値は 2n2^{n} 通りの組合せだけに依存し、その真理値表は有限である。第二は派生結合子の値の定理であり、公式の略記から、各結合子の値を成分の値の多項式として計算する。a=v(φ)a = v(\varphi)、b=v(ψ)b = v(\psi) とすると：

v(¬φ)=1−a,v((φ∨ψ))=a+b−ab,v((φ∧ψ))=abv(\neg\varphi) = 1 - a, \qquad v((\varphi \vee \psi)) = a + b - ab, \qquad v((\varphi \wedge \psi)) = ab
v((φ→ψ))=1−a(1−b),v((φ↔ψ))=ab+(1−a)(1−b),v((φ⊻ψ))=a+b−2abv((\varphi \rightarrow \psi)) = 1 - a(1 - b), \qquad v((\varphi \leftrightarrow \psi)) = ab + (1 - a)(1 - b), \qquad v((\varphi \veebar \psi)) = a + b - 2ab

この課の証明は、ほとんどすべて真理値の比較からなり、これらの多項式により、場合を一つずつ調べる代わりに計算によって比較できる。追加の規則はただ一つであり、00 と 11 は自分の平方に等しい唯一の数だということである。xx が 00 または 11 であれば、x2=xx^{2} = x かつ x(1−x)=0x(1 - x) = 0 である。さらに、同じ値のほかの三つの表記を手元においておくとよい。それらは積を展開して得られる。

v((φ↓ψ))=(1−a)(1−b),v((φ∨ψ))=1−(1−a)(1−b),v((φ↔ψ))=1−a−b+2abv((\varphi \downarrow \psi)) = (1 - a)(1 - b), \qquad v((\varphi \vee \psi)) = 1 - (1 - a)(1 - b), \qquad v((\varphi \leftrightarrow \psi)) = 1 - a - b + 2ab

第一は否定論理和の条項である（1−a1 - a と 1−b1 - b の積が 11 になるのは、ちょうど a=b=0a = b = 0 のときである）。第二は、選言が 00 になるのは両方の成分が 00 のときに限ることをいい、第三は、双条件が 11 になるのは a=ba = b のとき（1−2a+2a2=11 - 2a + 2a^{2} = 1 だから）、00 になるのは a≠ba \neq b のとき（このとき a+b=1a + b = 1 かつ ab=0ab = 0 だから）であることをいう。