離散数学及び演習 講義1

離散数学クラス分け


離散数学及び演習（Discrete Mathematics）

別途掲示で指定されたクラスで受講すること．
指定以外のクラスでの受講は認めない．



間違いなく受講申請すること．

3年次編入者・2013年度以前入学の再履修者

工学部専門系科目 （専門基礎科目）



電気電子・情報工学科
Bクラス
2014年度前期

学籍番号の学科内番号部分（08-1Z-3-XXX-Y）を３で割り，割り切れる場合 ：１余る場合：
 ２余る場合
：

Ａクラス
Ｂクラス
Ｃクラス



2

講義の内容
離散的対象の性質や離散的対象の間に存在する関係についての議論
 離散的対象の表現手法（解析・設計手法）


離散数学及び演習
第 1 回 2014. 4.17（木）集合論（set theory）
 整数論（number theory）
 代数系（algebraic system）
講義概要
集合・集合演算（教科書 pp.1-3, 5-9）
教科書･･･野崎昭弘：離散系の数学、近代科学社4週

講義の目的
離散的対象に関する知識の習得
 様々な分野に対する基礎的知識の習得




講
義・演
習
予
定

理論計算機科学，ソフトウェア基礎論など

概念を客観的かつ論理的に表現，論証するための手法・技術の習得


数学のための日本語表現


記号の使い方
論理的表現・言い回し
「任意の…」，「ある…」，「一意的」「かつ」，「または」，「…であるとき，かつそのときに限り，…」，etc.

論証技術
証明の記述＝論理的思考の洗練 数学の体系的記述

定義，定理，補題，系，証明
5

1

月日

講義

演習

14/17

1

講義の概要，集合・集合演算

1

集合・集合演算24/24

2

直積・関係，2項関係の性質

2

直積・関係

35/ 1

3

同値関係，半順序

3

2項関係の性質45/ 84束

4同値関係

55/155関数

5

半順序

65/226

束7関数75/2986/ 5

96/12（講義なし）
中間試験（範囲：講義1～5）
6

約数・倍数

7素数

81次不定方程式，合同式

9合同式（続き）

約数・倍数（演習なし）

9素数， 1次不定方程式

10

合同式

10

6/19

116/2610多項式，環11多項式，環127/ 311環（続き），群12環（続き） ，群

13

7/10

12部分系，準同型

13

商系

14

7/17157/24 ??

（講義なし）（演習なし）
8（講義なし）期末試験（範囲：講義1～13）（演習なし）
13部分系，準同型

14

商系
6

離散数学及び演習 講義1

講義の進め方

原則として1時限目
教科書






野崎昭弘：離散系の数学，近代科学社（1980）．
事前に該当部分を読んでおくこと

PowerPoint 使用
http://www.kl.i.is.nagoya-u.ac.jp/~toyama/lecture/risan14/

原則として２時限目
教室


講義資料




演習の進め方

pdf 版をダウンロード可能



小テスト



問題解答

参考書
 佐藤文広：数学ビキナーズマニュアル［第2版］，日本評論社（2014）．
 結城浩：数学文章作法 基礎編，筑摩書房（2013） ．








リュー（成嶋・秋山訳）：コンピュータサイエンスのための離散数学入門，オーム社（1986）．
小倉久和：情報の基礎離散数学，近代科学社（1999）．
楫元：工科系のための初等整数論入門，培風館（2000）．
新妻弘・木村哲三：群・環・体入門，共立出版（1999）．

143教室 … １年（B－1クラス），２年，４年
144教室 … １年（B－2クラス），３年



前回演習の内容（解答用紙は次回返却）指定された問題を解答
解答を板書・解説
解答用紙を提出（次回返却）
指定外の問題は自学自習

演習問題解答例


http://www.kl.i.is.nagoya-u.ac.jp/~toyama/lecture/risan14/


pdf 版をダウンロード可能

78

成績評価



中間試験
期末試験
小テスト
演習解答



演習板書



評価区分







約30％
約40％

集合論
（set theory）

約30％

2011年度以降入学者
Ｓ：100～90，Ａ： 89～ 80，Ｂ： 79～70，Ｃ：69～60，Ｆ：59～0
2010年度以前入学者
優：100～80，良：79～70，可：69～60，不可： 59～0
期末試験を欠席した場合は，「欠席」とする．

不合格の場合

来年度も同じクラスで受講
9

集合（set）
集合（続き）
S

集合（素朴な定義） 相異なる対象の集まり

対象 … 要素，元（element）
 対象 a は集合 S の要素である（対象 a は集合 S に属する） … a∈S 対象 a は集合 S の要素でない（対象 a は集合 S に属さない） … aSc集合は相異なる要素のみを含む
例： { a，a，b，c }＝{ a，b，c }

ba





集合の要素を並べる順序は問わない
例： { b，c，a }＝{ a，b，c }Venn 図文字の使い方（原則）：


例：




集合 … 大文字 （A，B，C，S，R，T，…）
要素 … 小文字 （a，b，c，x，y，z，…）

要素 a，b，c からなる集合… { a，b，c }すべての自然数からなる集合 … { 1，2，3，…}11122

