カルノー図による論理式の簡単化を理解する

真理値表を書き下すところまでは誰でもできます。入力4本のスイッチに対して出力を1か0で埋めていけば、その回路の仕様は完全に決まります。ところが、その真理値表をそのまま論理式にすると、値が1になる行の数だけ4入力ANDゲートが並び、それを巨大なORゲートで束ねる、という無駄だらけの回路になります。実際に後で計算しますが、たった10行が1になるだけの4変数関数でも、素直に実装すると2入力ゲート換算で43個、信号が通る段数は6段にもなります。同じ関数が、うまく整理すればゲート10個・4段で実現できます。ゲート数を4分の1に、遅延を3分の2に減らす — この差を生むのが論理式の簡単化です。

問題は「うまく整理する」の中身です。ブール代数の定理を使えば式は縮みますが、どの定理をどの順番で適用すればよいのか、そしてどこで止めれば本当に最小なのかが、式変形からは見えてきません。そこで登場するのがカルノー図（Karnaugh map）です。カルノー図は、真理値表のマス目を「隣どうしが1変数しか違わない」ように並べ替えた地図です。この並べ替えのおかげで、ブール代数で $AB + A\overline{B} = A$ と書いていた式変形が、「隣り合う1を四角く囲む」という図形操作にそのまま置き換わります。頭の中の代数的な探索が、目で見える図形のパズルになるのです。

この図が本記事全体の見取り図です。左の真理値表では、$A$ だけが違って結合できるはずの $m_0$ と $m_8$ が8行も離れて並んでおり、「どの行とどの行がまとめられるか」を目で追うことができません。右のカルノー図は同じ情報を持ちながら、行ラベルと列ラベルをグレイコード順 $00, 01, 11, 10$ に貼り直すことで、結合できるマスどうしを物理的に隣接させています。さらに上端と下端、左端と右端もつながっている（トーラス構造）ため、$m_0$ と $m_8$ もこの地図の上では隣り合っており、まとめて囲めることが一目で分かります。

カルノー図とその背後にある理論を理解すると、次のような場面で効いてきます。

• 組合せ回路の設計: BCD入力を7セグメントLEDの点灯パターンに変換するデコーダ、優先エンコーダ、比較器など、真理値表から出発する回路の実装コストを最小化できます
• FPGA・ASICの論理合成: 合成ツールが内部で行っている二段論理最小化（ESPRESSO など）の原理そのものです。ツールの出力が「なぜこの形なのか」を読めるようになります
• ハザード対策: 最小形は必ずしも安全な回路ではありません。カルノー図の上で「群と群の隙間」を見つけると、グリッチ（静的ハザード）が出る箇所と、その対策として残すべき冗長項が特定できます
• 論理関数の解析全般: 主項・被覆といった概念は、決定リストの学習やルール抽出、ソフトウェアの条件分岐整理にも同じ形で現れます

本記事の内容

• 論理式の「コスト」をどう測るか — リテラル数・ゲート数・段数
• ブール代数による簡単化と、その限界
• カルノー図の直感 — 真理値表を地図に貼り直す
• グレイコード配置が隣接結合を可能にする原理（導出）
• $2^k$ 個の1をまとめると $k$ 個の変数が消えることの証明
• インプリカント・主項・必須主項の定義と、最小積和形＝最小被覆問題
• 4変数の例題を被覆表まで含めて最後まで解く
• ドントケアの活用 — BCDデコーダ・7セグメントLED
• 5変数カルノー図への拡張
• Quine-McCluskey法とPetrick法のアルゴリズム化
• Python実装: 真理値表を入力すると最小積和形を返す関数、カルノー図の色分け描画、コスト比較

前提知識

この記事を読む前に、以下の記事を読んでおくと理解が深まります。

• デジタル回路の基礎 — 論理ゲートからブール代数・カルノー図まで完全解説
• フリップフロップと順序回路 — 記憶素子からカウンタ・状態機械まで

なぜ簡単化するのか — 論理式のコストを測る

「式が短いほうが気持ちいいから」では設計の理由になりません。簡単化が何を節約しているのかを、まず具体的な量として決めておきます。回路設計の文脈では、次の3つの指標がよく使われます。

第一にリテラル数です。リテラルとは、変数そのもの（$A$）またはその補元（$\overline{A}$）を1個と数えたものです。$\overline{A}BD$ は3リテラル、$C\overline{D}$ は2リテラルです。リテラル数は、AND入力に接続される信号線の総数にほぼ比例します。CMOSの標準セルではトランジスタ数がおおよそ入力数に比例するので、リテラル数は面積と消費電力の第一近似になります。

第二にゲート数です。ただし「4入力AND 1個」と「2入力AND 1個」を同列に数えるのはフェアではありません。そこで本記事では、すべてを2入力ゲート換算で数えます。$n$ リテラルの積項は2入力ANDが $n-1$ 個、$t$ 個の項の論理和は2入力ORが $t-1$ 個、そして補元を作るインバータが変数の種類だけ必要、という数え方です。

第三に段数（ロジックレベル）です。入力から出力まで信号が何個のゲートを通るかで、伝搬遅延がおおよそ決まります。$n$ リテラルの積項を2入力ANDの木で作れば $\lceil \log_2 n \rceil$ 段、$t$ 項のORの木は $\lceil \log_2 t \rceil$ 段なので、二段論理（AND-OR形）の実際の段数はこの和になります。

ここで、本記事を通して使う例題を導入します。4変数 $A, B, C, D$（$A$ が最上位）の関数で、出力が1になる入力の組み合わせが次の10通りだとします。

$$ f(A,B,C,D) = \Sigma m(0, 1, 2, 5, 6, 7, 8, 9, 10, 14) $$

$\Sigma m(\cdot)$ は「ミンターム番号の列挙」という記法です。ミンターム番号 $m$ は、入力を2進数 $ABCD$ と読んだときの値を表します。たとえば $m_5$ は $ABCD = 0101$、つまり $\overline{A}B\overline{C}D$ という積項に対応します。

真理値表をそのまま式にすると、1になる行それぞれに対応する4リテラルの積項を並べた形になります。

$$ f = \overline{A}\,\overline{B}\,\overline{C}\,\overline{D} + \overline{A}\,\overline{B}\,\overline{C}D + \overline{A}\,\overline{B}C\overline{D} + \overline{A}B\overline{C}D + \overline{A}BC\overline{D} + \overline{A}BCD + A\overline{B}\,\overline{C}\,\overline{D} + A\overline{B}\,\overline{C}D + A\overline{B}C\overline{D} + ABC\overline{D} $$

これを正準積和形（canonical sum of products）と呼びます。真理値表と1対1に対応するので、仕様を機械的に式にするには便利ですが、実装コストは最悪です。リテラル数は $4 \times 10 = 40$、2入力ゲート換算では43個、段数は6段になります（後ほどPythonで数えます）。

一方、これから求める最小積和形は次の3項です。

$$ f = C\overline{D} + \overline{B}\,\overline{C} + \overline{A}BD $$

リテラル数は $2+2+3 = 7$、ゲート数は10個、段数は4段です。同じ真理値表を実現する回路でありながら、コストが桁違いに違います。この2つを回路図として並べると、削減されているものの正体がはっきりします。

左は真理値表の1の行をそのまま積項にした回路で、4リテラルのANDが10本もORゲートに突き刺さっています。右は簡単化後で、ANDは3本、しかも2リテラルが2本と3リテラルが1本しかありません。どちらも入力に対して同じ出力を返す、論理的に等価な回路であるにもかかわらず、ORゲートの入力数もAND段の幅も大きく違い、これがそのまま面積・消費電力・遅延の差になります。

この差はどこから生まれ、どうすれば体系的に見つけられるのか — それがこの記事のテーマです。まずは伝統的な武器であるブール代数の式変形から始め、それがなぜ心もとないのかを確認しましょう。

ブール代数による簡単化と、その限界

ブール代数の定理のうち、簡単化で主役になるのは次の結合定理（combining theorem）です。

$$ AB + A\overline{B} = A $$

導出は一行です。分配則で $A$ をくくり出すと $AB + A\overline{B} = A(B + \overline{B})$ となり、相補則 $B + \overline{B} = 1$ を使えば $A \cdot 1 = A$ です。意味も明快で、「$A$ が1でありさえすれば、$B$ が0だろうが1だろうが出力は1になる。ならば $B$ は結果に関係ない」ということです。2つの積項が、ちょうど1つの変数についてだけ逆で、他は完全に一致しているとき、その変数を消せる — これが結合定理の中身です。

この定理を例題に当てはめてみましょう。$m_6 = \overline{A}BC\overline{D}$ と $m_{14} = ABC\overline{D}$ は、$A$ の肯定・否定だけが違い、残りの $BC\overline{D}$ は共通です。したがって、

