2.2 卡諾圖與化簡#

from itertools import product

# Gray 碼順序：相鄰位元只差一個
gray = [0, 1, 3, 2]   # 對應 00,01,11,10

def kmap_cells(minterms, care=True):
    """建立 4 變數卡諾圖：cell -> 1/0"""
    cells = {}
    for a, b, c, d in product([0,1], repeat=4):
        code = (a<<3) | (b<<2) | (c<<1) | d
        cells[(a,b,c,d)] = code in minterms
    return cells

def adjacent_groups(cells, minterms, size):
    """枚舉所有 2^k（k=給定 size 的位元數）個相鄰格構成的組；此處
       利用技巧：一個組 = 固定某些變數不變、其餘變數自由枚舉， 
       且組內全為 1 才合法。"""
    groups = []
    # 選擇固定不變的變數位置，其餘枚舉（組大小 = 2^自由數）
    for frees in [(0,), (1,), (2,), (3,),          # 8格組
                  (0,1), (0,2), (0,3), (1,2), (1,3), (2,3),  # 4格組
                  (0,1,2), (0,1,3), (0,2,3), (1,2,3)]:       # 2格組
        fixed_vals = [b for i, b in enumerate(product([0,1], repeat=4 - len(frees))[0])
                      if i not in []]  # 佔位，實際用下面方式
        _ = fixed_vals
        for fixed_value in product([0,1], repeat=4 - len(frees)):
            members = []
            for a,b,c,d in product([0,1], repeat=4):
                v = (a,b,c,d)
                fv = 0
                ok = True
                idx = 0
                for i in range(4):
                    if i not in frees:
                        if v[i] != fixed_value[idx]:
                            ok = False; break
                        idx += 1
                if ok:
                    members.append(v)
            if all(cells[m] for m in members):
                groups.append(frozenset(members))
    # 去除相同成員的組
    return set(groups)

def cover(minterms):
    """卡諾圖圈選：由大到小選組 + 吸收"""
    cells = {k: k in minterms for k in product([0,1], repeat=4)}
    groups6, groups4, groups2 = [], [], []
    for frees_size, bucket in ((3, groups6), (2, groups4)):
        pass
    # 重新以「自由變數數」分組
    def groups_with(free_count):
        res = set()
        for frees in product(range(4), repeat=free_count):
            if len(set(frees)) != free_count: continue
            fixed = [i for i in range(4) if i not in frees]
            for fv in product([0,1], repeat=len(fixed)):
                members = [v for v in product([0,1], repeat=4)
                           if all(v[fixed[i]] == fv[i] for i in range(len(fixed)))]
                if all(cells[m] for m in members):
                    lits = frozenset((fixed[i], fv[i]) for i in range(len(fixed)))
                    res.add(frozenset(members))
        return res
    G2, G3, G4 = groups_with(2), groups_with(3), groups_with(4)
    chosen, covered = [], set()
    for pool in (G4, G3, G2):          # 先用大組
        for g in sorted(pool):
            if not set(g) <= covered:
                covered |= set(g)
                chosen.append(g)
    return chosen

def term_of(group):
    """由組成員回推積項"""
    vals = [list(v) for v in group]
    lits = []
    for i in range(4):
        col = {v[i] for v in vals}
        if len(col) == 1:
            lits.append("abcd"[i] if col.pop() else "¬" + "abcd"[i])
    return "·".join(lits) if lits else "1"

minterms = {(1,0,1,0), (1,0,1,1), (1,1,1,0), (1,1,1,1)}   # ab 不變 = ab·c? 
print("真值為1的組合:", sorted(minterms))
for g in sorted(cover(minterms)):
    print("圈選積項:", term_of(g))

真值為1的組合: [(1,0,1,0), (1,0,1,1), (1,1,1,0), (1,1,1,1)]
圈選積項: a·c