离散数学步步笔记

离散数学里有无数的定义、概念、性质，在学习的过程中，就是看书、背公式、做题，很难知道为什么会有这些公式，它们能用在哪里。问别人的时候，他们往往也不知道，“只要记住就行了”，“想那么多干什么”。

也许自己坚持学完，以后用上的时候，才会明白每个概念和公式出现的理由，但是在学习的过程中，如同在迷雾中摸索，不知道路在何方，真担心自己什么时候就会迷路放弃。

我认为某个概念的出现一定是有意义的，每一个章节与前面的知识都是有联系的。所以我边学习边记录下自己的思考，虽然可能不正确，但这没关系，等以后想明白的时候再补上。也希望大家可以纠正我的错误。

我使用的教材是“离散数学”耿素云，屈婉玲编著的那本：http://book.douban.com/subject/1231190/

全书分为四章，分别是：

数理逻辑2. 集合论3. 代数结构4. 图论

我现在看完了数理逻辑，正在看集合论，进展比较慢。

数学是不断抽象的过程，一层层的抽象，不断提高思考层次。这个过程如同盖楼，在不同的层次，考虑的东西也不同。

第一层：原子、分子。考虑化学反应、物理特性2. 第二层：沙子、泥土、水泥、钢铁、木材。考虑材料性质、硬度、粘性、脆度、热胀冷缩，原料来源、价格、成本等3. 第三层：砖、瓦、板、钢筋。考虑形状、颜色、尺寸，能否批量生产，是否满足标准4. 第四层：房屋、公路、铁路、桥、广场。考虑要实现的功能、风格，建筑力学，抗震、防火，成本、价格。5. 第五层：城市规划、社区、商圈、公园。考虑交通、经济、人口、政策、未来发展等6. 第六层：……

在每一层，需要考虑的东西都是独特的，各不相同。但它们都要依赖低一层的基础，借用其研究成果。如果低一层的特性改变了，高一层能实现的目标和表现形式也会不同。

离散数学也是一样，一层一层累积起来。

一、命题与联结符

首先是数理逻辑中关于“命题与联结符”，它们就是原子、分子，是后面的基础。命题是可以判断出真假的陈述句，可分为前提和结论。仅仅五个联结符“”就描述了各个前提与结论之间的关系。此时每个前提都是独立的，有自己的真或假，彼此之间互不依赖，只能通过联结符运算提出结论是真是假。

为什么会选择这五个联结符？为什么不是四个或者六个？为什么是这五个而不是别的五个呢？我想之所有选择这几个，是因为它们很符合我们的日常表达习惯：并且，或者，不是，因为所以，还有一个不常用但比较重要的“当且仅当”。

通过“联结词的完备集”那一章，我们可以看到，要实现这五个联结词要表达的内容，实际上只需要其中的几个就可以了，剩下的都可以推出来：

但这样的话，虽然理论上可以表达，但与我们直觉及语言习惯相差太远，或者表达不方便，增大了学习和表达的难度。选择这五个“”应该是综合了多种考虑之后的最优选。

但这五个联结论，也并不是完全与语言中的“并且，或者，不是，因为所以”完全对应的。因为语言是很灵活的，在不同的语境及习惯用语中，使用的是同一个词，而实际上要表达的意思却对应了不同的联结词。所以，在把语言化的命题用符号表示时，需要根据每一个联结词的定义，重新组织语句，让他们可以对应起来。同时，为了让这几个联结词有着明确和精确的定义，使用了真值表，使得它们的表达没有任何歧义。

这几个联结词中，蕴含符让我想的不太明白。它对应了语言中的“因为，所以”，“如果，则”，但实际上并不完全相同。在生活中，“因为”与“所以”之间表达的内容，是有联系的，比如“因为我饿了，所以我去吃饭了”，但在命题逻辑中，前件与后件间可以没有任何关系，比如“我饿了下雪了”。命题逻辑中，每个前提、结论之间都是独立的，它们之间没关系。命题是真是假，仅仅由每个前提与结论的真假和它们之间的联结符确定。你可以把它们看作一张张没有感情的真值表，每一个前提都变成了冰冷的0和1，各联结符如同一个个开关，拨来拨去，最后灯亮或者灯灭。

还有，这个命题，当p为假时，不管q如何，命题为真。这个让我一开始很难想明白，因为在生活中，当我说“因为”什么，或者“如果”什么，当这个前提不成立的时候，结果应该不成立才对，但为什么命题是真呢？

这是因为混淆了“命题为真”和“结论为真”。当p为假时，命题为真，但并没有说结论q是真是假。实际上在生活中很多时候，我们很少考虑前提为假的情况，大都考虑的是前提为真时，结论是否成立。但在命题逻辑中，结论、前提之间是独立的，考虑的也是整个命题的真值。把定义为“p为假时，命题为真”是有意义的，因为在后面的一阶逻辑中，这种定义，可以让表达很符合我们的直觉。这点在后面说。

从上面可以看到，命题逻辑既和生活的逻辑有关系，但又不一样，它更加准确、考虑的范围更小、更确定。可以说是“源于生活，高于生活”。它与计算机对应得很好，因为计算机仅有0和1这两个状态，而命题逻辑研究的也只有“假”和“真”这两个状态，门当户对。

在命题逻辑，事物之间没有关系。如果以生活在地球上的人类来打比方，“命题逻辑”就像在高空中俯视，只能看到一个个的人。实际上人与人之间还有各种关系，比如家庭、朋友等等，但“命题逻辑”是不关心的。

这显然不够，所以在后面提出了“一阶逻辑”和“谓词”的概念。

二、一阶逻辑与谓词

从上面的“命题逻辑”可以看出，它研究的都是孤立的事物，不能很好地表达事物的性质和事物间的关系。比如“人都要吃饭，小明是人，所以小明要吃饭”。这样的命题，使用前面的命题逻辑是无法判断结论是否正确。

为了能推理这样的命题，提出了“谓词”这个概念。谓词表示一个事物怎么样，或者多个事物之间有什么关系。它是很重要的一个词，在后面经常会用到。

还提出了“量词”的概念，一个是“全部”，一个是“存在”，这样就可以表示上面的命题了。

设个体域为“全总个体域”，即“宇宙间一切事物”。F(x)表示“x是人”，G(x)表示“x要吃饭”。上面的命题可表示为：

前提：

结论：

即“对于宇宙间的一切事物，如果它是人，则它要吃饭。因为小明是人，所以小明要吃饭”。

这里要提到的定义了。前面说，，当p为假时，命题为真。可以看到，这种定义很适合这里的推理。因为对于宇宙间的一切事物来说，x可能是人，也可能不是人，则F(x)可能为真，也可能为假。当F(x)为真（即x是人时）好处理，直接看G(x)是否为真即可。但当F(x)为假（即x不是人时），应该怎么办呢？简单的办法就是让命题为真，即：F(x)为假时，不应该影响命题的真假。