離散数学及び演習 講義1

集合の要素を記述する方法
集合の要素数すべての要素を列挙する



例： S＝{ 2，4，6，8，… }

要素をひとつも含まない集合

すべての要素を一意的に特徴付ける性質を述べる
例： S＝{ x｜x は正の偶数}空集合（empty set） φ （ ＝{ } ）

有限集合（finite set）

すべての要素を生成する 1 組の規則を述べる

例：2∈S，x∈S ならば，x＋2∈S，（S は他の要素を含まない）．


要素が有限個である集合
有限集合 A の要素数 … A の大きさ（size） ｜A｜
例： ｜ { a，b，c } ｜＝3｜φ｜＝0無限集合（infinite set）


要素が無限個である集合

1314部分集合（subset）
定理

集合 A は集合 B の部分集合である （A ⊆ B）
集合 A は集合 B に含まれる集合 A，B，C に対して，次の（1）～（3）が成り立つ．
（1） A ⊆ A（2） φ⊆ A（3） A ⊆ B， B ⊆ C ならば，A ⊆ C

任意の x∈A に対して，x∈B であるB

例： A＝{ b，2 }，B＝{ y，2，b，3，a }A⊆Bb∈B，2∈B

A×x

例： { x｜x は正の偶数 } ⊆{ 1，2，3，… }1516

真部分集合（proper subset）

等しい集合集合 A と集合 B は等しい（equal） （A＝B）


A⊆B かつ B⊆AA⊆B かつ A≠B
B

任意の x∈A に対して x∈B ，かつ，任意の x∈B に対して x∈A

例： A＝{ b，2 }，B＝{ y，2，b，3，a }
A⊂B

×A⊆B
 y∈B，y A

例： { x｜x は正の偶数 }＝{ 2，4，6，… }集合 A は集合 B の真部分集合である （A⊂B）{ x｜x は正の偶数 }⊆{ 2，4，6，… }かつ{ 2，4，6，… }⊆{ x｜x は正の偶数 }A××x

例： { x｜x は正の偶数 } ⊂{ 1，2，3，… }17183

離散数学及び演習 講義1和集合（union）

真部分集合（続き）
集合 A は集合 B の真部分集合である （A⊂B）

A⊆B かつ A≠B
iff A⊆B， かつ，（ A⊆B かつ B⊆A ）でない
iff A⊆B， かつ，（ A⊆B でないか，または，B⊆A でない）
iff A⊆B， かつ， B⊆A でない
iff A⊆B， かつ，（ 任意の x∈B に対して x∈A ） でない
iff A⊆B， かつ，ある x∈B に対して x∈A でない集合 A と集合 B の和集合（合併集合，結び）
A∪B＝{ x｜x∈A または x∈B }ABP であるとき，かつそのときに限り，Q である（ Q if and only if P，Q iff P ）

B

P であるとき，Q である （ Q if P ）かつP であるときに限り，Q である （ Q only if P ）（＝ Q であるとき，P である （ P if Q ））P と Q は必要十分である

A×××A∪Bx1920

積集合（intersection)差集合（difference）

集合 A と集合 B の積集合（共通集合，交わり）A∩B＝{ x｜x∈A かつ x∈B }集合 A と集合 B の差集合
A－B＝{ x｜x∈A かつ xB }

AA
B

B
A－B

A∩B
2122

互いに素な集合定理
集合 A，B，C に対して，次の（1）～（6）が成り立つ．
（1） A⊆A∪B.
（2） A⊆C， B⊆C ならば，A∪B⊆C.
（3） A∪B＝Bであるとき，かつそのときに限り， A⊆B.
（4） A∩B⊆A.
（5） C⊆A， C⊆B ならば，C⊆A∩B.
（6） A∩B＝Aであるとき，かつそのときに限り， A⊆B.

集合 A と集合 B は互いに素（disjoint）
A∩B＝ΦAB

P であるとき，かつそのときに限り，Q である （ Q if and only if P，Q iff P ）

23

P であるとき，Q である （ Q if P ）かつP であるときに限り，Q である （ Q only if P ）（＝ Q であるとき，P である （ P if Q ））P と Q は必要十分である
24

4

離散数学及び演習 講義1

証明

証明（1） A⊆A∪B
（2） A⊆C， B⊆C ならば，A∪B⊆C「任意の x∈A に対して，x∈A∪B」 を示す．

任意の x∈A に対して，x∈A または x∈B だからx∈A∪B．
ゆえに，A⊆A∪B．

A⊆C， B⊆C を仮定して， A∪B⊆C を示す．
 「任意の x∈A∪B に対して，x∈C」 を示す．

A⊆C， B⊆C とする．
任意の x∈A∪B に対して，x∈A または x∈B．
x∈A のとき， A⊆C だから， x∈C．
x∈B のとき， B⊆C だから， x∈C．
いずれの場合も x∈C．
ゆえに， A∪B⊆C．

25

26

証明

証明（続き）（3） A∪B＝Bであるとき，かつそのときに限り， A⊆B a） 「A∪B＝B ならば A⊆B」 と b） 「A⊆B ならば A∪B＝B」 の両方を示す．
 b）
