【論理関数】積和標準形、最簡形、和積標準形の求め方

はじめに

論理関数の説明を最初に行い、積和形、和積形との関係を説明していきます。

論理関数とは

0,1の離散的な2通りの入力に対し、0,1の2通りを出力として返す機能を言います。

中学数学で、y=2xなる概念が出てきたと思います。xを代入すると、2倍した値を出力として返す機能を指しています。

上記の関数は連続的な値に対して、0,1以外の値でも出力を返します。

しかし、論理関数の場合は、計算機での処理を想定しているため、0,1の2通りしかありません。

入力変数に対し出力を返す流れは変わらないものの、入出力の中身が異なることがキーポイントです。

積和系とは

論理関数$f(x_0,x_1,x_2,\cdots ,x_n)$について

$$\begin{array}{}\text{(1)}& \begin{array}{r}f(x_0,x_1,x_2,\cdots ,x_n)=x_0{x}_1+x_1{x}_2+x_{n-1}{x}_n\end{array}\end{array}$$など、積項の和として表示したものを言います。

特に、$x_1{x}_2+x_1\overline{x_2}=x_1(x_2+\overline{x_2})=x_1$などを用いて、マージできる項をくっつけ、(1)式を限界まで簡単化したものを積和標準形(最簡形)と言います。

限界まで簡単化することにより、論理回路を組む際に必要な素子を低減することが出来ます。

和積系とは

積和系とは逆です。

$$\begin{array}{}\text{(2)}& \begin{array}{r}f(x_0,x_1,x_2,\cdots ,x_n)=(x_0+x_1)(x_1+x_2)(x_{n-1}+x_n)\end{array}\end{array}$$など、論理関数を和項の積として表示したものを言います。

特に、和項を最大限用いて(2)式を表したものを和積標準形と言います。

標準形の求め方

積和標準形の求め方

カルノー図を用いる方法

院試では、この方法を用いることが多いです。

n変数ならば、$2^n$のマスを用意し、出力1を返す入力の組み合わせのマスに1を入れます。

1が隣接するマスを2の倍数ずつ囲み、囲んだマスで変数が変化しないものを項として抽出します。

注意点としては、上から順に入力変数の組み合わせが(00,01,“11”,10)になる順にマスを作っていくことです。

これは、2つの入力変数を片方ずつ変えなければいけないルールに基づいた記載になっています。

丸を囲む意味として、$x_1{x}_2=(1,1)(1,0)$を満たす項$x_1{x}_2+x_1\overline{x_2}=x_1(x_2+\overline{x_2})=x_1$

のように、補元律$x_1+\overline{x_1}=1$を取ることに対応しています。これを繰り返すことで式を簡単化できます。

クワイン・マクラスキー法を用いる方法

こちらの記事で詳細解説しています。本記事では割愛します。

和積標準形の求め方

こちらは、真理値表からすぐに求めることができます。

ただ、入力を反転させたりと、気を付けないといけない部分があります。

<図解>

わざわざ出力0になる入力を選ぶ理由は、ドモルガン律を利用するからです。

出力0になる組み合わせを真理値表を読み取り、論理関数を記載すると$$\begin{array}{}\text{(3)}& \begin{array}{r}\bar{f}=x_{0}x1+x_1{x}_2\end{array}\end{array}$$

のように、左辺が反転しています。

これにNOTを取ると、ドモルガン律を利用して

$$\begin{array}{}\text{(4)}& \begin{array}{rl}\overline{\stackrel{―}{f}}& =\overline{x_0{x}_1+x_1{x}_2}\\ f& =(\overline{x_0{x}_1})(\overline{x_1{x}_2})\\ & =(\overline{x_0}+\overline{x_1})(\overline{x_1}+\overline{x_2})\end{array}\end{array}$$

のように、出力1を返す論理式を和積系で表現することができました。

このように、出力を反転させることを前提にしているので、出力が0になる組み合わせを選ぶということですね。

解答例

積和標準形

与えられた論理関数をカルノー図として表すと下記のようになる。

$(x_0,x_1,x_2)=(0,0,0)\mathrm{と}(0,0,1)、(0,0,1)\mathrm{と}(0,1,1)、(0,0,1)\mathrm{と}(1,0,1)$の3つが隣接しているので、

$$\begin{array}{}\text{(5)}& \begin{array}{r}f(x_0,x_1,x_2)=\overline{x_0}\overline{x_1}+\overline{x_0}{x}_2+\overline{x_1}{x}_2\end{array}\end{array}$$

和積標準形

0になる入力に注目すると、下記のようになる。

$$\begin{array}{}\text{(6)}& \begin{array}{r}f(x_0,x_1,x_2)=(x_0+\overline{x_1}+x_2)(\overline{x_0}+x_1+x_2)(\overline{x_0}+\overline{x_1}+x_2)(\overline{x_0}+\overline{x_1}+\overline{x_2})\end{array}\end{array}$$

最後に

本問は、東北大の院試でよく出題されます。

序盤の問題で出てくることが多いので、必ず得点できるようになりましょう。