\(n\)変数論理関数\(f(x)=(x_1,x_2,x_3,…,x_n)\)に対して
\(f(x_1,x_2,x_3,…,x_n)=\bar{x}_1f(0,x_2,x_3,…x_n) \vee x_1f(1,x_2,x_3,…,x_n) \)
を\(f\)のシャノン展開という。
なぜこの式が成立するの？
両辺に\(x_1=0,\;x_1=1\)をそれぞれ代入すると、ちゃんとこの式が成り立っているのが分かります。
\(x_1=0\)を代入：
（左辺）\(=f(0,x_2,x_3,…,x_n)\)
（右辺）\(=(1 \wedge f(0,x_2,x_3,…,x_n)) \vee (0 \wedge f(1,x_2,x_3,…,x_n))\)
\(=f(0,x_2,x_3,…,x_n) \vee 0\)
\(=f(0,x_2,x_3,…,x_n)\)
\(x_1=1\)を代入：
（左辺）\(=f(1,x_2,x_3,…,x_n)\)
（右辺）\(=(0 \wedge f(0,x_2,x_3,…,x_n)) \vee (1 \wedge f(1,x_2,x_3,…,x_n))\)
\(= 0 \vee f(1,x_2,x_3,…,x_n)\)
\(=f(1,x_2,x_3,…,x_n)\)
シャノン展開を何度も繰り返す
ここまでは\(x_1\)についてシャノン展開を行いましたが、さらに続けて\(x_2\)についてシャノン展開をやってみましょう。
\(x_1=0\)のときと\(x_1=1\)のときの2パターンあるのでそれぞれ展開します。
\(x_1=0\)のとき：
\(f(0,x_2,x_3,…,x_n)=\bar{x}_2f(0,0,x_3,…x_n) \vee x_2f(0,1,x_3,…,x_n) \)
\(x_1=1\)のとき：
\(f(1,x_2,x_3,…,x_n)=\bar{x}_2f(1,0,x_3,…x_n) \vee x_2f(1,1,x_3,…,x_n) \)
これを先ほどの式に代入してみると以下の式が得られます。
\(f(x_1,x_2,x_3,…,x_n)=\bar{x}_1(\bar{x}_2f(0,0,x_3,…x_n) \vee x_2f(0,1,x_3,…,x_n))\)
\(\vee x_1(\bar{x}_2f(1,0,x_3,…x_n) \vee x_2f(1,1,x_3,…,x_n)) \)
\(=\bar{x}_1\bar{x}_2f(0,0,x_3,…x_n) \vee \bar{x}_1x_2f(0,1,x_3,…,x_n)\)
\(\vee x_1\bar{x}_2f(1,0,x_3,…x_n) \vee x_1x_2f(1,1,x_3,…,x_n) \)
イメージ的には\(f\)の中身が0だった変数にはバーが付いて、1だったらそのままになります。\(x_1\)が0か1を取り、\(x_2\)が0と1を取るので、合計4つの項が登場します。
この先も\(x_3,x_4,…,x_n\)についてシャノン展開を繰り返すことができます。
真理値表を使ってシャノン展開してみる
それでは実際に真理値表を使って論理関数をシャノン展開してみましょう。以下の3変数論理関数を展開し、\(x_1,x_2,x_3\)だけで表したいと思います。
3変数論理関数を全ての変数についてシャノン展開すると以下の式を得ることができます。
\(f(x_1,x_2,x_3)=x_1x_2x_3f(1,1,1) \vee x_1x_2\bar{x}_3f(1,1,0) \vee x_1\bar{x}_2x_3f(1,0,1)\)
\(\vee x_1\bar{x}_2\bar{x}_3f(1,0,0) \vee \bar{x}_1x_2x_3f(0,1,1) \vee \bar{x}_1x_2\bar{x}_3f(0,1,0)\)
\(\vee \bar{x}_1\bar{x}_2x_3f(0,0,1) \vee \bar{x}_1\bar{x}_2\bar{x}_3f(0,0,0)\)
\(x_3\)についてシャノン展開をすると
\(f(0,0,x_3)=\bar{x}_3f(0,0,0)\vee x_3f(0,0,1)\)
\(f(1,0,x_3)=\bar{x}_3f(1,0,0)\vee x_3f(1,0,1)\)
\(f(0,1,x_3)=\bar{x}_3f(0,1,0)\vee x_3f(0,1,1)\)
\(f(1,1,x_3)=\bar{x}_3f(1,1,0)\vee x_3f(1,1,1)\)
が得られる。
これらの式を\(x_1,\;x_2\)について既にシャノン展開した式に代入すると
\(f(x_1,x_2,x_3)=x_1x_2x_3f(1,1,1) \vee x_1x_2\bar{x}_3f(1,1,0) \vee x_1\bar{x}_2x_3f(1,0,1)\)
\(\vee x_1\bar{x}_2\bar{x}_3f(1,0,0) \vee \bar{x}_1x_2x_3f(0,1,1) \vee \bar{x}_1x_2\bar{x}_3f(0,1,0)\)
\(\vee \bar{x}_1\bar{x}_2x_3f(0,0,1) \vee \bar{x}_1\bar{x}_2\bar{x}_3f(0,0,0)\)
が得られる。
また上の真理値表を見ると
\(f(1,1,1)=1\)
\(f(1,1,0)=0\)
\(f(1,0,1)=0\)
\(f(1,0,0)=1\)
\(f(0,1,1)=0\)
\(f(0,1,0)=1\)
\(f(0,0,1)=1\)
\(f(0,0,0)=0\)
が得られるので、シャノン展開した式に代入すると以下の式が得られます。
\(f(x_1,x_2,x_3)=x_1x_2x_3 \vee x_1\bar{x}_2\bar{x}_3 \vee \bar{x}_1x_2\bar{x}_3 \vee \bar{x}_1\bar{x}_2x_3\)
ということで\(f\)を\(x_1,x_2,x_3\)だけで表すことができました。このような表現方法を論理和標準形と言います。
2分決定木とシャノン展開
最後に2分決定木とシャノン展開の関係について見ていきましょう。さきほどの真理値表で表される3変数論理関数の2分決定木は以下のようになります。
この2分決定木とシャノン展開を見ると、これらが対応しているのが分かりますね。最終的に1に到達する道を全てピックアップすると、
\(x_1=1,\;x_2=1,\;x_3=1\)
\(x_1=1,\;x_2=0,\;x_3=0\)
\(x_1=0,\;x_2=1,\;x_3=0\)
\(x_1=0,\;x_2=0,\;x_3=1\)
の4つが得られます。\(x_i=1\)のやつを\(x_i\)、\(x_i=0\)のやつを\(\bar{x}_i\)で表して\(\vee\)でくっつけると
\(x_1x_2x_3 \vee x_1\bar{x}_2\bar{x}_3 \vee \bar{x}_1x_2\bar{x}_3 \vee \bar{x}_1\bar{x}_2x_3\)
が得られます。これって論理関数をシャノン展開した式と同じですよね。このようにシャノン展開に対応する2分決定木を作ることができます。
おわりに
いかがでしたか。
今回の記事ではシャノン展開について解説していきました。
今後もこのような論理関数に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
普段は統計検定2級の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
