离散数学（第3版） 屈婉玲 耿素云 张立昂 编著 清华大学出版社出版
第2章
命题逻辑
上海大学 谢 江
1
Hale Waihona Puke 第2章命题逻辑• 2.1 命题逻辑基本概念 • 2.2 命题逻辑等值演算 • 2.3 范式
• 2.4 推理
2
2.1 命题逻辑基本概念
• 2.1.1 命题与联结词
– 命题与真值(简单命题, 复合命题) – 联结词(¬ , , , , )
pq 的逻辑关系: p与q互为充分必要条件: (p→q)∧(q→p)
例如 这件事张三能做好, 且只有张三能做好 设 p:张三做这件事, q: 这件事做好了。形式化为: pq
20
2.1.1 命题与联结词
实例
例6 求下列复合命题的真值 (1) 2+2＝4 当且仅当 3+3＝6. (2) 2+2＝4 当且仅当 3是偶数. (3) 2+2＝4 当且仅当 太阳从东方升起. (4) 2+2＝5 当且仅当 美国位于非洲. 1 0 1 1
15
2.1.1 命题与联结词
联结词与复合命题(续)
定义2.4 “如果 p,则 q” 称作 p与q 的蕴涵式, 记作 p q, 并称 p是蕴涵式的前件, q为蕴涵式的后件. 称作蕴涵 联结词, 规定, p q 为假当且仅当 p 为真且 q 为假.
例如 如果明天天气好, 我们就出去郊游 设 p:明天天气好, q: 我们出去郊游, pq 形式化为
实例
例3 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数. (4) 元元只能拿一个苹果或一个梨. (5) 王晓红生于1975年或1977年. 解 记 p:2是素数, q:3是素数, r: 4是素数, s: 6是素数 (1) p∨r, 真值： 1 (2) p∨q, 真值：1 (3) r∨s, 真值： 0 (4) 记 t: 元元拿一个苹果,u:元元拿一个梨 t∨ u ？ × (5) 记v:王晓红生于1975年,w:王晓红生于1977年 (v∧w)∨(v∧w) v∨ w ？ √
(1) pq，真值为 1 (2) pq, 真值为 1
19
(3) pq ，真值为0 (4) p q, 真值为 1
2.1.1 命题与联结词
联结词与复合命题(续)
定义2.5 “p当且仅当q”称作p与q的等价式, 记作 pq, 称作等价联结词. 并规定 pq 为真当且仅当 p与q同时 为真或同时为假.
不是！
p，q，r，…是命题常数还是命题变项？ 根据上下文来确定 具体的简单命题为命题常项，如p: 3+3=6; q: 雪是白色的
24
2.1.2 命题公式及其分类
合式公式（续）
将命题变项用联结词和圆括号按一定的逻辑关系联结起 来的符号串称为合式公式或命题公式，简称公式. 当使用联 结词集{, ∧, ∨, →, ↔}中的联结词时： 定义2.6 合式公式 (命题公式, 公式) 递归定义如下： (1) 单个命题常项或变项是合式公式,并称作原子合式公式 (2) 若A是合式公式, 则 (A)也是合式公式 (3) 若A, B是合式公式, 则(AB), (AB), (AB), (AB)也 是合式公式 (4) 只有有限次地应用(1)~(3)形成的符号串才是合式公式
26
2.1.2 命题公式及其分类
合式公式的层次
定义2.7 (1) 单个命题变项或命题常项是 0 层公式 2) 称A是n+1(n≥0)层公式是指下面情况之一： (a) A=B, B是n层公式 (b) A=BC, 其中B,C分别为 i 层和 j 层公式, 且 n=max(i, j) (c) A=BC, 其中B,C的层次及n同(b) (d) A=BC, 其中B,C的层次及n同(b) (e) A=BC, 其中B,C的层次及n同(b) 3) 若公式A的层次为 k，则称A是 k层公式. 例如 p 0层 (pq)r 3层 命题公式的真值？ p 1层 pq ((pq) r)(rs) 2层 4层
(1) p∧q
(2) p∧q
(3) p∧q
r∧ s
(4) 记 r:张辉是三好生, s:王丽是三好生, (5) 简单命题, 记 t:张辉与王丽是同学
12
2.1.1 命题与联结词
联结词与复合命题(续)
定义2.3 “p或q”称作p与q的析取式,记作p∨q, ∨称作析取 联结词, 并规定p∨q为假当且仅当p与q同时为假.
16
2.1.1 命题与联结词
蕴涵联结词(续)
pq 的逻辑关系: q为 p的必要条件, p为 q的充分条件
“如果 p,则 q” 的多种表述方式： 若 p,就 q 只要 p, 就 q p 仅当 q 只有q 才 p 除非 q, 才 p 除非 q, 否则非 p 当 p为假时，pq为真(不管q为真, 还是为假) 在自然语言中，“如果p，则q”中的前件和后件往往具有某 种内在联系，而在数理逻辑中，p与q可以无任何内在联系
9
p并且q
2.1.1 命题与联结词
联结词与复合命题
定义2.1 “非p”(或 “p的否定”)称为p的否定式, 记作 p, 称作否定联结词, 规定 p为真当且仅当 p为假
例如 p:2是合数, p: 2不是合数,
p为假, p为真
10
2.1.1 命题与联结词
联结词与复合命题
定义 2.2 “ p 并且 q”( 或“ p 与 q”) 称为 p 与 q 的合取式 , 记作 p∧q, ∧称作合取联结词, 规定 p∧q为真当且仅当 p与q 同时为真
17
2.1.1 命题与联结词
实例
例4 设 p:天冷, q: 小王穿羽绒服， 将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候. pq pq qp 或 pq qp qp pq pq 或 qp qp
18
注意： pq 与 qp 等值（真值相同）
2.1.1 命题与联结词
实例
例5 将下列命题符号化，并指出真值 (1) 如果3+3=6，则雪是白色的. (2) 如果3+3≠6，则雪是白色的. (3) 如果3+3=6，则雪不是白色的. (4) 如果3+3 ≠ 6，则雪不是白色的.
解：设 p：3+3=6，p的真值为 1. q：雪是白色的，q的真值也为 1.
• 2.2.2 命题公式及其分类
–命题公式及其赋值 –真值表 –命题公式的分类
3
2.1.1 命题与联结词
推理
前提 => 结论 例如推理 若华盛顿是美国的首都，则多伦多是加拿大的 首都。华盛顿是美国的首都，所以多伦多是加拿大的首都. 推理的组成： 联结词 ＋ 陈述句
4
2.1.1 命题与联结词
命题及其真值
例如 p： 多伦多是加拿大的首都. 真值为 0 q： ������是无理数. r：火星上有生命.
真值为1 真值现在未知
s：2050年元旦北京是晴天. 真值现在未知
8
2.1.1 命题与联结词
简单命题与复合命题
复合命题:由简单命题通过联结词联结而成的陈述句
例如 1. 如果明天天气好, 我们就出去郊游 设 p: 明天天气好, q: 我们出去郊游, 如果p, 则q 2. 张三一面喝茶一面看报 设 p: 张三喝茶, q: 张三看报, 3. 多伦多不是加拿大的首都 设 p：多伦多是加拿大的首都，不是 p 4. 2是素数当且仅当3也是素数 设 s：2是素数，t：3是素数， s 当且仅当 t
命题及其真值
说明: • 命题是命题逻辑中最小的单位（命题逻辑中，对命题的 成分不再细分（如主语、谓语等）了）.. • 判定给定语句是否为命题，要分两步： 1）判断是否为陈述句； 2）判断是否有唯一的真值.
6
2.1.1 命题与联结词
实例
例1 下列句子中那些是命题？ (1) 北京是中华人民共和国的首都. (2) 2 + 5 ＝8. (3) x + 5 ＞ 3. (4) 你会开车吗？ (5) 2050年元旦北京是晴天. (6) 这只兔子跑得真快呀！ (7) 请关上门！ (8) 我正在说谎话.
1.可以有多种自然语 言表达；2.不是所有 的“和”和“与”都 使用联结词∧
例如 p:2是偶数, q: 2是素数, p∧q: 2是偶素数, p为真, q为真, p∧q为真
11
2.1.1 命题与联结词
实例
例2 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解 记 p:王晓聪明, q:王晓用功
真命题 假命题 真值不确定 疑问句 真值确定, 但未知 感叹句 祈使句 悖论
7
(1),(2),(5) 是命题, (3),(4),(6)~(8) 都不是命题
2.1.1 命题与联结词
简单命题与复合命题
简单命题(原子命题)：简单陈述句，无联结词成的命题
简单命题的符号化:用p, q, r, … ,pi,qi,ri (i≥1)表示 用“1”表示真，用“0”表示假
命题: 判断结果唯一的陈述句 命题的真值: 判断的结果,真或假 真命题: 真值为真的命题 假命题: 真值为假的命题
注意: 命题的两个特点 • 感叹句、祈使句、疑问句都不是命题 • 陈述句中的悖论以及判断结果不唯一确定的也不是命题 • 任何命题的真值都是唯一的
推理的基本要素：联结词＋命题
5
2.1.1 命题与联结词
25
2.1.2 命题公式及其分类
合式公式（续）
说明: (1) 定义给出的合式公式的定义方式称为归纳定义方式. (2) 定义中的A，B是表示任意的合式公式，而不是某个 具体的公式. (3) 在不影响运算顺序时, 括号可以省去 例如 0, p, pq, (pq)(pr), pq r, (pq)r