第1章 集合と論理
章間ナビゲーション
この章で使う記号
| 記号 | 意味 |
|---|---|
x ∈ A |
x が集合 A の要素である |
A ⊆ B |
A が B の部分集合である |
A ∪ B |
和集合 |
A ∩ B |
共通部分 |
∅ |
空集合 |
¬P |
命題 P の否定 |
P → Q |
P ならば Q |
∀x P(x) / ∃x P(x) |
全称量化 / 存在量化 |
この章で解消する詰まりどころ
理論計算機科学では、対象を「集合」として定義し、性質を「論理式」として書きます。最初に詰まりやすいのは、記号の意味ではなく、記号を日本語に戻せないことです。
この章では、次を扱います。
- 集合と要素
- 部分集合
- 集合演算
- 命題論理
- 述語論理
- 量化記号
- 含意と対偶
- 命題の否定
本体教科書のどこで使うか
- 第1章 数学的基礎
- 第3章 形式言語とオートマトン理論
- 第4章 計算可能性理論
- 第5章 計算複雑性理論
- 全章の定義・定理・証明
1. 集合
集合とは、対象を集めたものです。集合に含まれる対象を要素と呼びます。
A = {1, 2, 3}
このとき、1 ∈ A は真、4 ∈ A は偽です。
主要記号
| 記号 | 読み | 意味 |
|---|---|---|
x ∈ A |
x は A に属する | x は A の要素である |
x ∉ A |
x は A に属さない | x は A の要素ではない |
A ⊆ B |
A は B の部分集合 | A の全要素が B に含まれる |
A = B |
A と B は等しい | 同じ要素を持つ |
∅ |
空集合 | 要素を持たない集合 |
部分集合の定義
A ⊆ B とは、次の意味です。
任意の x について、x ∈ A ならば x ∈ B である。
量化記号で書くと、
∀x (x ∈ A → x ∈ B)
です。
2. 集合演算
| 演算 | 記号 | 定義 |
|---|---|---|
| 和集合 | A ∪ B |
A または B に属する要素の集合 |
| 共通部分 | A ∩ B |
A と B の両方に属する要素の集合 |
| 差集合 | A \ B |
A に属し、B には属さない要素の集合 |
| 補集合 | A^c |
全体集合のうち A に属さない要素の集合 |
| 冪集合 | P(A) |
A の部分集合すべての集合 |
例:
A = {1,2,3}
B = {2,3,4}
A ∪ B = {1,2,3,4}
A ∩ B = {2,3}
A \ B = {1}
3. 命題論理
命題とは、真または偽が決まる文です。
例:
2 は偶数である。 真
3 は偶数である。 偽
論理記号
| 記号 | 読み | 意味 |
|---|---|---|
¬P |
P でない | P の否定 |
P ∧ Q |
P かつ Q | 両方が真 |
P ∨ Q |
P または Q | 少なくとも一方が真 |
P → Q |
P ならば Q | P が真なら Q が真 |
P ↔ Q |
P と Q は同値 | P と Q の真偽が同じ |
4. 含意 P → Q
P → Q は、「P が真である場合には Q も真である」という主張です。
重要なのは、P が偽の場合、P → Q は真として扱われることです。これは計算機科学の定義や証明で頻繁に使われます。
| P | Q | P → Q |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 偽 | 偽 |
| 偽 | 真 | 真 |
| 偽 | 偽 | 真 |
逆・裏・対偶
命題 P → Q に対して、
| 種類 | 形 | 元の命題と同値か |
|---|---|---|
| 逆 | Q → P |
一般には同値でない |
| 裏 | ¬P → ¬Q |
一般には同値でない |
| 対偶 | ¬Q → ¬P |
常に同値 |
証明では、元の命題が直接示しにくいとき、対偶を証明します。
5. 述語と量化記号
述語とは、変数を含み、変数に値を入れると命題になる式です。
P(n): n は偶数である
P(2) は真、P(3) は偽です。
量化記号
| 記号 | 読み | 意味 |
|---|---|---|
∀x∈S, P(x) |
すべての x について | S の全要素で P が成り立つ |
∃x∈S, P(x) |
ある x が存在して | S の少なくとも1要素で P が成り立つ |
6. 量化記号の否定
最重要パターンです。
¬(∀x∈S, P(x)) ⇔ ∃x∈S, ¬P(x)
¬(∃x∈S, P(x)) ⇔ ∀x∈S, ¬P(x)
日本語にすると、
「すべてが P である」の否定は「P でないものが少なくとも1つある」
「P であるものが存在する」の否定は「すべてが P でない」
です。
7. 非例・誤解しやすい例
誤解1: 「または」は排他的である
数学・論理での P ∨ Q は、少なくとも一方が真という意味です。両方真でも真です。
誤解2: P → Q は因果関係を意味する
P → Q は論理的な真偽関係であり、時間的・因果的な関係を必ずしも意味しません。
誤解3: ∀ と ∃ の順序を入れ替えてよい
次の2つは一般に意味が違います。
∀x ∃y P(x,y)
∃y ∀x P(x,y)
前者は「各 x に対して何らかの y がある」。後者は「全ての x に同じ y が使える」です。
8. 接続問題
有限オートマトンの状態集合を Q、入力アルファベットを Σ とします。遷移関数は多くの場合、次のように書かれます。
δ: Q × Σ → Q
この記法を読むには、集合、直積、関数、定義域、値域が必要です。第2章で扱います。
演習
Level 1
x ∈ AとA ⊆ Bの意味を日本語で説明せよ。A={1,2,3},B={3,4,5}について、A∪B,A∩B,A\Bを求めよ。P → Qの対偶を書け。¬(∃x∈S, P(x))を量化記号を使って書き換えよ。
Level 2
A ⊆ BかつB ⊆ CならばA ⊆ Cを証明せよ。A = Bであることを示す標準手法を説明せよ。∀x∈S, P(x)→Q(x)の否定を書け。
Level 3
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)を要素追跡で証明せよ。A ⊆ BならばP(A) ⊆ P(B)を証明せよ。∀x ∃y P(x,y)と∃y ∀x P(x,y)が同値でない例を作れ。
自己診断
次を説明できれば、この章は通過です。
A ⊆ Bを量化記号で書ける。- 含意、逆、裏、対偶を区別できる。
- 量化記号の否定ができる。
- 集合等式を要素追跡で証明できる。