このブログは、旧・はてなダイアリー「檜山正幸のキマイラ飼育記 メモ編」（http://d.hatena.ne.jp/m-hiyama-memo/）のデータを移行・保存したものであり、今後（2019年1月以降）更新の予定はありません。

今後の更新は、新しいブログ http://m-hiyama-memo.hatenablog.com/ で行います。

問題集6の目的と解答と追加説明 (A14R6-1)

RSS練習問題

※この記事は「記事14 解答6-1」

問題集6とは、次の記事（の問題部分）のことです：

解答だけでなく、「どうしてこのような練習をするか？」や、関連する事項の説明もします。誤解されがちなメタ論理やメタ論理記号、反例と正例の話題にも触れます。

解説も付けたらだいぶ長くなったので、今回は問題集6の途中までです。残りは引き続く記事にします。

内容：

  1. 自然言語へ翻訳しても数学的な意味はない
  2. 限量子を含まない閉論理式
  3. 限量子を含む閉論理式
  4. 反例と正例
  5. 限量子の数学的（素朴集合論的）解釈
  6. 補集合の性質、ついでに「メタ」について
  7. 限量子を含む閉論理式の解説 (途中)

自然言語へ翻訳しても数学的な意味はない

論理記号は次の表と共に導入されます。

記号 意味
∧ かつ
∨ または
¬ ではない
⇒ ならば

この表の右欄の「意味」は、自然言語（日本語）としての意味です。記号 ←→ 日本語 の翻訳が出来ても、数学的な意味は何も確定しません。

記号'∧'の数学的意味を定義するひとつの方法は、∧を {0, 1}×{0, 1}→{0, 1} という写像〈関数 | 演算〉だと解釈して、写像∧の定義を下のように与えることです。ここで、0は偽、1は真を表すとします。

∧ 0 1
0 0 0
1 0 1

他の論理記号も同様にして、写像として数学的意味を確定できます。

しかし、変数xがある場合、

  • 0 ≦ x ∧ x ≦ 1

における'∧'の意味は明らかではありません。次のような解釈があります。

  • xの値が決まれば、0 ≦ x ∧ x ≦ 1 の意味は0（偽）または1（真）として決まる。

しかし、xの値が何であるか不明で、やっぱりよく分かりません。そこでコンテキストを明示して、

  • x∈R| 0 ≦ x ∧ x ≦ 1

これなら、

  • xの値が1/2と決まれば、0 ≦ 1/2 ∧ 1/2 ≦ 1 の意味は1として決まる。
  • xの値が3と決まれば、0 ≦ 3 ∧ 3 ≦ 1 の意味は0として決まる。
  • xの値が0と決まれば、0 ≦ 0 ∧ 0 ≦ 1 の意味は1として決まる。
  • xの値が-1と決まれば、0 ≦ -1 ∧ -1 ≦ 1 の意味は0として決まる。
  • …

結果として、上記のコンテキスト付き論理式は、R→{0, 1} という写像〈関数〉を定義します。より一般には、集合Xから{0, 1}への写像 X→{0, 1} が決まります。

X→{0, 1} という写像達に対して、∧、∨、¬、⇒ という演算を定義しても、もちろんいいのですが、我々にとってより馴染みがあるのは集合演算なので、∧、∨、¬、⇒ （の数学的意味）を集合演算として定義します。写像でも集合でもどっちでもよい理由は：

  • X→{0, 1} という写像 と Xの部分集合のあいだには1：1の対応がある。
  • （すぐ上と同じことだが）写像の集合 Map(X, {0, 1}) と Xのベキ集合 Pow(X) は集合として同型であり、標準的な同型写像がある。
  • 標準的な同型写像は、f |→ {x∈X| f(x) = 1} という対応と、S |→ λx∈X.(if(x∈S) then 1 else 0 end) という対応（互いに逆）で与えられる。

※ λx∈X.(…) は、「… という式で定義される関数」の意味です。

そんな事情で、(x∈R| 0 ≦ x ∧ x ≦ 1) というコンテキスト付き論理式は、Rのベキ集合 Pow(R) の要素（＝Rの部分集合）により意味付けられ、論理記号 ∧、∨、¬、⇒ も、Pow(R)において定義された集合演算（∪, ∩ など）として解釈されます。コンテキスト（の領域）が別な集合Xなら、Pow(X)の集合演算を使います。

以上の内容をまとめると：

  • 〚x∈X| A〛 = {x∈X| A}
  • 〚x∈X| A∧B〛 = 〚x∈X| A〛∩〚x∈X| B〛
  • 〚x∈X| A∨B〛 = 〚x∈X| A〛∪〚x∈X| B〛
  • 〚x∈X| ¬A〛 = 〚x∈X| A〛c （右肩のcは補集合をとることを表す）
  • 〚x∈X| A⇒B〛 = 〚x∈X| A〛c ∪〚x∈X| B〛