$$ \overline{A}BC\overline{D} + ABC\overline{D} = (\overline{A} + A)BC\overline{D} = BC\overline{D} $$

4リテラルの項が2つ消えて、3リテラルの項が1つ残りました。同じように $m_2 = \overline{A}\,\overline{B}C\overline{D}$ と $m_{10} = A\overline{B}C\overline{D}$ をまとめると $\overline{B}C\overline{D}$ になります。さらに、いま作った $BC\overline{D}$ と $\overline{B}C\overline{D}$ は $B$ だけが逆なので、もう一度結合定理が使えます。

$$ BC\overline{D} + \overline{B}C\overline{D} = (B + \overline{B})C\overline{D} = C\overline{D} $$

4つのミンターム $m_2, m_6, m_{10}, m_{14}$ が、たった2リテラルの $C\overline{D}$ に凝縮されました。これが最小形に現れた第1項の正体です。この3ステップをカルノー図の上に描くと、式変形が図形操作にそのまま対応していることが分かります。

左のパネルは $m_6, m_{14}$ の縦2マス、中央は $m_2, m_{10}$（上端と下端をまたぐ2マス）、右はそれらを合わせた $m_2, m_6, m_{10}, m_{14}$ の4マスです。囲むマス数が2倍になるたびに、積項のリテラル数がちょうど1つ減っていることに注目してください。4リテラル→3リテラル→2リテラルという減り方が、そのまま結合定理の適用回数に対応しています。中央のパネルは図の上端と下端をまたいでいますが、グレイコード配置ではこの2マスも隣接扱いなので、正当な結合です。

もう一つ、簡単化で重要なのがコンセンサス定理（consensus theorem）です。

$$ xy + \overline{x}z + yz = xy + \overline{x}z $$

証明してみましょう。左辺の第3項 $yz$ に $1 = x + \overline{x}$ を掛けます。

$$ yz = yz(x + \overline{x}) = xyz + \overline{x}yz $$

これを左辺に戻すと $xy + \overline{x}z + xyz + \overline{x}yz$ になります。ここで前2項に対して吸収則 $u + uv = u$ を使います。$xy + xyz = xy(1+z) = xy$、$\overline{x}z + \overline{x}yz = \overline{x}z(1+y) = \overline{x}z$ なので、結局 $xy + \overline{x}z$ に戻ります。つまり $yz$ という項は、他の2項が既にカバーしているので論理的には不要です。この $yz$ をコンセンサス項と呼びます。後でハザードの話をするとき、この「論理的には不要だが物理的には意味がある項」が再登場します。

さて、道具は揃いました。しかし実際に10項の正準形からスタートしてみると、すぐに困ります。$m_0$ は $m_1$（$D$ が違う）とも $m_2$（$C$ が違う）とも $m_8$（$A$ が違う）とも結合できます。どれと組むべきでしょうか。しかも一度使った項を再利用してよいのか（べき等則 $u + u = u$ があるので、実は何度でも使えます）、途中でできた項どうしをまた結合すべきか、どこまでやれば終わりなのか — 判断の根拠がありません。式変形は、正しい一歩を積み重ねることはできても、探索空間の全体像を教えてくれないのです。10項からの結合の組み合わせは指数的に増え、人間が「もうこれ以上縮まない」と確信することは困難です。

必要なのは、関数の全体像を一望できる表現です。真理値表は全体像を持っていますが、行が数値順に並んでいるため「どの行とどの行が結合できるか」が見えません。ならば、結合できる行どうしが物理的に隣り合うように並べ替えた表を作ればよい — この発想がカルノー図です。

カルノー図とは — 真理値表を地図に貼り直す

地下鉄の路線図を思い浮かべてください。実際の地理的な位置関係を捨てて、「乗り換えできる駅は隣に描く」というルールで描き直したものが路線図です。目的が「乗り換え経路を探すこと」なら、正確な地図より路線図のほうが圧倒的に速く読めます。カルノー図も同じ発想です。真理値表の行を数値順に並べるのをやめ、「結合定理が使える行どうしが隣り合う」という基準で2次元に並べ直します。

結合定理が使える条件は、すでに見た通り「ちょうど1変数だけが異なる」でした。2つの入力ベクトルをビット列と見なせば、これはハミング距離が1であることに他なりません。そこで、カルノー図では次のルールを課します。

図の上で上下左右に隣り合うマスは、対応する入力ベクトルのハミング距離が1でなければならない。

4変数の場合、$4 \times 4$ の格子に16個のミンタームを配置します。行に $AB$ の2ビット、列に $CD$ の2ビットを割り当てるところまでは自然ですが、行ラベルを $00, 01, 10, 11$ の数値順に並べてはいけません。$01$ と $10$ はハミング距離が2だからです。代わりに $00, 01, 11, 10$ の順に並べます。この順序がグレイコードです。

例題の関数をこのルールで配置すると、次のコードで描ける図になります。日本語フォントの設定を先に入れておきます。

import numpy as np
import matplotlib
import matplotlib.pyplot as plt

for cand in ["Hiragino Sans", "Yu Gothic", "Noto Sans CJK JP", "IPAexGothic", "Meiryo"]:
    if any(cand == f.name for f in matplotlib.font_manager.fontManager.ttflist):
        plt.rcParams["font.family"] = cand
        break
plt.rcParams["axes.unicode_minus"] = False

GRAY2 = [0, 1, 3, 2]           # 2ビットのグレイコード順 00, 01, 11, 10

def kmap_pos(m):
    """ミンターム番号 m → カルノー図の (行, 列)"""
    return GRAY2.index((m >> 2) & 3), GRAY2.index(m & 3)

def draw_kmap(ax, value_of, title):
    """4変数カルノー図の枠と値を描く。value_of(m) はマスに書く文字列を返す関数"""
    labs = ['00', '01', '11', '10']
    for r in range(4):
        for c in range(4):
            m = (GRAY2[r] << 2) | GRAY2[c]
            ax.add_patch(plt.Rectangle((c, 3 - r), 1, 1, fc='white', ec='#444', lw=1.2))
            ax.text(c + 0.5, 3 - r + 0.6, value_of(m), ha='center', va='center',
                    fontsize=15, fontweight='bold')
            ax.text(c + 0.92, 3 - r + 0.1, 'm{}'.format(m), ha='right', va='bottom',
                    fontsize=7, color='#888')
    for c in range(4):
        ax.text(c + 0.5, 4.12, labs[c], ha='center', fontsize=10)
    for r in range(4):
        ax.text(-0.12, 3 - r + 0.5, labs[r], ha='right', va='center', fontsize=10)
    ax.text(-0.12, 4.12, 'AB＼CD', ha='right', va='bottom', fontsize=10)
    ax.set_xlim(-1.1, 4.3); ax.set_ylim(-0.3, 4.6); ax.axis('off')
    ax.set_title(title, fontsize=12)

MT = [0, 1, 2, 5, 6, 7, 8, 9, 10, 14]
fig, ax = plt.subplots(figsize=(5.6, 5.2))
draw_kmap(ax, lambda m: '1' if m in MT else '0', '例題のカルノー図（1が10マス）')
plt.tight_layout()
plt.show()

このコードを実行すると、行ラベルが上から $00, 01, 11, 10$、列ラベルが左から $00, 01, 11, 10$ と並んだ $4 \times 4$ の図が描かれ、各マスに0か1、右下に小さくミンターム番号が入ります。図を眺めると、1が固まっている領域がはっきり見えます。右端の列（$CD = 10$）は4マスすべてが1、左上の $2\times2$ ブロック（$m_0, m_1, m_8, m_9$）も1です。真理値表を数値順に眺めていたときには気づけなかった「1のかたまり」が、配置を変えただけで視覚的に浮かび上がります。これがカルノー図の効能です。

ただし、この配置がなぜ結合定理と対応するのか、まだ「隣は1ビット違い」という約束を確認しただけです。次節では、グレイコードの性質を使って、この対応関係を厳密に導きます。

グレイコード配置の原理

グレイコードとハミング距離

グレイコードは、隣り合う符号語のハミング距離が常に1になる2進符号です。$k$ ビットの標準的なグレイコード（反射型グレイコード）は、整数 $i$ に対して次の式で与えられます。

$$ G(i) = i \oplus \lfloor i/2 \rfloor $$

ここで $\oplus$ はビットごとの排他的論理和です。$k=2$ で計算してみましょう。$G(0) = 0 \oplus 0 = 00$、$G(1) = 1 \oplus 0 = 01$、$G(2) = 10 \oplus 01 = 11$、$G(3) = 11 \oplus 01 = 10$ となり、確かに $00, 01, 11, 10$ の順が出てきます。隣接ペアを確認すると、$00 \to 01$ は下位ビットのみ、$01 \to 11$ は上位ビットのみ、$11 \to 10$ は下位ビットのみが変化しています。すべてハミング距離1です。