A⊆B を仮定して， A∪B＝B を示す．
 「 A∪B⊆B 」 かつ 「 B⊆A∪B 」 を示す．
 b-1）「任意の x∈A∪B に対して，x∈B 」 を示す．

（3） A∪B＝Bであるとき，かつそのときに限り， A⊆Ba） 「A∪B＝B ならば A⊆B」 とb） 「A⊆B ならば A∪B＝B」 の両方を示す．
 a）
A∪B＝B を仮定して， A⊆B を示す．
 「任意の x∈A に対して，x∈B」 を示す．
a） A∪B＝B とする．
任意の x∈A に対して，（1） A⊆A∪Bから，x∈A∪B＝B．
ゆえに， A⊆B．

b） A⊆B とする．
b-1）任意の x∈A∪B に対して， x∈A または x∈B．
A⊆B だから，x∈A のときも x∈B．
ゆえに， A∪B⊆B．
b-2）（1）から，B⊆A∪B．
したがって， A∪B＝B．
27

28

定理

定理（続き）

集合 A，B，C に対して，次の（1）～（5）が成り立つ．
（1） A∪A⊆A，A∩A⊆A
冪（べき）等則（idempotent law）
（2） A∪B＝B∪A ，A∩B＝B∩A
交換則（commutative law）
（3） （A∪B）∪C＝A∪（B∪C），（A∩B）∩C＝A∩（B∩C）
結合則（associative law）

（4） （A∪B）∩C＝（A∩C）∪（B∩C），（A∩B）∪C＝（A∪C）∩（B∪C）
分配則（distributive law）
（5） A∩（A∪B）＝A，
A∪（A∩B）＝A
吸収則（absorptive law）

29

30

5

離散数学及び演習 講義1

全体集合・補集合


全体集合（universe） U定理
集合 A，B に対して，次の（1）～（5）が成り立つ．
（1） A∪Ac＝U，
A∩Ac ＝φ（2） A ⊆ B ならば，Bc ⊆ Ac．
（3） A－B ＝ A∩Bc．
（4） Uc ＝ φ，φc ＝ U．
（5） （Ac）c ＝ A．

すべての対象からなる集合集合 A （⊆U）の補集合（complement）


Ac＝U－AUAcA

3132定理（de Morgan の法則）

証明
（1） （A∪B）c ＝ Ac∩Bc
a） 「（A∪B）c ⊆ Ac∩Bc 」 とb） 「 Ac∩Bc ⊆（A∪B）c 」 の両方を示す．
a）「任意の x∈（A∪B）c に対して， x∈ Ac∩Bc 」 を示す．
b）「任意の x∈Ac∩Bcに対して， x∈（A∪B）c 」 を示す．

集合 A，B に対して，次の（1），（2）が成り立つ．
（1） （A∪B）c ＝ Ac∩Bc（2） （A∩B）c ＝ Ac∪Bca） 任意の x∈（A∪B）c に対して， xA∪B．
x A かつ x B だから， x∈ Acかつ x∈ Bc．
ゆえに，x∈Ac∩Bc．
したがって， （A∪B）c ⊆ Ac∩Bc．
b） 任意の x∈ Ac∩Bc に対して， x∈Ac かつ x∈Bc ．
x A かつ x B だから， x A∪B ．
ゆえに，x∈（A∪B）c ．
したがって， Ac∩Bc ⊆（A∪B）c ．

A. de Morgan（英，1806-1871）33

34

定理（包除原理）

集合を要素とする集合

有限集合 A，B に対して，｜A∪B｜＝｜A｜＋｜B｜－｜A∩B｜



集合は相異なる対象（要素）の集まり


要素が集合である場合も考えられる

例： S＝{ x，2，{ 1，x，a } }＝{ x，2，T }AB（ T ＝{ 1，x，a } ）｜S｜＝ 3

例： A＝{ a，b，c }B＝{ a，b，c，{ a，b，c } }＝{ a，b，c，A }A∩B｜B｜＝ 4A∈B
 A⊆B



A∪B
35

636

離散数学及び演習 講義1冪（べき）集合（power set）

集合を要素とする集合（続き）
φ（ ＝{ } ）


空集合



… 要素をひとつも含まない集合 （｜φ｜＝ 0 ）集合 A の冪集合P（ A ）＝２A ＝ { S｜S ⊆ A }

A のすべての部分集合を要素とする集合{φ} （ ＝{ { } } ）

空集合を唯一の要素とする集合… 要素を１つだけ含む集合 （｜{φ}｜＝ 1 ）φ≠{φ}



集合のクラス（集合族（family））


例： A＝{ 1，2，3 }P（ A ）＝{ φ，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3} }要素が集合である集合
37

38

定理

まとめ有限集合 A に対して，｜P（ A ）｜＝｜２A｜＝ 2｜A｜



今回の講義
集合 集合演算

例： A＝{ 1，2，3 }P（ A ）＝{ φ，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3} }



次回の講義


｜P（ A ）｜＝ 82｜A｜＝ 23＝ 8

今回の演習
39

直積・関係，2 項関係の性質（教科書 pp.9-12）
集合・集合演算407