【ブール代数】論理式の簡単化(解き方)のコツ【練習問題付き】

大学で学ぶ情報学
スポンサーリンク

・実はブール代数って何かすらあまりわかってない

・論理式の簡単化って何が何だかわからない

 

この記事では、このようにブール代数を少し聞いたことがあるレベルの人向けに、応用情報技術者の筆者がブール代数の簡単化について丁寧に解説します。

 

※ブール代数の証明問題の解き方は、下記の記事がより参考になります。

【あの定理を知っていますか?】ブール代数における証明のコツ【分かりやすい】
 ・ブール代数の証明って難しくない??・ブール代数の証明にコツとか裏技とかないの?? 今回の記事はこのような方のお役に立てる記事になっています。ブール代数の証明方法をマスターして、いい点数をゲットしましょう。 ブー...

 

ブール代数の基礎

一応、ほぼ初学者の人のために、記号の意味変換規則等を解説します。 既にある程度の理解がある方は、読み飛ばしても問題ありません。

 

ブール代数における記号の意味

ブール代数において、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)

 

「他の問題はよ(ノシ ‘ω’)ノシ バンバン」な方は、以下の記事もどうぞ。

 

まとめ

論理式の簡単化は、基本パターンを覚えて慣れるまで練習すべし。

お疲れ様でした。

ブール代数のまとめ記事へ

 

コメント

  1. 放浪者 より:

    補元則の A+~A = Aとありますが 正しくは,A+~A=1ですよ

  2. 新一年 より:

    A+~AB=A+B の証明の下から3行目で
    どうして4項目のABを加えることができるのですか?

    • 運営者 運営者 より:

      +ABというのは式中に既に存在しているため、+ABを加えても結果が変わることはないためです。
      A,Bそれぞれに1か0を代入した4つの組み合わせを確認していただければ、理解しやすいかもしれません。

  3. 定年おじさん より:

    簡単化の基本パターン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)
    ということと思われますが、どうしてでしょうか?

  4. 定年おじさん より:

    上記コメントですが、自己解決しました。
    (A+B)(¬A+B)=Bの逆ですね。

    失礼しました。

タイトルとURLをコピーしました