クワイン・マクラスキー法

この記事は ひとりアドベントカレンダーRosettaCodeで楽しむプログラミング Advent Calendar 2025の17日めの記事です。

論理式の簡単化を機械的に行う（仕事の一部をする）アルゴリズム

pedia.ja にアルゴリズムが説明されている。英語版からの翻訳。
pedia.en こちらでは、さらにpseudo codeによる追加の説明がある、のだが…

タスク

真理値関数が与えられる。真理値表、最小項の集合、カルノー図、形式は問わない。
その関数の積和形での最簡形を求めよ。

Wikipediaを見ながら、アルゴリズムを整理する：

アルゴリズム

入力：関数の出力を1にする入力パターン（最小項という）のリストと、
関数の出力を1にしてもよい（0でもよい、ドントケア）（擬最小項と呼ぼう）のリスト

手順は3つの段階に分かれている。

1 主項の生成

最小項と偽最小項全体の集合から始め、違いが1ビットだけの二つを統合することで、より小さな項に直していく。
（$ABC + AB\overline{C} \Rightarrow AB$ のような）
一度も使わなかった最小項は脇によけておく。
新たに生成された項だけを使ってこの操作を繰り返す。
項が生成されなくなったら、脇へよけておいた項の全体が主項と呼ばれるものとなる。

主項とは、統合元になった最小項全ての代理となるもので、
主項をいくつか選択して、全ての最小項をカバーできれば、元の関数を再現できる。
なので、その最小の組み合わせを作りたい。

2 必須項を求める

最小項のうち、自分を代表する主項の選択肢が一つしかないものは、それが必ず最終結果に含まれることになる。
そのような確定する主項を必須項という。

3 最簡形を求める

必須項だけでは全ての最小項を代理できずに漏れがあるので、
残った主項を組み合わせて、それらを全て代理できる、最もコストの安い組み合わせを探す。

• 総当たり（ja.pediaには『試行錯誤』と書いてある）
• ペトリック法

などのやり方がある。

と、説明されてはいるのだが

後半に行くほど説明は尻すぼみになり、最簡形は「総当たりで」以上の説明がない。
ペトリック法に関する言及では、英語版からの訳に不備があり、具体例の話が一般論のように述べられている。
実際、最簡形を求める段階は、選んだ主項の組み合わせによるコストを最小化し、代理する最小項の組み合わせをスコアとする、変わったナップサック問題と解釈することができる、上手いやり方のないNP困難な問題である。
ペトリック法は「系統的」と紹介されているが、内容は総当たりしているのと何も変わらず、別の問題に対応付けて解釈できる、という説明をしているだけにすぎない。

アルゴリズムと称するものには、入力、計算の手順、そして「出力」が必要だと思うのだが、出力が何か明確に定義されておらず、手順にも何を出力するという話なしに終わっている。

日本語翻訳版では省略されているが、英語版ではこの続きに、擬似コードによる説明がある。
しかし、擬似コードで実行できないゆえのバグ、表記揺れ、抽象度のばらつき、肝心な部分の省略など、読むほどに腹が立つ内容になっている。

また、最簡形を求める最後のステップに関しては「必須項で全ての最小項を代理できると仮定する」とふざけたことを言い捨ててコードなしに終わっている。

以下、そのコードを読み解きながら、アルゴリズムを記述するによりふさわしい言語で書き直していこう。

このウンコードを書いたのは誰だあっ！

全ての項は 1 （信号 $A$ などを表す） 0 （信号 $\overline{A}$ などを表す）そして参照しないことを表す - からなる、同じ長さ（入力ビット数）の文字列で表す。
入力は、最小項のリストと、擬最小項のリストで与えられるとする。これは 0と1だけからなる。

Step 1: Finding the prime implicants

まずはその補助関数から。3つある。

• MergeMinterms

最小項、もしくは主項なりかけの項2つで、違いが1ビットだけなので統合できるようなものが与えられる。
その違いの1ビットを - に置き換えた項を作る。

function MergeMinterms(minterm1, minterm2) is
    mergedMinterm ← empty string
    for i = 0 to length(minterm1) do
        //If the bits vary then replace it with a dash, otherwise the bit remains in the merged minterm.
        if minterm[i] != minterm2[i] then
            mergedMinterm ← mergedMinterm + '-'
        else
            mergedMinterm ← mergedMinterm + minterm1[i]
    return mergedMinterm

