开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> 【离散数学】数理逻辑1 命题逻辑 -> 正文阅读

[人工智能]【离散数学】数理逻辑1 命题逻辑

本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：

离散数学及其应用第七版 Discrete Mathematics and Its Applications 7th ，作者是 Kenneth H.Rosen
离散数学第二版，武波等编著，西安电子科技大学出版社

0. 逻辑、数理逻辑及其应用

研究逻辑的必要性在于，人类的高级思维是通过各种方式加以表达的，其中最重要的就是通过自然语言。然而自然语言作为一种交流思想的工具，它既要表达精确的概念，又要表达含混不清的思想，在叙述时往往显得不够确切，容易产生二义性，进行严密推理时相当不便。因此，就需要研究数理逻辑来解决这些问题。

所谓的逻辑，就是研究推理的科学，包括形式逻辑和辩证逻辑。而数理逻辑（又称符号逻辑），则是用数学方法来研究形式逻辑的一门数学学科，基本内容包括命题逻辑和谓词逻辑。数理逻辑具有符号化、形式化的显著特征，即首先把逻辑所涉及到的“概念、判断、推理”用符号来表示，然后用公理体系和形式推演来刻画推理过程的一般规律。

数理逻辑为机器证明、人工智能、程序设计自动化、 算法设计方法、形式语义学等计算机科学的应用和研究提供了必要的理论基础。

1. 命题逻辑 `Proposition Logic`

命题逻辑也称命题演算，或语句逻辑。它研究的对象是命题、以命题为基本单位构成的前提和结论之间的可推导关系。什么是命题，如何表示命题？如何由一组前提推导一些结论？下面将详细讨论这些问题。

1.1 命题 `Propositions`

命题是一个或真或假而不能都是的陈述句（判断句）。通常用大写字母表示，如 A, B, C, P₁。一个命题总是具有一个值，就是真值。真值要么为 True 要么为 False ，用来判断命题是否合理或符合客观实际。

判断一个语句是否为命题的主要依据有两点，是否为陈述句或判断句？真值是否唯一（不能既真又假）？

例1：判断下列语句是否为命题。
（1） 2+1=4；
（2） X+Y>4 ；
（3）别的星球上有生物；
（4）哥德巴赫猜想是正确的（每个大于2的偶数均可表示为两素数之和）；
（5） 2是偶数且3是偶数。

答案是：是（真值为F）；不是；是（真值不确定）；是（真值不确定）；是（真值为F）

命题能分为两种类型：

原子命题：不能再分解成更为简单的命题。通常用大写字母、带下标的大写字母或数字表示，如 A, B, …, A_i, [3], …
复合命题：由原子命题通过一些联结词构成的新命题。

上例中(1)、(3)、(4)是原子命题，(5)是复合命题。

1.2 命题联结词

联结词即命题演算（命题逻辑）中的运算符（逻辑联结词又叫逻辑运算符），通过联结词，可以将命题和原子命题构成新命题。常用的联结词有5个，否定词“不” $?$ 、合取词“并且” $\wedge$ 、析取词“或” $\vee$ 、条件词 $\to$ 、双条件词（等值词） $\Leftrightarrow$ 。

1.2.1 否定词 $\lnot$

设 $P$ 表示命题，则 $P$ 的否定是一个新的命题，记为 $\lnot P$ ，读作“ $P$ 的否定”（非 $P$ ）。含义是 $? P$ 为真 iff $P$ 为假。

真值表（左侧是运算对象真值的所有可能组合，右边是新命题真值的所有可能组合）为：

$P$	$\lnot P$
0	1
1	0

例2：命题 $P$ ：我们都是好学生。 $? P$ ：并非我们都是好学生。或者， $\lnot P$ ：我们不都是好学生。如果写成我们都不是好学生，就错了。

1.2.2 合取词 $\wedge$

$P$ 与 $Q$ 的合取为一新命题，记为 $\wedge Q$ ，读作“ $P$ 且 $Q$ ”或者“ $P$ 与 $Q$ 的合取”。含义为， $\wedge Q$ 为真 iff $P$ 、 $Q$ 均为真。“ $\wedge$ ”运算定义如下表：

$P$	$Q$	$\wedge Q$
0	0	0
0	1	0
1	0	0
1	1	1

例3：①今天和明天天气晴朗
答：设命题 $P$ ：今天天气晴朗， $Q$ ：明天天气晴朗。命题可符号化为 $P\wedge Q$ 。
② 张华和李明是好朋友。
答：此命题为原子命题。

注意，合取与自然语言中的“与”意义相似，但并不完全相同。区别在于，合取可将毫无内在联系的 $P, Q$ 联结成新命题。只要 $P, Q$ 真值确定，则 $P\wedge Q$ 真值也确定。如“天气很热且狗有尾
巴。”

1.2.3 析取词 $\vee$

$P$ 与 $Q$ 的析取为一个新命题，记为 $\vee Q$ ，读作“ $P$ 或 $Q$ ”或者“ $P$ 与 $Q$ 的析取”。含义为， $\vee Q$ 为真 iff $P$ 、 $Q$ 至少有一个为真。

