离散数学[2]-数理逻辑基本概念

一、什么是数理逻辑

• 逻辑学是探索、阐述和确立有效推理原则的学科，最早由古希腊学者亚里士多德创立。
•  亚里士多德在逻辑学上最重要的工作是提出 三段论学说。
•  只要符合三段论的推理就是正确的。
•  一个三段论就是一个包括有大前提、小前提和结论三个部分的论证。

三段论有许多不同种类，其中最著名的例子:

1. 凡是人都会死(大前提)
2. 苏格拉底是人(小前提)
3. 所以:苏格拉底会死(结论)

逻辑学还是以自然语言来表述，可能会因为自然语言的模糊性损害其准确和权威。 用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑(也叫做符号逻辑)。

数理逻辑的萌芽

• 利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在十七世纪就有人提出过。
• 莱布尼茨(Leibniz)就曾经设想能不能创造一种“通用的科学语言”，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。
• 由于当时的社会条件，他的想法并没有实现。但是他的思想却是现代数理逻辑部分内容的 萌芽，从这个意义上讲，莱布尼茨的思想可以说是数理逻辑的先驱。

数理逻辑的开创

1847年，英国数学家布尔G.Boole发表了《逻辑的数学分析》，建立了“布尔代数”。布尔创造了一套符号系统，利用符号来表示逻辑中的各种概念。还建立了一系列的运算法则，利用代数的方 法研究逻辑问题，初步奠定了数理逻辑的基 础

数理逻辑的大发展

1884年，德国数学家弗雷格Frege出版了《数论的基础》一书，在书中引入量词的符 号，使得数理逻辑的符号系统更加完备。 美国人皮尔斯Peirce，他也在著作中引入了更多逻辑符号。从而使现代数理逻辑最基本的理论基础逐步 形成，成为一门独立的学科。

数理逻辑的四大分支

• 数学史上的第三次大危机是由于发现了集合论的逻辑悖论引起的。
• 悖论的提出，促使许多数学家去研究集合论的无矛盾性问题，从而产生了数理逻辑的一个重要分支—公理集合论。
• 为了研究数学系统的无矛盾性问题，需要以数学理论体系的概念、命题、证明 等作为研究对象，研究数学系统的逻辑结构和证明的规律，这样又产生了另一 个分支—证明论。
•  递归论主要研究可计算性的理论，它和计算机的发展和应用有密切的关系。
•  模型论主要是研究形式系统和数学模型之间的关系。

我们课程中介绍的是数理逻辑各个分支的共同基础部分:命题演算与谓词演算

二、命题(proposition)

• 命题是数理逻辑中最基本的概念
• 对确定的对象作出判断的陈述句称作命题
• 如果判断正确，称命题真(true),否则称命题假(false)
• “真、假”是命题的属性，称为“真值”

什么样的语句是命题?

• 雪是白的。
• 2+2=5。
• 您贵姓? （No）
• x+y<10。 (No,x和y不是确定的对象)

三个识别要点:

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

识别命题

再来看看几个语句

• 袁世凯称帝那天北京下雨。

• 大于2的偶数均可分解为两个素数之和。

• 请把脚挪一下! （No,祈使句，不是陈述句）

• 谁拿走了桌上的杯子? （No,不是陈述句）

• 2是偶数而且3也是偶数。

• 真值是命题的固有属性

• 不过，是否知道真值，能否知道真值是另一回事。

• 悖论(自相矛盾)不能作为命题。如“这句 话是错的”

• 命题非真即假，不能兼有之，也不能不真不假

• 非真即假，是一个基本假设?

三、排中律（Law of Excluded Middle）

• 排中律是传统逻辑的基本规律之一
• “是非之间，必居其一”。
• 墨子也说过:“辩也者，或谓之是，或谓之 非，当者胜也“——《经说下》。
• 任一事物在同一时间里具有某属性或者不具 有某种属性，而无其它可能。

反证法与排中律