if文条件式の左辺mintermはminterm1のtypo
文字列が文字ごとに配列のようにランダムアクセスできるので、その文字の位置というインデックスを使って回す、というK&R Cのような「実装」を、pseudo language によるアルゴリズムの説明と言い張っている。
Haskellに直訳すればこのようになるだろうか。

type Term = String

mergeMinterms :: Term -> Term -> Term
mergeMinterms minterm1 minterm2 = zipWith f minterm1 minterm2
      where
-- ビットが等しいならそのまま、異なるなら '-' に置き換える
        f c d | c == d    = c
              | otherwise = '-'

これすら「実装」だと思うなら、冒頭に示した自然言語の説明で十分だ。それが擬似コードだ。

• CheckDashesAlign

mergeMinterms が適用できる条件のひとつは、二つの項の - の位置が揃っていることである。
片方がハイフンのある位置は、もう一方もハイフンでなくてはならない。
この条件を満たしているか検査しようとしている。

function CheckDashesAlign(minterm1, minterm2) is
    for i = 0 to length(minterm1) do
        // If one minterm has dashes and the other does not then the minterms cannot be merged.
        if minterm1[i] != '-' && minterm2[i] == '-' then
            return false
    return true

えーとなになに？

全ての文字について順に調べて
　　項1で '-' でない　かつ　項2で '-' である
　　　　ならば失敗
最後まで失敗にならなかったら成功

ややこしいんじゃ。

項1	項2	正解	コードの式
'0'/'1'	'0'/'1'	○	続行（せいかい）
'0'/'1'	'-'	×	中断（せいかい）
'-'	'-'	○	続行（せいかい）
'-'	'0'/'1'	×	続行（まちがい！）

駄目じゃん。

その点を直すことも含めてHaskellにする：

checkDashesAlign :: Term -> Term -> Bool
checkDashesAlign minterm1 minterm2 = all prop $ zip minterm1 minterm2
  where
    f ('-', d) = d == '-' -- cが == '-' ならdもそう
    f ( _ , d) = d /= '-' -- cが /= '-' ならdもそう
-- 別解
    f c d = (c == '-') == (d == '-') -- cが'-'かどうかと、dが'-'かどうかが、同じ

-- もっと平易に「どちらかが '-' なら両方 '-'」
checkDashesAlign minterm1 minterm2 = and
  [a == b | (a,b) <- zip minterm1 minterm2, a == '-' || b == '-']

• CheckMintermDifference

二つの項の違いが1ビットだけであるか調べる。

function CheckMintermDifference(minterm1, minterm2) is
    // minterm1 and minterm2 are strings representing all of the currently found prime implicants and merged
    // minterms. Examples include '01--' and '10-0'
    m1, m2 ← integer representation of minterm1 and minterm2 with the dashes removed, these are replaced with 0
    // ^ here is a bitwise XOR
    res ← m1 ^ m2
    return res != 0 && (res & res - 1) == 0

違いを数えるのに「2進数のtrailing zeroを数える」テクニックの類似手法を使っている。

任意の2進数について、1を引くと、繰り下がりがおきて、trailing zeroが全て1になり、
繰り下がりで最下位のビット1が0になる。
引く前の値 x と x-1 との bitwise XOR をとると、1引くことによって変化したこれらのビットだけが1になり、他は0になるので、あとは popCount すると trailing zero のビット数+1が得られる。

ここで xor の代わりに bitwise AND をとると、変化したビットが全て0になり、繰り下がりで守られた、最下位の1以外のビットだけが残る。
残るはずなのに結果が0なら、それは、元の値には1のビットが一つしかなかったということ。

さて、2進数に直そうにも、minterm1 や 2 には 0 1 だけでなく - もある。
でも、CheckMintermDifference が呼ばれる前に、これらの項は checkDashesAlign に合格している前提なので、ハイフンは0と読み替えてしまって構わない。なので

m1, m2 ← integer representation of minterm1 and minterm2 with the dashes removed, these are replaced with 0

（訳：minterm1とminterm2の整数表現、なお、ダッシュは0に置き換えて）

そこをそれだけざっくり書いて終わりでいいなら、この関数の動作も冒頭の一言で終わりでいいよ。
というか xor とって 1 引いて and とるとか、それはただの実装だよ。

Numericライブラリを使って、-を0と同一視する二進数 ReadS Int を作っても仕方ないので、上2つと同じように、1文字ずつ調べるという抽象度で書き直しましょう。
ハイフンの位置は一致しているので、違いがあるとすれば 0 と 1 なので、それだけ数える。

