《第十二讲：布尔代数》由会员分享，可在线阅读，更多相关《第十二讲：布尔代数（37页珍藏版）》请在金锄头文库上搜索。
1、2012年3月31日 第十二讲：布尔代数 离 散 数 学 Discrete Mathematics 南京大学计算机科学与技术系 前 情 提 要 2 前情提要 子 格 格同态 分配格 有补格 布尔代数引论 本讲主要内容 3 本讲主要内容 布 尔 格 布尔代数 布尔代数的性质 布尔代数的同态 有限布尔代数 数字逻辑电路设计* 布尔格 4 布尔格 定义（布尔格布尔格）：如果一个格为有补分配 格，则称其为布尔格或布尔代数 （Boolean algebra），可记为 , 集合代数 , 是布尔格 逻辑代数 , , 是布尔格 布尔格的性质 5 布尔格的性质 观察集合代数系统 , ： 集合交运算满足交换、结合
2、律 集合并运算满足交换、结合律 集合交与并运算相互满足吸收律（上述三点此为格） 集合交与并运算相互满足分配律，因此是分配格 定义()上的关系， = , 即为集合包含 关系，是偏序，与分别为全下界和全上界，为有界格 ， = 即为唯一的补元，故为布尔格 布尔代数系统 6 布尔代数系统 布尔代数 , 是代数系统，其中和是两 个二元运算，是一元运算，, 是零元运算 （常量），且满足下列系统公理系统公理： 和满足交换律交换律：, = , = 对 ，对均满足分配律分配律： , , ( ) = ( ) ( ), ( ) = ( ) ( ) ,分别是和的单位元单位元：, = , = 和满足补元律补元律：: (
3、 ) = , ( ) = 布尔代数系统（续） 7 事实：布尔代数系统 , 即有补 分配格 , 证明（布尔代数与布尔格等价布尔代数与布尔格等价）： 引理引理1 1（,分别为分别为和和的零元的零元）： 证 明 ：证 明 ： , = ( ) = ( ) ( ) = ( ) = = , = ( ) = ( ) ( ) = ( ) = = 布尔代数系统 布尔代数系统（续） 8 事实：布尔代数系统 , 即有补分 配格 , 引理引理2 2（含补含补同一性同一性）： , , = 且 = = 证明：证明：由前提可得( ) ( ) = ( ) ( ) = = = 布尔代数系统 布尔代数系统（续） 9 事实：布尔代
4、数系统 , 即有补分 配格 , 证明布尔代数系统满足吸收律： ( ) = ( ) ( ) = ( ) = = ( ) = ( ) ( ) = ( ) = = （由由引理引理1 1： = , = ） 布尔代数系统 布尔代数系统（续） 10 事实：布尔代数系统 , 即有补分 配格 , 证明布尔代数系统满足结合律： 注意：注意： = = 且 = = ( ) 由引理由引理2： ( ) = ( ) ；同理可证满足结合律 布尔代数系统 布尔代数系统（续） 11 事实：布尔代数系统 , 即有补分 配格 , 以上证明了布尔代数系统 , 是格 格导出的代数系统为 , ，故二元运算“” 即为 ，“”即为 由布尔代
5、数系统公理中的单位元公理及引理1可知， 与即为全下界和全上界，故即为求补运算 布尔代数系统 布尔代数的性质 12 布尔代数的性质 布尔代数的性质 13 布尔代数的性质 布尔代数的同态 14 布尔代数的同态 布尔代数的同态（续） 15 布尔代数的同态 布尔代数的同态（续） 16 布尔代数的同态 有限布尔代数 17 有限布尔代数 定义（格中的原子格中的原子）：设是格，中有最小元 （全下界），给定元素 ，若 有： = 则称是中的原子(即覆盖最小元的那些元素) 有限布尔代数（续） 18 有限布尔代数 定理：设,是格中的原子，若 则 = 证明：证明：假设 0，注意： 且 ，由 原子的定义： = ， =
6、， = ，矛盾矛盾 有限布尔代数的表示定理 19 有限布尔代数 定理（有限布尔代数表示定理有限布尔代数表示定理）：设任意有限布 尔代数中全体原子构成的集合为，则： () 即 , , 有限布尔代数的表示定理（续） 20 有限布尔代数 定理（有限布尔代数表示定理有限布尔代数表示定理）：设任意有限布 尔代数中全体原子构成的集合为，则： , , 推论1（有限布尔代数的基数有限布尔代数的基数）：任何有限布尔 代数的基数为2， 有限布尔代数的表示定理（续） 21 有限布尔代数 推论2（有限布尔代数的有限布尔代数的同构性同构性）：任何等势的 有限布尔代数皆同构 最小的几个有限布尔代数： 布尔代数与数字逻辑电
7、路设计* 与含个元素的集合的幂集代数系统同构的布尔代数 记为。逻辑代数逻辑代数系统是=, , 的每一个元素可以看做一个长度为的二进字符串 一个有个输入、一个输出的逻辑电路对应于一个用 含个布尔变量的布尔代数表达式定义的布尔函数 1 1, 也可以看作 在确定表示该函数的布尔表达式后，很容易用门电路 元件搭出所需要的逻辑电路 因此，关键问题是如何确定所需的布尔表达式，并将 其化为最简形式 22 布尔代数与数字逻辑电路设计 一个逻辑电路设计的例子 举重比赛中三个裁判中两个或者两个以上判定为成功则 该次成绩有效，设计一个电子打分器，输出一个结果： “成功”或“失败” 布尔函数： , = 1 iff.
8、,中至少有两个为1 x z y 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 f(x,y,z) 0 0 0 1 0 1 1 1 相应的布尔表达式相应的布尔表达式 ()() 23 布尔代数与数字逻辑电路设计 基本逻辑元件 x y xy “或”门 x y xy “与”门 x x 反相器（“非”门） 24 布尔代数与数字逻辑电路设计 电路设计 相应的相应的布尔表达式布尔表达式 ( )()()() x y z x y z f(x,y,z) 25 布尔代数与数字逻辑电路设计 过于复杂 卡诺图： = 2 基本位置 : 2 1 00 01 10 11 y x
9、 x y xy xy xy xy , = ( ) x y f(x,y) 0 0 1 1 0 1 0 1 1 1 0 0 y y x x 1 0 0 1 26 布尔代数与数字逻辑电路设计 用卡诺图化简布尔表达式 : 2 1 , = ( ) x y f(x,y) 0 0 1 1 0 1 0 1 1 1 1 0 y y x x 1 1 0 1 , = 27 布尔代数与数字逻辑电路设计 基本位置 00 01 10 11 y x x y xy xy xy xy 卡诺图： = 3 00 01 10 11 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0
10、 x x xyz xyz xyz xyz xyz xyz xyz xyz yz yz yz yz y y z z 28 布尔代数与数字逻辑电路设计 化简三个变量的布尔表达式 x z y 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 f(x,y,z) 1 0 1 0 1 0 1 1 布尔表达式布尔表达式 ()() x x yz yz yz yz 1 1 1 1 1 0 0 0 z () 29 布尔代数与数字逻辑电路设计 回归举重裁判的问题 x z y 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 f(x,y,z) 0 0 0 1 0 1 1 1 x x yz yz yz yz 0 0 1 0 1 0 1 1 简化后的简化后的表达式表达式 ()()() 30 布尔代数与数字逻辑电路设计 改进后的电路设计 x y z f(x,y,z) 31 布尔代数与数字逻辑电路设计 简化后的简化后的表达式表达式 ()()() 布尔代数与信息论* 信息是什么？信息是什么？ 信息是可以在在决策中消除不确定性的数据信息是可以在在决策中消除不确定性的数据 信息量的大小与何有关？信息量的大小与何有关？ 与它的不确定性有关与它的不确定性有关 如何度量信息？如何度量信息？ 将决策域确定为将决策域确定为,中的某一个，