• 传统数学证明中经常采用的“反证法”即利用了排中律:
• 要证明一个命题为真，并不直接证明;
• 而是假设命题不为真，推出矛盾;
• 根据排中律，此命题非假，即真;
• 从而间接证明命题为真。

反证法的著名范例

• 欧几里德:素数有无穷多个 假设命题不真，那么素数就是有限个，把它们按照大小顺序排列起来，记为a1<a2<a3..<an 接下来，我们构造一个新的数 N=a1a2a3*…*an+1。 所有的这些素数ai(i=1,2…n)都不是N的因子 这样，就有两种可能:

1，N有另外的素数真因子

2，N本身就是一个素数 显然，N比所有的ai都要大，无论哪种情况，我们都 发现了ai之外的素数。 这跟假设矛盾，根据排中律，命题就是真的!

直觉主义对排中律的质疑

• 但直觉主义认为，数学的基础和出发点是人类直觉所构造;

• 数学理论可靠性依赖于心智上的可构造性;

• 对命题真假的确定必须给出构造性证明;

• 而反证法虽然对命题的反面推出矛盾;

• 但不意味着命题本身具有构造性证明。

• 直觉主义否定排中律的普遍有效性;

• 从有穷事物中概括出来的排中律，不能贸然推广到对无穷事物适用;

• 涉及到有穷事物全体的命题，可以通过逐个检验来验证其真假;

• 但一旦涉及到无穷事物，一般是无法来做此种检验的。

四、命题符号化

原子命题和复合命题

我们回来再看看刚才的一个命题:

• 2是偶数而且3也是偶数。
• 这是由两个小命题和一个“而且”连接而成
• 联结词“而且”将两个命题组合成新命题， 并产生了新的真值。

这样，我们有了三个新概念:

• 逻辑联结词(logical connectives):连接命题，对真值进行运算的词;
• 原子命题(atom proposition):不含有逻辑联结词的命题;
• 复合命题(compound proposition):包含了原子命题和逻辑联结词的命题。

复合命题

逻辑联结词有哪些呢? 我们来看看更多的复合命题:

• 雪不是白的
• 今晚我去看书或者看电影
• 你去了教室，我去了食堂(省略了“且”) 〉
• 如果天气好，那么我去车站接你
• 偶数a是素数，当且仅当a=2

接下来，我们要回到数理逻辑创立的初衷: 对逻辑和思维过程进行形式化，使之象算术那样简单明了，确切无误。

如何把命题变成“算式”?

1. 形式化的第一步:抽象(abstraction): 仅关注命题的本质属性:真值，而抛弃其丰富的内涵; 仅关注逻辑联结词的本质属性:对真值的运算，而抛弃多变的语言表达方式。
2. 然后是将这两者都变成符号，以规则相连接 真命题用t表示，假命题用f表示 原子命题一般用p, q, r, s或pi, qi, ri, si表示 逻辑联结词用特殊符号来表示: 并非(not):¬ 并且(and):∧;或(or):∨ 如果……那么……(if … then …):→ 当且仅当(if and only if):↔

符号的定义

• 命题的真值

• 为真(true)用1表示，为假(false)用0表示

• 真命题的真值为1，假命题真值为0

• 逻辑联结词用真值表来定义

• 真值表列出了原子命题的真值组合(0、1) 〉 以及经过联结词作用后的真值

• 符号体系对于数学乃至科学体系的发展至关 重要

• 简洁清晰的符号能使人的抽象思维效率飞跃。

• 想象一下全中文、竖排的微分方程?

• 形式主义者甚至认为，数学就是符号变换的游戏。

五、联结词

1. 否定词（negation） “并非”(not):¬

¬p的逻辑关系为p不成立 如果p表示命题“雪是白的”，那么“雪不 是白的”应该表示为¬p

注意在包含多个对象判断的命题否定时，其 意义的变化:

• “天鹅都是白的”，其否定并不是“天鹅都 不是白的”
• 而是“天鹅不都是白的”或“并非所有天鹅 都是白的”

