概要
応用情報技術者試験の出題範囲にある集合と論理を学習したのでアウトプットしていきます。
集合論理
集合とは、ある条件を満たし、それ以外とは明確に区別できるものの集まりのこと。
ある1つの集合Uについて、それに属するものを元(要素)といい、要素が0である集合を空集合($\phi$)という。
部分集合とべき集合
有限個の元からなる集合を有限集合、有限ではない集合を無限集合と呼ぶ。
応用情報には出てこないですが、濃度という概念も面白そうです。
また、1つの集合の中にいくつかの集合を考えることが出来ますが、それを部分集合と言います。
例えば、数1, 2, 3からなる集合Uの場合、その部分集合は空集合と集合U自身を合わせ$8=2^3$個あります。また、部分集合を集合の元とした集合をその集合のべき集合といいます。
集合U = {1 , 2, 3}
集合Uのべき集合 = {$\phi$, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
集合Aが集合Bの部分集合であり、AとBが一致しないとき、AをBの真部分集合という。
集合A = {1}
集合B = {1, 2, 3}
差集合と対称差
集合AとBがあるとき、集合Aの元であり、集合Bの元でない集合を集合AとBの差集合といい、$A-B$で表します。
また、集合Aの元であって集合Bの元でないか、又は、集合Bの元であってAの元でない集合を集合AとBの対称差といい、$ A \Delta B $と表す。
対称差は、論理演算でいう排他的論理和に相当します。
集合の要素数
集合Aの要素数はn(A)で表します、集合が有限集合であれば以下の公式でそれぞれの和集合の要素数を求めることが出来ます。
n(A \cup B) = n(A) + n(B) - n(A \cap B)
命題論理
命題
命題とは、ある１つの判断や主張を記号や文章で表したもので、それが正しい(真：True)か正しくない(偽：False)かがはっきり区別できるものをいう。
「3は素数である」は真の命題、「10は素数である」は偽の命題となる。
命題はp, qといった記号で表せます。
命題に変数を含み、その値によって真偽が決まる命題を条件命題又は命題関数といい、一般にp(x), q(x)と表す。
変数がx, yと2つある場合、p(x, y)と表す。
複合(合成)命題
複数の命題を「かつ」、「又は」などで結んでつくられる命題を複合命題あるいは合成命題と呼ぶ。
| 意味 | 論理記号 | 真理値 | |
|---|---|---|---|
| 連言命題 (合接命題) |
pかつq | p$\land$q | 命題p, qがともに真のとき真、それ以外は偽 |
| 選言命題 (合成命題) |
pまたはq | p$\lor$q | 命題p, qのどちらかが真のとき真、それ以外は偽 |
| 否定命題 | pでない | $\lnot$p | 命題pが真であれば偽、偽であれば真 |
| 条件文 (含意命題) |
pならばq | p$\to$q | 命題pが真で命題qが偽のとき偽、それ以外は真 |
| 双条件文 | pならばq かつ qならばp |
p$\Leftrightarrow$q | 命題pとqの真理値が同じとき真、それ以外は偽 |
条件文(含意命題)
複合命題「pならばqである」という命題を条件文といい、「p$\to$q」と表す。"$\to$"は、「真$\to$偽」となるときに限り、偽となる演算で、これを含意という。
論理式の真理値は、それを構成するpやqといった論理式(これを原子理論式という)の真理値によって定まる。なお、原子論理式の真理値に係わらず常に真となる論理式をトートロジーといい、常に偽となる論理式を矛盾式という。
条件文の逆・裏・対偶
ある条件文「p$\to$q」に対しての逆・裏・対偶は以下のようになり、元の条件文と対偶は一致します。
論理演算
基本論理演算には、論理積演算(AND演算)、論理和演算(OR演算)、否定演算(NOT演算)があり、この3つを組み合わせることにより、様々な論理回路を作ることが出来る。
論理演算と集合演算
論理演算で用いられる記号や演算の種類
▼演算記号
| 論理演算 | 集合演算 | |
|---|---|---|
| 論理積 | $\cdot$又は$\land$ | $\cap$ |
| 論理和 | $+$又は$\lor$ | $\cup$ |
| 否定 | $\overline{}$又は$\lnot$ | $\overline{}$又は$^c$ |
| 排他的論理和 | $\oplus$ | $\bigtriangleup$ |
▼演算則
| 論理演算 | 集合演算 | |
|---|---|---|
| べき等則 | $ A \cdot A = A$ | $ A \cap A = A $ |
| 〃 | $ A + A = A$ | $ A \cup A = A $ |
| 交換の法則 | $ A \cdot B = B \cdot A $ | $ A \cap B = B \cap A $ |
| 〃 | $ A + B = B + A $ | $ A \cup B = B \cup A $ |
| 結合の法則 | $ (A \cdot B) \cdot C = A \cdot (B \cdot C) $ | $ (A \cap B) \cap C = A \cap (B \cap C) $ |
| 〃 | $ (A + B) + C = A + (B + C)$ | $ (A \cup B) \cup C = A \cup (B \cup C) $ |
| 分配の法則 | $ A \cdot (B + C) = (A \cdot B) + (A \cdot C) $ | $ A \cap (B \cup C) = (A \cap B) + (A \cap C) $ |
| 〃 | $ A + (B \cdot C) = (A + B) \cdot (A + C) $ | $ A \cup (B \cap C) = (A \cup B) \cap (A \cup C) $ |
| 吸収の法則 | $ A + (A \cdot B ) = A $ | $ A \cup (A \cap B) = A $ |
| 〃 | $ A \cdot (A + B) = A $ | $ A \cap (A \cup B) = A $ |
| ド・モルガンの法則 | $ \overline{A \cdot B} = \overline{A} + \overline{B} $ | $ \overline{A \cap B} = \overline{A} \cup \overline{B} $ |
| 〃 | $ \overline{A + B} = \overline{A} \cdot \overline{B} $ | $ \overline{A \cup B} = \overline{A} \cap \overline{B} $ |
| その他 | $ A + \phi = A $ $ A \cdot \phi = A $ | $ A \cup \phi = A $ $ A \cap \phi = A $ |
| 〃 | $ A + 1 = A $ $ A \cdot 1 = A $ | $ A \cup 1 = A $ $ A \cap 1 = A $ |
| 〃 | $ A + \overline{A} = 1 $ $ A \cdot \overline{A} = \phi $ | $ A \cup \overline{A} = 1 $ $ A \cap \overline{A} = \phi $ |
論理式の簡略化
カルノー図を用いた簡略化
論理式を図的に表現したものがカルノー図です。
以下の論理式をカルノー図を用いて簡略化してみましょう。
\overline{A}\cdot\overline{B}+\overline{A}\cdot\mathit{B}+A\cdot\overline{B}
カルノー図で表すと以下のようになります。
以上から、$B$の真偽に関係なく$\overline{A}$であれば真なので、$\overline{A}$となり、$A$の真偽に関係なく$\overline{B}$であれば真なので、$\overline{B}$となる。このことから、$\overline{A}+\overline{B}$と簡略化できることになります。
終わりに
今回は、「集合と論理」について学びました、次は「情報理論と符号化」を学んでいこうと思います。