- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
(2) P 1 (P2 P 1) (3) (P 1 P2) (P 1 P 1)
L1 MP规L2则
L1 (1)、(2)，MP L1 (3)、(4)，MP
38
例10 证明 ├L AA
[证] (1) (A((AA)A))((A(AA))(AA))
(2) A((AA)A) (3) (A(AA))(AA) (4) A(AA) (5) AA
• 课堂实训
应用实例1 分析下列事实“如果我有很高的收 入，那么我就能资助许多贫困学生；如果我能资 助许多贫困学生，那么我很高兴；但我不高兴， 所以我没有很高的收入。”试指明前提和结论， 并给予证明。
33
应用实例2 将下列条件作为前提，验证所得结论是 否有效：
(a) 明天或是天晴，或是下雨； (b) 如果是天晴，我去公园； (c) 如果我去公园，我就不看书。 结论：如果我在看书，则天下雨。
39
3、演绎定理
例11 证明 A ,B (A C )├L (BC)
[证] (1) B (A C)
假设
(2) (B (A C)) ((B A) (B C)) L2
(3) (B A) (B C)
(1)、(2)，MP
(4) A (B A) (5) A (6) (B A) (7) (B C)
30
例8 构造下面推理的证明
前提: (pq)r, rs, s, p ；结论: q
证明：用归缪法
①q
结论否定引入
② rs
前提引入
③ s
前提引入
④ r
②③拒取式
⑤ (pq)r
前提引入
⑥ (pq)
④⑤析取三段论
⑦ pq
⑥置换
⑧ p
①⑦析取三段论
31
⑨p
前提引入
⑩ pp
⑧⑨合取
推理正确, q是有效结论
32
36
3、公理集：
(L1) (A (BA)) (L2) ((A (B C)) ((A B) (A C)) (L3) (((A) (B)) (BA)
4、推理规则：假言推理规则（MP规则）。
37
例9 证明
├L (P 1 P 2) (P 1 P 1)
L2
L1
[证] (1) (P 1 (P2 P 1)) (P (1 P2) (P 1 P 1()1))、L2(2)，MP
34
三、公理系统
1、公理系统的组成
（1）初始符号：它们是不经定义而直接使用的符号； （2）形成规则：确定定义在初始符号上的哪些符号串 是合式公式； （3）公理集：它们是不经证明而直接认为是恒真的命 题； （4）推理规则：规定如何从公理和前面已推导出的合 式公式经过符号变形而推出其它公式。
35
2、公理系统L
理由: A1A2…AkB (A1A2…Ak)B (A1A2…AkB)
括号内部为矛盾式当且仅当 (A1A2…AkB)为重言式
21
例3 证明 P Q R ,Q P ,S R P S
[证] ① P Q R 前提
②P
附加前提
③Q R
①、②，假言推理
④Q P
前提
⑤Q
②、④，拒取式
11
2.4.2 自然推理系统P
一、自然推理系统P的定义
自然推理系统P由下述3部分组成: 1. 字母表
(1) 命题变项符号: p,q,r,…, pi,qi,ri,… (2) 联结词: , , , , (3) 括号与逗号: ( ), , 2. 合式公式
12
一、自然推理系统P的定义（续）
3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 (5) 附加规则 (6) 化简规则
pqr
26
前提: (pq)r, rs, s
结论: pq
证明：
① rs
前提引入
② s
前提引入
③ r
①②拒取式
④ (pq)r
前提引入
⑤ (pq)
③④拒取式
⑥ pq
⑤置换
结论有效, 即明天不是星期一和星期三.
27
附加前提证明法举例
欲证明
前提: A1, A2, …, Ak 结论: CB
等价地证明
前提: A1, A2, …, Ak, C 结论: B
推理的形式结构一般有以下三种： 形式(1) A1 A2 … Ak B 形式(2) 前提: A1, A2, … , Ak 结论: B 形式(3) A1， A2 ， … ， Ak B
4
判断推理是否正确的方法:
真值表法 等值演算法 主析取范式法 构造证明法 真值表的方法参见P.67例2.23。
(7) 拒取式规则 (8) 假言三段论规则 (9) 析取三段论规则 (10)构造性二难推理
规则 (11) 破坏性二难推理
规则 (12) 合取引入规则
13
例2 证明 (p q ) (q r ) r p
[证] ① p q ② q r ③ p r ④r ⑤ p
前提 前提 ①、②，假言三段 前提 ③、④，拒取式
14
二、证明方法
用推理的概念说明一些证明方法的正确性。
（1）前件假证明法
为了证明 AB，只需证明 A 永假即可。
（2）后件真证明法
为了证明 AB，只需证明 B 永真即可。
15
（3）直接证明法
为了证明 AB，只需证明若 A 为真，则 B 亦为真。
（4）间接证明法
为了证明 AB，只需证明若 B 为假，则 A 亦为假。
则，称之为不相容的。
19
（7）反证法（归谬法）
为了证明 A 1 A 2 A n B 只需证明 {A 1,A 2, ,A n, B }是不相容的 即证明 A 1 A 2 A n B 是永假式
20
归谬法(反证法)的说明
欲证明
前提：A1, A2, … , Ak 结论：B 将B加入前提, 若推出矛盾, 则得证推理正确.
⑨ 是一个永假式，因此，原推理正确。
23
直接证明法举例
例5 在自然推理系统P中构造下面推理的证明:
前提: pq,qr, ps,s 结论: r(pq)
证明： ( 1 ) p s 前提
(2 ) s
前提
(3 ) p
(1)、(2)拒取式
( 4 ) p q 前提
(5 )q
(3)、(4)析取三段论
24
(6)q r (7 )r (8)r ( p q )
L1 假设 (4)、(5)，MP (3)、(6)，MP
40
L的演绎定理：若A├L B，则 ├L AB。
推论：设A，B和C是L的任意合式公式，则
A B ,B C ├L AC 。
例12 证明 ├L B (B A)
[证] (1) B(AB)
L1
(2) (AB)(BA) L3
(3) B(BA)
(1)、(2)，HS
2.4 命题逻辑推理理论
• 2.4.1 推理的形式结构
– 推理及其形式结构 – 推理定律
• 2.4.2 自然推理系统P
– 自然推理系统的定义 – 证明方法
1
2.4.1 推理的形式结构
一、什么是推理
定义2.19 设A1，A2 ， … ，Ak ，B都是命题公式，若对于 每组赋值, A1A2 … Ak为假, 或者当A1 A2 … Ak 为真时，B也为真, 则称由前提A1，A2，…, Ak推B的推 理有效或推理正确, 并称B是有效的结论。
43
28
例7 构造下面推理的证明: 前提: pq, qr, rs 结论: ps
证明： ① p
附加前提引入
② pq
前提引入
③q
①②析取三段论
④ qr
前提引入
⑤r
③④析取三段论
⑥ rs
前提引入
⑦s
⑤⑥假言推理
推理正确, ps是有效结论
29
归谬法(反证法)举例
欲证明
前提：A1, A2, … , Ak 结论：B 将B加入前提, 若推出矛盾, 则得证推理正确.
等价地证明
前提: A1, A2, …, Ak, C 结论: B
理由: (A1A2…Ak)(CB) ( A1A2…Ak)(CB) ( A1A2…AkC)B (A1A2…AkC)B
18
不相容的概念：
定义—— 若 A 1A 2A n是可满足式，则称公
式集 A 1,A 2, ,A n是相容的（或一致的），否
公理系统L的定义：
1、初始符号： p1 , p 2 , L , pi , L , ()
2、形成规则：
(1)p （ i 1in)是 合 式 公 式 ; (2)若 A是 合 式 公 式 ,则 (A)是 合 式 公 式 ; (3)若 A和 B是 合 式 公 式 ,则 (A B)是 合 式 公 式 ; (4)只 有 通 过 有 限 次 使 用 (1):(3)得 到 的 符 号 串 才 是 合 式 公 式 。
A, A B B
A B, B A
9
2、常见的推理规则（续）
5）析取三段论 A B, B A
6）假言三段论 AB,BC
AC
7）合取引入
A, B
AB
8）构造性二难 AB,CD,AC
BD
10
• 注意：
（1）推理规则中出现的A、B、C 等是元语言符号； （2）直接引用而不需证明，只要说明所引用规则的名称； （3）24个永真公式每个都可以等效为2个推理规则。
6
例1 (2) 若今天是1号, 则明天是5号. 明天是5号. 所以, 今天是1号。
解 设 p: 今天是1号, q: 明天是5号
推理的形式结构为 (p q)q p
证明 用主析取范式法 (pq)qp((pq)q)p
