ブール代数が基本
コンピュータでは0と1だけを使った「二進数」を使います。
電気のOFFとONを0と1として取り扱っています。
たった2つの文字だけで様々なことができるのは論理計算をしているからです。
ブール代数は0と1をTRUEとFALSEで扱う
0と1を二進数の数字ではなく「真(TRUE)：1」と「偽(FALSE)：0」の二値として扱うブール代数という数学の分野があります。
このブール代数は論理計算の基礎です。
それでは計算例を具体的に見ていきましょう。
通常の二進数として扱う場合、
1+1=10
となります。
一方で、ブール代数では1+1=10ではありません。
なぜなら、ブール代数は0と1だけで表現するからです。
10のように二桁になることはありません。
ブール代数では1+1＝1となります。
ブール代数と足し算引き算との違う点
ブール代数は普通の数字の足し引きではありません。
以下のような違いがあります。
- ブール代数では0と1のみで桁を繰上らない
- 「＋」は足し算ではなく「または」という意味 1 or 1→1です。
これだけ聞いても一体何に使えるのかよく分からないですよね？
まずはブール代数の基本を理解しましょう。
ブール式の基本
ブール式では2つの(0,1), (0,1)
ブール代数は入力→出力という形式の関数、ブール関数はブール式で表現されます。
基本のブール式は
- 「・」AND, かつ
- 「＋」OR, または
- 「x̄」 NOT, 否定
の三種類があります。
例えば、入力→出力のブール関数の例として
入力 x=1, y=0の時、出力はどうなるでしょうか？
これは、ブール式の記述によって変化します。
- x OR y（x または y, x + y）の時は出力は1です。
- x AND y（x かつ y, x + y）の時は出力は0です。
- NOT x の時は出力は0です。
ブール式の基本AND, OR, NOTですべての論理式を表現できる
ANDはx=1, y=1の時のみ1になります。ORはx=0, y=0の時のみ0です。NOTxはx=1の時のみx=0になります。
この３つのブール式があればすべてのブール関数を表現できます。
なんでそうなるのか？ということはとりあえず考えず、そういう決まりであると思ってください。真理値表という入力と出力の組み合わせを確認すると仕組みが分かると思います。
ブール式の基本であるAND、OR、NOTはちゃんと電子回路で表現できます。詳しくは以下の記事をご覧ください。
AND回路とは？
OR回路とは？
NOT回路とは？電子回路で作る方法
真理値表とは？
真理値表とはブール代数において入力に対してすべての出力結果を表にしたものです。
例えばx(0, 1)とy(0, 1)の入力に対して作れる組み合わせは22＝4通りになります。
したがって、x AND yの真理値表は
| x | y | 出力( x AND y) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
となります。真理値表は二進数の小さい順に並べます(000, 001, 010,011, 100…)
x OR yの真理値表は
| x | y | 出力( x OR y) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
このようにブール関数のすべての出力値に対して表現するのが真理値表です。
入力がx, y, zの時は23=8通り(n個の入力に対して出力は2n個）
したがって、x AND yの真理値表は
| x | y | 出力( x AND y) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
命題から真理値表を作成する
先ほどはブール関数 x AND yなどから真理値表を作成しましたが、次は視点を変えて命題から真理値表を作成してみましょう。
3値の場合は2*2*2=8通りなので
| x | y | z | 出力 |
| 0 | 0 | 0 | |
| 0 | 0 | 1 | |
| 0 | 1 | 0 | |
| 0 | 1 | 1 | |
| 1 | 0 | 0 | |
| 1 | 0 | 1 | |
| 1 | 1 | 0 | |
| 1 | 1 | 1 |
の真理値表ができます。
命題：入力の一つが真ならば、出力が真という真理値表を作成してみましょう。
命題に従って一つだけ「1」のものに「1」を入れるだけです。
| x | y | z | 出力 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
の真理値表ができます。簡単ですね。
出力が1になっているものは３つあります。
命題は他にも3値が真の時のみ真などたくさんのパターンが作れます。
真理値表からブール式を導き出す方法
先ほどは命題から真理値表を作成しましたが、次は真理値表からブール式を導き出す方法を紹介します。
どんな真理値表からも少なくとも一つのブール式を導き出すことができます。
真理値表からブール式を導き出すには出力が1のところのみに着目します。
先ほどの真理値表からブール式を導き出してみましょう。
| x | y | z | 出力 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
1が出力されているものは上から３つあります。
- NOT x, NOT y, z (0, 0, 1)
- NOT x, y, NOTz (0, 1, 0)
- x, NOT y, NOT z (1, 0, 0)
正準表現
正準表現の作り方は上で出てきた項目をそれぞれAND(・)で結合して作ります。
そうしてできた３つの項をOR(+)でつなぎます
(NOT x・ NOT y・ z)+(NOT x・y・NOT z)+(x・NOT y・NOT z)。
f (x, y, z)=(NOT x・ NOT y・ z)+(NOT x・y・NOT z)+(x・NOT y・NOT z)が真理値表から導き出したブール関数です。
このような表記を正準表現といいます。
このように真理値表の出力が1の項のみを抽出し、各項をANDでつないでできたそれぞれの項をORでつなぐことによって真理値表からブール式を導くことができます。
導き出したブール式をよく見ると使われているブール式はANDとORとNOTだけです。やはりAND、OR、NOT３つがあれば複雑なものであっても表現することができるというのが分かります。
2変数のブール関数一覧
入力値xとyの取りうる値に対する出力値を真理値表として表した時のブール関数の名称を全て挙げてみます。
| ブール関数 | x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 | |
| Constant 0 | 0 | 0 | 0 | 0 | 0 |
| And | x・y | 0 | 0 | 0 | 1 |
| x And Not y | x・Not y | 0 | 0 | 1 | 0 |
| x | x | 0 | 0 | 1 | 1 |
| Not x And y | Not x・y | 0 | 1 | 0 | 0 |
| y | y | 0 | 1 | 0 | 1 |
| Xor | x・Not y + Not x・y | 0 | 1 | 1 | 0 |
| Or | x + y | 0 | 1 | 1 | 1 |
| Nor | Not (x+y) | 1 | 0 | 0 | 0 |
| Equivalence | x・y + Not x・Not y | 1 | 0 | 0 | 1 |
| Not y | Not y | 1 | 0 | 1 | 0 |
| If y then x | x+Not y | 1 | 0 | 1 | 1 |
| Not x | Not x | 1 | 1 | 0 | 0 |
| If x then y | Not x + y | 1 | 1 | 0 | 1 |
| Nand | Not(x・y) | 1 | 1 | 1 | 0 |
| Constant 1 | 1 | 1 | 1 | 1 | 1 |
参考
参考 【入門】ブール代数まとめ【スッキリ見やすい】 | Golden-DatabaseGolden-Database 参考 Part4 ブール代数を理解する | 日経クロステック（xTECH）日経クロステック（xTECH）書籍：コンピュータシステムの理論と実装: モダンなコンピュータの作り方, 2015, オライリージャパン
