4.5意味論的同値な論理式-4.7命題言語の意味論

数理論理学

4.5 意味論的同値

A \simeq B どんな解釈の仕方をしてもAとBは真偽が同じ
定義：すべての付値V:Var \rightarrow |M|について

M \left[ \left[ A \right] \right] (V)=M \left[ \left[ B \right] \right] (V)

意味論的同値は同値関係である
復習：同値関係

  • 反射的　A \simeq A
  • 対称的　A \simeq BならばB \simeq A
  • 推移的　A \simeq BかつB \simeq CならばA \simeq C
補題4.5.6 変数の名前替えをしたもの同士は意味論的に同値である。

\xi xA \simeq \xi yA[y/x]

命題4.5.7 AとBがα同値ならばA \simeq B

逆は成り立たない

4.6 意味論的帰結 (Semantic Consequence)

P(a) \subset \forall xQ(x)と\neg Q(b)が両方成り立つならばいつでも\neg P(a)が成り立つ。

意味論的帰結に関する定義

Aを論理式、Φを論理式の集合とすると

  • 解釈I *1は、I=trueのとき、Aを満たす(satisfy)といい、I |= Aとあらわす。これをモデルという。
  • 解釈について
    • Aを満たす解釈が存在するとき、Aは充足可能であるという
    • Aを満たす解釈が存在しないとき、Aは充足不能（恒偽）であるという
    • すべての解釈がAを満たすとき、Aは恒真であるという
    • Φのすべての論理式を満たす解釈が存在するとき、Φは充足可能であるという。そうでなければ、Φは充足不能であるという。
  • 解釈IがすべてのA \in \PhiのモデルであるときΦのモデルであるといい、I |= Φと表す。
  • すべての解釈Iにおいて、I |= ΦならばI |= Aのとき、AはΦの意味論的帰結であるという。（ΦのモデルはAのモデル）
命題4.6.2 A|=BかつB|=AならばA \simeq B
命題4.6.2 任意の論理的集合Φと論理式Aに対して

Φ|=A iff Φ∪{¬A}は充足不能

命題4.6.8 任意の論理式Aについて
  1. Aは恒真 iff ∀xAは恒真
  2. Aは充足可能 iff ∃xAは充足可能

4.7 命題言語の意味論

命題言語において、変数はない（Var=φ）。また、すべての述語記号のアリティは0。
したがって、以下の命題が成り立つ

  • 任意の解釈(M,V)に対して、V＝{φ}

V(付値)は関係がなく、関数は出てこないので、各原子論理式の真偽が定まればその組み合わせとなる論理式の解釈の真偽も定まる。
したがって、命題言語における解釈は述語言語を真偽値に対応つけるもの

I[[・]]:�槇�{true,false}


と考えられる。

*1:解釈I＝(M,V) 解釈は構造と付値の組み合わせである I\left[ \left[ A \right] \right]=M\left[ \left[ A \right] \right](V)