2024-01

論理関数\(f_{1}\left( x_{1},x_{2},\ldots ,x_{i},\ldots ,x_{j},\ldots x_{n}\right)\)の\(x_{i},x_{j}\)を入れ替えた関数\(f_{2}\left( x_{1},x_{2},\ldots ,x_{j},\ldots ,x_{i},\ldots x_{n}\right)\)の\(x_{i},x_{j}\)を考える。任意の\(i,j\)について\(f_{1},f_{2}\)の出力が等しいとき、n変数対称関数と言う。

あるn変数論理関数について、\begin{eqnarray}f\left( x_{1},x_{2},\ldots ,x_{n}\right)=c_{0}\oplus c_{1}x_{1}\oplus c_{2}x_{2}\oplus \ldots \oplus c_{n}x_{n}\end{eqnarray}が成立するとき、線形関数と呼ぶ。

論理関数の性質に関する問題は、東北大を初め、京大などで出題されます。閾値関数、対称関数、正関数など、様々な関数が存在しますが、本問ではまず自己双対関数の性質について例題を用いて説明していきます。