加法標準形の否定

加法標準形の関数値を最小項の論理係数と考えれ ば、加法標準形全体を否定するばあいは全ての係数を否定するだけでよい。

1変数$(x)$の論理関数を否定する例：

$$\sim f(x) = \sim f(0) \sim x \lor \sim f(1) x$$

$$\sim f(x) = \sim f_0 m_0 \lor \sim f_1 m_1$$

2変数$(x, y)$の論理関数を否定する例：

$$\sim f(x, y) = \sim f(0, 0) \sim x \sim y \lor \sim f(0, 1) \sim x y \lor \sim f(1, 0) x \sim y \lor \sim f(1, 1) xy$$

$$\sim f(x, y) = \sim f_0 m_0 \lor \sim f_1 m_1 \lor \sim f_2 m_2 \lor \sim f_3 m_3$$

3変数$(x, y, z)$の論理関数を否定する例：

略記だけを示す。

$$\sim f(x, y, z) = \sim f_0 m_0 \lor \sim f_1 m_1 \lor \sim f_2 m_2 \lor \sim f_3 m_3$$

$$\lor \sim f_4 m_4 \lor \sim f_5 m_5 \lor \sim f_6 m_6 \lor \sim f_7 m_7$$

n変数 $(x_1, x_2, x_3, \ldots , x_n)$の論理関数を否定する例：

略記だけを示す。

$$\sim f(x_1, x_2, x_3, \ldots , x_n) = \sim f_0 m_0 \lor \sim f_1 m_1 \lor \sim f_2 m_2 \lor \cdots \lor \sim f_{2^n-1}m_{2^n-1}$$

これは次のような一般式で表現できる。

$$\sim f(x_1, x_2, x_3, \ldots , x_n) = \bigvee_{i=0}^{2^n-1}\sim f_i m_i$$

上の式をさらに否定すればド・モルガンの法則より、乗法標準形が導かれる。

$$\sim \sim f(x_1, x_2, x_3, \ldots , x_n) = \sim \bigvee_{i=0}^{2^n-1}\sim f_i m_i$$

$$f(x_1, x_2, x_3, \ldots , x_n) = \sim \bigvee_{i=0}^{2^n-1}\sim f_i m_i$$

$$= \bigwedge_{i=0}^{2^n-1}(\sim \sim f_i \lor \sim m_i)$$

$$= \bigwedge_{i=0}^{2^n-1}(f_i \lor \sim m_i)$$

$$= \bigwedge_{i=0}^{2^n-1}(fi \lor M_{2^n-1-i})$$

指数形式で表現すると、次のようになる。

最初に $\sim f(x_1, x_2, \ldots ,x_n) = F(x_1, x_2, \ldots ,x_n)$とする。

$$F(x_1, x_2, x_3, \ldots ,x_n) = \bigvee_{(a_1, a_2, a_3, \ldots ,... ...a_2, a_3, \ldots , a_n) x_{1}^{a_1} x_{2}^{a_2} x_{3}^{a_3} \ldots x_{n}^{a_n}$$

左右両辺を否定する。

$$\sim F(x_1, x_2, x_3, \ldots ,x_n) = \sim \bigvee_{(a_1, a_2, a_3... ...a_2, a_3, \ldots , a_n) x_{1}^{a_1} x_{2}^{a_2} x_{3}^{a_3} \ldots x_{n}^{a_n}$$

$$\sim F(x_1, x_2, x_3, \ldots ,x_n) = \bigwedge_{(a_1, a_2, a_3, \... ...2, a_3, \ldots , a_n) x_{1}^{a_1} x_{2}^{a_2} x_{3}^{a_3} \ldots x_{n}^{a_n}\}$$

$$\sim F(x_1, x_2, \ldots ,x_n) = \bigwedge_{(a_1, a_2, \ldots , a_... ... \lor \sim x_{1}^{a_1} \lor \sim x_{2}^{a_2} \lor \ldots \lor \sim x_{n}^{a_n}$$

$\sim F(x_1, x_2, \ldots ,x_n) = f(x_1, x_2, \ldots ,x_n)$に戻す。

$$f(x_1, x_2, \ldots ,x_n) = \bigwedge_{(a_1, a_2, \ldots ,a_n) \in... ... \lor \sim x_{1}^{a_1} \lor \sim x_{2}^{a_2} \lor \ldots \lor \sim x_{n}^{a_n}$$

任意の$n$変数論理関数(最小項表現)を否定するばあは、次のようになる。 いままでの $f(x_1, x_2, x_3, \ldots ,x_n)$という関数の代わり $\sim f(x_1, x_2, x_3, \ldots ,x_n)$を最初の関数として考える。

$$\sim f(x_1, x_2, x_3, \ldots ,x_n) = \bigvee_{\sim f(a_1, a_2, a_3, \ldots ,a_n) = 1} x_{1}^{a_1} x_{2}^{a_2} x_{3}^{a_3} \ldots x_{n}^{a_n}$$

左右両辺を否定する。

$$\sim \sim f(x_1, x_2, x_3, \ldots ,x_n) = \sim \bigvee_{f(a_1, a_2, a_3, \ldots ,a_n) = 0} x_{1}^{a_1} x_{2}^{a_2} x_{3}^{a_3} \ldots x_{n}^{a_n}$$

$$f(x_1, x_2, x_3, \ldots ,x_n) = \bigwedge_{f(a_1, a_2, a_3, \ldots ,a_n) = 0} \sim(x_{1}^{a_1} x_{2}^{a_2} x_{3}^{a_3} \ldots x_{n}^{a_n})$$

$$f(x_1, x_2, x_3, \ldots ,x_n) = \bigwedge_{f(a_1, a_2, a_3, \ldot... ... \lor \sim x_{2}^{a_2} \lor \sim x_{3}^{a_3} \lor \ldots \lor \sim x_{n}^{a_n}$$

$\sim x_{i}^{a_i}$は $x_{i}^{\sim a_i}$であるから、次のように 表すこともできる。

$$f(x_1, x_2, x_3, \ldots ,x_n) = \bigwedge_{f(a_1, a_2, a_3, \ldot... ...\lor x_{2}^{\sim a_2} \lor x_{3}^{\sim a_3} \lor \ldots \lor x_{n}^{\sim a_n}$$