これでやっと、論理記号 ∧、∨、¬、⇒ を数学的に議論できる準備ができました。

「記号'∧'は『かつ』の意味です」という説明は、もちろん必要だし、最初はこう言って導入すべきです。が、記号'∧'の数学的意味については何ひとつ規定してないので、論理の数学的モデルの構築には、これっぽっちも役に立ちません -- 形式的には何も言ってなかったのです。

限量子を含まない閉論理式

0を空集合として、1 = {0}, Pow(1) = {0, 1} とします。0は偽を意味し、Fとも書きます。1は真を意味し、Tとも書きます。混乱の恐れがないなら、0を0, 1を1とも書きます。ほとんどの場合、0と0とF、1と1とTを区別しません -- こういうイイカゲンさ、ちゃらんぽらんさは、論理では当たり前のことなので、神経質になるのはやめましょう。

スコット・ブラケット（の値）を求めるときに使う公式（定義）を、コンテキストを省略して繰り返すと：

  • 〚A∧B〛 = 〚A〛∩〚B〛
  • 〚A∨B〛 = 〚A〛∪〚B〛
  • 〚¬A〛 = 〚A〛c （右肩のcは補集合をとることを表す）
  • 〚A⇒B〛 = 〚A〛c ∪〚B〛

記号 '⇒' を集合演算の意味でもオーバーロードして使うことにします。

  • （なんかの親集合の）部分集合 V, W に対して、 V⇒W := Vc ∪ W

この書き方を使うと：

  • 〚A⇒B〛 =〚A〛⇒〚B〛

左側の'⇒'は論理結合子、右側の'⇒'は集合演算です。こういうオーバーロード（記号の流用、多義的使用）は良くない（実害がある）習慣ですが、記号が足りないので現実には多用されます。ちゃらんぽらんで、悪いこともやってしまう、のが論理のやり口です。

では解答。一部（7番以降）は計算過程も示します。以下の論理式の場合、（記述が省略されているが）変数の変域を示すコンテキストは空。コンテキスト領域は1。したがって、スコット・ブラケットの値は0または1。念の為ここでは、0, 1 ではなくて 0, 1 を使います。

  1. 〚1 + 2 = 3〛 = 1
  2. 〚1 + 2 < 3〛 = 0
  3. 〚12 = 22〛 = 0
  4. 〚3 ≦ 5 ∧ 3 ≦ 3〛 = 1
  5. 〚1 + 2 < 3 ⇒ 12 = 22〛 = 1
  6. 〚1 + 2 < 3 ∨ 12 = 22 ∨ 3 ≦ 3〛 = 1
  7. 〚(3 ≦ 5 ∧ 3 ≦ 3) ⇒ 1 + 2 < 3〛 = 0
  8. 〚(3 ≦ 5 ∨ 3 ≦ 3) ⇒ ¬(1 + 2 < 3)〛 = 1
  9. 〚¬(1 + 2 < 3) ⇒ (1 + 2 = 2)〛 = 0
  10. 〚1 + 2 = 3 ⇒ (1 + 2 < 3 ⇒ 12 = 22)〛 = 1

計算過程：



7.

   〚(3 ≦ 5 ∧ 3 ≦ 3) ⇒ 1 + 2 < 3〛

 = 〚3 ≦ 5 ∧ 3 ≦ 3〛⇒〚1 + 2 < 3〛

 = (〚3 ≦ 5〛∩〚3 ≦ 3〛)⇒〚1 + 2 < 3〛

 = (1∩1)⇒0

 = 1⇒0

 = 1c∪0

 = 0∪0

 = 0
8.

   〚(3 ≦ 5 ∨ 3 ≦ 3) ⇒ ¬(1 + 2 < 3)〛

 = 〚3 ≦ 5 ∨ 3 ≦ 3〛⇒〚¬(1 + 2 < 3)〛

 = (〚3 ≦ 5〛∪〚3 ≦ 3〛)⇒〚1 + 2 < 3〛c

 = (1∪1)⇒0c

 = 1⇒1

 = 1c∪1

 = 0∪1

 = 1
9.

   〚¬(1 + 2 < 3) ⇒ (1 + 2 = 2)〛

 = 〚1 + 2 < 3〛c⇒〚1 + 2 = 2〛

 = 0c⇒0

 = 1⇒0

 = 1c∪0

 = 0∪0

 = 0
10.

   〚1 + 2 = 3 ⇒ (1 + 2 < 3 ⇒ 12 = 22)〛

 = 〚1 + 2 = 3 ⇒ (1 + 2 < 3 ⇒ 12 = 22)〛

 = 〚1 + 2 = 3〛⇒〚1 + 2 < 3 ⇒ 12 = 22〛

 = 〚1 + 2 = 3〛⇒(〚1 + 2 < 3〛⇒〚12 = 22〛)

 = 1⇒(0⇒0)

 = 1⇒1

 = 1

