
・実はブール代数って何かすらあまりわかってない
・論理式の簡単化って何が何だかわからない
この記事では、このようにブール代数を少し聞いたことがあるレベルの人向けに、応用情報技術者の筆者がブール代数の簡単化について丁寧に解説します。
※ブール代数の証明問題の解き方は、下記の記事がより参考になります。

ブール代数の基礎
一応、ほぼ初学者の人のために、記号の意味や変換規則等を解説します。 既にある程度の理解がある方は、読み飛ばしても問題ありません。
ブール代数における記号の意味
ブール代数において、1と0はそれぞれ、“真” と “偽” を意味します。真・偽というのは、正しい・正しくないという意味です。
そして、+は足すではなく、”または” を意味する記号です。
・は掛けるではなく、”かつ” を意味する記号です。
より詳しい解説が必要な場合は、以下の記事を参考にしてください。
重要な変換法則
簡単化には、変換法則というものを用いる必要があります。 そこで、重要な5つの変換法則を確認しておきましょう。
ド・モルガンの法則
- $\overline{A+B}=\overline{A}\cdot \overline{B}$
- $\overline{A\cdot B}=\overline{A}+ \overline{B}$
恒等則
- $A + 1 = 1$
- $A \cdot 1 = A$
- $A + 0 = A$
- $A \cdot 0 = 0$
同一則
- $A \cdot A = A$
- $A + A = A$
補元則
- $A \cdot \overline{A} = 0$
- $A + \overline{A} = 1$
吸収則
- $A+A \cdot B = A$
- $A\cdot (A + B) = A$
おまけ:その他数学と一緒の法則
交換則 $A+B=B+A$ , $A \cdot B = B \cdot A $
結合則 $A+(B+C)=(A+B)+C$ , $A\cdot (B\cdot C)=(A\cdot B)\cdot C$
分配則 $A(B+C)=AB+AC$
なお、公式は双対定理を理解していれば、覚える量が半分になりますので、知らない方は一度確認しておくことをお勧めします。
論理式の簡単化について
では、いよいよ論理式の簡単化について解説していきます。実は論理式には簡単化の基本パターンが存在するため、まずはそれを理解し覚えます。これがコツです。しかし、簡単化のパターンは複雑な論理式の中に隠れて存在しています。ゆえに、練習問題を通して基本パターンの適用を練習していきます。
簡単化の基本パターン
簡単化の基本パターンは3つ+吸収則(わかりにくい法則のため追加)です。では、順に紹介します。
基本パターン1:
$AB+A\overline{B}=A$
[証明] $AB+A\overline{B}=A(B+\overline{B})=A(1)=A$
基本パターン2:
$A(\overline{A}+B)=AB$
$A+\overline{A}B=A+B$
[証明] $A+\overline{A}B=A+B$
$=A(\overline{B}+B)+\overline{A}B$
$=A\overline{B}+AB+\overline{A}B$
$=A\overline{B}+AB+\overline{A}B+AB$
$=A(\overline{B}+B)+B(\overline{A}+A)$
$=A+B$
基本パターン3:
$AB + \overline{A}C + BC = AB +\overline{A}C$
$(A+B)(\overline{A}+C)(B+C)=(A+B)(\overline{A}+C)$
[証明] $AB + \overline{A}C + BC$
$=AB + \overline{A}C + BC(A+\overline{A})$
$=AB + \overline{A}C + BCA+BC\overline{A}$
$=AB(1+C) + \overline{A}C(1+B)$
$=AB +\overline{A}C$
[証明] $(A+B)(\overline{A}+C)(B+C)$
$=(A+B)(\overline{A}+C)(B+C+A)(B+C+\overline{A})$
$=(A+B)(B+C+A)\cdot (\overline{A}+C)(B+C+\overline{A})$
$=(A+B)(1+C)\cdot (\overline{A}+C)(1+B)$
$=A(A+B)(\overline{A}+C)$

保存・印刷用画像です。
練習問題
それでは、練習問題を通して、基本パターンの適用に慣れていきましょう。
$Q1$ : $(A+B)(A+C)$
$A1$ : $(A+B)(A+C)$
$ =A+AB+AC+BC$
$ =A+BC$ (吸収則)
$Q2$ : $AB+\overline{A}BD+BC$
$A2$ : $AB+\overline{A}BD+BC$
$=B(A+\overline{A}D+C)$
$=B(A+D+C)$ (パターン2)

$Q3$ : $(ABC+\overline{A}BC)(C+D)$
$A3$ : $(ABC+\overline{A}BC)(C+D)$
$=BC(C+D)$ (パターン1)
$=BC$ (吸収則)
$Q4$ : $(ABD+BCD+\overline{A}CD)(\overline{D}+E)$
$A4$ : $(ABD+BCD+\overline{A}CD)(\overline{D}+E)$
$=D(AB+BC+\overline{A}C)(\overline{D}+E)$
$=D(AB+\overline{A}C)(\overline{D}+E)$ (パターン3)
$=DE(AB+\overline{A}C)$ (パターン2)
「他の問題はよ(ノシ ‘ω’)ノシ バンバン」な方は、以下の記事もどうぞ。
まとめ
論理式の簡単化は、基本パターンを覚えて慣れるまで練習すべし。
お疲れ様でした。
コメント
補元則の A+~A = Aとありますが 正しくは,A+~A=1ですよ
そうですね!
放浪者様、ご指摘ありがとうございます!
A+~AB=A+B の証明の下から3行目で
どうして4項目のABを加えることができるのですか?
+ABというのは式中に既に存在しているため、+ABを加えても結果が変わることはないためです。
A,Bそれぞれに1か0を代入した4つの組み合わせを確認していただければ、理解しやすいかもしれません。
なるほど!わかりました!
ありがとうございます!
簡単化の基本パターン3の2番目の証明について教えてください。
(A+B)(¬A+C)(B+C)
=(A+B)(¬A+C)(B+C+A)(B+C+¬A)
と記述されておりますが、最後の()2個がわかりません。
つまり(B+C)=(B+C+A)(B+C+¬A)
ということと思われますが、どうしてでしょうか?
上記コメントですが、自己解決しました。
(A+B)(¬A+B)=Bの逆ですね。
失礼しました。