数理論理学：ノート2 - クッキーの日記

読んでいる本（出典）：数理論理学 | 戸次大介 |本 | 通販 | Amazon

前回：ノート1 ／次回：ノート3
目次：数理論理学

以下、第3章の自分の理解。第3章は一階命題論理。

一階命題論理の統語論

一階命題論理では、命題（≡ 真偽を問うことのできる形式）を下のような論理式にかきあらわす。
この形式を満たさないものは論理式ではない。
一階命題論理に
おける論理式 $P, \; Q, \; R,$ 　命題記号は論理式
$\top , \; \perp , \; \lnot(P) , \; \land(P, Q) , \; \to \! \! (P, Q),$ 　 $n$ 項真理関数に論理式を代入した形式も論理式
$\lnot(\top) , \; \lor(\land(P, Q), R) , \; \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R))$ 　なので、これらも論理式
ちなみに、上の例の最後の論理式の部分論理式の集合は以下。
${\rm SubF}\bigl( \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R)) \bigr) = \{ \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R)) \} \cup {\rm SubF}\bigl( \lnot(\top) \bigr) \cup {\rm SubF}\bigl( \lor(\land(P, Q), R)) \bigr)$
　 $= \{ \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R)), \; \lnot(\top), \; \lor(\land(P, Q), R)) \} \cup {\rm SubF}\bigl( \top \bigr) \cup {\rm SubF}\bigl( \land(P, Q) \bigr) \cup {\rm SubF}\bigl( R \bigr)$
　 $= \{ \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R)), \; \lnot(\top), \; \lor(\land(P, Q), R)), \; \top, \; \land(P, Q), \; R \} \cup {\rm SubF}\bigl( P \bigr) \cup {\rm SubF}\bigl( Q \bigr)$
　 $= \{ \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R)), \; \lnot(\top), \; \lor(\land(P, Q), R)), \; \top, \; \land(P, Q), \; R, \; P, \; Q \}$

一階命題論理における論理式	$P, \; Q, \; R,$ 　命題記号は論理式 $\top , \; \perp , \; \lnot(P) , \; \land(P, Q) , \; \to \! \! (P, Q),$ 　 $n$ 項真理関数に論理式を代入した形式も論理式 $\lnot(\top) , \; \lor(\land(P, Q), R) , \; \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R))$ 　なので、これらも論理式

一階命題論理の意味論

上で命題をあらわす論理式に形式的定義を与えたので、次に、論理式の真偽を考える。ここで「真偽を問う」というのは、「集合 $D_t \equiv \{1,0\}$ の要素へ対応させる」ということとする。この $D_t$ を領域という。ここでの領域には「真（1）」と「偽（0）」のみがあり、「ちょっと真」とかはない。
それで論理式の真偽を考えると、「 $n$ は偶数である」「今年は2月29日がある」「丸の内線の線路は地下にある」「コイルはでんきタイプ単色である」など、真か偽かは状況によることに気付く。このようなあらゆる状況を明示的に取り扱うことはできない気がする。

逆に、「論理式の集合 $\rightarrow D_t$ 」という写像の1つ1つが「このような状況」を表しているといえる。

例えば、以下の原子命題を考える。
　　　　　 $P$ コイルはでんき単 $\equiv$ 「コイルはでんきタイプ単色である」
このとき、コイルはでんき単なる写像全体は以下の2つ。これらがそれぞれ状況に相当する。
写像1 写像2
$P$ コイルはでんき単 $\mapsto \; 1$ $P$ コイルはでんき単 $\mapsto \; 0$
- 写像1は感覚的には、コイルがでんき単色だった "第1世代" という状況に相当する。
- 写像2は感覚的には、はがねタイプが追加された "第2世代以降" という状況に相当する。

写像1	写像2
$P$ コイルはでんき単 $\mapsto \; 1$	$P$ コイルはでんき単 $\mapsto \; 0$

ここに原子命題をもう1つ付け加える。

　　　　　 $P$ コイルはでんき単 $\equiv$ 「コイルはでんきタイプ単色である」
　　　　　 $P$ ピッピはノーマル $\equiv$ 「ピッピはノーマルタイプである」

