真理値表の情報から簡略化(クワイン－マクラスキー法+α)

これはなに

4変数の真理値表からできるだけ簡単化した式を出力するプログラムを作りました．

発端は学校で課せられた実験レポートを書く際面倒な作業が多かったため自動化したいと思ったからです．
https://shibaken28.github.io/KarnaughMap/

簡略化の表示に成功！！！https://t.co/EYLrRtRp6V pic.twitter.com/c0zaA257m6

— しばけん💧 (@Shibaken_8128) 2021年11月19日

また，この記事は長野高専 Advent Calendar 2021の4日目の記事です．
qiita.com
3日目と5日目の記事はこちら
3日目↓
qiita.com

5日目↓
https://qiita.com/advent-calendar/2021/nnct
5日目は誰も入っていませんでしたorz

実装

JavaScriptで実装します．

準備

真理値表と配列

$bitState$という名前の配列に真理値表での出力値を格納しています．
入力の変数の数が$N$個のとき，$N$個の入力それぞれについて$0$か$1$の2通りあるので，配列$bitState$の大きさは$2^N$になります．
下の表のように入力$p$を横に並べて2進数と見た数字に出力を格納することにします．

例えば，次のような入力が2つの真理値表があったとすると，

$p_1$	$p_0$	出力$Z$	対応する添え字
$0$	$0$	$1$	$00_{(2)}=0_{(10)}$
$0$	$1$	$1$	$01_{(2)}=1_{(10)}$
$1$	$0$	$0$	$10_{(2)}=2_{(10)}$
$1$	$1$	$1$	$11_{(2)}=3_{(10)}$

$bitState$配列の中身は$bitState=\{1,1,0,1\}$になります．

厳密に表現すると，入力の変数を$p_0,p_1,p_2,...,p_{N-1}$とおくと，添字が$\displaystyle \sum_{\substack{i}} 2^{i} p_i$のところに出力を格納します．

ビット列

前節のように添字は$10$進数の整数として扱っているので，入力の組み合わせを得るには$2$進数に変換をする必要があるます．
$2$で割ったあまりを出して2で割る，を繰り返して2進数に変換する方法がありますが，ここでは任意の桁(bit)の情報を得られるbit演算を使います．
$i$桁目(右から0-indexed)は$2^i$の位を表していますので，$AND$演算によりそのbitが立っているかがわかります．

N & 1<<i //Nのi桁目が立っているか

これにより，for文を回せば次のような関数が作れます．

function toBin(n,k){//10進数整数nをk桁0埋め2進数表示へ
  s=""
  for(var i=0;i<k;i++){
    s=(1<<i&n?"1":"0")+s;  
  }
  return s;
}

クワイン－マクラスキー法(QM法)

QM法(の一部)によって，主項を求めます．カルノー図では長方形で$1$を囲むことで簡略化しますが，この長方形にあたるのが主項です．ただし，カルノー図で囲む長方形は，その長方形自身を完全に含む別の長方形がないことが条件です．私はWikipediaを見ながら実装しました．

次のような真理値表で説明します．

$p_2$	$p_1$	$p_0$	出力
$0$	$0$	$0$	$1$
$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$1$
$1$	$0$	$1$	$1$
$1$	$1$	$0$	$0$
$1$	$1$	$1$	$1$

まず，出力が$1$である入力のbit列を書き出します．この場合，$\{000,001,010,011,100,101,111\}$の$7$つです．これらを項と呼ぶことにし，今からこの項たちをまとめていきます．
これらの項のうち，ある$1$ビットのみ異なっている$2$つの項の組み合わせを見つけます．
例えば$010$と$000$は$1$ビット目のみが異なっているので$0\_0$としてまとめられます(記号$\_$は$0$か$1$を表します)．
ここで，全ての組み合わせに関して比較しても良いですが，立っているビット数の数によってグループ分けをし，
$i$個ビットが立っているグループの要素と$i+1$個ビットが立っているグループの要素同士のみを比較しても問題はありません．
なぜなら，まとめられるbit列はどれも立っているビットの数が必ず$1$つ違うからです．これにより少し高速化が可能です．

グループ分けすると次のようになります．

