20260507_4

20260430_4

---

主項≠必須項(絶対に含めないといけない項)

よって、主項を単純に囲めばいいというわけではない

必須項: 最小項がただ一つの主項に含まれる場合、その主項に着目すると見つけられる

主項よりも必須項を書き出していく操作になる

最小の論理式が複数パターンある場合もある

graph TD
A[まだ包含されていないXを選択]
B[選択したXについて隣接するすべての1とXを探す]
C{単一の項が選択した最小項と隣接するすべての1とXを包含するか？}
D[その項を必須項として選んでループで囲む]
E{包含されていない1を全て調べたか？}
F[カルノー図上に残る1を包含する最小の主項の集合を見つける]

A-->B
B-->C
C--YES-->D
C--NO-->E
D-->E
E--YES-->F
E--NO-->A

5変数カルノー図

• 一つのマスを二つに分けて3次元的にとらえる
• 3変数をグレー順に並べて場合分けする

論理式が同じこと

二つの論理式が等しいことを確かめるには

• 真理値表を用意する
• 最小項展開
• 最大項展開
• 共通項の発見
• カルノー図を用意する←New!!

カルノー図の利用

• 式が同じであることの確認
• 冗長なコンセンサス項の発見/追加

ベイチ図(ラベルを付けて値を表現、5変数カルノー図を見やすくするのに利用できる)

ベイチ図では左右が対象になるように置く

---

より大きな論理式も簡単化したい

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

---

カルノー図では閉包の定理をひたすら適用していく
→これをアルゴリズムにする

主項表を用意する

$f(a,b,c,d)=\Sigma m(0,1,2,5,6,7,8,9,10,14)$

$$\{\begin{array}{ll}0& 0000\end{array}\{\begin{array}{ll}1& 0001\\ 2& 0010\\ 8& 1000\end{array}\{\begin{array}{ll}5& 0101\\ 6& 0110\\ 9& 1001\\ 10& 1010\end{array}\{\begin{array}{ll}7& 0111\\ 14& 1110\end{array}$$

一変数だけ違うものを閉方する

→1の個数でグループ分けすると、隣のグループとの確認だけで済む

総当たりする！！

閉方したものは$0000$と$0001$を$000-$のように書いて再度総当たり

閉方できなくなるまで繰り返していく(内項の削除)

最終的に主項が求まる

主項表

	0	1	2	5	6	7	8	9	10	14
b’c’	x	x					x	x
b’d’	x	x					x		x
cd’			x		x				x	x
a’c’d		x		x
a’b’d				x		x
a’bc					x	x

この場合、9と14を含むものは必須項
横方向は最小項を消し、消えている最小項の部分は気にしなくてよくなる
これを繰り返す

不完全定義関数のクワイン・クラマスキー法

趣向を求める分ではこの方法ではドントケア項も必要な最小項として扱う
主項表ではドントケア項を書かない

マップ挿入変数

6変数のカルノー図は書きにくい

	00	01	11	00
00	1
01	X	E	X	F
11	1	E	1	1
10	1			X

EとFについて場合分けをしてそれぞれで主項を求める
→積和形で整理する