当前位置：文档之家 › 离散数学-1-8推理理论共24页

离散数学-1-8推理理论共24页

  • 格式：ppt
  • 大小：158.50 KB
  • 文档页数：24

下载文档原格式

  / 24

合集下载

离散数学课件1.8

离散数学课件1.8


∀ xA( x) ∴ A( y )
应用US规则的条件是: A(x)对于y必须是自由的。 设 A( x) = ∃y( x > y) 则 ∀xA( x) = ∀x∃y( x > y) , x,y的 的 个体域为R， 是一真命题. 个体域为 ， 是一真命题 若应用US得 则是错误的。 若应用 得 ∃y( y > y) ，则是错误的。 正确的做法是换成 ∃y( z > y) ( z ∈ R)
用变元x取代 ， 则要求在 原公式中y不 用变元 取代y， 则要求 在 原公式中 不 取代 能出现在量词(∀ 或 ∃ 的辖域之内 的辖域之内。 能出现在量词 ∀x)或(∃x)的辖域之内。
16
第一章 数理逻辑
推理规则的正确使用（4）
推导4： （1）G(x, c) （2）(∃x)G(x, x) P EG,(2)
17
第一章 数理逻辑 1.8.3 推理举例 例1 根据前提集合：同事之间总是有工作矛盾的，张平和李 明没有工作矛盾, 能得出什么结论? ; 解 设P(x, y): x和y是同事关系, Q(x, y): a: 张平, x和y有工作矛盾, b: 李明,
则前提是:∀x∀y(P(x,y) → Q(x,y)) ， ┐Q(a,b) ∀ ∀
6
第一章 数理逻辑 这一规则也可写为:
∀ xA( x)推得A( x) 或
它的意义是, 全称量词可以删除。
∀ xA( x) ⇒ A( x).
7
第一章 数理逻辑 (2) 存在指定规则 存在特定规则 存在量词消去规则 ) 存在指定规则(存在特定规则 存在特定规则/存在量词消去规则 (Existential Specification)简记为ES。
15
第一章 数理逻辑
离散数学课件03命题逻辑的推理理论

离散数学课件03命题逻辑的推理理论


((┐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
命题逻辑的推理理论
概念
描述问题 的句子
离散数学 推理理论

离散数学 推理理论

S ( P∨Q) S ∨ (P∨Q) ( S ∨P ) ∨Q ( S ∧ P ) ∨Q ( S ∧ P ) Q 例题 证明: (P∨Q) ∧(P R) ∧(Q S) S ∨ R
作业：P46(1)a, b (2)a,c (3)a,c (4)c
结束
T规则：由前提得出的阶段性有效结论（由一个或多 个公式重言蕴含着的公式）也可以在证明中使用。
P43两个表要熟练
例2：用推理规则证明下列各式。
1 . 证明: (P∨Q) ∧(P R) ∧(Q S) S ∨ R
(1) P∨Q
Ｐ
(2)E Ｐ
证法2见书P44
(4) P S
T (7) E
(9) C ( D E)
T (8) E
(10) D E
T (5) (9) I
(11) (D∧ E) (12) F (D∧ E) (13) F (14) BF (15) A(BF)
T (10) E P T (11) (12) I CP CP
3 . 半反证法
当结论是析取式，具有形式P∨Q时，我们把其中一析取 项的否定（ P或 Q）作为假设前提，并和其它前提 一起共同得出另外一析取项（ Q或P） 。 即要证S P∨Q，可通过证明( S ∧ P ) Q 半反证法的正确性证明：
Ｔ (1) I Ｔ (2) (3) I Ｐ
(6) P (7) ( P ∧S)
Ｔ (4) (5) I Ｐ
(8) P ∨ S (9) S
Ｔ (7) E Ｔ (6) (8) I
例3：公安人员破案问题。
一公安人员审查某工厂失窃案，他认为下列情况 是真的： (1)有两个怀疑对象，保管员小王和材料科长老李； (2)值班员小张工作一贯负责； (3)失窃案发生的那天白天，老李去兄弟厂开会； (4)如果晚上仓库上锁，就不会发生失窃案； (5)如果晚上仓库未上锁或灯未亮，则值班员小张失职。 请问谁是盗窃犯？
离散数学命题逻辑推理理论

离散数学命题逻辑推理理论


构造性二难
(A®B)Ù(ØA®B) Þ B
构造性二难(特殊形式)
(A®B)Ù(C®D)Ù( ØBÚØD) Þ (ØAÚØC) 破坏性二难
自然推理系统P
自然推理系统P由下述3部分组成:
1、 字母表
命题变项符号: p,q,r,…,
pi,qi,ri,…
联结词:
,
,
,
,
括号与逗号: ( ), , 2、 合式
明天就是5号、 解 设 p: 今天就是1号, q: 明天就是5号 推理得形式结构为 (p®q)Ùp®q 证明 用等值演算法
(p®q)Ùp®q Û Ø((ØpÚq)Ùp)Úq Û ((pÙØq)ÚØp)Úq Û ØpÚØqÚq Û 1
得证推理正确
实例( 续 )
(2) 若今天天冷,小王就穿羽绒服。小王就穿羽绒服。 所以, 今天天冷。
r:我有课,
s:我备课
前提: (pÚq)®r, r®s, Øs
结论: ØpÙØq
实例( 续 )
前提: (pÚq)®r, r®s, Øs
结论: ØpÙØq
证明 ① r®s ② Øs ③ Ør ④ (pÚq)®r
前提引入 前提引入 ①②拒取式 前提引入
Ø(pÚq)
③④拒取式
⑥ ØpÙØq
置换
结论有效, 即明天不就是星期一与星期三
公式
3. 推理规则
前提引入规则
结论引入规则
置换规则
自然推理系统P(续)
(4) 假言推理规则 A®B A
\B (5) 附加规则
A \AÚB (6) 化简规则
AÙB \A
(7) 拒取式规则 A®B ØB
\ØA (8) 假言三段论规则
A®B B®C
离散数学课件03命题逻辑的推理理论

离散数学课件03命题逻辑的推理理论


③ p
④ q ⑤ q→r
Hale Waihona Puke ②化简②化简 ①③假言推理
⑥ r
⑦ r∨s ⑧ ┐r→s
④⑤假言推理
⑥附加 ⑦置换
例题
例3.4 在自然推理系统P中构造下面推理的证明： 若数a是实数，则它不是有理数就是无理数；若a不能表 示成分数，则它不是有理数；a是实数且它不能表示成分数。 所以a是无理数。 构造证明： （1）将简单命题符号化： 设 p：a是实数。 r：a是无理数。 （2）形式结构： 前提：p→(q∨r), ┐s→┐q, p∧┐s 结论：r q：a是有理数。 s：a能表示成分数。
若一个推理的形式结构与某条推理定律对应的蕴涵 式一致，则不用证明就可断定这个推理是正确的。
2.1节给出的24个等值式中的每一个都派生出两条推 理定律。例如双重否定律A A产生两条推理定 律A A和 AA。 由九条推理定律可以产生九条推理规则,它们构成了 推理系统中的推理规则。
–推理的形式结构 –自然推理系统P
本章与后续各章的关系
–本章是第五章的特殊情况和先行准备
3.1 推理的形式结构 3.2 自然推理系统P


本章小结
习题

作业
3.1 推理的形式结构
数理逻辑的主要任务是用数学的方法来研究数学中的 推理。 推理是指从前提出发推出结论的思维过程。
前提是已知命题公式集合。
(┐q∨p) ∨ q 1
推理定律--重言蕴含式
(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)
离散数学-第一部分-数理逻辑-第五章 一阶逻辑等值演算与推理

离散数学-第一部分-数理逻辑-第五章 一阶逻辑等值演算与推理

(4) 量词分配等值式 ① x(A(x)B(x)) xA(x)xB(x) ② x(A(x)B(x)) xA(x)xB(x)
注意：对，对无分配律
5
量词分配等值式证明
设A(x)，B(x)是任意的含自由出现个体变项x的公式，则
（1）x(A(x)∧B(x)) xA(x)∧xB(x) （2）x(A(x)∨B(x)) xA(x)∨ xB(x)
置换规则、换名规则、代替规则
1. 置换规则
设(A)是含A的公式, 那么, 若AB, 则(A)(B).
2. 换名规则 设A为一公式，将A中某量词辖域中个体变项的所有约束 出现及相应的指导变元换成该量词辖域中未曾出现过的个 体变项符号，其余部分不变，设所得公式为A，则AA.
3. 代替规则 设A为一公式，将A中某个个体变项的所有自由出现用A中 未曾出现过的个体变项符号代替，其余部分不变，设所得 公式为A，则AA.
14
实例
解法二
xy(F(x)G(y)) x(F(x)yG(y))
辖域缩小等值式
x(F(x)G(a)G(b)G(c))
(F(a)G(a)G(b)G(c))
(F(b)G(a)G(b)G(c))
(F(c)G(a)G(b)G(c))
15
实例
(2) xyF(x,y) xyF(x,y)
x(F(x,a)F(x,b)F(x,c)) (F(a,a)F(a,b)F(a,c))
而
x(F(x)G(x))
x(F(x)y(G(y)H(x,y))) 不是前束范式，
17
前束范式存在定理
定理5.1（前束范式存在定理） 一阶逻辑中的任何公式都存在与之等值的前束范式
例4 求下列公式的前束范式 (1) x(M(x)F(x)) 解 x(M(x)F(x))
离散数学知识点

离散数学知识点

离散数学知识点(总23页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--说明：定义：红色表示。

定理性质：橙色表示。

公式：蓝色表示。

算法:绿色表示页码：灰色表示数理逻辑：1.命题公式：命题，联结词(，，，，)，合式公式，子公式2.公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式3.范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式4.联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集5.推理理论：重言蕴含式，有效结论，P规则，T规则， CP规则，推理6.谓词与量词:谓词，个体词，论域，全称量词，存在量词7.项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入8.公式语义:解释，赋值，有效的，可满足的，不可满足的9.前束范式:前束范式10.推理理论:逻辑蕴含式，有效结论，-规则（US），+规则（UG），-规则(ES)，+规则(EG), 推理集合论：1.集合: 集合, 外延性原理, , , , 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关系3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R),对称闭包 s(R), 传递闭包 t(R)4.等价关系: 等价关系, 等价类, 商集, 划分5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下界6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集代数结构：1.运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺元,零元,逆元2.代数系统：代数系统，子代数，积代数，同态，同构。

离散数学课件第二章 一阶逻辑

离散数学课件第二章 一阶逻辑


§2.1
一阶逻辑的基本概念
原因：命题逻辑不考虑命题之间的内在联系
和数量关系。
要反映这种内在联系，就要对命题逻 辑进行分析 , 分析出其中的个体词、谓词和 量词，再研究它们之间的逻辑关系，总结出 正确的推理形式和规则，这就是一阶(谓词) 逻辑的研究内容。 办法：将命题再次细分。
解决这个问题的方法： 在表示命题时，既表示出主语，也表示 出谓语，就可以解决上述问题。这就提出了 谓词的概念(谓词是用来刻划个体词的性质 或事物之间的关系的词,谓词S(x)相当于一 个函数).
§2.1 一阶逻辑的基本概念
2.1.1 个体、谓词和命题函数 在谓词逻辑中，将原子命题分解为谓词和个体两部分。
主语 谓语 宾语
讨论对象 对象的性质或关系
讨论对象
个体词（组）
谓词
个体词（组）
1、定义：在原子命题中，所描述的对象称为个体；用 以描述个体的性质或个体间关系的部分，称为谓词。
例2.1：分析下列个命题中的个体和谓词
如何表示？
2.1.3 命题函数 谓词本身并不是命题，只有谓词的括号内填入足够 的个体，才变成命题。 设 H(x) 是谓词 表示 x “能够到达山顶” ， l 表示个体李四， t 表示老虎， c 表示汽车， 那么H（l）， H（t）， H（c），等分别表示各 个不同的命题：但它们有一个共同的形式， 即 H（x） 当 x 分别取 l、 t、 c 时 就表示“李四能够到达山顶”，“老虎能够到达山 顶”，“汽车能够到达山顶”。
Discrete Mathematics
刘师少
Tel： 86613747（h） E-mail： lss@
授课:
51学时
教学目标:
知识、能力、素质
第二章 一阶逻辑
离散数学---推理理论

离散数学---推理理论


实例分析
西 华 大 学 制 作
判断推理是否正确：张红不管有无空闲都不看电影。张红看了电影。所以张 红有空闲时间又没有空闲时间。 解：P:张红有空闲时间；Q：张红看电影 。 前提：A1=P∨ P→ Q A2=Q 结论：A=P∧ P 问题：该结论是否有效结论。(该推理是否正确)。
P 0 0 1 1
自然推理系统P
西 华 大 学 制 作
自然推理系统
特点：可以从任意给定的前提出发，
形式系统
应用系统中的推理进行推演，得到 的结论在系统中被认为是有效的。
公理系统
特点：只能从几个给定的公理出发， 应用系统中的推理规则进行推演，
得到的结论是系统中的定理。
自然推理系统P
自然推理系统P定义如下：
1.字母表
§1.6 推理理论
西 华 大 学 制 作
一、有效论证推理规则 二、基本蕴涵式 三、自然推理系统P 四、推理证明的方法
一、有效论证与推理规则
西 华 大 学 制 作
• 定义：A1∧A2∧…∧An→A,其为永真式，则称 前提A1,A2,…,An得到有效结论A；从前提公式得 到有效结论的过程称为正确推理。 • 若AB是永真式，则记为AB； • 若A→B是永真式，则记为AB。 • 前提一致和不一致： • 如果前提A1∧A2∧…∧An为可满足式，则 为前提A1,A2,…,An一致。
西 (1)命题常元，命题变元：P,Q,R,…,Pi,Qi,…,1,0(T,F) 华 大 (2)命题联结词：、∧、∨、→、 学 (3)括号：(,) 制 2.合式公式：(略) 作
3.推理规则：
(1).前提引入规则(P规则)：在证明的任何步上，都可引入前 提； (2).结论引用规则(T规则)：在证明的任何步上，所得的结论 都可作为证明得前提； (3).置换规则：在证明的任何步上，命题公式的任何子命题 公式都可以用与之等价的命题公式置换。 (4).永真蕴涵规则：使用基本蕴涵式，常常将条件用‘，’
离散数学18

离散数学18


15
推理理论
设Г ={P→Q,┐(Q∨R)},G=┐P。 证明：Г G
。证：⑴ ┐(┐P)
P(附加前提)
⑵P
T,⑴,E
//E1
⑶ P→Q
P
⑷Q
T,⑵,⑶,I
//I11
⑸ ┐(Q∨R) P
⑹ ┐Q∧┐R //E9
T,⑸,E
⑺ ┐Q
T,⑹,I
//I2
⑻ Q∧┐Q
T,⑷,⑺,I
//I9
离散数学
16
推理理论
暗而明，暮则自明而暗，或暗或明，变化不一，这是山间早晚的景色。野花开放，有一股清幽的香味，好的树木枝叶繁茂，形成浓郁的绿荫。天高气爽，霜色洁白，泉水浅了，石底露出水面，这是山中四季
的景色。意译法：太阳升起，山林里雾气开始消散，烟云聚拢，山谷又开始显得昏暗，清晨自暗而明，薄暮又自明而暗，如此暗明变化的，就是山中的朝暮。春天野花绽开并散发出阵阵幽香，夏日佳树繁茂
并形成一片浓荫，秋天风高气爽，霜色洁白，冬日水枯而石底上露，如此，就是山中的四季。【教学提示】翻译有直译与意译两种方式，直译锻炼学生用语的准确性，但可能会降低译文的美感；意译可加强
译文的美感，培养学生的翻译兴趣，但可能会降低译文的准确性。因此，需两种翻译方式都做必要引导。全文直译内容见《我的积累本》。目标导学四：解读文段，把握文本内容1．赏析第一段，说说本文
//I10 //I12 // E16
离散数学
22
智仙也。名之者/谁？太守/自谓也。太守与客来饮/于此，饮少/辄醉，而/年又最高，故/自号曰/醉翁也。醉翁之意/不在酒，在乎/山水之间也。山水之乐，得之心/而寓之酒也。节奏划分思考“山行/六七里”
为什么不能划分为“山/行六七里”？
离散数学--第二章 命题逻辑的推理理论

离散数学--第二章 命题逻辑的推理理论

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为蕴涵式。 ⇒ 为蕴涵式

离散数学第三章 命题逻辑的推理理论

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 ∧ ⑧⑨合取

离散数学逻辑推理


常见的蕴涵规则表
P∧QP P∧QQ P P ∨ Q
P,Q P ∧ Q ¬P, P ∨ Q Q P, P → Q Q
QP∨Q
¬Q, P → Q ¬P
¬P P → Q QP→Q ¬(P → Q ) P ¬(P → Q ) ¬Q
P → Q, Q → R P → R P ∨ Q, P → R, Q → R R A → B (A∨ C ) →(B ∨ C) A → B (A ∧ C ) →(B ∧ C)
T (1) I1 T (1) I2 P
(5) (Q∧Ｒ (6) Q∨R (7) Q (8) P→Q
T(3)(4) I12 T (5) E8 T (2)(6) I10 P
(9) P
T (7)(8) I12
(10)(R∧S)→P CP
【example】 A→ (B→C), D ∨ A, B D → C。
【example】求证 P→Q，Q→R，P R Proof：
序号 前提或结论 所用规则 从哪几步得到 所用公式
(1)
P
P
(2)
PQ P
(3)
Q
T
(4)
Q→R P
(1)(2) I11
(5)
R
T
(3)(4)
I11
（注公式I11为： P,P→Q Q ）
【example】证明(P ∨ Q) ∧ (P → R) ∧ (Q → S) S ∨ R.
CP规则
间接证法的另一种情况是：
若要证H1∧H2∧....∧Hm (R →C)。设H1∧H2∧....∧Hm为S ，即证S (R →C)或S (R ∨ C)，故S → (R ∨ C)为永真 式。
因为S → (R ∨ C) S ∨ (R ∨ C) (S ∨ R) ∨ C (S∧R) ∨ C (S∧R) → C ,

离散数学---谓词逻辑推理

S(x): x 是理科生； T(x): x 是优等生。 要引入的个体常项是：c : 小张。 前提：x(P(x)(Q(x)S(x)))、x(P(x)T(x))、 Q(c)T(c)
结论：P(c)S(c)，
推理举例(续)
西 华 大 学
前提：x(P(x)(Q(x)S(x)))、 x(P(x)T(x))、Q(c)T(c) 结论：P(c)S(c)， 证明: (1). x(P(x)(Q(x)S(x))) P规则 (2). P(c)(Q(c)S(c)) 全称量词消除规则 (3). P(c) CP规则 (4). Q(c)S(c) (2)(3)I (5). Q(c)T(c) P规则 (6). Q(c) (5)I (7). S(c) (4)和(6) I
在证明的任何步骤上一阶公式中的任何子公式都可用与之等值的公式置换得到证明的公式序列的另一公式证明的公式序列的另公式
第二章 谓词逻辑
西 华 大 学
第3节 一阶逻辑推理理论
推理的定义
西 华 大 学
称蕴涵式(A1A2…Ak)B为推理的形式结构， A1, A2, …, Ak为推理的前提，B为推理的结论。 若(A1A2…Ak)B为永真式，则称从前提A1,
// 前提
(2). P(a)Q(a) // 全称量词消除规则
举例：全称量词消除规则
西 华 B 大 学
指出下列推导中的错误，并加以改正： (1). x P(x)Q(x) // 前提 (2). P(y)Q(y) // 全称量词消除规则
量词 x 的辖域为 P(x) ，而非 P(x)Q(x) ，所以不 能直接使用全称量词消除规则。
举例：全称量词消除规则
西 华 A 大 学
指出下列推导中的错误，并加以改正： (1). (x)(P(x)Q(x))// 前提 (2). P(a)Q(b) // 全称量词消除规则

离散数学

第一章命题逻辑1.1 命题及其表示方法1.2 联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其它联结词1.7 对偶与范式1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题的表示（一个命题标识符（比如P）表示确定的命题）重点：如何判断语句是否为命题。

1.2 联结词否定⌝合取∧析取∨条件→双条件↔重点：五种联结词的含义、真值表1.3 命题公式与翻译命题公式符号化：所谓命题的符号化就是把一个用文字叙述的句子相应地写成由命题标识符、联结词和括号表示的合式公式。

命题符号化的重要性命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。

重点：命题的符号化符号化应该注意下列事项:①确定给定句子是否为命题。

②句子中连词是否为命题联结词。

③要正确地表示原子命题和适当选择命题联结词。

1.4 真值表与等价公式真值表的构造方法(1) 找出公式中所含的全体命题变元P1, P2, …, Pn, (若无下角标就按字典顺序排列), 列出2n个赋值. 赋值从00…0开始, 然后按二进制加法依次写出各赋值, 直到11…1为止.(2) 按从低到高的顺序写出公式的各个层次.(3) 对应各个赋值计算出各层次的真值, 直到最后计算出公式的真值.等价关系的含义等价式的判别方法•真值表法•等价演算法基本等价式（必须掌握）(1)对合律（双重否定）：⌝⌝P⇔P(2)幂等律：P∧P⇔P，P∨P⇔P(3)结合律：(P∧Q)∧R⇔P∧(Q∧R)，(P∨Q)∨R⇔P∨(Q∨R)(4)交换律：P∧Q⇔Q∧P，P∨Q⇔Q∨P(5)分配律：P∧(Q∨R)⇔(P∧Q)∨(P∧R)，P∨(Q∧R)⇔(P∨Q)∧(P∨R)(6)德·摩根律：⌝ (P∧Q) ⌝⇔P∨⌝Q，⌝ (P∨Q) ⌝⇔P∧⌝Q(7)吸收律：P∧(P∨Q)⇔P，P∨(P∧Q)⇔P(8)同一律：P∧T⇔P，P∨F⇔P(9)零律：P∧F⇔F，P∨T⇔T(10)否定律：P∧⌝P⇔F，P∨⌝P⇔T(11) 条件式转化律：P→Q⌝⇔P∨Q，P→Q⌝⇔Q→⌝P(12) 双条件式转化律：P↔Q ⇔(P→Q)∧(Q→P) ⇔(P∧Q)∨(⌝P∧⌝Q)⌝ (P↔Q) ⇔P⌝↔Q ⌝⇔P↔Q(13) 输出律(CP规则)：P→(Q→R) ⇔(P∧Q)→R重点：等价式的证明、基本等价式1.5 重言式与蕴含式重言式或永真公式定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。

离散数学命题逻辑


Q）
(MQ) P（附加前提）
(2) SR
P
第一章命题逻辑
本题即证：M Q, MS, SR R→Q (3) RS T(2)E (4) S T(1)(3)I (5) MS P (6) M T(4)(5)I (7) (MQ) P (8) MQ T(7)E (9) (MQ)∧(QM) T(8)E (10) QM T(9)E (11) MQ T(10)E (12) Q T(6)(11)E (13) R→Q CP
第一章命题逻辑
请根据下面事实，找出凶手：
1. 清洁工或者秘书谋害了经理。 2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。 3.如果秘书的证词是正确的，则谋害发生在午夜前。 4.如果秘书的证词不正确，则午夜时屋里灯光未灭。 5. 如果清洁工富裕，则他不会谋害经理。 6.经理有钱且清洁工不富裕。 7.午夜时屋里灯灭了。 令A:清洁工谋害了经理。 B:秘书谋害了经理。 C:谋害发生在午夜前。 D:秘书的证词是正确的. E:午夜时屋里灯光灭了。 H:清洁工富裕. G:经理有钱. 命题符号为： A∨B,AC,DC,DE,HA,G∧H,E ?
第一章命题逻辑
例题1-8.2 用命题逻辑推理方法证明下面推理的 有效性： 如果我学习，那么我数学不会不及格。如果我不 热衷于玩朴克，那么我将学习。但是我数学不 及格。因此，我热衷于玩朴克。 解 设 P：我学习。 Q：我数学及格。 R：我热衷于玩朴克。 于是符号化为： P→Q，R→P，Q R
1-8 推理理论
第一章得出一个新 的判断的思维过程。称这些已知的判断为前提。 得到的新的判断为前提的有效结论。 实际上，推理的过程就是证明永真蕴含式的过程， 即令H1，H2，…，Hn是已知的命题公式(前提)， 若有 H1∧H2∧....∧Hn C 则称C是H1，H2，…Hn的有效结论，简称结论。

离散数学---推理理论共19页


大学⑴
p
制作⑵ p ((r∧s)q)
p规则 p规则
⑶ (r∧s)q
⑴⑵I
⑷ s
p规则
⑸ s ∨ r
⑷I
⑹ (r∧s)
⑸E
⑺ q
⑶⑹I
西 华 大 学 制 作
推理证明
推理证明的方法
前提的合取→结论 是永真式
演绎证明 直接证明法 附加前提证法 (CP)
间接证明法
归纳证明
归谬法(反证法)
附加前提证法
(CP)
一、有效论证与推理规则
西 华
• 定义：A1∧A2∧…∧An→A,其为永真式，则称 前提A1,A2,…,An得到有效结论A；从前提公式得
大 到有效结论的过程称为正确推理。
学
制 • 若AB是永真式，则记为AB；
作
•
若A→B是永真式，则记为AB。
• 前提一致和不一致：
• 如果前提A1∧A2∧…∧An为可满足式，则 为前提A1,A2,…,An一致。
西华大学(((453)))...如如午果夜果李时李四屋四证内证词灯词不灭正正了确确。，，则则午作夜案时时屋间内在灯午光夜未前灭；；
设 P:张三盗窃录像机； Q:李四盗窃录像机; R:作案时间发生在午夜前； S:李四证词正确； M:午夜时灯光未灭。
制 作 则前提为: (1) P∨Q,
(2)P→ R, (3)S→M,
结论：Q。
西 华
证： ① M
大
学
② S→M
制 作
③ S
④ S→R
P
P ①② I拒取式 P
⑤R
③ ④ I假言推理
⑥ P→ R
P
⑦ P
⑤ ⑥I拒取式
⑧ P∨Q
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

当
H1∧H2∧…∧HnC，
5. 称C是一组前提H1，H2，…，Hn 的有效结论。
6.*判断有效结论的过程就是论证过程，基本方法是
真值表法、直接证法、间接证法。
2
二、真值表法
由定义1-8.1可以看出，要证明C是一组前提H1，H2，…，Hn 的有效结 论，只需证明H1∧H2∧…∧Hn→C为重言式。而证明一个公式为重言 式，可以用真值表、等值演算、主析(合)取范式或已知的蕴含式等方 法进行。用等价演算和主析(合)取范式证明重言式的方法前面已经讨 论过了，我们已经非常熟悉了。这里仅对真值表法作简单说明。 （1）真值表法
公式都可以用与之等价的公式置换。(等价式表） 合取引入规则：任意两个命题公式A,B可以推出A∧B 常用的蕴含式和等价式见P43表1-8.3 表1-8.4
7
直接证法（直接推理）
例题１：用直接推理法证明
(Ｐ∨Ｑ)∧(Ｐ→Ｒ)∧ (Ｑ→Ｓ) Ｓ∨Ｒ 证法1: (1)Ｐ∨Ｑ P -(P规则，引入前提)
(2) Ｐ→Q T(1) E -(对(1)式T规则,根据E16蕴含等值式) (3)Ｑ→Ｓ P -(P规则，引入前提) (4) Ｐ→Ｓ T(2),(3) I-(对(2),(3)式Ｔ规则，根据I13 假言三
1
一、有效推理
1.假设一些命题为Ｔ，并使用一些公认的规则，得
到另外的命题，形成结论，这种过程就是论证。
Байду номын сангаас
2. 定义1-8.1 设A和C是2个命题公式，当且仅当A→C
为一重言式，即AC，则称C为A的有效结论。或
C可由A逻辑的推出。A叫做C的前提。
3.上述定义可以推广到n个前提的情况：
4. 设H1，H2，…，Hn,C是n+1个命题公式,当且仅
设P1，P2，…，Pn出现于前提H1，H2，…，Hm 和结论C的 全部命题变元，假定对P1，P2，…，Pn作了全部的真值指 派，这样就能对应地确定H1，H2，…，Hn 和C的所有真值，
列出这个真值表，即可看出 H1∧H2∧…∧HmC 是
否成立
即找出H1，H2，…，Hm 均为１的行，对于每一个这样的行，若 C也为１,则上式成立。或C为０， H1，H2，…，Hm 中起码有一 个为０
即证明：(P→Q)∧(Q→R)∧¬R¬P
4
二、真值表法
作公式P→Q，Q→R，¬R，¬ＨP的1真值表Ｈ2
Ｈ3
C
P Q R P→Q Q→R ¬R ¬P
000
1
1
1
1
001
1
1
0
1
010
1
0
1
1
011
1
1
0
1
100
0
1
1
0
101
0
1
0
0
110
1
0
1
0
111
1
1
0
0
从表中可以看出:P→Q，Q→R，¬R都为1的行(赋值000的行)，¬P也为1。
的真值均为Ｆ，则称公式H1，H2，…，Hm是
不相容的。
11
间接证法（间接推理）
将不相容的概念应用于命题公式的证明(归谬法)
设有一组前提H1，H2，…，Hn ，要推出结论C，
即要证 H1∧H2∧…∧Hn C ，
令 SH1∧H2∧…∧Hn 则上式可以简记为 SC 由永真蕴含的定义有 1S→C¬S∨C 两边否定 0S∧¬C H1∧H2∧…∧Hn∧¬C 即要证明C是前提H1，H2，…，Hn的有效结论，只 须证明 H1∧H2∧…∧Hn∧¬C0
3
二、真值表法
例：分析事实：“如果我有时间，那么我就去上街；如
果我上街，那么我就去书店买书；但我没有去书店买书， 所以我没有时间。”。试指出这个推理前提和结论，并证 明结论是前提的有效结论。
解：令 Ｐ：我有时间。 Ｑ：我去上街。 Ｒ：我去书店买书。
根据题意，前提为：Ｐ→Ｑ，Ｑ→Ｒ，¬Ｒ 结论为：¬Ｐ 以下证明¬Ｐ是一组前提Ｐ→Ｑ,Ｑ→Ｒ,¬Ｒ的有效结论。
(或¬P为0的行(赋值100，101，110，111的行) P→Q，Q→R，¬R至少有 一个为0）
所以 (P→Q)∧(Q→R)∧¬R¬P
5
三、命题逻辑的推理理论
当推理中包含的命题变元较多时，真值表 法或等值演算法，主析取范式法等方法的 演算量太大。给推理带来了困难。为此引 入命题逻辑的推理理论。命题逻辑的推理 是一个描述推理过程的命题公式序列，其 中的每个命题公式或者是已知前提，或者 是由某些前提应用推理规则得到的结论(中 间结论或推理中的结论)。它有两种方法： 直接证法（直接推理）和间接证法（间接 推理）。
T⑴⑵ I P
假言推理(I11)
⑸R
T⑶⑷ I
假言推理(I11)
10
间接证法（间接推理）
定义1-8.2 假设公式H1，H2，…，Hm中的 命题变元P1，P2，…，Pn，对于P1，P2，…， Pn的一些真值指派，如果能使
H1∧H2∧…∧Hm的真值为Ｔ，则称公式H1，
H2，…，Hm是相容的。如果对于P1，P2，…， Pn的每一组真值指派，使H1∧H2∧…∧Hm
证法2: (1)Ｐ→Ｒ
P
(2)Ｐ∨Ｑ→R∨Ｑ T(1) I
(3) Ｑ→Ｓ
P
(4)Ｑ∨R →S∨R T(3) I
(5)Ｐ∨Ｑ→S∨R T(2)(4) I
(6)Ｐ∨Ｑ
P
(7)Ｓ∨Ｒ
T(5),(6) I
9
直接证法（直接推理）
• 用直接推理法证明(P→Q)∧(Q→R)∧PR
证明： ⑴ P→Q
P
⑵P
P
⑶Q ⑷ Q→R
段论)
(5) S→P T(4) E -(对(４)式T规则,根据E16蕴含等值式) (6)Ｐ→Ｒ P -(P规则，引入前提) (7) S→R T(5),(6) I (对(5),(6)式Ｔ规则，根据I13 假言三段
论)
(8)Ｓ∨Ｒ T(7) E -(对(7)式T规则,根据E16蕴含等值式)
8
直接证法（直接推理）
6
直接证法（直接推理）
⑴ 直接证法（直接推理） 基本思想是：由一组前提出发，利用一些公认的规则，根 据已知的等价式或蕴含式，推演得到有效结论。 公认的推理规则有4条：
P规则：前提在推导过程中的任何时候都可以引入使用。 T规则：推导中，如果一个或多个公式蕴含着公式S，则 公式S可以引入到以后的推理之中。 置换规则：在推导过程的任何步骤上，命题公式中的子
在数学和其它自然科学中，经常要考虑从某些前 提A1、A2、……An出发，能推导出什么结论。 数理逻辑的主要任务是用逻辑的方法研究数学中 的推理。所谓推理是指从前提出发，应用推理规 则推出结论的思维过程。任何一个推理都由前提 和结论两部分组成。前提就是推理所根据的已知 命题，结论则是从前提出发通过推理而得到的新 命题。 要研究推理，首先应该明确什么样的推理是有效 的或正确的