求最小化布尔函数 EN 的算法

     X   Y   Z   F
0    0   0   0   0
1    0   0   1   0
2    0   1   0   0
3    0   1   1   1
4    1   0   0   1
5    1   0   1   1
6    1   1   0   0
7    1   1   1   1

# An implicant consists of two parts in a tuple:
#   - A string consisting of 0, 1, and dash
#   - A set of numbers representing the minterms

# Construct an implicant from its index in the truth table.
# [var_cnt] number of variables in the truth table.
# [index] its index in the truth table.
def implicant_from_index(var_cnt, index):
    return (
        bin(index)[2:].rjust(var_cnt, "0"),
        frozenset({index}),
    )


# Combines two implicants.
# Returns the combined implicant, or False if they cannot be combined.
# For example, combining "10-1" and "10-0" gives us "10--".
def combine(implicant_a, implicant_b):
    str_a, nums_a = implicant_a
    str_b, nums_b = implicant_b

    def combine_str(str_a, str_b):
        assert len(str_a) == len(str_b)
        assert str_a != str_b

        if len(str_a) == 0 and len(str_b) == 0:
            return ""

        head_a, *rest_a = str_a
        head_b, *rest_b = str_b

        if head_a == head_b:
            combined = combine_str(rest_a, rest_b)
            if combined:
                return head_a + combined
            else:
                return False

        elif {head_a, head_b} == {"0", "1"} and rest_a == rest_b:
            return "-" + "".join(rest_a)

        else:
            return False

    combined_str = combine_str(str_a, str_b)
    if combined_str:
        return combined_str, nums_a.union(nums_b)
    else:
        return False


# Find a set of prime implicants from DNF(disjunctive normal form).
# [var_cnt] the number of variables.
# [minterms] a list of intergers representing the boolean function in DNF.
def find_prime_implicants(var_cnt, minterms):
    def iter(implicants):
        if len(implicants) == 0:
            return set()

        unused_implicants = implicants.copy()
        resulting_implicants = set()
        for term_a in implicants:
            for term_b in implicants:
                if term_a != term_b:
                    combined = combine(term_a, term_b)
                    if combined:
                        unused_implicants.discard(term_a)
                        unused_implicants.discard(term_b)
                        resulting_implicants.add(combined)
        return unused_implicants.union(iter(resulting_implicants))

    return iter({implicant_from_index(var_cnt, minterm) for minterm in minterms})


# Union in function form.
# It also converts normal set to frozensets.
# [sets] an iterable of sets to be unioned.
def union(*sets):
    return frozenset().union(frozenset(s) if isinstance(s, set) else s for s in sets)


# Select a minimum set of sets that cover their union.
# This is a NP-complete problem.
# Instead of implementing a proper algorithm that runs in exponential time, we just try some greedy method and give up if a solution cannot be found.
# [sets] an iterable of sets to be covered.
# [ignore_values] a set of values that should be excluded from the union. This argument is just for easy implementation.
def minimum_cover(sets, ignore_values=frozenset()):
    # Remove "empty" sets.
    sets = frozenset(
        s for s in sets if len([x for x in s if x not in ignore_values]) > 0
    )

    if len(sets) == 0:
        return frozenset()

    # Remove sets that are completely covered("shadowed") by another set.
    sets = frozenset(s for s in sets if not any(s < t for t in sets))

    # Try find a value that is only covered by one set.
    for v in union(*sets) - ignore_values:
        for s in sets:
            if v not in union(t - s for t in sets):
                # Gotcha
                return minimum_cover(
                    sets - frozenset({s}), ignore_values=ignore_values.union(s)
                ).union({s})

    # Worst case: non of the values are only covered by one set.
    # We give up.
    raise Exception()


# Run the argorithm and print the result.
# [vars] variable names of the boolean function.
# [minterms] a list of intergers representing the boolean function in DNF(disjunctive normal form)
def qm_algorithm(vars, minterms):
    prime_implicants = find_prime_implicants(len(vars), minterms)
    sets = frozenset(implicant[1] for implicant in prime_implicants)
    cover = minimum_cover(sets)

    strs = [implicant[0] for implicant in prime_implicants if implicant[1] in cover]
    terms = [
        "".join(
            {"0": vars[i] + "'", "1": vars[i], "-": "",}[char]
            for i, char in enumerate(str)
        )
        for str in strs
    ]
    print("sigma(", end="")
    print(*minterms, sep=", ", end="")
    print(") => ", end="")
    print(*terms, sep=" + ")

qm_algorithm("XYZ", [3, 4, 5, 7])  # YZ + XY'
qm_algorithm("XYZ", [1, 3, 5, 6, 7])  # XY + Z
qm_algorithm("ABCD", [0, 2, 4, 8, 10, 11, 15])  # ACD + B'D' + A'C'D'
qm_algorithm("WXYZ", [0, 1, 3, 5, 14, 15])  # W'X'Y' + W'Y'Z + W'X'Z + WXY