数理逻辑—命题逻辑共50页

结合词的优先顺序为： , , , , ; 1:假设出现的结合词同级，又无括号时，那么
按从左到右的顺序运算; 2:假设遇有括号时，应该先进展括号中的运算.
留意: 本书中运用的 括号全为圆括号〔〕.
2.2 命题公式
命题变项与合式公式 公式的赋值 真值表 命题的分类
重言式 矛盾式 可满足式
命题变项与合式公式
随堂练习
1：写出命题、简单命题的定义。 2：用符号定义五个结合词及其各自取值情况。 3：写出蕴涵式的定义，分析前件与后件的关系，
列出对应的言语表达方式。 4：写出遇到析取结合词二义性时的判别方式及对应
符号表示。 5：列出下面公式的真值表，阐明各公式的层次
(p q) ((p q) (q p)) (p q) (p q) 6：写出命题公式的定义
pq r
pq
000
0
001
0
010
1
011
1
100
1
101
1
110
1
111
1
r (pq)r
1
1
0
1
1
1
0
0
1
1
0
0
1
1
0
0
公式的类型
定义2.9 设A为一个命题公式 (1) 假设A在它的各种赋值下取值均为真，那么称A为重言 式(也称永真式) (2) 假设A在它的各种赋值下取值均为假，那么称A为矛盾 式(也称永假式) (3) 假设A至少存在一组赋值是成真赋值，那么称A为可满 足式
3.析取式与析取结合词“∨〞
定义2.3 设 p,q为二命题，复合命题“p或q 〞称作p与q的析取式，记作p∨q，∨称作 析取结合词，并规定
p∨q为假当且仅当p与q同时为假. 例即将:p以∨下命q题为符真号化当且仅当p与q至少有一个为真。 此处(1)定2或义4是的素析数.取式p∨q表示的是一种相容性

18
10.1.3 复合命题
2021/4/8
• 例10.13 设命题P为“明天上午七点下雨”, Q为 “明天上午七点下雪”, R为“我去学校”
1) 如果明天上午七点不是雨夹雪则我去学校 ¬(P∧Q)→R
2) 如果明天上午七点不下雨并且不下雪则我去学校 ¬P∧¬Q→R
3) 如果明天上午七点下雨或下雪则我不去学校 P∨Q→¬R
2021/4/8
22
10.1.3 复合命题
• 例: “除非你年满18岁，否则只要你身高不足1.6 米就不能乘坐过山车”,翻译成命题公式.
• 解：
找出原子命题：
P: 你年满18岁
Q: 你身高不足1.6米 R: 你乘坐过山车
A：只要你身高不足1.6米就不能乘坐过山车:
=只要Q就非R：Q→¬R
除非你年满18岁，否则A:
28
10.2 命题变元与命题公式
• 例：¬(P∧Q)→(¬(P∧¬Q))的真值表
2021/4/8
P
T
T
F
F
Q
TF TF
P∧Q
T
F
F
F
¬(P∧Q)
F
T
T
T
¬Q
FT FT
P∧¬Q
F
T
F
F
¬(P∧¬Q) T
F
T
T
¬(P∧Q)→ T
F
T
T
(¬(P∧¬Q))
29
10.3 重言式
• 定义10.3
一个公式如果对其所有指派均取值为真, 则称此 类公式为永真公式或叫重言式(tautology). 反之,一个公式如果对其所有指派均取值为假, 则 称此类公式为永假公式或叫矛盾.

例2：
• 函数y=f(x)或是奇函数或是 偶函数。 (AB) • 函数y=f(x)不是奇函数 计算机学院 A • 所以函数y=f(x)是偶函数。 B
计算机学院
29
29
1.2公式和真值赋值
合式公式
真值表计算
语义
可满足性
计算机学院
计算机学院
30
30
合式公式
命题逻辑中
计算机学院
12
12
命题示例
雪是白的。 2是奇数。 X+Y>5。 你是谁？ 我正在说谎。 北京是中国的首都。 命题，真 命题，假 不确定，非命题
疑问句，非命题
悖论，非命题 命题，真
每个不小于6的偶数都是两个 奇素数之和（歌德巴赫猜想）
21世纪有人住在月球上。
pq=(pq)(qp)
逻辑联接词的含义 计算机学院 自然语言中，当且仅当的含义
计算机学院
22
22
逻辑联结词—
真值表
p q称为p与q异或， 读作p异或q。
pq= (pq)(qp)
北航在海淀区或北航在西城区。
比较 李明学习英语或学习法语
计算机学院
??当且仅当?异或??????真值表逻辑联结词?10pp??命题p的否定记为?p读作非p真值表计算机学院1818计算机学院01?逻辑联接词?的含义?自然语言中并非的含义逻辑联结词?010000qpqp?真值表?p?q称为p和q的合取?读作p且q计算机学院1919计算机学院111001?逻辑联接词?的含义?自然语言中并且的含义逻辑联结词?000qpqp?真值表?p?q称为p和q的析取读作p或q计算机学院2020计算机学院111101110?逻辑联接词?的含义?自然语言中或的含义逻辑联结词?111100100qpqp?真值表?p?q称为p蕴涵q?读作p则q?p称为前件称为后件?q称为后件计算机学院2121计算机学院111001?逻辑联接词?的含义?自然语言中如果