$\{P$ コイルはでんき単 $, \; P$ ピッピはノーマル $\} \to D_t$ なる写像全体は以下の4つになる。

写像3	写像4	写像5	写像6
$P$ コイルはでんき単 $\mapsto \; 1$ $P$ ピッピはノーマル $\mapsto \; 1$	$P$ コイルはでんき単 $\mapsto \; 1$ $P$ ピッピはノーマル $\mapsto \; 0$	$P$ コイルはでんき単 $\mapsto \; 0$ $P$ ピッピはノーマル $\mapsto \; 1$	$P$ コイルはでんき単 $\mapsto \; 0$ $P$ ピッピはノーマル $\mapsto \; 0$

写像3は感覚的には、"第1世代" という状況に相当する。
写像4のような世代は実際なかったが、とりあえず状況としては定義できる。
写像5は感覚的には、"第2～5世代" という状況に相当する。
写像6は感覚的には、フェアリータイプ追加後の "第6世代" という状況に相当する。

この「 $I:$ 論理式の集合 $\rightarrow D_t$ 」であるような写像 $I$ を解釈という。解釈という言葉へのイメージは、「地球は動いている」は、「天動説」という解釈の下では偽で、「地動説」という解釈の下では真みたいな。
解釈をつかうと、「 $P$ コイルはでんき単は真か？」という問いへの答えは「 $I(P$ コイルはでんき単 $)=1$ であるような解釈 $I$ の下では真である」になるけど、これ自体は「真のときは真です」と言っているだけなので何もうれしくない。
ただ、論理式が原子命題ではない場合、例えば「 $P$ コイルはでんき単 $\lor P$ ピッピはノーマルは真か？」という問いには、部分論理式に含まれる原子命題の真偽で場合分けすればよく、「写像3, 写像4, 写像5で表される解釈の下では真で、写像6で表される解釈の下では偽です」となる。これは「真のときは真です」以上のことを言っている。真偽を考えるべき論理式は無数に存在するが、考えなければならない状況の数は $2$ 原子命題の数だけでよい。
解釈によらず真な論理式（恒真式）もある。よく知られているものは例えば以下。
- $\varphi \land \psi \leftrightarrow \psi \land \varphi$ 　交換律
- $\varphi \lor \psi \leftrightarrow \psi \lor \varphi$ 　交換律
- $\varphi \to \psi \leftrightarrow \lnot \psi \to \lnot \varphi$ 　対偶律
- $\varphi \land \lnot \varphi$ 　排中律

じゃあ一階命題論理において妥当な推論とは何か

妥当な推論とは何かとは意味論的推論に基づくことにしていたのだが、意味論的推論を一階命題論理の言葉に書き直すとこうなる：を論理式列として（ただしは高々）、以下を満たすとき「はを意味論的に含意する」といい、とかく。
- 以下のような解釈が存在しない。
  - $\Gamma$ に含まれるすべての論理式 $\varphi$ について $I(\varphi)=1$ である。
  - $\Delta$ に含まれるすべての論理式 $\psi$ について $I(\psi)=0$ である。
例えば、は妥当な推論である。つまり、が成立する。これは、以下の真偽値表で確認できる。
- まず、登場する原子命題が $P, Q, R$ の3つなので、 $2^3=8$ つの解釈を考えればよい（下表の各行）。
- それぞれの解釈の下での $P \to Q, \; Q \to R, \; P \to R$ の真偽値を書き入れる。
- $P \to Q, \, Q \to R \, \models \, P \to R$ であるためには、 $I(P \to Q), \; I(Q \to R)$ が $1$ であって、 $I(P \to R)$ が $0$ であるような解釈 $I$ が存在してはならないが、 $I(P \to Q), \; I(Q \to R)$ が $1$ であるような行を薄い青で塗ると、それらの行ではすべて $I(P \to R)$ が $1$ なので、 $P \to Q, \, Q \to R \, \models \, P \to R$ は成立する。

