Ver.2 ２００７年度情報数学金曜日スケジュールは後述 2007年 4月～7月（合計12回予定）講義資料：上田和紀原著後藤滋樹三訂 ☆ 金曜日の担当は後藤滋樹と上田和紀教授です 1 2 班別の授業の注意 ※）金曜日の青字の分担が当初の予定から変更奇数と偶数  学籍番号による（定期試験の会場も班別）  月曜日１限（奇数）と２限（偶数）奇数：小林聡先生全期間偶数：小林聡先生全期間  金曜日２限（偶数）と３限（奇数） 4/13, 4/20, 5/25, 6/1, 6/8, 6/29: 後藤滋樹 4/27, 5/11, 5/18, 6/22, 7/6, 7/13: 上田和紀先生（※）5/4 祝日、6/15 理工スポーツ大会  再履修の諸君の班別は柔軟に対処します。 3 後藤担当分は教科書の指定なし（※）  講義資料のＵＲＬはシラバスの「情報数学」の「履修上の注意」に掲載されています。  後藤研のＷＥＢページ（日本語）の「後藤先生担当の講義」から辿ることもできます。 http://www.goto.info.waseda.ac.jp/ ~goto/infomath.html ここに ~ が必要 ※）過去のシラバスの記述では教科書を指定するように書いてありました。訂正。 4 情報数学の概観  書店の店頭で「情報数学」という題名の本を手に取ってみると、その内容が著者により異なる。  本科目は、ＣＳ学科の諸君が近い将来に必要とする数学的概念の中で重要なものを取扱う。  数学A, Bおよび各専門科目で取扱う題材とは、できるだけ重複しないように題材を選択するが、基本概念は随所に登場するものと心得よ。 5 後藤が担当する授業の題材集合 (set)  万物は集合である  写像 (map) または関数 (function)  集合と集合との対応  関係 (relation) と順序 (order)  友達という関係は推移的 (transitive) であるか  帰納法 (induction)  数学的帰納法  代数 (algebra) の初歩  群、環、体  6 集合とは相異なるものの集まり  集合の例  { a, b, c }  2 次元平面上のすべての点の集合  ＣＳ学科の２年生の集合  自然数の集合  判断基準が明確であることＦｕｚｚｙな概念の例。本科目ではファジー集合を扱わない  新宿区に住民登録をしている金持ちの集合  実は上の素朴な定義から矛盾が生じる  ラッセル (Russel) のパラドックス（後ほど説明）集合の表現  「ものの性質（基準）」と「その性質を満たすもの全体の集合」要素を列挙する（外延的） 7 集合には同じ要素を複数書いても無意味（⇔ 多重集合） {2, 4, 6, 9, 11}, {月, 月, 火, 水, 木, 金, 金}  要素が満たすべき性質を規定（内包的） { n | n 月には31日がない, 1  n  12}  空(くう)集合 {}または 0 (と書く本もある ) 8 無限の要素を持つ集合 “...” を使うのは厳密ではないが，誤解の恐れが無い場合には使う問題なし {2, 4, 6, 8, ...} 大体分る {2, 4, 8, 16, ...} 分らない {2, 3, 5, 7, ...}  下記の記号は多くの文献で定義せずに使う自然数の集合 N ... 普通は0 から始める  整数の集合 Z 有理数の集合 Q 実数の集合 R x X x が集合Xの要素(元)である  9 いろいろな概念が  を使った論理式で定義できる．  A  B  (x  Aならば x  B)  A  B とも書く、部分集合 (subset) ＡＢＶｅｎｎ図 A  B  ( A  B かつ B  A) 10 和集合、共通部分、差集合   和集合 x  A  B （結び、合併）共通部分（交わり）  (x  Aまたは　x  B) x  A  B  ( x  Aかつ　x  B) 否定 x  A  B  ( x  Aかつ x  B)  空集合の性質 x ( x {}) x ( x {})  差集合すべてのｘについて以下が成り立つ否定あるｘについて以下が成り立つ 11 集合の集合  集合 {ham, egg, りあるか？  potato} の部分集合は全部で何通 {ham}, {egg}, { potato}, {ham, egg}, {egg, potato}, {ham, potato} （これで全部だろうか。２つ足りない。）  与えられた集合 S の部分集合の全体は，集合をなす。これを S のべき集合 (powerset) という。べき集合を (S ) あるいは 2s と書く。  {ham, egg, potato} には {} と 2 {ham, egg, potato} が含まれる。 12 ラッセルのパラドックス  集合Ｘを次のような「もの」の集まりとするＸの要素（元）は集合である（つまり集合の集合）Ｘの要素は「自分自身を要素として含まない集合」である X  {x | x  x}, x は集合を表す。  この時、 X  X としても X  X としても矛盾を生じる［演習問題］ 13 直積（デカルト積，Cartesian product）  A の要素(元)と B の要素(元)の順序対の集合：A B   A  B  { a, b | a  A  b  B}  論理記号and 共通部分を積集合と呼ぶことがあるが別物  例１：Descartes座標の全体  例２：         14 二つのものを対(ペア)にする  a と b を対にする方法：  順序をつけない  {a, b}  {a, b}  {b, a},  順序をつける   （非順序対） {a, a}  {a} ( 集合として) a, b （順序対）順序対の間の同等性＝を次のように定義 a, b  c, d  (a  c)  (b  d )  非順序対で順序対を定義できる  a, b  {{a},{a, b}} 論理記号and 15 三つ以上の集合の直積   2，を A A A 1  A は何か? A A A を 3 と書く．以下同様． A 要素の個数が同じ二つの集合は，要素の対応づけの方法を決めることによって同一視できる   {0, 1, 2} vs. {red, green, yellow}  0  red, 1  green, 2  yellow A  B  C の二つの定義は同一 a, b, c   0, a , 1, b , 2, c    集合 1 A は A と同一視できる集合 16 対等 (equipollent) な集合 f A  g B 写像 f と g とが存在して  x  A( g( f ( x))  x)  y  B ( f ( g( y))  y) とできるとき，集合 A と B とは対等であるといい， A B と書く．また f や g を一対一対応 (one-toone mapping) という．対等な集合は同一視可能。  例：数直線上の点の集合と実数の集合 R 17 直和集合(disjoint union)  二つの集合の要素を区別して合併したもの  A  B  { 0, a | a  A} { 1, b | b  B}  先に説明した和集合  例：名簿の項目：連絡先： 0 A B 氏名 e-mail とは異なる連絡先（これは直積） or 1 携帯電話  例：メールのアドレス： 0 差出人 or 1 宛先  0 と 1 は区別するための目印：タグ (tag)  0 と 1 でなくても区別が明確であれば良い 18 要素の個数  集合 A が有限集合のとき，その要素の個数を A と書く（ A  N ）。Nは自然数の集合  注：後に無限集合に拡張する  A と B が有限集合のとき A  2 2  A B  A  B  A B  A  B A A 2 が成り立つ（ 記法 , A  B, A  B の合理性）この性質を使うと、べき集合の要素の数が分る