$0$個	$000$
$1$個	$001,010,100$
$2$個	$011,101$
$3$個	$111$

これで必要な比較回数が${}_7 \mathrm{C}_2 =42$回から$1\cdot 3+3\cdot 2+2\cdot 1=11$回に減りました．
各要素を比較し，$00\_,0\_0,\_00,0\_1,\_01,01\_,10\_,\_11,1\_1$の9項が得られます．
今回は出ませんでしたが，ペアが一つも見つからない項は，これ以上まとめられないという意味なので主項として取っておきます．

そして，再び立っているビット数でグループ分けをし，

$0$個	$00\_,0\_0,\_00$
$1$個	$0\_1,\_01,01\_,10\_$
$2$個	$\_11,1\_1$

同様に，$i$個ビットが立っているグループの要素と$i+1$個ビットが立っているグループの要素同士を比較します．
これらをまとめると，$0\_\_ , \_0\_ , \_\_1 $(このとき$\_$は一つの文字として認識します．)になります．

これを繰り返し，

$0$個	$0\_\_ , \_0\_$
$1$個	$\_\_1$

ここでどの項もペアが見つからなかったので全て主項になります．
このグループ分け→ペア探しの作業は高々(変数の数+1)回で終わります．なぜなら，1回の作業につき，ビット列の$1$が$\_$がに変化して立っているbitの数が一つ減るからです．

擬似コードを示します．ここで使われている集合は重複が許されません(集合$\{1,2,3,4\}$に，既に要素である$4$が追加されても集合は$\{1,2,3,4\}$のままです)．

// 入力の変数の数はn
// S[i]:=i個ビットが立っているビット列のリスト，T[i]も同様
// M:=主項の集合
// used:=ペアが見つかった項の集合

for t = 0~n
    usedを空にする
    Tを空にする
    for i = 0~n-1
        for j = 0~(S[i]の長さ-1)
            for k = 0~(S[i+1]の長さ-1)
                if S[i][j]とS[i+1][k]で1ビットだけ異なる
                    T[i] に S[i][j]とS[i+1][k]の異なる部分を"_"に変えたものを追加
                    used に S[i][j]とS[i+1][k]を追加
            if used に S[i][j]が含まれない
                M に S[i][j]を追加
    S に T をコピー

次に実際のコードを示します．
少し違いがあり，

• 擬似コードでは$S,T$と2つ配列を用意していますが，実際のコードは一つの配列を使いまわしている
• 擬似コードではペアが見つかったかどうかを$used$のみで判断しているが，実際のコードはペアが見つかったかの別のフラグfindを用意している

などの点があります．

擬似コードの方がコンパクトです(擬似コードを後に書いたので)．

