月別: 2021年5月

論理演算

/ tau / コメントする

記号定義

以降の議論で以下の様に記号を定義する。

  • 変数Aの否定(not)→\overline{A}
  • 変数AとBの論理積(and)→ABまたはA \cdot B
  • 変数AとBの論理和(or)→A + B
  • 変数AとBの吐いた論理和(xor)→A \oplus B

基本演算の真理値表

not/and/or

not、and、orの真理値表は以下のとおり。T、FはTrue(真)、False(偽)を表す。

    \begin{align*} \begin{array}{c|c} A & \overline{A} \\ \hline T & F \\ F & T \end{array} \qquad \begin{array}{cc|cc} A & B & AB& A+B \\ \hline T & T & T & T\\ T & F & F & T\\ F & T & F & T\\ F & F & F & F\\ \end{array} \end{align}

排他論理和(exclusive or)

2つの変数の真偽値が「異なるときに真、同じ時に偽」となる演算。

    \begin{align*} \begin{array}{cc|c} A & B & A \oplus B \\ \hline T & T & F \\ T & F & T \\ F & T & T \\ F & F & F \end{array} \end{align}

各種法則

基本

(1)   \begin{align*} \overline{\overline{A}} = A ,\quad \begin{array}{c} AA = A \\ A \overline{A} = F \end{array} ,\quad \begin{array}{c} A + A = A \\ A + \overline{A} = T \end{array} \end{align*} \begin{align*} \begin{array}{l} AT =A \\ AF =F \end{array} \quad \begin{array}{l} A + T = T \\ A + F = A \end{array} \end{align*}

交換法則

(2)   \begin{align*} AB = BA \quad A + B = B + A \end{align*}

結合法則

(3)   \begin{gather*} (AB)C = A(BC) \\ (A + B) + C = A + (B + C) \end{gather*}

＜確認＞

    \begin{align*} \begin{array}{ccc|cc|cc} A & B & C & AB & (AB)C & (BC) & A(BC)\\ \hline T & T & T & T &T & T & T\\ T & T & F & T & F & F & F\\ T & F & T & F & F & F & F\\ T & F & F & F & F & F & F\\ F & T & T & F & F & T & F\\ F & T & F & F & F & F & F\\ F & F & T & F & F & F & F\\ F & F & F & F & F & F & F\\ \end{array} \end{align} \begin{align*} \begin{array}{ccc|cc|cc} A & B & C & A+B & (A+B)+C & (B+C) & A+(B+C)\\ \hline T & T & T & T & T & T & T\\ T & T & F & T & T & T & T\\ T & F & T & T & T & T & T\\ T & F & F & T & T & F & T\\ F & T & T & T & T & T & T\\ F & T & F & T & T & T & T\\ F & F & T & F & T & T & T\\ F & F & F & F & F & F & F\\ \end{array} \end{align}

分配法則

(4)   \begin{align*} A(B + C) = AB + AC \end{align*}

＜確認＞

    \begin{align*} \begin{array}{ccc|cc|ccc} A & B & C & B+C & A(B+C) & AB & AC & AB+AC\\ \hline\hline T & T & T & T & T & T & T & T\\ T & T & F & T & T & T & F & T\\ T & F & T & T & T & F & T & T\\ T & F & F & F & F & F & F & F\\ F & T & T & T & F & F & F & F\\ F & T & F & T & F & F & F & F\\ F & F & T & F & F & F & F & F\\ F & F & F & F & F & F & F & F\\ \end{array} \end{align}

ド・モルガンの法則(De Morgan’s laws)

ド・モルガンの法則はandとorの相互変換に関するもので、論理式の変形の基本手順として使われる。

(5)   \begin{align*} \overline{A \cdot B} = \overline{A} + \overline{B} ,\quad \overline{A+B} = \overline{A} \cdot \overline{B} \end{align*}

＜確認＞

    \begin{align*} \begin{array}{cc|cc|cc|cc} A & B & \overline{A} & \overline{B} & \overline{A \cdot B} & \overline{A} + \overline{B} & \overline{A + B} & \overline{A} \cdot \overline{B} \\ \hline T & T & F & F & F & F & F & F \\ T & F & F & T & T & T & F & F \\ F & T & T & F & T & T & F & F \\ F & F & T & T & T & T &T & T \end{array} \end{align}

ド・モルガンの法則による式変形

