（计算机应用技术专业论文）二叉判定图理论研究及其应用.pdf

摘要 二叉判定图这种数据结构主要用来表示逻辑表达式，而现在人们已经研制了 一些表示方法：比如二叉判定树、真值表、卡诺图等等，但是对于这些表达方式 而言，存储空间的需要比较大，还存在着大量的冗余数据。二叉判定图则是在二 叉判定树的基础上，消除了其中的冗余结点，减少了对存储空间的需求，从而提 高了求解问题的速度。 文中比较全面地介绍了二叉判定图的基本理论。首先由二叉判定树表示的布 尔函数，引出了布尔函数的二叉判定图表示方法。之后详细的介绍了二叉判定图 的构造算法。通过对二叉判定图理论的学习和研究，我提出了利用二叉判定图对 极小碰集和约束满足问题求解的算法。 极小碰集问题是在基于模型的诊断中遇到的问题。这种方法不会因剪枝而丢 失解；而且不用求出全部的碰集，但是所求得的解却包含全部的极小碰集。 约束满足问题作为人工智能领域的研究方向，在经过几十年的研究后，目前 已经拥有了数量丰富的各种求解算法。本文给出了利用二叉判定图求约束满足问 题的算法，并编程实现了对n 皇后问题的求解。 关键词：二叉判定图极小碰集约束满足问题 a b s t r a c t b i n a r yd e c i s i o nd i a g r a m ( b d d ) a st h i sh n do f c o n s t r u c t i o no f d a t ai sm a i l yu s e d t oe x p r e s st h el o 百c a le x p r e s s i o n s o m em e a s u r e s h a v eb e e nd e v e l o p e d ，f o re x a m p l e b i n a r yd e c i s i o nt r e e ( b d t ) ，t r u t ht a b l e ，k a m a u g hm a pa n ds oo n ，h o w e v e rt h en e e do f s t o r a g es p a c ei sq u i t eb i g ，a n da l s oh a st h em a s s i v er e d u n d a n td a t a b a s e do nb d t , b d d r e d u c e st h er e q u i r e m e n to f s t o r a g es p a c eb yr e m o v i n gt h er e d u n d a n tn o d e sf r o mb d t t h u si te n h a n c e st h es p e e do f t h es o l u t i o nq u e s t i o n i nt h i sp a p e r , w ef u l l yi n t r o d u c et h eb a s i ct h e o r i e so f b d d f i r s t l yi td r a w so u tt h e e x p r e s s i o nm e a s u r e so fb b db yt h eb o o l e a n f u n c t i o nw h i c hi se x p r e s s e db yb b t l a t e r w ei n t r o d u c et h es t r u c t u r ea l g o r i t h mi nd e t a i l b yt h es t u d i e sa n dr e s e a r c h e so f b d d t h e o r i e s ，ip r e s e n tt h ea l g o r i t h mt h a tc a ns o l v et h em i n i m a lh i t t i n gs e t sa n dc o n s t r a i n t s a t i s f i e dp r o b l e m m i n i m a lh i t t i n gs e t si st h eq u e s t i o nb a s e do um o d e ld i a g n o s i s t h i sm e t h o dc a nn o t l o s es o l u t i o n sb e c a u s eo f p r u n i n ga n di ti sn o ti l e e d e dt of i n da nh i t t i n gs e t s b u tt h e s o l u t i o n sf o u n dc o n t a i na l lm i n i m a lh i t t i n gs e t s a sar e s e a r c ha s p e c to f a r t i f i c i a li n t e l l i g e n c e ，a t t e rd e c a d e so f r e s e a r c h ，b i n a r y d e c i s i o nd i a g r a m ( c s p ) h a sn u m b e r so f v a r i o u ss o l u t i o n f i n d i n ga l g o r i t h m t h i sp a p e r g i v e sc s ps o l u t i o n f i n d i n ga l g o r i t h mb yb d d ，a n dr e a l i z e snq u e e n ss o l u t i o n f i n d i n g a l g o r i t h mb yp r o g r a m m i n g k e y w o r d ：b i n a r yd e c i s i o nd i a g r a m m i n i m a lh i t t i n gs e t s b i n a r yd e c i s i o nd i a g r a m 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，二叉判定图理论研究及其应用 是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经注明 引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成 果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名： 趣。佥幽年也月一日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版 权使用规定”，同意长春理工大学保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权长春理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等 复制手段保存和汇编学位论文。 作者签名：赵垒近年鱼月彳日 指导导师签名：纽 坦2 年旦月幺日 第一章绪论 1 1 二叉判定图理论的国内外现状 布尔函数是数字与系统，计算机科学，人工智能等领域的基础，这其中的许 多问题都可表示为一系列布尔函数的运算。对于布尔函数人们已研制了一些表示 布尔函数的方法，如真值表，卡诺图，积之和的范式等，但不能满足现今复杂数 字系统的需要。为此需研究高效间接地表示运算方法。不仅软件上如此，基于对 运算速度的追求，工业上也需要相同的原理来设计可编程控制器的硬件，以获得 如人的神经反应速度。 二叉判定图( b d d ，b i n a r yd e c i s i o nd i a g r a m ) t 邓】是种被研究的有效方法，1 9 7 8 年s b a k e r s 对二叉判定图进行了系统地描述【4 】，并且指出其广泛的应用前景。二 叉判定图( b d d ) 则是在二叉判定树的基础上，消除了其中的冗余结点而得到的pj ， 从而减少了对存储空间的需求。但是，这种二叉判定图还不够完善，即任意给定 的布尔函数可以用多个不同二叉判定图来表示。这种表示的不唯一性给实现基于 二叉判定图的各种布尔操作的算法带来了很大困难。1 9 8 6 年r e b y r a n t 对二叉判 定图进行了一系列改进【6 】。b y a n t 对二叉判定图所描述的布尔函数的变量施加了固 定变量序的限制，称为有序的布尔函数可以唯一的用一个o b d d 来表示。b y a n t 还给出了化简0 b d d 的规则，并且证明了使用这种化简规则所生成的o b d d 不但 是最简的而且是唯一的。这种最简的o b d d 称为简化的o b d d ( r e d u c e do b d d 或 r o b d d ) 。如果存在两个r o b d d 同构并且有相同的变量序，那么它们必然描述 同一个布尔函数。r o b d d 和布尔函数之间的一一对应关系使得基于其上的各种 操作算法的实现变得非常简单。 二元判定图与布尔函数的其他表示方法相比，具有很多的优点： ( 1 ) 大多实用中的布尔函数都可用具有相当少结点数的二叉判定图表示： ( 2 ) 在一些限定条件下，每个布尔函数都只有一唯一表示形式； ( 3 ) 在计算机上用程序实现二叉判定图表示非常容易。 1 2 二叉判定图理论研究的目的和意义 对于二叉判定图这种数据结构而言，被广泛地用于表示各种逻辑表达式。逻 辑表达式可以有多种表示方式，如二叉判定树、真值表等等，但对于这些表示方 式而言，对存储空间需求量都比较大，其中存在大量的冗余数据。二叉判定图则 是在二叉判定树的基础上，消除了其中的冗余结点而得到的，从而减少了对存储 空间的需求。但对与一个逻辑表达式的二叉判定图构造而言，需要依赖于一个变 量顺序，通常都是构造一个逻辑表达式在给定变量顺序下的二叉判定图表示。对 同一个逻辑表达式而言，给定的变量顺序不同，得到的二叉判定图表达形式是不 同的，其中所包含的二叉判定图结点的个数也是不同的。一个好的变量顺序可以 使得该逻辑表达式的二叉判定图表示拥有较少的结点个数，从而使用较少的存储 空间。 极小碰集问题是在基于模型的诊断中遇到的问题。这类问题是与已知集合都 有交的最小的集合，通常会有很多个极小碰集。目前许多学者都对计算极小碰集 的方法进行了研究和改进，主要有h s t r e e ，h s d a g ，h s t - t r e e ，b h s t r e e ， 布尔代数方法，逻辑数组方法等。但是这些算法的缺点主要表现在：( 1 ) 因剪枝 而可能丢失正确解；( 2 ) 一般先存储所有碰集，最后还需要化简才能得出所有的 极小碰集。 目前，在求解约束满足问题时，传统的办法是利用搜索算法如回溯算法，另 一种方法是约束传播算法，也就是弧一致性算法。经过二十多年的改进，以弧一 致性算法和路径一致性算法为基础的约束传播算法已经越来越成熟和完善，在许 多领域的应用中取得了良好的效果。 利用二叉判定图计算极小碰集和求解约束满足问题，只是其应用的两个方面。 现在，二叉判定图这种数据结构被广泛的应用于c a d 、硬件设计与检验等多种领 域 6 ，”。工业上也需要相同的原理来设计可编程控制器的硬件，以获得如人的神经 反应速度。二叉判定图理论有着广泛的应用前景，有待于进一步的研究与发现。 1 3 本文主要的研究内容 在这篇论文中，我主要给出了利用二叉判定图原理计算极小碰集与求解约束 满足问题的算法。最终经过编程检验了利用二叉判定图原理解决这两个问题，具 有很多的优点。 本文的组织结构如下： 第一章是本文的绪论部分，主要介绍二叉判定图原理问题提出的背景，国内 外当前b d d 理论的发展、计算极小碰集以及求解约束满足问题的研究现状，以及 本文主要的研究工作。 第二章是b d d 和布尔函数的基础知识，主要给出了b d d 的基本概念以及 b d d 的一些常用算法，其中也讲述了变量顺序对b d d 存储空间大小的影响。 第三章给出了利用b d d 计算极小碰集的方法。 第四章给出了利用b d d 求解约束满足问题的方法。 第五章是结束语，是对本文的简要总结，并对未来的工作进行展望。 2 第二章二叉判定图的基础知识 2 1布尔函数和二叉判定图 2 1 1 相关概念和定理 在数学中，布尔函数是如下形式的函数：f ( x 1 ，x 2 ，x 。) ，带有n 个来自两元素 布尔代数( 0 ，1 ) 的布尔函数变量x j ，f 的取值也在( 0 ，1 ) 中。 对于布尔函数而言有多种表示方式，最常见的表示方式是真值表和二叉判定 树的表示方式。 定义2 1 限制变量【1 2 1 ：给定一个包含n 个变量的布尔函数f ( x l ，x 2 ，) ，把变 量x i 赋值为k ( 0 或1 ) 所得到的f 的结果，称为f 在变量x j 处的限制，记为fx i _ k ， 称x j 为限制变量。 定义2 2i f - t h e n e l s e 运算符( o p e r a t o r ) 1 3 1 ：我们用x 斗y o ，y 1 来表示i f - t h e n e l s e 运 算符( o p e r a t o r ) ，定义如下 x 寸y o ，y l = ( x a y 0 ) v ( - ，x a y l ) ( 2 1 ) 因此，x y o ，y l 当满足x 和y o 同时为真或x 为假y l 为真时为真。我们称x 为 测试表达式( t e s te x p r e s s i o n ) 。所有的运算符( o p e r a t o r ) 都可以很容易的用i f - t h e n - e l s e 运算符和常量0 、1 来表示。例如，x 表示成( x 寸0 ，1 ) ，x c ：v y 表示成 x 一( y j l ，o ) ，( y _ 0 ，1 ) 。 定义2 3 香农展式【3 j ；个含有n 个变量的布尔函数f ( x i ，x 2 ，x n ) ，在变量 x i 处可以表示为： f = - ( x i n flx ；= i ) v ( ，x i afix - 0 1 ( 2 2 ) 称上式为函数f 在变量x i 处的香农展式，把变量x j 称为函数f 的分解变量， 称fx 。= 1 为关于x i 的正伴因子，而称f ix l = o 为关于x i 的负伴因子。我们用t o x 来表示在布尔表达式t 中用0 来代替变量x ，则上述香农展示可表示为： f - - - - 3 ( i - ) f 1 x i ，t i o x i ( 2 3 ) 利用香农展式可以把布尔函数展开为一些简单函数。见下图，从图2 1 中可 以看到，根结点对应原函数f ，虚线指向的结点表示函数f f 0 x 月，实线指向的结点 表示函数t 1 i x l l 。 f i o x i 】 图2 1 展开一个结点 f 【l x l 】 更进一步，利用香农展式对一个布尔函数进行递归展开，当t 【l x i 和f i o x i 】 等于常函数1 或。时，用l 笺0 标记该结点，递归过程中止，这样最终形成一棵 二叉树，我们把这样的一棵二叉树称为该布尔函数对应的二叉判定树。因此，任 何一个布尔函数的递归香农展式都对应着一棵二叉判定树。我们把标记为0 或1 的结点称为终结点，其余的结点称为非终结点。用二叉判定树表示一个布尔函数 时，所需的存储空间随着变量数目n 呈指数增加。 例2 1 考虑布尔表达式t - ( x l 铮y 1 ) ( x 2 营y 2 ) 。如果我们按x l ，y l ，x 2 ，y 2 的顺序递 归展开香农展式，我们有 t 2 x t 斗t l , t o t o = y 1 0 ，t o o t l = y l t h 0 t 0 0 2 x 2 一t o o l ，t o o o t l l 。x 2 - - 9t 1 1 i ，t 1 1 0 t o o o = y 2 0 1 t 0 0 l = y 2 1 ，o t 1 1 0 = y 2 0 1 t n l = y 2 - - 1 ，0 由此，我们可以用一个二叉判定树来表示此表达式，如下图所示：其中虚线 表示该变量取0 值，实线表示取1 值。 图2 2 表示表达式( x t c ： y i ) ( x 2 y 2 ) 的决策树 实际上，一些香农展式它们表示的函数功能是相同的( 在b d d 中它们结点的 构造是相同的，我们称之为同构的) 。如上例当中t l l 0 和t o o o ，t l “和t o o l 。在这些表 示相同函数功能的香农展式中，可以选择一个来代替其它的。在上例中如果用t 0 0 0 代替t l l o ，用t 0 0 l 代替t m ，我们可以看到t l l 和t 0 0 表示的函数功能也是相同的。 在上例中我们合并功能重复的香农展式，得到如下展式： t 2 x 1 - - 9 t l ，t o t 0 = y l 0 ，t 0 0 t l = y l - 9 t o o ，0 t 0 0 2x 2 寸t o o l ，t o o o 0 0 2 y 2 - 90 1 t o o l2 y 2 _ l ，o 另外，二又树中的一些结点是重复表示的，如最后一层的0 ，1 结点，将这些 标记相同的结点合并后并不改变所表示的布尔函数，而此时树就变成了图。这种 存储布尔函数的图的数据结构就被称为二叉判定图( b d d ) 。 图2 3 用来表示表达式( 。l 营y 1 ) “。2 铮y 2 ) 的b d d 定义2 4 - - - x 判定图( b d d ) 【4 j ：二叉判定图( b i n a r yd e c i s i o nd i a g r a m ) 是一个有 限个结点的有向无环图g = ，其中v 是g 中所有结点的集合，e 是g 中所有 边的集合。v 中的结点分为终结结点( 或称为端结点，用方框表示) 和非终结结 点( 或称为非端结点、中间结点，用圆框表示) 。每个端结点v ，用0 或1 标识，无 射出边；每个非端结点v 。用变量v a r ( v 。) 标识，并且有两条射出边，一条指向h i g h ( v 。) 的t h e n 一边( 用实线表示，v a r ( v 。) 被赋值1 ) ，另一条指向l o w ( v 。) 的e l s e 一边( 用虚 线表示，v a r ( v 。) 被赋值0 ) 。 图2 3 是用布尔函数f 兰( x i y 1 ) ( x 2 营y 2 ) 的b d d 表示，与图2 2 所采用的二 叉判定树相比，只用了8 个结点。从图中可以看出，从b d d 根结点到一个端结点 的一条轨迹就对应着变量的一组赋值，由该分支的端结点所标识的值就是变量在 这组赋值下所对应的函数的值。通常，在构造一个逻辑公式或布尔函数的b d d 之 前，我们都要给出一个变量顺序，构造的b d d 是给定变量顺序的b d d ，我们把 这样的b d d 称为有序的二叉判定图( o b d d ，o r d e r e db i n a r yd e c i s i o nd i a g r a m ) 。如 果在构造o b d d 的过程中所有的同构结点都被共享，只保留一个同构结点，并且 所有冗余测试结点都去掉了，那么这样的o b d d 我们称为r o b d d ( r e d u c e d o r d e r e db i n a r yd e c i s i o nd i a g r a m ) 。今后，如果没有特殊说明，我们所说的b d d 都是指r o b d d 。 定义2 5 有序二叉判定图( o b d d ) 【6 】：一个b d dg = ，如果在变量集合 上满足全序关系 ，并且满足下述条件：对任意非端结点u v ，如果v e v 是u 的 l o w 子结点或者h i 曲予结点，且v 也是非端结点，那么必有v a r ( u ) v a r ( v ) 。 定义2 6 简化有序的二叉判定图( r o b d d ) f 6 】：如果一个o b d d 满足： ( 唯一性) 不存在这样的两个不同结点，它们具有同样的变量名和同样的l o w 、 h i 曲子结点，也就是说： 如果v a r ( u ) = v a r ( v ) ，l o w ( u ) = l o w ( v ) ，h i g h ( u ) ：h i g h ( v ) 则一定有u = 、， ( 无冗余测试结点) 不存在这样的变量结点u ，其l o w 、h i g h 子结点是同构的， 即： l o w ( u ) # h i g h ( u ) 我们称这样的o b d d 为r o b d d 。 唯一性无冗余测试结点 图2 4r o b d d 需满足的两个条件 定理2 1 1 12 】：给定一个布尔函数，有唯一的r o b d d 与之对应。 另外我们还能得到下面结论： 1 两个布尔函数的b d d 是同构的，当且仅当这两个布尔函数等价。 2 一个布尔函数是可满足的，当且仅当它的b d d 表示的一个端结点为l 。 3 一个布尔函数是永真的，当且仅当它的b d d 表示只有一个端结点，并且 该端结点为1 。 4 一个布尔函数不含变量x ，则它的b d d 表示不含v a r ( u ) - - x 的非端结点。 6 b 图2 5 同一个布尔函数f = - a l b l + a 2 b 2 + a 3 b 3 在不同 变量顺序下得到的不同的b d d 表示形式 其中( a ) 中变量的顺序是a l b l a 2 b 2 a 3 b 3 ，非终结结点的个数是6 个：而在 ( b ) 中变量的顺序是a l a 2 a a b l b 2 b 3 ，非终结结点的个数变成1 4 。 2 1 2 变量顺序对二叉判定图大小的影响 尽管b d d 是表示布尔函数的有效方法，但是表示一个布尔函数的b d d 的结 构和空间复杂度依赖于变量的顺序。例如： 例2 2 布尔函数f = a i b l + a 2 b 2 + a 3 b 3 在不同的变量顺序a l b l a 2 b 2 a 3 b 3 和a l a 2 a 3 b 1 b 2 b 3 下的b d d 表示，如图2 5 所示。 可见，在构造b d d 的过程中，选择一个好的变量序，也会使得b d d 结点的 个数减少，从而降低其存储的空间复杂度。显然选择一个合适的变量顺序对于存 储空间的要求和算法执行效率有很大的影响。在最坏的情况下，b d d 的大小( 即非 终结结点的个数) 会随着变量数的增加而呈指数增长。然而如果使用合适的变量顺 序我们可以使用b d d 来表示许多用其他方法不能表示的布尔函数。 近些年来，人们对b d d 的排序进行了大量的研究，希望对一个布尔函数可以 找到一个合适的变量顺序，以减少b d d 的存储空间。目前，对b d d 排序的方法 大致可以分为三种类型：第一种是启发式变量排序o j ；第二种是动态变量排序 【l l 】；第三种是最优化的变量排序法1 1 2 , 1 3 】。第三类方法的排序结果比较好，但时间 复杂度是o ( n 3 3 “) ，其中n 是变量的个数。这种方法只适用于变量个数较少的系统。 动态排序是指对已建立好的b d d 的变量次序进行调整以减少b d d 的规模。该方 法往往能找到一个更好的变量次序。目前的b d d 包都应用了这种方法。本文的目 的不在于找到一个优化的变量序，所以这里对于各种排序方法不再详细说明。 7 2 2b d d 的基本算法 目前，比较成熟的b d d 包主要有两个b u d d y t 3 1 和c u d d ”l 。为了适用于各种应 用领域，在b d d 包中，通常都采用通过递归调用香农展式来构造一个布尔函数在 给定变量顺序下的r o b d d 。在构造这种r o b d d 的时候，又存在两种方式：一 种方式是先构造函数的o b d d ，然后再将其化简：另外一种更可行的方式是在构 造过程中直接构造r o b d d 。而这种构造方式又可以采用下面两种方法： 2 2 1 一般的构造算法。1 这种方法是b d d 包中通常采用的构造b d d 的方法。该方法的前提条件是已 知需要构造的布尔函数的表达式。构造算法思想是先构造出该布尔函数对应的二 叉判定树，然后再合并冗余结点从而得到其b d d 的表示形式。 为了保证构造的o b d d 是简化的o b d d 。在构造过程中，所有的变量都将用 它们的变量序来表示，而常量0 和1 被表示为n + 1 ( n 为变量个数) 。每个结点将用 一个数字来唯一标识它们。这样r o b d d 中任何一个结点u 都被映射为一个三元 组：v a r ( u ) - - i ，l o w ( u ) = l ，h i g h ( u ) = h 。i 为结点u 中存储的变量，l 为标识结点l o w ( u ) 的数字，h 为标识结点h i 曲( u ) 的数字。这样r o b d d 可以被存储到一张表t 巾：u - - ( i ，l ，h ) 。 例2 3 布尔函数仁( x l 营x 2 ) ( x 3 曹】【4 ) 在给定的变量顺序：x t x 2 x 3 x 4 下的 r o b d d 表示如图2 6 所示 1 m k 函数 为了保证o b d d 在构造的过程中已经是简化的，必须在构造的过程中检测所 有的三元组( i ，l ，h ) ，看是否存在这样的结点u ，使得v a r ( u ) = i ，l o w ( u ) = l ，h i g h ( u ) = h ， 与正要建立的结点相同。如果存在，则说明正要建立的结点已经存在，无需再新 建，只需将该结点返回即可。否则，需要建立新的结点。为了实现这些操作，我 们假定存在一个表h ，它将变量序为i ，l o w 和h i 曲结点分别为l 和h 的三元组( i ，l ，h ) 映射为结点u 。表h 可以看作是表格t 的逆表，对于任意的结点u ，有t ( u ) = ( i ，l h ) 当且仅当h ( i ，l ，h ) - - u 。对这两个表的操作如下： t ：u 一( i ，l ，h ) i n i t ( t 1 初始化表t 仅有终结点0 和1 u - - a d d ( t , i ，1 ，h ) 根据( i ，1 ，h ) 值在表t 中加入一个新的结点 v a r ( u ) ，l o w ( u ) ，h i g h ( u )在表t 中查询结点u 的各项属性 h ：( i ，l ，h ) 一u i n i t ( h )初始化表h 为空表 b m e m b e r ( h ，i ，l ，h ) 在表h 中查找是否存在这样的三元组( i ，l ，h ) u l o o k u p ( h ，i ，l h ) 如果找到( i ，l ，h ) 对应表项，返回相应结点u 的标识 i n s e r t ( h ，i ，l ，i l ，u ) 否则，将( i ，l ，h ) 和与之对应的u 作为一项插入表格h 中 m k 函数需要对这两个表t 、h 进行操作。算法如下： m ki t , h l ( i ，l 舢 l ：i f l - - ht h e nr e t u r nl 2 ：e l s ei f m e m b e r ( h ，i ，1 ，l a ) t h e n 3 ：r e t t l r l ll o o k u p ( h ，i ，l ，h ) 4 ：e l s eu p a d d ( t ，i ，l ，h ) 5 ： i n s e r t ( h ，i ，l ，h ，u ) 6 ：r e t u r n u 如果所有的结点都是依靠m k 函数构造出来的，那么就可以保证该o b d d 是 简化的o b d d ( r o b d d ) ，如图2 6 所示： 7 表2 - 1 ：u 一( i ，l 山) uv a ri o w h i g h o5 15 2410 34o l 4323 524o 62 o4 7 l5 6 图2 6 布尔函数f - - ( x l 曹x 2 ) ( 。3 x 4 ) 在给定的变量顺序x 1 x 2 x 3 n t h e n 9 3 ：i f ti sf a l s et h e nr e t u r n0e l s er e t u ml 4 ：e l s ev o w - - b u i l d ( t 0 x i ，i + 1 ) 5 ： v l - b u i l d ( t 【1 x 1 ，i + 1 ) 6 ：r e t u r nm k ( i ，v 0 ，v 0 7 ：e n db u i l d 8 ：r e t l r 1b u i l d ( t ，1 ) 该算法是在己知变量顺序x 1 x 2 ( x 1 呻t 1 , t2 ) = x 1 一t 1 t l , t 2 t 2 ( 2 4 ) 如果我们从两个布尔表达式t 1 和t 2 相对应的r o b d d 的根结点开始构造 h t 2 的r o b d d ，只需要递归的构造其l o w 和h i g h 分支结点，并将它们作为新 的根结点继续调用上边的方法来构造即可。直到l o w 和h i 曲分支结点都是0 结点 或1 结点中的一个结点。同样的，为了保证得到的结果是一个简化的 o b d d ( r o b d d ) ，在生成结点的过程中，我们同样调用了m k 函数。 1 0 b u i l d ( x l x 2 ) v x 3 ，1 ) d 。入，f b u i l d ( 0 亡* x 2 ) v x 3 ，2 )b u - l d ( 1 c ： x 2 ) v x 3 ，2 ) i 口 ( b ) 4 、 b u i l d ( 1 铮1 ) v l 4 ) ( d ) ( e ) ( f )( g ) 图2 7 调用b u i l d 函数构造布尔表达式( 。l 营x 2 ) v x 3 的r o b d d ( a ) 调用函数b u i l d 的过程树。( b ) 函数调用b u i l d ( 0 o ) v x 3 ，3 ) 执行之后得到 的r o b d d 。( c ) 函数调用b u i l d ( 0 1 ) v x 3 ，3 ) 执行之后得到的r o b d d 。( d ) 函 数调用b u i l d ( 0 x 2 ) v x 3 ，2 ) 执行之后得到的r o b d d 。( e ) 函数调用 b u i l d ( 1 0 ) v x 3 ，3 ) 和b u i l d ( 1 c ，1 ) v x 3 ，3 ) 执行之后得到的r o b d d 。( f ) 函数调 用b u i l d ( 1 营x 2 ) v x 3 ，2 ) 执行之后得到的r o b d d 。( g ) 最终的结果。 2 2 2 深度优先b o o 构造算法 这种方法不必先将布尔函数表示成二叉判定树，然后再将它转化为b d d ，而是 直接从原子公式中构建b d d 。构建的算法不止一种。本部分主要介绍b r a c e 在1 9 9 0 年提出的深度优先的构造b d d 算法。 定义2 7 i t e 算子【2 l ：给定三个布尔函数f ，g ，h ，i t e 算子定义为： i t e ( f , g h ) = f g + ( 一f ) h ( 2 5 ) i t e 运算可以实现任意的布尔函数，所有一元和二元逻辑运算都可以用i t e 算子 来实现。 表2 2 用i t e 算子表示了两个变量所有可能的二元逻辑运算 编号布尔运算子表达式等价形式 集 looo 2 a n d ( f , g ) f g i t e ( f , g o ) 3f g f ( 1 g ) i t e ( f , 一g o ) 4fff 5f g ( - 1 f ) gi t e ( f , 0 ，g ) 6ggg 7 x o r ( f , g ) f o g i t e ( f , 一g g ) 8 o r ( f , g 1 f + g i t e ( f , 1 ，g ) 9 n o r ( f , a_ 1 口+ g )i t e ( f , 0 ，g ) l o x n o r ( f , g )，( f e g g )i t e ( f , g g ) 1 1 n o t ( g ) 1 g i t e ( g o ，1 ) 1 2f g f + ( 1 g )i t e ( f , 1 ，一g ) 1 3 n o t ( f ) 1 f i r e ( f , 0 ，1 ) 1 4 f g ( 1 f ) + gi t e ( f , g1 ) 1 5 n a i l d ( f ，g )- 1 ( f g )i t e ( f , 一g 1 ) 1 6ll1 定义2 8 顶层变量【2 】：一个函数f 的顶层变量就是指于这个函数根结点相关 1 2 联的变量。 用香农展式可以递归的计算一个函数的真值，下面的递归公式用来计算用 b d d 表示的f ，g h 的i t e ( f , g ；h ) 的值。假定v 是f , c h 的顶层变量，并且另 z = i t e ( f , g h ) 。在下面z v 表示把函数z 中变量v 赋值为l ，表示把函数z 中变量v 赋值为o ，则有： z = v z v + ( 1 v ) z ( ，v ) = v ( f g + ( _ 1 f ) h ) v + ( 1 v ) ( f g + ( ，f ) h ) ( ，v ) = v ( f v g v + ( 1 f ) v s o 十( 1 v ) ( f ( ，) g ( 1 v ) + ( 1 f ) ( ，v ) h ( 1 v ) ) = i t e ( v , i t e ( f v ，g v ，h ，) ，i t e ( f ( ，) ，g ( ，) ，h ( 。) ) ) = ( v ，i t e ( f v ，g v ，h v ) ，i t e ( f ( 1 v ) g 卜v ) ，h ( 1 v 】) ) 递归终止的条件是i t e ( 1 ，f ，g ) 2i t e ( 0 ，g f ) = i $ l ，o ) 2 f 。 我们用i t e 运算的方法，直接从原子公式的b d d 出发，逐级进行各种逻辑运 算，构造出对应的b d d 形式，从而得到最终结果的b d d 形式，其通用性比较好。 其具体算法描述如下： i t e ( f , g h ) i f ( t e r m i n a lc a s e ) r e t u r nr e s u l t ； e l s ei f ( c o m p u t e t a b l eh a se n t r y ( f , g h ) ) r e t u r nr e s u l t ； e l s e l e tvb et h et o pv a r i a b l eo f g h ) ； t = i t e ( f ，c v ，h o ； e = i t e ( f ，) ，g ( 卅，h 一) ) ； i f te q u a l ser c t u r ul r = f i n do ra d du n i q u e _ t a b l e ( v , t , e ) ； i n s e r t _ c o m p u t e d _ _ t a b l e ( f , g h ) ，r ) ； r e t u m r ： ) 假定f m do ra d du n i q u e _ t a b l e ( v , t , e ) 和i n s e r t _ c o m p u t e d _ t a b l e 的过程可以在常 量时间内完成，并且处理f ：q h 每个变量结点时，我们至多调用一次i t c 运算。假 定f g h 中结点的个数分别为ifi ，igi ，ihi ，则该算法的时间复杂度为 o ( ifi 术igi 车ih1 ) 。 例2 5 令f = a + b ，g = a e ，h _ b + d ；i t e ( f ，g t t ) = a c + ( 一a ) ( 一b ) d 。在给定变量顺序 a b c jt h e nr e t u r nu e l s ei f v a t ( u ) jt h e nr e t u nm k ( v a r ( u ) ，r e s ( 1 0 w ( u ) ) , r e s ( h i 曲( u ) ) ) 如果赋0 值则对当前结点的l o w 结点调用r e s 操作。著返回处理结果。 e l s ei f b = 0t h e nr e t u r nr e s ( 1 0 w ( u ) ) 如果赋1 值则对当前结点的h i 曲结点调用r e s 操作。并返彭回处理结果。 e l s er e t b r l lr e s ( i l i g h ( u ) ) e n dr e s r e t u r nr e s ( u ) 为了确保得到的o b d d 是r o b d d ，在算法中调用了m k 函数a 例2 6 给定布尔表达式( x l c ，x 2 ) v x 3 的r o b d d 如图2 9 ( a ) ，求得它在限定 o x f l 下的r o b d d 如图2 9 ( b ) 。 在图2 9 中可以看出，对变量x 2 赋0 值后得到的r o b d d ，实际上是通过把 原来r o b d d 中指向结点x 2 的边改为指向结点x 2 的l o w 分支。相反，如果对变量 x 2 赋l 值，则通过把原来r o b d d 中指向结点x 2 的边改为指向结点x 2 的h i 曲分 支，从而得到新的r o b d d 。 a b 图2 9 对变量x 2 赋1 值，应用r e c s t r i c t 算法前后表达式( x l 营x 2 ) v 韵的b d d 表示 2 a n y s a t 、a l l s a t 算法 a n y s a t 算法找n - 个使该r o b d d 表示的布尔表达式为1 的解。该算法是利 用深度优先搜索一条从根结点到结点1 的一条路径。一些没出现在此路径中的变 量他们可以取任意的值。 a t l s a t 算法找到所有使该r o b d d 表示的布尔表达式为l 的解。一些没出现 在解路径中的变量他们可以取任意的值。 a n y s m ( u ) i f u = 0 t h e n e r r o r e l s e i f u = 1 t h e nr e t u r n 【】 e l s ei f l o w ( u ) = ot h e nr e t u r n 【x 。砌) 一1 ，a n y s a t ( h i g h ( u ) ) 】 e l s er e t u m x 州u ) 一0 ，a n y s a t ( 1 0 w ( u ) ) 】 a l l s a t ( u ) i f u ；0 t h e l lr e t u r n o e l s ei f u = lt h e nr e t u r n e l s er e t u r n 一 2 4 小结 在本章我们主要介绍了b d d 的基本理论，以及如何由一个布尔表达式构造一 个b d d 。还有b d d 的一些算法。在以后的章节中我们还会用到这些算法来解决 问题。 1 6 第三章用r o b d d 计算极小碰集 3 1 模型诊断的相关概念 定义3 1 【1 4 】一个系统由s d c o m p so