2. 合取词(conjunction) “并且”(and): ∧

p∧q的逻辑关系为:p和q同时成立

• 自然语言中许多表示并列的连接词都 可以符号化为“∧”:
• “既…又…”，“不但…而且…”， “虽然…但是…”
• p:张三聪明;q:张三用功 张三既聪明又用功:p∧q 张三不仅聪明，而且用功: p∧q

张三虽然不太聪明，但他很用功:¬p∧q 张三不是不聪明，而是不用功: p∧¬q

我们看到形式化确实通过抽象，抛弃了原语句的很多内容:

• 抛弃了倾向、语气、价值判断等，
• 只留下命题的本质属性:真值

3.析取词(disjunction)”或”(or):∨

p∨q的逻辑关系为p和q中至少一个成立

自然语言中的“或”可以符号化为∨，但有时要注意原命题中的“或”可能表示排斥性 选择:

• 李四学过德语或法语(相容或):p∨q p:李四学过德语，q:李四学过法语
• 张三生于1972年或1973年(排斥或): p∨q p:张三生于1972年，q:张三生于1973年
• 人固有一死，或重于泰山，或轻于鸿毛(排斥或) (p∧¬q)∨(¬p∧q):异或p:人死重于泰山，q:人死轻于鸿毛

4.蕴涵词(implication)”如果…那么…”(if…then…): →

p→q的逻辑关系是，p是q的充分条件，或者说q是p的必要条件

p→q中的p称作蕴涵前件，q称作蕴涵后件

• 自然语言中的许多条件连接词都可以符号化 为→，但是要注意条件的顺序 “只要…就…”，“如果…那么…”，“只有…才…”

• 自然语言中，条件语句一般都具有内在的联系，而数理逻辑中的蕴涵则仅是命题的一种 连接，不一定具有什么内在联系

• 在蕴涵式中，只有p为真q为假时，p→q才 为假和(¬p∨q)真值表相同

• 如果天气好，那么我去接你:p→q p: 天气好，q: 我去接你 只有p真q假算是食言

• 只要2是偶数，雪就是黑的:p→q p: 2是偶数，q: 雪是黑的 p为真，q为假，本命题为假

• 只有天黑了，夜猫子才出来活动:p→q 注意:p: 夜猫子出来活动，q: 天黑了

5.双向蕴含词(two-way implication)”当且仅当”(if and only if):↔

p↔q的逻辑关系是p与q互为充分必要条件，在p，q真值相同的情况下， p ↔q为真

• 圆1和圆2面积相等当且仅当它们的半径相等: p↔q p: 圆1和圆2面积相等，q: 圆1和圆2半径相等 不管p和q的真值如何， p↔q为真
• 2+3=5当且仅当5是有理数:p↔q p:2+3=5，q:5是有理数
• 除非网断了，否则他一定QQ在线:p↔¬q p:网断了，q:他QQ在线

两个组合的例子 如果3是合数，则4是素数，并且如果 4是素数，则它不能被2整除:

〉 p:3是合数
〉 q:4是素数
〉 r:4能被2整除
〉 (p→q)∧(q→¬r)

如果2+3>5当且仅当5是合数，则2 和3都是有理数

〉 p:2+3>5
〉 q:5是合数
〉 r:2是有理数
〉 s:3是有理数
〉 (p↔q)→(r∧s)

符号组合的规则

〉 把符号组合起来，看起来开始象一个算式了
〉 算式的组合不是随意的;
〉 那么逻辑符号组合的规则是什么?
〉 逻辑符号组合成的算式具有什么意义?

六、命题公式

命题公式(proposition formula)的组成成分

• 命题常元(propositionconstants) 表示具体命题及表示常命题的p, q, r, s 等和t,f
• 命题变元(propositionvariables) 以“真，假”或者“1，0”为取值范围的 变量，仍用p, q, r, s等表示
• 命题公式(propositionformula) 由命题常元、变元和联结词组成的形式更为 复杂的命题

命题公式( proposition formula )定义