…
1 2 3 … n n+1
Note：上图说明两个事实：M（1），和对形式（和无约束的，无限的）参数n， M（n）→M（n+1），就可以得到对每个自然数k，有M（k）。
故，我们断言：对所有自然数n，1+2+…+ n之和等于n×（n +1）/2。
24
定理：对于所有自然数n，1+2+3+…+ n之和等于n× （n +1）/2。
Note：把∧与∨看作两个变量的函数；
Note：两列φ和ψ的四对真值遍历了所有可能性（T T，T F，F
T，和 F F）
15
总结：1）在析取和合取的真值表中，如果交换T和 F，
那么析取是合取的镜像。
即：当且仅当二者都是F析取取F，否则二者至少有一个取T
φ ψ φ∧ψ φ ψ φ∨ψ
二者至少有一个取 T T T T
q
r
∧∧
（┐p）
（（┐p）∧q
┐ qp ∨
（┐r）
（q∨（┐r））
p
q┐
（（ p∧（q∨（┐r））））
（（（┐p）∧q）→（ p∧（q∨（┐r ）））） r
10
∧ → ┐ 此此树树不不是是一一个个合合式式公公式式，，字字符符串串为为
∧→p┐∧┐┐ ∧→p┐∧┐┐ ∧ p┐
┐
11
例：已知树，求其逻辑公式线性表示
即：1+2+3+…+（n +1）=（n +1）*（（n +1）+1）/2
25
因为：1+2+3+…+（n +1）=（1+2+…+ n）+（n +1）

符号化： p: 凡是偶数都能被2整除。 q: 6是偶数。 r: 6都能被2整除。 (pq)r 是永真式吗？
•35/49
练习1
1. 将下列命题符号化。 (1) 豆沙包是由面粉和红小豆做成的。 (2) 苹果树和梨树都是落叶乔木。 (3) 王小红或李大明是物理组成员。 (4) 王小红或李大明中的一人是物理组成员。 (5) 由于交通阻塞，他迟到了。 (6) 如果交通不阻塞，他就不会迟到。 (7) 他没迟到，所以交通没阻塞。 (8) 除非交通阻塞，否则他不会迟到。 (9) 他迟到当且仅当交通阻塞。
(5) 在自然语言中，“如果p，则q”，p, q具有某
种
内在联系；但在数理逻辑中， p, q可以无任•13/49
蕴涵联结词
(3) 当 p 为假时，pq恒为真，称为空证明 证明：空集是任意集合的子集。
•14/49
联结词的实例
例4 设 p:天冷，q:小王穿羽绒服，将下列命题符号化。
(1) 只要天冷，小王就穿羽绒服。
pq (5) p: 张辉与王丽是同学
(1)—(3) 说明描述合取式的灵活性与多样性 (既/又、不但/而且、虽然/但是、一面/一面等)
(4)—(5) 要求分清 “与” 所联结的成分 •9/49
联结词的实例
例3 将下列命题符号化。 (1) 2 或 4 是素数。 (2) 2 或 3 是素数。 (3) 4 或 6 是素数。 (4) 小元元只能拿一个苹果或一个梨。 (5) 王小红生于 1975 年或 1976 年。
定义2 设p,q为两个命题，复合命题“p并且q”(或 “p与 q”)称为p与q的合取式，记作p∧q，∧称作 合取联结词。 规定: p∧q为真当且仅当p与q同时为真。
定义3 设p, q为两个命题，复合命题“p或q”称作 p与q的析取式，记作p∨q，∨称作析取联结词。 规定: p∨q为假当且仅当p与q同时为假。

