【論理関数】n変数対称関数、多数決関数の性質

論理関数$f_1(x_1,x_2,\dots ,x_i,\dots ,x_j,\dots x_n)$の$x_i,x_j$を入れ替えた
関数$f_2(x_1,x_2,\dots ,x_j,\dots ,x_i,\dots x_n)$の$x_i,x_j$を考える。
任意の$i,j$について$f_1,f_2$の出力が等しいとき、n変数対称関数と言う。
n個の変数のうち、過半数以上の変数が1であるときのみ1を出力する関数をn変数多数決関数と言う。
(1)n変数対称関数は何個存在するか。
(2)多数決関数は、対称関数かつ自己双対関数であることを示せ。
(3)ある論理関数$f$が対称ならば、$f$の双対関数は対称であることを示せ。

はじめに

論理関数に関する問題の続きです。以前の記事では、自己双対関数、線形関数をそれぞれ紹介しました。まだの方は是非ご覧ください。

本記事で覚えたいこと

１．について、例えば2変数対称関数$f$を考えます。

どのような変数の入力の組み合わせでも1を出力する場合を考えると

1を取る変数が0つのとき、$f_0=\bar{x}\bar{y}$

1を取る変数が1つのとき、$f_1=x\bar{y}+\bar{x}y$

1を取る変数が2つのとき、$f_2=xy$

これを全て組み合わせて、$$\begin{array}{}\text{(1)}& f=f_0+f_1+f_2=\bar{x}\bar{y}+x\bar{y}+\bar{x}y+xy\end{array}$$

もし、1を取る変数が1つのときは0を出力するならば、$f_1=0$とし、$$\begin{array}{}\text{(2)}& f=\bar{x}\bar{y}+xy\end{array}$$とできます。

このように、n変数対称関数は、$$\begin{array}{}\text{(3)}& f=a_0{f}_0+a_1{f}_1+\dots +a_n{f}_n\end{array}$$のうち、$(a_0,a_1,\dots ,a_k)\in (0,1)$が取る組み合わせで個数が決まります。

２．については、記載した通りです。イメージ通りだと思いますが、(2)(3)でこの考え方を利用します。

解答例

(1)n変数対称関数の個数

式(3)より、$a_i$$i=0,1,\dots ,n$は0か1を取り、$i$は合計n+1個存在するので

$2\ast 2\ast 2\ast \dots \ast 2=2^{n+1}$個存在する。

過去記事で紹介した、n変数線形関数と同様の考え方に帰着できました。

(2)多数決関数の対称性、自己双対性

対称性について

多数決関数は、$n=2m+1$$m=0,1,2,\dots$としたとき

式(3)の$\left[\frac{2m+1}{2}\right]<k$を満たす$a_k$に対し、全て$a_k=1$を代入。

$\left[\frac{2m+1}{2}\right]<k$未満は、全て$a_k=0$を代入することで実現できます。

$$\begin{array}{}\text{(4)}& f=f_{\left[\frac{2m+1}{2}\right]+1}+f_{\left[\frac{2m+1}{2}\right]+2}\dots +f_n\end{array}$$

と表すことができます。

これは、対称関数の一部であることから、対称性を説明することができました。

自己双対性について

自己双対関数の定義により、式(4)の変数及び関数$f$に否定を取ります。

$$\begin{array}{}\text{(5)}& \begin{array}{rl}{f}_d& =\overline{f_{\left[\frac{2m+1}{2}\right]+1}(\stackrel{―}{x_1},\stackrel{―}{x_2},\dots \stackrel{―}{x_n})+f_{\left[\frac{2m+1}{2}\right]+2}(\stackrel{―}{x_1},\stackrel{―}{x_2},\dots \stackrel{―}{x_n})\dots +f_n(\stackrel{―}{x_1},\stackrel{―}{x_2},\dots \stackrel{―}{x_n})}\\ & =\overline{f_0(x_0,x_1\dots x_n)+f_1(x_0,x_1\dots x_n)+f_{\left[\frac{2m+1}{2}\right]}(x_0,x_1\dots x_n)}\\ & =f_{\left[\frac{2m+1}{2}\right]+1}(x_0,x_1\dots x_n)+f_{\left[\frac{2m+1}{2}\right]+2}(x_0,x_1\dots x_n)\dots +f_n(x_0,x_1\dots x_n)\end{array}\end{array}$$

以上の式変形で説明できました。

(3)対称関数と双対性

第2章により、ある関数$f$が対称関数であるとき、変数の個数によって出力0,1が決まる。((x,y,z)=(1,0,0),(0,1,0),(0,1,1)が異なる出力になることは無い。)

例として3変数対称関数を考える。

変数及び出力$f$の否定を取って双対関数を計算すると、下記の真理値表の対応になる。

変数の否定を取り、元の対称関数に代入するため、真理値表が反転しただけで、対称性は保持される。

これが、任意のnに対して成立するため、題意は示された。

最後に

(3)は式で説明できるかもしれませんが、表で書いた方が分かりやすいと考え、上記の説明にしました。

問題が複雑になるほど、真理値表を書いて実験することが重要になります。

多数決関数は単調増大関数の性質もあります。合わせて確認しておきましょう。