さらに重要なのが巡回性です。最後の $10$ と最初の $00$ を比べると、これも上位ビットのみが違うのでハミング距離1です。つまり $k$ ビットのグレイコード列は、端と端がつながった輪になっています。この性質から、カルノー図では左端の列と右端の列も隣接扱い、上端の行と下端の行も隣接扱いになります。図の上下と左右をそれぞれ丸めて貼り合わせた形、すなわちトーラス（ドーナツ型）の表面が、カルノー図の本当の形です。

左のパネルは2ビットのグレイコード $00 \to 01 \to 11 \to 10$ を輪として描いたもので、4本の辺すべてがハミング距離1になっています。特に $10$ から $00$ に戻る辺が距離1であることが巡回性で、これが中央のパネルの「上端と下端が隣接」「左端と右端が隣接」に直結します。右のパネルが示す通り、カルノー図を平面の紙ではなくトーラスの表面と見なせば、端の巻き込みは特別扱いでも何でもなく、単に「隣どうしを囲んだ」だけになります。

2次元配置でも隣接条件が保たれる理由

行に $AB$、列に $CD$ を割り当て、行インデックス $r$ に $G(r)$、列インデックス $c$ に $G(c)$ を対応させます。マス $(r, c)$ が表すミンタームのビット列は $G(r) \| G(c)$（連結）です。

横に隣り合うマス $(r, c)$ と $(r, c’)$（$c, c’$ はグレイコード列で隣接）を比べます。上位2ビットは $G(r)$ で共通なので距離0、下位2ビットは $G(c)$ と $G(c’)$ でハミング距離1です。合計の距離は $0 + 1 = 1$。同様に縦に隣り合うマスは、下位2ビットが共通で上位2ビットの距離が1なので、やはり合計1です。

一方、斜めに隣り合うマスはどうでしょうか。$(r,c)$ と $(r’, c’)$ では上位2ビットの距離が1、下位2ビットの距離も1なので、合計は2になります。ハミング距離2ということは、2変数が同時に違うということで、結合定理は使えません。カルノー図で斜めをまとめてはいけないという有名なルールは、この計算から出てきます。

この違いは、隣接ペアのハミング距離を実際に書き込んで比べると一目瞭然です。

丸数字は、隣り合う2つのマスのミンターム番号のハミング距離です。左の数値順配置（$00, 01, 10, 11$）では、$01$ と $10$ の境目にあたる列間・行間がすべて距離2（赤）になっており、図の上では隣なのに結合定理が使えないという致命的な状態です。一方、右のグレイコード配置ではすべての隣接ペアが距離1（緑）で、どこを囲んでも必ず結合定理が成り立ちます。カルノー図の行列ラベルが $00, 01, 11, 10$ でなければならない理由が、この一枚に凝縮されています。

$2^k$ 個をまとめると $k$ 変数が消える

カルノー図の操作は「隣り合う1を四角く囲む」ですが、囲めるサイズには制約があります。1マス、2マス、4マス、8マス — つまり $2^k$ 個です。なぜ3マスや6マスではいけないのか、そして囲んだ結果どんな積項になるのかを、一般的に示しましょう。

$n$ 変数のうち $k$ 個を選んで「自由」にし、残る $n-k$ 個を特定の値に固定した集合を考えます。たとえば $n=4$、固定を $B=0, C=0$、自由を $A, D$ とすると、この集合は $\{0000, 0001, 1000, 1001\} = \{m_0, m_1, m_8, m_9\}$ の4個です。このような集合を部分立方体（subcube）と呼びます。自由変数が $k$ 個なら、その組み合わせは $2^k$ 通りなので、部分立方体の要素数はちょうど $2^k$ 個です。

この部分立方体に含まれるミンタームの論理和を計算します。固定部分を表す積項を $p$（$n-k$ リテラル）、自由変数を $x_1, \dots, x_k$ とすると、

$$ \sum_{\text{部分立方体}} m = p \cdot \sum_{(b_1,\dots,b_k) \in \{0,1\}^k} x_1^{b_1} x_2^{b_2} \cdots x_k^{b_k} $$

と書けます（$x^1 = x$、$x^0 = \overline{x}$ の記法です）。ここで右側の和は、$k$ 変数のすべてのミンタームの論理和なので、恒等的に1です。実際、$k$ 変数の入力がどんな値をとっても、対応するミンタームのどれか1つが必ず1になります。したがって、

$$ \sum_{\text{部分立方体}} m = p \cdot 1 = p $$

$2^k$ 個のミンタームからなる部分立方体は、$n-k$ リテラルの積項1つに等しい。これが囲む操作の正体です。1マス（$k=0$）なら4リテラル、2マス（$k=1$）なら3リテラル、4マス（$k=2$）なら2リテラル、8マス（$k=3$）なら1リテラル。囲む面積を2倍にするたびに、リテラルが1つ減るわけです。だからカルノー図を解くときは「できるだけ大きく囲め」が鉄則になります。

4枚のパネルは、同じ $\overline{A}B\overline{C}D$ を起点にして囲む範囲を段階的に広げたものです。1マスの $\overline{A}B\overline{C}D$（4リテラル）から、$A$ を自由にした2マスの $B\overline{C}D$（3リテラル）、さらに $B$ も自由にした4マスの $\overline{C}D$（2リテラル）、最後に $C$ も自由にした8マスの $D$（1リテラル）へと進みます。自由にした変数の個数 $k$ と消えたリテラルの個数がぴったり一致していることが、$n-k$ という式の意味そのものです。

なぜ3マスではいけないかも、これで明らかです。3個のミンタームの論理和が1つの積項に等しくなることはありません。積項が表す集合は必ず部分立方体で、その要素数は2のべき乗だからです。3マスを1つの積項で表そうとすれば、はみ出した4マス目まで含めるしかなく、それは元の関数を変えてしまいます。

左の禁止例1では $m_0$ と $m_5$ を斜めに囲もうとしていますが、この2つは $B$ と $D$ が同時に違うのでハミング距離2、結合定理の前提を満たしません。中央の禁止例2は3マスを囲もうとしたもので、3は2のべき乗でないため、どんな積項も過不足なくこの3マスを表せません。右の正しい例のように $2^k$ マスの長方形（ここでは横4マス＝$\overline{A}\,\overline{B}$）で囲んだときだけ、群がちょうど1つの積項に対応します。

そして、部分立方体がカルノー図上で「長方形」に見えることも、グレイコードの帰結です。$AB$ 側で $k_1$ 個の自由変数、$CD$ 側で $k_2$ 個の自由変数を持つ部分立方体は、行方向に $2^{k_1}$ 個、列方向に $2^{k_2}$ 個の連続した（トーラス上で連続した）マスからなる長方形になります。

ここまでで、「隣り合う1を $2^k$ 個ずつ長方形に囲む」という図形操作が、ブール代数の結合定理の反復適用と完全に等価であることが示せました。次は、ではどの長方形をいくつ選べば最小になるのかという、選択の理論に進みます。

インプリカント・主項・必須主項

インプリカントの定義

まず言葉を整えます。積項 $p$ が関数 $f$ のインプリカント（implicant、含意項）であるとは、

$$ p = 1 \ \Rightarrow \ f = 1 $$

が全入力について成り立つことをいいます。ブール代数の順序で書けば $p \le f$、集合で書けば「$p$ が被覆するミンタームの集合が $f$ のオンセット（1になる入力の集合）に含まれる」ということです。カルノー図の言葉では、0のマスを1つも含まない長方形がインプリカントです。

例題で確認しましょう。$C\overline{D}$ は $m_2, m_6, m_{10}, m_{14}$ を被覆し、これらはすべてオンセットに入っているのでインプリカントです。一方 $\overline{A}C$ は $m_2, m_3, m_6, m_7$ を被覆しますが、$m_3$ はオフセット（0の側）なのでインプリカントではありません。

インプリカントは「その項を積和形に足しても関数を壊さない」項です。逆に言えば、$f$ の積和表現は必ずインプリカントの和になっています。

主項の定義

インプリカントはいくらでもあります（極端な話、各ミンターム自身がインプリカントです）。コストを下げたいのだから、なるべく大きいインプリカントを使いたい。そこで極大なものに名前をつけます。

積項 $p$ が $f$ の主項（prime implicant、PI）であるとは、$p$ が $f$ のインプリカントであり、かつ $p$ からどのリテラルを1つ取り除いても、もはや $f$ のインプリカントでなくなることをいいます。カルノー図の言葉では、これ以上大きくできない長方形です。

$C\overline{D}$ は主項でしょうか。リテラルを1つ落とすと $C$ か $\overline{D}$ になります。$C$ は $m_3$（オフセット）を含むのでダメ、$\overline{D}$ は $m_4$（オフセット）を含むのでダメ。どちらも失敗するので、$C\overline{D}$ は主項です。

なぜ最小形は主項だけでできているのか

