なぜスマートフォンは計算ができるのでしょうか？ なぜ画像を処理し、音声を認識し、世界中と通信できるのでしょうか？ その根底には「すべての複雑な処理を、0 と 1 のたった2つの値の組合せに帰着させる」というデジタル回路の思想があります。
電圧の高低、スイッチのオン・オフ、コンデンサの充放電 — いずれも「2つの安定した状態」を持つ物理現象を利用して、私たちは数学的に完璧な論理演算を実現しています。しかし、複雑なシステムを設計するためには、回路を闇雲につなぎ合わせるわけにはいきません。論理ゲートを組み合わせて任意の論理機能を実現するための数学的枠組み — ブール代数 — と、論理式を最も少ないゲートで実現するための体系的手法 — カルノー図 — が不可欠です。
デジタル回路の基礎を理解すると、以下のような幅広い分野の設計力が身につきます。
- コンピュータアーキテクチャ: CPU内部の演算器（ALU）やレジスタファイルは、本記事で扱う加算器やマルチプレクサの組合せで構成されています
- FPGA設計: ルックアップテーブル（LUT）の中身は本記事で学ぶ真理値表そのものであり、論理式の簡単化がそのまま回路の効率に直結します
- 組込みシステム: マイコン周辺のデコーダやアドレスセレクタの設計に、ブール代数の知識が必要です
- 通信工学: 誤り検出・訂正回路（CRC、パリティ）はXORゲートの巧みな組合せで実現されています
本記事の内容
- アナログ回路とデジタル回路の本質的な違い — なぜ0と1で処理するのか
- 基本論理ゲート（AND, OR, NOT, NAND, NOR, XOR, XNOR）の動作と真理値表
- ブール代数の公理と法則 — ド・モルガンの定理の直感と証明
- 論理式の簡単化の手順（代数的手法とカルノー図法）
- ドントケア条件の活用
- 組合せ回路の設計実例（半加算器、全加算器、デコーダ、マルチプレクサ）
- CMOS論理回路によるゲートの物理的実現
- Python によるブール代数演算・真理値表の自動生成・カルノー図の可視化
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- FET・MOSFETの動作原理 — MOSFETのスイッチング動作とCMOSの概念
アナログ回路 vs デジタル回路 — なぜ0と1で処理するのか
アナログの世界とデジタルの世界
自然界の物理量 — 温度、気圧、光の強度 — は連続的な値をとります。アナログ回路はこの連続値をそのまま電圧や電流で表現し、処理します。たとえばアナログのラジオ受信機では、受信電波の電圧波形をそのまま増幅してスピーカーに流します。
一方、デジタル回路は信号を「High（1）」と「Low（0）」の2つの離散的な状態だけで表現します。なぜわざわざ連続的な情報を捨てて、2値に丸めてしまうのでしょうか？
デジタル化の3つの利点
第1の利点はノイズ耐性です。 アナログ回路では、信号に重畳したノイズは信号そのものと区別がつかず、増幅するたびにノイズも一緒に増えてしまいます。ところがデジタル回路では、ある閾値を境にして「これは1」「これは0」と判定するため、閾値範囲内のノイズは完全に無視できます。たとえば $0$ V 〜 $0.8$ V を Low、$2.0$ V 〜 $3.3$ V を High と判定するなら、$0.5$ V 程度のノイズが乗っても正しく読み取れます。
第2の利点は再現性です。 デジタル回路の出力は 0 か 1 なので、何段の回路を通しても信号が劣化しません。アナログ回路ではアンプを10段直列に繋ぐと歪みやノイズが蓄積しますが、デジタル回路ではバッファ（0/1をそのまま出力する回路）を何段挟んでも情報は完全に保存されます。
第3の利点はプログラマビリティです。 同じハードウェアでも、プログラム（メモリに格納された0と1の列）を変えるだけで異なる処理を実行できます。これがコンピュータの本質であり、アナログ回路では実現困難な柔軟性です。
正論理と負論理
デジタル回路では、電圧レベルと論理値（0, 1）の対応を「論理」として定義します。正論理（positive logic）では高電圧を1、低電圧を0に対応させます。これが最も一般的な方式です。逆に低電圧を1とする負論理（negative logic）も存在しますが、本記事では断りのない限り正論理を前提とします。
ここまでで、デジタル回路が「なぜ0と1の2値で処理するのか」が理解できました。次に、この0と1を入力として受け取り、特定のルールに従って0か1を出力する「論理ゲート」を見ていきましょう。
基本論理ゲート — デジタル回路の最小構成要素
論理ゲートとは
論理ゲート（logic gate）は、1つまたは複数の2値入力を受け取り、1つの2値出力を返す回路です。料理に例えるなら、論理ゲートは「包丁」や「鍋」のような基本調理器具にあたります。単体では料理にならなくても、組み合わせ方次第であらゆる料理（回路機能）を作れます。
デジタル回路のすべて — CPUもメモリもGPUも — は、以下で紹介する数種類の論理ゲートの組合せで構成されています。
NOT ゲート（インバータ）
最もシンプルな論理ゲートが NOT ゲート（インバータ） です。1入力1出力で、入力の論理値を反転します。
$$ Y = \overline{A} $$
真理値表は次のとおりです。
| $A$ | $Y = \overline{A}$ |
|---|---|
| 0 | 1 |
| 1 | 0 |
スイッチに例えると、「スイッチがOFFのときランプが点き、ONのとき消える」という動作です。冷蔵庫のドアスイッチがまさにこれで、ドアを閉める（スイッチON）とライトが消え、開ける（スイッチOFF）と点灯します。
AND ゲート
AND ゲート は2つ以上の入力がすべて1のときだけ出力が1になるゲートです。論理積とも呼ばれます。
$$ Y = A \cdot B $$
| $A$ | $B$ | $Y = A \cdot B$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
日常の例を挙げると、「鍵を回す AND ドアノブを回す」の両方をやって初めてドアが開く、という状況です。どちらか一方だけではドアは開きません。
OR ゲート
OR ゲート は2つ以上の入力のうち、少なくとも1つが1であれば出力が1になるゲートです。論理和とも呼ばれます。
$$ Y = A + B $$
| $A$ | $B$ | $Y = A + B$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
「非常口が2つある部屋」を想像してください。出口Aが開いている OR 出口Bが開いている、のどちらかが成り立てば脱出できます。
NAND ゲート
NAND ゲート は AND ゲートの出力を反転したものです。すべての入力が1のときだけ出力が0になります。
$$ Y = \overline{A \cdot B} $$
| $A$ | $B$ | $Y = \overline{A \cdot B}$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NANDゲートは ユニバーサルゲート（万能ゲート） と呼ばれます。NANDゲートだけで AND, OR, NOT を含むあらゆる論理関数を実現できるからです。実際のCMOS集積回路の設計では、NANDゲートが最も基本的な構成要素として使われています。その理由は後のCMOSセクションで詳しく説明します。
NOR ゲート
NOR ゲート は OR ゲートの出力を反転したものです。すべての入力が0のときだけ出力が1になります。
$$ Y = \overline{A + B} $$
| $A$ | $B$ | $Y = \overline{A + B}$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
NORゲートもNANDと同じくユニバーサルゲートです。歴史的には、アポロ誘導コンピュータ（AGC）がNORゲートだけで構成されていたことで有名です。
XOR ゲート（排他的論理和）
XOR ゲート は、2つの入力が異なるときだけ出力が1になるゲートです。
$$ Y = A \oplus B = A\overline{B} + \overline{A}B $$
| $A$ | $B$ | $Y = A \oplus B$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XORは「2人でじゃんけんして、あいこでないときだけポイントが入る」ルールに似ています。同じ手なら0、違う手なら1です。XOR ゲートは加算器やパリティチェック回路の心臓部であり、デジタル回路設計で極めて重要な役割を果たします。
XNOR ゲート（排他的論理和の否定）
XNOR ゲート は XOR の出力を反転したもので、2つの入力が同じときに出力が1になります。いわば「一致検出器」です。
$$ Y = \overline{A \oplus B} = A \cdot B + \overline{A} \cdot \overline{B} $$
| $A$ | $B$ | $Y = \overline{A \oplus B}$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
ここまでで7種類の基本論理ゲートを学びました。しかし、現実の設計では何十何百もの入力を扱う論理関数が登場します。そのとき、真理値表を眺めるだけでは効率よく回路を設計できません。論理式を代数的に操作し、簡単化するための数学的枠組み — ブール代数 — が必要になります。
ブール代数の基礎 — 論理式を操作する数学
ブール代数とは
19世紀のイギリスの数学者ジョージ・ブールは、論理的推論を代数のように記号で操作する方法を考案しました。通常の代数では変数が実数値をとりますが、ブール代数では変数は 0 と 1 の2値しかとりません。加算（+）は OR、乗算（$\cdot$）は AND、上線（$\overline{\ }$）は NOT に対応します。
この対応さえ理解すれば、通常の代数と似た感覚で論理式を変形・簡単化できます。ただし、通常の代数とは異なるルールもあるので注意が必要です。
ブール代数の基本法則
以下にブール代数の主要な法則をまとめます。各法則は AND（$\cdot$）と OR（+）の双対性（duality）を持っています。
同一律（Identity）:
$$ A + 0 = A, \quad A \cdot 1 = A $$
0 を OR しても値は変わらず、1 を AND しても値は変わりません。
零元・一元の法則（Null / Dominant）:
$$ A + 1 = 1, \quad A \cdot 0 = 0 $$
べき等律（Idempotent）:
$$ A + A = A, \quad A \cdot A = A $$
通常の代数では $A + A = 2A$ ですが、ブール代数では $A + A = A$ です。ここが大きな違いです。
補元律（Complement）:
$$ A + \overline{A} = 1, \quad A \cdot \overline{A} = 0 $$
ある命題とその否定の OR は常に真、AND は常に偽です。
交換律（Commutative）:
$$ A + B = B + A, \quad A \cdot B = B \cdot A $$
結合律（Associative）:
$$ (A + B) + C = A + (B + C), \quad (A \cdot B) \cdot C = A \cdot (B \cdot C) $$
分配律（Distributive）:
$$ A \cdot (B + C) = A \cdot B + A \cdot C $$
ここまでは通常の代数と同じです。しかし、ブール代数にはもう1つの分配律があります。
$$ A + (B \cdot C) = (A + B) \cdot (A + C) $$
通常の代数では $A + BC \neq (A+B)(A+C)$ ですが、ブール代数ではこれが成立します。直感的には、右辺を展開すると $AA + AC + AB + BC = A + AC + AB + BC$ であり、吸収律（後述）によって $A + AC = A$, $A + AB = A$ なので $A + BC$ に帰着する、と確認できます。
吸収律（Absorption）:
$$ A + A \cdot B = A, \quad A \cdot (A + B) = A $$
吸収律は論理式の簡単化で頻繁に登場します。第1式の直感は「$A$ が1なら $AB$ の値に関係なく出力は1、$A$ が0なら $AB$ も0だから、$AB$ の項は冗長」ということです。
これらの法則を使いこなせるようになると、複雑な論理式を手作業で整理できるようになります。しかし、ブール代数の法則の中で最も強力かつ重要なのが、次に紹介するド・モルガンの定理です。
ド・モルガンの定理 — AND と OR を自在に変換する
ド・モルガンの定理は、AND と OR を否定を通じて相互変換する法則です。
$$ \overline{A \cdot B} = \overline{A} + \overline{B} $$
$$ \overline{A + B} = \overline{A} \cdot \overline{B} $$
第1式を直感的に読むと「$A$ と $B$ が同時に1でないこと」は「$A$ が0、または $B$ が0」と同じことを述べています。
この定理がなぜ重要かというと、NANDゲートやNORゲートを使って任意の論理回路を構成するときに不可欠だからです。たとえば、NANDゲート（$\overline{A \cdot B}$）をド・モルガンで読み替えると $\overline{A} + \overline{B}$ であり、これは「入力を反転してからORをとる」のと等価です。この変換を駆使すれば、NANDゲートだけであらゆる論理関数を実現できます。
ド・モルガンの定理の証明
真理値表による完全枚挙で証明します。第1式 $\overline{A \cdot B} = \overline{A} + \overline{B}$ を確かめましょう。
| $A$ | $B$ | $A \cdot B$ | $\overline{A \cdot B}$ | $\overline{A}$ | $\overline{B}$ | $\overline{A} + \overline{B}$ |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
$\overline{A \cdot B}$ の列と $\overline{A} + \overline{B}$ の列がすべての行で一致するため、定理は成立します。第2式も同様に4行すべてで一致を確認できます。
ド・モルガンの定理は2変数に限らず、$n$ 変数に一般化できます。
$$ \overline{A_1 \cdot A_2 \cdots A_n} = \overline{A_1} + \overline{A_2} + \cdots + \overline{A_n} $$
$$ \overline{A_1 + A_2 + \cdots + A_n} = \overline{A_1} \cdot \overline{A_2} \cdots \overline{A_n} $$
この一般化を使えば、多入力の複雑な論理式も AND/OR の変換が自在にできます。
ブール代数の法則を手に入れたところで、次の課題は「与えられた論理関数をいかに少ないゲートで実現するか」です。まずは代数的な手法を見てから、より視覚的で確実なカルノー図法に進みましょう。
論理式の簡単化 — 代数的手法
なぜ簡単化が必要か
真理値表から論理式を直接書き下すことは機械的にできます。$n$ 入力の論理関数に対して、出力が1になる各行について入力変数の積（AND）をとり、それらの和（OR）をとればよいのです。この形式を 加法標準形（SOP: Sum of Products） と呼びます。各積項を最小項（minterm）と呼びます。
しかし、得られたSOP式は一般に冗長です。冗長な式はそのまま回路にすると、ゲート数が増え、消費電力が増大し、信号の遅延が大きくなります。FPGA では論理セルの消費量が増え、ASIC ではチップ面積とコストが増大します。
代数的簡単化の例
具体的な例で簡単化の手順を見てみましょう。3変数の論理関数が次のSOP式で与えられたとします。
$$ F = A\overline{B}C + A\overline{B}\overline{C} + AB\overline{C} + ABC $$
ステップ1: 第1項と第2項に注目します。$A\overline{B}$ が共通因子なので括り出します。
$$ A\overline{B}C + A\overline{B}\overline{C} = A\overline{B}(C + \overline{C}) $$
補元律 $C + \overline{C} = 1$ を適用すると、次のように簡単化されます。
$$ A\overline{B}(C + \overline{C}) = A\overline{B} \cdot 1 = A\overline{B} $$
ステップ2: 同様に、第3項と第4項から $A$ と $\overline{C}$ の共通因子をそれぞれ見つけます。第3項と第4項は $AB$ が共通です。
$$ AB\overline{C} + ABC = AB(\overline{C} + C) = AB $$
ステップ3: ここまでの結果を合わせると次のようになります。
$$ F = A\overline{B} + AB $$
再び $A$ を括り出します。
$$ F = A(\overline{B} + B) = A \cdot 1 = A $$
4つの積項からなる式が、たった1変数 $A$ に簡単化されました。元の式のゲート数は AND ゲート4個 + OR ゲート1個 + NOT ゲート数個でしたが、簡単化後は入力 $A$ をそのまま出力に接続するだけです。
代数的手法は万能ですが、3変数以上になると「どの項を組み合わせるか」の見通しが難しくなります。特に、括り出す組合せを見落とすと最簡形に到達できません。そこで、より体系的かつ視覚的に最簡形を求められるカルノー図法が重要になります。
カルノー図法 — 視覚的に最簡形を求める
カルノー図の考え方
カルノー図（Karnaugh map, K-map）は、1953年にモーリス・カルノーが提案した論理式の簡単化手法です。真理値表の情報を2次元の格子に配置し、隣接するセルをグループ化することで簡単化を行います。
カルノー図のポイントは、隣接するセルが1ビットだけ異なるように配置されていることです。この配置（グレイコード順）のおかげで、隣接する2つのセルをまとめると1変数が消去されます。4つの隣接セルをまとめると2変数が消去され、8つなら3変数が消去されます。つまり、$2^k$ 個の隣接セルのグループは $k$ 個の変数を消去します。
2変数カルノー図
最も単純な2変数の例で手順を確認しましょう。
2変数 $A$, $B$ のカルノー図は $2 \times 2$ の格子です。
$$ \begin{array}{c|c|c} & B=0 & B=1 \\ \hline A=0 & m_0 & m_1 \\ \hline A=1 & m_2 & m_3 \\ \end{array} $$
ここで $m_i$ は最小項の値（0 または 1）です。たとえば $F = \overline{A}B + AB = B$ を確認してみると、$m_1 = 1, m_3 = 1$（$B=1$ の列がすべて1）なので、$B=1$ の列全体を囲めば $F = B$ が得られます。
3変数カルノー図
3変数 $A$, $B$, $C$ の場合、$2 \times 4$ の格子になります。列の順序が グレイコード（00, 01, 11, 10）であることに注意してください。
$$ \begin{array}{c|c|c|c|c} & BC=00 & BC=01 & BC=11 & BC=10 \\ \hline A=0 & m_0 & m_1 & m_3 & m_2 \\ \hline A=1 & m_4 & m_5 & m_7 & m_6 \\ \end{array} $$
グレイコードを使う理由は、隣り合う列が必ず1ビットしか違わないようにするためです。通常の2進数順（00, 01, 10, 11）では、01→10 の間で2ビット変化してしまい、隣接セルの簡単化規則が使えなくなります。
4変数カルノー図
4変数 $A$, $B$, $C$, $D$ のカルノー図は $4 \times 4$ の格子です。
$$ \begin{array}{c|c|c|c|c} & CD=00 & CD=01 & CD=11 & CD=10 \\ \hline AB=00 & m_0 & m_1 & m_3 & m_2 \\ \hline AB=01 & m_4 & m_5 & m_7 & m_6 \\ \hline AB=11 & m_{12} & m_{13} & m_{15} & m_{14} \\ \hline AB=10 & m_8 & m_9 & m_{11} & m_{10} \\ \end{array} $$
ここで重要なのは、カルノー図は上下と左右が繋がっている（トーラス状）とみなすことです。最上行と最下行、最左列と最右列も隣接しています。
カルノー図の使い方 — 手順
- 真理値表から、出力が1になるセルに1を書き入れる
- 隣接する1のセルを、$2^k$ 個の矩形グループ（$k = 0, 1, 2, \ldots$）にまとめる
- できるだけ大きなグループを優先する（大きいほど多くの変数が消去される）
- すべての1がいずれかのグループに含まれるまで繰り返す（1つの1が複数グループに含まれてもよい）
- 各グループに対して、グループ内で値が変化しない変数だけを残した積項を作る
- すべてのグループの積項を OR で結合する
具体例：4変数のカルノー図による簡単化
次の論理関数を簡単化してみましょう。
$$ F(A,B,C,D) = \sum m(0, 1, 2, 5, 8, 9, 10) $$
これは最小項番号 0, 1, 2, 5, 8, 9, 10 で出力が1になることを意味します。カルノー図に書き込むと次のようになります。
$$ \begin{array}{c|c|c|c|c} & CD=00 & CD=01 & CD=11 & CD=10 \\ \hline AB=00 & 1 & 1 & 0 & 1 \\ \hline AB=01 & 0 & 1 & 0 & 0 \\ \hline AB=11 & 0 & 0 & 0 & 0 \\ \hline AB=10 & 1 & 1 & 0 & 1 \\ \end{array} $$
グループ1: $m_0, m_1, m_8, m_9$（左上と左下の2列、上下がつながっているので隣接）。$A$ は0と1の両方、$B=0$, $C=0$, $D$ は0と1の両方 → 残る変数は $\overline{B}\overline{C}$
グループ2: $m_0, m_2, m_8, m_{10}$（$D=0$ の列と $CD=10$ の列、左右がつながっている）。$A$ は0と1, $B=0$, $C$ は0と1, $D=0$ → 残る変数は $\overline{B}\overline{D}$
グループ3: $m_5$ は $m_1$ と隣接。$m_1, m_5$ をグループ化。$A$ は0と1の…いえ、$m_1$ は $AB=00, CD=01$ で $m_5$ は $AB=01, CD=01$ です。$B$ は0と1, $A=0$…いえ、正確に見直しましょう。$m_1$: $ABCD = 0001$, $m_5$: $ABCD = 0101$。変化するのは $B$ のみ、$A=0, C=0, D=1$ が共通 → 残る変数は $\overline{A}\overline{C}D$
結果として簡単化された式は次のようになります。
$$ F = \overline{B}\overline{C} + \overline{B}\overline{D} + \overline{A}\overline{C}D $$
ここで吸収律を確認すると、これ以上の簡単化は不要です。元の7項のSOP式が3項に減りました。
カルノー図は視覚的に簡単化を行えるため、代数的手法のように「括り出す組合せの見落とし」が起きにくいという大きな利点があります。しかし、5変数以上ではカルノー図の可視化が困難になるため、実用上は4変数までが限界です。5変数以上の場合はクワイン・マクラスキー法などのアルゴリズム的手法を使います。
次に、カルノー図をさらに効果的に活用するための「ドントケア条件」について見ていきましょう。
ドントケア条件 — 曖昧さを味方にする
ドントケアとは
実際の設計では、ある入力の組合せが物理的に起こり得ない場合があります。たとえば、BCD（Binary-Coded Decimal）では4ビットで0〜9の10通りの十進数を表現しますが、1010〜1111の6通りの入力は正常な動作では発生しません。このような「出力を0にしても1にしても構わない」条件を ドントケア条件（don’t care condition） と呼び、カルノー図では「$d$」や「$\times$」で記入します。
ドントケアの活用
ドントケア条件のセルは、グループを大きくするために1としても0としても扱える自由度があります。この自由度を利用すると、より大きなグループが作れるため、さらに簡単な論理式が得られます。
たとえば、BCDの入力（0〜9）に対して、$F$ が 1, 3, 5, 7, 9 で1になる関数（奇数検出器）を考えます。ドントケア条件は $m_{10}, m_{11}, m_{12}, m_{13}, m_{14}, m_{15}$ です。
ドントケアを使わない場合の最簡形と、ドントケアをうまく1として利用した場合の最簡形では、後者のほうがゲート数が少なくなる可能性があります。この例では、最下位ビット $D$ が1のときに出力が1なので、$F = D$ という極めて単純な式になります。ドントケア条件 $m_{11}, m_{13}, m_{15}$（$D=1$）を1として扱うことで、$D=1$ の列が完全に1で埋まるからです。
ドントケア条件を適切に利用することは、実務のデジタル回路設計において非常に重要な最適化テクニックです。
ここまでで論理式の簡単化の手法を身につけました。次は、これらの手法を使って実用的な組合せ回路を設計してみましょう。
組合せ回路の設計 — 加算器・デコーダ・マルチプレクサ
組合せ回路とは
組合せ回路（combinational circuit） とは、現在の入力の組合せだけで出力が一意に決まる回路です。過去の入力の履歴（状態）に依存しません。真理値表1つで完全に動作が記述できるのが特徴です。
これに対し、過去の入力の履歴を記憶して動作に反映する回路を順序回路（sequential circuit）と呼びます。フリップフロップやカウンタがその代表例で、これらは別記事で解説します。
半加算器（Half Adder）
最も基本的な演算回路が 半加算器 です。1ビットの2数 $A$ と $B$ を加算し、和（Sum）$S$ と桁上げ（Carry）$C$ を出力します。
真理値表を書くと次のようになります。
| $A$ | $B$ | $C$（桁上げ） | $S$（和） |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
真理値表をよく見ると、$S$ の列は XOR そのものであり、$C$ の列は AND そのものです。
$$ S = A \oplus B, \quad C = A \cdot B $$
つまり、半加算器は XOR ゲート1個と AND ゲート1個だけで実現できます。非常にシンプルですが、下位桁からの桁上げ入力を受け付けることができないという制約があります。
全加算器（Full Adder）
全加算器 は、半加算器の制約を解決するために、下位桁からの桁上げ入力 $C_\text{in}$ も含めた3入力の加算器です。
| $A$ | $B$ | $C_\text{in}$ | $C_\text{out}$ | $S$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
$S$ の出力を見ると、3入力の XOR になっていることがわかります。
$$ S = A \oplus B \oplus C_\text{in} $$
$C_\text{out}$ は「3つの入力のうち2つ以上が1」のとき1になります。これを論理式で書くと次のようになります。
$$ C_\text{out} = AB + BC_\text{in} + AC_\text{in} = AB + (A \oplus B)C_\text{in} $$
後者の形は「半加算器2つとORゲート1つ」という構成を表しています。第1の半加算器で $A \oplus B$ と $AB$ を求め、第2の半加算器で $(A \oplus B) \oplus C_\text{in}$ と $(A \oplus B)C_\text{in}$ を求め、最後に $AB + (A \oplus B)C_\text{in}$ を OR で結合します。
全加算器を $n$ 個直列に接続し、各段の $C_\text{out}$ を次段の $C_\text{in}$ に接続すると、$n$ ビットの リプルキャリー加算器 が構成できます。これはCPU内のALU（算術論理演算器）の最も基本的な構成方式です。
デコーダ
デコーダ（decoder） は、$n$ ビットの入力を受け取り、$2^n$ 本の出力線のうち対応する1本だけを1にする回路です。アドレスデコーダとしてメモリ回路で広く使われています。
たとえば、2-to-4デコーダは2ビットの入力 $(A_1, A_0)$ に対して4本の出力 $(Y_0, Y_1, Y_2, Y_3)$ を持ちます。
$$ Y_0 = \overline{A_1} \cdot \overline{A_0}, \quad Y_1 = \overline{A_1} \cdot A_0, \quad Y_2 = A_1 \cdot \overline{A_0}, \quad Y_3 = A_1 \cdot A_0 $$
各出力 $Y_i$ はまさに最小項そのものです。つまり、デコーダは「最小項発生器」であり、デコーダの出力を OR ゲートで結合することで、任意の論理関数を実現できます。これが「デコーダ + ORゲート」による論理関数の汎用的な実現方式です。
マルチプレクサ
マルチプレクサ（multiplexer, MUX） は、$2^n$ 個のデータ入力のうち、$n$ ビットの選択信号で指定された1つを出力に接続する回路です。「データの切替器」のイメージです。
2-to-1マルチプレクサは、選択信号 $S$ と2つのデータ入力 $D_0, D_1$ を受け取り、$S$ の値に応じてどちらかを出力します。
$$ Y = \overline{S} \cdot D_0 + S \cdot D_1 $$
$S = 0$ なら $D_0$ が、$S = 1$ なら $D_1$ が出力されます。4-to-1マルチプレクサ（2ビット選択）ではこの考え方を拡張し、次のようになります。
$$ Y = \overline{S_1}\overline{S_0} \cdot D_0 + \overline{S_1}S_0 \cdot D_1 + S_1\overline{S_0} \cdot D_2 + S_1 S_0 \cdot D_3 $$
マルチプレクサも万能回路であり、$2^n$-to-1 MUX で $n$ 変数の任意の論理関数を実現できます。データ入力に真理値表の出力列を接続し、選択信号に入力変数を接続すれば、ルックアップテーブル（LUT）として機能します。FPGAの基本構成要素はまさにこの原理に基づいています。
組合せ回路の設計例を通じて、論理ゲートからブール代数、カルノー図までの知識がどのように実際の回路設計に結びつくかを見てきました。次に、これらの論理ゲートが物理的にどのようにトランジスタで実現されるのかを見ていきましょう。
CMOS 論理回路 — トランジスタで論理ゲートを実現する
CMOS とは
CMOS（Complementary Metal-Oxide-Semiconductor） は、pMOSFET と nMOSFET を相補的に組み合わせた論理回路方式です。現代のほぼすべてのディジタル集積回路（CPU, FPGA, メモリ等）はCMOS技術で製造されています。
CMOSの最大の利点は、定常状態で電流がほとんど流れないことです。出力が1のときは pMOSがON、nMOSがOFF なので電源から出力へのパスだけが形成され、出力が0のときは nMOSがON、pMOSがOFF なので出力からGNDへのパスだけが形成されます。電源からGNDへの貫通電流が流れないため、消費電力が極めて小さくなります。
CMOS インバータ
CMOS 論理回路の最も基本的な構成がインバータ（NOTゲート）です。
pMOSFET のソースを電源 $V_\text{DD}$ に、nMOSFET のソースを GND に接続し、両方のゲートを入力 $A$ に、両方のドレインを出力 $Y$ に接続します。
- $A = 0$（Low）のとき: pMOS が ON、nMOS が OFF → 出力は $V_\text{DD}$ を通じて High（1）
- $A = 1$（High）のとき: pMOS が OFF、nMOS が ON → 出力は GND を通じて Low（0）
これでインバータの動作が実現されます。pMOS は「プルアップネットワーク」、nMOS は「プルダウンネットワーク」を構成し、常にどちらか一方だけが ON になります。
CMOS NAND ゲート
2入力 NAND ゲートでは、nMOS 側が直列、pMOS 側が並列に接続されます。
nMOS側（プルダウンネットワーク）: 2つの nMOS が直列に接続されています。$A=1$ AND $B=1$ のときだけ両方がONになり、出力がGNDに接続されて Low になります。
pMOS側（プルアップネットワーク）: 2つの pMOS が並列に接続されています。$A=0$ OR $B=0$ のときどちらかがONになり、出力が $V_\text{DD}$ に接続されて High になります。
この動作はまさに NAND（$A$ AND $B$ の否定）です。重要なのは、nMOS の直列接続は AND 機能を、pMOS の並列接続は OR 機能を実現し、CMOS構造全体として反転（NOT）が自動的に含まれるということです。
CMOS NOR ゲート
NOR ゲートは NAND と逆で、nMOS 側が並列、pMOS 側が直列になります。
- nMOS 並列: $A=1$ OR $B=1$ で出力が Low
- pMOS 直列: $A=0$ AND $B=0$ のときだけ出力が High
なぜ NAND が CMOS で好まれるか
CMOS では、pMOS は nMOS よりも移動度が小さい（電流を流す能力が低い）ため、同じ駆動能力を得るにはpMOSのチャネル幅を nMOS の約2〜3倍にする必要があります。
NAND ゲートでは pMOS が並列なのでスイッチング速度が速く、NOR ゲートでは pMOS が直列なので遅くなります。そのため、実際の VLSI 設計では NAND ゲートベース の設計が主流です。ド・モルガンの定理を使えば、NOR で表現された論理も NAND に変換できるため、設計の柔軟性は失われません。
CMOSでゲートが物理的に実現できることを確認したので、いよいよPythonを使って本記事で学んだ理論を実装・可視化してみましょう。
Python で学ぶブール代数と論理回路
真理値表の自動生成
まずは任意の論理関数の真理値表を自動生成する関数を実装します。Python のビット演算子（& = AND, | = OR, ^ = XOR, ~ = NOT）を活用します。
import itertools
import numpy as np
import matplotlib.pyplot as plt
def truth_table(n_vars, func, var_names=None):
"""n変数の論理関数の真理値表を生成・表示する"""
if var_names is None:
var_names = [chr(65 + i) for i in range(n_vars)] # A, B, C, ...
print(" | ".join(var_names) + " | F")
print("-" * (4 * n_vars + 5))
results = []
for vals in itertools.product([0, 1], repeat=n_vars):
out = func(*vals)
results.append((*vals, out))
row = " | ".join(str(v) for v in vals) + " | " + str(out)
print(row)
return results
# --- 基本論理ゲートの定義 ---
def AND(a, b): return a & b
def OR(a, b): return a | b
def NOT(a): return 1 - a
def NAND(a, b): return NOT(AND(a, b))
def NOR(a, b): return NOT(OR(a, b))
def XOR(a, b): return a ^ b
def XNOR(a, b): return NOT(XOR(a, b))
# 各ゲートの真理値表を表示
print("=== AND ゲート ===")
truth_table(2, AND, ["A", "B"])
print("\n=== XOR ゲート ===")
truth_table(2, XOR, ["A", "B"])
# 3変数の論理関数の例: F = AB + NOT(A)C
print("\n=== F = AB + ~AC ===")
def f_example(a, b, c):
return OR(AND(a, b), AND(NOT(a), c))
truth_table(3, f_example, ["A", "B", "C"])
上のコードでは、Python のビット演算子を使って基本論理ゲートを関数として定義し、itertools.product で全入力パターンを網羅的に生成しています。truth_table 関数は任意の変数数と論理関数を受け取って真理値表を表示するため、新しい論理関数の動作確認に即座に使えます。XOR ゲートの真理値表では、入力が異なるときだけ出力が1になることが確認でき、3変数の例では $F = AB + \overline{A}C$ の8行の真理値表が正しく生成されることが確認できます。
ド・モルガンの定理の検証
ド・モルガンの定理が本当に成り立つかを、全入力パターンで検証します。
def verify_de_morgan():
"""ド・モルガンの定理を全入力パターンで検証する"""
print("ド・モルガンの定理の検証")
print("=" * 50)
all_pass = True
for a, b in itertools.product([0, 1], repeat=2):
# 第1法則: NOT(A AND B) = NOT(A) OR NOT(B)
lhs1 = NOT(AND(a, b))
rhs1 = OR(NOT(a), NOT(b))
# 第2法則: NOT(A OR B) = NOT(A) AND NOT(B)
lhs2 = NOT(OR(a, b))
rhs2 = AND(NOT(a), NOT(b))
ok1 = "OK" if lhs1 == rhs1 else "NG"
ok2 = "OK" if lhs2 == rhs2 else "NG"
if lhs1 != rhs1 or lhs2 != rhs2:
all_pass = False
print(f"A={a}, B={b}: "
f"~(A&B)={lhs1}, ~A|~B={rhs1} [{ok1}] "
f"~(A|B)={lhs2}, ~A&~B={rhs2} [{ok2}]")
print(f"\n全パターン検証: {'合格' if all_pass else '不合格'}")
verify_de_morgan()
このコードは2変数の全4パターン（00, 01, 10, 11）に対して、ド・モルガンの第1法則と第2法則の両辺を独立に計算し、一致を確認します。すべてのパターンで OK が表示されることで、真理値表による完全枚挙証明がプログラム的にも追試できます。もし定理が成立しない入力が見つかれば NG が表示されるため、反例の発見にも使えます。
論理式の代数的簡単化の確認
前のセクションで行った代数的簡単化 $F = A\overline{B}C + A\overline{B}\overline{C} + AB\overline{C} + ABC = A$ を、全パターン比較で検証します。
def verify_simplification():
"""論理式の簡単化が正しいことを検証する"""
print("論理式の簡単化の検証")
print("=" * 50)
print("元の式: F = A~BC + A~B~C + AB~C + ABC")
print("簡単化: F = A")
print()
all_pass = True
for a, b, c in itertools.product([0, 1], repeat=3):
# 元の式
term1 = AND(AND(a, NOT(b)), c) # A~BC
term2 = AND(AND(a, NOT(b)), NOT(c)) # A~B~C
term3 = AND(AND(a, b), NOT(c)) # AB~C
term4 = AND(AND(a, b), c) # ABC
f_original = OR(OR(term1, term2), OR(term3, term4))
# 簡単化した式
f_simplified = a
ok = "OK" if f_original == f_simplified else "NG"
if f_original != f_simplified:
all_pass = False
print(f"A={a}, B={b}, C={c}: "
f"元の式={f_original}, 簡単化={f_simplified} [{ok}]")
print(f"\n全パターン検証: {'合格' if all_pass else '不合格'}")
verify_simplification()
全8パターンでOKが表示されることで、4項からなる論理式が $F = A$ に等しいことが確認できます。このように、代数的な変形で得た結果をプログラムで全パターン検証する手法は、人間が途中計算を間違えていないかのセルフチェックとして非常に有効です。
カルノー図の可視化
次に、カルノー図を matplotlib で可視化するプログラムを実装します。4変数のカルノー図を対象とし、グレイコード順の配置と最小項の位置を視覚的に確認できるようにします。
def plot_karnaugh_map_4var(minterms, dont_cares=None, title="4変数カルノー図"):
"""4変数カルノー図を可視化する
Parameters
----------
minterms : list of int
出力が1になる最小項番号のリスト
dont_cares : list of int or None
ドントケア条件の最小項番号のリスト
title : str
グラフタイトル
"""
if dont_cares is None:
dont_cares = []
# グレイコード順のインデックスマッピング
# 行: AB = 00, 01, 11, 10 → グレイコード順
# 列: CD = 00, 01, 11, 10 → グレイコード順
row_order = [0, 1, 3, 2] # AB のグレイコード順
col_order = [0, 1, 3, 2] # CD のグレイコード順
fig, ax = plt.subplots(1, 1, figsize=(8, 6))
# グリッドの描画
for i in range(5):
ax.axhline(y=i, color="white", linewidth=2)
ax.axvline(x=i, color="white", linewidth=2)
# セルの値を配置
for i, ab in enumerate(row_order):
for j, cd in enumerate(col_order):
minterm_num = ab * 4 + cd
if minterm_num in minterms:
val = "1"
color = "#2196F3" # 青
text_color = "white"
elif minterm_num in dont_cares:
val = "d"
color = "#FF9800" # オレンジ
text_color = "white"
else:
val = "0"
color = "#263238" # 暗いグレー
text_color = "#78909C"
rect = plt.Rectangle((j, 3 - i), 1, 1,
facecolor=color, edgecolor="white",
linewidth=2)
ax.add_patch(rect)
ax.text(j + 0.5, 3.5 - i, val,
ha="center", va="center",
fontsize=18, fontweight="bold", color=text_color)
# 最小項番号を小さく表示
ax.text(j + 0.15, 3.15 - i + 0.7, f"$m_{{{minterm_num}}}$",
ha="center", va="center",
fontsize=8, color=text_color, alpha=0.7)
# 軸ラベル
col_labels = ["00", "01", "11", "10"]
row_labels = ["00", "01", "11", "10"]
for j, label in enumerate(col_labels):
ax.text(j + 0.5, 4.3, label, ha="center", va="center",
fontsize=12, fontweight="bold")
for i, label in enumerate(row_labels):
ax.text(-0.3, 3.5 - i, label, ha="center", va="center",
fontsize=12, fontweight="bold")
ax.text(2, 4.8, "CD", ha="center", va="center",
fontsize=14, fontweight="bold")
ax.text(-0.8, 2, "AB", ha="center", va="center",
fontsize=14, fontweight="bold", rotation=90)
ax.set_xlim(-1.2, 4.5)
ax.set_ylim(-0.5, 5.2)
ax.set_aspect("equal")
ax.axis("off")
ax.set_title(title, fontsize=16, fontweight="bold", pad=20)
plt.tight_layout()
plt.show()
# 先ほどの例: F(A,B,C,D) = Σm(0,1,2,5,8,9,10)
plot_karnaugh_map_4var(
minterms=[0, 1, 2, 5, 8, 9, 10],
title="$F(A,B,C,D) = \\Sigma m(0,1,2,5,8,9,10)$"
)
上のコードが生成するカルノー図では、青色のセルが出力1（最小項）、暗いグレーのセルが出力0を表しています。行と列がグレイコード順（00, 01, 11, 10）に並んでいることが視覚的に確認できます。隣接する青いセルのグループを目で追うと、$\overline{B}\overline{C}$（左上と左下の列を跨ぐ4セル）、$\overline{B}\overline{D}$（左端列と右端列の4セル）、$\overline{A}\overline{C}D$（上段の $m_5$ と $m_1$ のペア）のグループが見つかり、先ほどの代数的な結果と一致することが確認できます。
ドントケア条件を含むカルノー図
BCD の奇数検出器の例を可視化します。
# BCD奇数検出器: 1,3,5,7,9 で出力1、10-15はドントケア
plot_karnaugh_map_4var(
minterms=[1, 3, 5, 7, 9],
dont_cares=[10, 11, 12, 13, 14, 15],
title="BCD奇数検出器（ドントケア条件付き）"
)
このカルノー図では、青色（出力1）とオレンジ色（ドントケア）のセルが表示されます。$D=1$ の列（$CD=01$ と $CD=11$）を見ると、ドントケアのセルを1として扱えば列全体が1で埋まるため、$F = D$ という極めてシンプルな結論が得られることが一目でわかります。ドントケアなしでは5つの最小項を個別にまとめる必要がありますが、ドントケアを活用することで単一変数にまで簡単化できるという劇的な効果が視覚的に確認できます。
全加算器のシミュレーション
全加算器の動作を全入力パターンで確認し、加算が正しく行われることを検証します。
def full_adder(a, b, c_in):
"""全加算器: 3入力(a, b, carry_in) → (sum, carry_out)"""
s = a ^ b ^ c_in
c_out = (a & b) | ((a ^ b) & c_in)
return s, c_out
def ripple_carry_adder(a_bits, b_bits):
"""nビットリプルキャリー加算器
Parameters
----------
a_bits : list of int
被加数のビット列（LSBが先頭）
b_bits : list of int
加数のビット列（LSBが先頭）
Returns
-------
result_bits : list of int
和のビット列（LSBが先頭）
"""
n = len(a_bits)
result = []
carry = 0
for i in range(n):
s, carry = full_adder(a_bits[i], b_bits[i], carry)
result.append(s)
result.append(carry) # 最上位の桁上げ
return result
def bits_to_int(bits):
"""ビット列(LSBファースト)を整数に変換"""
return sum(b * (2 ** i) for i, b in enumerate(bits))
def int_to_bits(n, width):
"""整数をビット列(LSBファースト)に変換"""
return [(n >> i) & 1 for i in range(width)]
# 4ビット加算器の全パターンテスト
print("4ビットリプルキャリー加算器のテスト")
print("=" * 50)
n_bits = 4
errors = 0
total = 0
for a in range(2**n_bits):
for b in range(2**n_bits):
a_bits = int_to_bits(a, n_bits)
b_bits = int_to_bits(b, n_bits)
result_bits = ripple_carry_adder(a_bits, b_bits)
result = bits_to_int(result_bits)
if result != a + b:
errors += 1
print(f" エラー: {a} + {b} = {result} (正解: {a + b})")
total += 1
print(f"\n全 {total} パターン中、エラー: {errors} 件")
print("全パターン正常" if errors == 0 else "エラーあり")
# いくつかの具体例を表示
print("\n--- 具体例 ---")
examples = [(7, 5), (15, 1), (9, 9), (0, 0)]
for a, b in examples:
a_bits = int_to_bits(a, n_bits)
b_bits = int_to_bits(b, n_bits)
result_bits = ripple_carry_adder(a_bits, b_bits)
result = bits_to_int(result_bits)
a_bin = "".join(str(x) for x in reversed(a_bits))
b_bin = "".join(str(x) for x in reversed(b_bits))
r_bin = "".join(str(x) for x in reversed(result_bits))
print(f" {a:2d} ({a_bin}) + {b:2d} ({b_bin}) = {result:2d} ({r_bin})")
4ビットリプルキャリー加算器の全 $16 \times 16 = 256$ パターンのテストで、すべての場合で正しい加算結果が得られることが確認できます。具体例では、$7 + 5 = 12$, $15 + 1 = 16$（桁上げ発生）, $9 + 9 = 18$ などの計算が2進数表記で追跡でき、全加算器の桁上げ伝搬の仕組みが実際に動作していることが確認できます。
論理ゲートの動作波形の可視化
最後に、論理ゲートの入出力の時間波形を可視化して、動的な動作のイメージを掴みます。
def plot_gate_waveforms():
"""主要論理ゲートの入出力波形を可視化する"""
t = np.arange(0, 8, 0.01)
# 入力信号（方形波）
a = ((t % 4) < 2).astype(int) # 周期4、デューティ50%
b = ((t % 2) < 1).astype(int) # 周期2、デューティ50%
# 各ゲートの出力
gates = {
"A (入力)": a,
"B (入力)": b,
"AND": a & b,
"OR": a | b,
"NAND": 1 - (a & b),
"XOR": a ^ b,
}
fig, axes = plt.subplots(len(gates), 1, figsize=(12, 8),
sharex=True)
colors = ["#2196F3", "#4CAF50", "#F44336",
"#FF9800", "#9C27B0", "#00BCD4"]
for ax, (name, signal), color in zip(axes, gates.items(), colors):
ax.step(t, signal, where="post", linewidth=2, color=color)
ax.fill_between(t, signal, step="post", alpha=0.15, color=color)
ax.set_ylabel(name, fontsize=11, fontweight="bold", rotation=0,
labelpad=80, ha="left")
ax.set_ylim(-0.2, 1.4)
ax.set_yticks([0, 1])
ax.set_yticklabels(["L", "H"])
ax.grid(axis="x", alpha=0.3)
ax.spines["top"].set_visible(False)
ax.spines["right"].set_visible(False)
axes[-1].set_xlabel("Time", fontsize=12)
fig.suptitle("論理ゲートの入出力波形",
fontsize=14, fontweight="bold")
plt.tight_layout()
plt.show()
plot_gate_waveforms()
この波形図から、各論理ゲートの動作タイミングが一目でわかります。AND の出力は $A$ と $B$ が同時にHighの区間だけHighになり、OR の出力はどちらかがHighの区間すべてでHighになります。NAND は AND の完全な反転で、XOR は $A$ と $B$ が異なる区間でHighになることが確認できます。このような波形図は、デジタル回路のタイミング解析の基本であり、後に学ぶ順序回路の設計でも同じ手法で動作検証を行います。
NANDゲートの万能性の検証
NANDゲートだけでAND, OR, NOTが構成できることを実装で確認します。
def nand(a, b):
"""NANDゲート"""
return 1 - (a & b)
# NANDだけで構成した基本ゲート
def not_from_nand(a):
"""NOT = NAND(A, A)"""
return nand(a, a)
def and_from_nand(a, b):
"""AND = NOT(NAND(A, B)) = NAND(NAND(A,B), NAND(A,B))"""
return nand(nand(a, b), nand(a, b))
def or_from_nand(a, b):
"""OR = NAND(NOT(A), NOT(B)) = NAND(NAND(A,A), NAND(B,B))"""
return nand(nand(a, a), nand(b, b))
print("NANDゲートの万能性の検証")
print("=" * 50)
all_pass = True
for a, b in itertools.product([0, 1], repeat=2):
not_ok = not_from_nand(a) == (1 - a)
and_ok = and_from_nand(a, b) == (a & b)
or_ok = or_from_nand(a, b) == (a | b)
if not (not_ok and and_ok and or_ok):
all_pass = False
print(f"A={a}, B={b}: "
f"NOT(A)={not_from_nand(a)} [{'OK' if not_ok else 'NG'}] "
f"AND={and_from_nand(a,b)} [{'OK' if and_ok else 'NG'}] "
f"OR={or_from_nand(a,b)} [{'OK' if or_ok else 'NG'}]")
print(f"\n全パターン検証: {'合格' if all_pass else '不合格'}")
全パターンでOKが出力されることで、NANDゲートだけでNOT, AND, ORのすべてが実現できることが確認できます。NOT は NAND の2入力を同じ信号に接続するだけ、AND は NAND の出力をさらに NAND（NOT として使用）に通すだけ、OR はド・モルガンの定理 $A + B = \overline{\overline{A} \cdot \overline{B}}$ に基づいて各入力を反転してから NAND に入力するだけです。これが「NANDゲートは万能ゲートである」という主張の具体的な裏付けです。
まとめ
本記事では、デジタル回路の基礎を論理ゲートからブール代数、カルノー図、組合せ回路の設計、CMOS実現まで体系的に解説しました。
- アナログ vs デジタル: デジタル回路が0と1の2値で処理する理由は、ノイズ耐性、再現性、プログラマビリティの3つの利点にあります
- 基本論理ゲート: AND, OR, NOT, NAND, NOR, XOR, XNOR の7種類が全てのデジタル回路の構成要素であり、特にNANDとNORはユニバーサルゲートとして任意の論理関数を実現できます
- ブール代数: 同一律、補元律、分配律、吸収律、ド・モルガンの定理を使って論理式を代数的に操作・簡単化できます
- カルノー図: グレイコード順の2次元配置により、隣接セルのグループ化で視覚的かつ体系的に最簡形を求められます。ドントケア条件の活用でさらなる簡単化が可能です
- 組合せ回路: 半加算器、全加算器、デコーダ、マルチプレクサは基本的な組合せ回路であり、これらを組み合わせてCPU内部のALUやメモリのアドレス選択回路が構成されています
- CMOS実現: pMOSとnMOSの相補的構成により、消費電力の小さいゲートが実現でき、NANDゲートがCMOS設計で最も基本的な構成要素です
本記事で学んだ組合せ回路は「記憶」を持ちません。しかし、コンピュータが動作するためにはデータを保存する回路が必要です。次のステップでは、フリップフロップを用いた順序回路の世界に進みます。また、本記事で登場したアナログとデジタルの橋渡しであるAD/DA変換器についても、理解を深めてみてください。
次のステップとして、以下の記事も参考にしてください。
- フリップフロップと順序回路 — SR, D, JK, Tフリップフロップの動作原理と順序回路の設計
- AD/DA変換器の理論と方式 — アナログとディジタルの橋渡し、量子化誤差とADC/DACの方式