このページでは、集合の要素数の数え方、命題と逆・裏・対偶、ド・モルガンなどの論理演算の法則、カルノー図を使った論理式の簡略化がわかります。
-
記号の書き方(このメモのルール):
- 本来は上に線を引いて表す「否定」「補集合」は、論理なら ¬A、集合なら Aᶜ と書く
- 2乗などのべき乗は 2³、σ² のように書く。log の底は log₂ のように書く
-
一言で言うと:
- 「ものの集まり(集合)」と「正しいか正しくないか(命題)」を、記号と計算で扱う話。論理回路、SQLの条件、プログラムのif文の土台になる。
集まりを扱う(集合論理)→ 真偽を扱う(命題と論理)→ 計算のルール(論理演算)→ 式を短くする(論理式の簡略化)
覚え方の軸
- 集合と論理は同じものの言い換え:
- 積集合∩=論理積AND(・、∧)、和集合∪=論理和OR(+、∨)、補集合=否定NOT(¬)、対称差Δ=排他的論理和XOR(⊕)
- 数えるときは「足して、重なりを引く」:
- n(A∪B)=n(A)+n(B)−n(A∩B)
- 条件文p→qは「真→偽」のときだけ偽:
- 元の文と対偶は真偽が必ず一致する。逆と裏は一致するとは限らない
- 式を短くする方法は2つ:
- 演算則(特にド・モルガン)で変形する、またはカルノー図で「1」のかたまりをまとめる
集合論理:ものの集まりを記号で扱う
- 集合:
- ある条件を満たし、他のものとはっきり区別できるものの集まり
- 要素:
- 集合に属するもの。元(げん)ともいう
- 空集合:
- 要素数が0の集合。記号は ∅
- 有限集合:
- 要素が有限個の集合
- 無限集合:
- 要素が無限個の集合
- 部分集合:
- 1つの集合の中に考える、いくつかの要素の集まり
- 要素数がN個の集合の部分集合は、空集合と自分自身を含めて全部で 2ᴺ個
- 例:
- U={1,2,3}の部分集合は 2³=8個
- 真部分集合:
- AがBの部分集合で、AとBが一致しないとき、AをBの真部分集合という
- べき集合:
- 部分集合を全部集めて、それを要素にした集合
- 例:
- U={1,2,3}のべき集合={∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
- 差集合 A−B:
- Aの要素で、Bの要素ではないものの集合(AからBを取り除いた残り)
- A−B=A∩Bᶜ とも書ける(★過去問で問われた)
- 対称差 A△B:
- 「Aにあって Bにない」か「Bにあって Aにない」ものの集合(どちらか一方にだけあるもの)
- A△B=(A−B)∪(B−A)=(A∩Bᶜ)∪(Aᶜ∩B)
- 論理演算の排他的論理和にあたる
- 補集合の書き方:
- 集合Aの補集合は、上に線を引いて表すのが一般的だが、Aᶜ と書くこともある
- 集合の要素数 n(A):
- 集合Aの要素の数
- 和集合の要素数の公式(★)
- 2つの場合:
- n(A∪B)=n(A)+n(B)−n(A∩B)
- 3つの場合:
- n(A∪B∪C)=n(A)+n(B)+n(C)−n(A∩B)−n(B∩C)−n(C∩A)+n(A∩B∩C)
- イメージ:
- 全部足すと重なりを二重に数えてしまうので、その分を引く
- 2つの場合:
- 例:
- 50人のクラスで、犬を飼っている人が20人、猫を飼っている人が15人、どちらも飼っていない人が22人のとき、両方飼っている人は?
- n(A∪B)=50−22=28
- 28=20+15−n(A∩B) なので、n(A∩B)=7人
- 「どちらも飼っていない」=n(Aᶜ∩Bᶜ)=n((A∪B)ᶜ)。これはド・モルガンの法則
命題と論理:正しいか正しくないかを記号で扱う
- 命題:
- 1つの判断や主張を記号や文章で表したもので、真(True)か偽(False)かがはっきり決まるもの
- 例:
- 「今日は暑い」は人によって感じ方が違うので命題ではない。「7は奇数である」は真の命題、「9は素数である」は偽の命題
- ふつう p、q などの記号で表す
- 条件命題(命題関数):
- 変数xを含み、xの値によって真偽が決まる命題。p(x)、q(x)と書く(変数が2つならp(x,y))
- 例:
- 「xは偶数である」は、x=4なら真、x=3なら偽
- 複合命題(合成命題):
- 複数の命題を「かつ」「又は」などで結んだ命題
| 種類 | 意味 | 記号 | 真になるとき |
|---|---|---|---|
| 連言命題(合接命題) | pかつq | p∧q | 両方とも真のときだけ真 |
| 選言命題(隣接命題) | p又はq | p∨q | 少なくとも一方が真なら真(両方偽のときだけ偽) |
| 否定命題 | pでない | ¬p | pが偽なら真 |
| 条件文(含意命題) | pならばq | p→q | pが真でqが偽のときだけ偽、それ以外は真 |
| 双条件文 | pならばq、かつ、qならばp | p↔q(p≡q) | pとqの真偽が同じなら真 |
- 真理値表:
- 命題の真偽の組合せと、その結果を一覧にした表。真を1(T)、偽を0(F)で書く
- 真理集合:
- 命題が真になる範囲を、集合の図(ベン図)で表したもの
- 例:
- p:雨が降る、q:風が強い、とすると、「雨が降らず、風も強くない」は ¬p∧¬q(pもqも偽のときだけ真)
- 含意:
- 「真→偽」のときだけ結果が偽になる演算(→のこと)
- p→qの読みかえ:
- 「pであってqでない、ということはない」と考える
- p→q = ¬(p∧¬q)= ¬p∨q(ド・モルガンで展開)
- 前件と後件:
- 条件文p→qのpを前件、qを後件という
- 原子論理式:
- 論理式を組み立てている p や q のような、いちばん小さい論理式
- トートロジー:
- 原子論理式の真偽にかかわらず、常に真になる論理式(例:p∨¬p)
- 矛盾式:
- 常に偽になる論理式(例:p∧¬p)
- 逆・裏・対偶(★)
| 名前 | 形 | 元の文(p→q)と真偽が一致するか |
|---|---|---|
| 元の文 | p→q | − |
| 逆 | q→p | 一致するとは限らない |
| 裏 | ¬p→¬q | 一致するとは限らない |
| 対偶 | ¬q→¬p | 必ず一致する |
- 覚え方:
- 逆は入れかえ、裏は否定、対偶は入れかえて否定。逆と裏は、互いに対偶の関係なので、逆と裏どうしは真偽が一致する
- 例(推論問題):
- 前提:
- 毎日、電車かバスのどちらか一方で通勤する。電車のときは必ず本を読み、バスのときは必ず音楽を聴く
- 「電車→本を読む」の対偶は「本を読まない→電車ではない」。電車でなければバスなので、「本を読まない日はバスに乗っている」は正しい
- 「本を読む日は電車に乗っている」は逆なので、正しいとはいえない(バスで音楽を聴きながら本も読む日もありうる)
- 前提:
論理演算:計算のルール
- 基本論理演算:
- 論理積演算(AND)、論理和演算(OR)、否定演算(NOT)の3つ。この3つの基本論理回路を組み合わせれば、いろいろな論理回路を作れる
- 演算記号の対応(どちらの記号で出ても計算できるようにする)
| 演算 | 論理演算の記号 | 集合演算の記号 |
|---|---|---|
| 論理積 | ・ 又は ∧ | ∩ |
| 論理和 | + 又は ∨ | ∪ |
| 否定 | 上線 又は ¬ | 上線 又は ᶜ |
| 排他的論理和 | ⊕ | Δ(A△B=(A∩Bᶜ)∪(Aᶜ∩B)) |
- 排他的論理和(XOR)の真理値表:
| A | B | A⊕B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
- XORの使いみち:
- ビットの反転。反転したいビットだけ1にしたデータとXORをとる
- 例:
- 8ビットデータの下位4ビットを反転するには、0F(16進)=0000 1111 とXORをとる
- 0101 1100 ⊕ 0000 1111 = 0101 0011
- 演算則(論理演算と集合演算で同じ形になる)
- べき等則:
- A・A=A、A+A=A(集合:A∩A=A、A∪A=A)
- べき等:
- 同じ操作を何度繰り返しても同じ結果になること(例: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・(B+C)=(A・B)+(A・C)
- A+(B・C)=(A+B)・(A+C)(ふつうの数の計算では成り立たない形なので注意)
- 吸収の法則:
- A+(A・B)=A、A・(A+B)=A
- ド・モルガンの法則(★):
- ¬(A・B)=¬A+¬B、¬(A+B)=¬A・¬B
- 集合:(A∩B)ᶜ=Aᶜ∪Bᶜ、(A∪B)ᶜ=Aᶜ∩Bᶜ
- 覚え方:
- 否定を中に入れると、ANDとORが入れかわる
- その他:
- A+0=A、A・0=0、A+1=1、A・1=A、A+¬A=1、A・¬A=0
- 集合:A∪∅=A、A∩∅=∅、A∪U=U、A∩U=A、A∪Aᶜ=U、A∩Aᶜ=∅(∅:空集合、U:全体集合)
- べき等則:
論理式の簡略化:同じ意味のまま式を短くする
- 簡略化:
- 与えられた論理式と等価な(同じ結果になる)、より短い論理式を求めること
- 演算則を使う方法(例):
- A・B+A・¬B+¬A・B を簡略化する
- 手順:
- ①べき等則で A・B をもう1つ足す(足しても値は変わらない)
- ②A・B+A・¬B+¬A・B+A・B
- ③第1・2項をAでくくり、第3・4項をBでくくる:A・(B+¬B)+B・(¬A+A)
- ④B+¬B=1、¬A+A=1 なので:A+B
- カルノー図:
- 論理式を図(マス目)で表したもの
- 手順:
- ①論理式の各項にあたるマスに「1」、あたらないマスに「0」を入れる
- ②「1」が縦か横に連続しているマスをまとめる
- ③まとめた範囲で、真偽に関係なくなった変数を消す
- 上の例:
- A=1の行はBに関係なく1なので A、B=1の列はAに関係なく1なので B。合わせて A+B
- 変数が4つのカルノー図:
- 変数A,Bと変数C,Dに分けて、4行×4列の図で考える。行と列の並びは 00→01→11→10(隣どうしで1ビットだけ変わる順)
- 図の端どうし(例えば左端の列と右端の列)もつながっているとみなしてまとめられる
混同しやすいペア
- 差集合 A−B(Aだけにあるもの)/対称差 A△B(どちらか一方だけにあるもの)
- 部分集合(自分自身も含む)/真部分集合(自分自身とは一致しない)
- 部分集合(集まりの一部)/べき集合(部分集合を全部集めた集合。要素数は2ᴺ)
- 逆(q→p)/裏(¬p→¬q)/対偶(¬q→¬p。これだけ元と必ず同じ真偽)
- 連言(かつ、∧)/選言(又は、∨)
- 条件文 p→q(真→偽のときだけ偽)/双条件文 p↔q(真偽が同じときだけ真)
- トートロジー(常に真)/矛盾式(常に偽)
- 論理和 OR(両方1でも1)/排他的論理和 XOR(両方1なら0)