$P$	$Q$	$R$	$P$	$\to$	$Q$	$Q$	$\to$	$R$	$P$	$\to$	$R$
1	1	1	1	1	1	1	1	1	1	1	1
1	1	0	1	1	1	1	0	0	1	0	0
1	0	1	1	0	0	0	1	1	1	1	1
1	0	0	1	0	0	0	1	0	1	0	0
0	1	1	0	1	1	1	1	1	0	1	1
0	1	0	0	1	1	1	0	0	0	1	0
0	0	1	0	1	0	0	1	1	0	1	1
0	0	0	0	1	0	0	1	0	0	1	0

$\quad \models \varphi$ は論理式 $\varphi$ が恒真であることを意味する（ $I(\varphi)=0$ となる解釈 $I$ が存在しないということだから）。
$\Gamma \models \quad$ は論理式列 $\Gamma$ が矛盾していることを意味する（ $\Gamma$ に含まれるすべての $\varphi$ を同時に $I(\varphi)=1$ とする解釈 $I$ が存在しないということだから）。
$\varphi \models \psi$ かつ $\psi \models \varphi$ のとき、 $\varphi$ と $\psi$ は意味論的に同値であるといい、 $\varphi = \! \! \! | | \! \! \! = \psi$ とかく。
真偽値表をかけばどんな推論も妥当かどうか手続き的に確かめられるが、以下のような定理（教科書には他にも色々示されている）を活用するともっと楽になる。「推論が意味論的に妥当かどうか」を、「論理式が恒真かどうか」という確認に落とし込むとよい。
- $\varphi \models \psi \; \Longleftrightarrow \; \models \varphi \to \psi$
- $\varphi = \! \! \! | | \! \! \! = \psi \; \Longleftrightarrow \; \models \varphi \leftrightarrow \psi$
- ある論理式と、その論理式の部分論理式を意味論的同値な論理式に置き換えた論理式は、意味論的同値。置き換え
- $\Gamma \models \varphi, \; \; \Delta, \varphi, \Delta' \models \psi \; \Longrightarrow \; \Delta, \Gamma, \Delta' \models \psi$ 　カット
- $\varphi, \Gamma \models \perp \; \Longleftrightarrow \; \Gamma \models \lnot \varphi$ 　背理法

ここまで来て気付くこと

項真理関数を色々考えていたけど、冷静に考えると任意の真偽値の出力ってだけでできるのでは。
- 真偽値表で1になる行を全部抜いてきて、 $(P \land Q \land R) \lor (P \land \lnot Q \land R) \lor \cdots$ のようにつないでいけばよい。選言標準形
- 逆に、真偽値表で0になる行を抜いてきて、 $(P \land Q \land \lnot R) \land (P \land \lnot Q \land \lnot R) \land \cdots$ のようにつないでいって最後に全体に $\lnot$ してもよい。連言標準形
もっというと、ドゥ・モルガンの法則をつかうとをに換えたり、その逆ができるので、からかのどちらか一方をリストラしてもあらゆる真偽値の出力がつくれる。表現的適格性
- $\{ \lnot, \; \land \}$ や $\{ \lnot, \; \lor \}$ という組でなくてもよい。例えば $\{\lnot, \; \to\}$ でもOK。
さらにいうと、NAND または NOR は単独で表現的に適格になれる。

練習問題3.27　面倒なので略。

まず、(論理式全体の集合)＝(命題記号の集合) $\oplus$ (複合論理式の集合)。
仮定より、解釈 $I_1$ と $I_2$ で、任意の命題記号について、 $I_1 ($ 命題記号 $)=I_2 ($ 命題記号 $)$ 。
複合論理式は、手元に命題記号たちだけがある状態からはじめて、項真理関数を有限回つかえばつくれる。
以下を帰納法で示せばよい。
- $I_1 ($ $n$ 項真理関数を1回つかった論理式 $)=I_2 ($ $n$ 項真理関数を1回つかった論理式 $)$
- $I_1 ($ $n$ 項真理関数を2回つかった論理式 $)=I_2 ($ $n$ 項真理関数を2回つかった論理式 $)$
- $\cdots$

