2007年 4 月～7 月（ 合計12回予定） 講義資料： 上田 和紀 原著 後藤 滋樹 三訂

Presentation on theme: "2007年 4 月～7 月（ 合計12回予定） 講義資料： 上田 和紀 原著 後藤 滋樹 三訂"— Presentation transcript:

1 2007年 4 月～7 月（ 合計12回予定） 講義資料： 上田 和紀 原著 後藤 滋樹 三訂
Ver.2 ２００７年度 情報数学 金曜日 スケジュールは後述 2007年 4 月～7 月（ 合計12回予定） 講義資料： 上田 和紀 原著 　　　　　　後藤 滋樹 三訂 ☆　金曜日の担当は後藤滋樹と上田和紀教授です

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
後藤担当分は教科書の指定なし（※） 講義資料のＵＲＬはシラバスの「情報数学」の「履修上の注意」に掲載されています。 後藤研のＷＥＢページ（日本語）の「後藤先生担当の講義」から辿ることもできます。 ~goto/infomath.html ※）　過去のシラバスの記述では教科書を指定するように書いてありました。訂正。 ここに ~ が必要

4 情報数学の概観 書店の店頭で「情報数学」という題名の本を手に取ってみると、その内容が著者により異なる。
本科目は、ＣＳ学科の諸君が近い将来に必要とする数学的概念の中で重要なものを取扱う。 数学A, Bおよび各専門科目で取扱う題材とは、できるだけ重複しないように題材を選択するが、基本概念は随所に登場するものと心得よ。

5 後藤が担当する授業の題材 集合 (set) 万物は集合である 写像 (map) または関数 (function) 集合と集合との対応
関係 (relation) と順序 (order) 友達という関係は推移的 (transitive) であるか 帰納法 (induction) 数学的帰納法 代数 (algebra) の初歩 群、環、体 これが正しいかどうかを、以前に真理値表や式変換で確認した（代数的な方法）。 実はそれらは効率的な証明方法とはいえない。

6 Ｆｕｚｚｙな概念の例。本科目ではファジー集合を扱わない
集合とは相異なるものの集まり 集合の例 2 次元平面上のすべての点の集合 ＣＳ学科の２年生の集合 自然数の集合 判断基準が明確であること 新宿区に住民登録をしている金持ちの集合 実は上の素朴な定義から矛盾が生じる ラッセル (Russel) のパラドックス　（後ほど説明） Ｆｕｚｚｙな概念の例。本科目ではファジー集合を扱わない

7 集合には同じ要素を複数書いても無意味（⇔ 多重集合）
集合の表現 「ものの性質（基準）」 と 「その性質を満たすもの 全体の集合」 集合には同じ要素を複数書いても無意味（⇔ 多重集合） 要素を列挙する（外延的） 要素が満たすべき性質を規定（内包的） 空(くう)集合

8 無限の要素を持つ集合 “...” を使うのは厳密ではないが，誤解の恐れが 無い場合には使う 問題なし 大体分る 分らない
下記の記号は多くの文献で定義せずに使う 自然数の集合 N ... 普通は0 から始める 整数の集合　 Z 有理数の集合 Q 実数の集合　 R

9 いろいろな概念が を使った論理式で定義できる．
　　　　とも書く、部分集合 (subset) Ａ Ｂ Ｖｅｎｎ図

10 和集合、共通部分、差集合 和集合 （結び、合併） 共通部分 （交わり） 差集合 空集合の性質 否定 否定 すべてのｘについて以下が成り立つ
あるｘについて以下が成り立つ

11 集合の集合 集合 の部分集合は全部で何通りあるか？ （これで全部だろうか。２つ足りない。）
集合 の部分集合は全部で何通りあるか？ （これで全部だろうか。２つ足りない。） 与えられた集合 S の部分集合の全体は，集合をなす。これを S のべき集合 (powerset) という。 べき集合を 　あるいは　　と書く。 　　　　　　　　　には　　と 　　　　　　　　　が含まれる。

12 ラッセルのパラドックス 集合Ｘを次のような「もの」の集まりとする Ｘの要素（元）は集合である（つまり集合の集合） Ｘの要素は「自分自身を要素として含まない集合」である 　 この時、　　　　としても としても矛盾を生じる ［演習問題］

13 直積（デカルト積，Cartesian product）
A の要素(元)と B の要素(元)の順序対の集合： 共通部分を積集合と呼ぶことがあるが別物 例１：Descartes 座標の全体 例２： 論理記号and        

14 二つのものを対(ペア)にする a と b を対にする方法： 順序をつけない  （非順序対） ( 集合として) 順序をつける  （順序対）
順序をつけない  （非順序対） 　　( 集合として) 順序をつける  （順序対） 順序対の間の同等性＝を次のように定義 非順序対で順序対を定義できる 論理記号and

15 三つ以上の集合の直積 を ， を と書く．以下同様． は何か ?
を ， を と書く．以下同様． は何か ? 要素の個数が同じ二つの集合は，要素の対応づけの方法を決めることによって同一視できる の二つの定義は同一 集合 は　 と同一視できる集合

16 対等 (equipollent) な集合 A B f 写像 f と g とが存在して g
　とできるとき，集合 A と B とは対等であるといい， 　　　と書く．また f や g を一対一対応 (one-to-one mapping) という．対等な集合は同一視可能。 例：数直線上の点の集合と実数の集合 R g A B

17 直和集合(disjoint union) 二つの集合の要素を区別して合併したもの 先に説明した和集合 とは異なる
先に説明した和集合 とは異なる 例：名簿の項目：　　　　　　　　 （これは直積） 　　　　　　　　： or 例：メールのアドレス： 　　　or　　　 0 と 1 は区別するための目印：タグ (tag) 0 と 1 でなくても区別が明確であれば良い 氏名 連絡先 連絡先 1 携帯電話 差出人 1 宛先

18 要素の個数 集合 A が有限集合のとき，その要素の個数を と書く（ ）。Nは自然数の集合 注：後に無限集合に拡張する
A と B が有限集合のとき が成り立つ（ 記法　　　　　　　　の合理性） この性質を使うと、べき集合の要素の数が分る