标签: 布尔代数

我们回来，有认真的去看上面列出的公理（Axiom）和单变量定理么？   （对于其证明，有兴趣的人可以看一下，没兴趣的可以跳过。这里我就证明（b）里面的T4：由于A1和其双对可知，我们是在处理二进制问题。所以根据A2我们进行两次A2操作，也就相当于第一次进行了A1操作，第二次进行A1'的操作，结果是原数的本身。所以得证//）   那么让我们继续多变量的（多输入，2个或2个以上）的处理方法。 （c） 注意处理多变量，只要想加减多项式的运算法则就好了。（就是小学多项式计算） T6（和T6’一样）：加法（OR）交换律了 T7（和T7’一样）：加法（OR）结合律 T8：分配律 ///////////////////以下是二进制运算特有的///////////////// T8'：比较特殊，是OR分配于AND，而一般代数运算没有把加法分配于乘法的，只有乘法分配率。可以这样看： T9：覆盖律 T10：组合律 T11： 共识律 T12：就是摩尔根定律咯！   想证明这些定理么？必须的，这就是大家的任务咯。把每一条验证一下。不会证明？二进制只有1和0，列真值表也就是穷举法证明即可。不要偷懒哦。有能力的人，可以自己用（b）和（c）里的某些定理出发推到你想要的定理。 比如：为了证明T9'：用T8'：B+（B*C）=（B+B）*（B+C）= B*（B+C）= B，因为B OR C，结果可以取B和C，如果取B则得到结果。// 话说Morgan定律几乎是万能的可以导出上面所有的定理（当然和其他的加以组合）！ 这里我给出 共识律的证明方法： 。看表自然明了了吧。   有人说了，这么多，记不住怎么办？重点在这：只有一个方法，，也是能让你成为大师的开端：就是不厌其烦的去动手用（下面讲怎么用），配上下面即将讲的卡诺图！如果能做到卡诺图和上述定理灵活运用，你已经离大师进了一步了。 （不要靠Verilog，HDL神马的自动工具，这也是因为为什么大多数人走向码农的原因。太自动了，自己大脑懒得动，以后我们设计VLSI的时候，当然要用那些工具，但是集成上百万CMOS的时候，机器没有那么聪明，因为它体会不到设计的艺术和直觉。相信我，Intel和AMD神马的高级工程师都是在几千CMOS组合中很快能找出优化策略的人，因为他们见的多了，也就在脑中形成模块了。所以当自己有能力做到这一点的时候，才能算得上大师级。）     那么下面我们来讲应用吧~上面这些理论，目标只有一个，用更少的CMOS做更多的事！ 例如：化简Y=~A~B~C+A~ B~C+A~BC 第一种化简方法：（Justification列出了应用了哪条定理） 第二种化简方法：（Justification列出了应用了哪条定理） 注意这里应用B=B+B+B+...的定理也就是T3等幂定理的双对定理。   到这里，大家又要动笔了 任务就是 1：自己证明（c）里定理的正确性，不要懒哦 2.把最后一个例子用逻辑图实现一下（两种化简方法都要做）  

