计算机问题求解--论题1-13 --布尔代数 2017年12月28日.

Presentation on theme: "计算机问题求解--论题1-13 --布尔代数 2017年12月28日."— Presentation transcript:

1 计算机问题求解--论题 布尔代数 2017年12月28日

2 问题1：这个是布尔代数的定义，你有没有一种熟悉的感觉?它和另一个定义有什么异同之处？你能想到什么？
逻辑连接词的定义； 集合运算 格定义

3 “这个”代数和格 问题2：显然，这个代数一定是个格！那么：多出来的那些特性（由公理描述），有什么用呢？

4 我们可以很容易的验证B3是布尔代数 问题3：从这个B3中，我们能否设计一个“类似”的格？ 元素有哪些？偏序关系是什么？
001 111 110 011 101 010 100 000 B3 问题3：从这个B3中，我们能否设计一个“类似”的格？ 元素有哪些？偏序关系是什么？ meet和join分别是什么？ Bn有几个元素？

5 其实，布尔代数是一类特别的格： 1，我们可以从布尔代数和偏序集两个角度共同定义一个“系统” 2，布尔代数和有界有补分配格是“等价”的
从同构的角度上讲，有界布尔代数、有界有补分配格、有限集合运算格，同构！ 从同构的角度上讲，有界布尔代数、有界有补分配格、有限集合的幂集运算格，同构： Bn中的n=集合元素个数=原子个数 Bn中的0…1…0，对应为原子，对应为单元素子集 请问：三个同构的系统，是如何同构的？

6 问题4： 因为B1，B2，B3，…,Bn有2n个元素？ 其实，我们还可以这样来观察： 1，这样的格中，原子个数是n个
2,，除0外，所有元素都可以表示为一个或者多个原子的join，所有由一个或者多个原子的join的结果都是格中元素。 3，这样的元素有2n-1个 必定！

7 问题5：我们为什么要定义sum-of-products form?如何理解form是什么意思？
所有的集合，均可以由几个“并”范式表达：任意的三集合运算表达式，均可以表达为8个标准式中若干式子的并。 任何集合运算表达式，均可以表达为若干合取式的并 任何逻辑运算表达式，也均可以表达为若干“与范式”的或。 任意的n个集合，它们的交并结果，汇集成一个格，但

8 问题6：任意的布尔代数运算表达式，是否都可以表达为某个”sum-of-products form”？
如果可以，我们会想到什么？ 这个定理为我们证明两个逻辑（布尔）表达式的等价带来了极大的便利！

9 复习几个概念： Literal？Fundamental product？Contained in? “惊艳”的吸收率：

10 求和E等价的积和表达式

11 求解布尔表达式E的完全积和表达式

12 问题7：有没有科学办法，从任意的一个布尔逻辑表达式出发，得到和它等价的最简表达式？
回到举重裁判的问题 x y z f(x,y,z) 相应的逻辑表达式: (x’yz) (xy’z) (xyz’) (xyz) 问题7：有没有科学办法，从任意的一个布尔逻辑表达式出发，得到和它等价的最简表达式？ 问题7:相应的布尔代数表达式是什么？ x’ yz+ xy’ z+ xyz’+ xyz 问题8:相应的最简布尔代数表达式是什么？ yz+xz+xy

13 如何“化简”下列布尔代数表达式 这个式子难道就是最简的吗？ 什么是最简？ x’ yz+ xy’ z+ xyz’+ xyz=
x’ yz+ xyz+ xy’ z+ xyz+ xyz’+ xyz = yz+xz+xy 这个式子难道就是最简的吗？ 什么是最简？

14 如何去寻找（定义）最小（其实是极小）的积和表达式？
复习几个概念： E is simpler than F E is minimal if there is no equivalent sum-of-products expression which is simpler than E. x’ yz+ xy’ z+ xyz’+ xyz= yz+xz+xy 这种定义在数字逻辑电路设计中，意味着什么？ Minimal的定义在数字逻辑电路设计中，意味着什么？

15 什么是prime implicant？ 这个定理背后，有什么寓意？
素项P的加入，表面上看，增加了E的长度。但是因为吸收率的存在，素项P的加入多数时候会吸收掉若干个基础积，使得E的长度变小。 Theorem 15.9: A minimal sum-of-products form for a Boolean expression E is a sum of prime implicants of E. 这个定理背后，有什么寓意？

16 接下来的问题是：如何找到E的素(蕴含)项
一个有点突兀的概念： Consensus of Fundamental Products Let E = xyz + x’z’ + xyz’ + x’y’z + x’yz’ 你能在这个式子中找到某两个基本积的Consensus 吗？ Then： E = xyz + x’z’ + xyz’ + x’y’z + x’yz’+xy

17 共识项方法求素项和

18 问题9：你能说说看，下例中寻找素项的每一步的理论依据吗？
红色标记：书籍错误 其实在第二个“共识项”中，还有其它选择 显然，E有两个等价的素项表达，最终结果并不是极小式

19 怎么办？

20 我们为什么能够“理直气壮”地得到问题7,8的结论？
再回到举重裁判的问题 x y z f(x,y,z) 相应的逻辑表达式: (x’yz) (xy’z) (xyz’) (xyz) 我们为什么能够“理直气壮”地得到问题7,8的结论？ 问题7:相应的布尔代数表达式是什么？ x’ yz+ xy’ z+ xyz’+ xyz 问题8:相应的最简布尔代数表达式是什么？ yz+xz+xy

21 Logic circuits form a Boolean Algebra！
针对一个具体（逻辑）电路设计需求，我们得到一个满足需求的逻辑表达式，利用布尔代数的基本理论（定义定理算法等），转换成相应的布尔代数表达式，寻找其最简形式，利用与或非门，设计出一个逻辑电路

22 Open Topic 以三元素逻辑表达式化简为例，介绍卡诺图的使用及背后的基本 理论基础