布尔代数与格PPT精选课件

《布尔代数与格PPT精选课件》由会员分享，可在线阅读，更多相关《布尔代数与格PPT精选课件（57页珍藏版）》请在金锄头文库上搜索。

1、布尔代数与格 离散数学 代数结构 1 回顾 偏序关系偏序集与哈斯图偏序集中的特殊元素特殊元素的性质偏序格 2 提要 布尔函数代数系统与布尔代数作为有补分配格的布尔代数布尔代数与逻辑电路卡诺图与逻辑电路的化简 3 一个逻辑电路设计的例子 举重比赛中三个裁判中两个或者两个以上判定为成功则该次成绩有效 设计一个电子打分器 输出一个结果 成功 或 失败 布尔函数 f x y z 1iff x y z至少有两个为1 相应的布尔表达式 x y z x y z x y z x y z 4 集合 0 1 上的运算 令B 0 1 取值范围为B的变元称为布尔变元 x B 布尔和1 1 1 1 0 1 0 1 1

2、0 0 0布尔积1 1 1 1 0 0 0 1 0 0 0 0补0 1 1 0 5 布尔函数 Bn x1 xn xi B i 1 n 函数f Bn B称为n度布尔函数f x y z y z x z x y 总共有多少个不同的n度布尔函数 6 布尔函数上的运算 布尔和 f g x1 xn f x1 xn g x1 xn 布尔积 fg x1 xn f x1 xn g x1 xn 补函数f x1 xn f x1 xn 7 布尔函数 f x y z y z x z x y 8 回顾 命题表达式的主析取范式 求 p q r的主析取范式 p r q r p q r 析取范式 p q r p q r p q

3、 r p q r p q r p q r p q r p q r 001011100111 p r p q q r p q r p q r q r p q r p q r 9 布尔恒等式 1 10 布尔恒等式 2 11 代数系统 运算的定义 函数 An A称为A上的n元运算 举例 利用普通四则运算定义实数集上的二元运算 x y x y xy则 2 3 1 0 5 0 7 0 85对于A上的n元运算 An A 若B A 且 B B 则称该运算 在集合B上封闭 集合A 1 2 3 10 gcd封闭 lcm则否 12 代数系统 一个代数系统一个非空集合 元素可以是任何对象 有一个或者若干个运算 上述

4、运算在上述集合上封闭记法 S 例子 整数集与普通加法 Z 13 布尔代数的抽象定义 布尔代数 特殊的代数系统 包含特殊元素0和1的集合B集合B上的二元运算 和 一元运算 x y z B 下列性质成立 14 布尔代数举例 0 1 0 1 为布尔代数A的幂集也构成一个布尔代数 A A Bn 0 0 1 1 构成布尔代数 其中 x a1 an y b1 bn ai B bi Bx y c1 cn whereci ai bix y d1 dn wheredi ai bix e1 en whereei ai 15 2 3 5 和B3 16 布尔代数举例 n度布尔函数全体也构成一个布尔代数 f Bn B

5、布尔和 布尔积 补函数全取0的函数 全取1的函数 17 布尔代数是一种特殊的格 有补分配格 18 偏序格 定义 S 是偏序集 x y S 存在 x y 的最小上界lub x y x y S 存在 x y 的最大下界glb x y 则称S关于 构成格 lub leastupperbound glb greatestlowerbound 19 在格中定义运算 在格中可以定义如下的运算 保联 x y S x y lub x y 保交 x y S x y glb x y 20 偏序格的例子 1 2 3 4 6 8 12 16 24 48 x y gcd x y x y lcm x y B x y x

6、y x y x y 整数集 x y min x y x y max x y 21 格与哈斯图 右边两个哈斯图所表示的偏序集不是格 22 格的基本关系式 根据 最小上界 和 最大下界 的定义 有如下关系式 a a b b a b如果a c b c 则a b ca b a a b b如果c a c b 则c a b 23 关于格的对偶命题 对偶命题的例子 a b是格中元素 a b a和a b a互为对偶命题对偶命题构成规律格元素名不变 与 与 全部互换 格的对偶原理 如果命题P对一切格为真 则P的对偶命题P 也对一切格为真 24 格的性质 若 S 是格 则 a b S a b a b a a b

7、b采用循环证明 a b a b a 由下界定义 a b a 而a a a b 由最大下界定义 a a b a b aa b a a b b 由上界定义 b a b 而由a b b和a b a可知 a b 又b b 由最小上界定义可知 a b b a b ba b b a b a a b 而a b b a b 25 格导出的代数系统 若 S 是格 则 S 称为格S导出的代数系统 S 满足下列性质 证明利用偏序的反对称性以及格命题的对偶原理 交换律 a b b a a b b a a b b a b a a b b a 同理可得b a a b结合律 a b c a b c a b c a b c

8、注意 a b c a b a a b c a b b 当然还有 a b c c等幂律 a a a a a a由偏序的自反性 a a且a a a a a 当然还有a a a吸收律 a a b a a a b a由a a和a a b可得 a a a b 当然还有a a b a 26 代数格 定义 设 L 是代数系统 其中 是二元运算 且满足交换律 结合律 吸收律 则称 L 是 代数 格 代数格满足等幂律 即 a L a a a a a a根据吸收律 a a a a a a a a a a a a a a a a a a a a aa b b当且仅当a b a 若a b b 则a b a a b a

