2019-12-2
谢谢你的观看
7
3。CP规则 结论转作前提规则。 适用于结论为条件式时，把条件式前件 转变成附加的前提后证明出后件的情况。 也就是把 A1，A2，，An BC 转化成证明A1，A2，，An，B C。
2019-12-2
谢谢你的观看
8
四、推理方法 1。直接法 直接由前提出发利用规则推出
⑹
B
P
⑺ C D
TI ⑸⑹
证毕。
2019-12-2
谢谢你的观看
12
证明二、采用CP规则证 明
A （B D），A C，B C D
序号 公式
采用规则
⑴ A C
P
⑵C
P（附加）
⑶A
TI⑴⑵
⑷ A （B D） P
2019-12-2
谢谢你的观看
13
⑸ BD
⑹
B
⑺
D
⑻ CD
证毕。
TI ⑶ ⑷ P TI ⑸⑹ CP⑵⑺
2019-12-2
谢谢你的观看
14
证明三、反证法。 这时要把结论否定后作为附加前提， 与原有前提一起推出矛盾。因为
( C D )C D， 可以得到C和 D两个附加前提。
2019-12-2
谢谢你的观看
15
证明 A （B D），A C，B C D
22Βιβλιοθήκη ⑹C引用子句⑺
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)
2019-12-2
谢谢你的观看
23
例1
• 如果今天是星期一，则要进行离散数学或数据 结构两门课程中的一门课的考试；如果数据结 构课的老师生病，则不考数据结构；今天是星 期一，并且数据结构的老师生病。所以今天进 行离散数学的考试。
00001 ?
#YY是(永真式/矛盾式/可满足式) #程序运行时间: 开始: 结束 – 要求命题标示符为单字母, - 表示非 | 表示或 & 表示与 即可
2019-12-2
谢谢你的观看
29
者是谁？请问:谁是谋害者？怎样推理发现他？
2019-12-2
谢谢你的观看
26
• 解：设P：会计张某谋害了厂长 Q：邻居王某谋害了厂长 N：谋害发生在半夜。 O：邻居王某的证词是正确的。 R：半夜时屋里灯光灭了。 A：会计张某曾贪污过。
• 上述案情有如下命题公式： （1）P∨Q （2）P→～N （3）O→N （4）～O→～R （5）R∧A
取范式的办法分解成子句集。 2）如果子句 C1和 C2恰有一对互反的句节，则由
消去这对互反句节后的 C1和 C2经析取构成新 的子句，并加入子句集。 3）如果重复2）能导出空子句 ，则得到证明。
2019-12-2
谢谢你的观看
20
例：利用消解法证明
A （B D），A C，B C D 解：首先由上式得到子句集
谢谢你的观看
3
第六节 命题逻辑的推理
一、定义1： 设A1，A2，，An，B都是
WFF，如果A1 A2 An B，
就说B是前提A1，A2，，An的有效结 论或逻辑结果。也说由A1，A2，，An 推出了B。
2019-12-2
谢谢你的观看
4
定义2： 设 G 是一个 WFF的 集合， A1，A2，，An 是一个有限的WFF 序列。如果序列中的每个公式 Ai 要么 是G中的一个元素，要么是它前面的若 干公式的逻辑结果，就说An是G的逻辑 结果，或者说由G可以演绎出An。
序号 公式
采用规则
⑴ AC
P
⑵C
P（附加）
⑶A
TI⑴⑵
⑷ A （B D） P
2019-12-2
谢谢你的观看
16
⑸ BD
⑹
B
⑺
D
⑻ D
⑼

