閾値関数と単調増大関数、双対関数の関係

$$\begin{array}{}\text{(1)}& \begin{array}{r}f(x_1,x_2,\dots ,x_n)=c_1{x}_1+c_2{x}_2+\dots +c_n{x}_n\ge T\end{array}\end{array}$$
が成立するとき、$f$は閾値関数と言う。次の問いに答えよ。
(1)任意の$i$について$c_i=1$のとき、閾値関数の双対関数は単調増大関数であることを証明せよ。
(2)(1)のとき、n変数閾値関数の双対関数と閾値Tの関係を求めよ。
(3)単調増大かつ自己双対である3変数論理関数を示せ。
(4)単調増大かつ自己反双対であるn変数論理関数を示せ。

本記事で覚えたいこと

３．のように、関数の否定を取ると、閾値が変化する点に注目です。

上記の事実は、(1)(2)を解くうえで使います。(3)(4)は、自己双対関数の記事で扱ったように、真理値用を記載していくことで解決できます。

解答例

(1)(2)n変数閾値関数の双対関数

変数$x_i=1$を取る$i$の個数を$N(x_1,x_2,\dots ,x_n$とすると、閾値関数の定義より、以下の式が成立する。

$$\begin{array}{}\text{(2)}& N(x_1,x_2,\dots ,x_n)\geqq T\end{array}$$

これの双対関数が1を取るとき、下記の式が成立する。

$$\begin{array}{}\text{(3)}& N(\overline{x_1},\overline{x_2},\dots ,\overline{x_n})<T\text{(4)}& n-N(x_1,x_2,\dots ,x_n)<T\end{array}$$

このとき、

$$\begin{array}{}\text{(5)}& F(\overline{x_0},\overline{x_1},{\bar{x}}_2,\dots ,\overline{x_n})=0\end{array}$$

なので、

$$\begin{array}{}\text{(6)}& F_d(x_0,x_1,x_2,\dots ,x_n)=\overline{F(\stackrel{―}{x_0},\stackrel{―}{x_1},{\stackrel{―}{x}}_2,\dots ,\stackrel{―}{x_n})}=1\end{array}$$

が成立する。

(5)式を整理すると

$$\begin{array}{}\text{(7)}& n-T<N(x_1,x_2,\dots ,x_n\end{array}$$

よって、$F_d$は閾値n-T+1の単調増大関数であることが示された。

(3)単調増大かつ自己双対の3変数論理関数

自己双対関数の性質により、真理値表の上半分が決定すると、下半分は、上半分の出力にNOTを取った値が出力される。

単調増大のとき、$x_i=1$を取る変数が0個以上、1個以上、2個以上、3個以上の4通りある。下記により、2個以上の場合のみ題意を満たす。

以上より、3変数多数決関数が題意を満たすので、求める論理式は

$$\begin{array}{}\text{(8)}& f(x_1,x_2,x_3)=x_1{x}_2+x_2{x}_3+x_1{x}_3\end{array}$$

(4)単調増大かつ自己反双対のn変数論理関数

題意が成立するとき、以下の関係が成立する。

$$\begin{array}{}\text{(9)}& f(0,0,\dots ,0)=f(1,1,\dots ,1)\end{array}$$

全ての変数が0である場合と1である場合で値が等しい。また、一部の変数が1である場合も同じ値を取らなければならない。

このことから、題意を満たす論理関数は、0値関数か1値関数の2通りのみになる。

最後に

問題によっては、$c_1=1,c_2=2$など、変数に対して重みを付与した場合もあります。どのような式で表記されているか、事前に注意深く確認しましょう。

参考文献

スイッチング回路理論：当麻 喜弘 (著)