練習問題3.28　面倒なので略。

練習問題3.31

$2^{2^0}=2$ より、0項真理関数は2個ある。だから、 $\top, \; \perp$ で全部。

練習問題3.35

$2^{2^1}=4$ より、1項真理関数は4個ある。だから、 $\lnot$ の他に3個ある（練習問題3.36）。

練習問題3.36

どんな値を取っても1を返す関数。
どんな値を取っても0を返す関数。
「取った値に何もせずそのまま返す」という関数。

練習問題3.39

$2^{2^2}=16$ より、2項真理関数は16個ある。だから、 $\land , \; \lor, \; \to, \; \leftrightarrow$ の他に12個ある。
っていう話を数学ガールの秘密ノート第172回でやってた。
- 第172回裏の裏は表（後編）｜数学ガールの秘密ノート｜結城浩｜cakes（ケイクス）

練習問題3.40

$n$ 項真理関数は $2$ の $2^n$ 乗個ある。

練習問題3.42　面倒なので略。

練習問題3.44　真偽値表で38～39ページの恒真式が恒真式であることを確認せよという問題。ドゥ・モルガンの法則だけ。

①	①	③		①	②	①		④	②	①	③	②	①
$\varphi$	$\psi$	$\lnot$	$($	$\varphi$	$\land$	$\psi$	$)$	$\leftrightarrow$	$\lnot$	$\varphi$	$\lor$	$\lnot$	$\psi$
1	1	0		1	1	1		1	0	1	0	0	1
1	0	1		1	0	0		1	0	1	1	1	0
0	1	1		0	0	1		1	1	0	1	0	1
0	0	1		0	0	0		1	1	0	1	1	0

①	①	③		①	②	①		④	②	①	③	②	①
$\varphi$	$\psi$	$\lnot$	$($	$\varphi$	$\lor$	$\psi$	$)$	$\leftrightarrow$	$\lnot$	$\varphi$	$\land$	$\lnot$	$\psi$
1	1	0		1	1	1		1	0	1	0	0	1
1	0	0		1	1	0		1	0	1	0	1	0
0	1	0		0	1	1		1	1	0	0	0	1
0	0	1		0	0	0		1	1	0	1	1	0

練習問題3.45　面倒なので略。

練習問題3.47　面倒なので略。

練習問題3.52

「 $\quad \models \varphi$ 」がいえるなら、左側にどんな論理式列を書いたっていい。
「 $\Gamma \models \quad$ 」がいえるなら、右側にどんな論理式を書いたっていい。

練習問題3.53

「 $\quad \models \quad$ 」は「解釈 $I$ が存在しない」を意味するが、たとえその言語に原子命題が1つもなくとも $I$ は存在するので、「 $\quad \models \quad$ 」は成立しない。

練習問題3.54

「」は「かつかつであるが存在しない」を意味する。
- $\varphi_1, \, \cdots, \, \varphi_n$ がすべて矛盾式（恒偽式）であれば「 $\varphi_1, \, \cdots, \, \varphi_n \models \quad$ 」である。
- ただ、すべて矛盾式でなくとも、 $\varphi_1, \, \cdots, \, \varphi_n$ に1つでも矛盾式が含まれれば「 $\varphi_1, \, \cdots, \, \varphi_n \models \quad$ 」である。
- もっというと、個々の論理式は矛盾式でなくとも、に含まれる2つ以上の論理式の組をすべて真にする解釈がなければ、「」である。
  - 例えば、 $P$ と $\lnot P$ それぞれを真にする解釈はあるが、これらを同時に真にする解釈はない。

練習問題3.58　面倒なので略。

練習問題3.59　最初のだけ上のノート内で解いた。

練習問題3.63　面倒なので略。

練習問題3.64　面倒なので略。

練習問題3.66　面倒なので略。

練習問題3.67

1) 　 $(\lnot P \to P) \leftrightarrow P$ は恒真式。
2) 　左側が恒偽式なので、右側は何でもいい。
3) 　 $\lnot P \leftrightarrow (P \to \perp)$ は恒真式。
4) 　 $(P \to Q) \to (\lnot P \to \lnot Q)$ は恒真式ではないので意味論的妥当性は成立していない。

