Coursera 离散数学概论笔记：第一周

数学的出现是基于计量的需要；但随着人类社会的发展，对数学的要求也越来越严格。从某种角度来说，数学是由危机来推动其发展的：

1. 第一次数学危机：无理数无法用数轴表示，导致了欧几里得的公理体系与亚里士多德的逻辑体系（三段论）的诞生。（告诉我们直觉和经验是不可靠的！）
2. 第二次数学危机：芝诺悖论，无穷小的问题（阿基里斯追不上乌龟），导致了连续的定义，极限理论的产生，并由此产生了实数理论的严格基础（集合论 / 数理逻辑）
3. 第三次数学危机：罗素悖论，理发师困境，导致了公理化集合论的诞生，以及不完全定理的产生。

上述历史告诉我们，数学发展到今天，已经形成了一种严谨的、基于已知公理体系的、推理和演绎的过程。在形成数理逻辑这一套体系之前，人类采用自然语言（逻辑学）来探索、阐述、和确定有效推理规则。但由于自然语言描述逻辑会因为其本身的模糊性损害其准确性和权威性，因此，我们需要一种更加规范的推理过程来代替自然语言。这就是数理逻辑，一种利用计算代替逻辑推理的方法。

数理逻辑产生于 1847 年，英国数学家乔治·布尔（George Boole）的著作《逻辑的数学分析》。该著作建立了布尔代数系统，而这套系统使用了符号来表示逻辑中的各种元素，从而实现了利用代数的方法研究逻辑的问题。而在之后的德国数学家戈特洛布·弗雷格（Gottlob Frege）（谓词） 和 查理斯·皮尔斯 （Charles Peirce）分别对这套系统进行了改进。他们的贡献使得数理逻辑逐渐的形成了自身的理论系统，称为了一门独立的学科。

数理逻辑主要分为四大分支：

• 公理集合论：用于研究集合论的无矛盾问题
• 证明论：研究无矛盾问题促生的需求，需要以数学理论体系的概念、命题、证明 等作为研究对象，研究数学系统的逻辑结构和证明的规律。
• 递归论：研究可计算性的理论，与计算机有密切的关系。
• 模型论：研究形式系统与数学模型之间的关系。

命题是数理逻辑中最基本的概念，是对确定对象作出判断的陈述句。其具有以下三个特点：

• 确定的对象
• 判断
• 陈述句

三个对象只要缺少了一种，就不能构成命题。比如：

• 请把脚挪一下！（祈使句，不构成命题）
• $x + y = 10$ （对象是变量，不构成命题）

每一个命题都有一个属性：真值（Truth value），即代表了该命题为真的情况。因此，悖论是无法称之为命题的，因为它不具有真值。

因为真值是唯一的，因此命题只有两种情况：真或者假，即任何命题在同一时间内都只能具有独一的属性。该定律下有一种著名的应用：反证法：即证明一个命题为真，并不直接证明，而是假设该命题为假，通过排中律来判断该命题非假，从而得出命题是真的手段。著名的例子有：欧几里得证明素数有无穷多个。

直观主义者认为：数学的基础和出发点是基于人类的直觉而构造的， 数学理论可靠性依赖于心智上的可构造性。因此，对命题真假的确定必须给出构造性证明。而反证法虽然对命题的反面推出矛盾， 但不意味着命题本身具有构造性证明。也就是说，在直观主义者眼里，排中律并没有普遍有效性；排中律只能应用于在已知事物的范围，而不能贸然的推广到对无穷事物的应用。已知事物是有穷的，可以通过穷举来验证；但无穷的事物并不能通过穷举来验证（哥德巴赫猜想）。

命题是通过基本的元素加上联结词来形成的。基本的元素也被称为命题，我们称之为原子命题（Atom proposition）。因此，由此我们可以得到一些概念：

