主乗法標準形

logic

真理値表から論理式を作成するとき、主乗法標準形は真理値表の出力値が0の行に注目して論理式を表現します。主乗法標準形は、真理値表で出力が0になっているすべての行の入力の最大項を求め、それらをすべて論理積(AND)することで真理値表と同じ論理式を表します。

2入力の真理値表の例

表1は、2入力XORゲートの真理値表です。AとBがXORゲートの入力、Zが出力です。表の最大項は、Zが0になるように各行のAとBの組み合わせを論理和(OR)したものです。

*表1では、参考のためにすべての行について最大項を表記していますが、実際にはZ=0の行以外は最大項を考慮する必要はありません。

表1: 2入力XORゲートの真理値表
A B Z 最大項
0 0 0  \(A+B\)
0 1 1  \(A+\overline{B}\)
1 0 1  \(\overline{A}+B\)
1 1 0  \(\overline{A}+\overline{B}\)

表1は、1行目と4行目のAとBの組み合わせでZ=0です。1行目と4行目の最大項はそれぞれ次のようになります。

  • 1行目の組み合わせ: \(A+B = z1\) (結果をz1とする)
  • 4行目の組み合わせ:\(\overline{A}+\overline{B} = z2\) (結果をz2とする)

z1とz2をANDすると、XORは主乗法標準形の論理式で次のように表されます。

$$Z = z1 \bullet z2 = (A + B) (\overline{A} \bullet \overline{B})\ \ \ \ \ \text{(1)}$$

式(1)から、XORゲートは2つのORゲート、2つのNOTゲート、1つのANDゲートで実現できることがわかります。

3入力の真理値表の例

表2は、マルチプレクサ(セレクタ)と呼ばれる論理回路の真理値表です。
入力S=0の時、入力AをZから出力し、入力S=1の時、入力BをZから出力します。この真理値表を主乗法標準形の論理式で表します。

*表2では、参考のためにすべての行について最大項を表記していますが、実際にはZ=0の行以外は最大項を考慮する必要はありません。

表2: マルチプレクサの真理値表
S A B Z 最大項
0 0 0 0 \(S+A+B\)
0 0 1 0 \(S+A+ \overline{B}\)
0 1 0 1 \(S+ \overline{A}+B\)
0 1 1 1 \(S+ \overline{A}+\overline{B}\)
1 0 0 0 \( \overline{S} + A + B \)
1 0 1 1 \( \overline{S} + A + \overline{B} \)
1 1 0 0 \( \overline{S} + \overline{A} + B  \)
1 1 1 1 \( \overline{S} + \overline{A} + \overline{B}  \)

表2は、1行目、2行目、5行目、7行目の出力Zが0です。まず、これらの行についてそれぞれ最大項を求めます。

  • 1行目の組み合わせ: \(S+A+B = z1\) (結果をz1とする)
  • 2行目の組み合わせ: \(S+A+ \overline{B} = z2\) (結果をz2とする)
  • 5行目の組み合わせ: \(\overline{S}+A+B = z3\) (結果をz3とする)
  • 7行目の組み合わせ: \(\overline{S} + \overline{A}+B = z4\)(結果をz4とする)

次に、z1,z2,z3,z4をANDします。

\begin{equation}
\begin{split}
Z
&= z1 \bullet z2 \bullet z3 \bullet z4\\
&= (S+A+B) (S+A+ \overline{B}) (\overline{S}+A+B) (\overline{S} + \overline{A}+B)\ \ \ \ \ \text{(2)}
\end{split}
\end{equation}

ブール代数の相殺則を適用すると、(2)は次のように最適化することができます。

\begin{equation}
\begin{split}
Z
&= (S+A+B) (S+A+ \overline{B})  (\overline{S}+A+B)  (\overline{S} + \overline{A}+B)\\
&= (S+A) (\overline{S}+B)\ \ \ \ \ \text{(3)}
\end{split}
\end{equation}

タイトルとURLをコピーしました