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

离散数学PPT课件

离散数学第3讲命题逻辑的推理理论

离散数学PPT课件

本讲说明本讲的主要内容–推理的形式结构–构造推理的证明

本讲与后续各讲的关系–本讲是一阶逻辑推理的特殊情况和先行准备

2010-9-25

离散数学PPT课件

3.1推理的形式结构 3.2构造推理的证明本讲小结习题作业

2010-9-25

离散数学PPT课件

3.1推理的形式结构数理逻辑的主要任务是用数学的方法来研究数学中的推理。推理是指从前提出发推出结论的思维过程。前提是已知命题公式集合。结论是从前提出发应用推理规则推出的命题公式。证明是描述推理正确或错误的过程。要研究推理，首先应该明确什么样的推理是有效的或正确的。2010-9-25 4

离散数学PPT课件

有效推理的定义定义3.1设A1,A2,…,Ak和B都是命题公式，若对于

A1,A2,…,Ak和B中出现的命题变项的任意一组赋值， (1)或者A1∧A2∧…∧Ak为假; (2)或者当A1∧A2∧…∧Ak为真时，B也为真;则称由前提A1,A2,…,Ak推出B的推理是有效的或正确的，并称B是有效结论。

2010-9-25

离散数学PPT课件

关于有效推理的说明由前提A1,A2,…,Ak推结论B的推理是否正确与诸前提的排列次序无关。 T={A1,A2,…,Ak}由 T推B的推理记为T→B若推理是正确的，记为 T B若推理是不正确的，记为 T B

2010-9-25

离散数学PPT课件

例题例3.1判断下列推理是否正确。(真值表法)(1) (p (2) (p

∧ (p→q))→ q∧ (q→p))→ q

正确不正确 q 0 1 0 1 p∧(q→p) 0 0 1 1 q 0 1 0 17

p 0 0 1 12010-9-25

q 0 1 0 1

p∧(p→q) 0 0 0 1

离散数学PPT课件

有效推理的等价定理定理3.1命题公式A1,A2,…,Ak推B的推理正确当且仅当 (A1∧A2∧…∧Ak )→B为重言式。

说明2010-9-25

该定理是判断推理是否正确的另一种方法。8

离散数学PPT课件

推理的形式结构

(1) A1∧A2∧…∧Ak→B (2)前提： A1, A2,…, Ak结论： B

说明

当推理正确时，形式(1)记为A1∧A2∧…∧Ak B。 表示蕴涵式为重言式。9

2010-9-25

离散数学PPT课件

判断推理是否正确的方法真值表法等值演算法主析取范式法

说明

当命题变项较少时,这三种方法比较方便。

思考2010-9-25

是否有其他的证明方法？10

离散数学PPT课件

例题例3.2判断下列推理是否正确。(等值演算法) (1)下午马芳或去看电影或去游泳。她没去看电影，所以，她去游泳了。解：设p:马芳下午去看电影，q:马芳下午去游泳。前提： p∨q,┐p结论： q推理的形式结构： ((p∨q)∧┐p)→q ((p∨q)∧┐p)→q ┐((p∨q)∧┐p)∨ q ((┐p∧┐q)∨p)∨ q ((┐p∨p )∧(┐q∨p))∨ q (┐q∨p)∨ q 12010-9-25 11

由定理 3.1可知，推理正确。

离散数学PPT课件

例题例3.2判断下列推理是否正确。(主析取范式法 ) (2)若今天是1号，则明天是5号。明天是5号，所以今天是1号。解：设p:今天是1号，q:明天是5号。前提：p

→q,q结论： p推理的形式结构： (p→q)∧q→p (p→q)∧q→p (¬p∨q)∧q→p ¬ ((¬p∨q)∧q)∨p ¬q∨p (¬p∧¬q)∨(p∧¬q)∨ (p∧¬q)∨(p∧q)2010-9-25

m0∨m2∨m3

主析取范式不含m1,故不是重言式(01是成假赋值),所以推理不正确。 12

离散数学PPT课件

推理定律--重言蕴含式(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) (A B)∧ (B C) (A C) (8) (A→B)∧(C→D)∧(A∨C) (B∨D)附加律化简律假言推理拒取式析取三段论假言三段论等价三段论构造性二难

2010-9-25

离散数学PPT课件

关于推理定律的几点说明A,B,C为元语言符号，代表任意的命题公式。 2.1节给出的24个等值式中的每一个都派生出两条推理定律。例如双重否定律A ¬¬A产生两条推理定律A ¬¬A和¬¬A A。由八条推理定律可以产生八条推理规则,它们构成了推理系统中的推理规则。

2010-9-25

离散数学PPT课件

3.2构造推理的证明对于由前提A1,A2,…,Ak推B的正确推理应该给出严谨的证明。证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论(中间结论或推理中的结论)。

2010-9-25

离散数学PPT课件

推理规则(1)前提引入规则在证明的任何步骤上都可以引入前提。 (2)结论引入规则在证明的任何步骤上所得到的结论都可以作为后继证明的前提。 (3)置换规则在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。

2010-9-25