布尔代数.ppt

导入 8 3布尔代数 一 背景知识介绍 19世纪中后叶 代数学还开拓了另一个完全不同的领域 我们知道 早在17世纪 莱布尼茨就想要发明一种通用的语言 借助它的符号和专门语法来指导推理 他认为逻辑语言应该用一些表意的符号 每一个符号代表一个简单的概念 通过各种符号的组合表达复杂的思想 他也认真地考虑过建立一种推理的代数 试图通过演算完成一切正确的推理过程 在他真正开始的逻辑代数工作中 莱布尼茨已经直接或间接地有了我们现在所说的逻辑加法 乘法 等同 否定和空集这样一些概念 他还注意到需要研究一些抽象关系 如包含 等价关系等 并认识到一些关系的对称性和传递性 但是 莱布尼茨并没有完成这项工作 而他已做过的一些工作的细节知道20世纪初才出版 因此 对后来逻辑代数的产生和发展很少有直接的影响 一些前辈犹豫不决 是因为它牵涉到改进亚里士多德的工作 而人们对于改进亚里士多德的工作的尝试总有点犹豫不决 然而布尔敢于这么干 二 布尔代数的产生和发展 布尔的父亲是一位鞋匠 布尔青少年时期 在当地上了小学和短时间的商业学校 他自学了希腊语和拉丁语 后来又学会欧洲几个国家的语言 从商业学校毕业后 布尔原想做一名牧师 但由于生活所迫 他在16岁那年接受了中学教师的职务 1831 1835年 先后在唐卡斯特和瓦丁顿的一些中学教书 就在这个时期 他对数学产生了深厚的兴趣 并决定继续自学数学 1835年 他在林肯市创办了一所中学 仍是一面教书 一面自修高等数学 他先后攻读了著名科学家I 牛顿 Newton 的 自然哲学的数学原理 Philosophiaenaturalisprincipiamathematica 和J 拉格朗日 Lagrange 的 解析函数论 Th oriedesfunctionanalytiques 1835年发表了他的第一篇科学论文 论牛顿 OnNewton 21岁时 他就精通P S 拉普拉斯 Laplace 的 天体力学 M ca niquec leste 这在当时被认为是最深奥的学问 这一事实足以证明他自学取得的成功 1849年 34岁的布尔分别获得牛津大学和都伯林大学的名誉博士学位 随即被聘为爱尔兰科克皇后学院 今爱尔兰大学 的数学教授 从此 他才有了比较安稳的生活保证 他保持这个职位一直到15年后患病逝世为止 在此期间 他于1857年被推选为伦敦皇家学会会员 1855年 布尔和G 爱维累斯特 Iwirester 爵士的侄女玛丽 爱维累斯特 MaryIwirester 结婚 他们的长女玛丽嫁给数学家C H 欣顿 Hinton 三个外孙都有科学建树 另一个女儿艾丽西亚 Alicia 在四维几何方面的研究中取得成果 以后又与数学家H S M 考克斯特 Coxeter 合作 第四个女儿露西 Lucy 成为英国在大学担任化学教授的第一个妇女 布尔最小的女儿E 莉莲 Lillian 便是受到广泛阅读的小说 牛虻 的作者B L 伏尼契 Voynich 2 布尔代数的产生 3 布尔代数的内涵 对于逻辑代数 布尔的方法是着重于外延逻辑 extensionallogic 即类 class 的逻辑 其中类或集合用x y z 表示 而符号X Y Z 则代表个体元素 用1表示万有类 或全类或称论域 用0表示空类或零类 他用xy表示两个集合的交 他称这个运算为选拔 election 即x与y所有共同元素的集合 还用x y表示x中和y中所有元素的集合 严格地讲 对于布尔 加法只用于不相交的集合 后来 由W S 杰文斯 Jevons 推广了这个概念 至于x的补x 记作1 x 更一般地 x y是由不是y的那些x所组成的类 包含关系 即x包含在y中 他写成xy x 等号 表示两个类的同一性 在布尔代数里 布尔构思出一个关于0和1的代数系统 用基础的逻辑符号系统描述物体和概念 这种代数为今后数字计算机开关电路设计提供了最重要数学方法 1938年 克劳德 向农 C E Shannon 将布尔代数应用于电话继电器的开关电路 提出了 开关代数 随着电子技术的发展 集成电路逻辑门已经取代了机械触点开关 故 开关代数 这个术语已很少使用 为了与 数字系统逻辑设计 这一术语相适应 人们更习惯于把开关代数叫做逻辑代数 逻辑代数是数子系统逻辑设计的理论基础和重要数学工具 三 逻辑代数和开关电路 信息论的创始人克劳德 香农 C E Shannon 对现代电子计算机的产生和发展有重要影响 是电子计算机理论的重要奠基人之一 1938年 香农发表了著名的论文 继电器和开关电路的符号分析 首次用布尔代数进行开关电路分析 并证明布尔代数的逻辑运算 可以通过继电器电路来实现 明确地给出了实现加 减 乘 除等运算的电子电路的设计方法 这篇论文成为开关电路理论的开端 香农在贝尔实验室工作中进一步证明 可以采用能实现布尔代数运算的继电器或电子元件来制造计算机 香农的理论还为计算机具有逻辑功能奠定了基础 从而使电子计算机既能用于数值计算 又具有各种非数值应用功能 使得以后的计算机在几乎任何领域中都得到了广泛的应用 1956年 他参与发起了达特默斯人工智能会议 成为这一新学科的开山鼻祖之一 他不仅率先把人工智能运用于电脑下棋方面 而且发明了一个能自动穿越迷宫的电子老鼠 以此证明计算机可以通过学习提高智能 3 1逻辑代数的基本概念 2 不同点 在布尔代数中一个最基本的性质是 1 x 1 称之为0 1律 这是与实数运算最不同的性质 加法对乘法的分配律 x yz x y x z 吸收律 x xy x x x y x幂等律 x x x x x x在布尔代数中 有一种特殊的运算 求逆 在实数中不具有这种运算 布尔代数具有以下性质 德莫根律 x y x y 并之补等于补之交 xy x y 交之补等于补之并 双重逆反律 x x 或 运算的运算法则 0 0 01 0 1 0 1 11 1 1 实现 或 运算关系的逻辑电路称为 或 门 2 与 运算如果决定某一事件发生的多个条件必须同时具备 事件才能发生 则这种因果关系称之为 与 逻辑 在逻辑代数中 与 逻辑关系用 与 运算描述 其运算符号为 有时也用 表示 两变量 与 运算关系可表示为 F A B或者F A B 即 若A B均为1 则F为1 否则 F为0 例如 在右上图所示电路中 两个开关串联控制同一个灯 显然 仅当两个开关均闭合时 灯才能亮 否则 灯灭 假定开关闭合状态用1表示 断开状态用0表示 灯亮用1表示 灯灭用0表示 则电路中灯F和开关A B之间的关系即上表所示的 与 运算关系 例如 在右上图所示电路中 开关与灯并联 显然 仅当开关断开时 灯亮 一旦开关闭合 则灯灭 令开关断开用0表示 开关闭合用1表示 灯亮用1表示 灯灭用0表示 则电路中灯F与开关A的关系即为上表所示 非 运算关系 非 运算的运算法则 数字系统中实现 非 运算功能的逻辑电路称为 非 门 有时又称为 反相器 在举重比赛中 通常设三名裁判 一名为主裁 另两名为副裁 竞赛规则规定运动员每次试举必须获得主裁及至少一名副裁的认可 方算成功 裁判员的态度只能同意和不同意两种 运动员的试举也只有成功与失败两种情况 举重问题可用逻辑代数加以描述 用A B C三个逻辑变量表示主副三裁判 取值1表示同意 成功 取值0表示不同意 失败 举重运动员用L表示 取值1表示成功 0表示失败 显然 L由A B C决定 L为A B C的逻辑函数 列表如下 该表称为逻辑函数L的真值表 应用 从真值表可看出L取值为1只有三项 A B C的取值分别为101 110 和111三种情况L才等于1 A C A B A B C三项与上述三种取值对应 由于上述三种情况之一出现就可判定L成功 故 根据上述布尔式来设计就可以得到举重裁判的控制电路 其中由主裁控制 和分别由两个副裁控制 某银行打算在仓库门上装一