破棄されたブログ

このブログは破棄されました。

Propositions

まだ途中.

Mathematics for Computer Science LEC #1

命題

定義

命題とは, 真もしくは偽の(平叙)文である.

命題の例

  • 真の命題 2 + 3 = 5
  • 偽の命題 1 + 1 = 3

  • 命題にはあまり制限がないように見える.

  • 次のような文は命題ではない.
    • なぜあなたはロメオなの?
    • アレをくれ.
  • 命題が真であるか偽であるかを決めるのはいつも簡単とは限らない.
    • 命題が意味することがなにかさえも簡単とは限らない.
  • 日常会話には確かでない文章がかなり含まれている
    • 次の例文が正確に意味するものは何か.
    • 例文
      • あなたは多分ケーキを持ってる. あなたは多分アイスクリームを持っている
        • ケーキとアイスクリームの両方を持てるのか?
        • 片方のみのデザートを選ばなければならないのか?
      • 豚が飛べれば, 君にもチェビシェフの不等式が理解できるよ.
        • この命題が真なら, チェビシェフの不等式は理解できない?
      • ぼくらが考えたどんな問題でも解けるのなら, この講義で A がもらえるね.
        • 少しでも解けない問題があったら A がもらえないの?
      • アメリカ人はみんな夢を持ってる
        • アメリカ人すべてが同じ夢を持っているの?
        • それともみんなばらばらの夢を持っているの?
  • 考えを正確に明確に述べるには, 言語がもつ曖昧さが問題になる.
    • 数学やプログラミングなどで.
  • 文の正確な意味がわからなければ, 正確な議論をしたいとは思えない.
  • 論理的関係について話すための特別で小さな言語を数学者は発明した.
    • この言語のほとんどは日常会話で使われる単語やフレーズを使っている.
      • or, implies, or all など
    • 但し, 数学においては通常の辞書よりも厳密に意味が定義されている.
  • コンピュータサイエンスにおいて, 最も重要な未解決問題がある.
    • 解決策が世界を変えてしまうような問題.
      • a problem whose solution could change the world.

複合命題

  • 英語では命題の変更・結合・関連付けができる
    • not, and, or , implies, if-then など
  • 複合命題の例
    • もし、すべての人間が死を免れず、かつすべてのギリシャ人が人間であれば、すべてのギリシャ人は死を免れない.
      • If all humans are mortal and all Greeks are human, then all Greeks are mortal.
    • 命題の内容について考えたくない.
      • 命題の代わりに, P とか Q とかの変数を代わりに使う.
        • この変数は, T(真)か F(偽)しか値を取れない.
        • ブール変数と呼ぶ.

真理値表

  • 言葉の定義を正確に行うことができる
  • 一般に, 真理値表は, 設定された各変数が取りうる値について, 命題が真であるか偽であるかを明示する.

NOT

P NOT(P)
T F
F T
  • P が真なら NOT(P) は偽であることを示す.
  • P が偽なら NOT(P) は真であることを示す.

AND

P Q P AND Q
T T T
T F F
F T F
F F F
  • PQ がともに真の場合のみ, 真となる.

OR

P Q P OR Q
T T T
T F T
F T T
F F F
  • PQ がともに真の場合でも, 真となる.
  • 日常で使われる or が意味するところとは異なる場合がある.
  • 数学では標準的な定義.

XOR

P Q P XOR Q
T T F
T F T
F T T
F F F
  • どちらか片方しか真にしたくない場合

IMPLIES

P Q P IMPLIES Q
T T T (tt)
T F F (tf)
F T T (ft)
F F T (ff)
  • 仮定-結論という文において, 仮定部分が偽もしくは結論部分が真ならば, IMPLIES は真となる.

例1

もしリーマン予想が正しければ, x^2 >= 0 は, すべての実数 x に対して成り立つ if the Riemann Hypothesis is true, then x^2 >= 0 for every real number x.

  • この例文は, P IMPLIES Q として表すことができる.
    • 仮定 P
    • 結論 Q
      • x^2 >= 0 は, すべての実数 x に対して成り立つ
  • 結論 Q は確かに正しい.
    • (tt) と (ft).
  • リーマン予想は有名な数学の未解決問題.

例2

豚が飛べれば, 君にもチェビシェフの不等式が理解できるよ. If pigs can fly, then you can understand the Chebyshev bound.

  • チェビシェフの不等式を理解しているかを気にする必要はない.
  • 豚が飛べないということは正しい
    • (ft) と (ff)

例3