ここで一つ、大事な定理を証明しておきます。

定理（Quine）: 最小積和形は、主項のみからなる。

証明は簡単です。ある最小積和形 $f = p_1 + p_2 + \dots + p_t$ の中に、主項でないインプリカント $p_i$ が混じっていたとします。主項でないということは、$p_i$ からリテラルを1つ落とした $p_i’$ もインプリカントだということです。$p_i’$ は $p_i$ を包含する（$p_i \le p_i’$）ので、$p_i$ を $p_i’$ に置き換えても被覆は減らず、$f$ の値は変わりません。一方リテラル数は1減ります。これは「最小」の仮定に反します。よって最小形に非主項は含まれません。∎

この定理のおかげで、探索の対象を主項だけに絞れます。無限にあるように見えたインプリカントの中から、有限個（4変数なら多くて十数個）の主項だけを列挙すればよいのです。

必須主項と最小被覆問題

主項をすべて列挙したら、次は「どの主項を選ぶか」です。条件はオンセットの全ミンタームがどれかの主項に被覆されること、目的は選んだ主項のコスト（項数、次いでリテラル数）を最小にすること。これは組合せ最適化でいう集合被覆問題（set covering problem）そのものです。一般に NP困難であり、変数が増えると厳密解を求めるのは難しくなります。

ただし、多くの場合は簡単に確定する部分があります。あるミンターム $m$ を被覆する主項がただ1つしかないとき、その主項は必須主項（essential prime implicant）と呼ばれ、どんな被覆にも必ず含まれなければなりません。$m$ を被覆する手段が他にないからです。必須主項を先に確定させ、それが被覆するミンタームを表から消してしまえば、残った小さな問題だけを考えればよくなります。

ここで一つ注意しておくと、「主項を全部使う」ことと「最小」は違います。次節の例題では、6個の主項のうち3個だけを使うのが最小解になります。使われない主項は、他の主項の組み合わせによってすでに被覆されているため、足しても被覆が増えず、リテラルだけ増える無駄な項です。この「論理的には正しいが無駄な主項」の存在が、簡単化を単純な貪欲手続きにさせない原因です。

概念が揃いました。実際に例題を最後まで解いて、手順を体に入れましょう。

例題を最後まで解く

主項をすべて列挙する

対象は $f = \Sigma m(0,1,2,5,6,7,8,9,10,14)$ です。カルノー図を見ながら、これ以上大きくできない長方形を探します。結果を先に示すと、主項は6個あります。

6枚のパネルが、それぞれ1つの主項に対応します。上段の3つは4マス群で2リテラル、下段の3つは2マス群で3リテラルです。どのパネルも枠が0のマスにかかっていない（＝インプリカントである）こと、そしてどの枠も縦か横に1段でも広げると必ず0を巻き込んでしまう（＝これ以上大きくできない＝主項である）ことを、実際に目で確かめてみてください。

$\overline{B}\,\overline{D}$ と $\overline{B}\,\overline{C}$ は、行ラベルで言えば $AB = 00$ の行と $AB = 10$ の行にまたがる群です。上の図でもこの2つだけが上端と下端に分断されて描かれています。数値順の表では $m_0$ と $m_8$ は遠く離れていますが、グレイコード配置では上端と下端が接しているので、これは正当な4マスの長方形です。端の巻き込みを見落とすのが、手作業でカルノー図を解くときの最頻出ミスです。

被覆表を作り、必須主項を見つける

行にミンターム、列に主項を取り、被覆関係を書き出します。

この表は、縦にオンセットの10個のミンターム、横に6個の主項を並べ、被覆関係を●で埋めたものです。ほとんどの行には●が2つ以上あり、「どちらの主項で覆ってもよい」という選択の余地があります。ところが赤く囲った2行、$m_9$ と $m_{14}$ には●が1つしかありません。この2行に対しては選択の余地がなく、対応する列（薄赤で塗った $\overline{B}\,\overline{C}$ と $C\overline{D}$）はどんな解にも必ず入ることが確定します。

行を眺めて、被覆主項が1つしかない行を探します。$m_9$ の行には $\overline{B}\,\overline{C}$ しかありません。$m_{14}$ の行には $C\overline{D}$ しかありません。したがって $\overline{B}\,\overline{C}$ と $C\overline{D}$ は必須主項です。

必須主項を確定させたので、それらが被覆するミンタームを消します。$C\overline{D}$ が $\{2,6,10,14\}$、$\overline{B}\,\overline{C}$ が $\{0,1,8,9\}$ を担当するので、残るのは $m_5$ と $m_7$ の2つだけです。

残りを被覆する

$m_5$ を被覆できるのは $\overline{A}\,\overline{C}D$ か $\overline{A}BD$、$m_7$ を被覆できるのは $\overline{A}BD$ か $\overline{A}BC$ です。$\overline{A}BD$ は両方を被覆できます。したがって $\overline{A}BD$ を1つ選べば済みます。$\overline{A}\,\overline{C}D$ と $\overline{A}BC$ の組を選ぶと2項・6リテラルになってしまうので、明らかに損です。

最終的な最小積和形は、

$$ f = C\overline{D} + \overline{B}\,\overline{C} + \overline{A}BD $$

3項・7リテラルです。

赤い枠が右端の列4マス（$C\overline{D}$）、青い枠が上端と下端に分断された4マス（$\overline{B}\,\overline{C}$）、緑の枠が中央の横2マス（$\overline{A}BD$）です。10個ある1のマスがこの3枠で漏れなく覆われ、0のマスには枠が一切かかっていないことを確認してください。右側には、主項でありながら選ばれなかった3つの項が並んでいます。

ここで注目してほしいのが、主項 $\overline{B}\,\overline{D}$ が1回も使われなかったことです。$\overline{B}\,\overline{D}$ が被覆する $\{0,2,8,10\}$ は、$C\overline{D}$ と $\overline{B}\,\overline{C}$ の被覆の和 $\{0,1,2,6,8,9,10,14\}$ にすっぽり含まれています。主項であっても、他の項に完全に肩代わりされてしまえば、選ぶ理由がありません。

冗長な主項にも役割がある — 静的ハザード

いま捨てた $\overline{B}\,\overline{D}$ は、実は物理的な回路では重要な意味を持ちます。$A=0, B=0, D=0$ に固定して、$C$ を $1 \to 0$ に変化させる場面を考えてください。入力は $m_2 \to m_0$ と移ります。どちらも出力は1なので、理想的には出力は1のまま変化しないはずです。

ところが最小形の回路では、$m_2$ のときに1を出しているのは $C\overline{D}$ の項、$m_0$ のときに1を出しているのは $\overline{B}\,\overline{C}$ の項です。ここで、2つの項が $C$ を受け取る経路の長さが違うことに注目してください。$C\overline{D}$ のANDゲートには $C$ が直結していますが、$\overline{B}\,\overline{C}$ のANDゲートにはインバータを1段通った $\overline{C}$ が入ります。したがって $C$ が落ちると、$C\overline{D}$ は即座に0になるのに、$\overline{B}\,\overline{C}$ はインバータの遅延ぶんだけ遅れてからしか1になりません。この遅延の間、どちらの項も0という一瞬が生じ、出力が0に落ちます。これが静的1ハザード（グリッチ）です。

上から順に、入力 $C$、インバータ出力 $\overline{C}$、2つの積項の出力、そして回路全体の出力です。赤い帯が、$C$ が落ちてから $\overline{C}$ が立ち上がるまでのインバータ遅延を表します。$C\overline{D}$ は $C$ が直結なのでこの帯の開始と同時に0へ落ちるのに対し、$\overline{B}\,\overline{C}$ が1になるのは帯の終わりです。この帯の中では両方の項が0になるため、5段目の最小形の出力に幅の狭いくぼみ（グリッチ）が現れます。一方、最下段のように恒に1を出す項が1つでもあれば、出力は帯の中でも1のまま保たれます。

対策は、この2つの群にまたがる項を回路に足しておくことです。$B=0, D=0$ の間は $C$ の値によらずずっと1を出し続ける項があれば、$C$ の切り替わりに巻き込まれる項がなくなるのでグリッチは起きません。それこそが $\overline{B}\,\overline{D}$ です。しかもこれは偶然ではありません。コンセンサス定理 $xy + \overline{x}z + yz = xy + \overline{x}z$ に $x = C$, $y = \overline{D}$, $z = \overline{B}$ を代入すると、

$$ C\overline{D} + \overline{C}\,\overline{B} + \overline{D}\,\overline{B} = C\overline{D} + \overline{C}\,\overline{B} $$

となり、$\overline{B}\,\overline{D}$ はまさに $C\overline{D}$ と $\overline{B}\,\overline{C}$ のコンセンサス項です。

