命題論理の構文と意味論 | 数理論理

1 論理式の有限高さ構成

定義 1.1. 命題変数の集合を $P$ とする。各構成子には互いに異なるタグを付ける。高さが高々 $n$ の論理式の集合 $F_n$ を

F_0=\{\langle\mathrm{var},p\rangle:p\in P\},\qquad F_{n+1}=F_n\cup\{\langle\neg,\varphi\rangle:\varphi\in F_n\} \cup\{\langle\to,\varphi,\psi\rangle:\varphi,\psi\in F_n\}

で定める。命題論理式 (propositional formula) 全体を

\operatorname{Form}(P)=\bigcup_{n<\omega}F_n

とする。変数タグ $\langle\mathrm{var},p\rangle$ は $p$ と書き、ほかのタグ付き組は通常の記法で $\neg\varphi$ と $(\varphi\to\psi)$ と書く。 $\varphi$ が属する最小の $F_n$ の添字を $\operatorname{ht}(\varphi)$ (formula height) と呼ぶ。

派生結合子は

\begin{aligned} \varphi\land\psi&:=\neg(\varphi\to\neg\psi),\\ \varphi\lor\psi&:=\neg\varphi\to\psi,\\ \varphi\leftrightarrow\psi&:=(\varphi\to\psi)\land(\psi\to\varphi) \end{aligned}

によって定める。 $P$ が空でないとき、 $p\in P$ を一つ固定して $\bot:=\neg(p\to p)$ 、 $\top:=p\to p$ と略記する。

有限段階の和集合として定めたため、すべての論理式は有限の高さをもつ。タグは外側の構成子を記号列の解析に依存せず一意にする。

命題 1.2. 任意の $\varphi\in\operatorname{Form}(P)$ は、命題変数、 $\neg\psi$ 、 $(\psi\to\chi)$ のちょうど一つの形をとる。後二者では直下の論理式も一意である。また、 $P$ を含み、否定と含意の構成で閉じた任意の集合 $C$ は $\operatorname{Form}(P)$ を含む。

証明. 三種類のタグの像は互いに素であり、各タグ付き構成子は引数について単射である。したがって三つの形は排反であり、直下の論理式も一意である。

最小性を示す。 $C$ が主張の条件を満たすとする。通常記法の下で $F_0=P\subseteq C$ である。 $F_n\subseteq C$ と仮定すると、 $C$ の閉性から $F_{n+1}\subseteq C$ である。自然数に関する帰納法により、すべての $n<\omega$ について $F_n\subseteq C$ となる。ゆえに $\operatorname{Form}(P)=\bigcup_{n<\omega}F_n\subseteq C$ である。▨

定理 1.3. $A\subseteq\operatorname{Form}(P)$ が次の条件を満たすとする。

すべての $p\in P$ について $p\in A$ である。
$\varphi\in A$ ならば $\neg\varphi\in A$ である。
$\varphi,\psi\in A$ ならば $(\varphi\to\psi)\in A$ である。

このとき $A=\operatorname{Form}(P)$ である。

証明. $F_n\subseteq A$ を $n$ に関して帰納的に示す。 $F_0=P\subseteq A$ である。 $F_n\subseteq A$ と仮定すると、第二条件と第三条件により $F_{n+1}\subseteq A$ である。したがって $\operatorname{Form}(P)=\bigcup_{n<\omega}F_n\subseteq A$ である。逆の包含は $A$ の仮定に含まれる。▨

構造帰納法は論理式についての性質を証明する。構造再帰は論理式から別の集合への写像を定義する。

定理 1.4. 集合 $X$ 、写像 $a:P\to X$ 、写像 $N:X\to X$ 、写像 $I:X\times X\to X$ を与える。このとき、次を満たす写像 $h:\operatorname{Form}(P)\to X$ が一意に存在する。

h(p)=a(p),\qquad h(\neg\varphi)=N(h(\varphi)),\qquad h(\varphi\to\psi)=I(h(\varphi),h(\psi)).

証明. $h_n:F_n\to X$ を $n$ に関して構成する。 $h_0=a$ とする。 $h_n$ が定まったとき、 $F_{n+1}\setminus F_n$ の各元には一意可読性によって外側の構成子と直下の論理式が一意に定まる。直下の論理式は $F_n$ に属するので、表示された二つの再帰式によって $h_{n+1}$ を定める。 $F_n$ 上では $h_{n+1}=h_n$ とする。この構成は整合しているから、

h=\bigcup_{n<\omega}h_n

は求める写像である。

$g$ も同じ再帰式を満たすとする。 $h$ と $g$ が $F_n$ 上で一致することを $n$ に関して帰納的に示す。 $F_0$ 上では両者とも $a$ である。 $F_n$ 上で一致すれば、再帰式と一意可読性により $F_{n+1}$ 上でも一致する。したがって $h=g$ である。▨

例 1.5 (構文木の高さ). $p,q\in P$ とする。論理式

\neg\bigl(p\to\neg q\bigr)

の高さは $3$ である。外側から順に否定、含意、右側の否定を除くと命題変数に到達する。派生記号では $p\land q$ と書くが、構文上は原始記号による左辺の木を指す。

2 付値と真理値

定義 2.1. 二元集合を $\mathbf 2=\{0,1\}$ とする。命題変数への写像 $v:P\to\mathbf 2$ を付値 (valuation) という。論理式の真理値 (truth value) $\widehat v:\operatorname{Form}(P)\to\mathbf 2$ は

\widehat v(p)=v(p),\qquad \widehat v(\neg\varphi)=1-\widehat v(\varphi),

\widehat v(\varphi\to\psi)= \begin{cases} 0&\widehat v(\varphi)=1\text{ かつ }\widehat v(\psi)=0,\\ 1&\text{それ以外} \end{cases}

