2.1 布林代數與真值表#

from itertools import product

def truth_table(nvars, func):
    rows = []
    for bits in product([0, 1], repeat=nvars):
        rows.append(bits + (int(func(*bits)),))
    return rows

def sop_from_truth_table(nvars, func):
    names = [chr(ord('a') + i) for i in range(nvars)]
    terms = []
    for bits in product([0, 1], repeat=nvars):
        if func(*bits):
            terms.append(tuple(v if b else "¬" + v
                               for v, b in zip(names, bits)))
    return terms

def shrink(term):
    """把 '¬a' 正規化為 ('a', 0)，方便比較"""
    return frozenset((l.lstrip("¬"), 0 if l.startswith("¬") else 1)
                     for l in term)

def simplify(nvars, minterms):
    """合併律 + 吸收律的兩層 SOP 化簡"""
    cubes = [shrink(t) for t in minterms]
    # 步驟1：合併——兩個積項只在同一變數上取值相反且其餘相同
    changed = True
    while changed:
        changed = False
        new, used = set(), [False] * len(cubes)
        for i, c1 in enumerate(cubes):
            for j, c2 in enumerate(cubes):
                if i < j and len(c1 ^ c2) == 1 and len(c1) == len(c2):
                    used[i] = used[j] = True
        # 將差一個「相反字面值」的對合併：直接丟掉那兩個對立方
        merged_map = {}
        for i, c1 in enumerate(cubes):
            for j, c2 in enumerate(cubes):
                if i < j and len(c1) == len(c2):
                    diffs = [(v, a, b) for (v, a) in c1
                             for (v2, b) in c2 if v == v2 and a != b]
                    if len(diffs) == 1 and c1 - {diffs[0][:2]} == c2 - {(diffs[0][0], diffs[0][2])}:
                        m = c1 - {diffs[0][:2], (diffs[0][0], diffs[0][2])}
                        new.add(frozenset(m))
                        used[i] = used[j] = True
        for i, u in enumerate(used):
            if not u:
                new.add(cubes[i])
        if new != set(cubes):
            changed = True
        cubes = list(new)
    # 步驟2：吸收——若 A ⊇ B（A 的約束更少）則 A 是多餘的
    final = [c for c in cubes if not any(
        c != d and {v for v, _ in d} - {v for v, _ in c} == set()
        and len(d) < len(c) for d in cubes)]
    return final

def pretty_term(c):
    return "·".join(lit + v for v, lit in sorted(c))

data = [("f(a,b) = ab + ab'（可合併為 a）", 2, lambda a, b: a and (b or not b)),
        ("g(a,b,c) = ab + bc", 3, lambda a, b, c: (a and b) or (b and c))]

for name, n, f in data:
    print("==", name)
    print("真值表:")
    for row in truth_table(n, f):
        print("  ", row)
    mints = sop_from_truth_table(n, f)
    print("標準SOP:", " + ".join("·".join(t) for t in mints))
    print("化簡後:", " + ".join(sorted(pretty_term(c) for c in simplify(n, mints))),
          "\n")

== f(a,b) = ab + ab'（可合併為 a）
真值表:
   (0, 0, 0)
   (0, 1, 0)
   (1, 0, 1)
   (1, 1, 1)
標準SOP: a·b + a·¬b
化簡後: a