【授業】離散数学入門c
第一回
集合：与えられたものが属するかどうかを明確に判定できる集まり
要素（元）：集合に属するもの
集合の表し方
外延的記法：要素を列挙する 例、{x, y, z}
内包的記法：{要素|条件}の形で表す 例、{n|nは自然数かつn<100}
記号
$ \mathbb{N} :自然数全体
Z:整数全体
Q有理数全体
R実数全体
C複素数全体
命題：真偽が明確に決まる主張
真のとき命題の値をT
偽のとき命題の値をFで表す
条件命題：「pならばq」の形の命題(p, q : 命題)
「p→q」などで表す
p→qの真理値表
p q →T
p !q →F
!p q→T
!p !q →T
p→q && q→pが成り立つときp⇔qと表す
全称記号 ”任意の”, "全ての"
$ \forall x \in \mathbb{R} 全ての実数xに対して
存在記号 "(少なくとも１つ)存在する"
$ \exists x \in \mathbb{R} ある実数xが存在して
注意
s.t. : such that が存在記号のあとに付くことがある
定義1-1(部分集合)
集合Aの任意の要素が集合Bの要素であるとき、AはBの部分集合である、AはBに含まれるなどといい、$ A \subset B 等と書く
集合A,Bに対して「$ A \subset B かつ B \supset A」のときA=Bという
A$ \subsetBかつA!=BのときAはBの真部分集合であるといい、$ A\subsetneq Bとかく
空集合：要素を一つも持たない場合、$ \emptysetとかく
任意の集合Aに対して、$ \emptyset \subset Aである
＄1-2
全体集合（普遍集合）：考察対称である要素の全体
$ \mathbb{U}で表す
AとBの差集合
A\B = {x| x $ \inA, x$ \notinB}
Aの 補集合
$ \overline{A}= {x| xは$ \mathbb{U}の要素でAの要素でない}
$ A \cap B=\emptysetのとき、AとBは互いに素(disjoint)であるといい、$ A \cup Bをdisjoint unionという
交換律 $ A\cap B = B \cap A(和集合も)
結合律 $ (A\cap B)\cap C = A \cap (B\cap C)(和集合も)
分配率 $ A \cap (B\cup C) = (A \cap B) \cup (A\cap C)
ド・モルガンの法則 $ \overline{A\cap B} = \overline{A}\cup \overline{B}
第二回
有限集合
有限個の要素からなる集合
無限集合
有限集合でない集合
Aが有限集合のときAの要素数を|A|と表し、Aの濃度という
|A|をn(A), # Aなどと書く
包除原理
|$ A\cup B| = |A| + |B| - |$ A\cap B|
|$ A\cup B\cup C| = |A| + |B| + |C| - || - || - || + ||
A1, A2, ..., An : 有限集合
一般に|$ A1\cup A2\cup A3 ... \cup An| も書ける
Aのべき集合
Aの全ての部分集合を要素とする集合
A : 集合としたとき A ^ 2 : Aのべき集合とする
順序対
$ a\in A, b\in B から作った対(a, b)
AとBの直積(集合)A×B
A×B = {(a,b)| $ a\in A, b\in B}
一般にA1×A2×...×Anもある
A×AをA^2、A×A×AをA^3等とあらわす
関係
$ R\subset A×Bのとき、RをAからBへの関係という
$ R\subset A×Aのとき、RをA上の関係という
(x, y) $ \inRであるとき、xはyと関係Rにあるといい、xRyと書く
(x, y)$ \notinRのとき、xR\y(Rに斜線)と書く
恒等関係 等号=で表される関係
I ={(a,a)| $ a \in A} ？？？？
整除関係
x,y $ \inZに対し、y=gxとなる$ g\in Zが存在するとき、xはyの約数等という
第三回
最初いなかった
同値関係
定義...集合A上の関係Rが次の３条件を満たすときRを同値関係という
反射律: AのすべてのxでxRx
対称律:Aのすべてのx,yでxRy→yRx
推移律:Aのすべてのx,y,zでxRyかつyRz→xRz
例...恒等関係は同値関係である
例... $ m \in N $ x,y \in Zに対して、mがx-yの約数(m|(x-y))であるときxとyはmをほうとして合同であるといい、x=-y(mod m)と書く
定義...集合A上の同値関係
$ x \in Aに対し、
［x］= { y | xRy}
と定義し、［x］をxの同値類という ???
xを［ｘ］の代表元という
例題 Z上の、２を法とした合同関係に関して、同値類［１］を求めなさい
解：定義から
［1］= {x | x =- 1 (mod 2)}
よって［１］＝{...,-3,-1,1,3 ...}はすべての奇数からなる集合である
商集合 A / R = {［ｘ］｜$ x \in A}