主加法標準形

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

2入力の真理値表の例

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

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

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

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

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

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

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

3入力の真理値表の例

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

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

表2は、3行目、4行目、6行目、8行目の出力Zが1です。まず、これらの行についてそれぞれ最小項を求めます。

• 3行目の組み合わせ: \(\overline{S} \cdot A \cdot \overline{B} = z1\) (結果をz1とする)
• 4行目の組み合わせ: \(\overline{S} \cdot A \cdot B = z2\) (結果をz2とする)
• 6行目の組み合わせ: \(S \cdot \overline{A} \cdot B = z3\) (結果をz3とする)
• 8行目の組み合わせ: \(S \cdot A \cdot B = z4\) (結果をz4とする)

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

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

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

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