DNF算法的代码

DNF算法是指将逻辑表达式转换为与或非（DNF）形式的算法，这里提供一份Python代码实现：

def dnf(expression):
    variables = set()
    clauses = []
    for clause in expression.split("∧"):
        literals = []
        for literal in clause.split("∨"):
            if literal.startswith("!"):
                variables.add(literal[1:])
                literals.append((False, literal[1:]))
            else:
                variables.add(literal)
                literals.append((True, literal))
        clauses.append(literals)

    truth_table = []
    for i in range(2**len(variables)):
        truth_values = {}
        for j, variable in enumerate(variables):
            truth_values[variable] = bool((i >> j) & 1)
        truth_table.append(truth_values)

    dnf_clauses = []
    for truth_values in truth_table:
        if all(any(literal_value == truth_values[literal_variable] for literal_value, literal_variable in clause) for clause in clauses):
            dnf_clause = []
            for variable, value in truth_values.items():
                if not value:
                    dnf_clause.append((False, variable))
                else:
                    dnf_clause.append((True, variable))
            dnf_clauses.append(dnf_clause)

    return "∨".join("∧".join(("!" if not value else "") + variable for value, variable in clause) for clause in dnf_clauses)

其中，`expression`参数是逻辑表达式，例如`"p ∧ q ∨ !p ∧ r"`。函数首先将表达式转换为子句的列表，每个子句包含多个文字。然后，函数生成真值表并计算出每个子句是否满足。最后，函数使用满足子句的变量值生成DNF子句，并将其组合成DNF表达式。