命题逻辑的推理理论,证明方法.pptx

. 武汉大学国际软件学院唐存琛刘峰
1
命题逻辑推理理论
推理的形式结构
推理及其形式结构
推理定律
自然推理系统P
自然推理系统的定义
证明方法
. 武汉大学国际软件学院唐存琛刘峰
2
推理的形式结构
一、什么是推理
设A1,A2 , …,Ak ,B都是命题公式,若对于每组赋值, A1A2 …Ak为假, 或者当A1  A2 … Ak为真时,B也为真, 则称由前提A1,A2,…, Ak推B的推理有效或推理正确, 并称B是有效的结论。
. 武汉大学国际软件学院唐存琛刘峰
3
由前提A1, A2, …, Ak 推出B 的推理正确当且仅当
A1  A2 … Ak  B为重言式.
如果把(A1  A2 … Ak ) B为永真式记为:
上式的含义???
. 武汉大学国际软件学院唐存琛刘峰
4
二、推理的形式结构
称(A1  A2 … Ak ) B为由前提 A1, A2, …, Ak推结论 B 的推理的形式结构。
推理的形式结构一般有以下三种:
形式(1) A1  A2 … Ak  B
形式(2) 前提: A1, A2, …, Ak
结论: B
形式(3) A1, A2 , …, Ak  B
. 武汉大学国际软件学院唐存琛刘峰
5
真值表法
等值演算法
主析取范式法
构造证明法
判断推理是否正确的方法:
。
. 武汉大学国际软件学院唐存琛刘峰
6
例1 判断下面推理是否正确:
(1) 若今天是1号, 则明天是5号. 今天是1号. 所以, 明天是5号.
解设 p: 今天是1号, q: 明天是5号
推理的形式结构为
证明用等值演算法
所以,原推理正确。
. 武汉大学国际软件学院唐存琛刘峰
7
例1 (2) 若今天是1号, 则明天是5号. 明天是5号. 所以, 今天是1号。
解设 p: 今天是1号, q: 明天是5号
推理的形式结构为
证明用主析取范式法
这不是一个永真式,01是该公式成假的赋值,所以推理不正确。
. 武汉大学国际软件学院唐存琛刘峰
8
三、推理规则
1、推理规则的定义
是一个推理规则,当且仅当
,其中, A1, A2, …, An 称为推理规则的前提,B 称为推理规则的结论。
. 武汉大学国际软件学院唐存琛刘峰
9
1)附加规则
2)化简规则
3)MP规则
(假言推理)
4)拒取式
2、常用的推理规则
. 武汉大学国际软件学院唐存琛刘峰
10
5)析取三段论
6)假言三段论
7)合取引入
8)构造性二难
2、常见的推理规则(续)