SymPy 逻辑模块sympy.logic完全指南从布尔表达式构造到 SAT 求解【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy导读SymPy 的sympy.logic模块提供了一套完整的命题逻辑propositional logic工具箱你既可以用、|、~等 Python 运算符直接构造和操作符号化布尔表达式也可以借助SOPform、POSform、ANFform从真值表反推逻辑函数还能通过to_cnf/to_dnf等函数完成范式转换、使用simplify_logic化简并最终用satisfiable、valid、entails等推理例程进行可满足性判定与知识库推理。读完本文你将掌握这一模块从表达式构造、范式变换、真值表映射到 SAT 求解的完整调用链并了解其背后的源码实现主要位于 sympy/logic/boolalg.py 与 sympy/logic/inference.py。构造逻辑表达式使用 Python 运算符直接构造逻辑模块的核心能力是用 Python 原生运算符表达逻辑运算。所有标准布尔运算符都被重载在 Boolean 基类上与直觉完全一致→And合取逻辑与|→Or析取逻辑或~→Not否定逻辑非→Implies蕴含x y表示Implies(x, y)→Implies反向蕴含x y表示Implies(y, x)^→Xor异或文档给出的基础示例可以直接在交互环境中验证 from sympy import * x, y symbols(x,y) y | (x y) y | (x y) x | y x | y ~x ~x蕴含运算的构造 x y Implies(x, y) x y Implies(y, x)从源码看运算符重载的实现位于Boolean基类例如__and__直接返回And(self, other)__rshift__返回Implies(self, other)__lshift__返回Implies(other, self)见 boolalg.py。__or__、__xor__、__invert__同理且都定义了对应的反向运算符__rand__、__ror__等因此True x这类 Python 布尔值与符号混合的写法也能正常工作。与 SymPy 基础框架的集成与 SymPy 中大多数类型一样布尔表达式继承自Basic因此天然具备subs替换、atoms原子提取等能力 (y x).subs({x: True, y: True}) True (x | y).atoms() {x, y}subs在 Boolean 中被重载返回类型标注为Boolean保证替换后的结果仍是布尔对象。此外Boolean还提供了equals真值表等价判断见 boolalg.py、as_set把布尔表达式改写为实数集如Eq(x, 0).as_set()返回{0}等高级方法。布尔函数类总览逻辑模块内置了完整的布尔函数类型全部定义在 sympy/logic/boolalg.py 中。文档通过 autoclass 指令收录了以下核心类类语义说明Boolean布尔对象基类所有逻辑运算的载体kind BooleanKindBooleanTrue/BooleanFalse逻辑真 / 逻辑假单例对象对应true/falseAnd/Or合取 / 析取可接受任意多个参数自动展平嵌套Not否定作用于单个参数Xor异或奇数个真则真Nand/Nor与非 / 或非默认会被自动求值为Not(And(...))/Not(Or(...))可用evaluateFalse保留原形Xnor同或偶数个真则真Implies蕴含Implies(A, B)等价于~A \| BEquivalent等价所有参数真值相同ITEif-then-else 选择三参ITE(A, B, C)等价于(A B) \| (~A C)Exclusive互斥恰好一个参数为真一个与gateinputcount见下文相关的细节值得注意Nand、Nor、Xnor默认会展开成Not(And(...))等形式这会影响门输入计数测试用例可在 sympy/logic/tests/test_boolalg.py如test_Nand、test_Xnor中找到验证。由真值表推导逻辑函数SOPform / POSform / ANFform这是逻辑模块最有实用价值的功能之一给出输出为 1 的输入组合minterms最小项自动生成最简的逻辑表达式。SOPform和之积最小项之和SOPform(variables, minterms, dontcaresNone)使用简化的成对比较_simplified_pairs加冗余组消除算法_rem_redundancy把生成1的输入组合转换为最小的和之积sum-of-products形式返回Or对象。其实现见 boolalg.py。 from sympy.logic import SOPform from sympy import symbols w, x, y, z symbols(w x y z) minterms [[0, 0, 0, 1], [0, 0, 1, 1], ... [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1]] dontcares [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]] SOPform([w, x, y, z], minterms, dontcares) (y z) | (~w ~x)minterms与dontcares支持三种等价表示源码通过_input_to_binlist统一归一化见 boolalg.py二进制列表如[[0, 0, 0, 1], ...]按variables顺序逐位给出整数如[1, 3, 7, 11, 15]整数即二进制位的十进制表示字典允许部分指定如[{w: 0, x: 1}, {y: 1, z: 1, x: 0}]。三种写法可混用例如 minterms [4, 7, 11, [1, 1, 1, 1]] dontcares [{w : 0, x : 0, y: 0}, 5] SOPform([w, x, y, z], minterms, dontcares) (w y z) | (~w ~y) | (x z ~w)POSform和之积最大项之积POSform与SOPform输入完全一致但输出的是积之和product-of-sums形式返回And对象。内部实现先把未出现在 minterms 与 dontcares 中的组合作为 maxterms最大项再对 maxterms dontcares 做同样的化简见 boolalg.py。 from sympy.logic import POSform minterms [1, 3, 7, 11, 15] dontcares [0, 2, 5] POSform([w, x, y, z], minterms, dontcares) z (y | ~w)注意SOPform 与 POSform 使用 Quine-McCluskey 算法源码 docstring 明确引用了该算法与 dont-care 术语结果是最简形式之一但可能不是唯一解——文档原文明确提示The result will be one of the (perhaps many) functions that satisfy the conditions。此外若某个 minterm 同时出现在 dontcares 中函数会抛出ValueError。ANFform代数范式Zhegalkin 多项式ANFform(variables, truthvalues)把真值表的结果列转换为代数范式Algebraic Normal Form即 Zhegalkin 多项式。在这种表示中True对应 1、False对应 0And即乘法、Xor即加法 from sympy.logic.boolalg import ANFform from sympy.abc import x, y ANFform([x], [1, 0]) x ^ True ANFform([x, y], [0, 1, 1, 1]) x ^ y ^ (x y)实现上ANFform先调用anf_coeffs(truthvalues)得到 Zhegalkin 系数再对系数为 1 的项用_convert_to_varsANF转换为变量合取最后组装成Xor见 boolalg.py。若truthvalues长度不等于2^nn 为变量数会抛出ValueError。范式转换ANF / CNF / DNF / NNF逻辑模块提供了四套范式的转换与判定函数全部位于 sympy/logic/boolalg.py函数作用to_anf(expr, deepTrue)转代数范式deepFalse时只转换顶层表达式见 boolalg.pyto_nnf(expr, simplifyTrue, formNone)转否定范式Not只作用于文字literalform可传cnf/dnf优化 XOR 转换方向to_cnf(expr, simplifyFalse, forceFalse)转合取范式(A \| ~B) (B \| C) ...to_dnf(expr, simplifyFalse, forceFalse)转析取范式(A ~B) \| (B C) \| ...is_anf/is_nnf/is_cnf/is_dnf判定表达式是否已是某种范式to_cnf与to_dnf的行为高度对称源码实现的关键点在于若表达式已是目标范式则直接返回不做多余转换Dont convert unless we have to见 boolalg.py先eliminate_implications(expr, form...)消除蕴含再做分配律展开当simplifyTrue时内部走simplify_logic(expr, cnf/dnf, True, forceforce)使用 Quine-McCluskey 求最简形式可能非常耗时当变量超过 8 个时必须显式传forceTrue否则抛出ValueError见 boolalg.py。示例 from sympy.logic.boolalg import to_cnf, to_dnf, to_nnf, to_anf from sympy.abc import A, B, C, D to_cnf(~(A | B) | D) (D | ~A) (D | ~B) to_cnf((A | B) (A | ~A), True) # simplifyTrue A | B to_dnf(B (A | C)) (A B) | (B C) to_nnf(Not((~A ~B) | (C D))) (A | B) (~C | ~D) to_anf(Not(A)) A ^ True关于 ANF 的一个关键特性它是规范范式canonical normal form——两个等价的公式转换后必然得到相同的 ANF见 boolalg.py因此可用于公式等价性判定。化简与等价性测试simplify_logic最简 SOP/POS 化简simplify_logic(expr, formNone, deepTrue, forceFalse, dontcareNone)把布尔函数化简为最简 SOP 或 POS 形式返回值是Or或And对象。核心参数见 boolalg.pyformcnf或dnf时返回对应范式的最简表达式None默认时返回参数个数更少的形式默认偏向 CNFdeep是否递归化简输入中内嵌的非布尔函数如关系式force默认限制 8 个变量以内才做完整化简超过 8 个变量只做符号级化简由deep控制forceTrue解除限制但可能耗时极长dontcare指定在该表达式为真的输入视为无关项dont care典型场景是Piecewise的条件化简——先前条件已经覆盖的输入无需再考虑。示例 from sympy.logic import simplify_logic from sympy.abc import x, y, z b (~x ~y ~z) | ( ~x ~y z) simplify_logic(b) ~x ~y simplify_logic(x | y, dontcarey) xsimplify_logic的内部实现相当精巧先把关系式Relational替换为Dummy符号以减少变量数、再生成真值表并用_get_truthtable计算、最后套用模式库_simplify_patterns_and/_simplify_patterns_or/_simplify_patterns_xor进行模式化化简见 boolalg.py。同时SymPy 的通用 simplify 函数也可以化简逻辑表达式到最简形式这是文档明确提示的另一条路径。bool_map变量重命名下的逻辑等价bool_map(bool1, bool2)判断两个布尔表达式是否在某种变量对应关系下逻辑等价若存在这样的映射返回(化简后的bool1, 变量映射字典)否则返回False见 boolalg.py。 from sympy import SOPform, bool_map, Or, And, Not, Xor from sympy.abc import w, x, y, z, a, b, c, d function1 SOPform([x, z, y],[[1, 0, 1], [0, 0, 1]]) function2 SOPform([a, b, c],[[1, 0, 1], [1, 0, 0]]) bool_map(function1, function2) (y ~z, {y: a, z: b})实现分两步先对两个表达式分别simplify_logic再用指纹字典_finger做结构匹配内部match函数。文档也提醒映射结果不唯一但规范canonical——例如(w, z)可能对应(a, d)也可能对应(d, a)函数只保证返回其中之一。针对指纹匹配的健壮性问题如 issue 4835 描述的Basic.match缺陷代码注释说明这是一种专门为化简后布尔表达式设计的替代方案。表达式操作逻辑模块还提供一组直接操作表达式结构的函数见 boolalg.pydistribute_and_over_or(expr)把合取分配到析取上得到 CNF。Or(A, And(Not(B), Not(C)))→(A | ~B) (A | ~C)distribute_or_over_and(expr)把析取分配到合取上得到 DNF输出不做化简。And(Or(Not(A), B), C)→(B C) | (C ~A)distribute_xor_over_and(expr)把异或分配到合取上输出不做化简。And(Xor(Not(A), B), C)→(B C) ^ (C ~A)eliminate_implications(expr, formNone)消除蕴含与等价转换为等价的 NNF内部直接调用to_nnf(expr, simplifyFalse, formform)见 boolalg.py。例如Equivalent(A, B, C)→(A | ~C) (B | ~A) (C | ~B)。这三个distribute_*函数共用底层递归分发器_distribute其逻辑是若表达式是指定外层运算符的实例且参数中存在另一运算符则把该参数逐个与其余部分组合并递归分发见 boolalg.py。真值表与整数表示映射truth_table生成真值表truth_table(expr, variables, inputTrue)返回一个生成器产出所有输入组合及其对应的表达式取值。核心参数expr待求值的布尔表达式variables变量列表注意真值表按product((0, 1), repeatlen(variables))全排列变量顺序影响输出顺序inputTrue时产出(输入列表, 结果)元组False时只产出结果值序列。 from sympy.logic.boolalg import truth_table from sympy.abc import x,y table truth_table(x y, [x, y]) for t in table: ... print({0} - {1}.format(*t)) [0, 0] - True [0, 1] - True [1, 0] - False [1, 1] - True当inputFalse时输出序列的下标对应输入组合的二进制编码可与sympy.utilities.iterables.ibin配合还原输入文档给出了[(y, 0), (x, 0)] - True的完整还原示例见 boolalg.py。整数 / 项 / 符号之间的映射这一组函数解决真值表位置整数↔ 0/1 列表 ↔ 符号表达式之间的互转问题函数作用term_to_integer(term)把 0/1 列表或二进制字符串转换为整数integer_to_term(integer, n)整数转回 n 位 0/1 列表bool_minterm(k, variables)返回第 k 个最小项直接形式编码为 1、补形式编码为 0。bool_minterm(6, [x, y, z])→x y ~zbool_maxterm(k, variables)返回第 k 个最大项编码约定与最小项相反直接形式为 0、补形式为 1。bool_maxterm(6, [x, y, z])→z \| ~x \| ~ybool_monomial(k, variables)返回第 k 个单项式按变量存在/缺席的二进制编码用于 ANF 构建anf_coeffs(truthvalues)把真值表结果列转换为 Zhegalkin 多项式系数模 2 多项式to_int_repr(clauses, symbols)把 CNF 子句集转换为整数表示正数表示该编号变量、负数表示其否定。如to_int_repr([x \| y, y], [x, y]) [{1, 2}, {2}]见 boolalg.py其中anf_coeffs通过逐层异或x^y的蝶形计算把真值列变换为系数列bool_monomial与anf_coeffs配合即可从真值表手工重建 Zhegalkin 多项式源码 docstring 给出了完整示例见 boolalg.py。to_int_repr的整数表示是下游 SAT 求解器见下文直接使用的内部格式。推理satisfiable 与 SAT 求解器sympy.logic.inference模块inference.py实现了命题逻辑的推理例程。文档特别强调了satisfiable给定一个布尔表达式satisfiable判定它是否可满足——即是否存在一组变量赋值使整个句子为True。 from sympy.logic.inference import satisfiable from sympy import Symbol x Symbol(x) y Symbol(y) satisfiable(x ~x) False satisfiable((x | y) (x | ~y) (~x | y)) {x: True, y: True}返回值约定可满足时返回一个模型变量→真值的字典不可满足时返回False。这个例子恰好演示了x ~x永假而三子句合取式有模型xTrue, yTrue。satisfiable 的算法选择satisfiable(expr, algorithmNone, all_modelsFalse, minimalFalse, use_lra_theoryFalse)支持多种后端 SAT 求解器算法选择逻辑见 inference.pyalgorithm 参数可选值dpll、dpll2、pycosat、minisat22、z3默认行为algorithmNone时优先尝试pycosat若未安装则静默回退到纯 Python 实现的dpll2同样地minisat22需要pysat、z3需要z3库缺失时都回退dpll2all_modelsTrue可满足时返回模型生成器可用next()逐个取出不可满足时返回只含单个元素False的生成器minimalTrue要求返回最小模型仅当使用minisat22后端时有效use_lra_theoryTrue启用线性实数算术理论Linear Real Arithmetic此时强制使用dpll2若显式传入其他 algorithm 会抛ValueError。纯 Python 的 DPLL 实现位于 sympy/logic/algorithms/dpll.py经典 DPLL单元传播unit_propagate、纯符号find_pure_symbol、单元子句find_unit_clause与 sympy/logic/algorithms/dpll2.py现代实现内置 VSIDS 决策启发式与子句学习选项外部求解器封装位于 sympy/logic/algorithms/pycosat_wrapper.py、minisat22_wrapper.py、z3_wrapper.py。这些求解器共同的基础是把 CNF 转换为整数表示的子句集to_int_repr。satisfiable的all_models、valid、entails等行为在 sympy/logic/tests/test_inference.py 中有系统性测试。更多推理例程inference模块还提供valid(expr)判定表达式是否有效对所有赋值恒真。实现为not satisfiable(Not(expr))见 inference.py。如valid(A | ~A)为Truepl_true(expr, modelNone, deepFalse)判断给定赋值是否为该表达式的模型。部分赋值时可能返回None表示尚不明确deepTrue时会对剩余部分做有效/可满足性分析给出更精确的答案见 inference.pyentails(expr, formula_setNone)判断子句集是否蕴含某公式formula_set为空时退化为判定公式的效性。实现为把Not(expr)追加进子句集后检查合取式是否不可满足见 inference.py。如entails(C, [A B, B C, A])为Trueliteral_symbol(literal)提取文字literal对应的符号去掉否定外层如literal_symbol(~A)返回A见 inference.py。PropKB命题知识库inference模块还提供了知识库框架抽象基类KB定义tell/ask/retract接口与clauses属性PropKB(KB)是其命题逻辑实现见 inference.pytell(sentence)把句子的子句加入知识库内部用conjuncts(to_cnf(sentence))展开为 CNF 子句集合ask(query)用entails(query, self.clauses_)判断查询是否为知识库的逻辑结论retract(sentence)从知识库移除对应子句。 from sympy.logic.inference import PropKB from sympy.abc import x, y l PropKB() l.tell(x ~y) l.ask(x) True l.ask(y) False类 docstring 明确自述a KB for Propositional Logic. Inefficient, with no indexing即这是一个教学级、无索引的朴素实现适合理解推理原理。门电路输入计数gateinputcountgateinputcount(expr)返回实现该布尔表达式所需的逻辑门输入总数常用于数字电路综合与代价估算见 boolalg.py。计数规则只承认标准门And、Or、Xor、Not、ITE多路选择器Nand、Nor、Xnor会先被展开为Not(And(...))等再计数evaluateFalse可避免展开关系比较如x z和符号按一个布尔变量计单个符号计 0非布尔输入抛出TypeError。 from sympy.logic import And, Or, Nand, Not, gateinputcount from sympy.abc import x, y, z gateinputcount(And(x, y)) 2 gateinputcount(Or(And(x, y), z)) 4 gateinputcount(Nand(x, y, z)) # 自动展开为 Not(And(x,y,z)) 4 gateinputcount(Nand(x, y, z, evaluateFalse)) 3实用工作流一个完整示例把上述能力串起来一个典型的真值表 → 最简逻辑 → 可满足性验证工作流如下from sympy import symbols from sympy.logic import SOPform, POSform, simplify_logic from sympy.logic.inference import satisfiable, valid from sympy.logic.boolalg import truth_table, to_cnf w, x, y, z symbols(w x y z) # 1. 由真值表推导最简 SOP / POS minterms [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1]] dontcares [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]] sop SOPform([w, x, y, z], minterms, dontcares) # (y z) | (~w ~x) pos POSform([w, x, y, z], minterms, dontcares) # z (y | ~w) # 2. 范式转换供 SAT 求解器使用 cnf to_cnf(sop) # 3. 可满足性与有效性判定 print(satisfiable(sop)) # 一个使表达式为真的模型 print(valid(sop | ~sop)) # True重言式恒有效深入阅读逻辑模块核心实现sympy/logic/boolalg.py推理例程satisfiable / valid / entails / PropKBsympy/logic/inference.pyDPLL 与 SAT 求解器目录 sympy/logic/algorithmsDIMACS CNF 文件加载工具load/load_filesympy/logic/utilities/dimacs.py测试见 sympy/logic/tests/test_dimacs.py单元测试覆盖运算符重载、范式转换、bool_map、simplify_logic、求解器回退等sympy/logic/tests/test_boolalg.py 与 sympy/logic/tests/test_inference.py本模块与假设系统assumptions的联动入口sympy.logic包导出见 sympy/logic/init.py总体而言SymPy 的逻辑模块在纯 Python 环境中同时提供了符号化布尔代数构造、化简、范式与命题推理SAT 判定、知识库两条能力线前者面向数字电路设计、真值表综合等场景后者面向逻辑验证与自动推理。所有核心算法均可脱离外部依赖运行默认回退到内置的dpll2而pycosat、pysat、z3等可选后端则按需提供性能增强。【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考