Computational Boolean Algebra Recursive Tautology—URP Implementation

​ 上节讲到如果不能判断一个函数是否是重言式，我们选择一个变量，使用Shannon cofactor，将复杂的函数划分成两个较简单的部分，然后递归判断两个子式是否为1。

Recursive Cofactoring

​ 如下图。

​ 求 Fa 时，a=1，此时的 abd 项变为 bd，因此 [01 01 11 01] 修改为 [11 01 11 01] ；同理，bc’ 项不变，因此还是 [11 01 10 11] 。

​ 求 Fc 时，c=1，此时 bc’ 项变为 0，因此这项的位置立方符号则删掉。这样 cube list 就变得更短。

Unate Functions

​ 如何选择变量x？什么时候终止递归？什么时候只需要观察、计算位置PCN来判断是否是重言式？

​

​ 一个式子中如果有 a 就没有 a’ ，有 b‘ 就没有 b。

​ They don’t all have to be positive. They don’t all have to be negative. They just have to be 1 polarity.

​ 单调非递减函数：f(x)的值不会减小。Unate 函数正是类似的概念，只不过是针对多个乘积项之和的布尔函数。假设有一个 positive unate 变量x，如果这个变量从0变到1，那么输出的 f 无非只有 0->0、1->1、0->1这三种情况，这就是布尔领域的单调非递减函数。

Can Exploit Unate Func’s For Computation

​ 把cube-list垂直放置，并忽略不需要关心的内容（如，第一个f(a,b,c)中的a项，该项不存在b、c，因此b、c处的slot为11，这个cube表示这项为a。因此可忽略为11的slot）。

​ 只需要机械地从上往下看所有的cube，看每个cube中每个slot的值，看是否该cube该插槽的值和其它cube该插槽的值相同。如下图所示得出结果如下：

​ ① 左侧 unate 可以很容易的发现 ：a 只出现在一极（a：01），b 只出现在一级（b’：10），c 只出现在一级（c：01）。

​ ② 右侧 not unate 可以发现：b 即在 b（01）中出现，又在b’（10）中出现，即可通过观察快速判断出这个函数不是 unate 函数！！！

​ 为什么我们要讨论Unate函数呢？因为可以利用Unate函数来判断重言式！！！

Using Unate Functions in Tautology Checking

​ We can look for tautology directly if we have a unate cube-list.

​ 视频10:21没看懂…

So, Unateness Gives Us Termination Rules

​ ① Rule1：如果cube-list有一项为[11 11 … 11]（可以理解为全为11的这个list表示该乘积项永远为1，则函数f() = 乘积项A + 1 + 乘积项B = 1），则为tautology。

​ ② Rule2：如果cube-list是unate ，并且没有 [11 11 … 11]，那么 f() 不可能是 tautology，此时就可以停止递归了。

​ So, these rules are important because it means that you don’t always have to go down to one cube at the bottom before you can calculate stuff. You can calculate that you can stop and return an answer with big and very complicated lists of cubes.

​ ③ Rule3：…

​ 问题：除非有一个unate-list，否则就不能更好地利用上面终止递归的规则。

​ So, when I pick variables to split on, maybe I should try to pick the splitting variables to force the cofactors to be unate. So, the big idea is to pick the most not-unate variable as the variable to split on the variable to cofactor on. So, you try to pick the most binate variable. And this is a heuristic, right, no guarantees.

​ 下图中 x 和 w 都是binate。

​ 选择出现在更多个乘积项中的binate变量，因为这样将简化更多的cube，有可能更多的cube会消失。

​ 但是如果有两个binate变量出现在相同数量的乘积项中怎么办？例如 x 和 w 都是 binate，并且都出现在4个乘积项中，此时该选哪个呢？

​ 此时，计算他们以 true 形式出现在多少 cube 中，以及它们以 complement （补体）形式出现在多少 cube 中。取它们差的绝对值，选择绝对值较小的那个。这样做的是因为平衡 positive cofator tree 和 negative cofator tree 的复杂性。

Algorithm

Example

​ 因为 a 出现在4个项中，b出现在2个项中，c出现在2个项中，因此选择变量 a 进行划分。

​ 左下角：a=1 时，得到方框中的cube-list，其中最后一行 a’=0，因此该项消失。因为此时无法通过这个cube-list得到结果，没有适用的规则，所以要对该cube进行递归。

​ 右下角：a=0时，前三项都消失。第四项，a’=1，因此第个cube变为了[11 11 11]，因此可以立即得出 f() 是 Tautology！！！

​ 对左下角的递归如下图：向下递归时设 b=1 和 b=0，（PPT有错，理解下图做法即可）。

Summary

11248)]

​ 对左下角的递归如下图：向下递归时设 b=1 和 b=0，（PPT有错，理解下图做法即可）。

[外链图片转存中…(img-ugGNaci1-1626529711248)]

Summary