やさしく学べる離散数学

概要

本

• やさしく学べる離散数学 | 石村 園子

かかった時間

• 8.9 時間

読む前の状態

• 離散数学という分野があることを知って、全体観を掴むために読むことにした

感想

• 離散数学の全体観がわかった

  • 各分野の基本的な用語を理解した

  • どの分野も定義がしっかりしていて、とてもわかりやすかった

• コンピュータサイエンスだと数え上げとグラフが大切そうなので、そこは別の本で補足する

読書メモ

1. 集合と論理

集合

• 集合

  • 対象としているものの集まりのうち、対象物が属しているかいないかが、明確に判定できる集まりを集合という

• ベキ集合

  • 集合 A のすべての部分集合からなる集合を A のベキ集合といい、P(A) または 2^A などで表す

  • 例えば A = {a, b} のベキ集合 P(A) = {φ, {a}, {b}, {a, b}}

• 「∀」は全称記号と呼ばれる。「すべての」という意味。「∃」は存在記号と呼ばれる。「ある要素が存在する」ことを表す

論理

• 命題

  • 真か偽かどちらか一方に明確に定まる主張を命題という

• 命題関数

  • 変数にある特定の要素を代入すると真偽が定まる主張を命題関数、または述語という

• 論理演算

  • 2 つの命題 p, q の p∨q, p∧q について「p∨q を p と q の選言、or 演算、論理和」「p∧q を p と q の連言、and 演算、論理積」という

  • 命題 p について、~p を p の否定、not p、論理否定などどいう

• 恒真命題と矛盾命題

  • 命題が、それを構成している命題の真偽に関わらず、常に真である時、恒真命題またはトートロジー(tautology)という

  • 常に偽である時、矛盾命題またはコントラディクション(contradiction)という

• 論理式

  • 命題変数 p, q, r, ... を論理記号で結びつけた P(p, q, r, ...) を論理式という

• 恒真命題 3 つ

  • 三段論法

    • [(p → r)∧(r → q)] → [p → q]

  • 対偶法

    • [(~q) → (~p)] → [p → q]

  • 背理法

    • [p∧(~q) = F] → [p → q]

2. 関係と写像

関係

• 直積集合

  • 2 つの集合 A, B に対して A × B = {(a, b) | a∈A, b∈B} を A と B の直積集合、または直積という

• 関係

  • 2 つの集合 A, B の直積集合 A × B の部分集合 R を A から B への関係という

  • 関係行列を使うと、関係を行列の式として表現できる（転置行列にすれば、逆行列を表現できる）

• 合成

  • 3 つの集合 A, B, C について、R を A から B への関係、S を B から C への関係とする。(a, b)∈R に対して (b, c)∈S の時、A × C の部分集合 {(a, c) | (a, b)∈R かつ (b, c)∈S} を関係 R と S の合成といい、R❍S と書く

• 逆関係

  • R を A から B への関係とする。この時 R^-1 = {(b, a) | (a, b)∈R} を R の逆関係という

• 集合 A 上の関係 R の特別な性質

  • 反射律

    • ∀x∈A に対して xRx が成立する時、反射律が成立するという

    • すべての要素にループが付いている場合

  • 対称律

    • x, y∈A, xRy ⇒ yRx が成立する時、対称律が成立するという

    • ループ以外の矢印がついている要素同士は必ず両向きの矢印がついている

  • 推移律

    • x, y, z∈A, xRy and yRz ⇒ xRz が成立する時、推移律が成立するという

    • 矢印 2 回たどって到達できる要素同士は必ず直接矢印がついている

  • 反対称律

    • x, y∈A, xRy and yRx ⇒ x = y が成立する時、反対称律が成立するという

    • ループ以外の矢印は必ず片方の方向しかない

• 同値類

  • 集合 A 上の関係 R が反射律・対称律・推移律を満たしている時、A 上の同値関係という。また、A の部分集合 Ca = {x | xRa , x∈A} を a の R による同値類という

  • 集合 A を R による同値類に完全に分けることができる

写像

• 写像

  • 集合 A の各要素に、それぞれ B の要素がただ 1 つ対応している関係を A から B への写像という

