将带括号的条件转换为不带括号的等价条件

Question

我正在开发一个应用程序，用户可以在其中向某些任务添加条件。

例如，他可以有条件 a、b、c、d 并将它们组合在一起，最终看起来像：

(a AND b) OR ( c AND d )
或
(a AND b AND c) or d
或
(a AND !b) AND c OR !d

等等。

如何通过删除括号将这些条件转换为等效条件？

Answer 1

布尔代数中的每个表达式都可以转换为等效表达式，无需括号，仅使用AND、OR和!（一元NOT）。

这是一个简单但低效的算法：

使用示例表达式(a OR !b) AND c，

1. 为变量真值的每个组合构建真值表：

   | a | b | c | (a OR !b) AND c  |
   | 0   0   0 | 0                |
   | 0   0   1 | 1                |
   | 0   1   0 | 0                |
   | 0   1   1 | 0                |
   | 1   0   0 | 0                |
   | 1   0   1 | 1                |
   | 1   1   0 | 0                |
   | 1   1   1 | 1                |
   

2. 对于表达式为 true 的每组值（最右列中的每一行），使用s1创建一个表达式，并且仅针对该特定值组计算结果为 true。AND!

   | a | b | c | (a OR !b) AND c  |
   | 0   0   0 | 0                |
   | 0   0   1 | 1                |  (!a AND !b AND c )
   | 0   1   0 | 0                |
   | 0   1   1 | 0                |
   | 1   0   0 | 0                |
   | 1   0   1 | 1                |  (a  AND !b AND c )
   | 1   1   0 | 0                |
   | 1   1   1 | 1                |  (a  AND b  AND c )
   

3. 用 OR 连接表达式。

   (!a AND !b AND c ) OR (a  AND !b AND c ) OR (a  AND b  AND c )
   

4. 生成的表达式很少是最小的，因此您可能需要随后应用一些最小化技术。

   (!a AND !b AND c) OR (a AND !b AND c) OR (a AND b AND c)
   =
   (!a AND !b AND c) OR (a AND c)
   =
   (!b AND c) OR (a AND c)
   

哒哒！

需要注意的是，在步骤 1 中构建真值表是一个 O(2^n) 操作（以变量数量计算），这是很糟糕的。对于变量数量较多的情况，您可能需要使用不同的技术。该算法的主要优点是它使任何表达式如何转换为您想要的形式变得非常明显。

编辑：要明确的是，如果您使用正常的优先规则，则可以删除最终表达式中的括号。