• 原子命题（Atom proposition）:不含有逻辑连接词的命题，是命题的基本组成部分。
• 逻辑联结词（Logical connectives）：连接命题，对真值进行计算的词（可以想象为运算符）。
• 复合命题（Compound proposition）：由原子命题和逻辑联结词组成的命题。

我们可以通过不同的联结词来指定不同的新复合命题，从而达到对逻辑和思维进行形式化的目的。那么要如何形式化呢？

形式化大致可以分为以下几步：

1. 抽象（Abstraction）：抛弃所有自然语言的内涵，仅关注逻辑联结词的本质–对真值的运算。
2. 将命题的元素以符号的形式表达出来
   1. 原子命题可以使用 p、q、w、s 表示。
   2. 真 / 假命题用 T / F 表示。
   3. 逻辑联结词可以用特殊符号来表示：
      1. 并非(not): $¬$
      2. 并且(and): $∧$
      3. 或(or):$∨$
      4. 蕴含（如果….那么… / if…then…）$→$
      5. 双蕴含（当且仅当 / if and only if）$↔$

逻辑联结词是由真值表来定义的。真值表代表了所有原子命题的真值组合的结果，以及通过联结词作用有的命题的真值结果。

联结词主要分为 5 种：

• 否定词（Negation）:并非(not): $¬$
• 合取词(Conjunction) “并且”(and): $∧$
• 析取词(Disjunction)”或”(or):$∨$
• 蕴涵词(Implication)”如果…那么…”(if…then…): $→$
• 双向蕴含词(Two-way implication)”当且仅当”(if and only if):$↔$

否定词的逻辑关系表示为：$¬p$，即 p 不成立。用自然语言举例说明则是：

p:雪是白的
¬p:雪不是白的

p:天鹅是白的
¬p:天鹅不都是白的（而不是天鹅都不是白的）

合取词的逻辑关系表示为 $p∧q$，即 p 与 q 都成立。自然语言中有一些固定的结构都可以符号化为合取词，比如：

即...又...
不但...而且...
虽然...但是...

p:张三聪明
q:张三用功 
p∧q:张三既聪明又用功
¬p∧q:张三虽然不太聪明
p∧¬q:张三不是不聪明，而是不用功

析取词的逻辑关系表示为 $p∨q$，即 p 和 q 中至少一个成立。

需要注意的是，析取词分为两种情况：相容或 $⊙$（同或）、排斥或 $⊕$（异或）:

相容或代表了两个条件可以选择，但也有同时具备两个条件的情况，比如：

李四学过德语或者法语
李四学过德语 \ 李四学过法语 \ 李四学过德语和法语

人固有一死，或重于泰山，或轻于鸿毛
人死要么重于泰山 / 要么轻于鸿毛

</html>

蕴涵词的逻辑关系表示为 $p→q$，即 p 是 q 的充分条件，或者说 q 是 p 的必要条件。如果事件 p 发生必导致事件 q 发生，则称 p 蕴含了 q。在 $p→q$ 中， p 称为蕴含前件，q 称为蕴涵后件。

一些可以作为蕴含关系的连词如下：

只要…就…
如果…那么…
只有…才… //“只有”是“才”的必要条件，因此只有后面的条件是 q，才后面的条件是 p。

如果天气好，那么我去接你
p: 天气好
q: 我去接你
天气好，但我不去接你，那么就是食言了 // p→q: false

双向蕴含词的逻辑关系表示为 $p↔q$，即 p、q 互为充分必要条件。当 p、q 真值相同的情况下， $p↔q$ 为真，即真的只能推断出真的，假的只能推断出假的，比如：

圆1和圆2面积相等当且仅当它们的半径相等
两个圆的半径相等，因此可以推出两个圆面积相等
两个圆半径不相等，英雌可以推出两个圆面积不相等

上述的联结词加上原子命题，通过一定的顺序联结起来，可以组成复合命题。如果我们将这样的复合命题当做成一个算式，那么该复合命题就可以称作命题公式（Proposition formula）。

