《计算机原理》课程教学资源：机械工业出版社《编码的奥秘》参考书籍（PDF电子书）第10章 逻辑与开关

chinaopub.com 下载 第10章逻辑与开关 真理是什么呢?亚里士多德认为逻辑与它有关。他的讲义合集《工具论》( Organon,可 追溯到公元前4世纪)是最早的关于逻辑的详细著作。对于古希腊人而言,逻辑是追寻真理的 过程中用于分析语言的一种手段,因此它被认为是一种哲学。亚里土多德的逻辑学的基础是 段论。最有名的三段论(它并非是在亚里士多德的著作中发现的)是 All men are mortal Socrates is a man Hence Socrates is mortal. (所有的人都是要死的 苏格拉底是人 所以,苏格拉底是要死的。) 在三段论中,两个前提被假设是正确的,并由此推出结论 苏格拉底之死这个例子看上去似乎太直白了,但还有许多其他不同的三段论。例如,考 虑下面两个由19世纪数学家 Charles Dodgson(也就是 Lewis carroll)提出的前提 All philosophers are logical; An illogical man is alwvays obstinate. (所有的哲学家都是有逻辑头脑的 个没有逻辑头脑的人总是顽固的。) 它所能推出的结论一点儿也不明显。(事实上,结论是“一些顽固的人不是哲学家(Some dostinate persons are not philosophers)”)请注意结论中一个出乎意料且令人迷惑的词“一些 两千多年来,数学家们对亚里士多德的逻辑理论苦苦思索,试图用数学符号和操作符来 表现它。19世纪以前,唯一能接近这个目标的人是莱布尼兹(1648-1716),他早年涉足逻 学领域,后来转向其他学科(比如说,他几乎和牛顿同时独立地发明了微积分)。 接下来有所突破的是乔治·布尔 乔治·布尔1815年生于英格兰,他周围的环境对他的 成长很不利。他父亲是鞋匠,而母亲曾是女仆,英国森严 的等级制度使布尔学不到什么有别于父辈的东西。但是 容 靠着他自身强烈的好奇心及父亲的帮助(其父对科学研究、 数学和文学有浓厚的兴趣),年轻的乔治自学了上层阶级 男孩才能学到的课程,包括拉丁文、希腊语及数学。由于 他早年在数学方面发表的论文,1849年,布尔被任命为爱 尔兰Cork市的皇后大学数学系的首席教授 19世纪中期的几位数学家在逻辑理论的数学定义上做 了一些工作(最著名的是迪摩根),但只有布尔有真正概

下载 第10章 逻辑与开关 真理是什么呢？亚里士多德认为逻辑与它有关。他的讲义合集《工具论》（O rg a n o n，可 追溯到公元前4世纪）是最早的关于逻辑的详细著作。对于古希腊人而言，逻辑是追寻真理的 过程中用于分析语言的一种手段，因此它被认为是一种哲学。亚里士多德的逻辑学的基础是 三段论。最有名的三段论（它并非是在亚里士多德的著作中发现的）是： (所有的人都是要死的; 苏格拉底是人; 所以,苏格拉底是要死的。) 在三段论中，两个前提被假设是正确的，并由此推出结论。 苏格拉底之死这个例子看上去似乎太直白了，但还有许多其他不同的三段论。例如，考 虑下面两个由1 9世纪数学家Charles Dodgson（也就是Lewis Carroll）提出的前提： (所有的哲学家都是有逻辑头脑的 ; 一个没有逻辑头脑的人总是顽固的。 ) 它所能推出的结论一点儿也不明显。（事实上，结论是“一些顽固的人不是哲学家 ( S o m e dostinate persons are not philosophers)”)请注意结论中一个出乎意料且令人迷惑的词 “一些 ( s o m e )”。 两千多年来，数学家们对亚里士多德的逻辑理论苦苦思索，试图用数学符号和操作符来 表现它。1 9世纪以前，唯一能接近这个目标的人是莱布尼兹（ 1 6 4 8—1 7 1 6），他早年涉足逻辑 学领域，后来转向其他学科（比如说，他几乎和牛顿同时独立地发明了微积分 )。 接下来有所突破的是乔治·布尔。 乔治·布尔1 8 1 5年生于英格兰，他周围的环境对他的 成长很不利。他父亲是鞋匠，而母亲曾是女仆，英国森严 的等级制度使布尔学不到什么有别于父辈的东西。但是， 靠着他自身强烈的好奇心及父亲的帮助（其父对科学研究、 数学和文学有浓厚的兴趣），年轻的乔治自学了上层阶级 男孩才能学到的课程，包括拉丁文、希腊语及数学。由于 他早年在数学方面发表的论文， 1 8 4 9年，布尔被任命为爱 尔兰C o r k市的皇后大学数学系的首席教授。 1 9世纪中期的几位数学家在逻辑理论的数学定义上做 了一些工作（最著名的是迪摩根），但只有布尔有真正概

