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

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

命題と、そのコンテキスト／真理集合 (A8P6)

RSS練習問題

※この記事は「記事8 問題集6」

2018-12-02: 冒頭に、スコット・ブラケット＝真理集合の役割の説明を追記。

与えられた論理式〈形式化された命題〉に対して、そのスコット・ブラケットを実際に計算する練習。スコット・ブラケット（の値）と真理集合は同じもの。予備知識として、中学・高校で習った、方程式・不等式と図形の関係が必要になる。

「もう分かった。同じタイプの問題をこれ以上やり続けるのは辛い。」と感じたらやめてよい。逆に、「もっと練習したい。」と感じたら、同種の問題を自作するのは容易だから、作って解く。

内容：

  1. 正しさの程度を測ること (2018-12-02に追加)
  2. 限量子を含まない閉論理式
  3. 限量子を含む閉論理式
  4. コンテキスト付き論理式
  5. コンテキストの水増し
  6. 様々な論理式を作ってみる
  7. 限量子も使ってみる

正しさの程度を測ること

[追記 date="2018-12-02"]この節はすべて追記[/追記]

「たかし君よりゆかりさんのほうが背が高いんじゃないの」
「いや、ゆかりさんは女の子だから、大きく見えるだけだよ」
「そうじゃなくて、ゆかりさん、ほんとに大きいよ」
「俺はたかし君が大きいと思うな、感じとして」

こんな話をグダグダしていても埒が明かない！

人の量的属性である身長について語っているのだから、適切な測定装置 -- つまり身長計で測ればいい。測った結果が、

  • たかし 161.3cm
  • ゆかり 162.1cm

であれば、「ゆかりさんのほうが背が高い」が正しい。身長計を使えば、「クラスのなかで誰が一番背が高いか？」も疑義なく明白に決定できるだろう。

数理的手法、あるいは自然科学一般の方法論は、対象物の属性を適切な測定装置で測ることを基本とする。ときには、複数の測定値を組み合わせた計算値として結果が得られることもある。例えば、肥満度を表すBMI（Body Mass Index）は、身長と体重から計算される量的属性である。

測定値（算出された値も含む）の集合として、自然数N（個数）や実数R（連続量）だけではなくて、集合Xのベキ集合Pow(X)を使うこともできる。命題の「正しさ」の測定値は実際Pow(X)に値をとる。

「(x∈R| x2 > 0) より (x∈R| ¬(x = 0)) のほうが正しいんじゃないの」
「いや、(x∈R| ¬(x = 0)) は否定が入ってるから、より正しいように見えるだけだよ」
「そうじゃなくて、(x∈R| ¬(x = 0))、ほんとに正しいよ」
「俺は (x∈R| x2 > 0) がより正しいと思うな、感じとして」

こんな話をグダグダしていても埒が明かない！ サッサと正しさの程度を適切な測定装置で測って比べなさい。その測定装置がスコット・ブラケットというものだ。対象物（今は命題）に対して、雰囲気的に語ったり、思弁的に論じたり、私的感慨を縷縷述べあり、そんなことをしても何も始まらない。グダグダ言ってないでチャンと測れ。

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

次の等式／不等式の組み合わせは、閉論理式（自由変数をまったく含まない論理式）である。その真偽を常識的に解釈して、スコット・ブラケットを使って記述せよ。

例： 〚1 + 1 = 2〛 = 1, 〚1 > 3〛 = 0. 〚1 > 3 ∨ 1 = 1〛 = 1

[追記 date="2018-12-02"]もう少し複雑な例題をやっておく。

  • 1 + 1 = 2 ⇒ ((2 ≦ 1 ∧ 2 ≦ 3) ⇒ 1 + 2 > 5) のスコット・ブラケットを計算せよ。

混乱を避けるために、真偽値（1 = {0} の部分集合）としての 0, 1 は 0, 1 と書く。自分で計算するときは、0, 1 でも混乱はないだろう。記号 '⇒' を集合演算の意味でもオーバーロードして使う。

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

この書き方を使うと：

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

