代码之家 › 专栏 › 技术社区 › INS

布尔表达式的等价性

language-agnostic boolean-expression c c++

5

INS · 技术社区 · 16 年前

我在比较布尔表达式(或is+、is*)时遇到了一个问题。更准确地说,这里有一个例子:

我有下面的表达式:“A+B+C”,我想将它与“B+A+C”进行比较。将它像字符串一样进行比较并不是一个解决方案——它将告诉我表达式不匹配,这当然是错误的。关于如何比较这些表达有什么想法吗?

我对如何解决这个问题有什么想法吗?我接受任何建议,但是(作为注释)我的应用程序中的最终代码将用C++编写(当然是C接受)。

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

(a*b*c)+d 或 a+b*(c+d)+x*y

事先谢谢,

尤利安

2 回复 | 直到 16 年前

1

9

High Performance Mark 16 年前

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

如何编写(或从网上抓取)C或C++函数,将您的表达式重写为CNF,我不知道。然而,在C和C++中有很多人工智能工作,所以当你谷歌时你可能会发现一些东西。

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

无论您使用真值表还是规范表示,您当然可以根据输入表单所包含的不同符号的数量将输入表单分成多个组,从而减少要完成的工作。

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

假设我们使用rpn来编写表达式,这将避免处理括号,并且有10个符号,这意味着9(二进制)运算符。会有10个!符号的顺序不同,运算符的顺序也不同。因此将有10个!x 2^9=此表达式的真值表中的1857945600行。这确实包括一些重复项,例如,任何只包含“and”和“or”的表达式都将是相同的,而不管符号的顺序如何。但我不确定能不能再进一步…

还是我犯了个大错误?

2

8

Mark Byers 16 年前

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