import Data.List

checkMintermDifference :: Term -> Term -> Bool
checkMintermDifference minterm1 minterm2 =
  compareLength (filter (/=) $ zip minterm1 minterm2) 1 == EQ

-- もっと平易に
checkMintermDifference minterm1 minterm2 =
  1 == length [() | (a,b) <- zip minterm1 minterm2, a /= b]

• getPrimeImplicants

大丈夫？ついてきてる？ようやくステップ1の本体。

// Computes the prime implicants from a list of minterms.
// each minterm is of the form "1001", "1010", etc and can be represented with a string.
function getPrimeImplicants(list minterms) is
    primeImplicants ← empty list
    merges ← new boolean array of length equal to the number of minterms, each set to false
    numberOfmerges ← 0
    mergedMinterm, minterm1, minterm2 ← empty strings

    for i = 0 to length(minterms) do
        for c = i + 1 to length(minterms) do
            minterm1 ← minterms[i]
            minterm2 ← minterms[c]
            // Checking that two minterms can be merged
            if CheckDashesAlign(minterm1, minterm2) && CheckMintermDifference(minterm1, minterm2) then
                mergedMinterm ← MergeMinterms(minterm1, minterm2)
                if primeImplicants Does Not Contain mergedMinterm then
                    primeImplicants.Add(mergedMinterm)
                numberOfMerges ← numberOfMerges + 1
                merges[i] ← true
                merges[c] ← true

    // Filtering all minterms that have not been merged as they are prime implicants. Also removing duplicates
    for j = 0 to length(minterms) do
        if merges[j] == false && primeImplicants Does Not Contain minterms[j] then
            primeImplicants.Add(minterms[j])

    // if no merges have taken place then all of the prime implicants have been found so return, otherwise
    // keep merging the minterms.
    if numberOfmerges == 0 then
        return primeImplicants
    else
        return getPrimeImplicants(primeImplicants)

流れは以下の通り：
最小項（とそれを mergeMinterms した結果）のリストを引数にとり、
全ての組み合わせについてマージできるならしたものを作る。
一度もマージができなかったならそれで完了。
一度でもできたときは、「一度もマージに使わなかった引数」をマージ結果に足して自己再帰で繰り返し。

本来は、一度もマージに使わなかった引数は脇へ避けておき、全て終わった後の結果に継ぎ足せば済むのだが、そうやって戻って来たくない、末尾再帰最適化した形にしたい、ということなのか、次の引数に混ぜ込んでいる。
それらは、今回マージに使えなかったのだから、これ以降もマージに使われることはなく、そこに混ざっていても結果は変わらない。
しかし「引数の全ての2つの組み合わせ」で二重ループしているその回数を無駄に増やして実行速度を悪化させている。

引数の項が一度でも使われたか、をチェックするために merges[] という真理値の配列を使っている。
しかし一方で「一度でもマージが実行できたか」を知るためだけに、マージができた回数を numberOfmerges でカウントしている。無駄。なぜ同じロジックを使わない。

そもそも、二重ループが終了した時点で primeImplicants が空なら、一度もマージできなかったとわかる。
その場合、引数をそのまま結果として途中脱出すれば、それ以降の計算を無駄にやる必要がない。
しかしなぜか、「return は一箇所にせよ」というMISRA-Cの規則にでも従っているのか、末尾に2つ return を書いている。

primeImplicants は集合だ、と宣言すればいいのに「まだ含まれていないならば含める」という集合の実装が混入している。

以上の分析を踏まえてHaskell化しよう。

import qualified Data.Set as S

-- 最小項と擬最小項のリストから主項を求める
getPrimeImplicants :: [Term] -> [Term]
getPrimeImplicants = S.elems . go . S.fromList
  where
    go minterms
      | null pairs4merge = minterms
      | otherwise        = S.union unused $ go mergedTerm
      where
-- mergeするべきmintermの組、を総当たりから抽出
        pairs4merge = [ (mt1,mt2) | mt1:mt2s <- tails $ S.elems minterms, mt2 <- mt2s
                      , checkDashesAlign mt1 mt2, checkMintermDifference mt1 mt2]
-- mergeで作られた新しいterm
        mergedTerm = S.fromList $ map mergeMinterms pairs4merge
-- 一度もmergeに使わなかったtermを洗い出し
        unused = minterms S.\\ S.fromList (map fst pairs4merge) S.\\ S.fromList (map snd pairs4merge)