空なコンテキストの領域が1であることは、あまり深く考え込まないで、便宜的な約束だと思って受け入れましょう。この約束を受け入れれば、二値真偽値 {T, F} と、命題の真理集合（命題の外延、解集合、集合の内包的記法、デカルト解析幾何の意味での図形などと同じ）を、スコット・ブラケットにより統一的に扱うことができます。「便宜的」と言いましたが、この約束は実際は極めて整合的です。

限量子を含む閉論理式

解答を先に：

  1. 〚∀n∈N.(n ≧ 0)〛 = 1
  2. 〚∃n∈N.(n < 0)〛 = 0
  3. 〚∀n∈N.∃m∈N.(m ≧ n)〛 = 1
  4. 〚∀n∈N.∃m∈N.(m < n)〛 = 0
  5. 〚∀x∈R.∃y∈R.(y2 = x)〛 = 0 [追記 date="2018-12-07"]←間違っていた、修正しました。[/追記]
  6. 〚∀x∈R.∃y∈R.(x ≧ 0 ⇒ y2 = x)〛 = 1
  7. 〚∃y∈R.∀x∈R.(x ≧ 0 ⇒ y2 = x)〛 = 0
  8. 〚∀x∈R.∀y∈R.∃n∈N.((x ≧ 0 ∧ y > 0) ⇒ yn ≧ x)〛 = 1

これらの真偽値を理解するひとつの方法は、「命題と、そのコンテキスト／真理集合 (A8P6)」の追記に書いた「感情表現をタップリ混じえた日本語」に沿って考える方法です。

自然言語に基づく直感的理解も重要で、決して悪いものではありません。ですが、スコット・ブラケットは素朴集合論に基づいて定義されている関数なので、素朴集合論の観点からも理解しておいたほうがいいでしょう（次節以降／次回以降）。

反例と正例

反例という言葉はよく知られています。反例と対になる言葉はなんでしょう？ それは「例」です。しかし、「例」では、一般的な事例と区別が付かないので、テクニカルタームとして「正例」と呼ぶことにします。

コンテキスト付き論理式 (x∈X| A) があったとき、

  • 集合Xの特定の要素aが正例だとは、論理式Aの変数xにaを代入した後のスコット・ブラケット（の値） 〚A'〛 が1になること。A'は、Aの変数xにaを代入した後の閉論理式。
  • 集合Xの特定の要素aが反例だとは、論理式Aの変数xにaを代入した後のスコット・ブラケット（の値） 〚A'〛 が0になること。A'は、Aの変数xにaを代入した後の閉論理式。

正例集合は真理集合と同じであり、反例集合は真理集合の補集合です。また言葉が増えてしまいましたが、同じ意味です。

我々は、変数を持つ命題（＝コンテキスト付き命題）を、その正例や反例を通して理解します。つまり、命題の真理集合や、真理集合の補集合を使って考えるのです。“真理集合＝スコット・ブラケット”による“意味のモデリング”が、人間の思考とかけ離れているわけでもないでしょ。

限量子の数学的（素朴集合論的）解釈

限量された〈限量子付きの | quantified〉論理式とコンテキスト付き論理式は、相互に関連していて、切り離して議論は出来ません。

限量された論理式 ∀x∈X.P、∃x∈X.P のスコット・ブラケット（の値）を求めるには、限量子を外してコンテキストに換えた (x∈X| P) のスコット・ブラケットを先に求める必要があります。

  1. 〚∀x∈X.P〛 = 1 (⇔) 〚x∈X| P〛 = X
  2. 〚∀x∈X.P〛 = 0 (⇔) 〚x∈X| P〛 ≠ X
  3. 〚∃x∈X.P〛 = 1 (⇔) 〚x∈X| P〛 ≠ 0
  4. 〚∃x∈X.P〛 = 0 (⇔) 〚x∈X| P〛 = 0

ここで、記号 '(⇔)' は、メタな（つまり、普通の、形式化されてない）論理的同値の記号です。テクニカルタームとしての「正しい」と、テクニカルタームとしての「正例」を使って述べれば：

  1. ∀x∈X.P が正しい (⇔) (x∈X| P) が正しい
  2. ∀x∈X.P が正しくない (⇔) (x∈X| P) が正しくない
  3. ∃x∈X.P が正しい (⇔) (x∈X| P) が正例を持つ
  4. ∃x∈X.P が正しくない (⇔) (x∈X| P)が正例を持たない