“”运算定义如下表：
P Q P ∨ Q

注意：
可兼或：可用“”表示
不可兼或：(又称排斥或)，可用“⊕”表示
不可兼或不能用“”直接表示。
例4：A：小王明天上午8时在教室上课；
B：小王明天上午8时参加长跑比赛；
C：小王明天上午8时在教室上课或参加长跑比赛。
如何符号化命题C？
C可否符号化为“AB”？
31二、命题联结词
AB为真 iff A、B至少有一个为真
C为真 iff A、B恰好有一个为真
C：小王明天上午8时在教室上课或参加长跑比赛
A
B A ∨B
0 0
0 1
1 0
1 1
0
1
1
1
C可符号化为：
A
B
0 0
0 1
1 0
1 1
C
0
1
1
0
或A⊕B
32二、命题联结词
4. 条件词（蕴含词）
P、Q的条件命题为一新命题，记为P→Q，读做“若P则
Q”
或“如果P, 那么Q”。
P叫做前提 , 假设或前件, 而Q叫做结论或后件。
含义：P→Q为假 iff P是真而Q是假。
“→”定义如下表：
P
当 P 为假时， P ? Q为真
善意的推定：前件为假，结
论无论真/假，命题为真。

3.命题公式与翻译

33二、命题联结词
P→Q可以用多种方式陈述：
“若P, 则Q”、
“如果P, 那么Q”
“P仅当Q”
“P
“
是Q的充分条件”、
“Q是P的必要条件”
只要P，就Q”
给定命题P→Q, 称Q→P为命题 P→Q的逆命题,
称? P→? Q为命题 P→Q的否命题
称? Q→ ? P为命题 P→Q的逆否命题
.
34二、命题联结词
5.等值词（双条件词）
PQ为双条件命题，读作“P等值于Q”或“P当且
仅当Q”。
含义： PQ为真 iff P、Q同时为真或同时为假
”定义如下表：
“
P
0
0
1
1
Q
0
1
0
1
P  Q
1
0
0
1
35基本命题联结词
联结词
记
号
复合命
题
否定 ┐ 非P
合取 ∧ P并且Q
析取 ∨ P或者Q
读法
记
法
真值结果
P的否定 ┐ ┐P为真当且仅当P为假
P与Q的
合取
P与Q的
析取
P∧Q
P∨Q
条件
→ 若P,则Q 若P则Q P→Q
双条件 
P当且仅
当Q
P等价于
Q
PQ
P∧Q为真当且仅当P,Q同为
真
P∨Q为真当且仅当P,Q中至
少一个为真
P→Q为假当且仅当P为真Q
为假
PQ为真当且仅当P,Q同
为真假

1.3 命题公式与翻译（难点）

命题常元：表示已经确定真值的命题标识符，
表示为T或F。
命题变元：以“真，假”为其变域的命题标识符
(真值未确定的命题标识符)
表示：A,B,C,
3.原子公式：单个命题变元或命题常元
37三、命题公式与翻译
4.命题公式
(1) (基础)单个原子公式是命题公式。
(2) (归纳)如果A和B是命题公式, 则(? A) , (A∧B) ,
(A∨B) , (A→B) , (A  B)是命题公式。
(3) (极小性)只有有限步应用条款(1)和(2)生成的长度有
限的符号串才是命题公式。
这种定义叫归纳定义, 也叫递归定义。由这种定义产生的公
式叫命题公式或合式公式（Well formed formula ）
。
38三、命题公式与翻译
例 5
(a) 说明(P→(P∨Q))是命题公式。
解 (i) P是命题公式根据条款(1)
(ii) Q是命题公式根据条款(1)
(iii) (P∨Q)是命题公式根据(i)(ii)和条款(2)
(iv) (P→(P∨Q))是命题公式根据(i)(iii)和条款(2)
39三、命题公式与翻译
(b) 以下不是命题公式, 因为它们不能由形成规则得出。
∧Q, (P→ Q∨, P→∧Q, ((PQ)∧R)
并非由命题变元、联结词和一些括号组成的字符串都能成为命题公式。
40三、命题公式与翻译
例6. 符号化下列命题：
①若天不下雨也不下雪，则我去学校。
P:天下雨； Q：天下雪。R:我去学校
翻译时约定:
运算符结合力的强弱顺序为： ? 、 ∧ 、 ∨、
→ 、 ，凡符合此顺序的, 括号均可省去。相同
的运算符, 按从左至右次序计算时, 括号可省去。
最外层的圆括号可以省去。
(? P  ? Q) →R
41
(((? P)  ? Q)) →R)三、命题公式与翻译
例6. 符号化下列命题： ②林芬和林芳是姐妹。
P:林芬和林芳是姐妹。（原子命题） ③除非你掌握情况，否则你不能作出科学判断。
P:你掌握情况 Q:作出科学判断 ?P → ? Q
Q → P ④说离散数学枯燥无味或毫无价值，那是不对的。
P:离散数学是枯燥无味的; Q:离散数学是毫无价值的。 ? (P  Q)