算法之布尔表达式化简

算法之布尔表达式化简

概念介绍

  1. 逻辑表达式: 由逻辑变量和{与,或,非} 3种运算符连接所构成的表达式。
  2. 逻辑表达式相等: 两个表达式具有同样的变量,且对于变量的任意一组取值,表达式的值均相等,这两个表达式是相等的
  3. 最小项: 如果某个表达式的某个乘积(与)项包含了表达式的全部变量,其中每个表达式都以原变量或是反变量的形式出现。n个变量可以有2^n个最小项。
  4. 主析取式: 可以将表达式化简为全部由最小项组成的唯一表达式,也被称为主析取式.

示例代码在github

矩阵化提取析取范式

析取范式矩阵

设表达式出现的所有布尔变量为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. 根节点的矩阵就是化简结果

参考资料:

  • 任春玲,刘晓平.矩阵化方法在布尔表达式化简中的应用[C].//计算机技术及应用进展.北京:%,2004:1174-1177.
-------------本文结束感谢您的阅读-------------
坚持分享,您的支持将鼓励我继续创作!
0%