論理関数
で定義される関数を自己双対関数と言う。下記の問に答えよ。
(1)n変数自己双対関数は何個存在するか。
(2)2変数自己双対関数を論理式で全て挙げよ
(3)
(4)
はじめに
論理関数の性質に関する問題は、東北大を初め、京大などで出題されます。閾値関数、対称関数、正関数など、様々な関数が存在しますが、本問ではまず自己双対関数の性質について例題を用いて説明していきます。
本問で覚えたいこと
- 自己双対関数は、期待値表の上半分が決定すると、下半分が決定する
- 自己双対関数を組み合わせた関数も自己双対関数と証明する問題は、ドモルガン律を使用するとうまくいきやすい
ある3変数自己双対関数

上記のような真理値表だったとします。実は、残りの下半分は一意に決まります。
自己双対関数の性質により、変数のbitを反転させた入力をすると、反転前の入力に対する出力値のnotを取った値を出力します。

上図は、(0,1,1)で1を出力するのですから、(1,0,0)ならば0を出力することになります。
これを他の組み合わせに対しても考えることで、下半分は一意に決まります。
2.については(3)で用います。
解答例
(1)n変数自己双対関数の個数

まず、n変数論理関数の個数を考える。真理値表より、入力の組み合わせは

一方、n変数双対関数の個数を考える。前章の説明から、入力の組み合わせ半分に対する出力が決まれば、もう半分は一意に決まる。よって、入力の組み合わせは
(2)2変数双対関数の論理式ついて
前章の説明から、真理値表の上半分を決めて、下半分の出力を反転させれば良い。
この考えから、2変数双対関数の取りうる真理値表は
実際の真理値表は、下記になる。

左から順に、
(3)自己双対関数の証明問題
与えられた論理関数
ドモルガン律を用いて、(3)式を変形すると
(i)
(2)式は、
(ii)
(6)式より、
よって、全ての
(4)GとHの関係
(3)より、
最後に
本記事では、自己双対関数について紹介しました。一方で、逆の性質を持つ関数もあります。
と、右辺の
問題で問われている関数は、どちらの関数に対してか、確認してから解答に移ると良いと思います。
参考文献
解法と演習 大学院入試問題<情報通信系>:関 正治(著),陳 啓浩(著),姫野 俊一(著) P32