左は最小形の3群だけを描いたもので、$m_2$（赤い群）から $m_0$（青い群）への移動が群の境界をまたいでいることが矢印から読み取れます。群をまたぐ移動は、必ずどちらかの項の立ち上がりと立ち下がりの競合を伴うため、ハザードの候補になります。右は橙の破線で $\overline{B}\,\overline{D}$ を追加したもので、$m_2$ と $m_0$ が同じ1つの群の中に収まっており、移動中ずっとその項が1を出し続けます。カルノー図の上で「隣接する2つの群が斜めに接している箇所」を探し、そこをまたぐ群を追加するのが、ハザードフリー設計の定石になります。最小形が常に正解ではない、というのは実務上とても重要な注意点です。

例題の解き方は分かりました。次は、実際の設計でほぼ必ず登場する「気にしなくてよい入力」の扱いに進みます。

ドントケアの活用

起きない入力・見られない出力

4ビットのBCD（二進化十進）コードは、0から9までの10個の数字だけを $0000$〜$1001$ で表します。$1010$ から $1111$ までの6通りは、BCDとしては意味を持ちません。この6通りが入力されることが設計上ありえないなら、その入力に対して回路が何を出力しようと構いません。同じことは「出力側が見ていない」場合にも起きます。ある制御信号が有効でない期間、別の出力の値は誰も参照しない、という状況です。

このような入力をドントケア（don’t care）と呼び、真理値表には $X$（または $d$）と書きます。関数の定義域は、オンセット $F$、オフセット $R$、ドントケア集合 $D$ の3つに分割されます。これを不完全指定関数（incompletely specified function）といいます。

なぜドントケアで式が縮むのか

ドントケアの威力は、$X$ を0にも1にも自由に決められる点にあります。1にすれば群を大きくできる（＝リテラルが減る）、0にしておけば余計な群を作らなくて済む。設計者は群ごとに都合のよいほうを選べます。式で言えば、$X$ の割り当て方は $2^{|D|}$ 通りあり、その中で最も安く実装できる完備化を選んでよい、ということです。

主項を求めるときの扱いは明快です。主項の生成にはドントケアを1として参加させ、被覆すべき対象（被覆表の行）にはオンセットのミンタームだけを並べます。前者はドントケアを使って群を大きくすることを許すため、後者は「使われなかったドントケアは0のままでよい」ためです。

例1: BCD入力の「5以上」検出

BCD 1桁 $ABCD$ が5以上のとき1を出す回路を考えます。オンセットは $\{5,6,7,8,9\}$、ドントケアは $\{10,11,12,13,14,15\}$ です。

まずドントケアを無視して（$1010$〜$1111$ で強制的に0を出すと決めて）解くと、

$$ f = \overline{A}BD + \overline{A}BC + A\overline{B}\,\overline{C} $$

3項・9リテラルになります。$A\overline{B}\,\overline{C}$ という項は、「$A=1$ のとき、BCDでは $8$ か $9$ しかありえないのに、$10$ 以降で0を出すために $\overline{B}\,\overline{C}$ をわざわざ付けている」項です。起きない入力のために回路が太っているわけです。

ドントケアを活用すると、

$$ f = A + BD + BC $$

3項・5リテラルまで縮みます。$A$ の項は「$A=1$ なら無条件で1」という意味で、$m_{10}$ 以降のドントケアを1と割り当てたことで成立しています。$BD$ は $\{5,7\}$ と $\{13,15\}$（ドントケア）を、$BC$ は $\{6,7\}$ と $\{14,15\}$（ドントケア）をまとめた4マス群です。$X$ を味方につけるだけで、リテラル数がほぼ半減しました。

例2: 7セグメントLEDのセグメント a

もっと実務的な例が7セグメントデコーダです。数字の上辺にあたるセグメント a は、$0,2,3,5,6,7,8,9$ を表示するとき点灯し、$1$ と $4$ のときだけ消灯します。オンセットは $\{0,2,3,5,6,7,8,9\}$、ドントケアはBCDと同じく $\{10,\dots,15\}$ です。

ドントケアを無視すると、

$$ a = \overline{A}C + \overline{A}\,\overline{B}\,\overline{D} + \overline{A}BD + A\overline{B}\,\overline{C} $$

4項・11リテラル。ドントケアを活用すると、

$$ a = A + C + \overline{B}\,\overline{D} + BD $$

4項・6リテラルになります。2つの例について、ドントケアを0に固定した場合と活用した場合のカルノー図を並べてみましょう。

各行の左が「$X$ を0に固定した場合」、中央が「$X$ をドントケアのまま活用した場合」、右がリテラル数の比較です。中央の図では橙色の $X$ のマスが群に取り込まれ、同じ数の群でありながら1つ1つの群が大きく育っていることが見て取れます。群が2倍になればリテラルが1つ減るので、「5以上」検出は9→5リテラル、7セグメントのセグメント a は11→6リテラルへ縮みました。棒グラフのタイトルにある通り、どちらも項数は変わっていません。ドントケアは「項を減らす」のではなく「群を太らせてリテラルを削る」自由度なのです。

教科書に載っている7セグメントデコーダの式がこの形をしているのは、まさにドントケアを使い切っているからです。項数は同じ4でも、リテラルが11から6へ減っており、これは配線数とトランジスタ数の直接の削減です。7セグメントデコーダはセグメント a から g まで7個の関数を実装するので、この節約が7回効きます。

なお実務では、ドントケアを本当にドントケアとして扱ってよいかの検証が要ります。$1010$ が絶対に来ないと言い切れず、来たときに表示が化けると困るなら、それはドントケアではなく仕様です。「気にしなくてよい」は設計判断であって、数学的な前提ではありません。

ドントケアで4変数の道具は完成しました。では変数が増えたらどうなるでしょうか。次は5変数への拡張を見ます。

5変数カルノー図への拡張

4変数までは平面の $4\times4$ で足りました。5変数 $A,B,C,D,E$ になると、ミンタームは32個。$8\times4$ に並べる方法もありますが、実用的なのは4変数カルノー図を2枚重ねるやり方です。1枚目を $A=0$ の面、2枚目を $A=1$ の面とし、それぞれの中は $BC$ と $DE$ をグレイコードで並べた通常の4変数図にします。

隣接関係は2種類になります。同じ面の中での上下左右の隣接（これは従来通り）に加えて、2枚の面の同じ位置どうしも隣接します。$A$ だけが違ってあとは全部同じだからです。したがって、2枚の図で同じ場所にある群を見つけたら、それらを重ねて1つの大きな群にでき、$A$ が消えます。

具体例を挙げます。

$$ g(A,B,C,D,E) = \Sigma m(0,1,4,5,10,11,14,15,16,17,20,21,25,27,29,31) $$

この関数の最小積和形は次のようになります。

$$ g = \overline{B}\,\overline{D} + \overline{A}BD + ABE $$

第1項の $\overline{B}\,\overline{D}$ は、$B=0, D=0$ を固定し $A, C, E$ を自由にした8マスの群です。ミンタームで書くと $\{0,1,4,5\}$（$A=0$ の面）と $\{16,17,20,21\}$（$A=1$ の面）で、2枚の面の同じ位置にある4マス群が上下に重なった形です。$2^3 = 8$ マスなので $5 – 3 = 2$ リテラルになり、$A$ が消えています。

第2項の $\overline{A}BD$ は $A=0$ の面だけに存在する4マス群（$\{10,11,14,15\}$）で、$A=1$ の面の対応位置には1がありません。だから $\overline{A}$ が残り、3リテラルになります。第3項の $ABE$ は逆に $A=1$ の面だけの群（$\{25,27,29,31\}$）です。

赤い群に注目すると、$A=0$ の面と $A=1$ の面のまったく同じ位置（左上の $2\times2$）に現れています。この2つは $A$ だけが違うので重ねられ、合わせて8マス＝$5-3=2$ リテラルの $\overline{B}\,\overline{D}$ になります。対して青い群は $A=0$ の面にしかなく、$A=1$ の同じ位置は0です。重ねられないので $\overline{A}$ が残り3リテラルのままです。緑も同様に $A=1$ の面だけの群です。「2枚を重ねて消せるか、片面だけで残るか」が、リテラルが1つ減るかどうかを分けているわけです。

つまり5変数図の読み方は、「まず2枚重ねて消える群を探し、次に片面だけの群を探す」という手順になります。6変数になると4枚の面（$AB$ の4通り）を管理することになり、面どうしの隣接関係もグレイコード順（$00,01,11,10$）で決まります。ここまで来ると、隣接の見落としが現実的なリスクになり、人間の視覚に頼る方法は限界を迎えます。

カルノー図の真価は、少ない変数で「なぜ簡単化できるのか」を体得することにあります。実務で6変数以上を扱うなら、同じ理論をアルゴリズムに落とし込む必要があります。それが次に見る Quine-McCluskey 法です。

Quine-McCluskey法 — カルノー図を機械化する

発想