9、 若a b a 则a b a b b b b a b 27 在代数格中定义偏序关系 设 L 是代数格 定义L上的关系R如下 a b L aRb a b b则R是偏序 自反性 注意 满足等幂律反对称性 若aRb bRa 则a b b b a a 但a b b a a b传递性 若aRb bRc 则a b b b c c 则a c a b c a b c b c c 即aRc 28 a b即 a b 的最小上界 a b即 a b 的上界 a a b a a b a b aR a b b a b a b b a b b a b bR a b a b即 a b 的最小上界任给c L 若c也是 a b

10、的上界 则a c c b c c于是 a b c a b c a c c 即 a b Rc 29 a b即 a b 的最大下界 注意 a b b当且仅当a b a 因此aRb a b aa b即 a b 的下界 a b a a a b a a b a b a b Ra a b b a b b a b a b Rba b即 a b 的最大下界任给c L 若c也是 a b 的下界 则c a c c b c于是 c a b c a b c b c 即cR a b 30 偏序格与代数格的等价 L R 即偏序格 和 即相应的 保交 和 保联 运算代数格 L 即相应的导出代数系统 31 布尔代数VS格 布

11、尔代数是代数格 也是 偏序 格结合律 交换律 吸收律最小上界x y 最大下界x y布尔代数是有补的分配格分配律 同一律 补律 32 格中的原子 定义 设L是格 L中有最小元 全下界 0 给定元素a 0 若 b L 有 0 b a b a则称a是L中的原子 原子是覆盖最小元的那些元素 设a b是格L中的原子 若a b 则a b 0假设a b 0 注意 a b a且a b b 由原子的定义 a b a a b b a b 矛盾 33 格中的原子 a b c d a b d a b c d e 1 2 3 e c 原子 34 有限布尔代数的表示定理 任一有限布尔代数B同构于B中所有的原子构成的集合A

12、的幂集代数系统P A 即 B 0 1 P A A 备注 关于无限布尔代数 2N 即无限的0 1序列x0 x1 x2 这一无限布尔代数有原子2N的一个子代数 周期序列 Periodicsequence 这个布尔代数没有原子 35 2 3 5 2 3 5 3 5 2 5 3 2 30 6 5 15 10 3 2 1 36 有限布尔代数基数是2的整数次幂 任何有限布尔代数的基数为2n n是自然数 设B是有限代数系统 A是B中所有原子的集合 则 B P A B P A 2 A 等势的有限布尔代数均同构 37 最小的几个有限布尔代数 与含n个元素的集合的幂集代数系统同构的布尔代数记为Bn 38 Hass

13、eDiagramsofIsomorphicLattices 39 BnasProductofnB s B1 0 1 1 0 isdenotedasB Foranyn 1 BnistheproductB B BofB nfactors whereB B Bisgiventheproductpartialorder Productpartialorder 40 HasseDiagramsofBn 001 111 110 011 101 010 100 000 11 10 01 00 n 0 n 1 0 1 n 2 n 3 41 布尔代数与数字逻辑电路设计 Bn的每一个元素可以看做一个长度为n的二进

14、字符串 一个有n个输入 一个输出的逻辑电路对应于一个用含n个布尔变量的布尔代数表达式定义的布尔函数f B1n B1 也可以看做f Bn B1 在确定表示该函数的布尔表达式后 很容易用门电路元件搭出所需要的逻辑电路 因此 关键问题是如何确定所需的布尔表达式 并将其化为最简形式 42 一个逻辑电路设计的例子 举重比赛中三个裁判中两个或者两个以上判定为成功则该次成绩有效 设计一个电子打分器 输出一个结果 成功 或 失败 布尔函数 f x y z 1iff x y z至少有两个为1 x z y 00001111 00110011 01010101 f x y z 00010111 相应的布尔表达式 x

15、 y z x y z x y z x y z 43 基本逻辑元件 或 门 x y x y 与 门 x x 反相器 44 电路设计 相应的布尔表达式 x y z x y z x y z x y z x y z x y z f x y z 太复杂 45 用卡诺图化简布尔表达式 x z y 00001111 00110011 01010101 f x y z 00010111 x x yz y z yz y z 0 0 1 0 1 0 1 1 简化后的表达式 y z x z x y 46 改进后的电路设计 相应的布尔表达式 y z x z x y 47 作业 教材 11 1 11 2 p 593 9

16、 10 24 27 41p 596 3 c d 12 a b 设 B 是代数格 x y B 定义x yiffx y x 证明这个关系 满足自反性 反对称性和传递性 48 卡诺图 Karnaughmap n 2 基本位置 f B2 B 00 01 10 11 y x x y x y x y x y x y f x y x y x y x y f x y 0011 0101 1100 y y x x 1 0 0 1 我们知道 f x y x 49 用卡诺图化简布尔表达式 基本位置 f B2 B 00 01 10 11 y x x y x y x y x y x y f x y x y x y x y x y f x y 0011 0101 1110 y y x x 1 1 0 1 f x y x y 50 卡诺图n 3 00 01 10 11 0 1 000 100 010 101 001 011 111 110 x x x y z x y z x y z x y z x y z x y z x y z x y z y z y z y z y z y y z z 51 化简三个变量的布尔表