基礎理論～集合と論理～
論理演算
今回は集合と論理です。
集合って高校の時習いましたね、数Aでした。
プログラマはできて当然？
実はエンジニアでプログラムをごりごり書いてる方は無意識に得意になっているはずです。
条件分岐の if で書いているからです。
では改めて今回はそんなifの中身である 集合と論理 に触れていきましょう。
論理演算
論理演算 (別名 ブール演算 )は、 0 or 1、 YES or No など、二値の判定をする計算です。
ブール と聞いて、扱う言語によってはピンと来る方もいるかと思います。Boolean または bool のことです。わからない方はプログラムを書いていくと学べます。
さて、 論理演算 って難しいワードを出されると「ふええ」ってなるかもしれませんが、前述したとおり結局は「二値の判定」です。どんな難しい計算も、砕いて砕いて砕けばこの「YES or NO」の二値に収束します。
論理和
A または B のとき 「YES」 となるお話です。
例えば、「晴れまたは曇のときに洗濯物を干す」という日常生活の話を、論理演算チックに書くと
「晴れ」または「曇り」ならば「洗濯物を干す」というふうになります。
この「または」を OR と表します。
論理積
A かつ B のとき「YES」 となるお話。
例えば、「15時以降に洗濯物が乾いていたら取り込む」という日常生活を論理演算チックに書くと…
「15時以降」かつ「洗濯物が乾いている」ならば「取り込む」という条件を示します。
論理積と論理和
これが、プログラムになると
YesはTrueや1と訳されて、NoはFalseや0と訳されます。表現が難しいだけですね。
大事なのは、 条件となるもの両方がYESかNOかで結果が変わる ことを理解すること。
この2点をあえて少し難しくまとめますね。
| x | y | 論理和 | 論理積 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 |
数値で表されていますが、1を「YES」、0を「NO」と読み替えてください。
論理積が1すなわち「YES」となっているのは事象X、事象Yともに1すなわち「YES」となっている場合のみなのです。
論理和は、事象X、事象Yのどちらかが「YES」ならば答えも「YES」となっています。
論理積と論理和以外
排他的論理和
論理積が「AND」、論理和が「OR」表された次、 排他的論理和 です。記号は XOR または EOR です。
これは日常生活に言い換えることは難しく、唯一つ 事象X と 事象Y の答えが同一ならば0 という論理演算なんです。
否定論理積
論理積の逆ですね。 NOT AND の略で NAND と表されます。
否定論理和
論理和の逆です。 NOT OR の略で NOR と表されます。
論理演算まとめの表
| x | y | 論理和 | 論理積 | 排他的論理和 | 否定論理和 | 否定論理積 |
|---|---|---|---|---|---|---|
| X | Y | OR | AND | XOR | NOR | NAND |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
ド・モルガンの法則
懐かしい方もいらしゃいませんか？
AND の否定 = OR ( =NAND)
OR の否定 = AND ( =NOR)
と、入れ替わることを把握しておこう。
カルノー図
カルノー図は 論理式、論理演算を簡略化するために用いる表 です。カルノー図はAPよりFEが出題率高めです。
ですが、私は勉強していた当初はちんぷんかんぷんでした。
| AB\CD | 00 | 01 | 10 | 11 |
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 1 | 1 | 0 |
| 10 | 0 | 1 | 1 | 0 |
| 11 | 1 | 0 | 0 | 1 |
論理演算の01の関係性が理解できている前提ではありますが、このカルノー図から論理式を導出する問題が頻出です。
表の見方
一番左の列は、 ABの組み合わせ 、一番上の行が CDの組み合わせ です。
ABが00の行とCDが00の列が1であることが見て取れます。
| AB\CD | 00 | 01 | 10 | 11 |
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 1 | 1 | 0 |
| 10 | 0 | 1 | 1 | 0 |
| 11 | 1 | 0 | 0 | 1 |
導出方法
※ 否定を ¬ 記号で表します。
※ 論理積を AND でなく 「・」で表します。
※ 論理和を OR でなく 「＋」で表します。
結果が「１」となる行列を抽出します。
例)A = 0, B = 0, C = 0, D = 0 の場合1 => ¬A ･ ¬B ･ ¬C ･ ¬D = 1
すると、
- ¬A ･ ¬B ･ ¬C ･ ¬D
- ¬A ･ ¬B ･ C ･ ¬D
- ¬A ･ B ･ ¬C ･ D
- ¬A ･ B ･ C ･ D
- A ･ B ･ ¬C ･ D
- A ･ B ･ C ･ D
の6通りが挙げられます。
次に、その中で1が隣り合うものを同じグループとして、グループ分けを行います。
グループA
- ¬A ･ ¬B ･ ¬C ･ ¬D
- ¬A ･ ¬B ･ C ･ ¬D
グループB
- ¬A ･ B ･ ¬C ･ D
- ¬A ･ B ･ C ･ D
- A ･ B ･ ¬C ･ D
- A ･ B ･ C ･ D
このグループA と グループBの論理和が答えです。グループ内の論理式は論理積です。
グループA
- ¬A ･ ¬B ･ ¬C ･ ¬D
- ¬A ･ ¬B ･ C ･ ¬D
の論理積（共通項）なので
- ¬A ･ ¬B ･ ¬D
グループB
- ¬A ･ B ･ ¬C ･ D
- ¬A ･ B ･ C ･ D
- A ･ B ･ ¬C ･ D
- A ･ B ･ C ･ D
の論理積（共通項）なので
- B ･ D
となります。
最後に、グループAとグループBの論理和なので、 ¬A ･ ¬B ･ ¬D + B ･ D が答えになります。
基本情報を受ける方はこのカルノー図は抑えたいところです。