カルノー図でやっていたことを、図を使わずに実行する手続きが Quine-McCluskey法（QM法）です。手順は2段階に分かれます。

1. 主項の生成: 結合定理を、もう結合できなくなるまで機械的に反復適用する
2. 最小被覆の選択: 被覆表から必須主項を抜き出し、残りを厳密に解く

第1段階: 主項の生成

まず、ミンターム（とドントケア）を $n$ ビットの文字列で表します。次に、1ビットだけ異なるペアをすべて探し、異なる位置を - に置き換えた新しいキューブを作ります。たとえば $0110$（$m_6$）と $1110$（$m_{14}$）から -110 が生まれ、これは $BC\overline{D}$ を表します。

ここが要点です。結合に一度でも使われたキューブは、より大きなキューブに吸収されるので主項ではありません。逆に、どの相手とも結合できなかったキューブは、それ以上大きくできない＝主項です。だから各ラウンドで「使われなかったキューブ」を回収し、「新しく生まれたキューブ」を次のラウンドに渡す、という処理を繰り返せば、主項が漏れなく集まります。

素朴に全ペアを試すと $O(N^2)$ ですが、古典的な実装ではビット中の1の個数でグループ分けし、隣接するグループ間（1の個数が1違うペア）だけを比較します。1ビットだけ異なるなら1の個数は必ず1違うので、これで正しさを失わずに比較回数を減らせます。

第2段階: 被覆の選択

主項が出そろったら、被覆表を作ります。必須主項の抽出は例題でやった通りです。それでも残る部分に対しては、いくつかの方法があります。

行支配・列支配による削減: あるミンターム行 $m_1$ の被覆主項集合が別の行 $m_2$ のそれを含むとき、$m_2$ を被覆すれば自動的に $m_1$ も被覆されるので、$m_1$ の行は削除できます。また、主項 $p_1$ の被覆集合が $p_2$ の被覆集合を含み、かつコストが同等以下なら、$p_2$ の列は削除できます。この削減を繰り返すと、多くの問題は必須主項だけで解けてしまいます。

Petrick法: 削減しても解けない場合の厳密解法です。発想はシンプルで、「ミンターム $m$ を被覆する」という条件を、$m$ を被覆する主項の論理和として書きます。たとえば $m_5$ が主項 $P_3$ と $P_4$ に被覆されるなら、条件は $(P_3 + P_4)$ です。すべてのミンタームについてこの条件を論理積でつなぐと、和積形の被覆条件式ができます。

$$ \Phi = (P_1 + P_2)(P_2 + P_3)(P_3 + P_4)\cdots $$

この $\Phi$ を分配則で展開して積和形に直すと、各積項が「1つの妥当な被覆」に対応します。展開の途中で吸収則 $u + uv = u$ を使って冗長な積項を捨てながら進め、最後に項数が最小、同点ならリテラル数が最小の積項を選べば、それが最小積和形です。展開は指数的に膨らむため大規模問題には向きませんが、10変数程度までなら十分実用になります。

貪欲法では最小にならない例

「毎回いちばん多くの未被覆ミンタームを覆う主項を選ぶ」という貪欲法は直感的ですが、最小を保証しません。有名な反例が巡回被覆（cyclic covering）です。

$$ h = \Sigma m(0,1,5,7,8,10,14,15) $$

この関数の主項は8個あり、必須主項が1つもありません。8個の主項はどれも3リテラルで、ちょうど2個のミンタームを覆います。被覆関係を辿ると、$m_0 – m_8 – m_{10} – m_{14} – m_{15} – m_7 – m_5 – m_1 – m_0$ という長さ8の輪になっています（各辺が主項に対応）。

輪の上で全頂点を覆う最小の辺集合は、1つおきに辺を選んだ4本です。Petrick法で解くと、次の2つの4項解が得られます。

$$ h = \overline{A}\,\overline{B}\,\overline{C} + \overline{A}BD + A\overline{B}\,\overline{D} + ABC $$ $$ h = \overline{B}\,\overline{C}\,\overline{D} + \overline{A}\,\overline{C}D + BCD + AC\overline{D} $$

どちらも4項・12リテラルで同点です。

中央のパネルが、この関数の被覆構造を輪として描いたものです。頂点が8個のミンターム、辺が「2マスを覆う主項」で、$m_0 – m_8 – m_{10} – m_{14} – m_{15} – m_7 – m_5 – m_1$ と一周してもとに戻ります。どの頂点にもちょうど2本の辺が接しているため、必須主項（＝1本しか辺が接していない頂点）が存在せず、緑で示した「1つおきに4辺」が最小解になります。右のパネルは、主項の選択順を $8!$ 通りすべて試した貪欲法の結果で、最小の4項に到達できるのはわずか5.4%、半数以上（57.1%）は5項、1.3%は最悪の7項という分布になりました。一方、貪欲法は選ぶ順番によって結果が変わります。すべての主項の選択順（$8!$ 通り）を試すと、最良は4項ですが、最悪では7項になります。「どれを選んでも同じ2マスが覆える」ため、貪欲法の判断基準が働かず、輪を分断するような不味い選び方をしてしまうのです。厳密解法が必要な理由が、この例に凝縮されています。

理論が完成したので、ここからはすべてをPythonで実装し、手作業の結論と一致することを確かめます。

Pythonによる実装

主項の生成

まず QM 法の第1段階を実装します。ミンタームを文字のタプルとして持ち、1ビット差のペアを結合していきます。

from itertools import combinations

def to_cube(m, n):
    """ミンターム番号 m を n ビットの文字タプルへ（先頭が最上位変数）"""
    return tuple(format(m, '0{}b'.format(n)))

def combine(c1, c2):
    """1ビットだけ異なるキューブを結合し、その位置を '-' にする"""
    diff = [i for i in range(len(c1)) if c1[i] != c2[i]]
    if len(diff) != 1:
        return None
    merged = list(c1)
    merged[diff[0]] = '-'
    return tuple(merged)

def prime_implicants(minterms, dontcares, n):
    """QM法 第1段階: 結合できなくなるまで繰り返して主項を集める"""
    cubes = {to_cube(m, n) for m in list(minterms) + list(dontcares)}
    pis = set()
    while cubes:
        nxt, used = set(), set()
        for a, b in combinations(sorted(cubes), 2):
            c = combine(a, b)
            if c is not None:
                nxt.add(c); used.add(a); used.add(b)
        pis |= (cubes - used)   # 誰とも結合できなかった = 主項
        cubes = nxt
    return sorted(pis)

def cube_str(cube, names):
    """キューブを積項の文字列へ（'0' は補元なので ' を付ける）"""
    s = ''.join(names[i] + ("" if c == '1' else "'")
                for i, c in enumerate(cube) if c != '-')
    return s or '1'

NAMES4 = ['A', 'B', 'C', 'D']
MT = [0, 1, 2, 5, 6, 7, 8, 9, 10, 14]
pis = prime_implicants(MT, [], 4)
print('主項:', [cube_str(p, NAMES4) for p in pis])

実行すると 主項: ["CD'", "B'D'", "B'C'", "A'C'D", "A'BD", "A'BC"] と表示されます（' は補元を表し、B'C' は $\overline{B}\,\overline{C}$ の意味です）。手作業でカルノー図から読み取った6個の主項と完全に一致しました。特に、端の巻き込みで見つけた $\overline{B}\,\overline{D}$ と $\overline{B}\,\overline{C}$ もきちんと出ています。アルゴリズムは図形を見ていませんが、ハミング距離1の結合を尽くすだけで同じ結論に到達する点が重要です。

被覆表と必須主項

第2段階に進みます。被覆表を辞書で作り、被覆主項が1つしかない行から必須主項を集めます。

def covers(cube, m, n):
    """キューブ cube がミンターム m を含むか"""
    b = to_cube(m, n)
    return all(c == '-' or c == b[i] for i, c in enumerate(cube))

def essential_pis(pis, minterms, n):
    """被覆表を作り、必須主項と、未被覆のまま残るミンタームを返す"""
    table = {m: [i for i, p in enumerate(pis) if covers(p, m, n)] for m in minterms}
    ess = {row[0] for row in table.values() if len(row) == 1}
    covered = {m for m in minterms if any(covers(pis[i], m, n) for i in ess)}
    return table, sorted(ess), sorted(set(minterms) - covered)

table, ess, rest = essential_pis(pis, MT, 4)
for m in MT:
    print('m{:<3d} {} : {}'.format(m, format(m, '04b'),
          ', '.join(cube_str(pis[i], NAMES4) for i in table[m])))
print('必須主項:', [cube_str(pis[i], NAMES4) for i in ess], '／ 残り:', rest)

出力される被覆表は、先ほど手で作った表と同じ内容になります。$m_9$ の行には B'C' だけ、$m_{14}$ の行には CD' だけが並び、最後の行に 必須主項: ["CD'", "B'C'"] ／ 残り: [5, 7] と出ます。手作業で「1つしか主項がない行」を目で探した作業が、len(row) == 1 という1行の条件に置き換わりました。残るミンタームが $m_5$ と $m_7$ だけになるところまで、手計算と一致しています。