1. 命题常元和命题变元是命题公式，特别的称作原子公式或原子
2. 如果A,B是命题公式，那么(¬A), (A∧B), (A∨B), (A→B), (A↔B)也是命题公式
3. 只有有限步引用上述两条所组成的符号串是命题公式

命题公式简称做公式，采用大写A,B,C等表示

注意大小写符号的差别(A、B、C和p、q、r、s、t、f) 命题公式的这种定义方法称作归纳定义，在集合论中将会详细讨论归纳定义

命题公式的例子

根据定义:

(¬(p→(q∧r))) 是命题公式

以下式子都不是命题公式:

(qp) (p1∧(p2∧… p→r∧s

严格按照定义的命题公式太繁琐，简化约定

1. 公式最外层的括号一律可以省略
2. 约定逻辑联结词的优先级，进一步减少括号

逻辑联结词优先级

• 联结词{¬,∧,∨,→,↔}中， ¬是一元联结词，其它都是连接两个命题的二元联结词
• 我们定义优先级为:¬, [∧∨], →, ↔
• 除非有括号，否则按照优先级从高到低，从左到右的次序结合

¬p∨q 等同于 ((¬p)∨q)

p→q∧r→s 并不是 ((p→q)∧(r→s)),其实是 ((p→(q∧r))→s)

命题公式的意义

• 命题公式是一个按照归纳定义构成的字符串
• 其形式上具有既定的规则
• 那么其内容上具有什么意义呢?

七、真值函数

命题公式与真值函数(truth function)

• 如果将联结词看作逻辑运算符，那么包含命题变元p1, p2, …pn的公式A 可以看作是关于p1, p2, …pn的一个真值函数
• 每个变元的取值范围是{0,1}
• 真值函数值的取值范围也是{0,1}

赋值

对任意给定的p1, p2, …pn的一种取值状况组合，称为指派或者赋值 (assignments)

• 赋值用希腊字母α,β等表示
• 对于每个赋值，公式A均有一个确定的真值
• 这样，命题公式在形式上是一个规则 的字符串，内容上则对应一个真值函 数

真值表

（真值表略）

• 对于所有可能的赋值，公式A的真值可以用真值表来确定
• 当A(p1, p2, …pn)中包含有k个联结词时，公式A的真值表应为2n行、 k+n列
• 前n列是所有变元的取值组合
• 最后1列是公式A的真值

成真赋值和成假赋值

• 当公式A对赋值α为真时 称α是A的成真赋值，或者α弄真A 〉 记做α(A)=1
• 反之 称α是A的成假赋值，或者α弄假A 〉 记做α(A)=0

八、命题形式化

自然语言句子的形式化

由自然语言表述的命题，经过抽象，可以形式化为命题公式

• 首先确定原子命题

• 其次确定联结词

• 最后处理命题之间的联结关系及顺序

• 我和他既是兄弟又是同学(p:我和他是兄弟，q:我和他是同学) 形式化命题:p∧q

• 狗急跳墙(p:狗急了，q:狗跳墙) 形式化命题:p→q

• 如果他不来那么是生病了或者不在本地(p:他来，q:他生病，r:他在本地) 形式化命题:¬p→(q∨¬r) *无论是否下雨，我都去上学(p:天下雨，q:我去上学) 〉 形式化命题:(p→q)∧(¬p→q) 或者:(p∧q)∨(¬p∧q) 或者:q

自然语言句子的形式化:注意事项

1. 要善于确定原子命题，如兄弟这个概念就无需进一步拆分;
2. 要善于识别自然语言中的联结词;
3. 对于涉及多个对象进行否定的否定词位置要准确;
4. 不能省略必要的括号，另外，为了提高公式 的可读性，要保留一些括号;
5. 有时候语句的形式化结果不是唯一的，可能具有不同形式，但是逻辑上是等价的。

参考资料

陈斌 北京大学地球与空间科学学院 gischen@pku.edu.cn

https://www.coursera.org/learn/dmathgen/home/info