与えられた論理関数 $G(A, B, C, D) = \sum m(0, 1, 4, 5, 10, 11, 14, 15)$ に対して、クワイン・マクラスキー法を用いて最小積和形を求める。手順は、1の数で最小項を分類、ハミング距離が1のペアを作る、グループ化を繰り返す、主項をリストアップ、主項被覆表を作成し必須主項を特定する、という流れで行う。
2025/5/19
1. 問題の内容
与えられた論理関数 に対して、クワイン・マクラスキー法を用いて最小積和形を求める。手順は、1の数で最小項を分類、ハミング距離が1のペアを作る、グループ化を繰り返す、主項をリストアップ、主項被覆表を作成し必須主項を特定する、という流れで行う。
2. 解き方の手順
ステップ1: 1の数で最小項を分類する表を作成
- 0: 0 (0000)
- 1: 1 (0001), 4 (0100), 10 (1010)
- 2: 5 (0101), 11 (1011), 14 (1110)
- 3: 15 (1111)
ステップ2: ハミング距離が1のペアを作り、グループ化する。チェックされなかった最小項を記録する。
- (0, 1): (000-) チェック済み: 0, 1
- (0, 4): (0-00) チェック済み: 0, 4
- (1, 5): (0-01) チェック済み: 1, 5
- (4, 5): (010-) チェック済み: 4, 5
- (10, 11): (101-) チェック済み: 10, 11
- (10, 14): (1-10) チェック済み: 10, 14
- (5, 15): (-101) チェック済み: 5, 15
- (11, 15): (1-11) チェック済み: 11, 15
- (14, 15): (111-) チェック済み: 14, 15
ステップ3 & 4: ハミング距離が1のペアをさらにグループ化する。
- (0, 1, 4, 5): (0--0) と (0-0-) (010-) を組み合わせることは出来ない
- (10, 11, 14, 15): (1--1)と(1-10) (1-11) を組み合わせることは出来ない
- (4, 5, 14, 15): グループ化不可能
ハミング距離が1のペアをグループ化
- (0, 1, 4, 5): (--00)と(0--0)を組み合わせることは出来ない。グループ化不可
- (10, 11, 14, 15) : (1-1-)
ステップ5: 全ての主項をリストアップする。
- (0, 1): (000-) = A'B'C'
- (0, 4): (0-00) = A'C'D'
- (1, 5): (0-01) = A'C'D
- (4, 5): (010-) = A'BC'
- (10, 11): (101-) = AB'C
- (10, 14): (1-10) = AC'D'
- (5, 15): (-101) = BCD
- (11, 15): (1-11) = ACD
- (14, 15): (111-) = ABC
- (10,11,14,15): (1--1)はAC
- (4,5,14,15):グループ化できない
ステップ6: 主項被覆表を作成し、必須主項を特定する。
| | 0 | 1 | 4 | 5 | 10 | 11 | 14 | 15 |
|--------|---|---|---|---|----|----|----|----|
| A'B'C' | o | o | | | | | | |
| A'C'D' | o | | o | | | | | |
| A'C'D | | o | | o | | | | |
| A'BC' | | | o | o | | | | |
| AB'C | | | | | o | o | | |
| AC'D' | | | | | o | | o | |
| BCD | | | | o | | | | o |
| ACD | | | | | | o | | o |
| ABC | | | | | | | o | o |
| AC | | | | | o | o | o | o |
必須主項は存在しない。
最小積和形を求めるために、Petrick法や他の簡略化手法を用いる必要がある。
3. 最終的な答え
クワイン・マクラスキー法だけでは最小積和形は一意に決定できない。
最小積和形を求めるには、主項被覆表を用いた更なる簡略化（例えばPetrick法）が必要である。
ここでは、カルノー図を用いることで、以下の最小積和形を得ることができる。
あるいは