によって定める。 $\widehat v(\varphi)=1$ を $v\models\varphi$ と書く。

系 2.2. 任意の付値 $v:P\to\mathbf 2$ は、定義 2.1の再帰式を満たす真理値関数へ一意に拡張される。

証明.定理 1.4において $X=\mathbf 2$ とし、 $N$ と $I$ を否定と含意の真理値演算に取れば、存在と一意性を得る。構造再帰定理は本稿で証明済みであるから、別の存在仮定を用いていない。▨

命題 2.3. $\operatorname{Var}(\varphi)$ を $\varphi$ に現れる命題変数の有限集合とする。付値 $v,w:P\to\mathbf 2$ が $\operatorname{Var}(\varphi)$ 上で一致するなら、 $\widehat v(\varphi)=\widehat w(\varphi)$ である。

証明. $\operatorname{Var}(p)=\{p\}$ 、 $\operatorname{Var}(\neg\psi)=\operatorname{Var}(\psi)$ 、 $\operatorname{Var}(\psi\to\chi)=\operatorname{Var}(\psi)\cup\operatorname{Var}(\chi)$ と再帰的に定める。 $\varphi$ に関する構造帰納法を用いる。命題変数の場合は仮定そのものである。否定の場合は帰納法の仮定と否定の真理値規則から従う。含意の場合は二つの直下の論理式に帰納法の仮定を適用し、含意の真理値規則を用いる。▨

例 2.4 (派生結合子の意味). 定義を展開すると、 $v\models\varphi\land\psi$ は $v\models\varphi$ かつ $v\models\psi$ と同値である。また、 $v\models\varphi\lor\psi$ は $v\models\varphi$ または $v\models\psi$ と同値である。ここで「または」は両方が真である場合を含む。

3 三つの意味論的概念

定義 3.1. $\varphi\in\operatorname{Form}(P)$ 、 $\Gamma\subseteq\operatorname{Form}(P)$ とする。

$\varphi$ が充足可能 (satisfiable) であるとは、 $v\models\varphi$ を満たす付値 $v:P\to\mathbf 2$ が少なくとも一つ存在することをいう。
$\varphi$ が恒真 (valid) であるとは、すべての付値 $v:P\to\mathbf 2$ について $v\models\varphi$ が成り立つことをいい、 $\models_{\mathrm{PL}}\varphi$ と書く。
$\varphi$ が $\Gamma$ の意味論的帰結 (semantic consequence) であるとは、すべての付値 $v:P\to\mathbf 2$ について、 $v\models\gamma$ がすべての $\gamma\in\Gamma$ について成り立つなら $v\models\varphi$ が成り立つことをいい、 $\Gamma\models_{\mathrm{PL}}\varphi$ と書く。

命題 3.2. 次が成り立つ。

任意の $\varphi\in\operatorname{Form}(P)$ について、 $\varphi$ が恒真であることと、 $\{\neg\varphi\}$ を同時に真にする付値が存在しないことは同値である。
任意の $\Gamma\subseteq\operatorname{Form}(P)$ と任意の $\varphi\in\operatorname{Form}(P)$ について、 $\Gamma\models_{\mathrm{PL}}\varphi$ であることと、 $\Gamma\cup\{\neg\varphi\}$ を同時に真にする付値が存在しないことは同値である。
$P\ne\varnothing$ ならば、充足可能であるが恒真でない論理式が存在する。

証明.(1)は $\widehat v(\neg\varphi)=1-\widehat v(\varphi)$ による。(2)について、 $\Gamma\models_{\mathrm{PL}}\varphi$ が成り立たないことは、すべての $\gamma\in\Gamma$ を真にし、 $\varphi$ を偽にする付値が存在することと同値である。否定の真理値規則により、後者は $\Gamma\cup\{\neg\varphi\}$ を同時に真にする付値が存在することと同値である。(3)では $P\ne\varnothing$ であるから $p\in P$ を取ることができる。論理式 $p$ は $v(p)=1$ とすれば充足可能であるが、 $v(p)=0$ とする付値の下では偽である。▨

例 3.3 (意味論的帰結の量化範囲). $\{p,p\to q\}\models_{\mathrm{PL}}q$ である。実際、 $p$ と $p\to q$ をともに真にする付値では、含意が偽になる唯一の場合を除外するため $q$ も真である。一方、 $\{p\lor q\}\not\models_{\mathrm{PL}}p$ である。 $v(p)=0$ 、 $v(q)=1$ が反例を与える。

4 演習

問題 4.1.

$\operatorname{Var}((p\to q)\to p)$ を求め、この論理式の真理値を決めるために $P$ 上の付値全体が不要である理由を述べよ。
$p\to(q\to p)$ が恒真であることを、含意が偽になる条件から証明せよ。
「充足可能」と「恒真」を入れ替えることができない例を一つ与えよ。

解答 (確認問題の解答).

変数集合は $\{p,q\}$ である。命題 2.3により、 $p,q$ 上の値だけが真理値を決める。
外側の含意が偽なら $p$ は真で $q\to p$ は偽である。後者が偽なら $p$ は偽であり、矛盾する。したがって外側の含意はすべての付値で真である。
$p$ は充足可能であるが恒真ではない。

▨

構文上の形成規則は、どの文字列が論理式であるかを決める。付値の再帰的拡張は、形成規則に沿って各論理式の真理値を決める。両者を分離したうえで、次に有限個の変数に対する真理表と標準形を扱う。

§E16.1命題論理の構文と意味論

1 論理式の有限高さ構成

2 付値と真理値

3 三つの意味論的概念

4 演習

参考文献

前提記事