pairs4merge の生成器がHaskellの総当たりイディオムが入っている以外、平易に読める記述になっていると思う。
とはいえ元の

for i = 0 to length(minterms) do
    for c = i + 1 to length(minterms) do

に比べれば可愛いものだろう。

Step 2: Prime implicant chart

奇妙な補助関数から。

function ConvertToRegularExpression(string primeImplicant)
    regularExpression ← new string
    for i = 0 to length(primeImplicant) do
        if primeImplicant[i] == "-" then
            // Add the literal character "\d".
            regularExpression += @"\d"
        else
            regularExpression += primeImplicant[i]
    return regularExpression

@ が何だかよくわからないが、termの中のダッシュをバックスラッシュdに置き換えている。

is used to convert the prime implicant into the regular expression to check for matches between the implicant and the minterms.

（訳：主項と最小項がマッチするか（主項が最小項の代理となっているか）を調べるために、主項を正規表現に直す）

先の2進数テクが霞むほどのベタベタな実装が飛び出しました。他と同様に一文字ずつ調べるではダメだったんですか？
これは放置。

本体：ステップ1で作った主項のリストと、今度はドントケアは含まない最小項のリストを引数にとり、
主項に対して、各最小項を代理するかを 0/1 の並びで表現した文字列を対応付けた連想配列を構築する。
minterms に渡された位置の順序で文字列にする。

これは「必須項を求める」のに使う「横軸に最小項（Don't care でないもの）、縦軸に求めた主項を書いた表」に相当する。

function CreatePrimeImplicantChart(list primeImplicants, list minterms)
    primeImplicantChart ← new dictionary with key of type string and value of type string
    // Creating the empty chart with the prime implicants as the key and empty strings as the value.
    for i = 0 to length(primeImplicants) do
        // Adding a new prime implicant to the chart.
        primeImplicantChart.Add(primeImplicants[i], "")

    for i = 0 to length(primeImplicantChart.Keys) do
        primeImplicant ← primeImplicantChart.Keys[i]
        // Convert the "-" to "\d" which can be used to find the row of ticks above.
        regularExpression ← ConvertToRegularExpression(primeImplicant)
        for j = 0 to length(minterms) do
            // If there is a match between the regular expression and the minterm than append a 1 otherwise 0.
            if regularExpression.matches(minterms[j]) then
                primeImplicantChart[primeImplicant] += "1"
            else
                primeImplicantChart[primeImplicant] += "0"

    // The prime implicant chart is complete so return the completed chart.
    return primeImplicantChart

あえて書くとこんな感じだろうか。

import qualified Data.Map as M
import Data.Bool

createPrimeImplicantChart :: [Term] -> [Term] -> M.Map Term String
createPrimeImplicantChart primeImplicants minterms = M.fromList
    [ (prim, map (bool '0' '1' . matches prim) minterms)
    | prim <- primeImplicants ]
  where
    matches prim mt = all p $ zip prim mt
    p ('-', _ ) = True
    p ( c , d ) = c == d

表ができたので、必須項を取り出す。

function getEssentialPrimeImplicants(Dictionary primeImplicantChart, list minterms)
    essentialPrimeImplicants ← new list
    mintermCoverages ← list with all of the values in the dictionary
    for i = 0 to length(ticks) do
        mintermCoverage ← ticks[i]
        for j = 0 to length(mintermCoverage) do
            if mintermCoverage[j] == "1" then
                essentialPrimeImplicants.Add(primeImplicantChart.Keys[i])

    return essentialPrimeImplicants

CreatePrimeImplicantChart では、表を行ごとの文字列で表した。
しかし今回のステップでは、表を縦に読む必要がある。どうしてこうなった？

mintermCoverages ← list with all of the values in the dictionary

自然言語で誤魔化して、しかも言葉足らずだが、表を transpose するという意味だろうか。
そしてこの変数は、これ以降登場しない。末尾の s のないものは出てくるけど。

代わりに ticks[] が出てくる。きっとこれが、minterms の背番号ごとに表を縦に読んで、1 だけ抜き出して0 は飛ばしたものなのだろう。
結果が "1" なら、それを return する必須項リストに投入しているから。

そしてここで終わる。必須項では足らない部分を補うところが、コストを最小化する肝心なところだと思うのだが。

オリジナる

