【あの定理を知っていますか?】ブール代数における証明のコツ【分かりやすい】

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

 

基本/応用情報技術者 教えあいコミュつくりました!【LINEオープンチャットで無料です 7/30~】

スクールに入る気はないけど、みんなで教え合いながら合格を目指したい人はどうぞー!
 

 

・ブール代数の証明って難しくない??

・ブール代数の証明にコツとか裏技とかないの??

 

今回の記事はこのような方のお役に立てる記事になっています。ブール代数の証明方法をマスターして、いい点数をゲットしましょう。

 

ブール代数の基本公式

まずは、ブール代数の重要公式を確認しておきましょう。これが分かってないと証明は不可能です。

交換則 $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$
$A+BC=(A+B)(A+C)$
恒等則 $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$
ド・モルガンの法則 $\overline{A+B}=\overline{A}\cdot \overline{B}$
$\overline{A\cdot B}=\overline{A}+ \overline{B}$

記号の意味も分からないという方は、

【ブール代数】論理式の全記号と公式【読み方,例,解説付き】
・論理式ってどんな記号があるの?・記号の読み方は?・公式ってどういうのがある? こういった疑問に答えるため、応用情報技術者の筆者が分かりやすく解説し、見やすくまとめていきます。 論理式で使用される記号論理式で使...

こちらもご覧ください。

 

ブール代数の証明のコツ

ブール代数の証明のコツは2つあります。順番に説明していきます。

 

コツ1:双対定理を使う

1つ目は、双対定理を使うことです。

双対論理式とは

双対定理の前に、双対論理式について説明します。双対論理式というのは、元の式に対して

  • $0→1 , 1→0$ 
  • $\cdot →+ , +→\cdot$ 

これを行った論理式のことを言います。

式 $X$ があれば、これの双対論理式は $X^d$ と表します。

 

$(x+y)\cdot z $ の双対論理式は、$x\cdot y + z$ になります。

 

双対定理とは

そして、双対定理というのは、

$X=Y$ が成り立つとき、$X^d = Y^d$ が成り立つという定理です。

$X = X^d$ ではないことに注意
 

双対定理の使い方

では、双対定理を用いた論理式の証明方法を解説していきます。

例えば、

$Q1$ : $A+\overline{A}B = A+B$ を示せ。

という問題があったとします。なかなかぱっと見ではわからないですよね。一回がむしゃらに証明してみることにしましょう。

 

$A+\overline{A}B$

$=A+AB+\overline{A}B$   (吸収則)

$=A+(A+\overline{A})B$   (分配則)

$=A+B$   (補元則+恒等則)

無理やり証明した感が否めません。特に、初めの吸収則とか勘ですよね笑

 

では、いよいよ双対定理を使ってみます。

まずは、 $A+\overline{A}B = A+B$ これに双対定理を使います。すると、

$A(\overline{A}+B) = A\cdot B$  こうなりますよね。では、左辺を変形していきます。

$A(\overline{A}+B)$

$=A\overline{A}+AB$ (分配則)

$=AB$ (補元則+恒等則)

元の式の双対論理式は無理なく証明できましたね。公式としては、

分配則→補元則→恒等則 の順に使用しました。これを元の式にも順に適用していけば OK です。

ちなみに、論理式の公式は

分配則 $A(B+C)=AB+AC$
$A+BC=(A+B)(A+C)$

のように、偶数個になってますが、これは「お互いに双対論理式になっている」のに気づきましたか?? つまり、双対定理を使って証明するときは、「双対論理式に使った公式と対になる方の公式を使えばよい」ということです。

 

双対論理式の変形の時には、$A(B+C)=AB+AC$ の方を使ったので、元の式に分配則を使うときには、 $A+BC=(A+B)(A+C)$ こちらを使えばいいということですね。

 

$A+\overline{A}B$

$=(A+\overline{A})(A+B)$ (分配則)

$=A+B$ (補元則+恒等則)

こんな感じです! 

 

コツ2:基本パターンを暗記する

残念ながら、双対定理は無敵ではないんですね…。例えば、

$Q2$ : $(ABD+BCD+\overline{A}CD)(\overline{D}+E)=DE(AB+\overline{A}C)$を証明しなさい。

このような問題には双対定理を使ってもしんどいですね。そこで、基本パターンを暗記しておきます。基本パターンはこちらです。

論理式変形基本パターン

 

画像にしたので保存しててください。基本パターン3種+吸収則です。証明は論理式の簡単化のコツこちらをご覧ください。

すると、こちらの式は

 

$A2$ : $(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)

のようになり、証明できましたね。とはいえ、基本パターンの適用には慣れが必要です。そのため、以下の記事で練習することをおすすめします。

【ブール代数】論理式の簡単化(解き方)のコツ【練習問題付き】
・実はブール代数って何かすらあまりわかってない・論理式の簡単化って何が何だかわからない この記事では、このようにブール代数を少し聞いたことがあるレベルの人向けに、応用情報技術者の筆者がブール代数の簡単化について丁寧に解説...

 

まとめ

ブール代数の証明には、双対定理と基本パターンの暗記が有効。あとは、ひたすら問題を解くべし。お疲れ様でした。

 

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

コメント

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