13,009
回編集
「回路計算 - ブール代数」の版間の差分
ナビゲーションに移動
検索に移動
→双対論理式
(→双対論理式) |
(→双対論理式) |
||
| 64行目: | 64行目: | ||
実際の回路設計では、この双対性を利用することにより、NANDゲートのみで構成された回路をNORゲートのみの回路に変換することや、その逆を行うことができる。<br> | 実際の回路設計では、この双対性を利用することにより、NANDゲートのみで構成された回路をNORゲートのみの回路に変換することや、その逆を行うことができる。<br> | ||
これは製造プロセスや性能要件に応じて、最適なゲート構成を選択する場合に役立つ。<br> | これは製造プロセスや性能要件に応じて、最適なゲート構成を選択する場合に役立つ。<br> | ||
<br><br> | |||
== 双対定理 == | |||
双対定理は、ブール式において、AND (論理積) と OR (論理和)、0と1を互いに置き換えることで得られる式が等価であることを示す定理である。<br> | |||
<br> | |||
元の式から以下に示す変換を行うことにより、双対な式が得られる。<br> | |||
* ANDをORに | |||
* ORをANDに | |||
* 0を1に | |||
* 1を0に | |||
* 変数はそのままにする。 | |||
<br> | |||
例: | |||
<math>A \cdot B = B \cdot A</math> | |||
上式の双対は | |||
<math>A + B = B + A</math> | |||
<br> | |||
この双対定理は、1つの定理を証明すれば、その双対も自動的に証明されたことになる。<br> | |||
これにより、ブール代数の法則や定理の導出を効率的に行うことができる。<br> | |||
<br> | |||
重要な例として、ド・モルガンの法則がある。<br> | |||
<math>\overline(A \cdot B) = \overline{A} OR \overline{B}</math><br> | |||
この双対は、<math>\overline{A + B} = \overline{A} \cdot \overline{B}</math> となる。<br> | |||
<br> | |||
双対定理は、集合論においても同様の形で成り立つ。<br> | |||
集合の和集合と積集合、全体集合と空集合が、それぞれブール代数におけるORとAND、1と0に対応する。<br> | |||
<br> | |||
例題 1: | |||
<math>A + \overline{A} \cdot B = A + B</math> を示せ。 | |||
一般的な方法: | |||
<math> | |||
\begin{align} | |||
A + \overline{A} \cdot B &= A + A \cdot B + \overline{A} \cdot B \qquad \mbox{(分 配 則 )} \\ | |||
&= A + (A + \overline{A}) \cdot B \qquad \mbox{(吸 収 則 )} \\ | |||
&= A + B \qquad \mbox{(補 元 則 + 恒 等 則 )} | |||
\end{align} | |||
</math> | |||
双対定理を用いた方法: | |||
<math>A + \overline{A} \cdot B = A + B</math> に対して双対定理を使用すると、<math>A(\overline{A} + B) = A \cdot B</math> となる。 | |||
<math> | |||
\begin{align} | |||
A \cdot (\overline{A} + B) &= A \cdot \overline{A} + A \cdot B \qquad \mbox{(分 配 則 )}\\ | |||
&= A \cdot B \qquad \mbox{(補 元 則 + 恒 等 則 )} | |||
\end{align} | |||
</math> | |||
<br><br> | <br><br> | ||