2001年度情報数学 - GOTO Laboratory

Ver.2
2007年度 情報数学
金曜日
スケジュール
は後述
2007年 4月~7月(合計12回予定)
講義資料: 上田 和紀 原著
後藤 滋樹 三訂
☆ 金曜日の担当は後藤滋樹と上田和紀教授です
1
2
班別の授業の注意
※) 金曜日の青字の分担が当初の予定から変更
奇数と偶数
 学籍番号による(定期試験の会場も班別)
 月曜日 1限(奇数)と2限(偶数)
奇数: 小林聡先生 全期間
偶数: 小林聡先生 全期間
 金曜日 2限(偶数)と3限(奇数)
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
後藤担当分は教科書の指定なし(※)

講義資料のURLはシラバスの「情報数学」の
「履修上の注意」に掲載されています。

後藤研のWEBページ(日本語)の「後藤先生担
当の講義」から辿ることもできます。
http://www.goto.info.waseda.ac.jp/
~goto/infomath.html
ここに ~ が必要
※) 過去のシラバスの記述
では教科書を指定するように
書いてありました。訂正。
4
情報数学の概観
 書店の店頭で「情報数学」という題名の本を手
に取ってみると、その内容が著者により異なる。
 本科目は、CS学科の諸君が近い将来に必要と
する数学的概念の中で重要なものを取扱う。
 数学A,
Bおよび各専門科目で取扱う題材とは、
できるだけ重複しないように題材を選択するが、
基本概念は随所に登場するものと心得よ。
5
後藤が担当する授業の題材
集合 (set)
 万物は集合である
 写像 (map) または関数 (function)
 集合と集合との対応
 関係 (relation) と順序 (order)
 友達という関係は推移的 (transitive) であるか
 帰納法 (induction)
 数学的帰納法
 代数 (algebra) の初歩
 群、環、体

6
集合とは相異なるものの集まり

集合の例

{ a, b, c }
 2 次元平面上のすべての点の集合
 CS学科の2年生の集合
 自然数の集合

判断基準が明確であること
Fuzzyな概念の
例。本科目では
ファジー集合を
扱わない
 新宿区に住民登録をしている金持ちの集合

実は上の素朴な定義から矛盾が生じる
 ラッセル (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
Venn図
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 {})

差集合
すべてのxについて
以下が成り立つ
否定
あるxについて以下
が成り立つ
11
集合の集合

集合 {ham, egg,
りあるか?

potato} の部分集合は全部で何通
{ham}, {egg}, { potato},
{ham, egg}, {egg, potato}, {ham, potato}
(これで全部だろうか。2つ足りない。)

与えられた集合 S の部分集合の全体は,集合をな
す。これを S のべき集合 (powerset) という。
べき集合を (S ) あるいは 2s と書く。

{ham, egg, potato} には
{} と
2
{ham, egg, potato} が含まれる。
12
ラッセルのパラドックス

集合Xを次のような「もの」の集まりとする
Xの要素(元)は集合である(つまり集合の集合)
Xの要素は「自分自身を要素として含まない集合」
である
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
共通部分を積集合と呼ぶことがあるが別物
 例1:Descartes座標の全体
 例2:


  
  
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 の合理性)
この性質を使うと、べき集合の要素の数が分る