62 编码的奥秘 China°dco 念上的突破。他最早的贡献是发表的一本很简短的书《 The Mathematical Analysis of logic, Being an Essay Towards a Calculus of Deductive Reasoning》(1847),接着又发表了一篇很长且 充满抱负的文章:《 An Investigation of the Laws of Thought on Which Are Founded the Mathematical Theories of logic and probabilities》(1854),简称为《 The laws of thought》 1864年的一天,布尔在雨中赶去上课时不幸感染上了肺炎,不治身亡,享年49岁。 我们可以从布尔在1854年所著书的题目中看出他富于野心的想法:由于充满理性的人脑 用逻辑去思考,那么,如果能用数学来表征逻辑,我们也就可以用数学来描述大脑是如何工 作的。当然,现在看来这种想法似乎十分幼稚。(但却超越了他所在的年代。) 布尔发明了一种和传统代数看起来、用起来都十分相似的代数。在传统代数中,操作数 (通常是字母)代表数字,而操作符(多是“+”或“×”)指明这些操作数如何结合到一起 般我们可用传统代数解决类似下面的问题:如果安娜有3磅豆腐,贝蒂的豆腐是安娜的2 倍,卡门的豆腐比贝蒂多5磅,迪尔德丽的豆腐是卡门的3倍。那么,迪尔德丽有多少豆腐 为了计算这个问题,我们首先把语句转化为算术式子,用四个字母代表每个人拥有豆腐 的数量,即: B=2×A C=B+5 D=3×C 可以通过代入把上述四个表达式合为一个式子,最后执行加法和乘法,即 D=3×C D=3×(B+5) D=3×((2×A)+5) D=3×((2×3)+5) 当做传统代数题时,要遵循一定的规则。这些规则可能已经和实践融为一体,以至于我 们不再认为它们是规则,甚至忘记了它们的名字。但规则确实是任何形式的数学的基础 第一个规则是加法与乘法的交换律,即我们可以在操作符两边交换操作数的位置 A+B =B+A A×B=B×A 相反,减法和除法是不满足交换律的。 加法和乘法也满足结合律,即: A+(B+C)=(A+B)+C A×(B×C)=(A×B)×C 最后,乘法对加法可以进行分配

62 编码的奥秘 下载 念上的突破。他最早的贡献是发表的一本很简短的书《 The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning》( 1 8 4 7 )，接着又发表了一篇很长且 充满抱负的文章：《An Investigation of the Laws of Thought on Which Are Founded the Mathematical Theories of Logic and Probabilities》( 1 8 5 4 )，简称为《The Laws of Thought》。 1 8 6 4年的一天，布尔在雨中赶去上课时不幸感染上了肺炎，不治身亡，享年 4 9岁。 我们可以从布尔在 1 8 5 4年所著书的题目中看出他富于野心的想法：由于充满理性的人脑 用逻辑去思考，那么，如果能用数学来表征逻辑，我们也就可以用数学来描述大脑是如何工 作的。当然，现在看来这种想法似乎十分幼稚。（但却超越了他所在的年代。） 布尔发明了一种和传统代数看起来、用起来都十分相似的代数。在传统代数中，操作数 （通常是字母）代表数字，而操作符（多是“ +”或“×”）指明这些操作数如何结合到一起。 一般我们可用传统代数解决类似下面的问题：如果安娜有 3磅豆腐，贝蒂的豆腐是安娜的 2 倍，卡门的豆腐比贝蒂多 5磅，迪尔德丽的豆腐是卡门的 3倍。那么，迪尔德丽有多少豆腐 呢？ 为了计算这个问题，我们首先把语句转化为算术式子，用四个字母代表每个人拥有豆腐 的数量，即： A = 3 B = 2×A C = B+5 D = 3×C 可以通过代入把上述四个表达式合为一个式子，最后执行加法和乘法，即： D = 3×C D = 3×（B + 5） D = 3×（（2×A）+ 5） D = 3×（（2×3）+ 5） D = 33 当做传统代数题时，要遵循一定的规则。这些规则可能已经和实践融为一体，以至于我 们不再认为它们是规则，甚至忘记了它们的名字。但规则确实是任何形式的数学的基础。 第一个规则是加法与乘法的交换律，即我们可以在操作符两边交换操作数的位置： A+B = B+A A×B = B×A 相反，减法和除法是不满足交换律的。 加法和乘法也满足结合律，即： A +（B + C）=（A + B）+ C A×（B×C）=（A×B）×C 最后，乘法对加法可以进行分配： A×（B + C）=（A×B）+（A×C）