• 単射

  • A から B への写像を f とする。f(a1) = f(a2) ⇒ a1 = a2 が成り立っている時、f を単射または 1 対 1 (写像) という

  • 矢印が当たっている要素には矢印が 1 本しか当たっていない場合

• 全射

  • A から B への写像を f とする。∀b∈B, ∃a∈A, b = f(a) が成り立つ時、f を全射(写像) という

• 置換

  • 集合 {1, 2, ..., n} 上の全単射写像を n 次の置換という

3. 代数系

代数系

• 代数系

  • A に演算 * が定義されている時、集合 A と演算 * とを一緒に考えた系 (A ; *) を代数系という

  • 特に A が離散集合の時、(A ; *) を離散代数系という

• 交換律

  • a * b = b * a が成立する時、交換律が成立するという

• 結合律

  • a * (b * c) = (a * b) * c が成立する時、結合律が成立するという

• 単位元

  • A の任意の元 a に対して a * e = e * a = a が成立する A の元 e を (A ; *) の単位元という

• 逆元

  • (A ; *) が単位元 e を持つ時、A∋a に対して a * xa = xa * a = e となる xa が A に存在する時、xa を a の逆元と言い、a^-1 で表す

半群と群

• 半群

  • 代数系 (S ; *) の演算 * が結合律を満たす時、(S ; *) を半群という

• モノイド

  • 特に単位元を持つ半群をモノイドという

• 群

  • 代数系 (G ; *) が次の性質を満たす時、群という

    • 演算 * について結合律が成立する

    • 演算 * について単位元が存在する

    • G の全ての元に演算 * に関する逆元が存在する

環と体

• 環

  • 集合 R に 2 つの演算 + と × が定義され、次の性質を満たす時、(R ; +, ×) を環という

    • R1: (R ; +) は可換群(交換律を満たす群。a b = b a)である

    • R2: (R ; ×) は半群である

    • R3: 以下の分配律が成立する

      • a × (b + c) = a × b + a × c

      • (a + b) × c = a × c + b × c

• 体

  • 集合 F に 2 つの演算 + と × が定義され、次の性質を満たす時、代数系 (F ; +, ×) を体という

    • F1: (F ; +) は可換群である

    • F2: F* = F = {о} (F よりоを除いた集合) について (F* ; ×) は群である

    • F3: 以下の分配律が成立する

      • a × (b + C) = a × b + a × c

      • (a + b) × c = a × c + b × c

4. 順序集合と束

順序

• 半順序

  • 集合 A 上の関係 R が次の性質を満たす時、半順序(関係)という

    • 反射律

      • ∀a∈A に対して aRa

      • すべての元はループを持っている

    • 反対称律

      • aRb and bRa ⇒ a = b

      • ループ以外の矢印は必ず片方の方向しかない

    • 推移律

      • aRb and bRc ⇒ aRc

      • 矢印 2 回たどって到達できる要素同士は必ず直接矢印がついている

  • 集合 A に半順序 R が定義されている時、(A ; R) を半順序集合という

  • 半順序集合に属する 2 つの元には半順序の関係があってもなくてもよい。半順序の関係が付いている元同士を比較可能であるといい、付いていない元同士は比較不可能であるという

• 全順序

  • (A ; R) を半順序集合とする。A の任意の 2 つの元が比較可能な時、(A ; R) を全順序集合といい、R を全順序または線形順序という

• ハッセ図

  • 半順序集合 (A ; <=) の 2 つの元 a, b について、関係「<」と「<<」を以下のように定める

    • a < b ⇔ a <= b and a ≠ b

    • a << b ⇔ a < b かつ a < x < b となる x は A に存在しないと定める

  • (A ; <=) を有限な半順序集合とする。A∋a, b について a << b の時、点 b を点 a の上方に描き、a << b の関係にある A の点同士をすべて線で結んだ図を (A ; <=) のハッセ図という

• 最大元と最小元

  • (A ; <=) を半順序集合とする

  • ∀x∈A に対して x <= a が成立する A の元 a を A の最大元という

  • ∀x∈A に対して b <= x が成立する A の元 b を A の最小元という

