logo资料库

有序二叉决策图（OBDD）及其应用.ppt

发布时间：2022-06-12 发布人：admin 分类：说明书 资料大小：3.03M 资料格式：ppt 举报 版权申诉
第1页 / 共48页
第2页 / 共48页
第3页 / 共48页
第4页 / 共48页
第5页 / 共48页
第6页 / 共48页
第7页 / 共48页
第8页 / 共48页
资料共48页，剩余部分请下载后查看
    有序二叉决策图（OBDD）及其应用 古天龙 2014全国离散数学年会 1 2022-6-12
    • （1）布尔表达式及其表示 • （2）有序二叉决策图（OBDD） • （3）符号模型检验 2014全国离散数学年会 2 2022-6-12
    （1）布尔表达式及其表示 布尔代数 → 布尔表达式 → 布尔函数 → 二叉决策图 布尔代数是英国数学家George Boole（乔治布尔）十九世纪提出来的将古典逻 辑推理转化为抽象符号代数计算的技术。布尔代数是计算技术和自动化技术中逻 辑设计的数学基础，因此布尔代数也称为逻辑代数。 布尔代数 对于非空集合B（B中至少包含两个不同元素），以及集合B上的二元运 算“”和“+”、一元运算“”，集合B中的元素a，b，cB，称满足下述条件的 多元组(B, +, , )为一个布尔代数： 交换律 ① ab =ba ; ② a+b = b+a . 分配律 ③ a (b+c) = (ab)+(ac) ; ④ a+(bc) = (a+b)(a+c). 同一律 ⑤ 二元运算“+”存在单位元，称为布尔代数的零元，即存在 0B ，使得任意aB，有a+0 = a ; ⑥ 二元运算“”存在单位元，称为布尔代数的 单位元，即存在1B，使得任意aB，有a1=a . 互补律 对任意aB，存在aB，满足：⑦ aa=0; ⑧ a+a=1. 2014全国离散数学年会 3 2022-6-12
    （1）布尔表达式及其表示 在布尔代数B中，元素aB所对应的aB称为元素a的补元，用来表示B中任意元 素的符号称为布尔变量或者变元，而B中确定的元素称为布尔常元或者常量。 二值逻辑系统是最简单的二元素布尔代数B，它是在B = {0, 1}上定义二元运算“” 和“+”、以及一元运算“”的布尔代数（B, +, , ），该布尔代数B也称为（二值） 开关代数，其中，二元运算分别为“与”/“合取”、“或”/“析取”、“非”。 在n重笛卡尔积Bn（B={0,1}）上，对于任何(a1, a2, …,an)，(b1, b2, …, bn)  Bn，这 里ai , bi{0,1}（i = 1,2,…,n），定义如下运算： (a1, a2, …, an)  (b1, b2, …, bn) = (a1b1, a2b2, …, anbn); (a1, a2, …, an) + (b1, b2, …, bn) = (a1+b1, a2+b2, …,an+bn); (a1, a2, …, an) = (a1, a2, …, an). 不难证明：(Bn, +, , )是布尔代数，零元为(0, 0, …,0)，单位元为(1, 1, …,1)，此布 尔代数也称为(n维)矢量开关代数。 2014全国离散数学年会 4 2022-6-12
    （1）布尔表达式及其表示 布尔表达式是布尔代数上按照一定规则形成的符号串。它是逻辑演算、逻辑电路 综合等的有效形式化符号描述。 布尔表达式 对于布尔代数(B, +, , )，令x1, x2,, xn是B 上的n个变量，用 “”“+”“”把B的元素和变量连接起来的表达式就是布尔表达式。对于布尔 代数(B, +, , )，布尔表达式定义为由如下规则构成的有限字符串： ① B中任意一个元素是一个布尔表达式； ② B上的任意一个变元是一个布尔表达式； ③ 若x和y是布尔表达式，则xy、x+y和x也是布尔表达式； ④ 只有有限次运用①~③所产生符号串是布尔表达式。 n元布尔表达式 对于布尔代数(B, +, , )，一个含有n个互异变量的布尔表 达式， 称为含有n元的布尔表达式，简称为n元布尔表达式，记为P(x1, x2, …, xn)，其中x1, x2, …, xn为变量。 约定: 一元运算“”的优先级最高、其次是“”、最低的是“+”，这样布尔表 达式中可以省去一些括号。 2014全国离散数学年会 5 2022-6-12
    （1）布尔表达式及其表示 表达式的值 对于布尔代数(B, +, , )上的n元布尔表达式P(x1, x2,…, xn)，对 变量xi（i=1,2,…, n）在B中取值，并代入布尔表达式P(x1, x2, …, xn)，即对 变量赋值，所计算出的结果，称为n元布尔表达式P(x1, x2, …, xn)的值。 例如，对于布尔代数({0, 1}, +, ,  )上的布尔表达式 (x+y)(x+y)(y+z)，如果变量 的一组赋值为x = 1, y = 0, z =1，那么便可求得(1+0)(1+0) (0+1) = 110 = 0. 布尔表达式等价 对于布尔代数(B, +, , )上的n元布尔表达式P(x1, x2,…, xn) 和Q(x1, x2,…, xn) ，如果对于n个变量的任意赋值，这两个表达式的值都相 同，则称这两个布尔表达式等价，记为P(x1, x2,…, xn) = Q(x1, x2,…, xn) 。 我们可以利用布尔代数的一些恒等式（性质），将一个布尔表达式简化成为另外 一个简单的等价形式。 2014全国离散数学年会 6 2022-6-12
    （1）布尔表达式及其表示 对于布尔代数(B, +, ,  )上的任何一个布尔表达式P(x1, x2, …, xn)，由于运 算“”、“+”和“”在B上的封闭性，所以对于任何n元组(x1, x2, …, xn) ， xiB（i=1,2,…,n）的一组赋值就可以得到布尔表达式P(x1, x2, …, xn)对应 的一个值，这个值必属于B。由此可见，我们可以说布尔表达式P(x1, x2, …, xn)确定了一个由Bn到B的函数。 布尔函数 对于布尔代数（B, +, , )，如果一个从Bn到B的映射能够用(B, +, , )上的n元布尔表达式来表示，那么这个映射称为布尔函数。 对于布尔代数({0,1}, +, , )，右表所给 出的映射f  Bn  B，可以用B上的布 尔表达式 f (x, y, z) = x (y+z) 表示，所 以f 是布尔函数。 x y z 0 0 0 0 0 1 0 1 0 0 1 1 f 0 0 0 0 x y z 1 0 0 1 0 1 1 1 0 1 1 1 f 1 0 1 1 2014全国离散数学年会 7 2022-6-12
    （1）布尔表达式及其表示 对于布尔代数B，从Bn  B的映射不一定都能用B上的布尔表达式来表示 出来。换言之，任意映射f  Bn B不一定都是布尔函数。但是，对于布尔 代数({0,1}, +, , )，从{0,1}n到{0,1}的任一映射都可用({0,1}, +, , )上的布 尔表达式来表示出来，反之亦然。 定理 对于布尔代数({0,1}, +, , )，任何一个从{0,1}n到{0,1}的映射都是布 尔函数。 对于从{0,1}n到{0,1}的n元布尔函数f (x1, x2, …, xn)，若对其中第i个分量xi 取值1或0， 则可得到{0,1}n1到{0,1}的布尔函数f (x1, …, xi1, 1, xi+1, …,xn)或f (x1, …, xi1, 0, xi+1, …,xn)，称之为输入模式(x1, …, xi1, 1, xi+1, …,xn)或(x1, …, xi1, 0, xi+1, …,xn)下的 布尔函数，并分别记作fxi或fxi 。 类似地，从{0,1} n到{0,1}的布尔函数f (x1, x2, …, xn)，若对其中k（kn）个分量取 值则可得到{0,1}nk到{0,1}的布尔函数。例如，输入模式(x1, 0, 1, x4, 1, x6, …, xn)下 的布尔函数为f (x1, 0, 1, x4, 1, x6, …, xn) ，记为fx2 x3 x5 。 布尔函数的函数族 对于从{0,1}n到{0,1}的布尔函数f (x1, x2, …, xn)，在不同输入 模式下的布尔函数形成一个布尔函数集合，称为该布尔函数的函数族，并记为 f (x1, x2, …, xn)。 2014全国离散数学年会 8 2022-6-12
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料