离散数学DISCRETE-MATHEMATICS课件

离散数学DISCRETEMATHEMATICSxxx1谢谢观赏2019-8-23重点词--定义极大项\极小项命题公式蕴涵重点掌握主合取范式\主析取范式表达命题公式蕴涵的判别

上次课重点:2谢谢观赏2019-8-23本次课重点命题逻辑的推理3谢谢观赏2019-8-23第六节命题逻辑的推理一、定义1：设A1，A2，，An，B都是

WFF，如果A1A2AnB，就说B是前提A1，A2，，An的有效结

论或逻辑结果。也说由A1，A2，，An

推出了B。4谢谢观赏2019-8-23

定义2：设G是一个WFF的集合，

A1，A2，，An是一个有限的WFF

序列。如果序列中的每个公式Ai要么是G中的一个元素，要么是它前面的若干公式的逻辑结果，就说An是G的逻辑结果，或者说由G可以演绎出An。5谢谢观赏2019-8-23

二、推理的公理集合：前面已介绍的基本蕴含式和由蕴含性质导出的基本结果，都可以作为推理的公理集合。三、推理的规则：

1。P规则引入前提规则6谢谢观赏2019-8-232。T规则变换规则。分两种情形：如果当前结果是由前面公式经过等价变换得到的，就把这个变换规则记为TE。如果是经过蕴含变换得到的，就记为TI。(E=EQUIVALENCYI=IMPLICATION)7谢谢观赏2019-8-233。CP规则结论转作前提规则。适用于结论为条件式时，把条件式前件转变成附加的前提后证明出后件的情况。也就是把

A1，A2，，AnBC

转化成证明A1，A2，，An，BC。8谢谢观赏2019-8-23四、推理方法

1。直接法直接由前提出发利用规则推出结论的过程

2。间接法又分两种方式

1）第一种是反证法，把要证明的结论否定后加入前提，推出矛盾的过程。9谢谢观赏2019-8-232）第二种是采用CP规则进行证明。这种方法常用于结论是条件式的情形，把条件式前件作为附加前提与原有前提一起推出后件即可。不同的证明方法有不同的效率，下面用例子说明。10谢谢观赏2019-8-23

例：证明A（BD），A

C，BCD证明一、采用直接法序号公式采用规则⑴A

CP⑵CATE⑴⑶A（BD）P11谢谢观赏2019-8-23⑷C（BD）TI⑵⑶⑸B（CD）TE⑷⑹BP⑺CDTI⑸⑹证毕。12谢谢观赏2019-8-23证明二、采用CP规则证明A（BD），A

C，BCD序号公式采用规则⑴A

CP⑵CP（附加）⑶ATI⑴⑵⑷A（BD）P13谢谢观赏2019-8-23⑸BDTI⑶⑷⑹BP⑺DTI⑸⑹⑻CDCP⑵⑺证毕。14谢谢观赏2019-8-23证明三、反证法。这时要把结论否定后作为附加前提，与原有前提一起推出矛盾。因为

(CD)CD，可以得到C和D两个附加前提。15谢谢观赏2019-8-23证明

A（BD），A

C，BCD

序号公式采用规则⑴A

CP⑵CP（附加）⑶ATI⑴⑵⑷A（BD）P16谢谢观赏2019-8-23⑸BDTI⑶⑷⑹BP⑺DTI⑸⑹⑻DP(附加)⑼证毕。17谢谢观赏2019-8-23

五、消解法应用于命题逻辑推理消解法是基于反证法的一种机械推理方法。消解是指当子句C1和C2一起恰好含有一对

互反的句节时，消去这对互反句节后，由剩余句节构成新子句的过程。

例如：由子句PQ和QR经消解后得到新子句PR。18谢谢观赏2019-8-23消解法原理P,PQQ更一般性有:PA,PQAQ19谢谢观赏2019-8-23

消解法的应用过程如下：1）把前提中每个公式以及否定后的结论通过化合取范式的办法分解成子句集。

2）如果子句C1和C2恰有一对互反的句节，则由消去这对互反句节后的C1和C2经析取构成新的子句，并加入子句集。3）如果重复2）能导出空子句，则得到证明。20谢谢观赏2019-8-23

例：利用消解法证明

A（BD），A

C，BCD解：首先由上式得到子句集

G={ABD，AC，B，C，D}

消解过程如下：21谢谢观赏2019-8-23

序号子句说明⑴ABD引用子句⑵A

C引用子句⑶CBD由⑴⑵消解⑷B引用子句⑸CD由⑶⑷消解22谢谢观赏2019-8-23⑹C引用子句⑺D由⑸⑹消解⑻D引用子句⑼由⑺⑻消解作业：习题一20（4）（5），21（2），23（3）习题1.71(4)(5)，2(2),4(3)习题1.61(4)(5)，2(2),4(3)23谢谢观赏2019-8-23例1如果今天是星期一，则要进行离散数学或数据结构两门课程中的一门课的考试；如果数据结构课的老师生病，则不考数据结构；今天是星期一，并且数据结构的老师生病。所以今天进行离散数学的考试。解：设P：今天是星期一；

Q：要进行离散数学考试；

R：要进行数据结构考试；

S：数据结构课的老师生病；则P→QR，S→～R，P∧SQ。24谢谢观赏2019-8-23证:⑴P∧SＰ

⑵

SＴI⑴

⑶S→～RＰ⑷～RＴI⑵⑶⑸PＴI⑴I⑹P→QRＰ⑺QRＴI⑸⑹I⑻QＴI⑷⑺25谢谢观赏2019-8-23例2一位计算机工作者协助公安员审查一件谋杀案，他认为下列情况是真的；（1）会计张某或邻居王某谋害了厂长。（2）如果会计张某谋害了厂长，则谋害不能发生在半夜。（3）如果邻居王某的证词是正确的，则谋害发生在半夜。（4）如果邻居王某的证词不正确，则半夜时屋里灯光未灭。（5）半夜时屋里灯光灭了，且会计张某曾贪污过。计算机工作者用他的数理逻辑知识，很快推断出谋害者是谁？请问:谁是谋害者？怎样推理发现他？26谢谢观赏2019-8-23解：设P：会计张某谋害了厂长

Q：邻居王某谋害了厂长

N：谋害发生在半夜。

O：邻居王某的证词是正确的。

R：半夜时屋里灯光灭了。

A：会计张某曾贪污过。上述案情有如下命题公式：（1）P∨Q

（2）P→～N

（3）O→N

（4）～O→～R

（5）R∧A27谢谢观赏2019-8-23问题是需求证：

{P∨Q，P→～N，O→N，～O→～R，R∧A}

？证：①R∧AP②RTI①③～O→～RP④OTI②③⑤O→NP⑥NTI④⑤⑦P→～NP⑧～PTI⑥⑦⑨P∨QP⑩QTI⑧⑨∴{P∨Q，P→～N，O→N，～O→～R，R∧A}Q结论是：邻居王某谋害了厂长。28谢谢观赏2019-8-23实验题1实验项目名称:一个简单的命题公式语法分析器实验原理:利用关于命题公式的构成原理及所学编程语言C,分析一个输入字符串是否是一个合适公式实验要求:每个同学要上交四个文件PF_XXX.exe

可执行程序xxx表示自己的学号Readme.txt

说明如何编译原程序,如何运行程序PF_source_xxx.zip

原文件实验报告程序运行要求PF_XXXYY