• 極大元と極小元

  • 極大元、極小元は部分的に最大、最小となっている元

• 上界

  • (A ; <=) を半順序集合とし、M ⊆ A とする。a∈A が ∀x∈M に対して、x <= a を満たす時、a を M の上界という

  • M のすべての上界からなる集合に最小元が存在する時、それを M の上限と言い、sup M と書く

• 下界

  • (A ; <=) を半順序集合とし、M ⊆ A とする。b∈A が ∀x∈M に対して、b <= x を満たす時、b を M の下界という

  • M のすべての下界からなる集合に最大元が存在する時、それを M の下限と言い、inf M と書く

束とブール代数

• 束

  • 半順序集合 (A ; <=) において、A∋∀a, b に対して sup{a, b} と inf{a, b} が必ず存在する時、(A ; <=) を束という

    • (A ; <=) が全順序集合であれば、必ず束となる

• 束において sup{a, b} = a ∨ b, inf{a, b} = a ∧ b とする時、次の性質が成立する

  • ベキ等律

    • a ∨ a = a, a ∧ a = a

  • 対称律

    • a ∨ b = b ∨ a, a ∧ b = b ∧ a

  • 結合律

    • a ∨ (b ∨ c) = (a ∨ b) ∨ c

    • a ∧ (b ∧ c) = (a ∧ b) ∧ c

  • 吸収律

    • a ∨ (a ∧ b) = a, a ∧ (a ∨ b) = a

• ブール代数

  • 束 (A ; ∨, ∧) が以下の条件を満たす時、ブール束またはブール代数という

    • 分配律

      • a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)

      • a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

    • 最大・最小元の存在

      • 最大元 1、最小元 0 が存在する

    • 補元の存在

      • A∋∀a に対して a ∨ not a = 1 and a ∧ not a = 0 となる ∃not a∈A が存在する

5. グラフ

グラフ

• グラフ

  • 集合 V (≠φ) と V × V (非順序対で考える)の元と対応を持つ集合 E の組 (V, E) をグラフといい、V の要素を点または頂点、E の要素を辺という

• 端点・接続・隣接

  • 辺 e に対し、e = (P, Q) の時

    • P, Q は辺 e の端点であるという

    • P, Q は辺 e に接続するという

    • P と Q は隣接する

• 同型

  • 2 つのグラフ G と G' の頂点と辺の接続状態が全く同じである時、2 つのグラフは同型であるといい、G =~ G' と表す

• 次数

  • グラフ G の頂点 P について、P に接続する辺の数を点 P の次数といい、d(P) で表す

• 隣接行列・接続行列

  • G = (V, E) を頂点の数 P、辺の数 q のグラフとする

  • 次で定義される p × p 行列 A を G の隣接行列という

    • A = (aij)。aij = Pi と Pj を結ぶ辺の個数

  • 次で定義される p × q 行列 M を G の接続行列という

    • M = (mij)。mij = Pi が ej に接続する回数

• 経路

  • グラフ G の頂点と辺の交互に現れる有限な列 W = P0e1P1e2P2...enPn を経路または歩道(walk)という

• n-閉路

  • 始点と終点以外はすべて異なる頂点からなる閉じた小道を閉路(cycle)といい、長さ n の閉路を n-閉路という

• 連結

  • グラフ G の任意の 2 点 P, Q について P-Q 経路が存在する時、G は連結であるという。連結でない時、非連結という

• 切断点(分離点)・橋(分離辺)

  • G を単純連結グラフとし、2 個以上の頂点を持つという

  • G より点 P とそれに接続している辺をすべて取り除くとグラフが非連結になる時、P を G の切断点または分離点という

  • G より辺 e を取り除いたグラフが非連結となる時、e を G の橋または分離辺という

• 完全グラフ

  • どの 2 頂点も隣接している単純グラフを完全グラフという

• 正則グラフ

  • 各頂点の次数が等しいグラフを正則グラフという

