【連載:命題論理2】論理式とモデルの定義

この記事の範囲

今回は論理式とモデルを定義しましょう.

今回の範囲

今回の範囲

論理式の定義

早速,論理式を定義します.

定義(命題変数)
\(A, B, C, \cdots \)
のようなアルファベット大文字1文字や,
\(A_0, A_1, A_2, \cdots \)
のようなアルファベット大文字1文字に自然数の添字をつけたものを命題変数と呼ぶ.

これらの命題変数は論理記号\( \lnot, \land, \lor, \rightarrow \)によって結合することができます.これらの記号はそれぞれ「〜でない,かつ,または,ならば」を表しています.命題変数をこれらの論理記号で結合することによって論理式を作ることができます.また, 矛盾を表す\( \bot \)を導入します.

定義(論理式)
論理式を以下で定める.
(1) 各命題変数は論理式である.
(2) \( \bot \)は論理式である.
(3) 論理式\( \varphi, \psi \)について,\( \lnot \varphi, (\varphi \land \psi), (\varphi \lor \psi), (\varphi \rightarrow \psi) \)は論理式である.
(4) 以上によって論理式とわかるものだけが論理式である.

以上で論理式を定義できました.定義中でも用いましたが, 命題変数を表すときはアルファベット大文字を,論理式を表すときはギリシャ文字を用いることにします.

例を挙げると,

\(
((A \land B ) \rightarrow C ), (\lnot A \rightarrow ( B \lor C )),
\)

などが論理式になります.しかし,定義通りに括弧を付けると煩雑になるので解釈が一意に定まる範囲で括弧を省略することにします.またその際次の省略規則を導入します.

括弧の省略規則:
括弧が省略されているとき,\(\land, \lor, \rightarrow \)のうち2つが連続して並んでいる場合は右側の結合を優先する.

すなわち,\( \varphi \rightarrow \psi \rightarrow \theta \)は\( \varphi \rightarrow (\psi \rightarrow \theta) \)を表すことにします.

定義(素論理式)
命題変数全体および\( \bot \)の集合を\(I\)で表し,素論理式と呼ぶ.

つまり,論理記号\( \lnot, \land, \lor, \rightarrow \)が使用されていない論理式を素論理式ということにします.

モデルの定義

定義(付値・構造)
\(2 = \{0, 1\} \)と表す. 素論理式\(I\)上の写像,
\( \nu : I \rightarrow 2, \)
付値という.ただし,\( \nu(\bot) = 0\)で定める.
また, \(2\)と付値の組\( \mathcal{S} = \langle 2, \nu \rangle \)を構造という.

\(2 = \{0, 1\} \)という表記は数理論理学でまま見かけます.最初は疑問に思うかもしれませんが順序数に関する知識があると自然に思えるはずです.

付値はすべての論理式に一意に拡張できます.拡張の仕方は次で定めます.

\( \nu( \lnot \varphi ) := 1 – \nu(\varphi), \)
\( \nu( \varphi \land \psi ) := {\rm min}(\nu(\varphi), \nu(\psi)), \)
\( \nu( \varphi \lor \psi ) := {\rm max}(\nu(\varphi), \nu(\psi)), \)
\( \nu( \varphi \rightarrow \psi ) := {\rm max}(1 – \nu(\varphi), \nu(\psi)), \)

これらの拡張によって\( \nu \)は論理式全体の上の関数に拡張されます.とくに混乱は起きないので付値といえば論理式全体の上に拡張されているものとして扱います.

定義(モデル)
論理式の集合を\( \Gamma \)とする. 構造\( \mathcal{M} \)が任意の\( \varphi \in \Gamma\)に対して\( \nu(\varphi) = 1\)を満たすとき,\( \mathcal{M} \)を\( \Gamma \)のモデルといい, \( \mathcal{M} \vDash \Gamma \)と表す.
命題論理においてはどんな構造についても\( \mathcal{M} = \langle 2, \nu \rangle \)の\(2\)は固定であるから,これを省略し\(\nu \vDash \Gamma\)のように付値をそのモデルと同一視することにする.とくに,\(\nu \vDash \Gamma\)が成り立つことを\(\nu \) が \( \Gamma\)を充足するという.また,あるモデル\( \nu \)が存在して\(\nu \vDash \Gamma\)となるとき\( \Gamma \)は充足可能という.

参考文献

[1] 新井敏康,数学基礎論 増補版,東京大学出版会,2021.

[2] 前原昭二,復刊 数理論理学序説,共立出版,1966.

[3] 鹿島亮, 現代基礎数学15 数理論理学, 朝倉書店, 2009.

コメントを残す