1、离散数学离散数学DISCRETE MATHEMATICSDISCRETE MATHEMATICSxxx1谢谢观赏2019-8-23 重点词重点词 -定义定义 极大项极大项极小项极小项 命题公式蕴涵命题公式蕴涵 重点掌握重点掌握 主合取范式主合取范式主析取范式表达主析取范式表达 命题公式蕴涵的判别命题公式蕴涵的判别 上次课重点上次课重点:2谢谢观赏2019-8-23本次课重点 命题逻辑的推理3谢谢观赏2019-8-23第六节第六节 命题逻辑的推理命题逻辑的推理一、一、定义定义1：设设A1，A2，An，B都是都是 WFF，如果，如果A1 A2 An B，就说就说B是前提是前提A1，A2，An的的有
2、效结有效结 论论或或逻辑结果逻辑结果。也说。也说由由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 二、推理的二、推理的公理集合公理集合：前面已介绍的基本蕴含式和由蕴含前面已介绍的基
3、本蕴含式和由蕴含 性质导出的基本结果，都可以作为性质导出的基本结果，都可以作为 推理的公理集合。推理的公理集合。三、推理的三、推理的规则规则：1。P规则规则 引入前提规则引入前提规则6谢谢观赏2019-8-232。T 规则规则 变换规则。分两种情形：变换规则。分两种情形：如果当前结果是由前面公式经过等价变如果当前结果是由前面公式经过等价变 换得到的，就把这个变换规则记为换得到的，就把这个变换规则记为TE。如果是经过蕴含变换得到的，就记为如果是经过蕴含变换得到的，就记为TI。(E=EQUIVALENCY I=IMPLICATION)7谢谢观赏2019-8-233。CP规则规则 结论转作前提规则。
4、结论转作前提规则。适用于结论为条件式时，把条件式前件适用于结论为条件式时，把条件式前件 转变成附加的前提后证明出后件的情况。转变成附加的前提后证明出后件的情况。也就是把也就是把 A1，A2，An BC 转化成证明转化成证明A1，A2，An，B C。8谢谢观赏2019-8-23 四、推理方法推理方法 1。直接法直接法 直接由前提出发利用规则推出直接由前提出发利用规则推出 结论的过程结论的过程 2。间接法间接法 又分两种方式又分两种方式 1）第一种是第一种是反证法反证法，把要证明的结论否，把要证明的结论否 定后加入前提，推出矛盾的过程。定后加入前提，推出矛盾的过程。9谢谢观赏2019-8-23 2
5、）第二种是采用）第二种是采用C P规则进行证明。规则进行证明。这种方法常用于结论是条件式的情形，这种方法常用于结论是条件式的情形，把条件式前件作为附加前提与原有前把条件式前件作为附加前提与原有前 提一起推出后件即可。提一起推出后件即可。不同的证明方法有不同的效率，下面不同的证明方法有不同的效率，下面 用例子说明。用例子说明。10谢谢观赏2019-8-23 例例：证明：证明 A（B D），），A C，B C D证明一证明一、采用直接法、采用直接法序号序号 公式公式 采用规则采用规则 A C P C A TE A （B D）P11谢谢观赏2019-8-23 C （B D）TI B （C D）TE
6、B P C D TI 证毕。证毕。12谢谢观赏2019-8-23证明二证明二、采用、采用CP规则证规则证明明A （B D），），A C，B C D序号序号 公式公式 采用规则采用规则 A C P C P（附加）（附加）A TI A （B D）P13谢谢观赏2019-8-23 B D TI B P D TI C D CP证毕。证毕。14谢谢观赏2019-8-23证明三证明三、反证法。、反证法。这时要把结论否定后作为附加前提，这时要把结论否定后作为附加前提，与原有前提一起推出矛盾。因为与原有前提一起推出矛盾。因为 (C D)C D，可以得到可以得到C和和 D两个附加前提。两个附加前提。15谢谢观赏
7、2019-8-23证明证明 A（B D），），A C，B C D 序号序号 公式公式 采用规则采用规则 A C P C P（附加）（附加）A TI A （B D）P16谢谢观赏2019-8-23 B D TI B P D TI D P(附加附加)证毕。证毕。17谢谢观赏2019-8-23 五、消解法应用于命题逻辑推理五、消解法应用于命题逻辑推理 消解法是基于反证法的一种机械推理方法。消解法是基于反证法的一种机械推理方法。消解消解是指当子句是指当子句C1和和C2一起一起恰好含有一对恰好含有一对 互反的句节互反的句节时，消去这对互反句节后，由剩时，消去这对互反句节后，由剩 余句节构成新子句的过程。
8、余句节构成新子句的过程。例如例如：由子句：由子句 P Q 和和 Q R 经消解后得经消解后得 到新子句到新子句 P R。18谢谢观赏2019-8-23消解法原理消解法原理P,P Q Q更一般性有更一般性有:P A,P Q A Q19谢谢观赏2019-8-23 消解法的应用过程如下：消解法的应用过程如下：1）把前提中每个公式以及否定后的结论通过化合）把前提中每个公式以及否定后的结论通过化合 取范式的办法分解成子句集。取范式的办法分解成子句集。2）如果子句）如果子句 C1和和 C2恰有一对互反的句节，则由恰有一对互反的句节，则由 消去这对互反句节后的消去这对互反句节后的 C1和和 C2经析取构成新
9、经析取构成新 的子句，并加入子句集。的子句，并加入子句集。3）如果重复）如果重复2）能导出空子句）能导出空子句，则得到证明。，则得到证明。20谢谢观赏2019-8-23 例例：利用消解法证明：利用消解法证明 A （B D），），A C，B C D解解：首先由上式得到子句集：首先由上式得到子句集 G=A B D，A C，B，C，D 消解过程如下：消解过程如下：21谢谢观赏2019-8-23 序号序号 子子 句句 说说 明明 A B D 引用子句引用子句 A C 引用子句引用子句 C B D 由由 消解消解 B 引用子句引用子句 C D 由由 消解消解22谢谢观赏2019-8-23 C 引用子句引
10、用子句 D 由由 消解消解 D 引用子句引用子句 由由 消解消解作业：习题一作业：习题一 20（4）（）（5），），21（2），），23（3）习题习题1.7 1(4)(5)，2(2),4(3)习题习题1.6 1(4)(5)，2(2),4(3)23谢谢观赏2019-8-23例1 如果今天是星期一，则要进行离散数学或数据结构两门课程中的一门课的考试；如果数据结构课的老师生病，则不考数据结构；今天是星期一，并且数据结构的老师生病。所以今天进行离散数学的考试。解：设P：今天是星期一；Q：要进行离散数学考试；R：要进行数据结构考试；S：数据结构课的老师生病；则PQR，SR，PSQ。24谢谢观赏2019-
11、8-23 证:PS S I SR R I P II PQR QR II Q I 25谢谢观赏2019-8-23例2 一位计算机工作者协助公安员审查一件谋杀案，他认为下列情况是真的；（1）会计张某或邻居王某谋害了厂长。（2）如果会计张某谋害了厂长，则谋害不能发生在半夜。（3）如果邻居王某的证词是正确的，则谋害发生在半夜。（4）如果邻居王某的证词不正确，则半夜时屋里灯光未灭。（5）半夜时屋里灯光灭了，且会计张某曾贪污过。计算机工作者用他的数理逻辑知识，很快推断出谋害者是谁？请问:谁是谋害者？怎样推理发现他？26谢谢观赏2019-8-23 解：设P：会计张某谋害了厂长 Q：邻居王某谋害了厂长 N：谋
12、害发生在半夜。O：邻居王某的证词是正确的。R：半夜时屋里灯光灭了。A：会计张某曾贪污过。上述案情有如下命题公式：（1）PQ （2）PN （3）ON （4）OR （5）RA27谢谢观赏2019-8-23 问题是需求证：PQ，PN，ON，OR，RA？证：RA P R TI OR P O TI ON P N TI PN P P TI PQ P Q TI PQ，PN，ON，OR，RA Q 结论是：邻居王某谋害了厂长。28谢谢观赏2019-8-23实验题1实验项目名称:一个简单的命题公式语法分析器实验原理:利用关于命题公式的构成原理及所学编程语言C,分析一个输入字符串是否是一个合适公式实验要求:每个同学要上交四个文件 PF_XXX.exe 可执行程序 xxx 表示自己的学号 Readme.txt 说明如何编译原程序,如何运行程序 PF_source_xxx.zip 原文件 实验报告程序运行要求 PF_XXX YY (YY 表示输入字符串)如果YY 是合适公式,请根据当前时间生成一个结果文件,文件内容如下#学号 姓名P1 P2 P3 P4 P5 YY0 0 0 0 0?0 0 0 0 1?#YY是(永真式/矛盾式/可满足式)#程序运行时间:开始:结束 要求命题标示符为单字母,-表示非|表示或&表示与 即可29谢谢观赏2019-8-23
