命題論理に入門したい！
目次
- はじめに
- 準備
- 定義
- $\Omega$は"本当にほしいもの"か？
- モデル論
はじめに
今回は、命題論理に入門したい！ということで、基礎論のいくつかの本を読んで、学んだ内容を勉強ノート替わりにここに書き留めたいと思います。
本記事では、命題論理についての形式的な定義から、命題の真偽、コンパクト性定理まで述べます。
以下、この記事では$\omega=\mathbb{N}=\{0,1,2,\dots\},\mathbb{N}_{>0}=\mathbb{N}^+=\{1,2,3,\dots\}$とし、
自然数$n$と言った場合は、$n\in\mathbb{N}$を指すものとする。
準備
集合$X$に対して、$X$の要素を並べた有限列全体の集合を$X^{<\omega}=\displaystyle\bigcup_{n=1}^\infty{X^n}$で定める。
$X$の有限列$x\in X^{<\omega}$に対して、$x\in X^n$なる$n$が一意に存在する。この$n$を有限列$x$の長さ(length)という。
記法
長さ$n$の有限列$x$が$x=(x_1,x_2,\dots,x_n)$であるとき、
$x=x_1x_2\dots x_n$と書くと約束する。
また、$x=x_1\dots x_n,y=y_1\dots y_n$のとき、$xy=x_1\dots x_ny_1\dots y_n$とする。
定義
$\Omega_0$を可算集合とする。
また、$\mathbb{N}$から$\Omega_0$への全単射でもって、$\Omega_0$の元を$0$番目から順に一列に並べておく。
すなわち、$\Omega_0=\{p_0,p_1,p_2,\dots \}$とする。
これらの$p_n\in\Omega_0$ $(n=0,1,2,\dots)$を命題変項(propositional variable)といい、これらは原子命題を表す非論理記号 (nonlogical symbol)である。
記号$\neg,\land,\vee,\to,(,)$を論理記号(logical symbol)という。これら6つのうち丸括弧以外は論理演算子を表す記号である。
論理記号はすべて$\Omega_0$に含まれないとする。
つまり、$\{\neg,\land,\vee,\to,(,)\}\cap \Omega_0=\varnothing$である。
$\Omega_{lng}=\{\neg,\land,\vee,\to,(,)\}\cup\Omega_0$を、命題論理の言語(language)という。
また、$\Omega_{seq}$を$\Omega_{lng}$の有限列全体、つまり、$\Omega_{seq}＝\Omega_{lng}^{<\omega}$と定め、
$\Omega_{seq}$の元を記号列(symbolic sequence)と呼ぶ。
$(\neg x) $や$ ((p\to q)\land(q\to p))$なども記号列だが、これに限らず、
$\to \to p$とか$\neg\neg))$とか$\land\land\neg\neg q$みたいな意味不明（まだ"意味"も定義していないが...）なやつも記号列に含まれる。
また、命題変項$p_n\in\Omega_0$も、長さ1の記号列である。
上で述べたように、扱いたい文字列ではないものまで$\Omega_{seq}$に入ってくるので、これをうまいこと落として"論理式"を定義したい。ここでは二通りで述べる。しっくりくる方で理解すれば良いと思う。
記号列のうち、論理式(formula)であるものを、以下のように帰納的に定める。
- 命題変項$p_n\in\Omega_0(n=0,1,2,\dots)$は論理式である。
- $A,B$が論理式ならば、$(\neg A),(A\land B),(A\vee B),(A\to B)$という記号列は全て論理式である。
- 以上により論理式であると定まる記号列以外は論理式ではない。
以上により定まる$ \Omega_{seq}$に含まれる論理式全体の集合を$\Omega$とする。
記号列全体の集合$ \Omega_{seq}$の部分集合$\Omega'\subset \Omega_{seq}$が論理的であるとは、$\Omega'$が以下を満たすことである。
- $\Omega'$は全ての命題変項$p_n\in\Omega_0(n=0,1,2,\dots)$を含む。つまり、$\Omega_0\subset\Omega'\subset\Omega_{seq}$を満たす。
- 記号列$A,B$が、もし$\Omega'$の元ならば、$(\neg A),(A\land B),(A\vee B),(A\to B)$という記号列は全て$\Omega'$の元である。
$ \Omega_{seq}$はそれ自身、$ \Omega_{seq}$の論理的な部分集合である。よって論理的な部分集合は少なくとも1つ存在する。$ \Omega_{seq}$の論理的な部分集合のうち、(包含関係で)最小のものを$\Omega\subset\Omega_{seq}$と定める。$\Omega$は$ \Omega_{seq}$の全ての論理的な部分集合の共通部分と一致するので存在することがわかる。
このとき、$\Omega$に含まれる記号列を論理式(formula)という。
ここで得た、$\Omega$は我々が普段数学をしている日常生活でよく見る意味での論理式と一致していると考えて良いだろう。丸括を必ず書かなければいけないというルールがあるが、それも後々省略することになる。
$\Omega$は"本当にほしいもの"か？
さて、前節では論理式と論理式全体の集合$\Omega$を定義したが、これは本当に我々がほしいものになっているのだろうか？という疑問が残る。本当にほしいものとは、命題変項から出発して、$\neg,\land,\vee,\to$をつける操作を有限回繰り返して得られる記号列のことである。もちろん、そのような記号列は全て論理式であることは明らかであろう。しかし、この操作で得られるものが論理式の全てだろうか？という問題が残る。そこで、問題をはっきり述べるために以下を定義する。
$\Omega_0=\{p_0,p_1,p_2,...\}$(再掲)
$\Omega_1=\{A,(\neg A),(A\land B),(A\vee B),(A\to B)\mid A,B\in\Omega_0\}$
$...$
$\Omega_{n+1}=\{A,(\neg A),(A\land B),(A\vee B),(A\to B)\mid A,B\in\Omega_n\}$
$...$
として、帰納的に$\Omega_n(n=0,1,2,\dots)$を定義する。また、
$\Omega_\infty=\displaystyle\bigcup_{n\in\mathbb{N}}\Omega_n=\Omega_0\cup\Omega_1\cup\dots\cup\Omega_n\cup\dots$
また定義から、これらは上昇列
$\Omega_0\subset\Omega_1\subset\dots\subset\Omega_n\subset\dots\subset\Omega_{\infty}$
をなす。また、$\Omega_{\infty}$の元$x$に対して$x\in\Omega_n$となる最小の$n$を$x$の深さといい、$n=d(x)$で表す。
実は、この$\Omega_{\alpha} $は一般の順序数$\alpha$に対して定義できる。いわゆる超元気農法💪もとい超限帰納法である。
順序数$\alpha$に対して、$\Omega_{\alpha}$を以下で定義する。
- $\alpha=0$のとき、$\Omega_0=\{p_0,p_1,p_2,...\}$(再掲)
- $\alpha$が後続順序数で$\alpha=\beta+1$のとき、
$\Omega_{\alpha}=\{A,(\neg A),(A\land B),(A\vee B),(A\to B)\mid A,B\in\Omega_{\beta}\}$ - $\alpha$が極限順序数のとき、
$\Omega_{\alpha}=\displaystyle\bigcup_{\beta<\alpha}\Omega_{\beta}$
これに従うと、$\Omega_{\infty}$とは$\Omega_{\omega}$のことであると分かる。しかし実際は、$\omega\leq\alpha$なる任意の順序数$\alpha$に対して、$\Omega_{\infty}=\Omega_{\alpha}$であることが、以下の命題から従う。
$\Omega=\Omega_{\infty}$
各$n$に対して、$ \Omega_n$の定義から明らかに、$\Omega_n\subset \Omega$
よって、$\Omega_{\infty}\subset \Omega$
一方、$A,B$を$\Omega_{\infty}$の任意の元とする。ここで、$n=\max\{d(A),d(B)\}$とすると、$A,B\in\Omega_n$であるから、$(\neg A),(A\land B),(A\vee B),(A\to B)\in\Omega_{n+1}\subset\Omega_{\infty}$
よって、$\Omega_{\infty}$は$\Omega_{seq}$の論理的な部分集合だから、$ \Omega$の最小性から、$\Omega\subset \Omega_{\infty}$
ゆえに、$\Omega=\Omega_{\infty}$
以上より、$\Omega$が本当に我々がほしい集合であるとわかった。
モデル論
ここまでで、命題論理に用いる記号と、その記号列のうち、命題論理が扱う"論理式"と呼ばれる形の記号列を定義した。ここで再度確認する。
$\Omega_0=\{p_0,p_1,p_2,\dots \}$
$\Omega_{lng}=\{\neg,\land,\vee,\to,(,)\}\cup\Omega_0$
$\Omega_{seq}＝\Omega_{lng}^{<\omega}$
$\Omega=\bigcap\{\Omega'\mid\Omega'\subset\Omega_{seq}$は論理的$\}$
さて、論理式は定義したので、次に考えたいのは"真偽"である。ただし、当然$\Omega_0$に属する各命題変項$p_n$は自明に真偽が決まっているわけではない。しかし、論理式$A$と$B$の真偽が定まれば、$(\neg A),(A\land B),(A\vee B),(A\to B)$の真偽も定まってほしい。そこで、論理式の真偽を以下で定義する。
写像$v:\Omega\rightarrow \{0,1\}$が真理値関数あるいはモデル,解釈,意味であるとは、写像$v$が以下を満たすことである。
- $v((\neg A))=1\Longleftrightarrow v(A)=0$
- $v((A\land B))=1\Longleftrightarrow v(A)=1$かつ$v(B)=1$
- $v((A\vee B))=1\Longleftrightarrow v(A)=1$または$v(B)=1$
- $v((A\to B))=1\Longleftrightarrow v(A)=0$または$v(B)=1$
論理式$A\in\Omega$と真理値関数$v$に対して、
$v(A)=1$となるとき、$A$は$v$において真である(充足する,妥当である)といい、
$v(A)=0$となるとき、$A$は$v$において偽である(充足しない,非妥当である)という。
また、
$A$は$v$において真であるとき、$v\vDash A$
$A$は$v$において偽であるとき、$v\nvDash A$
と書く。
ここで興味があるのは、$\Omega$の部分集合上で$1$を取る真理値関数、つまり、いくつかの論理式を真にさせるモデルについてである。そのようなモデルの存在の有無や、それら全てで一定の真偽値を持つ命題について考える。
$T\subset\Omega$に対して、$T$上で常に値が$1$のみを取る真理値関数を、$T$を充足する真理値関数あるいは$T$のモデルという。真理値関数$v$が$T$を充足するとき、$v\vDash T$と書く。
$T\subset\Omega$に対して、$T$を充足する真理値関数が存在するとき、
$T$は充足可能であるという。
$T\subset\Omega$と$A\in\Omega$に対して、$T$を充足する任意の真理値関数$v$に対して、$v$が$A$を充足するとき、つまり、任意の真理値関数$v$に対して、
$v\vDash T \Longrightarrow v\vDash A$
が成り立つとき、$A$を$T$上妥当であるといい、$T\vDash A$と書く。
$T=\{p_0,(\neg p_0)\}\subset\Omega$とすると、$T$は充足不可能である。
実際、任意の真理値関数$v$に対して、$v(p_0)=0\Longleftrightarrow v((\neg p_0))=1$より、$v(p_0)=v((\neg p_0))=1$となることはない。
$\Omega_0$及びその部分集合は充足可能である。
実際、帰納的に(深さに関する帰納法により)$\Omega_0,\Omega_1,...$と順次真偽値を確定させていくことで、具体的に目的の真理値関数を得ることができる。
この真理値関数について考察することが、命題の真偽についての形式的な考察に繋がる。
以下の命題は最も基礎的な定理の一つである。
$T\subset\Omega$に対して、$T$の任意の有限部分集合$T_0\subset T$が充足可能とする。
このとき、$T$は充足可能。
この証明は、もう少し準備が必要なので、次回に回す。
力尽きたので、今回はここで。次回はコンパクト性定理の証明を目指します。
この記事を高評価した人
この記事に送られたバッジ
投稿者
