我们知道,按照立方体理论,布尔函数可以用一个覆盖表示。设布尔函数
f (x1,...,xi, ...,xn , h)
可以用覆盖C表示。不难理解,布尔差分本身也是一个布尔函数,所以也能用覆盖表示,设其覆盖为D。因为
= f(c=0) f(c=1)
= f (x1,...,xi, ...,xn,0) f
(x1,...,xi, ...,xn,1)
设f(h = 0)与f(h = 1)分别表示为C0 ,C1
, 于是有
D = (C0-C1)∪(C1-C0)
= (C0∪C1)-(C1∩C0)
= (C0∪C1) # (C1∩C0)
其中 # 为锐积运算符。
根据立方体的意义,可以容易地由C得到C0和C1。 因而可求得表示布尔差分的覆盖D。
求覆盖D的算法
{
令立方体集合C0 = C1 = CX = φ;
for t∈C do
{
t1 = t; t1(h) = 'X'; --做临时立方体t1,并令其中h对应的位为'X'
if t(h) = '0' then C0 = C0∪t1
;
else if t(h) = '1' then C1 = C1∪t1
;
else CX = CX∪t1 ;
}
CX = (C1∩C0)∪CX ;
D = (C0∪C1)#CX ;
}
测试集也用立方体集合形式表示:
T(hs-a-0) = D∩H
T(hs-a-1) = D # H
其中H为信号节点h相对于外部输入的函数。为了得到标准结果形式,需要对T(hs-a-0)、T(hs-a-1)去冗余,并展开为质立方形式。
|