・ブール代数の証明って難しくない？？
・ブール代数の証明にコツとか裏技とかないの？？
今回の記事はこのような方のお役に立てる記事になっています。ブール代数の証明方法をマスターして、いい点数をゲットしましょう。
ブール代数の基本公式
まずは、ブール代数の重要公式を確認しておきましょう。これが分かってないと証明は不可能です。
| 交換則 | $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つ目は、双対定理を使うことです。
双対論理式とは
双対定理の前に、双対論理式について説明します。双対論理式というのは、元の式に対して
- $0→1 , 1→0$
- $\cdot →+ , +→\cdot$
これを行った論理式のことを言います。
式 $X$ があれば、これの双対論理式は $X^d$ と表します。
例 $(x+y)\cdot z $ の双対論理式は、$x\cdot y + z$ になります。
双対定理とは
そして、双対定理というのは、
$X=Y$ が成り立つとき、$X^d = Y^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$ (補元則+恒等則)
こんな感じです！
コツ２：基本パターンを暗記する
残念ながら、双対定理は無敵ではないんですね…。例えば、
$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)
のようになり、証明できましたね。とはいえ、基本パターンの適用には慣れが必要です。そのため、以下の記事で練習することをおすすめします。
まとめ
ブール代数の証明には、双対定理と基本パターンの暗記が有効。あとは、ひたすら問題を解くべし。お疲れ様でした。
コメント