离散数学 DISCRETE MATHEMATICS

Presentation on theme: "离散数学 DISCRETE MATHEMATICS"— Presentation transcript:

1 离散数学 DISCRETE MATHEMATICS
教师:石兵 二零一三

2 上次课重点: 重点词 -- 定义 极大项\极小项 命题公式蕴涵 重点掌握 主合取范式\主析取范式表达 命题公式蕴涵的判别

3 本次课重点 命题逻辑的推理

4 第六节 命题逻辑的推理 一、定义1： 设A1，A2，，An，B都是 WFF，如果A1  A2    An  B，
第六节 命题逻辑的推理 一、定义1： 设A1，A2，，An，B都是 WFF，如果A1  A2    An  B， 就说B是前提A1，A2，，An的有效结 论或逻辑结果。也说由A1，A2，，An 推出了B。

5 定义2： 设 G 是一个 WFF的 集合， A1，A2，，An 是一个有限的WFF 序列。如果序列中的每个公式 Ai 要么 是G中的一个元素，要么是它前面的若 干公式的逻辑结果，就说An是G的逻辑 结果，或者说由G可以演绎出An。

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

7 2。T 规则 变换规则。分两种情形： 如果当前结果是由前面公式经过等价变 换得到的，就把这个变换规则记为TE。 如果是经过蕴含变换得到的，就记为TI。 (E = EQUIVALENCY I=IMPLICATION)

8 3。CP规则 结论转作前提规则。 适用于结论为条件式时，把条件式前件 转变成附加的前提后证明出后件的情况。 也就是把 A1，A2，，An  BC 转化成证明A1，A2，，An，B C。

9 四、推理方法 1。直接法 直接由前提出发利用规则推出 结论的过程 2。间接法 又分两种方式 1） 第一种是反证法，把要证明的结论否 定后加入前提，推出矛盾的过程。

10 2）第二种是采用C P规则进行证明。 这种方法常用于结论是条件式的情形， 把条件式前件作为附加前提与原有前 提一起推出后件即可。 不同的证明方法有不同的效率，下面 用例子说明。

11 例：证明 A （B D），A  C，B C  D
证明一、采用直接法 序号 公式 采用规则 ⑴ A  C P ⑵ C  A TE ⑴ ⑶ A  （B D） P

12 ⑷ C  （B D） TI⑵⑶ ⑸ B  （C D） TE ⑷ ⑹ B P ⑺ C D TI ⑸⑹ 证毕。

13 A  （B D），A  C，B C  D 序号 公式 采用规则 ⑴ A  C P ⑵ C P（附加） ⑶ A TI⑴⑵
序号 公式 采用规则 ⑴ A  C P ⑵ C P（附加） ⑶ A TI⑴⑵ ⑷ A  （B D） P

14 ⑸ B  D TI ⑶ ⑷ ⑹ B P ⑺ D TI ⑸⑹ ⑻ C  D CP⑵⑺ 证毕。

15 证明三、反证法。 这时要把结论否定后作为附加前提， 与原有前提一起推出矛盾。因为 ( C D )C   D， 可以得到C和  D两个附加前提。

16 证明 A （B D），A  C，B C  D
序号 公式 采用规则 ⑴ A   C P ⑵ C P（附加） ⑶ A TI⑴⑵ ⑷ A  （B D） P

17 ⑸ B  D TI ⑶ ⑷ ⑹ B P ⑺ D TI ⑸⑹ ⑻ D P(附加) ⑼  证毕。

18 五、消解法应用于命题逻辑推理 消解法是基于反证法的一种机械推理方法。 消解是指当子句C1和C2一起恰好含有一对 互反的句节时，消去这对互反句节后，由剩 余句节构成新子句的过程。 例如：由子句 P Q 和 Q R 经消解后得 到新子句 P R。

19 消解法原理 P, P  Q  Q 更一般性有: P A, P Q A  Q

