- シャノン展開ってなに？
- なんでシャノン展開の式が成立するの？
- シャノン展開と真理値表の関係は？
- シャノン展開と2分決定木の関係は？
\(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) \)
これを\(x_1\)のみ展開した式に代入すると以下の式が得られます。
\(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を取る2パターン、\(x_2\)が0と1を取る2パターンあるので合計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分決定木とシャノン展開を見ると、この2つが対応しているのが分かります。最終的に1に到達する道を全てピックアップすると、
\((x_1,x_2,x_3)=(1,1,1)\)
\((x_1,x_2,x_3)=(1,0,0)\)
\((x_1,x_2,x_3)=(0,1,0)\)
\((x_1,x_2,x_3)=(0,0,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\)
が得られます。これって第4章で論理関数をシャノン展開して得られた式と同じですよね。このようにシャノン展開と2分決定木が対応していることが分かります。
おわりに
いかがでしたか。
今回の記事ではシャノン展開について解説していきました。
今後もこのような論理関数に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
普段は統計検定2級の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
