\(n\)変数論理関数\(f(x)=(x_1,x_2,x_3,…,x_n)\)に対して以下の展開をそれぞれ正Davio（ダビオ）展開と負Davio（ダビオ）展開という。
正Davio（ダビオ）展開
\(f(x_1,x_2,…,x_n) = f(0,x_2,…,x_n) \)
\(\oplus x_1 (f(0,x_2,…,x_n) \oplus f(1,x_2,…,x_n))\)
負Davio（ダビオ）展開
\(f(x_1,x_2,…,x_n) =\bar{x}_1( f(0,x_2,…,x_n) \oplus f(1,x_2,…,x_n)) \)
\(\oplus f(0,x_2,…,x_n)\)
なぜこの式が成立するの？
両辺に0,1をそれぞれ代入して確かめる
両辺に\(x_1=0,\;x_1=1\)をそれぞれ代入すると、ちゃんとこの式が成り立っているのが分かります。見やすくするため
\(f(0,x_2,…,x_n) = f_{x_1=0}\)
\(f(1,x_2,…,x_n) = f_{x_1=1}\)
とします。
\(x_1=0\)を代入（正ダビオ展開）：
（左辺）\(=f_{x_1=0}\)
（右辺）\(=f_{x_1=0} \oplus 0 \wedge (f_{x_1=0} \oplus f{x_1=1})\)
\(= f_{x_1=0} \oplus ((0 \wedge f_{x_1=0}) \oplus (0 \wedge f_{x_1=1}))\)
\(= f_{x_1=0} \oplus (0 \oplus 0)\)
\(= f_{x_1=0} \oplus 0\)
\(= f_{x_1=0}\)
\(x_1=1\)を代入（正ダビオ展開）：
（左辺）\(=f_{x_1=1}\)
（右辺）\(=f_{x_1=0} \oplus 1 \wedge (f_{x_1=0} \oplus f{x_1=1})\)
\(= f_{x_1=0} \oplus ((1 \wedge f_{x_1=0}) \oplus (1 \wedge f_{x_1=1}))\)
\(= f_{x_1=0} \oplus (f_{x_1=0} \oplus f_{x_1=1})\)
\(= (f_{x_1=0} \oplus f_{x_1=0}) \oplus f_{x_1=1}\)
\(= 0 \oplus f_{x_1=1}\)
\(= f_{x_1=1}\)
負ダビオ展開の場合も同じように成立するのが分かります。
排他的論理和\( \oplus \)についてはこちらの記事で解説しています！
シャノン展開から導出する
シャノン展開からも導出できます。
\(f = \bar{x}_1f_{x_1=0} \vee x_1f_{x_1=1}\) （シャノン展開）
\(= \bar{x}_1f_{x_1=0} \oplus x_1f_{x_1=1}\)
\(= (x_1 \oplus 1)f_{x_1=0} \oplus x_1f_{x_1=1}\)
\(= x_1f_{x_1=0} \oplus f_{x_1=0} \oplus x_1f_{x_1=1}\)
\(=f_{x_1=0} \oplus x_1(f_{x_1=0} \oplus f_{x_1=1})\)
\(x \vee y = x \oplus y \oplus xy\)が成り立ちます。
つまり
\((\bar{x}_1f_{x_1=0}) \vee (x_1f_{x_1=1}) = (\bar{x}_1f_{x_1=0}) \oplus (x_1f_{x_1=1}) \oplus(\bar{x}_1f_{x_1=0})(x_1f_{x_1=1})\)
となります。ここで\((\bar{x}_1f_{x_1=0})(x_1f_{x_1=1})\)は\(\bar{x}_1x_1\)が含まれており、\(\bar{x}_1x_1=0\)なので
\((\bar{x}_1f_{x_1=0})(x_1f_{x_1=1})\)
\( = \bar{x}_1x_1f_{x_1=0}f_{x_1=1}\)
\(= 0 \wedge f_{x_1=0} \wedge f_{x_1=1}\)
\(= 0\)
従って
\((\bar{x}_1f_{x_1=0}) \vee (x_1f_{x_1=1})\)
\( = (\bar{x}_1f_{x_1=0}) \oplus (x_1f_{x_1=1}) \oplus(\bar{x}_1f_{x_1=0})(x_1f_{x_1=1})\)
\( = (\bar{x}_1f_{x_1=0}) \oplus (x_1f_{x_1=1}) \oplus 0\)
となります。また、排他的論理和の性質より\(x \oplus 0 = x\)なので
\( (\bar{x}_1f_{x_1=0}) \oplus (x_1f_{x_1=1}) \oplus 0\)
\( =\bar{x}_1f_{x_1=0} \oplus x_1f_{x_1=1}\)
となります。
証明完了
シャノン展開はこちらの記事で詳しく解説しています！
ダビオ展開を何度も繰り返す
ここまでは\(x_1\)についてダビオ展開をしていきましたが、続けて\(x_2\)についてダビオ展開をしていきましょう。簡単のため2変数論理関数を正ダビオ展開することを考えます。
\(x_1=0\)のときと\(x_1=1\)のときの2パターンあるのでそれぞれ展開します。
\(x_1 = 0\)のとき
\(f(0,x_2) = f(0,0) \oplus x_2(f(0,0) \oplus f(0,1))\)
\(x_1 = 1\)のとき
\(f(1,x_2) = f(1,0) \oplus x_2(f(1,0) \oplus f(1,1))\)
これを先ほどの式に代入すると以下の式が得られます。
\(f(x_1,x_2)\)
\( = f(0,x_2) \oplus x_1(f(0,x_2) \oplus f(1,x_2))\)
\( = f(0,0) \oplus x_2(f(0,0) \oplus f(0,1))\)
\(\oplus x_1(f(0,0) \oplus x_2(f(0,0) \oplus f(0,1)) \oplus f(1,0) \oplus x_2(f(1,0) \oplus f(1,1)))\)
\( = f(0,0) \oplus x_1(f(0,0) \oplus f(1,0)) \oplus x_2(f(0,0) \oplus f(0,1))\)
\(\oplus x_1x_2(f(0,0) \oplus f(0,1) \oplus f(1,0) \oplus f(1,1))\)
2変数論理関数を例に使ったのでこれ以上ダビオ展開はできませんが、より変数の数が多い場合は\(x_3,…,x_n\)についてさらにダビオ展開を続けていくこともできます。
真理値表を使ってダビオ展開してみる
それでは実際に真理値表を使って論理関数をダビオ展開してみましょう。以下の2変数論理関数について正ダビオ展開をして、\(x_1,x_2\)及び論理積\(\wedge\)と排他的論理和\(\oplus\)だけで論理関数を表したいと思います。
2変数論理関数の正ダビオ展開をおさらいします。
\(f(x_1,x_2)\)
\( = f(0,0) \oplus x_1(f(0,0) \oplus f(1,0)) \oplus x_2(f(0,0) \oplus f(0,1))\)
\(\oplus x_1x_2(f(0,0) \oplus f(0,1) \oplus f(1,0) \oplus f(1,1))\)
また上の真理値表を見ると
\(f(1,1) = 1\)
\(f(1,0) = 0\)
\(f(0,1) = 1\)
\(f(0,0) = 1\)
が得られるので正ダビオ展開した式に代入すると以下の式が得られます。
\(f(x_1,x_2)\)
\( = 1 \oplus x_1(1 \oplus 0) \oplus x_2(1 \oplus 1) \oplus x_1x_2(1 \oplus 1 \oplus 0 \oplus 1)\)
\( = 1 \oplus (x_1 \wedge 1) \oplus (x_2 \wedge 0) \oplus (x_1x_2 \wedge 1)\)
\( = 1 \oplus x_1 \oplus x_1x_2\)
ということでダビオ展開することができました。このような表現方法を環和標準形またはリードマラー標準形と言います。
おわりに
いかがでしたか。
今回の記事ではダビオ展開について解説していきました。
今後もこのような論理関数に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
普段は統計検定2級の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
