布尔表达式的等价性
我遇到的问题在于比较布尔表达式（ OR 是 +，AND 是 * ）。更准确地说，这里有一个例子：
我有以下表达式：“A+B+C”，我想将它与“B+A+C”进行比较。像字符串一样比较它不是一个解决方案 - 它会告诉我表达式不匹配，这当然是错误的。关于如何比较这些表达式有什么想法吗？
关于如何解决这个问题有什么想法吗？我接受任何类型的建议，但（作为注释）我的应用程序中的最终代码将用 C++ 编写（当然也接受 C）。
正常表达式还可以包含括号：
(A * B * C) + D 或 A+B*(C+D)+X*Y
提前致谢，
Iulian
I have a problem that consist in comparing boolean expressions ( OR is +, AND is * ). To be more precise here is an example:
I have the following expression: "A+B+C" and I want to compare it with "B+A+C". Comparing it like string is not a solution - it will tell me that the expressions don't match which is of course false. Any ideas on how to compare those expressions?
Any ideas about how can I tackle this problem? I accept any kind of suggestions but (as a note) the final code in my application will be written in C++ (C accepted of course).
An normal expression could contain also parenthesis:
(A * B * C) + D or A+B*(C+D)+X*Y
Thanks in advance,
Iulian
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为详尽（并且可能令人筋疲力尽）创建真值表的竞争方法是将所有表达式简化为规范形式并进行比较。例如，将所有内容重写为合取范式，并使用一些有关符号（例如术语内的字母顺序）和术语（例如术语中第一个符号的字母顺序）排序的规则。当然，这要求一个表达式中的符号 A 与另一表达式中的符号 A 相同。
我不知道编写（或从网上获取）C 或 C++ 函数将表达式重写为 CNF 有多容易。然而，已经有很多人工智能工作是用 C 和 C++ 完成的，所以当你谷歌时你可能会找到一些东西。
我也有点不确定这种方法和真值表方法的相对计算复杂性。我强烈怀疑这是一样的。
无论您使用真值表还是规范表示，您当然可以通过根据输入形式包含的不同符号的数量将输入形式分成几组来减少要完成的工作。
编辑：在阅读其他答案时，特别是生成所有真值表并进行比较的建议，我认为@Iulian严重低估了可能的真值表的数量。
假设我们选择 RPN 来编写表达式，这将避免处理括号，并且有 10 个符号，这意味着 9 个（二元）运算符。将会有10个！符号的不同顺序，以及运算符的 2^9 种不同顺序。因此将会有 10 个！ x 2^9 == 此表达式的真值表中有 1,857,945,600 行。这确实包括一些重复项，例如，任何仅包含“and”和“or”的表达式将是相同的，无论符号的顺序如何。但我不确定我能否进一步解决这个问题……
或者我犯了一个大错误？
I think the competing approach to exhaustive (and possibly exhausting) creation of truth tables would be to reduce all your expressions to a canonical form and compare those. For example, rewrite everything into conjunctive normal form with some rule about the ordering of symbols (eg alphabetical order within terms) and terms (eg alphabetical by first symbol in term). This of course, requires that symbol A in one expression is the same as symbol A in another.
How easy it is to write (or grab from the net) a C or C++ function for rewriting your expressions into CNF I don't know. However, there's been a lot of AI work done in C and C++ so you'll probably find something when you Google.
I'm also a little unsure about the comparative computational complexity of this approach and the truth-table approach. I strongly suspect that it's the same.
Whether you use truth tables or a canonical representation you can of course keep down the work to be done by splitting your input forms into groups based on the number of different symbols that they contain.
EDIT: On reading the other answers, in particular the suggestion to generate all truth tables and compare them, I think that @Iulian has severely underestimated the number of possible truth tables.
Suppose that we settle on RPN to write the expressions, this will avoid having to deal with brackets, and that there are 10 symbols, which means 9 (binary) operators. There will be 10! different orderings of the symbols, and 2^9 different orderings of the operators. There will therefore be 10! x 2^9 == 1,857,945,600 rows in the truth table for this expression. This does include some duplicates, any expression containing only 'and' and 'or' for instance will be the same regardless of the order of symbols. But I'm not sure I can figure this any further ...
Or am I making a big mistake ?
您可以计算所有可能输入的每个表达式的真值表，然后比较真值表。
You can calculate the truth table for each expression over all possible inputs then compare the truth tables.