20 消解法的应用过程如下： 1）把前提中每个公式以及否定后的结论通过化合 取范式的办法分解成子句集。 2）如果子句 C1和 C2恰有一对互反的句节，则由 消去这对互反句节后的 C1和 C2经析取构成新 的子句，并加入子句集。 3）如果重复2）能导出空子句 ，则得到证明。

21 例：利用消解法证明 A  （B D），A  C，B C  D 解：首先由上式得到子句集 G={A B  D，A C，B ，C，D } 消解过程如下：

22 序号 子 句 说 明 ⑴  A   B D 引用子句 ⑵ A  C 引用子句 ⑶  C   B D 由⑴ ⑵消解 ⑷ B 引用子句 ⑸  C  D 由⑶ ⑷消解

23 ⑹ C 引用子句 ⑺ D 由⑸ ⑹消解 ⑻  D 引用子句 ⑼  由⑺ ⑻消解 作业：习题一 20（4）（5），21（2），23（3） 习题 (4)(5)，2(2), 4(3) 习题 (4)(5)，2(2), 4(3)

24 例1 如果今天是星期一，则要进行离散数学或数据结构两门课程中的一门课的考试；如果数据结构课的老师生病，则不考数据结构；今天是星期一，并且数据结构的老师生病。所以今天进行离散数学的考试。 解：设P：今天是星期一； Q：要进行离散数学考试； R：要进行数据结构考试； S：数据结构课的老师生病； 则P→QR，S→～R，P∧SQ。

25 证: ⑴ P∧S Ｐ ⑵ S ＴI⑴ ⑶ S→～R Ｐ ⑷ ～R ＴI⑵⑶ ⑸ P ＴI⑴I ⑹ P→QR Ｐ ⑺ QR ＴI⑸⑹I ⑻ Q ＴI⑷⑺

26 例2 一位计算机工作者协助公安员审查一件谋杀案，他认为下列情况是真的； （1）会计张某或邻居王某谋害了厂长。
（2）如果会计张某谋害了厂长，则谋害不能发生在半夜。 （3）如果邻居王某的证词是正确的，则谋害发生在半夜。 （4）如果邻居王某的证词不正确，则半夜时屋里灯光未灭。 （5）半夜时屋里灯光灭了，且会计张某曾贪污过。 计算机工作者用他的数理逻辑知识，很快推断出谋害者是谁？请问:谁是谋害者？怎样推理发现他？

27 解：设P：会计张某谋害了厂长 Q：邻居王某谋害了厂长 N：谋害发生在半夜。 O：邻居王某的证词是正确的。 R：半夜时屋里灯光灭了。 A：会计张某曾贪污过。 上述案情有如下命题公式： （1）P∨Q （2）P→～N （3）O→N （4）～O→～R （5）R∧A

28 问题是需求证： {P∨Q，P→～N，O→N，～O→～R，R∧A}  ？ 证：① R∧A P ② R TI① ③ ～O→～R P ④ O TI②③ ⑤ O→N P ⑥ N TI④⑤ ⑦ P→～N P ⑧ ～P TI⑥⑦ ⑨ P∨Q P ⑩ Q TI⑧⑨ ∴ {P∨Q，P→～N，O→N，～O→～R，R∧A}  Q 结论是：邻居王某谋害了厂长。

29 实验题1 实验项目名称: 一个简单的命题公式语法分析器
实验原理:利用关于命题公式的构成原理及所学编程语言C,分析一个输入字符串是否是一个合适公式 实验要求: 每个同学要上交四个文件 PF_XXX.exe 可执行程序 xxx 表示自己的学号 Readme.txt 说明如何编译原程序,如何运行程序 PF_source_xxx.zip 原文件 实验报告 程序运行要求 PF_XXX YY (YY 表示输入字符串) 如果YY 是合适公式, 请根据当前时间生成一个结果文件,文件内容如下 #学号 姓名 P1 P2 P3 P4 P5 YY ? ? #YY是(永真式/矛盾式/可满足式) #程序运行时间: 开始: 结束 要求命题标示符为单字母, - 表示非 | 表示或 & 表示与 即可