Petrick法と最小化関数

残った部分を Petrick 法で厳密に解き、真理値表から最小積和形を返す関数にまとめます。

def petrick(pis, minterms, n):
    """Petrick法: 各ミンタームの被覆条件(論理和)の積を展開し、最小解を選ぶ"""
    products = [frozenset()]
    for m in minterms:
        options = [frozenset([i]) for i, p in enumerate(pis) if covers(p, m, n)]
        expanded = {a | o for a in products for o in options}
        keep = []                                   # 吸収則で冗長な積項を捨てる
        for s in sorted(expanded, key=len):
            if not any(k <= s for k in keep):
                keep.append(s)
        products = keep
    lit = lambda s: sum(sum(1 for c in pis[i] if c != '-') for i in s)
    return min(products, key=lambda s: (len(s), lit(s)))

def minimize(minterms, dontcares, n, names):
    """真理値表(オンセットとドントケア)から最小積和形の項リストを返す"""
    pis = prime_implicants(minterms, dontcares, n)
    table, ess, rest = essential_pis(pis, minterms, n)
    chosen = set(ess) | (set(petrick(pis, rest, n)) if rest else set())
    return [pis[i] for i in sorted(chosen)], pis

terms, pis = minimize(MT, [], 4, NAMES4)
print('最小積和形: f =', ' + '.join(cube_str(t, NAMES4) for t in terms))
print('リテラル数:', sum(sum(1 for c in t if c != '-') for t in terms))

出力は 最小積和形: f = CD' + B'C' + A'BD と リテラル数: 7 です。手作業で導いた $f = C\overline{D} + \overline{B}\,\overline{C} + \overline{A}BD$ と一致しました。集合被覆を厳密に解いているので、これが本当に最小であることも保証されています。petrick の中で吸収則による枝刈り（if not any(k <= s for k in keep)）を入れているのがポイントで、これがないと展開した積項の数が爆発します。

カルノー図に選ばれた群を描く

アルゴリズムの答えと図形が一致することを、目で確かめましょう。前に定義した draw_kmap と kmap_pos をそのまま使い、選ばれた項ごとに色を変えて枠を描きます。

import matplotlib.pyplot as plt

COLORS = ['#e8453c', '#2b7bba', '#39a25a', '#e8a33c', '#8e5bbf']

fig, ax = plt.subplots(figsize=(6.0, 5.6))
draw_kmap(ax, lambda m: '1' if m in MT else '0', '最小積和形として選ばれた群')
for k, t in enumerate(terms):
    col = COLORS[k % len(COLORS)]
    for m in range(16):
        if covers(t, m, 4):
            r, c = kmap_pos(m)
            # 群ごとに枠を少しずつ内側にずらし、重なっても見えるようにする
            ax.add_patch(plt.Rectangle((c + 0.06 + 0.05 * k, 3 - r + 0.06 + 0.05 * k),
                                       0.88 - 0.1 * k, 0.88 - 0.1 * k,
                                       fc='none', ec=col, lw=2.4))
    ax.plot([], [], color=col, lw=3, label=cube_str(t, NAMES4))
ax.legend(loc='lower left', bbox_to_anchor=(-0.05, -0.02), fontsize=10, frameon=False)
plt.tight_layout()
plt.show()

このコードが出力するのが、先ほど見た最小被覆の図です。赤い枠が右端の列4マス（$m_2, m_6, m_{10}, m_{14}$ = $C\overline{D}$）、青い枠が上下に分かれた4マス（$m_0, m_1, m_8, m_9$ = $\overline{B}\,\overline{C}$）、緑の枠が中央の横2マス（$m_5, m_7$ = $\overline{A}BD$）を囲みます。青い群が図の上端と下端に分断されて描かれることが、グレイコード配置の巻き込み（トーラス構造）を視覚的に示しています。数値順の真理値表なら $m_0$ と $m_8$ が同じ群に入る理由は見えませんが、この図では上下がつながっていると分かれば納得できます。1が10個あるうち、3つの枠がすべての1を漏れなく覆い、0のマスには枠が一切かかっていないことも確認できます。

ドントケアの効果を測る

BCDの2つの例で、ドントケアを使う場合と使わない場合を比較します。

def report(name, on, dc):
    t1, _ = minimize(on, dc, 4, NAMES4)     # ドントケアあり
    t0, _ = minimize(on, [], 4, NAMES4)     # ドントケアなし（強制的に0）
    fmt = lambda ts: (' + '.join(cube_str(t, NAMES4) for t in ts),
                      sum(sum(1 for c in t if c != '-') for t in ts))
    print(name)
    print('  ドントケアなし: f = {}  （{}リテラル）'.format(*fmt(t0)))
    print('  ドントケアあり: f = {}  （{}リテラル）'.format(*fmt(t1)))

DC_BCD = [10, 11, 12, 13, 14, 15]
report('BCD入力の「5以上」検出', [5, 6, 7, 8, 9], DC_BCD)
report('7セグメントLED セグメントa', [0, 2, 3, 5, 6, 7, 8, 9], DC_BCD)

出力は次の通りです。「5以上」検出は A'BD + A'BC + AB'C'（9リテラル）から BD + BC + A（5リテラル）へ、7セグメントのセグメント a は A'C + A'B'D' + A'BD + AB'C'（11リテラル）から C + B'D' + BD + A（6リテラル）へ縮みました。どちらも項数は変わらず、リテラル数だけが4〜5個減っている点に注目してください。ドントケアの効果は「群を大きくしてリテラルを削る」形で現れ、項数（＝ORの入力数）にはあまり効かないことが多い、という傾向がここに出ています。7セグメントデコーダはこれを7出力分行うので、削減量は積み上がります。

簡単化の効果を数える

最後に、コスト指標を実際に計算して比較します。2入力ゲート換算のゲート数と段数を数える関数を書きます。

import math
import matplotlib.pyplot as plt

def cost(terms, n):
    """リテラル数・2入力ゲート換算のゲート数・ゲート段数を返す"""
    size = lambda t: sum(1 for c in t if c != '-')
    lits = sum(size(t) for t in terms)
    and_g = sum(max(0, size(t) - 1) for t in terms)          # 各積項のANDツリー
    and_d = max(math.ceil(math.log2(max(1, size(t)))) for t in terms)
    or_g = max(0, len(terms) - 1)                            # 全体のORツリー
    or_d = math.ceil(math.log2(len(terms))) if len(terms) > 1 else 0
    inv = len({i for t in terms for i, c in enumerate(t) if c == '0'})  # インバータ
    return lits, and_g + or_g + inv, and_d + or_d

canon = [to_cube(m, 4) for m in MT]      # 正準積和形（ミンタームをそのまま並べる）
c0, c1 = cost(canon, 4), cost(terms, 4)
print('正準積和形:', c0, ' 最小積和形:', c1)

labels = ['リテラル数', '2入力ゲート数', 'ゲート段数']
fig, axes = plt.subplots(1, 3, figsize=(11, 3.4))
for ax, lab, a, b in zip(axes, labels, c0, c1):
    ax.bar(['簡単化前\n(正準積和形)', '簡単化後\n(最小積和形)'], [a, b],
           color=['#9aa5b1', '#2b7bba'])
    for i, v in enumerate([a, b]):
        ax.text(i, v, str(v), ha='center', va='bottom', fontsize=11, fontweight='bold')
    ax.set_title(lab, fontsize=11)
    ax.set_ylim(0, max(a, b) * 1.25)
plt.suptitle('簡単化によるハードウェアコストの変化', fontsize=13)
plt.tight_layout()
plt.show()

出力は 正準積和形: (40, 43, 6) 最小積和形: (7, 10, 4) です。棒グラフの3枚のパネルが、それぞれ 40→7、43→10、6→4 と大きく下がる様子を示します。リテラル数は約6分の1、ゲート数は約4分の1、段数は3分の2になりました。段数の減り方がゲート数ほど劇的でないのは、二段論理という構造自体は変わらず、AND木とOR木の幅が狭くなった分だけ浅くなっているためです。遅延よりも面積・消費電力への効果が大きい、というのが二段論理最小化の典型的な性格です。

巡回被覆で貪欲法が失敗することを確認する

理論編で挙げた巡回被覆の例を、実際に走らせて確かめます。

import itertools

CYC = [0, 1, 5, 7, 8, 10, 14, 15]
pis_c = prime_implicants(CYC, [], 4)
_, ess_c, rest_c = essential_pis(pis_c, CYC, 4)
print('主項数:', len(pis_c), '／ 必須主項:', ess_c)

best = petrick(pis_c, CYC, 4)
print('Petrick法の最小解:', ' + '.join(cube_str(pis_c[i], NAMES4) for i in sorted(best)))

