集合・命題・論理演算
集合の基本用語から命題の真偽、逆・裏・対偶、論理演算の法則とカルノー図まで、具体例と表で解説する。
VIDEO
この内容を動画でも確認できます
集合
集合とは、条件を満たすものを集めたものである。例えば、1から10までの整数のうち、素数を集めると A = {2, 3, 5, 7}、3の倍数を集めると B = {3, 6, 9} という集合になる。
ベン図と要素
ベン図は、集合同士の関係を視覚的に表した図である。円の内側は、その集合に含まれるものを表す。
集合に含まれるもの一つひとつを要素と呼ぶ。Aの要素は2、3、5、7の4つである。3は素数であり、3の倍数でもあるため、二つの円が重なる部分に置く。
空集合と部分集合
要素が一つもない集合を空集合と呼び、∅ や {} で表す。
ある集合の要素だけで作られた集合を、その集合の部分集合と呼ぶ。例えば、{2, 5} はAの部分集合である。Aに含まれる要素であれば、どの組合せを選んでも部分集合になる。
要素を一つも選ばない空集合も、Aの要素を全て選んだA自身も、Aの部分集合である。
共通部分・和集合・補集合
集合の記号では、「かつ」に対応する ∩、「または」に対応する ∪、そして「含まれない」を表す補集合が登場する。
ここでは、考える範囲全体を U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} とする。補集合は、このUの中で考える。
| 関係 | 記号 | 意味・例 |
|---|---|---|
| 共通部分 | A ∩ B | 両方に含まれる要素。{3} |
| 和集合 | A ∪ B | 少なくとも一方に含まれる要素。{2, 3, 5, 6, 7, 9} |
| Bの補集合 | Bᶜ | Uの中でBに含まれない要素。{1, 2, 4, 5, 7, 8, 10} |
補集合は、集合の記号の上に棒を付けて表すこともある。
差集合
Aから、Bにも含まれる要素を全て除いた集合を差集合と呼ぶ。A − B と書き、A ∩ Bᶜ とも表せる。
ベン図では、Aの円のうち、Bと重なっていない部分に当たる。Aの要素から3を除くので、A − B = {2, 5, 7} となる。
A ∩ Bᶜ は、「Aに含まれる、かつBには含まれない」という意味である。
対称差
AとBのどちらか一方だけに含まれる要素を集めた集合を対称差と呼び、A △ B と表す。両方に含まれる要素は除く。
この例では、両方に含まれる3を除き、A △ B = {2, 5, 6, 7, 9} となる。差集合を使うと、(A − B) ∪ (B − A) と表せる。
要素数・有限集合・無限集合
集合Aの要素数は n(A) と表すことがある。この例では n(A) = 4、n(B) = 3 である。
要素数が有限である集合を有限集合と呼ぶ。例えば、12の正の約数の集合 {1, 2, 3, 4, 6, 12} は、要素数が6の有限集合である。
要素が限りなく存在する集合を無限集合と呼ぶ。例えば、正の偶数の集合 {2, 4, 6, 8, …} は、どこまで進んでも要素が続くため、無限集合である。「順番に並べられない」という意味ではなく、要素数を有限の数で表せないという意味である。
冪集合
ある集合の部分集合を全て集めたものを冪集合（べき集合）と呼ぶ。冪集合の要素は、数などではなく「集合」になっている。
例えば、6の正の約数の集合を D = {1, 2, 3, 6} とすると、その冪集合は次の16個の部分集合からなる。
要素が0個：∅
要素が1個：{1}, {2}, {3}, {6}
要素が2個：{1, 2}, {1, 3}, {1, 6}, {2, 3}, {2, 6}, {3, 6}
要素が3個：{1, 2, 3}, {1, 2, 6}, {1, 3, 6}, {2, 3, 6}
要素が4個：{1, 2, 3, 6}
空集合もD自身も部分集合なので、冪集合に含まれる。
命題
命題とは、真か偽かが定まる文である。「5は素数である」は真、「10は奇数である」は偽なので、どちらも命題である。
一方、「5は素敵な数である」は人の主観に左右される。真偽を定める基準がないため、命題として扱わない。
変数を含む文
「xは10以上の整数である」のような文は、xの値が決まるまでは真偽を定められない。このような文を命題関数と呼ぶ。xに12を入れれば真、3を入れれば偽というように、値が決まると命題になる。
変数を含むことと、「ならば」で結ばれた条件文であることは別の話である。
複合命題
複数の命題を組み合わせたものを複合命題と呼ぶ。
例えば、「5は素数である」と「10は奇数である」を「かつ」でつなぐと、「5は素数であり、かつ10は奇数である」となる。「かつ」は両方が真のときだけ真なので、この複合命題は偽になる。
| 名称 | 記号 | 読み方 |
|---|---|---|
| 連言 | P ∧ Q | PかつQ |
| 選言 | P ∨ Q | PまたはQ（両方が真でもよい） |
| 否定 | ¬P | Pではない |
| 条件文 | P → Q | PならばQ |
| 双条件文 | P ↔ Q | PならばQ、かつQならばP |
条件文：PならばQ
「xが10以上の整数ならば、xは5以上の整数である」は、整数xについて成り立つ。前提を満たす整数は、結論も満たしている。
条件文 P → Q は、Pが真でQが偽のときだけ偽になる。それ以外は真である。
| P | Q | P → Q |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 偽 | 偽 |
| 偽 | 真 | 真 |
| 偽 | 偽 | 真 |
結論Qが偽でも、前提Pも偽であれば条件文全体は真になる。例えば、「10は奇数であるならば、5は2より小さい」は、前提も結論も偽なので、論理学の条件文としては真である。
日常会話の「ならば」では、前後に因果関係を期待することがある。しかし、ここで扱う条件文の真偽は、上の表で決まる。
双条件文：双方の「ならば」
双条件文 P ↔ Q は、P → Q と Q → P の両方が真であることを表す。
例えば、「10は偶数であるならば、10は2で割り切れる」は真で、その逆向きの「10は2で割り切れるならば、10は偶数である」も真である。そのため、この二つの命題の双条件文は真になる。
双条件文は、PとQが両方とも真、または両方とも偽のときに真になる。
| P | Q | P ↔ Q |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 偽 | 偽 |
| 偽 | 真 | 偽 |
| 偽 | 偽 | 真 |
逆・裏・対偶
P → Q に対して、前後の入れ替えや否定によって、逆・裏・対偶が定まる。
| 名称 | 式 | 読み方 |
|---|---|---|
| 元の命題 | P → Q | PならばQ |
| 逆 | Q → P | QならばP |
| 裏 | ¬P → ¬Q | PでないならばQでない |
| 対偶 | ¬Q → ¬P | QでないならばPでない |
自然数xについて、「xが4で割り切れるならば、xは偶数である」を例に考える。
- 元の命題は真である。4の倍数は全て偶数になる。
- 逆「xが偶数ならば、xは4で割り切れる」は偽である。6は偶数だが、4で割り切れない。
- 裏「xが4で割り切れないならば、xは偶数ではない」も偽である。6が反例になる。
- 対偶「xが偶数でないならば、xは4で割り切れない」は真である。
逆や裏が、必ず元の命題と反対の真偽になるわけではない。対偶は常に元の命題と真偽が一致する。
論理演算
集合や命題で登場した「かつ」「または」「でない」は、論理演算では演算子として扱う。真を1、偽を0とすると、式を使って真偽を計算できる。
論理積・論理和・否定・排他的論理和
- 論理積（AND）：両方が1のときだけ1。
A · BやA ∧ Bと表す。 - 論理和（OR）：少なくとも一方が1なら1。
A + BやA ∨ Bと表す。 - 否定（NOT）：0と1を入れ替える。
¬Aと表すほか、Aの上に棒を付けることもある。 - 排他的論理和（XOR）：どちらか一方だけが1のとき1。
A ⊕ Bと表す。
集合の対称差に対応するのが、排他的論理和である。両方が1なら、論理和は1になるが、排他的論理和は0になる。
以下では、+ を論理和、· を論理積、¬ を否定として使う。
| A | B | A · B | A + B | A ⊕ B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
否定は ¬0 = 1、¬1 = 0 である。
論理積は 0 · 1 = 0、論理和は 0 + 1 = 1 となるので、普通の掛け算や足し算に似ている。ただし、論理和では 1 + 1 = 1 である。否定も普通の引き算や負の符号ではないため、数の計算と区別する。
論理演算の法則
論理式は、法則を使って変形できる。以下の式は、A・B・Cに0と1のどの組合せを入れても成り立つ。
交換則
A + B = B + A
A · B = B · A
結合則
(A + B) + C = A + (B + C)
(A · B) · C = A · (B · C)
分配則
A · (B + C) = A · B + A · C
A + (B · C) = (A + B) · (A + C)
べき等則
A + A = A
A · A = A
補元の関係
A + ¬A = 1
A · ¬A = 0
0・1との演算
A + 0 = A
A · 1 = A
ド・モルガンの定理
¬(A · B) = ¬A + ¬B
¬(A + B) = ¬A · ¬B
ド・モルガンの定理では、式全体を否定すると、論理積と論理和が入れ替わり、それぞれの項も否定される。
例えば、「AかつBではない」は、「Aでない、またはBでない」と同じ真偽になる。
法則を使って式を簡単にする
式変形の例として、次の式を考える。
F = ¬A · B + A · ¬B + A · B
これは「Bだけが1」「Aだけが1」「両方が1」のいずれかで1になる式である。実は、A + B と同じ結果になる。
まず、最後の A · B を二つに増やす。べき等則により、同じ項の論理和を足しても結果は変わらない。
F = ¬A · B + A · ¬B + A · B + A · B
項を並べ替え、二つずつまとめる。
F = (¬A · B + A · B) + (A · ¬B + A · B)
分配則を逆向きに使い、前半はB、後半はAでくくる。
F = (¬A + A) · B + A · (¬B + B)
¬A + A = 1、¬B + B = 1 なので、次のように変形できる。
F = 1 · B + A · 1
= B + A
= A + B
結果を変えない項を加えて、くくりやすい形にすることがポイントである。式を簡単にすると、論理回路などの構成を簡単にすることにもつながる。
カルノー図で同じ式を簡単にする
式変形のために加える項を思いつきにくいときは、カルノー図を使う方法がある。入力の組合せごとに式の値を調べ、隣り合うマスをまとめて式を簡単にする。
先ほどの式 F = ¬A · B + A · ¬B + A · B に、AとBの全ての組合せを代入する。
A = 0、B = 0：1 · 0 + 0 · 1 + 0 · 0 = 0
A = 0、B = 1：1 · 1 + 0 · 0 + 0 · 1 = 1
A = 1、B = 0：0 · 0 + 1 · 1 + 1 · 0 = 1
A = 1、B = 1：0 · 1 + 1 · 0 + 1 · 1 = 1
行をA、列をBとして並べると、次のカルノー図になる。
| A ＼ B | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
1が隣り合っている部分に注目する。
- 下の行の2マスをまとめる。Bは0と1で変わるが、Aは1で共通している。このまとまりはAで表せる。
- 右の列の2マスをまとめる。Aは0と1で変わるが、Bは1で共通している。このまとまりはBで表せる。
- 二つのまとまりの論理和を取ると、
F = A + Bになる。
右下の1は両方のまとまりに含まれているが、重複して使ってよい。全ての1を覆うようにまとめる。
共通する入力の値が1ならその変数を、0ならその変数の否定を採用する。例えば、Bが1、Cが0で共通しているまとまりは、B · ¬C で表せる。
3変数の場合
3変数では、二つの変数を組にして列を作る。例えば、行をC、列をABとすると、列は 00 → 01 → 11 → 10 の順に並べる。隣り合う列で、変わる入力が一つだけになるようにするためである。
例として F = B · ¬C のカルノー図は次のようになる。
| C ＼ AB | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
上の行の AB = 01 と AB = 11 の2マスをまとめる。Aは変わるが、Bは1、Cは0で共通しているため、B · ¬C が得られる。
まとめるマス数は1・2・4・8などの2の累乗とし、長方形のまとまりを作る。0を含めず、できるだけ大きくまとめる。左右の端同士や上下の端同士も隣接すると考える。