立方体化简

还是拿上次那个栗子:

  f(x1,x2,x3)=∑(1,4,5,6) -> (!x1!x2x3)+(x1!x2!x3)+(x1!x2x3)+(x1x2!x3)

该函数真值表:

  

根据公式画出卡诺图:

得到最简函数为:!x2x3+x1!x3

函数的变量个数(原变量和反变量也算一个)代表立方体的维数.因为变量个数的2次方是该函数的立方体的顶点个数,也就是说,一个2变量的函数,那么有00,01,10,11这几个值,那么该函数的立方体是一个2维立方体.至于3个变量的函数,那就是3维.用下面图更直观:

   用变量代表一个2维立方体的X轴与Y轴,可以发现,相邻的顶点间只有一位不同,如果画好一面2维立方体,那么其他面也可以推导出来,至于更多的维数,可以用内嵌3维立方体表示,立方体间只有代表该3维的一个变量不同,其他都一样.

   根据真值表的最小项,标记一下使F=1的顶点:

 

  如果两个相邻的顶点都被标记了,那么可以使用一个可变变量X来标记两顶点间不相同的一位.所以上面的例子有1X0,10X,X01.这个3个顶点的其中一个都可以使F=1.但是得出的乘积项还不是最简函数.下面使用覆盖表化简.

画一个表,把刚得到的用可变变量乘积项都按行排列,把该函数的最小项按列排列,如果该可变变量乘积项

能覆盖该最小项则在该行所对应的最小项列中打钩.如果某一列的最小项只有一个勾覆盖它,那么使F=1的一个乘积项就就是本质蕴含项,那么这个可变变量是必选的,因为只有它才能使该最小项的结果为真.接下来可以先在表去掉这个必选项,并且把它所覆盖的最小项的列也去掉,得到:

下一步则用支配法,把重复覆盖的乘积项去掉,如上图,乘积项1X0既能使最小项4为真也能使最小项6为真,而10X只能使最小项4为真,而且1X0已经包含该功能,所以10X是多余的,可以把它去掉.

   最后,得到的可变变量乘积项为:X01和1X0,因为X不管取值为1或者0,只要x2为假x3为真,那么该函数都为真,后者一样,所以把X去掉得到:!x2x3+x1!x3 ,该结果与上面的卡诺图化简结果一致.这种覆盖表法其中心思想就是使能覆盖所有该函数为真的最小项的乘积项的个数达到最少，所覆盖的项尽量不被重复覆盖.

  

立方体是CAD工具所使用的化简方法,这种相邻一位不同的化简法是结合律的具体体现,我们也可以用列表化简的得到这种体现.由上面真值表得到的最小项画一个表,从上往下,把每一个最小项都与它下面的所有最小项对比,如果只有一位不相同的,就用可变变量X代替该位.最后得出的可变变量乘积项后,还是按从上往下对比,一直到找不出相邻只有一位不同的结果为止.这样就能得到立方体相邻两顶点间的可变变量乘积项.