求布尔函数最小化的算法

Question

这是我关于数字逻辑设计的作业的一部分，所以我想先介绍一些技术背景。

算法是一种最小化布尔函数的方法。给定布尔函数的真值表，它试图找到表示该函数的最简单的乘积和。

例如，布尔函数F_{xyz}=xy' + yz 有以下真值表：

     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

从真值表中，我们可以编写布尔函数的析取范式，它是F = 1所在的所有行的乘积之和。

F_{xyz}= x'yz + xy'z' + xy'z + xyz

通常，DNF是通过简单列出术语的索引来表示的。例如，前面的函数可以表示为\sum m(3,4,5,7) 。

Quine算法从DNF开始，以简化的形式F_{xyz}=xy' + yz 结束.

更多的行话：

• minterm是每一个变量出现一次的产品，如xy'z。
• 隐含词是一种不一定是腹地的产品，就像xy'一样。Implicants可以通过组合腹板或其他含意物(例如xy'z + xy'z')来获得。
• 素数隐含词是指当你手头有一群隐含词时，不能与任何其他隐含词组合，以获得更简单的隐含词。

这将使我们更容易理解算法。

现在是代码部分。我实现了算法的简化版本。没有“不关心”的投入。该实现假设问题的“素数隐含图”部分可以通过贪婪算法来解决，否则我们就放弃并抛出一个异常。

我主要关注代码的两个方面，但欢迎任何建议或改进！

• 弗罗森塞茨。Python区分了"normal“集(它是可变的，因此不能包含在一个集合中)和frozensets。因为我想要集内的集合，我基本上散落在任何地方，有时将它们与正常集混合。这样可以吗？有更好的方法吗？
• 数据抽象我公开了一个隐写符(一个字符串和一个集合的元组)的实现，这会使以后很难更改它。事实上，我最初设计的它只是一个字符串，后来我对它进行了修改，这涉及到大量的搜索/替换。解决这个问题的正确方法是什么？(我对OOP抽象略知一二，但我通常觉得它们冗长易碎，很难设计好。)

# 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

Answer 1

函数签名

这是：

def combine(implicant_a, implicant_b):
    str_a, nums_a = implicant_a
    str_b, nums_b = implicant_b

应该朝两个方向中的一个方向走：

• 解包参数本身，即def combine(str_a, nums_a, str_b, nums_b)；或
• 制作某种命名的元组：

def combine(implicant_a, implicant_b):
    # Refer to implicant_a.str and implicant_a.nums

这个combine函数也有一个有问题的返回类型--混合布尔-或组合-隐含项。在失败时返回False是一种C-主义.在Python中，更明智的做法是引发一个异常，然后在调用代码中捕获它(或不捕获)。

不隐藏内置的

def iter(implicants):

应该有不同的名字，因为iter已经是一件事了。

特定异常

raise Exception()

实际上是不可能有意义地抓住这一例外，并将其与其他人区分开来。您至少应该使用更窄的内置(也许是ValueError)，或者更有可能定义自己的异常。这可以用两行来完成，并使调用者的工作更加容易。

测试

你有测试，那很好！实际上，您应该将asserts应用到它们上，这样它们就可以作为一种正常检查快速运行。