応用情報技術で学ぶ「集合と論理」

# 概要
応用情報技術者試験の出題範囲にある**集合と論理**を学習したのでアウトプットしていきます。

#集合論理
集合とは、ある条件を満たし、それ以外とは明確に区別できるものの集まりのこと。
ある1つの集合Uについて、それに属するものを**元(要素)**といい、要素が0である集合を**空集合**(<ruby>$\phi$<rt>ファイ<rt></ruby>)という。
![集合と空集合.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2361140/3e123bb7-36ab-279f-740b-b7b68f31f382.png "集合と空集合")

## 部分集合とべき集合
有限個の元からなる集合を**有限集合**、有限ではない集合を**無限集合**と呼ぶ。

:::note info
応用情報には出てこないですが、濃度という概念も面白そうです。
:::

また、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}

![真部分集合.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2361140/b795fe7e-4d79-46a8-19e1-4548e7f44d07.png "真部分集合")


## 差集合と対称差
集合AとBがあるとき、集合Aの元であり、集合Bの元でない集合を集合AとBの**差集合**といい、$A-B$で表します。
![差集合.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2361140/47373c2a-c2c9-d2e1-4950-b341a9cb3841.png "差集合")

また、集合Aの元であって集合Bの元でないか、又は、集合Bの元であってAの元でない集合を集合AとBの**対称差**といい、$ A \Delta B $と表す。
![対称差.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2361140/a2d5862f-f9a5-35e2-2f53-3aade5c54d70.png)

:::note info
対称差は、論理演算でいう排他的論理和に相当します。
:::

## 集合の要素数
集合Aの要素数はn(A)で表します、集合が有限集合であれば以下の公式でそれぞれの和集合の要素数を求めることが出来ます。

```math
n(A \cup B) = n(A) + n(B) - n(A \cap B)
```

![要素数.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2361140/fae1176f-1644-f43a-2b6c-51fd88804de7.png "要素数")

# 命題論理

## 命題
**命題**とは、ある１つの判断や主張を記号や文章で表したもので、それが正しい(真：True)か正しくない(偽：False)かがはっきり区別できるものをいう。
![命題(偽).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2361140/1d4335dc-a4f0-a683-7399-ab4fcedb3e39.png)

「3は素数である」は真の命題、「10は素数である」は偽の命題となる。

命題はp, qといった記号で表せます。

命題に変数を含み、その値によって真偽が決まる命題を**条件命題**又は**命題関数**といい、一般にp(x), q(x)と表す。

:::note info
変数がx, yと2つある場合、p(x, y)と表す。
:::

## 複合(合成)命題
複数の命題を「かつ」、「又は」などで結んでつくられる命題を**複合命題**あるいは**合成命題**と呼ぶ。

|  | 意味 | 論理記号 | 真理値 |
|:-:|:-:|:-:|:-:|
| 連言命題 <br> (合接命題) | pかつq | p$\land$q | 命題p, qがともに真のとき真、それ以外は偽 |
| 選言命題 <br> (合成命題)  | pまたはq | p$\lor$q | 命題p, qのどちらかが真のとき真、それ以外は偽 |
| 否定命題 | pでない | $\lnot$p | 命題pが真であれば偽、偽であれば真 |
| 条件文 <br> (含意命題) | pならばq | p$\to$q | 命題pが真で命題qが偽のとき偽、それ以外は真 |
| 双条件文 | pならばq <br> かつ <br> qならばp | p$\Leftrightarrow$q | 命題pとqの真理値が同じとき真、それ以外は偽 |

## 条件文(含意命題)
複合命題「pならばqである」という命題を**条件文**といい、「p$\to$q」と表す。"$\to$"は、「真$\to$偽」となるときに限り、偽となる演算で、これを**含意**という。

> 論理式の真理値は、それを構成するpやqといった論理式(これを原子理論式という)の真理値によって定まる。なお、原子論理式の真理値に係わらず常に真となる論理式を**トートロジー**といい、常に偽となる論理式を**矛盾式**という。

## 条件文の逆・裏・対偶
ある条件文「p$\to$q」に対しての逆・裏・対偶は以下のようになり、元の条件文と対偶は一致します。
![対偶.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2361140/491ea667-ff31-34cf-2dc2-97fb6855b78a.png "逆・裏・対偶")

# 論理演算
基本論理演算には、論理積演算(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 $ |

# 論理式の簡略化
## カルノー図を用いた簡略化
論理式を図的に表現したものがカルノー図です。
以下の論理式をカルノー図を用いて簡略化してみましょう。

```math
\overline{A}\cdot\overline{B}+\overline{A}\cdot\mathit{B}+A\cdot\overline{B}
```

カルノー図で表すと以下のようになります。
![カルノー図.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2361140/6a73178c-cb4c-82a0-3450-c6420b16beff.png "カルノー図")

以上から、$B$の真偽に関係なく$\overline{A}$であれば真なので、$\overline{A}$となり、$A$の真偽に関係なく$\overline{B}$であれば真なので、$\overline{B}$となる。このことから、$\overline{A}+\overline{B}$と簡略化できることになります。

# 終わりに
今回は、「集合と論理」について学びました、次は「情報理論と符号化」を学んでいこうと思います。