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 下载