pdfファイル

除法定理と剰余演算
- ∈ , ∈ に対して
0
なる , が一意に定まる
-
mod
剰余系
上の演算
mod
mod
mod
例題
(1)
(2)
(3)
(4)
(5)
15mod11
8
4
2
5
5
5
3
5
(ただし 5
9
)
外延的記法と内包的記法
1,3,5,7,9
%2
1∣ ∈ ,
5'
集合演算
( ∪ *, ( ∩ *, (, ( *
ドモルガン律
( ∪ * ( ∩ *, ( ∩ * ( ∪ *,
冪集合とその要素数
, ( : (の部分集合の集合
, (
2.
集合の直積（デカルト積）とその要素数
/, 0 / ∈ (, 0 ∈ *
( *
( *
(
*
例題
(
3
2
∈ ,
5 ,*
, , 1 %1,2,3'のとき
(1) (を外延的記法で表せ
(2) 普遍集合をとして、偶数の集合2を内包的記法で表せ
(3) , *
(4) , (
(5) * 1
(6) |1 4 |
(7) ( ∩ 1
(8) ( ∪ 1
(9) ドモルガン律などを用いて、より単純な式に書き換えよ
5∪6
5∩ 6∪
包除原理（和集合の要素数に関する性質）
|(1 ∪ (2 ∪ ⋯ ∪ ( | |(1| |(2| … |( |
∩( | |(1 ∩ (2| … |(
|(1 ∩ (2 ∩ (3| … |( 4 ∩ (
∩ ( |− …
1
(1 ∩ ⋯ ∩ (
正しさの証明には数学的帰納法が必要
直和分割
1 1
1 1 ∪ 14 ∪ ⋯ ∪ 1
9 : ; ならば 1< ∩ 1=
14
⋯
1
∅
集合をいくつかの部分集合に「分類」
全称限量子「∀」：任意の～（すべての～）
e.g.∀ , ∈ 存在限量子「∃」：～が存在する
e.g.∃ , ∈ 0
例題
以下の言明を限量子を用いて簡潔に表現せよ
任意の整数/, 0について / 0 4 /4 2/0 0 4 が
成立する
/D 0 D E D を満たす自然数/, 0, Eが存在する
解答は教科書p.21
, → Gが成り立つとき
「,はGの十分条件」、「Gは,の必要条件」
, → G、 G → ,がともに成り立つとき
「, G はG , の必要十分条件」
例題
宝くじを買うことは、宝くじに当たるための
条件
総理大臣であることは国会議員であることの条件
2つの三角形の三辺がそれぞれ等しいことはそれらが
合同であるための条件
腹囲が85cm以上あることはメタボであるための条件
が整数であることは、が有理数であるための条件
であり、が自然数であるための条件である
順命題, → Gに対して
逆：
G→,
裏：
~, → ~G
対偶：
~G → ~,
・順命題が真であるとき、その対偶も真であるが、逆、裏
は真であるとは限らない
・順命題の証明が「一筋縄でいかない」とき、対偶命題を
証明するという手がある
対偶による証明
背理法
真であることを証明したい命題,に対して、,が偽である
ことを仮定（背理法の仮定）すると矛盾が生じることを示
すことによって、,が真であることを証明する方法
集合5から集合6への対応I: 5 → 6 ⊆ 5 6
部分写像：多対1の対応を「部分写像」、
写像： 5にもれの無い（定義域が5に一致する）部分写像
全射： 6にももれの無い（値域が6に一致する）写像
単射： 1対1対応
全単射：全射かつ単射
5, 6が有限集合であるとき要素数が同じ 5
6
5, 6が無限集合であるとき濃度が同じ
可付番集合（可算集合）
・自然数の集合と濃度が同じ無限集合
・偶数の集合、有理数の集合などは可付番集合
・,
,実数の集合Kは可付番集合でない（対角線論法）
5, 6が有限集合であるとき
5から6への写像は 6 L 通り
5から6への部分写像は 6
1 L 1通り
5から6への単射は M , L 通り
5から6への全射は、「場合わけ」した数え上げが必要
例題
(
1,2,3,4 , *
/, 0, E であるとき(から*への部分写像、
写像、全射はそれぞれ何通りあるか
(
1,2,3,4 , *
/, 0, E, N, O であるとき(から*への部分
写像、写像、単射はそれぞれ何通りあるか
置換：有限集合5上の 5から5への全単射
巡回置換： 5の部分集合を「ぐるっと」置き換える置換
定理「5上の任意の置換は、巡回置換の積で表すことがで
きる」
例題
1
5
2 3 4 5
を巡回置換の積で表しなさい
4 2 3 1
個の要素の中から個を選んで並べる順列の数
個の要素の中から個を選ぶ組合せの数
1
,
/
0
/
/
0
1
⋯
ただし
P
0
2
1
/
/
4
04
⋯
0
1Q
例題
101R
100
1
R
最小公倍数（LeastCommonMultiple） LCM
最大公約数 GreatestCommonDivisor GCD
例題
b1c 42,140
d1e 42,140
0
基底：基本となる要素を有限個定義
漸化式の場合: f ~fQ P g 1 を定義
帰納：定義済の要素の組合せで新たな要素を定義
漸化式の場合：f をf Q ~f を用いて定義
結論: 以上によって得られるもののみが集合の要素
漸化式の例
フィボナッチ数列
1, f 1
2
f 0
f
f
1
f
2 g2
「∀ ∈ , 」の証明
(1) 基本段階:
, が真であることを示す
(2) 帰納段階:
,Q が真であることを仮定して
,Qh が真であることを示す
(3) 結論:
すべての自然数について , が真
以下を数学的帰納法により証明せよ
（p.67の解8を参考にすること）
1.
3
7 は8で割ると2余る
2.
2i
2
24
2D
3.
1D
2D
⋯
D
⋯
＝ 1
2 ＝2
2
⋯
h
1
4

Download Report