基于{NOT,AND,OR,XOR,IMPLY,XNOR}生成短布尔公式的Python实现问询

核心思路 #

扩展逻辑集中的XOR/XNOR可高效表达变量奇偶性或等价关系（替代冗长的DNF组合），IMPLY可简化条件依赖式（替代NOT a OR b类结构）。通过模式匹配替换+符号化简的组合，将基于NOT/AND/OR的长表达式转换为包含扩展运算符的短公式。

具体实现步骤 #

1. 生成初始布尔表达式 #

先从真值表生成基于NOT/AND/OR的初始DNF/CNF，可使用PyEDA快速完成：

• 定义变量、构建真值表
• 转换为布尔表达式

2. 模式匹配替换扩展运算符 #

识别并替换以下典型模式：

• (a AND NOT b) OR (NOT a AND b) → a XOR b
• (a AND b) OR (NOT a AND NOT b) → a XNOR b（或~(a XOR b)）
• NOT a OR b → a IMPLY b
• 多变量奇偶性组合（如4项AND的OR）→ 多变量XOR链（如a XOR b XOR c）

3. 迭代优化与化简 #

使用SymPy的符号化简功能，指定允许扩展运算符，迭代优化直到表达式长度不再缩短。

Python 代码示例 #

from pyeda.inter import exprvars, truthtable, exprfromtruth
from sympy import simplify_logic, Xor, Implies, Equivalent
from sympy.logic.boolalg import BooleanFunction

def extend_logic_simplify(tt_binary_str, var_names):
    # 1. 从真值表生成初始表达式（PyEDA）
    vars = exprvars(*var_names)
    tt = truthtable(vars, tt_binary_str)
    pyeda_expr = exprfromtruth(tt)
    sym_expr = pyeda_expr.to_sympy()

    # 2. 自定义模式替换：替换为扩展运算符
    def replace_patterns(expr):
        # 替换XNOR为等价式
        for i in range(len(vars)-1):
            a, b = vars[i], vars[i+1]
            expr = expr.subs((a & b) | (~a & ~b), Equivalent(a, b))
            # 替换XOR
            expr = expr.subs((a & ~b) | (~a & b), Xor(a, b))
            # 替换IMPLY
            expr = expr.subs(~a | b, Implies(a, b))
        
        # 合并多变量XOR
        if isinstance(expr, BooleanFunction):
            args = list(expr.args)
            xor_args = []
            other_args = []
            for arg in args:
                if isinstance(arg, Xor):
                    xor_args.extend(arg.args)
                else:
                    other_args.append(arg)
            if len(xor_args) >= 2:
                combined_xor = Xor(*xor_args)
                other_args.append(combined_xor)
                expr = expr.func(*other_args)
        return expr

    # 3. 迭代化简
    simplified = replace_patterns(sym_expr)
    simplified = simplify_logic(simplified, form='dnf', ops=('not', 'and', 'or', 'xor', 'implies', 'equivalent'))
    
    # 再次替换确保所有可替换模式都被处理
    simplified = replace_patterns(simplified)
    return simplified

# 示例：3变量真值表（奇数个1时输出1，即XOR(a,b,c)）
tt_str = "01101001"
var_names = ['a', 'b', 'c']
result = extend_logic_simplify(tt_str, var_names)
print("初始表达式（PyEDA）:", exprfromtruth(truthtable(exprvars(*var_names), tt_str)))
print("简化后表达式:", result)

# 10变量示例：假设真值表为变量奇偶性判断，二进制字符串长度为2^10=1024
# tt_10var = "..."  # 1024位的二进制字符串
# var_10 = [f'x{i}' for i in range(10)]
# result_10 = extend_logic_simplify(tt_10var, var_10)
# print("10变量简化后表达式长度:", len(str(result_10)))

关键注意事项 #

• 对于10变量等大规模真值表，PyEDA生成初始表达式时需注意内存占用，可直接通过二进制字符串构建真值表，避免显式枚举所有行。
• 模式替换规则可根据需求扩展，比如增加多变量IMPLY的组合替换（如NOT a OR NOT b OR c → Implies(a & b, c)）。
• SymPy的simplify_logic函数通过ops参数指定允许的运算符，确保化简过程中保留XOR/IMPLY等扩展符号。

内容的提问来源于stack exchange，提问作者tangsongxiaoba