練習問題3.71　面倒なので略。

練習問題3.73　面倒なので略。

1) 　対偶律＋二重否定律
2) 　分配律＋ドゥ・モルガンの法則
3) 　同一律＋ドゥ・モルガンの法則＋二重否定律

練習問題3.80　面倒なので略。

練習問題3.84　何この問題。

身内の犯行であるならば、貞夫か光枝が犯人である。	$P \to Q \lor R$
貞夫が犯人ならば、犯人は財産目当てではない。	$Q \to \lnot S$
犯人が財産目当てならば、光枝は犯人ではない。	$S \to \lnot R$
したがって、身内の犯行であるならば、犯人は財産目当てではない。	$P \to \lnot S$

妥当性を示すべき推論： $P \to Q \lor R, \; \; Q \to \lnot S, \: \: S \to \lnot R \; \; \models \; \; P \to \lnot S$
以下に略解を記す。

1)	$Q \to \lnot S , \; \; R \to \lnot S \; \; \models \; \; Q \lor R \to \lnot S$	（構成的両刃論法）
2)	$Q \to \lnot S , \; \; S \to \lnot R \; \; \models \; \; Q \lor R \to \lnot S$	（1) の前提の一部を対偶律で置き換え）
3)	$P \to Q \lor R , \; \; Q \lor R \to \lnot S \; \; \models \; \; P \to \lnot S$	（推移律）
4)	$P \to Q \lor R , \; \; Q \to \lnot S , \; \; S \to \lnot R \; \; \models \; \; P \to \lnot S$	（2) と 3) をカット）

練習問題3.87

1)	$\models \; \; \varphi \to \psi \; \; \; \Longleftrightarrow \; \; \; \varphi \; \; \models \; \; \psi$	（定理 3.60）
2)	$\models \; \; \psi$	（ $\models \varphi$ と 1) をカット）

練習問題3.89　面倒なので略。

練習問題3.91
背理法以前にこの推論は妥当でない。出題ミス？

練習問題3.94
左側は0になっている行がないので連言標準形の手続きを進めることができないし、右側は1になっている行がないので選言標準形の手続きを進めることができないよね。

練習問題3.95　面倒なので略。

練習問題3.101　面倒なので略。

練習問題3.103　 $n$ 項真理関数を別の $n$ 項真理関数で表現。

1) 　 $\varphi \to \psi \; = \! \! \! | | \! \! \! = \; \lnot(\varphi \land \lnot \psi)$
2) 　 $\varphi \to \psi \; = \! \! \! | | \! \! \! = \; \lnot \varphi \lor \psi$
3) 　 $\varphi \lor \psi \; = \! \! \! | | \! \! \! = \; (\varphi \to \psi) \to \psi$
4) 　 $\varphi \land \psi \; = \! \! \! | | \! \! \! = \; ((\varphi \to \psi) \to \psi) \leftrightarrow (\varphi \leftrightarrow \psi)$
5) 　 $\land$ は $\to$ のみでは表現できないことを示すのはすぐできなさそうなのでパス。

練習問題3.106　面倒なので略。

練習問題3.107
一項真理関数は原子命題を1つとって「そのまま返す」「裏返して返す」「1にして返す」「0にして返す」しかできない。
2つ目以降の原子命題を全く考慮できない。

所感

以下の記事を書くときにペアノの公理の5番目ってなんでこんな浮いているんだろうと思ったけど、自然数の定義に自然数をつかってはいけないのでそんな感じにせざるをえない。たぶん。
- 雑記：読書メモ - クッキーの日記
それで、一階命題論理では集合の概念をつかっているけど、本来集合の概念自体が論理体系を整えた上にあるのに大丈夫？というのが心配になるけど、それについては集合の概念を回避できる意味論もあるらしい（35ページ注釈9）。
意味論的同値の記号 $= \! \! \! | | \! \! \! =$ ってこうですか。わかりません。
= \! \! \! | | \! \! \! =