布尔表达式的等价性

Question

我有一个问题,包括比较布尔表达式(OR是+,AND是*).更准确地说,这是一个例子:

我有以下表达式:"A + B + C",我想将它与"B + A + C"进行比较.比较像字符串不是一个解决方案 - 它会告诉我表达式不匹配当然是假的.关于如何比较这些表达式的任何想法？

关于如何解决这个问题的任何想法？我接受任何建议,但(作为注释)我的应用程序中的最终代码将用C++编写(C当然接受).

正常表达式也可以包含括号:

(A*B*C)+ D或A + B*(C + D)+ X*Y.

提前致谢,

尤利安

Answer 1

我认为对真值表的详尽(并且可能耗费精力)创建的竞争方法是将所有表达式减少为规范形式并进行比较.例如,将所有内容重写为连接正常形式,并使用关于符号排序(例如,术语中的字母顺序)和术语(例如,术语中的第一个符号的字母顺序)的一些规则.当然,这要求一个表达式中的符号A与另一个表达式中的符号A相同.

用C或C++函数编写(或从网上抓取)将表达式重写为CNF是多么容易我不知道.但是,在C和C++中已经完成了很多AI工作,所以当你使用Google时,你可能会找到一些东西.

我对这种方法和真值表方法的比较计算复杂性有点不确定.我强烈怀疑它是一样的.

无论您使用真值表还是规范表示,您当然可以通过根据输入表单中包含的不同符号的数量将输入表单拆分为组来完成工作.

编辑:在阅读其他答案时,特别是关于生成所有真值表并进行比较的建议,我认为@Iulian严重低估了可能的真值表的数量.

假设我们在RPN上建立表达式,这将避免必须处理括号,并且有10个符号,这意味着9(二元)运算符.会有10个!符号的不同排序,以及运算符的2 ^ 9个不同的排序.因此会有10个!此表达式的真值表中的x 2 ^ 9 == 1,857,945,600行.这确实包括一些重复,任何只包含'和'和'或'的表达式将是相同的,无论符号的顺序如何.但我不确定我能否进一步说明这一点......

还是我犯了一个大错？

Answer 2

您可以在所有可能的输入上计算每个表达式的真值表,然后比较真值表.