ブール代数が基本
コンピュータでは0と1だけを使った「二進数」を使います。
コンピュータが様々なことができるのは論理計算をしているからです。
コンピュータは電気のON、OFFを1と0にして使います。
ブール代数ではこの0と1を二進数の数字として扱うのではなく、「真(TRUE)：1」と「偽(FALSE)：0」の二値だけを扱うのがブール代数です。
具体的に見ていきましょう。通常の二進数として扱う場合、1+1=10となります。一方で、ブール代数では1+1=10ではありません。
ブール代数では1+1＝1となります。ブール代数では0と1のみで桁を繰上りません。そして「＋」の意味は加算ではなく「または」という意味になります。1 or 1→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
- NOT x, y, NOTz
- x, NOT y, NOT z
それぞれを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, オライリージャパン