证毕。
TI ⑶ ⑷ P TI ⑸⑹ P(附加)
2019-12-2
谢谢你的观看
17
五、消解法应用于命题逻辑推理
• 消解法是基于反证法的一种机械推理方法。 • 消解是指当子句C1和C2一起恰好含有一对
• 结论是：邻居王某谋害了厂长。
2019-12-2
谢谢你的观看
28
实验题1
• 实验项目名称: 一个简单的命题公式语法分析器
• 实验原理:利用关于命题公式的构成原理及所学编程语言C,分析一个输入字符串是否是 一个合适公式
• 实验要求: 每个同学要上交四个文件
– PF_XXX.exe 可执行程序 xxx 表示自己的学号
互反的句节时，消去这对互反句节后，由剩 余句节构成新子句的过程。 例如：由子句 P Q 和 Q R 经消解后得 到新子句 P R。
2019-12-2
谢谢你的观看
18
消解法原理
P, P Q Q 更一般性有: P A, P Q A Q
2019-12-2
谢谢你的观看
19
消解法的应用过程如下： 1）把前提中每个公式以及否定后的结论通过化合
• 解：设P：今天是星期一；
Q：要进行离散数学考试；
R：要进行数据结构考试；
S：数据结构课的老师生病； 则P→QR，S→～R，P∧SQ。
2019-12-2
谢谢你的观看
24
• 证: ⑴ P∧S ⑵S ⑶ S→～R ⑷ ～R ⑸P ⑹ P→QR ⑺ QR ⑻Q
2019-12-2
谢谢你的观看
Ｐ ＴI⑴ Ｐ ＴI⑵⑶ ＴI⑴I Ｐ ＴI⑸⑹I ＴI⑷⑺
离散数学
DISCRETE MATHEMATICS
教师:
二零一三
2019-12-2
谢谢你的观看
1
上次课重点:
• 重点词 -- 定义
– 极大项\极小项 – 命题公式蕴涵
• 重点掌握
– 主合取范式\主析取范式表达 – 命题公式蕴涵的判别
2019-12-2
谢谢你的观看
2
本次课重点 • 命题逻辑的推理
2019-12-2
– Readme.txt 说明如何编译原程序,如何运行程序
– PF_source_xxx.zip 原文件
– 实验报告
• 程序运行要求
– PF_XXX YY
(YY 表示输入字符串)
– 如果YY 是合适公式, 请根据当前时间生成一个结果文件,文件内容如下
#学号 姓名
P1 P2 P3 P4 P5 YY
00000 ?
结论的过程 2。间接法 又分两种方式
1） 第一种是反证法，把要证明的结论否 定后加入前提，推出矛盾的过程。
2019-12-2
谢谢你的观看
9
2）第二种是采用C P规则进行证明。 这种方法常用于结论是条件式的情形， 把条件式前件作为附加前提与原有前 提一起推出后件即可。
• 不同的证明方法有不同的效率，下面 用例子说明。
2019-12-2
谢谢你的观看
10
例：证明 A （B D），A C，B C D
证明一、采用直接法
序号 公式
采用规则
⑴ A C
P
⑵ CA
TE ⑴
⑶ A （B D） P
2019-12-2
谢谢你的观看
11
⑷ C （B D） TI⑵⑶
⑸ B （C D） TE ⑷
25
例2
• 一位计算机工作者协助公安员审查一件谋杀案，他认 为下列情况是真的；
• （1）会计张某或邻居王某谋害了厂长。 • （2）如果会计张某谋害了厂长，则谋害不能发生在半
夜。 • （3）如果邻居王某的证词是正确的，则谋害发生在半
夜。 • （4）如果邻居王某的证词不正确，则半夜时屋里灯光
未灭。 • （5）半夜时屋里灯光灭了，且会计张某曾贪污过。 • 计算机工作者用他的数理逻辑知识，很快推断出谋害
2019-12-2
谢谢你的观看
5
二、推理的公理集合： 前面已介绍的基本蕴含式和由蕴含 性质导出的基本结果，都可以作为 推理的公理集合。
三、推理的规则： 1。P规则 引入前提规则
2019-12-2
谢谢你的观看
6
2。T 规则 变换规则。分两种情形： • 如果当前结果是由前面公式经过等价变
换得到的，就把这个变换规则记为TE。 • 如果是经过蕴含变换得到的，就记为TI。 • (E = EQUIVALENCY I=IMPLICATION)
2019-12-2
谢谢你的观看
27
• 问题是需求证：
{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
G={A B D，A C，B ，C，D } • 消解过程如下：
2019-12-2
谢谢你的观看
21
序号 子 句
说明
⑴ A B D 引用子句
⑵ A C
引用子句
⑶ C B D 由⑴ ⑵消解
⑷B
引用子句
⑸ CD
由⑶ ⑷消解
2019-12-2
谢谢你的观看