カルノー図による簡単化

質問

カルノー図を用いて論理関数の簡単化を行うプログラムを作っているのですが、
変数の入力からカルノー図の表示まで出来たものの、最簡形を求めるところで行き詰まってしまいました。
以下今時点での実行結果です。

（変数：小文字は偽、大文字は真を表しています）
abd
AbCd
AD
ABD

（カルノー図：'_'は空白を表しています）

1___
__11
__11
1__1

いまカルノー図はchar型で宣言しています。

最簡形を求めるには、カルノー図の2^i(i=0,1,2…）個の'1'を長方形または正方形になるようにループで囲んでいき、すべての１を囲むまでこれを行う。
（ループは重なっても構わない。また一番上と下の項はつながっており、一番右と左の項はつながっている）
そして各ループを積項表現をすると主項が得られる。
最後に全主項をORで結ぶことにより、最簡形が得られる。

もしアドバイス等いただける方、回答できる方、いらっしゃいましたら、是非書き込みお願いします。

回答No.2

minimum · ベストアンサー

>この複数の最小項の値に0が含まれておらず、1が1つ以上含まれているとこの項が主項になります。

この部分は実際のカルノー図では四角で括る部分を選んでいます。
括った中に偽が含まれていては困りますよね。
また、禁止項のみを括っても意味が無いので最低1個は真が含まれていないといけません。

>また完全に他の要素とかぶる項を避けるため、一度、主項に含まれた値が1の最小項の値はXに変えましょう

これは例えば、
ABCという主項で括った後に
ABCDとABCdを括る必要はありませんよね。
なのでABCで括ったときに対応する真のところを禁止項にするのです。すると、上記の「最低1個は1が…」によって
ABCDとABCdは括られることがありません。

また最初にABCDとABCdを括ってしまって、ABCが括られない。という事態を避けるために、
「主項候補中にXが多いものから主項としていきましょう。 」ということです。

お礼

遅くなりました。なんとか完成し提出することができました。
ありがとうございました。

回答No.1

minimum

とりあえず思いつく方法を

まず、各項の状態は、真、偽、そして真偽どちらでも良い禁止項の3状態が必要になってきます。

説明のため
　真
　偽
　禁止項
を
　1
　0
　X
と、
　AbCd
　AD
なんかは
　1010
　1XX1
としておきましょう。

さて、手書きでは2^i個の長方形で括る所は、プログラム的には、主項となりえるパターンぞれぞれで、当てはまる最小項を選び出しましょう。探すべきでしょう。
具体的には
1XX0という主項候補ならば
1000
1010
1100
1110という最小項が対象になります。

この複数の最小項の値に0が含まれておらず、1が1つ以上含まれているとこの項が主項になります。

また完全に他の要素とかぶる項を避けるため、一度、主項に含まれた値が1の最小項の値はXに変えましょう。

また、大きな項から括るために、主項候補中にXが多いものから主項としていきましょう。

我ながら下手な説明だな…

補足

早速の書き込みありがとうございます。
最小項を求めるところまでは理解できたのですが、

この複数の最小項の値に0が含まれておらず、1が1つ以上含まれているとこの項が主項になります。

また完全に他の要素とかぶる項を避けるため、一度、主項に含まれた値が1の最小項の値はXに変えましょう。

この部分がいまいち理解できません。
もう少し詳しく説明していただければ幸いですm(_ _)m