テクニカルタームとしての「反例」「正例」を使えば：

  1. ∀x∈X.P が正しい (⇔) (x∈X| P) が反例を持たない
  2. ∀x∈X.P が正しくない (⇔) (x∈X| P) が反例を持つ
  3. ∃x∈X.P が正しい (⇔) (x∈X| P) が正例を持つ
  4. ∃x∈X.P が正しくない (⇔) (x∈X| P)が正例を持たない

限量された〈限量子付き〉の命題は、限量子を取り外したコンテキスト付き命題の、正しさの程度（＝スコット・ブラケットの値）を要約した表現と捉えられます。

補集合の性質、ついでに「メタ」について

正例の集合と反例の集合は、互いに補集合になっています。補集合は次の性質を持ちます。V, W をXの部分集合として：

  • V∪Vc = X
  • (Vc)c = V
  • (V∩W)c = Vc∪Vc
  • (V∪W)c = Vc∩Vc

これら補集合の性質は、排中律、二重否定、ド・モルガンの法則という論理法則の集合バージョンです。我々は、これらの論理法則とその集合バージョンを疑ったりしないし、平気で使います。他の数学の分野でも平気で使っているのだから、当然の話です。

そのことと、形式化された演繹システム内で、排中律、二重否定、ド・モルガンの法則などが成立するかどうかはまったくの別問題です。演繹システムは、我々が新しく作り出す（ソフトウェアプログラムと同様な）人工的構築物なので、下手に作れば期待される性質を持ちません。バグだらけのシステムだってありえます。

次の二文は、まったく別なことを述べています。メタ論理（我々が通常使っている形式化されてない論理）記号は丸括弧で包む規則で書きます。

  • メタ論理（我々が通常使っている形式化されてない論理）において、ド・モルガンの法則 (¬)(A(∧)B) (⇔) (¬)A(∨)(¬)B が成立しているし、既に平気で使っている。
  • 我々が構築した演繹システムSは、形式化されたド・モルガンの法則 "¬(A∧B) ⇔ ¬A∨¬B" を（なんらかのメカニズムにより）正しいと判断できる。

二番目の主張は、メタ命題（演繹システムSに関する普通の命題）であり、メタ論理（普通の論理）を使ってメタ証明（普通に証明）すべき事項です。

限量子を含む閉論理式の解説 (途中まで)

1. ∀n∈N.(n ≧ 0)

今まで述べたことから、次のような（メタな）同値性があります。

  • ∀n∈N.(n ≧ 0) が正しい (⇔) (n∈N| n ≧ 0) が反例を持たない
  • ∀n∈N.(n ≧ 0) が正しい (⇔) (n∈N| n ≧ 0) の反例集合が空
  • ∀n∈N.(n ≧ 0) が正しい (⇔) (n∈N| n ≧ 0) の正例集合がN
  • 〚∀n∈N.(n ≧ 0)〛 = 1 (⇔) 〚n∈N| n ≧ 0〛 = N

あるいは、

  • ∀n∈N.(n ≧ 0) が正しくない (⇔) (n∈N| n ≧ 0) が反例を持つ
  • ∀n∈N.(n ≧ 0) が正しくない (⇔) (n∈N| n ≧ 0) の反例集合が空ではない
  • ∀n∈N.(n ≧ 0) が正しくない (⇔) (n∈N| n ≧ 0) の正例集合がNではない
  • 〚∀n∈N.(n ≧ 0)〛 = 0 (⇔) 〚n∈N| n ≧ 0〛 ≠ N

これら同値な判定基準のどれを使ってもいいですが、例えば、「n ≧ 0 がN内で反例を持たない」ことから、〚∀n∈N.(n ≧ 0)〛 = 1 です。

2. ∃n∈N.(n < 0)
  • ∃n∈N.(n < 0) が正しい (⇔) (n∈N| n < 0) が正例を持つ
  • ∃n∈N.(n < 0) が正しい (⇔) (n∈N| n < 0) の正例集合が空ではない
  • ∃n∈N.(n < 0) が正しい (⇔) (n∈N| n < 0) の反例集合がNではない
  • 〚∃n∈N.(n < 0)〛 = 1 (⇔) 〚n∈N| n < 0〛 ≠ 0

あるいは、

  • ∃n∈N.(n < 0) が正しくない (⇔) (n∈N| n < 0) が正例を持たない
  • ∃n∈N.(n < 0) が正しくない (⇔) (n∈N| n < 0) の正例集合が空
  • ∃n∈N.(n < 0) が正しくない (⇔) (n∈N| n < 0) の反例集合がN
  • 〚∃n∈N.(n < 0)〛 = 0 (⇔) 〚n∈N| n < 0〛 = 0

前問と同じく、どれで判断しても 〚∃n∈N.(n < 0)〛 = 0 。


中途半端な場所ですが、続きは別な記事にします。続き → 問題集6の目的と解答と追加説明 その2 (A14R6-2) - 檜山正幸のキマイラ飼育記 メモ編