如果把复合命题作为公式，那么联结词就相当于是公式里的运算符了。那么公式里的原子命题，就可以当做是公式里的常量或者变量了。因此，一个命题公式的组成可以分为以下三个部分：

• 命题常元（Proposition constants）
• 命题变元（Proposition variables）
• 逻辑运算符

命题常元和命题变元被称为原子公式。而对于命题公式的定义有如下两个规则：

1. 如果A,B是命题公式，那么 $(¬A), (A∧B), (A∨B), (A→B), (A↔B)$ 也是命题公式
2. 只有有限步引用上述两条所组成的符号串是命题公式

命题公式采用大写 $A,B,C$ 等表示。

严格意义上的命题公式还有一个条件：必须使用括号保证运算的优先级。因此，以下的式子都不是命题公式：

(qp) //没有联结词
(p1∧(p2∧…//括号不完整
p→r∧s//没有括号

1. 公式最外层的括号可以省略
2. 提前约定逻辑联结词的优先级：$¬, [∧∨], →, ↔$ （从左到右，从高到低）

如果把逻辑联结词看作是运算符，那么包含命题变元 $p_1,p_2, ....p_n$ 的公式 $A$ 实际上就可以看做是一个函数，一个关于变量 $p_1,p_2, ....p_n$ 的真值函数。既然是真值函数，那么得到的结果一定是一个真值。因此，该函数的自变量和因变量的取值范围都是 $[0, 1]$。

既然 $p_1,p_2, ....p_n$ 表示真值函数的变量，那么对于每一种 $p_1,p_2, ....p_n$ 的取值组合，就被称为赋值 （Assignments）。赋值有需要注意的地方：

• 赋值用希腊字母 $α,β$ 等表示
• 对于每个赋值，公式 $A$ 均有一个确定的真值，该真值由真值表定义
• 对于有 $k$ 个联结词的命题，其真值表是一个 $2n *(k+n)$ 的矩阵，前 $n$ 列是所有变元的取值组合，最后一列是该公式 $A$ 的真值。

对应的赋值有对应的真值。当赋值 $\alpha$ 导致公式 $A$ 为真时，则称 $\alpha$ 是 $A$ 的成真赋值，记做 $\alpha(A) = 1$，反之，则称 $\alpha$ 是 $A$ 的成假赋值，记做 $\alpha(A) = 0$。

我们是这样将自然语言转变为命题公式的：

1. 确定原子命题
2. 确定联结词
3. 处理命题之间的联结关系及顺序

一些相关的例子如下：

我和他既是兄弟又是同学(p:我和他是兄弟，q:我和他是同学) //形式化命题:p∧q
//-------------------------//
狗急跳墙(p:狗急了，q:狗跳墙) //形式化命题:p→q
//------------------------//
无论是否下雨，我都去上学(p:天下雨，q:我去上学)  
天下雨，我去上学 加上 天不下雨，我也去上学
//形式化命题 (p→q)∧(¬p→q) 或者 (p∧q)∨(¬p∧q)

• 善于确定原子命题
• 注意识别联结词
• 括号需要适当的保留，保证可读性
• 形式化可能不唯一，但在逻辑上的结果会等价

充分条件 （Sufficient Condition）有两个重要的判断特点：

1. $A$ 能够推导出 $B$ （属于 $A$ 的 一定属于 $B$）
2. $B$ 不一定能推导出 $A$ （属于 $B$ 的不一定属于 $A$）

必要条件 （Necessary Condition）有两个重要的判断特点：

1. 如果 $B$ 成立，那么 $A$ 一定成立
2. 但 $A$ 成立不一定意味着 $B$ 成立。

充要条件：双蕴含，$A$、$B$ 可以互推。

• 真值表
• 离散数学[2]-数理逻辑基本概念
• coursea 离散数学概论 陈斌 北京大学地球与空间科学学院
• 充分必要条件