左側の'⇒'は論理結合子、右側の'⇒'は集合演算である。

例えば次のように計算するが、この計算は、Pow(1) = {0, 1} における部分集合の計算である。



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

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

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

 =  0 ∪ 〚(2 ≦ 1 ∧ 2 ≦ 3) ⇒ 1 + 2 > 5 〛

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

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

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

 =  (0∩1) ⇒ 〚1 + 2 > 5〛

 =  0 ⇒ 〚1 + 2 > 5〛

 =  0c ∪ 〚1 + 2 > 5〛

 =  1 ∪ 〚1 + 2 > 5〛

 =  1

[/追記]

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

※注意： 閉論理式は、空なコンテキストを持つコンテキスト付き論理式とみなせる。例えば、1 + 2 = 3 は (| 1 + 2 = 3) である。

限量子を含む閉論理式

次の論理式は変数を含むが、変数が限量子で束縛されているので閉論理式である。その真偽を常識的に解釈して、スコット・ブラケットを使って記述せよ。

例： 〚∀x∈R.( x2 ≧ 0 )〛 = 1, 〚∃x∈R.( x2 < 0 )〛 = 0

  1. ∀n∈N.(n ≧ 0)
  2. ∃n∈N.(n < 0)
  3. ∀n∈N.∃m∈N.(m ≧ n)
  4. ∀n∈N.∃m∈N.(m < n)
  5. ∀x∈R.∃y∈R.(y2 = x)
  6. ∀x∈R.∃y∈R.(x ≧ 0 ⇒ y2 = x)
  7. ∃y∈R.∀x∈R.(x ≧ 0 ⇒ y2 = x)
  8. ∀x∈R.∀y∈R.∃n∈N.((x ≧ 0 ∧ y > 0) ⇒ yn ≧ x)

※注意：限量子を含む閉論理式も、空なコンテキストを持つコンテキスト付き論理式とみなせる。例えば、∀n∈N.(n ≧ 0) は (| ∀n∈N.(n ≧ 0)) である。

[追記 date="2018-12-02"]感情表現をタップリ混じえた日本語で表現しておく。

  1. ∀n∈N.(n ≧ 0) ： 自然数nをどんなに勝手に選んだところで、n ≧ 0 である。
  2. ∃n∈N.(n < 0) ： n < 0 である自然数nが、頑張って探せば必ず見つかる。
  3. ∀n∈N.∃m∈N.(m ≧ n) ： 自然数nをどんなに勝手に選んだところで、m ≧ n である自然数mが、頑張って探せば必ず見つかる。
  4. ∀n∈N.∃m∈N.(m < n) ： 自然数nをどんなに勝手に選んだところで、 m < n である自然数mが、頑張って探せば必ず見つかる。
  5. ∀x∈R.∃y∈R.(y2 = x) ： 実数xをどんなに勝手に選んだところで、 y2 = x である実数yが、頑張って探せば必ず見つかる。
  6. ∀x∈R.∃y∈R.(x ≧ 0 ⇒ y2 = x) ： 実数xをどんなに勝手に選んだところで、 「x ≧ 0 ならば y2 = x」である実数yが、頑張って探せば必ず見つかる。
  7. ∃y∈R.∀x∈R.(x ≧ 0 ⇒ y2 = x) ： どんなに勝手に選んだ実数xに対しても「x ≧ 0 ならば y2 = x」である実数yが、頑張って探せば必ず見つかる。
  8. ∀x∈R.∀y∈R.∃n∈N.((x ≧ 0 ∧ y > 0) ⇒ yn ≧ x) ： 実数xをどんなに勝手に選んだところで、実数yをどんなに勝手に選んだところで、「(x ≧ 0 かつ y > 0) ならば、yn ≧ x」となる自然数nが、頑張って探せば必ず見つかる。

[/追記]

コンテキスト付き論理式

※注意： 自由変数を含む論理式にコンテキストがないと、解釈不可能・意味不明なので、単に「論理式」と言った場合でも、たいていはコンテキスト付き論理式を意味する。