もし月が白く輝くのなら, 月は白いチェダーチーズで作られている If the moon shines white, then the monn made of white cheddar.

  • 月は確かに白く輝くが, チェダーチーズで作られていない.
    • (tf)

IFF

P Q P IFF Q
T T T
T F F
F T F
F F T
  • P if and only if Q
    • if-and-only-if
    • 日常会話にない形
    • PQ が論理的に等しい.

x^2 - 4 >= 0 iff |x| >= 2
  • 次のどちらの場合においても, 命題全体としては真となる.
    • ある値 x に対して, 両方の不等式が真になる.
    • ある値 x に対して, 両方の不等式が真にならない.

記法

  • NOT(P)
    • P
  • P AND Q
    • PQ
  • P OR Q
    • PQ
  • P IMPLIES Q
    • PQ
  • if P then Q
    • PQ
  • P IFF Q
    • PQ

IMPLIES の論理同値

  • 次の文は同値か

    • もし, お腹が減っていれば, 機嫌が悪い.
    • もし, 機嫌が悪くなければ, お腹が減っていない.
  • P: お腹が減っている

  • Q: 機嫌が悪い
P Q P IMPLIES Q NOT(P) NOT(Q) NOT(P) IMPLIES NOT(Q)
T T T F F T
T F F F T F
F T T T F T
F F T T T T
  • P IMPLIES QNOT(P) IMPLIES NOT(Q) は同値.
    • 対偶命題
P Q P IMPLIES Q Q IMPLIES P
T T T T
T F F T
F T T F
F F T T
  • P IMPLIES QQ IMPLIES P は同値でない.
    • 逆, 転換命題
P Q P IMPLIES Q Q IMPLIES P (P IMPLIES Q) AND (Q IMPLIES P) P IFF Q
T T T T T T
T F F T F F
F T T F F F
F F T T T T
  • (P IMPLIES Q) AND (Q IMPLIES P)P IFF Q は同値.

プログラミングにおける論理命題

if (x > 0 || (x <= 0 && y > 100))if (x > 0 || y > 100) は同値なコード

  • A: x > 0
    • NOT(A): x <= 0
  • B: y > 100

    A OR (NOT(A) AND B)

A B A OR (NOT(A) AND B) A OR B
T T T T
T F T T
F T T T
F F F F

論理式の最適化のメリット

  • プログラミング
    • コードの高速化
  • チップ設計
    • チップを搭載するデバイスの小型化
    • 省電力化
    • 低価格化

命題と量

  • 真理値表で真偽を確認できるケースは稀.
    • 考えなければならない組み合わせが膨大もしくは無限大個の場合がある.

すべての正の整数 n について, n^2 + n + 41 の値は素数である.

  • 実際に数値を代入して確認するのもひとつの手.
    • n <= 39 までは素数となることがわかる.
    • n = 40 のとき, 40^2 + 40 + 41 = 41 * 41 となる.
      • 与えられた命題は偽である.
    • 実際に代入することで, 偽であることが判明する場合は少なくない.
    • ただし, 有限個の要素を用いて, 無限個の要素についての主張を確認することはできない.

先ほどの命題の別の書き方

{\forall}n{\in}\mathbb{N}. p(n) is prime.

用語

  • proposition
    • 命題
  • true
  • false
  • statement
    • 平叙文
  • compound proposition
    • 複合命題
  • boolean variable
    • ブール変数
    • 単に bool とも呼ぶ
  • truth talbe
    • 真理値表
  • exclusive-or
    • XOR
    • 排他論理和
  • implies
    • 論理包括
  • hypothesis
    • 仮定
  • IFF
    • 同値
  • contrapositive
    • 対偶
  • converse

単語・熟語・イディオム

  • sound link
    • らしい
  • riddled [with ...]
    • ... で穴だらけ
    • ... (望ましくないもの)でいっぱい
  • ambiguity
    • あいまいさ
  • come up with
    • 句動詞
    • 思いついた
  • precisely
    • 正確に
  • precise
    • 正確な
  • incomprehensible
    • 理解できない
  • imply
    • 含む
  • tolerable
    • かなりの
  • inherent in
    • 固有の
  • exact
    • 正確な
  • make an argument
    • 議論する
  • devise
    • 考案する
  • endow with ...
    • ... に与える
  • surprisingly
    • 驚いたことに
  • in the midst of ...
    • の中で
  • open problem
    • 未解決問題
  • frequently
    • 頻繁に
  • intended
    • 意図される
  • intuitive
    • 直感的な
  • either way
    • どちらにしても
  • inequalities
    • 不等式
  • contrived
    • 不自然な
  • suspect
    • 気づく

参考資料

広告を非表示にする