9.1 命题
定义9.1命题：凡能分辨真、假的语句称命题。 定义 命题：凡能分辨真、假的语句称命题。 命题 定义9.2 原子命题：一命题凡不能分解为更简单的 原子命题： 定义 命题称原子命题或简称原子。 命题称原子命题或简称原子。 定义9.3命题常量 具有确定真值的命题，它可用T 命题常量： 定义 命题常量：具有确定真值的命题，它可用 表示， 或F表示，称命题常量或命题常元。 表示 称命题常量或命题常元。 定义9.4命题变量 命题变量： 为其变域的命题， 定义 命题变量：以 T，F为其变域的命题，并可 ， 为其变域的命题 用命题标识符表示之。称命题变量或称命题变元。 用命题标识符表示之。称命题变量或称命题变元。
第9章 命题逻辑 章
（3）自然语言中的联结词的衡量标准不完全是其真 值表； 值表 ； 但命题逻辑中的联结词的衡量标准则是真值 因此， 联结词的唯一衡量标准是其真值表， 表 。 因此 ， 联结词的唯一衡量标准是其真值表 ， 而 不是由自然语言的一些日常语义确定。 不是由自然语言的一些日常语义确定。
9.3 命题公式
2
第9章 命题逻辑 章
9.2命题联结词
定义9.5复合命题 ： 定义 复合命题： 由原子命题通过联结词所构成 复合命题 的命题称复合命题。 的命题称复合命题。 (1)否定 否定 否定联结词是一元联结词， 否定联结词是一元联结词，它的作用对象仅为一个 命题。 命题 。 否定联结词作用于一个命题后使该命题出现 相反的语义。 如有命题： 今天下雨， 相反的语义 。 如有命题 ： 今天下雨 ， 而加上否定联 结词后即成为：今天不下雨。 结词后即成为：今天不下雨。 在命题逻辑中将此联结词予以符号化， 在命题逻辑中将此联结词予以符号化，并建立符号 体系如下： 体系如下：

➢ 设P、Q为两个命题，复合命题“P而且Q”称为P、Q的合取式，
记为P∧Q，“∧”称为合取联结词。 P∧Q为真当且仅当P 与
Q 为同时为真。
P
Q
P∧Q
T
T
T
F
F
T
F
F
T F F F
16
§1 命题与联结词
3、析取联结词
EX4： “期中考试张三或李四中有人考90分。” P 代表：“期中考试张三考了90分”，
➢ 上述诸如“没有”、“如果…那么…”等词称为联结词。
➢ 由联结词和命题连接而成的更加复杂命题称为复合命题；相 对地，不能分解为更简单命题的命题成为简单命题。（命题 的分类）
➢ 复合命题的真假完全由构成它的简单命题的真假所决定。
注：简单命题和复合命题的划分是相对的。
13
二、命题联结词
1、否定联结词
然后借助于这些符号、规则、定律，将逻辑推理的过程在形 式上变得像代数演算一样，因此数理逻辑又称符号逻辑。 数理逻辑是传统逻辑的发展，是现代形式逻辑
4
微积分 ——力学、机械工程 ——人类体力劳动自动化 数理逻辑 ——人工智能、知识工程 ——脑力劳动自动化
5
数理逻辑
命题逻辑（数理逻辑的基础，以命题为研究对象，研究基 于命题的符号逻辑体系及推理规律，也称命题演算）。
EX5： ① 张三或者李四考了90分。
② 第一节课上数学课或者上政治课。
③ 去教学楼需要6分钟或8分钟。
差异在于：
当构成他们的简单命题都真时，（1）为真，（2）为假。
➢ （1）称为“可兼或”，（2）称为“排斥或”，（3）非 联结词，表示近似的数。
➢ （1）可表示为P∨Q，（2）却不能。

判断给定句子是否为命题, 应该分两步：
首先判定它是否为陈述句, 其次判断它的真值是 否唯一。
例1.1 判断下例句子是否为命题。
(1) 2 是素数。
(2) 雪是黑色的。
(3) 1+101=110
(4) 十是整数。
(5) 向右看齐！
(6) 今天是十五号。
(7) 这朵花多美啊！ (8) 我们这里四季如春。
命题符号化是很重要的, 一定要掌握好。 在命题推理中常常最先遇到的就是符号化 这个问题, 解决不好, 等于说推理的首要前提 没有了。
在本节结束时, 应强调指出的是: 复合命题的真值只
取决于各原子命题的真值, 而与它们的内容、含义无关, 与原子命题之间是否有关系无关。
理解和掌握这一点是至关重要的, 请认真领会。
2. 在自然语言中, “如果P, 则Q”中的前件P与后件Q往往具有某 种内在联系。而在数理逻辑中, P与Q可以无任何内在联系。
3. 在数学或其它自然科学中, “如果P, 则Q”往往表达的是前件 P为真, 后件Q也为真的推理关系。但在数理逻辑中, 作为 一种规定, 当P为假时, 无论Q是真是假, PQ均为真。即: “只有P为真Q为假”使得复合命题PQ为假。
或 0 表示“假”。
(3) 命题中的联结词也符号化: ¬、∧、∨、、。
四、命题常量与命题变元
简单命题可用命题标识符表示。表示命题的符号有双 重作用:
(1) 如果命题标识符表示确定的命题(真值确定)——命题 常元;
(2) 如果命题标识符只表示任意命题的位置标志, 即可表
示任意命题(真值不确定)——命题变元。
由它构成的命题称为简单命题。简单命题是命题逻
辑的基本单位。
三、命题符号化

