离散数学课件03命题逻辑的推理理论.共57页文档

((┐p∧┐q)∨p) ∨ q
((┐p∨p )∧(┐q∨p)) ∨ q
(┐q∨p) ∨ q 1
精选课件ppt
由定理 3.1可知， 推理正确。
15
推理定律--重言蕴含式
(1) A (A∨B)
附加律
(2) (A∧B) A
化简律
(3) (A→B)∧A B
假言推理
(4) (A→B)∧┐B ┐A
拒取式
(5) (A∨B)∧┐B A
析取三段论
(6) (A→B) ∧ (B→C) (A→C)
假言三段论
(7) (AB) ∧ (BC) (A C)
等价三段论
(8) (A→B)∧(C→D)∧(A∨C) (B∨D) (A→B)∧(┐A→B)∧(A∨┐A) B
构造性二难 构造性二难
(特殊形式)
(9)(A→B)∧(C→D)∧(┐B∨┐精D选)课件pp(t ┐A∨┐C) 破坏性二难16
只要不出现(3)中的情况，推理就是正确的，因而判断 推理是否正确，就是判断是否会出现(3)中的情况。
推理正确，并不能保证结论B一定为真。
精选课件ppt
8
例题
例3.1 判断下列推理是否正确。（真值表法）
(1) {p,p→q}├ q (2) {p,q→p}├ q
正确 不正确
p q p(p→q) q p(q→p)
推理是指从前提出发推出结论的思维过程。
前提是已知命题公式集合。
结论是从前提出发应用推理规则推出的命题公式。
证明是描述推理正确或错误的过程。
要研究推理，首先应该明确什么样的推理是有效的或 正确的。
精选课件ppt
4
命题逻辑的推理理论
概念
描述问题 的句子

联结词与复合命题(续)
定义2.5 设p, q为命题, 复合命题 “p当且仅当q”称作p与q 的
等价式, 记作pq, 称作等价联结词. 并规定pq为真当 且仅当 p与q同时为真或同时为假.
pq 的逻辑关系: p与q互为充分必要条件
例如 这件事张三能做好, 且只有张三能做好
设p:张三做这件事, q:这件事做好了
26
(v∧w)∨(v∧w) 又可形式化为 v∨w
12
联结词与复合命题(续)
定义2.4 设 p,q为二命题, 复合命题 “如果p,则q” 称作p与q 的蕴涵式, 记作pq, 并称p是蕴涵式的前件, q为蕴涵式的 后件. 称作蕴涵联结词, 并规定, pq为假当且仅当 p为 真且q为假.
例如 如果明天天气好, 我们就出去郊游 设p:明天天气好, q:我们出去郊游, 形式化为 pq
说明: (1) 赋值记作=12…n, i=0或1, 诸i之间不加标
点符号 (2) 通常赋值与命题变项之间按下标或字母顺序对应, 即
当A的全部命题变项为p1, p2, … , pn时, 给A赋值12…n 是指p1=1,p2=2,…,pn=n; 当A的全部命题变项为p,q,r,… 时, 给A赋值123…是指p=1, q=2, r=3, …
是指p1= 1,p2= 2,…,pn= n; 当A的全部命题变项为p,q,r,…
例如 p:2是偶数, q: 2是素数, p∧q: 2是偶素数,
0 0 1 1 1
联结词(¬, , , , )
1
1
(2) ( p q) q
0 1 1 例4 设p:天冷, q:小王穿羽绒服，
(e) A=B C, 其中B,C的层次及n同(b)
p的否定式, 记作p, 符号称作否定联结词, 并规定p 为真当且仅当 p为假 例如 p:2是合数, p: 2不是合数, p为假, p为真