Rは直線、R2 = R×R は平面とみなして、次のコンテキスト付き論理式のスコット・ブラケットを図示せよ。

例： コンテキスト付き論理式 (x∈R| x + 1 ≦ 3 ∧ -1 ≦ x) のスコット・ブラケット 〚(x∈R| x + 1 ≦ 3 ∧ -1 ≦ x)〛 = 〚x∈R| x + 1 ≦ 3 ∧ -1 ≦ x〛 は、集合 {x∈R| x + 1 ≦ 3 ∧ -1 ≦ x} のことだから、図としては、直線内の区間 [-1, 2] 。

この練習問題は、内容的には数直線／座標平面内の図形を描くものだが、「コンテキスト付き論理式の真理集合を求める」という意図と解釈を持つ。

  1. (x∈R| x < 0 ∨ 1 < x)
  2. (x∈R| 0 < x ∧ x < 1)
  3. (x∈R| 0 < x ∧ 1 < x)
  4. (x∈R| x < 0 ⇒ x2 = 1)
  5. (x∈R| x2 = 1 ⇒ x < 0)
  6. (x∈R| x2 = 1 ⇒ x = 0)
  7. (x∈R| x2 = 1 ⇒ x = 1)
  8. (x∈R| x2 = 1 ⇒ (x = 1 ∨ x = -1))
  9. (x∈R| (x2 = 1 ∧ x ≧ 0) ⇒ x = 1)
  10. (x∈R| (x2 = 1 ∧ x ≧ 0) ⇒ (x = 1 ∨ x = -1))
  11. (x, y∈R| x2 + y2 = 1)
  12. (x, y∈R| x2 + y2 = 4 ∧ x + y ≧0)
  13. (x, y∈R| x2 + y2 = 4 ∧ x + y ≧ -1)
  14. (x, y∈R| x2 + y2 = 1 ∨ x + y = 0)
  15. (x, y∈R| x2 + y2 = 1 ⇒ x = 1)
  16. (x, y∈R| x = 1 ⇒ x2 + y2 = 1)
  17. (x, y∈R| (x = 1 ∧ y = 0) ⇒ x2 + y2 = 1)
  18. (x, y∈R| x2 + y2 = 1 ⇒ x + y ≦ 2)
  19. (x, y∈R| x2 + y2 = 1 ⇒ x + y ≦ 1)
  20. (x, y∈R| x2 + y2 ≦ 1 ⇒ x + y ≦ 2)
  21. (x, y∈R| x2 + y2 ≦ 1 ⇒ x + y ≦ 1)
  22. (x, y∈R| (x2 + y2 ≦ 1 ∧ x + y ≦ 0) ⇒ x + y ≦ 1)

コンテキストの水増し

以下のコンテキスト付き論理式は、前問の論理式のコンテキストを水増し〈thinning〉したものである。そのスコット・ブラケット〈真理集合〉を図示せよ。

  1. (x, y∈R| x < 0 ∨ 1 < x)
  2. (x, y∈R| 0 < x ∧ x < 1)
  3. (x, y∈R| 0 < x ∧ 1 < x)
  4. (x, y∈R| x < 0 ⇒ x2 = 1)
  5. (x, y∈R| x2 = 1 ⇒ x < 0)
  6. (x, y∈R| x2 = 1 ⇒ x = 0)
  7. (x, y∈R| x2 = 1 ⇒ x = 1)
  8. (x, y∈R| x2 = 1 ⇒ (x = 1 ∨ x = -1))
  9. (x, y∈R| (x2 = 1 ∧ x ≧ 0) ⇒ x = 1)
  10. (x, y∈R| (x2 = 1 ∧ x ≧ 0) ⇒ (x = 1 ∨ x = -1))