function simplification(){
  var bitNum = new Array(vars+1);//bitNum[i]:=ビットがi個立ってる数の配列
  var uniquBits = new Set();//主項の集合
  //countBits
  var i,j,k,l;
  for(i=0;i<=vars;i++){
    bitNum[i]=new Array(0);
  }
  for(i=0;i<bitState.length;i++){
    if(bitState[i]==1)bitNum[countBits(i,vars)].push(toBin(i,vars));//ビットの数を数えてその場所に入力を表す2進数をpushする．
  }
  for(var t=0;t<=vars;t++){//高々(変数の数+1)回繰り返せばよい．
    var used = new Set();
    for(i=0;i<bitNum.length;i++){
      var len=bitNum[i].length;
      var csd=i+1;
      for(j=0;j<len;j++){
        var find=false;
        if(i==bitNum.length-1){
          if(!used.has(bitNum[i][0]))uniquBits.add(bitNum[i][0]);
          bitNum[i].shift();
          continue;
        }
        for(k=0;k<bitNum[csd].length;k++){
          //i,0とi+1,xを比較
          var a=bitNum[i][0];
          var b=bitNum[csd][k];
          var dif=0;//違いの数
          var out="";
          for(l=0;l<min(a.length,b.length);l++){
            if(a.charAt(l)!=b.charAt(l)){
              dif++;
              out+="\\d{1}"; //正規表現．0と1どちらでも良い
            }else{
              out+=a.charAt(l);
            }
          }
          if(dif==1){
            find=true;
            used.add(b);
            bitNum[i].push(out);//ビットがi個立っている，再び配列にpushする
          }
        }
        if(!find&&!used.has(bitNum[i][0])){
          uniquBits.add(bitNum[i][0]);
        }
        bitNum[i].shift();//配列の先頭を削除
      }
    }
  }

bit全探索で候補を列挙

Wikipediaには主項が求まった後には必須項を求める，とありますがその方法が試行錯誤またはぺトリック法と書いてあります．
が，ペトリック法を実装するのが面倒なので，全探索で殴りました．
前節の手順で$N$個の主項が求まっていれば，これらの項の組み合わせは$2^N$通りあります．これらを全列挙して，真理値表を満たしているかを確認すれば良いです．
$2^N$通りの全探索はbit全探索でできます．

任意の一文字記号$\_$を正規表現にしておくとちょっと楽ができます．

//(前のコードの続き)
  uniquArr = [...uniquBits];
  
  result = new Array(0);
  var num = uniquArr.length;
  for(i=0;i<(1<<num);i++){
    var ok=true;
    for(j=0;j<bitState.length;j++){
      if(bitState[j]==0)continue;//そもそも関係ない
      var match=false;
      for(k=0;k<num;k++){
        if(i&(1<<k)){
          var re = new RegExp(uniquArr[k]);
          if(toBin(j,vars).match(re)!=null){
            match=true;
          }
        }
      }
      if(!match)ok=false;
    }
    if(ok){
      result.push([]);
      for(k=0;k<num;k++){
        if(i&(1<<k)){
          result[result.length-1].push(uniquArr[k].replace(/\\d\{1\}/g, '*'));
        }
      }
    }
  }
}

こうして，簡略化を表す$result$配列に文字列が出力されます．

遊んでみた

4変数の場合はhttps://shibaken28.github.io/KarnaughMap/で遊ぶことができますし，実際4変数ならカルノー図書けば人力でも全然いけます．
せっかくなのでクワインーマクラスキー法の本領発揮ができる5変数以上でやってみます．
5変数になるとカルノー図が3次元に拡張しないと書くことができず人力だとなかなか苦労するでしょう．

まずは6変数で試してみました．真理値表は$2^6=64$行もあるので一部省略します．

これの出力が

これです．良さそうですね．

8変数にしてみました


良さそうです．

10変数...入力は$2^{10}=1024$通りです．表示がカクカクになったのでp5jsのフレームレートを落としました．


合っているかどうかすぐにはわかりませんが，たぶん合っているでしょう．

速度の問題で，一番のボトルネックは明らかに最後のbit全探索$\mathrm{O}(2^N)$ですね．
ここで必須項をペトリック法で事前に求めて，必須項以外の項のみをbit全探索をすることで高速化ができそうです．

が，そもそも10変数に関する簡単化を実際に必要とする機会があるのかはわからないです．

あとがき

bit演算様様です．GithubPagesも便利です．p5jsも便利です．

p5jsのすすめ

JSもHTMLもよくわからないけどwebブラウザで動くヤツ作りたい！Processingなら書ける！という人(僕です)におすすめなのが，p5jsです．
p5jsは，ブラウザで動くProcessingです．言語はJavaライクなものからJSに変わりますが，変数宣言とfunctionとArrayが使えればほとんど変わりません．setup()とかfill()みたいな関数は全く同じです．便利なオンラインエディタもあります．
editor.p5js.org

index.htmlというファイル名に次のコードを突っ込んで，

<!DOCTYPE html>
<html lang="en">
  <head>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.3.1/p5.js"></script>
    <link rel="stylesheet" type="text/css" href="style.css">
    <meta charset="utf-8" />
  </head>
  <body>
    <script src="./script.js"></script>
  </body>
</html>

同じ場所にstyle.cssというファイルも用意しておきます．中身は書かなくて大丈夫です(後から書き足すとき用)．
また，同じ場所にscript.jsというファイルも用意して，そこにp5jsのコードを書いて，index.htmlをChromeとかで開くと動きます．
githubにアップして，Settings/GitHub PagesのCheck it out hereを押してSourceのbranchをmainとかに設定すれば，ユーザー名.github.io/なんちゃらで公開されます．