読書メモ：プログラマの数学(2)

読書メモ

理論

なぜ理論が必要なのか

  • 自然言語のあいまいな部分をなくす。理論式で仕様書を表現しようとするとあいまいなところを見つけることができる。
  • シンプルで理解しやすい式に変換することができる

理論の言葉

命題・真偽

  • 命題：正しいか正しくないかを判断できる式
  • 真:命題が正しいとき「真である(true)」という
  • 偽：命題が正しくないとき「偽である(false)」という

もれ・だぶり

  • もれがないこと(網羅的であること）→　そのルールがどんな場合にも適応できる
  • ダブりがないこと(排他的であること) →　そのルールに矛盾がない
  • もれ・だぶりがないことは数直線を書くとわかりやすい　

withdom.jukendou.jp

  • 網羅的で排他的な分割をすると大きな問題を解きやすく分解することができるようになる。
  • 問題の分割はプログラムの中でいうとif文の部分。一つ一つは単純でも組み合わせると複雑になりバグが生まれやすい。if文を書くときは「網羅的で排他的である」のを意識する必要が有る。

命題を組み合わせて新しい命題を作る

  • 否定：「〜ではない」という命題を作る演算。
  • 二重否定は元に戻る
  • 論理積：「AかつB」という命題を作る演算
  • 理論和：「AまたはB」
  • 排他的論理和：「AまたはB(でも両方ではない)」
  • 等値：「AとBは等しい」
  • 含意：「AならばB」

論理包含 - Wikipedia

ド・モルガンの法則

ド・モルガンの法則 - Wikipedia

  • 理論式の相対性:理論式の中のtrueとfalse、Aと¬Aと、またはとかつを交換すると論理式全体を否定した式ができる。

カルノー図

複雑な理論式を整理するための図

カルノー図 - Wikipedia

  1. 命題の取り得るすべての真偽値の組み合わせに対応した図を書く
  2. チェックをつける
  3. 隣接するチェックマークを囲うグループをつくる（できるだけ大きく・重なっていてもOK）
  4. 作ったグループをあわらす式をつくる

未定義

  • true/falseのどちらも得られないとき　undefined(未定義)
  • 3値論理での論理積（条件付き論理積）→　&&
  • 3値論理での論理和（条件付き論理和）→　||
  • 3値論理での否定→　！

プログラマの数学

プログラマの数学