必須項云々は、答えに確実に選ばれるものを確定することで問題を小さくするヒューリスティックで、その後のアルゴリズムが正しく動作するなら、それをする必要は実はない。最悪計算量は変わらない。
そして、ヒューリスティックを投入して近似値で満足するのでなく、真の答えを求めるならば、総当たりをするしかない。

ということで、ステップ2以降は捨てて、総当たりで最適解を求めることを考える。

まだカバーされていない最小項（初期値全て）のリストと、
まだ使うことを選択していない主項のリストを持ち、
累積変数として、ここまでで選択した主項のリスト（使っていないリストの補集合になる）を持って再帰する。
最小項が空なら成功なので、ここまでで選択した主項のリストコストを一つの結果として返す。

まだ何か最小項があるなら、任意に一つ選ぶ。実装ではリストの先頭からとればいいだろう。

次に、まだ選んでいない主項の中で、この最小項をカバーするもの全てについて、以下を同様に行う。

残っている最小項のうち、主項がカバーするものを（今選んだものも含めて）全て削除する。
選んだ主項を選択済みにし、選んだ主項リストの方に入れる。
そして再帰呼び出しで探索を続行する。

全ての主項の選択について再帰呼び出しから戻ってきたら、それらの結果を統合し、ベストスコアのものだけを上に返す。

getMinimized :: [Term] -> [Term] -> [(Int,[Term])]
getMinimized minterms1 primeImplicants = recur minterms1 primeImplicants []
  where
    recur [] _ used = [(costOf used, used)]
    recur (mt:minterms) unused used = filter ((mincost ==) . fst) results
      where
        results =
          [ res
          | prim <- unused, covers prim mt
          , let minterms1 = filter (not . matches prim) minterms
          , let unused1 = delete prim unused
          , res <- recur minterms1 unused1 (prim:used)
          ]
        mincost = minimum $ map fst results

    costOf terms = sum (map (length . filter ('-' /=)) terms)

--  matches は上で作ったもの

選んだ主項リストに関するコストは、主項のその中の - でない文字の個数としてみた。
主項の表す論理式が $AB + C\overline{D}$ のようになっているとき、
一つの主項 $C\overline{D}$ の文字数は -でないものを除いて数えることで得られ、それは AND ゲートの個数＋１になる。
また、主項の個数が $+$ つまり OR ゲートの個数＋１になる。
結局、文字数の方だけ足せば、総ゲート数＋１になる、というのが理由である。

あとは全体を駆動する部分を書けば完成。

minimizeBinaryFunction :: [Term] -> [Term] -> [(Int,[Term])]
minimizeBinaryFunction minterms dontcares =
    getMinimized minterms prim
  where
    prim = getPrimeImplicants $ minterms ++ dontcares

pediaの例で実行してみる。

example1 = minimizeBinaryFunction mt dc
  where
    mt = ["0100","1000","1010","1011","1100","1111"]
    dc = ["1001","1110"]

> example1
[(7,["1-1-","1--0","-100"]),(7,["1-1-","10--","-100"])]

前者が $AC + A\overline{D} + B\overline{CD}$ 後者が $AC + A\overline{B} + B\overline{CD}$ を表している。
正解。

雑感

後半の「主項のカバー表を作る」「必須項をまとめる」は無駄と切り捨てたので、これは教科書的には「クワイン・マクラスキー法」とは呼べないものになってしまった気がする。
なので Rosetta Code に投稿してよいかも怪しい。

アルゴリズムを説明するための擬似コードに極力寄せることを意図したので、実用を考えるならそうはしない、という点が色々あるだろう。

例えば、深さ優先探索で総当たりする際に、全ての再帰が終わってから、ベストスコアを選出している。
一つ降りて戻ってくるたびにそれを計算し、現在のベストスコアを再帰呼び出しで知らせ、再帰の途中でもコストオーバーが確定したら探索を打ち切る、という枝刈りを入れることで実践的な効率の向上が期待できる。
しかしそのロジックを入れると「ややこしい実装」になってしまうし、Haskellではそういう計算は書きにくい（自分が下手なだけかも）ので入れなかった。
一つの最小項に対して可能な再帰呼び出しの主項を選ぶとき、代表する最小項が多いものほど再帰を早く終了させ、スコアも期待できるので、枝刈りをするならそちらを優先すべきである。
そのときは getPrimeImplicants の結果を後ろから使うというか、結果を作っている (++) の前後を入れ替えると、リストの前方ほど優先度の高いものになる。

以上、なかなかハードな回でした。