第11页
推理理论
（三） 间接证明法 1、反证法（归谬法） 、反证法（归谬法）
原理： 原理： 即 A1∧A2∧A3⋅⋅⋅⋅⋅∧An ⇒B ⋅⋅⋅⋅⋅∧ A1∧A2∧A3⋅⋅⋅⋅⋅∧An →B ⇔ T ⋅⋅⋅⋅⋅∧ ¬（A1∧A2∧A3⋅⋅⋅⋅⋅∧An）∨B ⇔ T （ ⋅⋅⋅⋅⋅∧ 即证 A1∧A2∧A3⋅⋅⋅⋅⋅∧An ∧¬B ⇔ F ⋅⋅⋅⋅⋅∧
更一般的有： 更一般的有： 定义2： 是命题公式， 定义 ：设A1、A2…An和B是命题公式，当且仅当 是命题公式 A1∧A2∧A3…∧An ⇒ B，则称 是一组前提 1，A2…An 是一组前提A ∧ ，则称B是一组前提 的有效结论，或称从 推出B。 的有效结论，或称从A1，A2…An推出 。 有时也记为: 有时也记为 A1，A2 ,…,An ⇒ B。 。
第15页
2、附加前提证明法（CP规则） 、附加前提证明法（ 规则 规则） 欲证明: 欲证明 ( A1 ∧ A2 ∧, …, ∧ Ak )→ (A→B) → →
(1)
而 (A1∧A2∧…∧Ak)→(A→B) ∧ → → ⇔ ¬( A1∧A2∧…∧Ak)∨(¬A∨B) ∧ ∨¬ ∨ ⇔ ¬( A1∧A2∧…∧Ak∧A)∨B ∧ ∨ ⇔ (A1∧A2∧…∧Ak∧A)→B (2) ∧ → 在(2) 式中原结论中的前件 已经变成了前提，如 式中原结论中的前件A已经变成了前提 已经变成了前提， 果能证明(2) 式为永真式， 式也是永真式。 果能证明 式为永真式，则(1)式也是永真式。称 式也是永真式 A为附加前提，称这种将结论中的前件作为前提 为附加前提， 为附加前提 的证明方法为附加前提证明法（ 规则 规则）。 的证明方法为附加前提证明法（CP规则）。
第4页
推理理论
二、命题演算的证明方法（推理理论） 命题演算的证明方法（推理理论） （一）真值表法： 真值表法： 检查真值表中使所有A 都取T的那些行 的那些行， ① 检查真值表中使所有 1，A2…An都取 的那些行， 在所有这些行都为真值T， 若B在所有这些行都为真值 ， 在所有这些行都为真值 即证得: 即证得 A1，A2…An ⇒ B。 。 检查真值表中B的取值为 的那些行，若在相应行中， 的取值为F的那些行 ② 检查真值表中 的取值为 的那些行，若在相应行中， 至少有一个A 至少有一个 i（i=1，2，…n）取值为 ， ， ， ）取值为F， 即证得: 即证得 A1，A2…An ⇒ B。 。

题 例：“张三学英语和李四学日语”

两个特殊的命题词
命题常量
T：永远表示真命题 F：永远表示假命题

T和F的两种含义
命题常量 命题的真值


数理逻辑不关心内容
具体的陈述句的真值究竟为什么或在什么环境
下是真还是假

数理逻辑只关心形式
命题可以被赋予真或假这样的可能性，以及规

一个陈述语句
命题
命题是一个非真即假(不可兼)的断言 如果命题是真

命题的真值（Truth Values）为真 真命题 大写字母“T”(1)表示


如果命题是假
命题的真值是假 假命题 大写字母“F”(0)表示

例1:
今天下雪
3+3=6
是偶数而 3 是奇数 1+101=110 明年的今天会下雨 较大的偶数都可表为两个质数之和

命题变元（命题词）
P表示任一命题时，P就称为命题变元（命题词）
命题词不是命题
命题指具体的陈述句，是有确定的真值 命题变元的真值不定，只当将某个具体命题代入命题
变元时，命题变元化为命题，方可确定其真值

复合命题(Compound proposition)
一个或几个简单命题用联结词联结所构成的命

设P表示命题, 那么“P不真”是另一命题, 表示为┐P, 叫做 P的否定, 读做“非P”。 如果P是假, 则┐P是真, 反之亦然。
P
F T
┐P
T F
真值表（Truth Table)
与自然语言中的“不”，“否”，“非”，“没有”，“未必 类似
例4