21
一、自然推理系统P
自然推理系统P由三个部分组成：
1.
字母表：命题变项符号；联结词符号；括
号和逗号。
2.
命题公式。
3.
推理规则。
22
二、推理规则
(1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 AB A \B (5) 附加规则 A \AB (6) 化简规则 AB \A (7) 拒取式规则 AB B \A (8) 假言三段论规则 AB BC \AC
30
四、附加前提证明法
例6：用附加前提证明法构造证明下面的推
理： 2是素数或合数。若2是素数，则 2 是 无理数。若 2 是无理数，则4不是素数。所 以，如果4是素数，则2是合数。
31
四、附加前提证明法
解： 设 p：2是素数， q：2是合数，
r： 2 是无理数，s：4是素数 推理形式结构 前提：pq, pr, rs 结论：sq
40
五、归谬法
解：命题符号化
p：小张守第一垒 q：小李向B队投球
r：A队取胜
s：A队成为联赛第一名
推理的形式结构如下：
( p q ) r , r s , s , p 结论： q
前提：
41
五、归谬法
证一：归谬法（略） 证二：直接法 ① r s 前提引入
② s
③r
前提引入
5
前提是有限个公式的集合，而不是序列 。
二、推理的有效性
A1A2… Ak
0 0
B
0 1
推理的有效性 有效 有效
1
1

0
有效
无效
6
二、推理的有效性
定义：若对于每组赋值，当 A1A2…Ak

联结词可以嵌套使用，在嵌套使用时，规定如下优先顺序： ( )，┐，∧，∨，→， ，对于同一优先级的联结词，先出现 者先运算。
例1.7 令 P : 北京比天津人口多 Q:22 4 R : 乌鸦是白色的
求下列复合命题的真值：
1P Q P Q R 2Q R P R 3P R P R
解 P，Q，R的真值分别为1，1，0。容易算出 (1)、(2)、(3)的真值分别为1，1，0。
2．在自然语言中，“如果P，则Q”中的前件P与后件Q往 往具有某种内在联系。而在数理逻辑中，P与Q可以无任何内 在联系。
3．在数学或其它自然科学中，“如果P，则Q”往往表达 的是前件P为真，后件Q也为真的推理关系。但在数理逻辑中， 作为一种规定，当P为假时，无论Q是真是假，P→Q均为真。 也就是说，只有P为真Q为假这一种情况使得复合命题P→Q为 假。
PQ 的真值定义为 PQ为真当且仅当P, Q同真值 因此, P, Q一真一假时, P Q为假。
复合命题P Q的真值表： P
0 0 1 1
Q
P Q
0
1
1
0
0
0
1
1
例1.6 将下列命题符号化，并指出它们的真值：
3如 两 圆O1 , O2的面积相等，则它们的半径相等；反之亦然. 4当王小红心情愉快时，她就唱歌；反之当她唱歌时，
真值为真的命题称为真命题；真值为假的命题为假命题。
说明：
1. 命题必须是陈述性语句，而不能是疑问句、命令句、 感叹句等；
2. 命题语句或者为真或者为假，二者必取其一，即命 题的真值是唯一的
判断句子是否为命题的标准： (1)陈述句 (2)有唯一的真值
例1 判断下列句子是不是命题: (1) 4是素数。
第一部分 数理逻辑

1 2 k
Dr Chen Guangxi
第二章 命题逻辑的推理理论
(4)构造证明法 构造证明法 当前提与结论中命题变项较多时，前几种方法 的工作量太大，不方便，而构造证明法较为方 便。构造证明法必须在给定的推理规则下进行。 常用的推理规则有以下11条： (1)前提引入规则：在证明的任何步骤上，都可 以引入前提。 (2)结论引入规则：在证明的任何步骤上，所得 中间结果都可以作为后继证明的前提。 (3)置换规则：在证明的任何步骤上的公式中的 子公式均可用与之等值的公式置换。
离散数学
Discrete Mathematics
Chen Guangxi
School of Mathematics and Computing Science
第二章 命题逻辑的推理理论
目标:
掌握推理形式结构 熟练运用构造推理方法 了解命题逻辑归结证明
学习建议:
与初中平面几何证明进行对比 勤做练习
Dr Chen Guangxi
第二章 命题逻辑的推理理论
(8)假言三段论 ：
A→B B→C ∴A→C
(9)析取三段论规则： A∨ B A∨ B ¬A ¬B 或者 ∴B ∴A
Dr Chen Guangxi
第二章 命题逻辑的推理理论
(10)构造性二难推理规则：
A → B C → D A∨C ∴B∨ D
(11)合取引入规则：
A B ∴A∧ B
Dr Chen Guangxi
第二章 命题逻辑的推理理论
是重言式类似， 与用 A ⇔ B 表示 A ↔ B是重言式类似，用 A ⇒ B表示A → B 是重言式， 不是联结词 是重言式， ⇒ 符。 推出B的推理正确 的推理正确， 若 A , A ,⋯, A 推出 的推理正确，则记作 ( A1 ∧ A2 ∧ ⋯ ∧ Ak ) ⇒ B 为蕴涵式。 称A⇒B为蕴涵式。 ⇒ 为蕴涵式

*
计算机应用技术研究所
*
联结词的概念
命题可以通过逻辑联结词(逻辑运算)构成新的命题——复合命题。 复合命题的真值依赖于其中简单命题的真值。
*
计算机应用技术研究所
*
联结词举例
【例】 （1）期中考试，张三没有考及格。 （2）其中考试，张三和李四都考及格了。 （3）期中考试，张三和李四中有人考了90分。 （4）如果张三能考90分，那么李四也能考90分。 （5）张三能考90分，当且仅当李四也能考90分。
*
计算机应用技术研究所
*
五个常用联结词
：Negation (NOT) 否定词 ∧ ：Conjunction (AND) 合取词 ∨ ：Disjunction (OR) 析取词 ：Implication (if – then) 蕴涵词 ：Biconditional (if and only if) 等价词
*
计算机应用技术研究所
*
命题的基本概念
【定义】对于任意一个给定的命题，当它不能再分解为更加简单的陈述句时，则称该命题为原子命题；否则，称之为复合命题。
*
计算机应用技术研究所
*
命题的基本概念
【例题】父亲让两个孩子（一男一女）在后院玩耍，并嘱咐他们不要把身上搞脏。然而，在玩的过程中，两个孩子都在额头上沾了泥。当孩子们回来后，父亲首先说他们当中至少有一个人额头上有泥，然后问每个孩子能否确定自己额头上是否有泥，两个孩子都说不能；可是当父亲第二次问同样问题时，两个孩子都说可以。假设：（1）每个孩子都可以看到对方的额头上是否有泥，但不能看见自己的额头；（2）两个孩子都很诚实并且都同时回答每一次提问。试分析两孩子能够做出正确判断的原因。
*
计算机应用技术研究所

例 构造下面推理的证明 2 是素数或合数. 若 2 是素数，则 2 是无理数. 若 2 是无理数，则 4 不是素数. 所以，如果 4 是素数，则 2 是合数. 用附加前提证明法构造证明 （1）设 p：2 是素数，q：2 是合数， r： 2 是无理数，s：4 是素数 （2）形式结构 前提：pq, pr, rs 结论：sq
结论（不正确）是对的 方法四 直接观察出 10 是成假赋值
解（2）答案：推理正确 方法一 方法二 方法三 方法四 真值表法（自己做） 等值演算法（自己做） 主析取范式法（自己做） P 系统中构造证明 ① pr ② rp ③ qr ④ qp （前提引入） （①置换） （前提引入） （③②假言三段论）
（8） 假言三段论规则： AB BC AC （9） 析取三段论规则： AB B A （10） 构造性二难推理规则： AB CD AC BD
(11) 破坏性二难推理规则： AB CD BD AC （12）合取引入规则： A B AB
三、P 中的证明 例 在自然推理系统 P 中构造下面推理的证明： (1)前提：p∨q,q→r,p→s,┐s 结论：r∧(p∨q) (2)前提：┐p∨q, r∨┐q ,r→s 结论：p→s 解 (1)证明： ① p→s 前提引入 ② ┐s 前提引入 ③ ┐p ①②拒取式 ④ p∨q 前提引入 ⑤ q ③④析取三段论 ⑥ q→r 前提引入 ⑦ r ⑤⑥假言推理 ⑧ r∧(p∨q) ⑦④合取 此证明的序列长为 8，最后一步为推理的结论，所以推理正确，r∧(p∨q) 是有效结论。
例
判断下面推理是否正确：
(1)若 a 能被 4 整除，则 a 能被 2 整除；a 能被 4 整除。所以 a 能被 2 整除。 (2)若 a 能被 4 整除，则 a 能被 2 整除；a 能被 2 整除。所以 a 能被 4 整除。 (3)下午马芳或去看电影或去游泳；她没有看电影。所以，她去游泳 了。 (4)若下午气温超过 30℃，则王小燕必去游泳；若她去游泳，她就不 去看电影了。所以王小燕没有去看电影，下午气温必超过了 30℃。

3
推理实例
例1 判断下面推理是否正确 (1) 若今天是 号，则明天是 号. 今天是 号. 所以 明天是 号. 若今天是1号 则明天是5号 今天是1号 所以, 明天是5号 (2) 若今天是 号，则明天是 号. 明天是 号. 所以 今天是 号. 若今天是1号 则明天是5号 明天是5号 所以, 今天是1号 解 设 p：今天是 号，q：明天是 号. ：今天是1号 ：明天是5号 → ∧ → (1) 推理的形式结构 (p→q)∧p→q 推理的形式结构: 用等值演算法 (p→q)∧p→q → ∧ → ⇔ ¬((¬p∨q)∧p)∨q ¬ ∨ ∧ ∨ ∨¬q∨ ⇔ ¬p∨¬ ∨q ⇔ 1 ∨¬ 由定理3.1可知推理正确 由定理 可知推理正确
19
练习1： 练习 ：判断推理是否正确
1. 判断下面推理是否正确 判断下面推理是否正确: (1) 前提：¬p→q, ¬q 前提： → 结论： 结论：¬p ∧¬q→¬ 推理的形式结构: ¬ → ∧¬ →¬p 解 推理的形式结构 (¬p→q)∧¬ →¬ 方法一：等值演算法 方法一： (¬p→q)∧¬ →¬ ∧¬q→¬ ¬ → ∧¬ →¬p ∧¬q)∨¬ ⇔ ¬((p∨q)∧¬ ∨¬ ∨ ∧¬ ∨¬p ∧¬q)∨ ∨¬ ∨¬p ⇔ (¬p∧¬ ∨q∨¬ ¬ ∧¬ ∨¬p ⇔ ((¬p∨q)∧(¬q∨q))∨¬ ¬ ∨ ∧ ¬ ∨ ∨¬ ⇔ ¬p∨q ∨ 易知10是成假赋值，不是重言式，所以推理不正确 易知 是成假赋值，不是重言式，所以推理不正确. 是成假赋值
16
例4 前提：¬(p∧q)∨r, r→s, ¬s, p 前提： ∧ ∨ → 结论： 结论：¬q 证明 用归缪法 ①q 结论否定引入 ② r→s → 前提引入 ③ ¬s 前提引入 ②③拒取式 ④ ¬r ②③拒取式 ⑤ ¬(p∧q)∨r ∧ ∨ 前提引入 ④⑤析取三段论 ⑥ ¬(p∧q) ∧ ④⑤析取三段论 ∨¬q ⑦ ¬p∨¬ ∨¬ ⑥置换 ①⑦析取三段论 ⑧ ¬p ①⑦析取三段论 ⑨p 前提引入 ⑧⑨合取 ¬p∧p ∧ ⑧⑨合取

判断方法一：真值表法
真值表的最后一列全为1，所以（（p∨q）∧┐p） →q为重言式。因而推理正确。
判断方法二：等值演算法
（（p∨q）∧┐p）→q ⇔ （（p∧┐p）∨（q∧┐p））→q ⇔ （ q∧┐p ）→q ⇔ ┐q∨p∨q ⇔1
因为（（p∨q）∧┐p）→q为重言式，所 以推理正确。
判断方法三：主析取范式法
★ ★★
可见，如果能证明★★是重言式，则★也是重言式。 在★★中，原来的结论中的前件A已经变成前提了，称A为 附加前提。称这种将结论中的前件作为前提的证明方法为 附加前提法。
例：在自然推理系统P中构造下面推理的证明 如果小张和小王去看电影，则小李也去看电影。小
赵不去看电影或小张去看电影。小王去看电影。所 以，当小赵去看电影时，小李也去。
前提引入
② ┐s
前提引入
③ ┐p
①②拒取式（A→B）∧┐B⇒┐A
④ p∨q
B）∧┐B⇒A
⑥ q→r
前提引入
⑦r
⑤⑥假言推理（A→B）∧A⇒B
⑧ r∧（p∨q） ⑦④合取引入
（2）前提：┐p∨q，r∨┐q，r→s 结论：p→s
证明：
① ┐p∨q 前提引入
② p→q
①置换
（A→B）∧（C→D）∧（┐B∨┐D） ⇒（┐A∨┐C）
（12）合取引入规则：若证明的公式序列中出现过 A和B，则A∧B是A和B的有效结论。
推理规则（12个）
（1）前提引入规则 （2）结论引入规则（隐规则） （3）置换规则：等值置换 （4）假言推理规则：（A→B）∧A⇒B （5）附加规则：A⇒（A∨B） （6）化简规则：A∧B ⇒A （7）拒取式规则：（A→B）∧┐B⇒┐A （8）假言三段论规则：（A→B）∧（B→C）⇒（A→C） （9）析取三段论规则：（A∨B）∧┐B⇒A （10）构造性二难推理规则 （11）破坏性二难推理规则 （12）合取引入规则

22
实例：公安破案
• 一个公安人员审查一件盗窃案，已知的 事实如下：A或B盗窃了钻石；若A盗窃 了钻石，则作案时间不能发生在午夜前； 若B证词正确，则在午夜时屋里灯光未灭； 若B证词不正确，则作案时间发生在午夜 前；午夜时屋里灯光灭了。谁盗窃了钻 石呢？
23
推பைடு நூலகம்正确, q是有效结论
17
归结证明法
归结规则 A B AC \BC 理由 (pq)pr)(qr)
(pq)pr))(qr) (pq)pr)qr (pq)q)pr)r) (pq)pr)
18
归结证明法(续)
在自然推理系统P中只需下述推理规则: (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 化简规则
(5) 合取引入规则
(6) 归结规则
19
归结证明法的基本步骤
1. 将每一个前提化成等值的合取范式, 设所有合取范式的 全部简单析取式为A1, A2,…, At 2. 将结论化成等值的合取范式B1B2…Bs, 其中每个Bj 是简单析取式 3. 以A1,A2,…,At为前提, 使用归结规则推出每一个Bj, 1js
10
实例
例3 构造推理的证明: 若明天是星期一或星期三, 我就有 课. 若有课, 今天必需备课. 我今天下午没备课. 所以, 明天 不是星期一和星期三.
解 设 p:明天是星期一, q:明天是星期三，
r:我有课， s:我备课 前提: (pq)r, rs, s
结论: pq
11
实例(续)
14
归谬法(反证法)
欲证明 前提：A1, A2, … , Ak 结论：B 将B加入前提, 若推出矛盾, 则得证推理正确. 理由: A1A2…AkB (A1A2…Ak)B (A1A2…AkB) 括号内部为矛盾式当且仅当 (A1A2…AkB)为重言式