以下のコンテキスト付き論理式は、最初の問題と二番目の問題の論理式のコンテキストを水増ししたものである。そのスコット・ブラケット〈真理集合〉を図示せよ。自由変数と束縛変数の名前がかぶっているが、理論的には問題にならない（紛らわしいので、現実的には避けたほうがよい）。

  1. (x, y∈R| 1 + 2 = 3)
  2. (x, y∈R| 1 + 2 < 3)
  3. (x, y∈R| 12 = 22)
  4. (x, y∈R| 3 ≦ 5 ∧ 3 ≦ 3)
  5. (x, y∈R| 1 + 2 < 3 ⇒ 12 = 22)
  6. (x, y∈R| 1 + 2 < 3 ∨ 12 = 22 ∨ 3 ≦ 3)
  7. (x, y∈R| (3 ≦ 5 ∧ 3 ≦ 3) ⇒ 1 + 2 < 3)
  8. (x, y∈R| (3 ≦ 5 ∨ 3 ≦ 3) ⇒ ¬(1 + 2 < 3))
  9. (x, y∈R| ¬(1 + 2 < 3) ⇒ (1 + 2 = 2))
  10. (x, y∈R| 1 + 2 = 3 ⇒ (1 + 2 < 3 ⇒ 12 = 22))
  11. (x, y∈R| ∀n∈N.(n ≧ 0))
  12. (x, y∈R| ∃n∈N.(n < 0))
  13. (x, y∈R| ∀n∈N.∃m∈N.(m ≧ n))
  14. (x, y∈R| ∀n∈N.∃m∈N.(m < n))
  15. (x, y∈R| ∀x∈R.∃y∈R.(y2 = x))
  16. (x, y∈R| ∀x∈R.∃y∈R.(x ≧ 0 ⇒ y2 = x))
  17. (x, y∈R| ∃y∈R.∀x∈R.(x ≧ 0 ⇒ y2 = x))
  18. (x, y∈R| ∀x∈R.∀y∈R.∃n∈N.((x ≧ 0 ∧ y > 0) ⇒ yn ≧ x))

様々な論理式を作ってみる

コンテキストの水増しにより、今まで登場した40個の論理式のコンテキスト領域は、すべてR2（平面）であるとしてよい。

  1. (x, y∈R| 1 + 2 = 3)
  2. (x, y∈R| 1 + 2 < 3)
  3. (x, y∈R| 12 = 22)
  4. (x, y∈R| 3 ≦ 5 ∧ 3 ≦ 3)
  5. (x, y∈R| 1 + 2 < 3 ⇒ 12 = 22)
  6. (x, y∈R| 1 + 2 < 3 ∨ 12 = 22 ∨ 3 ≦ 3)
  7. (x, y∈R| (3 ≦ 5 ∧ 3 ≦ 3) ⇒ 1 + 2 < 3)
  8. (x, y∈R| (3 ≦ 5 ∨ 3 ≦ 3) ⇒ ¬(1 + 2 < 3))
  9. (x, y∈R| ¬(1 + 2 < 3) ⇒ (1 + 2 = 2))
  10. (x, y∈R| 1 + 2 = 3 ⇒ (1 + 2 < 3 ⇒ 12 = 22))
  11. (x, y∈R| ∀n∈N.(n ≧ 0))
  12. (x, y∈R| ∃n∈N.(n < 0))
  13. (x, y∈R| ∀n∈N.∃m∈N.(m ≧ n))
  14. (x, y∈R| ∀n∈N.∃m∈N.(m < n))
  15. (x, y∈R| ∀x∈R.∃y∈R.(y2 = x))
  16. (x, y∈R| ∀x∈R.∃y∈R.(x ≧ 0 ⇒ y2 = x))
  17. (x, y∈R| ∃y∈R.∀x∈R.(x ≧ 0 ⇒ y2 = x))
  18. (x, y∈R| ∀x∈R.∀y∈R.∃n∈N.((x ≧ 0 ∧ y > 0) ⇒ yn ≧ x))
  19. (x, y∈R| x < 0 ∨ 1 < x)
  20. (x, y∈R| 0 < x ∧ x < 1)
  21. (x, y∈R| 0 < x ∧ 1 < x)
  22. (x, y∈R| x < 0 ⇒ x2 = 1)
  23. (x, y∈R| x2 = 1 ⇒ x < 0)
  24. (x, y∈R| x2 = 1 ⇒ x = 0)
  25. (x, y∈R| x2 = 1 ⇒ x = 1)
  26. (x, y∈R| x2 = 1 ⇒ (x = 1 ∨ x = -1))
  27. (x, y∈R| (x2 = 1 ∧ x ≧ 0) ⇒ x = 1)
  28. (x, y∈R| (x2 = 1 ∧ x ≧ 0) ⇒ (x = 1 ∨ x = -1))
  29. (x, y∈R| x2 + y2 = 1)
  30. (x, y∈R| x2 + y2 = 4 ∧ x + y ≧0)
  31. (x, y∈R| x2 + y2 = 4 ∧ x + y ≧ -1)
  32. (x, y∈R| x2 + y2 = 1 ∨ x + y = 0)
  33. (x, y∈R| x2 + y2 = 1 ⇒ x = 1)
  34. (x, y∈R| x = 1 ⇒ x2 + y2 = 1)
  35. (x, y∈R| (x = 1 ∧ y = 0) ⇒ x2 + y2 = 1)
  36. (x, y∈R| x2 + y2 = 1 ⇒ x + y ≦ 2)
  37. (x, y∈R| x2 + y2 = 1 ⇒ x + y ≦ 1)
  38. (x, y∈R| x2 + y2 ≦ 1 ⇒ x + y ≦ 2)
  39. (x, y∈R| x2 + y2 ≦ 1 ⇒ x + y ≦ 1)
  40. (x, y∈R| (x2 + y2 ≦ 1 ∧ x + y ≦ 0) ⇒ x + y ≦ 1)