Chinaopub.com 第0章与开关63 下载 传统代数的另外一个特点是它总是处理数字,如豆腐的重量或鸭子的数量,火车行驶的 距离或家庭成员的年龄。是布尔超凡的智慧使代数脱离了数字的概念而变得更加抽象。在 尔代数中(布尔的代数最终被这样命名)操作数不是指数字,而是指集(类)。一个类仅仅表 示一组事物,也就是后来熟知的集合 让我们来讨论一下猫。猫或公或母,为方便起见,我们用字母M指代公猫的集合,用F指 代母猫的集合。记住,这两个符号并不代表猫的数量,公猫或母猫的数量随着小猫仔的出生 和老猫的不幸离去而变化,这两个字母代表的是猫的种类——具有某种特点的猫。因而我们 不说公猫,而是用M来代表它们。 我们也可以用其他字母代表猫的颜色。例如,用T代表黄褐色的猫,用B代表黑猫,用W 代表白猫,而用O代表所有其他颜色的猫。 最后(至少就这个例子而言),猫要么是阉过的要么是有生育能力的。我们用字母N代 阉过的猫,而用U代表有生育能力的猫。 在传统代数中,操作符+和×被用于表示加法和乘法。在布尔代数中,同样用到了+和 这似乎会引起混淆。人人都知道在传统代数中如何对数字进行加和乘,但是我们如何对“类” 进行加和乘呢? 事实上,在布尔代数中我们并不真正地做加或乘,相反,这两个符号有着完全不同的意 在布尔代数中,符号+意味着两个集合合并,两个集合的合并就是包含第一个集合的所有 成员及第二个集合的所有成员。例如,B+W表示黑猫和白猫的集合 布尔代数中的符号×意味着取两个集合的交集,两个集合的交集包含的元素既在第一个 集合中,也在第二个集合中。例如,F×T代表了一种猫的集合,这个集合中的猫既是母猫又 是黄褐色的。与传统代数一样,我们可以把F×T写成F·T或简写为FT(这正是布尔代数所期 望的)。你可以把这两个字母看成是连在一起的两个形容词:黄褐色的母猫。 为避免传统代数和布尔代数之间的混淆,有时候用符号∪和∩而不用+和×来表示并运算 和交运算。但布尔对数学的解放性的部分影响是使熟悉的操作符更加抽象,所以,我们决定 坚持他的决定,而不为他的代数引入新的符号 交换律、结合律和分配律在布尔代数中均适用。而且,在布尔代数中,操作符+可以对 进行分配,这在传统代数中是不成立的,即 W+(B×F)=(W+B)×(W+F 这个式子表示白猫(W)和黑色母猫(B×F)的并集和等式右边两个集合的交集是一样 的,这两个集合是白猫和黑猫的并集(W+B)及白猫和母猫的并集(W+F)。要掌握这个规 则有些困难,但它的确有用 为了使布尔代数更加完整,我们还需要两个符号。这两个符号看上去像数字,但它们并 不真的是数字,因为有时候它们和数字有些不同。符号“1”在布尔代数中表示“整个宇宙 (全集)”,也就是我们所谈论的每件事物。本例中,符号“1”表示“所有的猫”。这样: M+F=1 即母猫和公猫的并集是所有的猫。同样,黄褐色猫、黑猫、白猫及其他颜色的猫的并集 也是所有的猫,即

第10章 逻辑与开关 63 下载 传统代数的另外一个特点是它总是处理数字，如豆腐的重量或鸭子的数量，火车行驶的 距离或家庭成员的年龄。是布尔超凡的智慧使代数脱离了数字的概念而变得更加抽象。在布 尔代数中（布尔的代数最终被这样命名）操作数不是指数字，而是指集（类）。一个类仅仅表 示一组事物，也就是后来熟知的集合。 让我们来讨论一下猫。猫或公或母，为方便起见，我们用字母 M指代公猫的集合，用 F指 代母猫的集合。记住，这两个符号并不代表猫的数量，公猫或母猫的数量随着小猫仔的出生 和老猫的不幸离去而变化，这两个字母代表的是猫的种类—具有某种特点的猫。因而我们 不说公猫，而是用M来代表它们。 我们也可以用其他字母代表猫的颜色。例如，用 T代表黄褐色的猫，用 B代表黑猫，用W 代表白猫，而用O代表所有其他颜色的猫。 最后（至少就这个例子而言），猫要么是阉过的要么是有生育能力的。我们用字母 N代表 阉过的猫，而用U代表有生育能力的猫。 在传统代数中，操作符+和×被用于表示加法和乘法。在布尔代数中，同样用到了 +和×。 这似乎会引起混淆。人人都知道在传统代数中如何对数字进行加和乘，但是我们如何对“类” 进行加和乘呢？ 事实上，在布尔代数中我们并不真正地做加或乘，相反，这两个符号有着完全不同的意 思。 在布尔代数中，符号+意味着两个集合合并，两个集合的合并就是包含第一个集合的所有 成员及第二个集合的所有成员。例如， B + W表示黑猫和白猫的集合。 布尔代数中的符号×意味着取两个集合的交集，两个集合的交集包含的元素既在第一个 集合中，也在第二个集合中。例如， F×T代表了一种猫的集合，这个集合中的猫既是母猫又 是黄褐色的。与传统代数一样，我们可以把 F×T写成F·T或简写为F T（这正是布尔代数所期 望的）。你可以把这两个字母看成是连在一起的两个形容词：黄褐色的母猫。 为避免传统代数和布尔代数之间的混淆，有时候用符号∪和∩而不用 +和×来表示并运算 和交运算。但布尔对数学的解放性的部分影响是使熟悉的操作符更加抽象，所以，我们决定 坚持他的决定，而不为他的代数引入新的符号。 交换律、结合律和分配律在布尔代数中均适用。而且，在布尔代数中，操作符 +可以对× 进行分配，这在传统代数中是不成立的，即： W +（B×F）=（W + B）×（W + F） 这个式子表示白猫（ W）和黑色母猫（ B×F）的并集和等式右边两个集合的交集是一样 的，这两个集合是白猫和黑猫的并集（ W + B）及白猫和母猫的并集（ W + F）。要掌握这个规 则有些困难，但它的确有用。 为了使布尔代数更加完整，我们还需要两个符号。这两个符号看上去像数字，但它们并 不真的是数字，因为有时候它们和数字有些不同。符号“ 1”在布尔代数中表示“整个宇宙 (全集)”，也就是我们所谈论的每件事物。本例中，符号“ 1”表示“所有的猫”。这样： M + F = 1 即母猫和公猫的并集是所有的猫。同样，黄褐色猫、黑猫、白猫及其他颜色的猫的并集 也是所有的猫，即：

64编的奥移 Chia°b6e0M T+B+W+0=1 你也可以这样表示所有的猫 N+U=1 符号1可以用一个减号一来排除一些事物。例如 表示除了公猫以外的所有猫。排除公猫以后的全集就是母猫的集合: 1-M=F 我们所需要的另外一个符号是“0”。在布尔代数中,“0”表示空集,即不含任何事物的 集合。当求取两个完全相互排斥的集合的交集时,空集就产生了。例如,既是母的又是公的 猫的集合可以表示为: FXM=O 注意,符号1和0有时的用法与传统代数相同。例如,所有的猫和母猫求交集即是母猫这 个集合: 1×F=F 空集和母猫求交集还是空集 0XF=0 空集和母猫的并是母猫这个集合: 0+F=F 但有时与传统代数中得到的结果就不太一样了。例如,所有的猫和母猫的并集是所有的 1+F=1 这个表达式在传统代数中是没有意义的 由于F代表母猫的集合,1一F代表所有其他猫的集合,则这两个集合的并集是1: F+(1-F)= 并且它们的交集是0: F×(1-F)=0 历史上,这个公式代表了逻辑中一个十分重要的概念,即矛盾律。它表明一个事物不能 同时是它自己和它自己的反面 使布尔代数和传统代数看起来完全不同的是下面这个表达式 FXF=F 这个式子在布尔代数中有着完美的意义:母猫的集合和母猫的集合的交集仍旧是母猫的 集合。但若F代表一个数字的话,这个公式显然就不对了。布尔认为 是使他的代数与传统代数区分开来的唯一表达式。另一个按照传统代数看起来很有趣的 布尔表达式是

64 编码的奥秘 下载 T + B + W + O = 1 你也可以这样表示所有的猫： N + U = 1 符号1可以用一个减号－来排除一些事物。例如： 1－M 表示除了公猫以外的所有猫。排除公猫以后的全集就是母猫的集合： 1－M = F 我们所需要的另外一个符号是“ 0”。在布尔代数中，“0”表示空集，即不含任何事物的 集合。当求取两个完全相互排斥的集合的交集时，空集就产生了。例如，既是母的又是公的 猫的集合可以表示为： F×M = 0 注意，符号1和0有时的用法与传统代数相同。例如，所有的猫和母猫求交集即是母猫这 个集合： 1×F = F 空集和母猫求交集还是空集： 0×F = 0 空集和母猫的并是母猫这个集合： 0+F = F 但有时与传统代数中得到的结果就不太一样了。例如，所有的猫和母猫的并集是所有的 猫： 1+F = 1 这个表达式在传统代数中是没有意义的。 由于F代表母猫的集合，1－F代表所有其他猫的集合，则这两个集合的并集是 1： F +（1－F）= 1 并且它们的交集是0： F×（1－F）= 0 历史上，这个公式代表了逻辑中一个十分重要的概念，即矛盾律。它表明一个事物不能 同时是它自己和它自己的反面。 使布尔代数和传统代数看起来完全不同的是下面这个表达式： F×F = F 这个式子在布尔代数中有着完美的意义：母猫的集合和母猫的集合的交集仍旧是母猫的 集合。但若F代表一个数字的话，这个公式显然就不对了。布尔认为： X2 = X 是使他的代数与传统代数区分开来的唯一表达式。另一个按照传统代数看起来很有趣的 布尔表达式是：

第0章遵与开关65 下载 F+F=F 母猫和母猫的并集仍是母猫这个集合 布尔代数为解决亚里士多德的三段论提供了一个数学方法。再看看这个著名三段论的两 个前提: 所有的人都是要死的 苏格拉底是人。 我们用字母P代表所有人的集合,M代表要死的东西的集合,S代表苏格拉底。那么,所 谓“所有的人都是要死的”意味着什么呢?它其实表示了所有人的集合和所有要死的东西的 集合的交集是所有的人这个集合,即 而P×M=M这个式子是错误的,因为要死的东西还包括猫、狗、榆树等等。 而“苏格拉底是人”意味着苏格拉底这个集合(非常小)和所有人的集合(很大)的交 集是苏格拉底这个集合 S×P=S 由于从第一个式子中知道P=PXM,所以可以把它代入第二个式子,即: S×(P×M)=S 根据结合律,上式等同于 (S×P)×M=S 但我们已经知道S×P等于S,所以上式可简化为: SXM=S 现在计算完毕。这个表达式告诉我们,苏格拉底和所有要死东西的集合的交集是苏格拉 底,也就是说苏格拉底是要死的。相反,如果认为S×M等于0,那么结论就是苏格拉底不会 死。再如果,若S×M等于M,则能推出的结论就是苏格拉底是唯一会死去的东西,而其他任 何东西都是不朽的! 用布尔代数来证明显而易见的事实似乎有些小题大做(尤其当考虑到苏格拉底早已在 2400年以前就去世了时),不过,布尔代数还可以用来判断一些事物是否满足一定的标准。也 许有一天,你走进宠物店对店员说:“我想要一只阄过的公猫,白的或黄褐色的均可:或者要 只没有生殖能力的母猫,除了白色,其他任何颜色均可:或者只要是只黑猫,我也要。”店 员对你说:“看来您想要的猫是下面的式子表示的集合中的一只 (M×N×(W+T))+(F×N×(1-W))+B 对吗?”你回答道:“是的,完全正确!” 为了证明店员是正确的,你可能想放弃并和交的概念而转向“OR(或者/或)”和“AND (并且/与)”。大写这两个词是因为虽然在通常情况下它们代表语言中的概念,但它们也代表 了布尔代数中的操作。当求两个集合的并集时,你实际上是从第一个集合“或”从第二个集 合中取得事物放入结果集合里。当求两个集合的交集时,满足条件的事物必定在第一个集合 中“并且”也在第二个集合中。此外,每当你看见后跟减号的1,你可以使用单词“NOT(非)

F + F = F 母猫和母猫的并集仍是母猫这个集合。 布尔代数为解决亚里士多德的三段论提供了一个数学方法。再看看这个著名三段论的两 个前提： 所有的人都是要死的； 苏格拉底是人。 我们用字母P代表所有人的集合， M代表要死的东西的集合， S代表苏格拉底。那么，所 谓“所有的人都是要死的”意味着什么呢？它其实表示了所有人的集合和所有要死的东西的 集合的交集是所有的人这个集合，即： P×M = P 而 P×M = M 这个式子是错误的，因为要死的东西还包括猫、狗、榆树等等。 而“苏格拉底是人”意味着苏格拉底这个集合（非常小）和所有人的集合（很大）的交 集是苏格拉底这个集合： S×P = S 由于从第一个式子中知道P = P×M，所以可以把它代入第二个式子，即： S×（P×M） = S 根据结合律，上式等同于： （S×P）×M = S 但我们已经知道S×P等于S，所以上式可简化为： S×M = S 现在计算完毕。这个表达式告诉我们，苏格拉底和所有要死东西的集合的交集是苏格拉 底，也就是说苏格拉底是要死的。相反，如果认为 S×M等于0，那么结论就是苏格拉底不会 死。再如果，若S×M等于M，则能推出的结论就是苏格拉底是唯一会死去的东西，而其他任 何东西都是不朽的！ 用布尔代数来证明显而易见的事实似乎有些小题大做（尤其当考虑到苏格拉底早已在 2 4 0 0年以前就去世了时），不过，布尔代数还可以用来判断一些事物是否满足一定的标准。也 许有一天，你走进宠物店对店员说：“我想要一只阄过的公猫，白的或黄褐色的均可；或者要 一只没有生殖能力的母猫，除了白色，其他任何颜色均可；或者只要是只黑猫，我也要。”店 员对你说：“看来您想要的猫是下面的式子表示的集合中的一只： （M×N×（W + T））+（F×N×（1 - W））+ B 对吗？”你回答道：“是的，完全正确！” 为了证明店员是正确的，你可能想放弃并和交的概念而转向“ O R（或者/或）”和“A N D （并且/与）”。大写这两个词是因为虽然在通常情况下它们代表语言中的概念，但它们也代表 了布尔代数中的操作。当求两个集合的并集时，你实际上是从第一个集合“或”从第二个集 合中取得事物放入结果集合里。当求两个集合的交集时，满足条件的事物必定在第一个集合 中“并且”也在第二个集合中。此外，每当你看见后跟减号的1，你可以使用单词“N O T（非）” 第10章 逻辑与开关 65 下载

66编的奥移 China°o 来表示。小结如下: ·+(以前表示求并集)现在表示OR ×(以前表示求交集)现在表示AND。 1-(以前表示从全集中排除一些事物)现在表示NOT 这样,刚才的表达式可以写成下面的形式: (M AND N AND (WOR T)) OR (F ANDN AND (NOT W))OR B 这与你的口头描述已经十分接近了。注意圆括号是如何清楚地表达出你的意图的。你想 要的猫来自下面三个集合之一: (M AND N AND (WORT)) (F AND N AND (NOT W) B 写下这个公式后,店员就可以进行布尔测试的工作了。别这么大惊小怪的,这里已经悄 悄转移到另一种不同形式的布尔代数中去了。在这种形式的布尔代数中,字母不再只表示集 合,字母还可以被赋予数字,但需要注意的是它们只能被赋予0或者1。数字1表示“是的”、 “正确”,本例中的意思是“这只猫符合我的要求”:数字0表示“否定”、“错误”、本例中即 “这只猫不符合我的要求”。 首先,店员拿出一只未阄过的黄褐色的公猫。下面是满足条件的猫的集合 (M×N×(W+T))+(F×N×(1-W))+B 当用0和1代替字母后就变成了下面的样子: (1×0×(0+1))+(0×0×(1-0))+0 注意被赋予了1的字母只有M和T,因为拿来的这只猫是公的,黄褐色的 现在必须要做的是简化这个表达式。如果简化后表达式的结果是1,这只猫就满足了你的 要求,否则就不是你想要的猫。当简化表达式时,千万记住我们并不是在真正地做加法和乘 法。当+表示OR,×表示AND时,大部分规则是相同的。(现代课本中有时用∧和∨分别表示 AND和OR,而不用×和+;但这里用+和×这两个符号却是恰到好处的。) 当用×表示AND时,可能的结果是 0×1=0 换句话说,只有当×的左、右两个操作数均为1时,结果才为1。这个过程和普通乘法 模一样。若用一张小表总结一下,你会发现它们和第8章的加法表和乘法表的形式相似: AND 0 当用+表示OR时,可能的结果是

66 编码的奥秘 下载 来表示。小结如下： • +（以前表示求并集）现在表示 O R。 • ×（以前表示求交集）现在表示 A N D。 • 1 -（以前表示从全集中排除一些事物）现在表示 N O T。 这样，刚才的表达式可以写成下面的形式： （M AND N AND （W OR T））O R（F AND N AND （NOT W））OR B 这与你的口头描述已经十分接近了。注意圆括号是如何清楚地表达出你的意图的。你想 要的猫来自下面三个集合之一： （M AND N AND（W OR T）） 或 （F AND N AND （NOT W）） 或 B 写下这个公式后，店员就可以进行布尔测试的工作了。别这么大惊小怪的，这里已经悄 悄转移到另一种不同形式的布尔代数中去了。在这种形式的布尔代数中，字母不再只表示集 合，字母还可以被赋予数字，但需要注意的是它们只能被赋予 0或者1。数字1表示“是的”、 “正确”，本例中的意思是“这只猫符合我的要求”；数字 0表示“否定”、“错误”、本例中即 “这只猫不符合我的要求”。 首先，店员拿出一只未阄过的黄褐色的公猫。下面是满足条件的猫的集合： （M×N×（W + T））+（F×N×（1－W））+ B 当用0和1代替字母后就变成了下面的样子： （1×0×（0 + 1））+（0×0×（1 - 0））+ 0 注意被赋予了1的字母只有M和T，因为拿来的这只猫是公的，黄褐色的。 现在必须要做的是简化这个表达式。如果简化后表达式的结果是 1，这只猫就满足了你的 要求，否则就不是你想要的猫。当简化表达式时，千万记住我们并不是在真正地做加法和乘 法。当+表示O R，×表示A N D时，大部分规则是相同的。（现代课本中有时用∧和∨分别表示 A N D和O R，而不用×和+；但这里用+和×这两个符号却是恰到好处的。） 当用×表示A N D时，可能的结果是： 0×0 = 0 0×1 = 0 1×0 = 0 1×1 = 1 换句话说，只有当×的左、右两个操作数均为 1时，结果才为 1。这个过程和普通乘法一 模一样。若用一张小表总结一下，你会发现它们和第 8章的加法表和乘法表的形式相似： A N D 0 1 0 0 0 1 0 1 当用+表示O R时，可能的结果是：

hinapub.com 第10章逻辑与开关 67 下载 0+0=0 0+1=1 1+0=1 当+的左、右操作数中有一个为1时,结果就是1。除了1+1=1这种情况,这种计算和普通 加法产生的结果是一致的。可用另一张小表来总结: OR 0 0 现在可以用这些表来计算前面那个表达式的结果了 (1×0×1)+(0×0×1)+0=0+0+0=0 结果是0,表示“否定”、“错误”,即这只小猫不满足客户需求 接下来,店员拿来一只无生育能力的白色的小母猫。原始表达式是 (M×N×(W+T))+(F×N×(1-W))+B 把0和1代入上式 (0×1×(1+0))+(1×1×(1-1))+0 并且把它简化一下: (0×1×1)+(1×1×0)+0=0+0+0=0 看来,这只可怜的小猫还是不符合要求。 然后,店员又拿来一只无生育能力的灰色的小母猫。(灰色是非白色、黑色或黄褐色的 种其他颜色。)下面是表达式 (0×1×(0+0))+(1×1×(1-0))+0 现在把它简化为 (0×1×0)+(1×1×1)+0=0+1+0=1 最后的结果1表示“是的”、“正确”,这只小猫总算找到新家了! 在你买到小猫的那天晚上,当小猫蜷身睡在你的腿上时,你开始考虑是否能够通过电线 连接一些开关和灯泡来决定哪些小猫满足你的要求。(你真是一个奇怪的家伙。)你丝毫没有 意识到你将要实现一个关键概念上的突破。你要做的是一些试验,这些试验把布尔代数和电 路结合在一起,从而使使用二进制数字工作的计算机的设计和制造成为可能。(可别让这些话 吓着你。) 下面就开始了。你像往常一样把灯泡和电池连接在一起,这一回你用了两个开关

0+0 = 0 0+1 = 1 1+0 = 1 1+1 = 1 当+的左、右操作数中有一个为 1时，结果就是1。除了1 + 1 = 1这种情况，这种计算和普通 加法产生的结果是一致的。可用另一张小表来总结： O R 0 1 0 0 1 1 1 1 现在可以用这些表来计算前面那个表达式的结果了： （1×0×1）+（0×0×1）+0 = 0 + 0 + 0 = 0 结果是0，表示“否定”、“错误”，即这只小猫不满足客户需求。 接下来，店员拿来一只无生育能力的白色的小母猫。原始表达式是： （M×N×（W + T））+（F×N×（1－W））+ B 把0和1代入上式： （0×1×（1 + 0））+（1×1×（1 - 1））+ 0 并且把它简化一下： （0×1×1）+（1×1×0）+ 0 = 0 + 0 + 0 = 0 看来，这只可怜的小猫还是不符合要求。 然后，店员又拿来一只无生育能力的灰色的小母猫。（灰色是非白色、黑色或黄褐色的一 种其他颜色。）下面是表达式： （0×1×（0 + 0））+（1×1×（1 - 0））+ 0 现在把它简化为： （0×1×0）+（1×1×1）+ 0 = 0 + 1 + 0 = 1 最后的结果1表示“是的”、“正确”, 这只小猫总算找到新家了！ 在你买到小猫的那天晚上，当小猫蜷身睡在你的腿上时，你开始考虑是否能够通过电线 连接一些开关和灯泡来决定哪些小猫满足你的要求。（你真是一个奇怪的家伙。）你丝毫没有 意识到你将要实现一个关键概念上的突破。你要做的是一些试验，这些试验把布尔代数和电 路结合在一起，从而使使用二进制数字工作的计算机的设计和制造成为可能。 (可别让这些话 吓着你。) 下面就开始了。你像往常一样把灯泡和电池连接在一起，这一回你用了两个开关： 第10章 逻辑与开关 67 下载

68编的奥移 China°beM 开关这种方式的连接一一个在另一个的右边—称为串联的。如果你闭合了左边的开关 什么也不会发生 同样,如果你让左边的开关断开而闭合右边的开关,结果还是一样。只有当左右两个开 关都闭合时,灯泡才会发光,如下所示 这里的关键是“都”。只有左边和右边的开关都闭合时,电流才能流过回路。 这个电路执行了一个逻辑运算。事实上,灯泡回答了这个问题:“两个开关都处于闭合状 态吗?”可以把电路的工作总结为下面这张表 右开关状态 灯泡状态 不亮 闭合 断开 不亮 在前一章中,我们已知道二进制数字(或“位”)是如何表示信息的:它可以表示从最普通 的数字到 Roger ebert的拇指方向等的一切事情。可以说“0”代表“ Ebert拇指向下的方向”,而 “1”表示“ ebert拇指向上的方向”。一个开关有两个位置,所以它可以代表一个位。“0”表示 “开关是断开的”,而“1”表示“开关是闭合的”。一个灯泡有两种状态,所以它也可以表示 个二进制位。“0”表示“灯泡不亮”而“1”表示“灯泡亮”。现在可以把上面的表简化一下: 左开关状态右开关状态灯泡状态 011 000 注意,如果交换左、右开关,结果是一样的,所以没必要指明哪个开关是左开关或右开 关。因此这张表可以重画成类似于前面“AND”表和“OR”表的样子

68 编码的奥秘 下载 开关这种方式的连接—一个在另一个的右边—称为串联的。如果你闭合了左边的开关， 什么也不会发生： 同样，如果你让左边的开关断开而闭合右边的开关，结果还是一样。只有当左右两个开 关都闭合时，灯泡才会发光，如下所示： 这里的关键是“都”。只有左边和右边的开关都闭合时，电流才能流过回路。 这个电路执行了一个逻辑运算。事实上，灯泡回答了这个问题：“两个开关都处于闭合状 态吗？”可以把电路的工作总结为下面这张表： 左开关状态 右开关状态 灯泡状态 断开 断开 不亮 断开 闭合 不亮 闭合 断开 不亮 闭合 闭合 亮 在前一章中，我们已知道二进制数字（或“位”）是如何表示信息的：它可以表示从最普通 的数字到Roger Ebert的拇指方向等的一切事情。可以说“0”代表“E b e r t拇指向下的方向”，而 “1”表示“E b e r t拇指向上的方向”。一个开关有两个位置，所以它可以代表一个位。“0”表示 “开关是断开的”，而“1”表示“开关是闭合的”。一个灯泡有两种状态，所以它也可以表示一 个二进制位。“0”表示“灯泡不亮”而“1”表示“灯泡亮”。现在可以把上面的表简化一下： 左开关状态 右开关状态 灯泡状态 0 0 0 0 1 0 1 0 0 1 1 1 注意，如果交换左、右开关，结果是一样的，所以没必要指明哪个开关是左开关或右开 关。因此这张表可以重画成类似于前面“ A N D”表和“O R”表的样子：

Chinapub.com 第0假与开关69 下载 关串联0 0 事实上,这和“AND”表是一样的。让我们检查一下: 0 这个简单的电路实际上执行了布尔代数的“AND”操作。 现在试着用另一种方式连接电路: 这些开关称为并行连接。它和前一种连接方式的区别是,如果闭合了上面的开关,灯泡 如果闭合了下面的开关,灯泡会亮

开关串联 0 1 0 0 0 1 0 1 事实上，这和“A N D”表是一样的。让我们检查一下： A N D 0 1 0 0 0 1 0 1 这个简单的电路实际上执行了布尔代数的“ A N D”操作。 现在试着用另一种方式连接电路： 这些开关称为并行连接。它和前一种连接方式的区别是，如果闭合了上面的开关，灯泡 会亮： 如果闭合了下面的开关，灯泡会亮： 第10章 逻辑与开关 69 下载

70编码的奥 如果同时闭合上、下两个开关,灯泡还是会亮: 可见,当上面或下面的开关有一个闭合时,灯泡就会亮。这里的关键字是“或”。 这个电路也执行了一个逻辑运算,灯泡回答了这样一个问题:“是否有开关闭合?”下面 的表总结了这个电路是如何工作的 上开关状态下开关状态 灯泡状态 打开 打开 不亮亮亮 仍然用“0”表示开关断开或灯泡不亮,用“1”表示开关闭合或灯泡亮。这张表可以这 上开关状态 下开关状态 灯泡状态 0 0 0101 同样,这两个开关交换位置也没关系,所以这张表可以重写成如下的样子 开关并联0 你可能已经猜到了这和布尔代数中的“OR”表是一样的 0 这意味着两个并联的开关执行的是和布尔一样的操作 当你再进入宠物店时,你告诉店员:“我想要一只阄过的公猫,白的或黄褐色的均可:或 者要一只没生育能力的母猫,除了白色,其他任何颜色均可:或者只要是只黑猫,我也要。” 店员便得到了如下的表达式:

如果同时闭合上、下两个开关，灯泡还是会亮： 可见，当上面或下面的开关有一个闭合时，灯泡就会亮。这里的关键字是“或”。 这个电路也执行了一个逻辑运算，灯泡回答了这样一个问题：“是否有开关闭合？”下面 的表总结了这个电路是如何工作的： 上开关状态 下开关状态 灯泡状态 打开 打开 不亮 打开 闭合 亮 闭合 打开 亮 闭合 闭合 亮 仍然用“0”表示开关断开或灯泡不亮，用“ 1”表示开关闭合或灯泡亮。这张表可以这 样： 上开关状态 下开关状态 灯泡状态 0 0 0 0 1 1 1 0 1 1 1 1 同样，这两个开关交换位置也没关系，所以这张表可以重写成如下的样子： 开关并联 0 1 0 0 1 1 1 1 你可能已经猜到了这和布尔代数中的“ O R”表是一样的： O R 0 1 0 0 1 1 1 1 这意味着两个并联的开关执行的是和布尔一样的操作。 当你再进入宠物店时，你告诉店员：“我想要一只阄过的公猫，白的或黄褐色的均可；或 者要一只没生育能力的母猫，除了白色，其他任何颜色均可；或者只要是只黑猫，我也要。” 店员便得到了如下的表达式： 70 编码的奥秘 下载