之前的几章里，大家已经做过不少练习了。现在大家手中的代数工具只有DeMorgen定理和推泡泡定理。那么在设计逻辑门的时候，有很多时候不止一种实现方法，各有不同的优势。那么怎样才能随心所欲的设计逻辑门电路呢。答案就是利用数学工具。数学？！头痛！没关系，只要动手做，就一定能学会。 说明一下，这里的形式采用和讲二进制时候一样。易懂而不罗嗦，以后忘了，来这一看就能想起来。 1。符号定义：和以前的规则一样 ~A 代表 “非”（NOT） A，A+B代表“A或B”（A OR B），A*B代表“A和B”（A AND B） 2. 优先权：和加减乘除类比，布尔代数优先权从高到低为NOT，AND，OR。 例Y=A+BC 等价于：Y=A+（BC）而不是Y=（A+B）C！所以括号用来改变运算优先权。 3.SOP（SumOfProduct）形式： 首先定义最小项（minterm）：真值表的每一行一定会有一个使输入以AND组合后为“真”的表达式。。。神马意思，看例子： （1） （2） 这里minterm的组合形式均为AND的形式，观察两个例子中的输入和minterm项，无论输入是什么，minterm都是“1”（真）。 在（1）中，输出为Y为1的时候，minterm只有~AB的形式，所以第一个真值表的表达式是Y=~AB，同理第二个例子的表达式是 Y=~AB+AB。---神奇吧，再也不用一行一行看去找表达式了。没什么了，这是数学的小把戏。其实原理是这样的，我们分析真值表的 时候，只要找出当输出为1的输入组合（AND组合）就可以。因真值表枚举了所有输入进行AND的情况，只有符合Y的值的才可以入选，而逻辑运算除了只有NOT，AND，OR。而一个逻辑回路里，可以有很多输入组合其输出结果为1，所以只要把这些情况相（加）或就能得到表达式。 而（2）得到的表达式就是叫做SOP规范形式（sum of product）~~用来唬人的名字。因为式的意思是 把两个AND的结果相OR（把两个积相加）。 这里大家想起来概率的运算了吗？独立事件神马的。是的有着密切的关联!因为二进制数操作本身就是概率的操作。举例说，有8个空bits，那么我们就有8个位置去放0和1，那么总共的概率就是 2^8=256，也就是有256种放的方法，这不就是8bits的范围嘛（0~255）。所以二进制操作符合概率的计算。再举个例子，Y=~A~B~C+A~B~C+A~BC也是SOP形式。（大家改动手画它的真值表了，然后验证上面讲的！）感觉式子好长吧，画起线路图来很麻烦。 是的，我们这不是在探索捷径呢嘛~ 4 POS（ProductOfSum）形式： 和SOP一样，不过先定义最大项（minterm）：真值表的每一行一定会有一个使输入以OR组合后为“假”的表达式（原理：真值表枚举了所有输入进行OR的情况，只有符合Y的值的才可以入选），看例子： 。大家自己用上面SOP的想法一步一步分析。我就不罗嗦了，不懂得留言。这个真值表的表达式即为Y=（A+B）*（~A+B）。 5.布尔代数（Boolean Algerbra） 就是和一般的加减乘除差不多，只比那个更简单。所以大家不要怕噢~。首先我要引入公理和定理的区别：公理不能被证明，而定理可以用一堆公理来证明。 其次就是双对的定义：如果1和0，AND和OR同时交换的时候，结果不变。我们说结果有双对的性质。例如：如果 ~B=1则B=0 和 如果 ~B=0则B=1 这两个描述的都是同一个事情，不过1和0交换了，就是这两个叙述成双对关系。 （如果不明白就跳过，学完之后回来再看一定会懂得） （a）好了，现在把布尔代数中需要的定义拿出来： 。解释一下：Axiom就是事实，Dual就是从另一个方向描述事实的双对。Name就是这个公理的名字。 例如A1说的就是如果B不等于1，则B等于0.也就是说这是二进制领域（见Name）。其双对的描述就是:如果B不等于0则B一定是1.A1'和A1很对称吧~。剩下的一定要一个一个看完。要不继续讲可能会糊涂。   （b）只有一个变量的定理： 。这里T代表Theorem，也就是可以用（a）里的公理证明的！注意Name里Identity就是代表“自己运算（经过某种运算后和原来相同）” 数学里也叫 单位运算 。Null Element顾名思义 “零元素”，概念就是和任何数乘0都得0一样。0“与”任意输入都是0，而1或任意输入都是1.Idempotency就是等幂性。说的是，一个输入AND自己一下得到仍是自己，在AND一下还是自己，n次以后还是自己即B^n=B就是无论是几次乘积操作都是等同的（幂就是乘方）。Involution我们早已见过，就是求两次逆的操作。Complements就是互补，一个输入AND自己的互补结果一定是0.因为1的互补是0，0的互补是1..       好了就先写到这，下一结我们看如何如何用这些工具，以及更多变量的时候怎么处理。