同じコンテキスト領域を持つ論理式（単に「論理式」と言ってもコンテキスト付きと考える）は、論理演算をしてもよいので、上記40個の論理式をもとに自由に複合論理式を作れる。

次の手順で、好きなだけ練習をせよ（お腹いっぱいになったら、それ以上やらなくてもよい）。

  1. 1から40のなかから適当に（乱数的に）番号を選んで、Aに割り当てる。必要があれば、B, C にも番号を割り当てる。
  2. 下の総称論理式の命題パラメータ（論理式を代入できる変数）A, B, C に、選んで割り当てた番号の論理式を代入する。
  3. 出来た具体的な論理式に対して、そのスコット・ブラケットを求める。

総称論理式：

  1. ¬A
  2. A∧B
  3. A∨B
  4. A⇒B
  5. A⇒¬B
  6. (A∧B)⇒C
  7. (A∨B)⇒C
  8. A⇒B∧C
  9. A⇒B∨C
  10. (A∧B)∨C

総称論理式をもっと増やせば、練習問題を増やせる。

※注意： 全称と総称は似た言葉だが違う。全証命題は、全称記号∀が頭にある命題、総称命題は、論理式を代入してよい変数〈命題パラメータ〉を持つ命題。すぐ上の論理式は命題パラメータ A, B, C を持っているので総称命題だが、全称命題ではない。なお、「総称」は論理の言葉というより計算科学の言葉である。

限量子も使ってみる

前問と同様に、次の手順で、好きなだけ練習をせよ。

  1. 1から40のなかから適当に（乱数的に）番号を選んで、Aに割り当てる。
  2. 下の総称論理式の命題パラメータ（論理式を代入できる変数）Aに、選んだ番号の論理式を代入する。
  3. 出来た具体的な論理式は限量子を持ち、そのコンテキスト領域はRまたは1になる。そのスコット・ブラケットを求める（図示する）。コンテキスト領域が1のときは、図示はあまり意味がないので、値 0, 1 で答えればよい。
  1. ∀x.A
  2. ∀y.A
  3. ∀x.∀y.A
  4. ∃x.A
  5. ∃y.A
  6. ∃x.∃y.A
  7. ∀x.∃y.A
  8. ∀y.∃x.A

限量子（∀, ∃）と論理結合子（∧, ∨, ¬, ⇒）を組み合わせた総称論理式、例えば ∀x.(A∧B⇒C) や A⇒¬∃y.B などを準備すれば、練習問題を増やせる。興味と気力があれば、やってみよ。