def greedy(order):
    """与えられた優先順で主項を選ぶ素朴な貪欲法。選んだ項数を返す"""
    rem, chosen = set(CYC), []
    for i in order:
        if not rem:
            break
        hit = {m for m in rem if covers(pis_c[i], m, 4)}
        if hit:
            chosen.append(i)
            rem -= hit
    return len(chosen)

sizes = [greedy(p) for p in itertools.permutations(range(len(pis_c)))]
print('貪欲法の項数 最良/最悪:', min(sizes), max(sizes))

結果は 主項数: 8 ／ 必須主項: []、Petrick法の最小解: A'B'C' + A'BD + AB'D' + ABC、貪欲法の項数 最良/最悪: 4 7 です。必須主項が空リストになっていることが、この問題が巡回被覆であることの証拠です。そして貪欲法は、選択順によって4項にも7項にもなります。最悪の場合、最小解の1.75倍の項数の回路ができてしまうわけで、被覆の選択を真面目に解く価値がここに現れています。実際の論理合成ツールも、この部分に分岐限定法やヒューリスティックを投入しています。

ランダムな関数での平均的な効果

最後に、例題1つだけでは分からない「平均的にどれくらい効くのか」を測ります。4変数のランダムな関数を300個生成し、正準積和形と最小積和形のリテラル数を比べます。

import random
import statistics
import matplotlib.pyplot as plt

random.seed(0)
before, after = [], []
for _ in range(300):
    ms = sorted(random.sample(range(16), random.randint(4, 12)))
    ts, _ = minimize(ms, [], 4, NAMES4)
    before.append(4 * len(ms))
    after.append(sum(sum(1 for c in t if c != '-') for t in ts))

ratio = [1 - a / b for a, b in zip(after, before)]
print('平均リテラル数 {:.1f} → {:.1f}（平均削減率 {:.1%}）'.format(
    statistics.mean(before), statistics.mean(after),
    1 - statistics.mean(after) / statistics.mean(before)))

fig, ax = plt.subplots(figsize=(7, 4))
ax.hist(ratio, bins=20, color='#2b7bba', edgecolor='white')
ax.axvline(statistics.mean(ratio), color='#e8453c', lw=2,
           label='平均 {:.1%}'.format(statistics.mean(ratio)))
ax.set_xlabel('リテラル数の削減率')
ax.set_ylabel('関数の個数')
ax.set_title('ランダムな4変数論理関数300個の簡単化効果')
ax.legend()
plt.tight_layout()
plt.show()

出力は 平均リテラル数 32.3 → 11.2（平均削減率 65.4%） です。ここで表示している 65.4% は「リテラル数の平均どうしの比」ですが、ヒストグラムが描いているのは関数ごとの削減率で、その平均（赤い線）は 61.3% になります。個々の関数を平等に扱うか、リテラル数の多い関数を重く見るかの違いで、数パーセントずれるわけです。分布そのものは0.2から0.95あたりに広がっており、山の中心はおおむね0.5〜0.8にあります。ランダムに作った関数でさえ、平均して6割前後のリテラルが削れるという事実は、簡単化が特殊な例題だけの話ではないことを示しています。分布に幅があるのは関数の性質によるもので、1が固まっている関数（大きな群が作れる）は右側に、1が散らばっている関数（群が育たない）は左側に来ます。右の散布図はこの傾向を別の角度から測ったもので、オンセットが4個しかない関数では削減率の中央値が0.375にとどまるのに対し、11個ある関数では0.795まで上がります。1が多いほど大きな部分立方体が成立しやすいという直感が、実測値としてきれいに現れています。

実装と実験を通じて、手作業のカルノー図とアルゴリズムが同じ答えを出すことを確認できました。最後に、この先の話題を整理しておきます。

積和形の先へ — 和積形・NAND化・そして現代の合成

積和形（SOP）は AND-OR の二段構成ですが、双対の和積形（POS）も同じ図から求められます。手順は「0のマスをまとめて補関数 $\overline{f}$ の最小積和形を作り、ド・モルガンの法則で反転する」だけです。例題の0のマスは $\{3,4,11,12,13,15\}$ で、これを最小化すると、

$$ \overline{f} = \overline{B}CD + B\overline{C}\,\overline{D} + ABD $$

が得られます。両辺を反転してド・モルガンを適用すると、

$$ f = \overline{\overline{B}CD + B\overline{C}\,\overline{D} + ABD} = (B + \overline{C} + \overline{D})(\overline{B} + C + D)(\overline{A} + \overline{B} + \overline{D}) $$

3項・9リテラルの和積形になります。

左は1のマス（薄赤）を群にまとめた積和形、右は0のマス（薄青）を群にまとめた和積形です。同じ関数・同じカルノー図でありながら、どちらの色を囲むかで得られる式の形がまったく変わります。今回の例題は1が10個・0が6個で0のほうが少ないにもかかわらず、積和形が7リテラル、和積形が9リテラルと積和形のほうが安くなりました。0の少なさが必ず和積形の有利につながるわけではなく、群がどれだけ大きく育つかで決まるということです。両方を計算して安いほうを採るのが定石です。

また、CMOSでは AND や OR より NAND / NOR のほうがトランジスタ数が少なくて済みます。積和形は $f = p_1 + p_2 + p_3$ に二重否定を入れて $f = \overline{\overline{p_1} \cdot \overline{p_2} \cdot \overline{p_3}}$ と書き換えれば、すべて NAND ゲートだけの2段回路に変換できます。段数も構造も変わらないので、リテラル数の最小化はそのまま NAND 実装のコスト最小化になります。

一方で、QM法の限界も明らかです。主項の個数は最悪の場合 $n$ 変数で $3^n/n$ のオーダーまで増えることが知られており、被覆問題自体も NP困難です。10変数を超えると厳密解は現実的でなくなります。そこで実用の論理合成では、ESPRESSO のようなヒューリスティック（主項を全列挙せず、展開・削減・再展開を繰り返して局所改善する）や、二分決定図（BDD）、SAT ソルバを使った手法が使われます。さらに、FPGAではLUT（ルックアップテーブル）が基本素子なので、「リテラル数」ではなく「LUT数」を最小化する別の技術マッピングが必要になります。

それでも、これらすべての土台にあるのは本記事で見た「インプリカント・主項・被覆」という枠組みです。カルノー図は、その枠組みを4変数という手に負えるサイズで完全に可視化してくれる教材であり、だからこそ半世紀以上たった今も教科書の最初のほうに載り続けています。

まとめ

本記事では、カルノー図による論理式の簡単化を、原理からアルゴリズム実装まで通して解説しました。

• 簡単化のコストは3つの指標で測る — リテラル数、2入力ゲート換算のゲート数、ゲート段数。例題では正準積和形の40リテラル・43ゲート・6段が、最小積和形で7リテラル・10ゲート・4段に減りました
• カルノー図はグレイコードで並べ替えた真理値表 — 反射型グレイコード $G(i) = i \oplus \lfloor i/2 \rfloor$ の性質から、隣接マスのハミング距離が1になり、さらに端と端も距離1なのでカルノー図はトーラス構造を持ちます
• $2^k$ マスの部分立方体は $n-k$ リテラルの積項に等しい — 自由変数のミンターム和が恒等的に1になることから導かれ、「大きく囲むほどリテラルが減る」「3マスは囲めない」という規則の根拠になります
• 最小積和形は主項だけからなる（Quineの定理） — 非主項を含む解は必ずリテラルを減らせるため。ただし主項を全部使うのが最小とは限らず、例題では6個の主項のうち3個だけを使いました
• 必須主項を先に確定させ、残りを被覆問題として解く — 必須主項はある1のマスを唯一被覆する主項で、どんな解にも必ず含まれます
• ドントケアは群を大きくする自由度 — 主項生成には参加させ、被覆表の行には入れません。BCDの「5以上」検出は9リテラルから5リテラルへ、7セグメントのセグメント a は11リテラルから6リテラルへ縮みました
• QM法とPetrick法でアルゴリズム化できる — 貪欲法は巡回被覆で失敗し、実験では最小4項に対して最悪7項の解を出しました
• 最小形が常に最良ではない — コンセンサス項（例題では $\overline{B}\,\overline{D}$）を意図的に残すことで、静的1ハザードを防げます

論理式の簡単化は、真理値表という仕様から実際のハードウェアへ橋を架ける最初の工程です。ここで身につけた「主項・被覆・冗長性」という見方は、組合せ回路にとどまらず、順序回路の状態割り当てや、状態機械の出力ロジック設計にもそのまま持ち込めます。

次のステップとして、以下の記事も参考にしてください。

• デジタル回路の基礎 — 論理ゲートからブール代数・カルノー図まで完全解説
• フリップフロップと順序回路 — 記憶素子からカウンタ・状態機械まで