算法之布尔表达式化简

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 4 分钟

算法之布尔表达式化简

概念介绍

布尔基础:

  • 逻辑表达式: 由逻辑变量和与 ∧\land ,或 ∨\lor ,非 ¬\neg 3种运算符连接所构成的表达式。

  • 析取式: 表达式之间都通过逻辑或连接的复合表达式。

  • 合取式: 表达式之间都通过逻辑与连接的复合表达式。

  • 合取范式 (Conjunctive Normal Form)2 是命题公式的一个标准型，它由一系列析取子句 用合取操作连接而来。如 (a)∧(a∨¬c)∧(b∨c)(a) \land (a \lor \neg c) \land (b \lor c)

  • 与之相反，析取范式 (Disjunctive Normal Form) 是命题公式的另一个标准型，它由一系列 合取子句 用 析取操作 连接而来。如 (a)∨(a∧¬c)∨(b∧c)(a) \lor (a \land \neg c) \lor (b \land c)

表达式化简:

  • 表达式相等: 两个表达式具有同样的变量，且对于变量的任意一组取值，表达式的值均相等，这两个表达式是相等的
  • 最小项: 如果某个表达式的某个乘积(与)项包含了表达式的全部变量，其中每个表达式都以原变量或是反变量的形式出现。n个变量可以有2^n个最小项。
  • 主析取式: 可以将表达式化简为全部由最小项组成的唯一表达式，也被称为主析取式(符合析取范式).

矩阵化提取析取范式

析取范式矩阵

设表达式出现的所有布尔变量为xi(i=1,2…n),n为布尔变量的个数,m为表达式的最小项个数。

例如 x1 x3 x5 + x2 x4 + x1 x2 x4 x5 可以写成:

1
2
3
4
5
[
 1 0 1 0 1
 0 1 0 1 0
 1 1 0 1 1 
]

单个布尔变量可以看成一个特殊的析取范式，只有一个最小项，且最小项只有一个布尔变量。

矩阵的计算

或运算

表达式 A 与表达式 B 的或运算，只需要将A和B的矩阵各行合并在一起，就可以得到结果

1
2
3
4
5
6
a11 a12 a13 ... a1n      b11 b12 b13 ... b1n   a11 a12 a13 ... a1n
a21 a22 a23 ... a2n   +  b21 b22 b23 ... b2n = ... ... ... ... ...
... ... ... ... ...      ... ... ... ... ...   am1 am2 am3 ... amn
am1 am2 am3 ... amn      bg1 bg2 bg3 ... bgn   b11 b12 b13 ... b1n
                                               ... ... ... ... ...
                                               bg1 bg2 bg3 ... bgn

其中 n 为A和B 使用的布尔变量个数，m 为A 中最小项个数，g 为B 中最小项个数。

单行析范矩阵的与操作

对于两个单行析范矩阵，他们的与操作也是一个单行析范矩阵，该矩阵的元素分别是两个矩阵对应元素的计算结果：

1
[a1 a2 ... an] * [b1 b2 ... bn] = [a1b1 a2b2 ... anbn]

析范矩阵的与操作

布尔表达式A 与 布尔表达式B 进行与操作，只要将A与B的矩阵的各行两两进行单行析范矩阵的与操作。

  1. 1*1 = 1
  2. 1*0 =1
  3. 0*1 =1
  4. 0*0 =0
1
2
3
4
1 1 0 0   1 0 1 0   1 1 1 0
0 0 1 0 * 1 1 0 1 = 1 1 0 1
                    1 0 1 0
                    1 1 1 1

析范矩阵的吸收操作

在矩阵中，如果某行含有另一行的所有非0元素,那么这行要被删除.

1
2
1 1 0 0
0 1 0 0  =  0 1 0 0

如何从语法树生成析范矩阵

  1. 如果当前语法节点是叶子节点（atom 或者 notatom), 生成当前节点的一阶析范矩阵
  2. 如果当前不是叶子节点：
    1. 获取第一个子节点和第二个子节点
    2. 根据与，或规则进行计算
    3. 使用吸收，化简矩阵
  3. 根节点的矩阵就是化简结果

问题

本方法的问题是在化简过程中未对"非"操作的布尔变量做处理。最终结果中可能会存在仍有进一步结合的可能性("非"A 或 A),或者是可以消去的子集("非"A 与 A)。

矩阵化提取析取范式V2

这一节优化了上一版本的问题，即添加了对“非”操作布尔变量的处理。

提取矩阵

设表达式出现的所有布尔变量为xi(i=1,2…n),n为布尔变量的个数,m为表达式的最小项个数。

例如 x1 x3 x5 + x2 x4 + x1 x2 x4 x5 可以写成:

1
2
3
4
5
[
 1 0 1 0 1
 0 1 0 1 0
 1 1 0 1 1 
]

例如 x1 !x3 x5 + x2 !x4 + x1 x2 x4 x5 可以写成:

1
2
3
4
5
[
 1 0 -1 0 1
 0 1 0 -1 0
 1 1 0 1 1 
]

对于不可拆分的原子布尔变量,如果表达式存在该表达式填写1，不存在该表达式填写0，存在该表达式的非填写-1.

或运算

表达式 A 与表达式 B 的或运算，只需要将A和B的矩阵各行合并在一起，就可以得到结果

1
2
3
4
5
6
a11 a12 a13 ... a1n      b11 b12 b13 ... b1n   a11 a12 a13 ... a1n
a21 a22 a23 ... a2n   +  b21 b22 b23 ... b2n = ... ... ... ... ...
... ... ... ... ...      ... ... ... ... ...   am1 am2 am3 ... amn
am1 am2 am3 ... amn      bg1 bg2 bg3 ... bgn   b11 b12 b13 ... b1n
                                               ... ... ... ... ...
                                               bg1 bg2 bg3 ... bgn

其中 n 为A和B 使用的布尔变量个数，m 为A 中最小项个数，g 为B 中最小项个数。很显然或运算中不涉及值的计算。

与操作

计算真值表:

A\B-101Ø
-1-1-1ØØ
0-101Ø
1Ø11Ø
ØØØØØ

Ø 表示 A 与 A’ , 即 永远是false.

单行析范矩阵的与操作

对于两个单行析范矩阵，他们的与操作也是一个单行析范矩阵，该矩阵的元素分别是两个矩阵对应元素的计算结果：

1
[a1 a2 ... an] * [b1 b2 ... bn] = [a1b1 a2b2 ... anbn]

析范矩阵的与操作

布尔表达式A 与 布尔表达式B 进行与操作，只要将A与B的矩阵的各行两两进行单行析范矩阵的与操作。

1
2
3
4
1 1 0 0   1 0 1 0   1 1 1 0
0 0 1 0 * 1 1 0 1 = 1 1 0 1
                    1 0 1 0
                    1 1 1 1

析范矩阵的简化操作

在矩阵中，如果某行含有Ø元素,那么这行要被删除.

1
2
-1 Ø 0 0
0 1 0 0  =  0 1 0 0

在矩阵中，如果某行含有另一行的所有非0元素,那么这行要被删除.

1
2
1 1 0 0
0 1 0 0  =  0 1 0 0

在矩阵中，如果某行与另一行，除了一个互斥，其他所有非0元素相同,那么这两行要被合并.

1
2
1 1 0 0
-1 1 0 0  =  0 1 0 0

参考资料

  • [1] 任春玲,刘晓平.矩阵化方法在布尔表达式化简中的应用.计算机技术及应用进展.北京,2004:1174-1177.

  • [2] github示例代码