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

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

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

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

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

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

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

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

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

求和E等价的积和表达式

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

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

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

如何去寻找（定义）最小（其实是极小）的积和表达式？ 复习几个概念： 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的定义在数字逻辑电路设计中，意味着什么？

什么是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. 这个定理背后，有什么寓意？

接下来的问题是：如何找到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

共识项方法求素项和

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

怎么办？

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

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

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