• 2 部グラフ

  • G = (V, E) とし、E の要素である辺は V = V1 ∨ V2, V1 ∧ V2 = φ (V1 ≠ φ, V2 ≠ φ) となるような V の部分集合 V1 と V2 の頂点を結ぶようにできる時、G を 2 部グラフという

  • さらに V1 と V2 のすべての頂点が互いに結ばれている単純 2 部グラフを完全 2 部グラフといい、K(m, n) で表す(ただし、m = V1 の要素数、n = V2 の要素数とする)

• 木グラフ

  • 閉路を持たない連結グラフを木(tree)グラフという

  • n 個の頂点からなる連結グラフが木グラフであるための必要十分条件は n - 1 個の辺を持つことである

• 2 個以上の頂点を持つグラフ T について、について、次の命題は同値である

  • T は木グラフである

  • T の任意の 2 頂点に対し、それらを結ぶただ 1 つの道が存在する

  • T は連結であり、かつ T のどの辺を除いても連結ではなくなる

  • T は閉路を含まず、かつ辺をどのように 1 本加えても閉路を 1 つ持つグラフとなる

• 全域木

  • グラフ G の部分グラフ T が G のすべての頂点を含む木グラフである時、T を G の全域木という

• 根付き木

  • 特別な頂点が 1 つ定められている木グラフを根付き木といい、特別な頂点を根という

平面的グラフ

• 平面グラフ

  • 平面上に描かれたどの辺も交差していないグラフを平面グラフという。また平面グラフと同型なグラフを平面的であるという

• オイラーの公式

  • G を連結な平面グラフとする。G の頂点の数を p、辺の数を q、領域の数を r とする時、p - q + r = 2 が成立する。(ただし、p >= 1, q >= 0)

• 単純な連結平面グラフ G の頂点の個数を p(p >= 3)、辺の個数を q とする時、次の不等式が成立する

  • q <= 3p - 6

• オイラーグラフ

  • すべての辺を含む閉じた小道を持つ連結グラフをオイラーグラフという

  • すべての辺を含む小道を持つグラフを周遊可能なグラフという。これらの中で特に始点と終点が同じである閉じた周遊小道(オイラー小道)を持つグラフをオイラーグラフという

• ハミルトングラフ

  • 各点をちょうど 1 回だけ通る閉じた小道が存在するグラフをハミルトングラフという。またその小道をハミルトン閉路という

• 頂点彩色

  • 隣接するどの 2 点も異なる色になるようにグラフの頂点を色分けすることを頂点彩色という

  • グラフ G が n 色で頂点彩色できる時、n-頂点彩色可能といい、最小の頂点彩色数を xv(G) で表す

• 単純平面グラフ G が 2-頂点彩色可能なのは、2 部グラフの時に限る

• ループを持たない平面グラフはすべて 4-頂点彩色可能である

• 地図

  • 橋のない連結平面グラフを地図という

• k-領域彩色可能

  • 地図 G の隣接している 2 つの領域が同じ色にならないように k 色で領域を彩色できる時、G は k-領域彩色可能という

  • また最小の彩色数を xR(G) で表す

• 双対グラフ

  • 平面グラフ G より次のステップで構成されたグラフ G* を G の双対グラフという

    • Step1: G の各領域 ri (無限領域も含む)に点 Pi を取り、G の点とする

    • Step2: G の各辺 ei に対し、ei を境界に持つ 2 つの領域に取った点を ei と 1 点で交差するように結び ei とし、G の辺とする

• Welch-Powell の頂点彩色アルゴリズム

  • Step1: 頂点の次数を調べる

  • Step2: 次数の高い順に頂点を調べる

  • Step3: 第 1 色目を配色

  • Step4: 第 2, 3, ... を配色

有限オートマトン

• 初期状態と状態遷移

  • 外部からの入力により、次々と状態が変化するシステムを考える

  • 入力がある以前の状態を初期状態といい、入力により状態が変化することを状態遷移という

• 状態機械

  • 入力集合、状態集合および状態遷移関数が定義されているシステムを状態機械という

• 順序機械

  • 状態遷移時に出力が定義された状態機械を順序機械または出力付き有限オートマトンという

• 有限オートマトン

  • 入力に対して、受理状態または認識状態が定義された状態機械を有限オートマトンという