人类的历史可以看做一部关于解放的历史。也有这样的说法，懒惰是人类进步的动力。为了偷懒，人类不断的做着各种努力，发明了各种机器工具，将自己从繁重的劳动解放出来，另一方面，每一次大的进步，都需要解放思想，同时也带来了全人类思想的大解放。在这样的历程中，计算机的出现无疑将人类从很多繁重的作业中解放了出来。与此同时，有些人开始思考能否制造出可以像人类一样进行思考的机器，以将人类从创造性的劳动和逻辑思考中解放出来，交给机器去完成。虽然计算机的出现，不到百年，然而为了它的出现，所进行的探索和研究，早已经历经数百年的历史。当然准确的说，这些探索和研究在当时实际并不是为了计算机产生而进行的，绝大多数只是做了一个无意的铺垫。或许我们并不熟悉这样的一个过程，老实说现代的大学教育中也很少提及计算机出现之前的那些历史。实际上，了解这样的一个过程，更有助于我们理解一个事物是如何产生出来，它背后的科学原理又是如何，让我们可以透过复杂的电路外表，接触到最本质的东西。可以让我们除了对科学家们的工作表示赞叹之外，也可以深入他们当初的思想过程，近距离地进行跨越时间和空间的沟通。这对于我们自己应该如何思考问题，创造性地提出自己的想法也是有所帮助的。实际上在离散数学的学习中，我们已经了解到这样的一些人物，乔治.布尔,康托，哥德尔，图灵，冯诺依曼。而我们的离散数学的教学中，本身太注重于知识本身的学习，而忽略了知识是如何被发现产生出来，以及不同的知识之间曾经的渊源和启发关系。而对于启迪思想来说，后者显然更为有力。早在17世纪的莱布尼茨就有一个伟大的构想，他希望可以将人类的思维像代数运算那样符号化，规则化，从而让笨的人通过掌握这样的规则变得聪明，更进一步的制造出可以进行思维运算的机器，将人类从思考中解放。从莱布尼茨为微积分所确定的依然在今天被沿用的符号中，我们可以看出他对符号具有良好的感觉，通过选择良好的符号，可以大大的简化运算的复杂性，甚至将这样的运算变成一种天然的过程。除了构想之外，莱布尼茨本身为了发展一种逻辑演算也进行了很多尝试，他得到的一些结果已经具有后来布尔的逻辑代数的雏形。19世纪的布尔，将逻辑代数化，发展出了逻辑代数成为后来计算机内部运算的逻辑基础。在早期的研究中，布尔就已经认识到符号的力量，代数的力量正源于代表着量和运算的符号在几条基本规则的支配下体现出来的。后来，他开始思考能否将逻辑推理也像代数那样用符号和几条基本规则就可以完全表达。他开始思考我们通常所说的某物具有某种性质，可以用一个类来表示，比如白的是x，绵羊是y，那么白绵羊就可以用xy来表示，这样日常生活中的概念开始具有代数的形式，用现代的术语来说上面的xy表示的正是交集。他又继续思考，xx表示什么呢，他发现xx与我们普通的代数运算不同xx依然表示的是x。xx=x实际上成为布尔的逻辑代数的一个基本规则。继续考虑下去，如果xx=x在普通的代数中意味着什么呢？xx=x，意味着x=1或者0.可以看到如果xx=x作为逻辑代数的基本规则，放在普通代数中意味着x=0或者1，那么逻辑代数是否意味着是01的普通代数呢。于是布尔得到一个基本原理，如果仅仅限于01，逻辑代数就变成了普通代数。关于这一点的思考，对于二进制运算的在逻辑代数中的主导作用具有很大的启发意义。如果限于01，那么01在我们的逻辑代数中代表的意思又是什么呢。我们之前看到可以用x表示某个类，对应地那么0可以解释成没有任何东西属于它的类，1可以解释成包含所有对象的全体。同时布尔又开始考虑普通代数中的+-在逻辑代数中的意义，x+y可以表示具有x和y两种属性的对象集合，x-y表示具有x属性同时不具有y属性的对象集合。考虑了这样的一些意义之后，接下来再看xx=x=> x-xx = 0 => x(1-x) = 0
现在我们以逻辑代数的观点看这个式子，它体现了这样一个含义：没有任何东西可以同时属于又不属于某个类。这点让布尔十分振奋，因为这刚好体现了亚里士多德的排中律，这就使他确信自己找对了路子。继续下去，布尔发现三段论也可以用他的逻辑代数来表达。所有x都是y x=xy(x中的任何东西也属于y，就等于说没有任何东西是属于x而不属于y的，也就是说x(1-y)=0)
所有y都是z y=yz
------------ ?
所有x都是z x=xz
x=xy
y=yz => x = xy = x(yz) = (xy)z = xz
最后，'如果x，那么y。'可以用x(1-y)=0来表示,可以这样理解这个式子意味着如果x=1，那么y=1。在这里一方面我们可以把'如果x，那么'理解为等同于前面的这样一句话'所有的x都是y',当然这两者有一个区别，现在的x，y表示的是命题，而原来的x，y表示的则是类概念。以今天的观点来看，前者是命题演算，后者是谓词演算。但是如果从另一个方面，重新考虑这句话，比如x=1表示命题x为真，x=0表示命题x为假，xy=1表示x且y，只有x，y均为1，xy=1，如果x=0或y=0，xy=0，这点又与普通代数相一致。从这个方向思考下去，就可以看到今天的布尔代数的基本面貌了，上面的这个定义正是与运算。布尔的逻辑体系，不仅包含了亚里士多德的逻辑体系，而且还超越了它，但是仍有无法表达的情形：所有失败的学生或者是糊涂的或者是懒惰的。回到今天，我们再看布尔再把逻辑转变成代数的过程中，所产生的逻辑代数在今天的计算机中扮演着什么样的作用。布尔代数只有1和0两个元素，not and or三种运算，用几张真值表就可以表达清楚。
这张表说明如果 AND 运算的两个元素有一个是 0，则运算结果总是 0。如果两个元素都是 1，运算结果是 1。例如，“太阳从西边升起”这个判断是假的(0),“水可以流动”这个判断是真的（1），那么，“太阳从西边升起并且水可以流动”就是假的（0）。
这张表说明如果OR运算的两个元素有一个是 1，则运算结果总是 1。如果两个元素都是 0，运算结果是 0。比如说，“张三是比赛第一名”这个结论是假的（0），“李四是比赛第一名”是真的（1），那么“张三或者李四是第一名”就是真的（1）。
这张表说明 NOT 运算把 1 变成 0，把 0 变成 1。比如，如果“象牙是白的”是真的（1），那么“象牙不是白的”必定是假的（0）。如此简单的运算，实际上当时的布尔也不会想到它会被运用到计算机中，直到1938 年香农在他的硕士论文中指出用布尔代数来实现开关电路，使得布尔代数成为数字电路的基础。所有的数学和逻辑运算，加、减、乘、除、乘方、开方等等，全部能转换成二值的布尔运算。弗雷格的一生主要发表了这样三本著作：《概念演算--一种模仿算术语言构造的纯思维的符号语言》（1879）、《算术的基础--对数概念的逻辑数学研究》（1884）《算术的基本规律》（l卷 1893，2卷1903）。其中概念演算，将普通数学中的一切演绎推理都包含在内，成为第一个完备的逻辑体系。布尔以普通代数为基础，用代数符号来表示逻辑关系。与此相反，弗雷格想以他的逻辑为基础而把代数构造出来。实际上这成为日后一个重要的学派'逻辑主义',在他们看来逻辑与数学的关系就像一门学科的基本部分和高等部分之间的关系。弗雷格的逻辑体系，表现在今天就是我们数理逻辑中的命题演算和谓词演算(用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑)。弗雷格第一次用精确的句法构造出形式化的人工语言，使得逻辑推理表示为机械演算即所谓的推理规则成为可能。从这个观点看，概念文字是我们今天使用的计算机程序设计语言的前身。弗雷格希望可以自然数提出一种纯粹逻辑的理论，从而证明算术，微积分乃至一切数学都可以看成逻辑的一个分支。于是弗雷格便希望可以用纯逻辑的术语来定义自然数，然后再用他的逻辑导出它们的性质。例如3这个数将被解释为逻辑的一部分。弗雷格的思想是把3定义为所有元素数为3的集合的集合。实际上这就是《算术的基础--对数概念的逻辑数学研究》这部著作的主要内容。然而正是这样的一些工作，1902年，年轻的伯特兰.罗素据此提出那个著名的罗素悖论。弗雷格的算术使用了集合的集合这样一种概念。罗素指出，用集合的集合进行推理很容易导致矛盾。罗素的悖论可以这样描述：如果一个集合是它自身的一个成员，那么就把集合成为异常的，否则它就是正常的。那么由所有正常集合组成的集合是正常还是异常的呢？如果是正常的，那么它应该包含自身，这样它就应该是异常的。如果是异常的，那么它就不会包含自身，这样它就应该是正常的。无论哪个结果都导致了矛盾。实际上罗素构造这个悖论的方法，与之后哥德尔，图灵构造不可判定命题却有着神似的地方。然而这一矛盾却表明弗雷格构造的算术体系所基于的那些前提是靠不住的，并给弗雷格带来了巨大的打击。虽然弗雷格的逻辑已经很完备，但仍然具有一些局限性。他的规则并没有提供判定某个结论能否从给定的前提中推导出来的计算步骤。另外能否找到一种计算方法，它能够说明在弗雷格的逻辑中某一推理是正确的呢？其结果是这样一则证明：没有这样的一般方法存在。然而正是在证明这样一条否定性的结论过程中，阿兰图灵发现原则上可以设计出一种通用机，它可以执行任何可能的计算。弗雷格的研究开启语言哲学的大门，后来人们在寻找证明逻辑推理正确性的过程中，图灵发现了通用机，也就是今天计算机的数学模型。康托尔进入无限的世界，开始无限的数目的研究。他发现自然数与实数具有不同的基数，以及由此提出的连续统假设，即实数和自然数之间不存在具有其他基数的集合。这也是1900年，希尔伯特提出的23个问题中的第一问题。这个问题直到今天并未完全解决，1938年哥德尔和1963年保罗科恩的重大发现表明，如果连续统假设问题可以被解决，就必须超越普通数学的方法。对于我们普通人来说，最有用的大概是康托尔在证明实数与自然数基数不同的过程中所采用的对角线方法，这种方法是1891年，康托尔在一篇4页的论文中发表的。而对角线方法，在以后的故事中仍然会被用到，它将会被哥德尔用来解决一致性问题时构造系统内不可证命题，然后阿兰.图灵又再次使用了哥德尔的方法构造出了不可判定命题。而关于连续统假设的研究也引发了关于图灵机的构想。现在我们可以看到康托尔的工作与计算机的起源在这里产生了联系。关于对角线方法，我们从自然数集来看，我们可以发现自然数与自然数的子集组成的集合之间具有不同的基数，假设我们把自然数与不同的自然数子集建立一个对应关系，1: M1 2: M2....，采用对角线方法，我们总是可以构造出一个新的自然数集，它没有任何自然数与之对应，我们这样产生这个新的自然数集：如果i属于Mi,那么排除i，否则包含i，容易看到这样产生的一个集合不同于任何的Mi。可见由一切自然数集组成的集合的基数要大于自然数的基数。实际上康托尔并不是第一个关注到无限的数目特殊性的人，早在17世纪，莱布尼茨就发现偶数和自然数是一一对应的，正如他所说：对于任何一个数，都存在一个与之对应的偶数，那就是它的二倍。因此所有数的数目并不比偶数的数目更多，也就是说整体没有部分大。但是他得出了这样一个结论：所有自然数的数目这一概念是不一致的，讨论一个无限集中元素的数目是没有意义的。但是康托了选择了另一条路，他承认某些无限集将与它的一个子集具有相同的元素数目。正是基于这样一个大胆的选择，他才创立了关于无限的新理论。当康托尔提出这些观点之后，立刻引来了各方面的责难。与弗雷格类似，人们发现用康托尔的超限数进行不加限制的推理会导致荒谬的结果。比如如果存在一个由所有基数组成的集合，那么它的基数该是多少呢？它必须比所有基数都大，但一个基数又怎么可能比所有基数都大呢？后来罗素又指出这样的一个问题：是否存在一个所有集合的集合？如果存在，那么倘若把对角线方法应用于它，会出现什么结果？这样我们会得到一个不同于所有那些已经拥有标签的集合的集合。正是在考虑这种情况时，罗素发现他那个关于由一切不是自身的集合组成的集合的著名悖论，也就是他向弗雷格传达的那个悖论。这里我们看到，弗雷格和康托尔之间被罗素悖论联系起来。而关于这个悖论的讨论和思考，则引发了数学史上的第三次危机。
来源：中国科学院数学与系统研究院，本文仅用于学术分享，版权属于原作者。若有侵权，请联系微信号: 1306859767，Eternalhui， 删除或修改！
