離散構造： 前半

離散構造 授業前半のポイント

1. 論理

* 論理記号と論理式の構造を理解すること (∧、∨、⇒、¬、⇔、∀、∃  お
  よび A¬B とか A∪B とか ∀∃x=0などは論理式でないことを理解する。)
* 日本語などの自然言語表現を、なるべく正確に論理式で表現すること
* 命題論理に対する真理値表を正確に書けるようになること (この式は恒真か、充足可
  能か、これとこれは同値か、などの質問に答えられるようになること)
  
2. 集合

* 集合とはなにか、「属する」という関係(a∈S)、内包的な表記 などを理解する
* 集合に対する演算を理解すること(∪、∩、-, べき集合、×)、
* 集合に対する推論を理解すること(S=T, S⊂T)
* 有限集合の要素数の計算に慣れること。(#(S∪T)=#S+...など)

3. 関数

* 関数の定義、部分関数の定義、基本的な言葉(定義域、コドメイン)
* 関数に関する概念については、その定義と推論を正確にできるようになるこ
  と。像、 合成関数 gof (f を適用してからgを適用するという順番に特に注意)
  単射、全射、全単射、逆関数。


※ A∧B∨C やA⇒B⇒Cという風に括弧を省略した場合、どう補うかは注意を要する
   (本講義の範囲内では、問題文にあらわれる論理式は括弧を十分つけたもの
   しか書かない)
※ ∀x∃yA と ∃y∀x A は、論理式としての意味が(まったく)異なることに
   注意。
※ 論理式A∧B と和集合A∪B は絶対に混同しない。
※ 集合の要素は、数や「もの」とは限らない。集合の集合もある。
※ 「ベン図」は証明には使えない。考えるための便利な道具。
※ 自然数の集合N は 0を要素とする。
※ S⊂T は、S=T の場合も含む。
※ 一般の集合については、「単射だから全射」といった関係はない。(有限集
   合SからSへの関数については、単射であることと全射であることは一致する。)

!! 証明問題は、「○○の定理」を使う、というようなことはなく、
   すべて、「定義にたちかえって解きほぐす」ことによって解けるはずである。

---------------------------------------------------------------------
進んだ学習、話題

論理->  
  SATソルバ (命題論理式の充足可能性をとんでもなく高速に解くプログラム)
  プログラムの仕様記述、形式検証 (プログラム検証)
  コンピュータを使った定理の証明 (数学の世界ではなく、コンピュータ屋さんの世界)
  論理プログラミング (Prolog)
  人工知能などにおける知識表現の手段

集合->
  数学(および様々なモデル化)の基礎中の基礎
  プログラム言語における型(データ型)

関数->
  関数型プログラム言語; OCaml, SML, Lisp/Scheme, Haskellなど
  プログラムのモデル； プログラムの意味論
  離散構造「6章」〜帰納的関数論 (計算モデルの1つ)

興味がある人は、インターネットを検索して Wikipedia 等を見るだけでもよ
い。(非常に興味深い記事が多数ある。)