【論理関数】n変数線形関数の個数、性質

はじめに

論理関数の中には、様々な性質を持つものがあります。例として、前回の記事では、自己双対関数を説明しました。今回は、線形関数について説明します。性質については、本問で述べた通りです。

こちらも、東北大をはじめとする院試でよく出題されます。

この記事で覚えたいこと

1.2.3.それぞれ(1)(2)(3)で使用します。

XORは排他的論理和です。$x\oplus y$が$x\ne y$のとき、1、$x=y$のとき0を出力します。

下記のように分配律が成立します。

$$\begin{array}{}\text{(2)}& NOR(x,y)& =(\overline{x+y})\text{(3)}& & =(\bar{x}･\bar{y})\text{(4)}& & =(1\oplus x)(1\oplus y)\text{(5)}& & =xy\oplus x\oplus y\oplus 1\end{array}$$

確かに、環和標準形で表すことができました。この式変形を利用し、(2),(3)を解いていきます。

解答例

(1) n変数線形関数の個数

問題で与えられた通り、n変数線形関数は、式(1)で表される。

$c_i$は、0,1の2通り入り、これが$i=0,1,2,\dots ,n$のn+1個の定数に対し当てはめることができる。

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

(2) 線形関数と双対関数

$$\begin{array}{}\text{(6)}& \overline{x_i}=1\oplus x_i\end{array}$$を使用して、式(1)を変形する。

$$\begin{array}{}\text{(7)}& & f(\overline{x_1},\overline{x_2},\dots ,\overline{x_n})\text{(8)}& & =c_0\oplus c_1\overline{x_1}\oplus c_2\overline{x_2}\oplus \dots \oplus c_n\overline{x_n}\text{(9)}& & =c_0\oplus c_1(1\oplus x_1)\oplus c_2(1\oplus x_2)\oplus \dots \oplus c_n(1\oplus x_n)\text{(10)}& & =(c_0\oplus c_1\oplus \dots \oplus c_n)\oplus c_1{x}_1\oplus c_2{x}_2\dots c_n{x}_n\end{array}$$

$c_1{x}_1\oplus c_2{x}_2\oplus \dots \oplus c_n{x}_n･･･(A)$ は線形関数の変数項である。

$(c_0\oplus c_1\oplus \dots \oplus c_n)･･･(B)$ の値次第で(7)式の結果が変化する。

(i) (B)=1 のとき、$\overline{x_i}=1\oplus x_i$ より出力は反転する。

$$\begin{array}{}\text{(11)}& f(\overline{x_1},\overline{x_2},\dots ,\overline{x_n})=\overline{f(x_1,x_2,\dots ,x_n)}\end{array}$$

これより、自己双対関数であることが示された。

(ii) (B)=0 のとき、$x_i=0\oplus x_i$ より、入力値を出力する。

$$\begin{array}{}\text{(12)}& f(\overline{x_1},\overline{x_2},\dots ,\overline{x_n})=f(x_1,x_2,\dots ,x_n)\end{array}$$

これより、自己反双対関数であることが示された。

(3) 環和標準形について

線形関数の性質(式(1))より、XORとANDで任意の論理関数を表すことができれば、題意を満たすことができる。

論理回路の他の演算子は、OR、NOR。これをXORとANDで示すことを考える。

NOT：式(6)より成立

NOR：式(5)より成立

OR：NOT(NOR)で、$1\oplus 1=0$より、$xy\oplus x\oplus y$で示すことができる。

3変数以上の場合でも上記の式変形は成立する。これより、任意の論理関数は、例として

$f=x_1\oplus x_2\oplus x_3{x}_4\oplus x_5{x}_6{x}_7\dots$

$f=1\oplus x_1\oplus x_2\oplus x_3{x}_4\oplus x_5{x}_6{x}_7\dots$

のように、ANDとXORで表すことができる。

$\oplus$と$\oplus$の間を$X_i$で表すと、題意の式が成立する。

最後に

任意の論理関数は、AND、OR、NOTでも表すことができますが、XORを使用すると簡潔に表すことができます。本問の考え方は、論理回路のbit演算(加算器)でも使用することがあります。是非、本問で使用した変形を別の問題でも応用できるよう演習を積んで下さればと思います。

参考文献

解法と演習 大学院入試問題<情報通信系>：関 正治(著),陳 啓浩(著),姫野 俊一(著) P93