変形の基本

ド・モルガンの法則を利用して論理式を変形していくのに、以下の変形手順が用いられる。

＜否定の否定＞

(6)   \begin{align*} \begin{array}{l} A \cdot B = \overline{\overline{A \cdot B}} = \overline{\overline{A} + \overline{B}} \\ A + B = \overline{\overline{A + B}} = \overline{\overline{A} \cdot \overline{B}} \\ \end{array} \end{align*}

＜Falseとのor＞

(7)   \begin{align*} A \cdot \overline{B} = A \cdot \overline{B} + A \cdot \overline{A} = A (\overline{B} + \overline{A}) \end{align*}

NANDゲート化

NANDゲートは、A、B2つの入力のandのnotを出力するゲートで、任意の論理回路をNANDゲートの組み合わせで実装できる(完全性：completeness)。

例えばnot、and、or、xorの基本演算を、ド・モルガンの低利で変形してNANDゲートのみで表してみる。

(8)   \begin{gather*} \overline{A} = \overline{A \cdot A} \\ A \cdot B = \overline{\overline{A \cdot B}} \\ A + B = \overline{\overline{A + B}} = \overline{\overline{A} \cdot \overline{B}} \end{gather*}

これらをゲート図で表すと以下のようになる。

真偽表の変換

変換の考え方

排他論理和(XOR)の演算をNANDゲートで構成することを考える。AとBに対するTrue、Falseの組み合わせのうち結果がTrueとなるものだけを抜き出すと、(A, B) = (T, F), (F, T)。それぞれの入力に対して結果がTrueとなるためには以下のいずれか満たされる必要がある。

(9)   \begin{equation*} \left\{ \begin{array}{l} A \cdot \overline{B} = T \\ \overline{A} \cdot B = T \end{array} \end{equation*}

これらのいずれかが成立すれば(左辺の論理和を取れば)Trueの結果となり、Falseとなる結果は論理和をとっても変わらないので、XORの出力は以下のように表現される。

(10)   \begin{equation*} A \oplus B = A \cdot \overline{B} +\overline{A} \cdot B \end{equation*}

この式に真偽値表の組み合わせを入れると、XORの結果になることが確認できる。

NANDゲートへの変換1

この式をド・モルガンの定理を使って変形すると以下のようになる。

(11)   \begin{align*} A \cdot \overline{B} +\overline{A} \cdot B &= \overline{\overline{A \cdot \overline{B} +\overline{A} \cdot B}} \\ &= \overline{ \overline{A \cdot \overline{B}} \cdot \overline{\overline{A} \cdot B}} \end{align*}

真理値表の確認。

    \begin{gather*} \begin{array}{cc|cc|cc|c} A & B & \overline{A} & \overline{B} & \overline{A \cdot \overline{B}} & \overline{\overline{A} \cdot B} & \overline{ \overline{A \cdot \overline{B}} \cdot \overline{\overline{A} \cdot B}}\\ \hline T & T & F & F & T & T & F \\ T & F & F & T & F & T & T \\ F & T & T & F & T & F & T \\ F & F & T & T & T & T & F \end{array} \end{gather}

式(11)をNANDゲートによる回路図で表すと以下の通り。2つのNOTはNANDゲートで作ることができ、5つのNANDゲートを使う。

NANDゲートへの変換2

一方、式(11)の2つのNANDの中を以下のように変形する。

(12)   \begin{align*} A \cdot \overline{B} &= A \cdot \overline{B} + A \cdot \overline{A} = A \cdot (\overline{A} + \overline{B}) = A \cdot \overline{A \cdot B} \\ \overline{A} \cdot B &= \overline{B} \cdot B + \overline{A} \cdot B = (\overline{A} + \overline{B}) \cdot B = \overline{A \cdot B} \cdot B \end{align*}

これらにより、XORは以下のようにも表せる。

(13)   \begin{align*} A \cdot \overline{B} +\overline{A} \cdot B &= \overline{ \overline{A \cdot \overline{B}} \cdot \overline{\overline{A} \cdot B}} \\ &= \overline{\overline{A \cdot \overline{A \cdot B}} \cdot \overline{\overline{A \cdot B} \cdot B}} \end{align*}

式(12)をNANDゲートによる回路図で表すと以下の通り。式(11)の場合に比べてNANDゲートが4つですむ。