命题逻辑的推理理论共48页文档

31
⑨p
前提引入
⑩ pp
⑧⑨合取
推理正确, q是有效结论
.
武汉大学国际软件学院
唐存琛 刘峰
32
课堂实训
应用实例1 分析下列事实“如果我有很高的收 入，那么我就能资助许多贫困学生；如果我能资 助许多贫困学生，那么我很高兴；但我不高兴， 所以我没有很高的收入。”试指明前提和结论， 并给予证明。
.
武汉大学国际软件学院
.
武汉大学国际软件学院
唐存琛 刘峰
20
归谬法(反证法)的说明
欲证明
前提：A1, A2, … , Ak 结论：B
将B加入前提, 若推出矛盾, 则得证推理正确.
理由: A1A2…AkB (A1A2…Ak)B (A1A2…AkB)
括号内部为矛盾式当且仅当 (A1A2…AkB)为重言式
.
武汉大学国际软件学院
12
一、自然推理系统P的定义（续）
3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 (5) 附加规则 (6) 化简规则
(7) 拒取式规则 (8) 假言三段论规则 (9) 析取三段论规则 (10)构造性二难推理
规则 (11) 破坏性二难推理
规则 (12) 合取引入规则
.
武汉大学国际软件学院
唐存琛 刘峰
16
（5）分情况证明法
为了证明 A1 A2 An B , 只需证明对任意的 i (1 i n) ，均有 Ai B 。
（6）附加前提证明法
为了证明 A1 A2 An A B ,
只需证明 A1 A2 An A B
.
武汉大学国际软件学院
武汉大学国际软件学院唐存琛 刘峰

第三章:命题逻辑的推理理论
第一节：推理的形式结构 第二节：自然推理系统P
1
第三章:命题逻辑的推理理论
主要内容 推理的形式结构 推理的正确与错误 推理的形式结构 判断推理正确的方法 推理定律
自然推理系统P 形式系统的定义与分类 自然推理系统P 在P中构造证明:直接证明法、附加前提证明法、归谬法
AB CD B D 结论：A C
24
3.2 自然推理系统P
形式推演(语法蕴涵)：给定A1,…,Ak和B
❖ 符号：{A1,…,Ak} ⊢ B ❖ 存在公式序列C1, C2,…,Cn，对每个
i(i=1,…,n),
• Ci是某个Aj或者 • Ci是有序列中前面的公式应用推理规则得到 • Cn=B
❖ 称C1,…,Cn是有A1,…,Ak推B的证明
9
9
3.1 推理形式结构
推理定律
A (A B) (A B) A (A B) A B (A B) B A (A B) B A (A B) (B C) (A C) (A B) (B C) (A C) (A B) (C D) (A C) (B D) (A B) ( A B) B (A B) (C D) ( B D) ( A C)
17
3.2 自然推理系统P
假言推理规则 (A B) A B
A B A
结论：B
All men are mortal Socrates is a man Therefore Socrates is mortal
18
3.2 自然推理系统P
附加规则 A (A B) A
结论：A B
19
3.2 自然推理系统P
❖ 结论： p
解：
①rΒιβλιοθήκη 前提引入② r q

构造下面推理的证明： 若明天是星期一或星期三，我就有课. 若有课， 今天必备课. 我今天下午没备课. 所以， 明天不是星期一和星期三. 解 设 p：明天是星期一，q：明天是星期三， r：我有课，s：我备课 推理的形式结构为 前提：(pq)r, rs, s 结论：pq
c为元语言符号若某推理符合某条推理定律则它自然是正确的ab产生两条推理定律
1.6 命题逻辑的推理理论
推理的形式结构 判断推理是否正确的方法 推理定律与推理规则
构造证明法
1
推理的形式结构—问题的引入
推理举例: (1) 正项级数收敛当且仅当部分和有上界. (2) 若ACBD，则AB且CD. 推理: 从前提出发推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理. 证明: 描述推理正确的过程.
2
推理的形式结构
定义 若对于每组赋值，或者A1A2… Ak 均为假， 或者当A1A2…Ak为真时, B也为真, 则称由A1, A2, …, Ak推B的推理正确, 否则推理不正确（错误）. “A1, A2, …, Ak 推B” 的推理正确 当且仅当 A1A2…AkB为重言式. 推理的形式结构: A1A2…AkB 或 前提： A1, A2, … , Ak 结论： B 若推理正确，则记作：A1A2…AkB.
18
(6) 化简规则 AB \A (7) 拒取式规则 AB B \A (8) 假言三段论规则 AB BC \AC
9
推理规则(续)
(9) 析取三段论规则 AB B \A (10)构造性二难推理 规则 AB CD AC \BD (11) 破坏性二难推理 规则 AB CD BD \AC (12) 合取引入规则 A B \AB
5
实例 (续)
(2) 若今天是1号，则明天是5号. 明天是5号. 所以今天是1号. 解 设p：今天是1号，q：明天是5号. 推理的形式结构为: (pq)qp 证明（用主析取范式法） (pq)qp (pq)qp ((pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确.

第三章 命题逻辑的推理理论§1 推理的形式结构推理：从前提出发推出结论的思维过程。

前提：已知命题公式集合。

结论：从前提出发应用推理规则推出的命题公式。

定义设A1, A2, …, A k, B都是命题公式，若命题公式A1∧A2∧…∧A k→B是重言式，则称由前提A1, A2, …, A k推出结论B的推理是有效的或正确的，并称B是有效的结论。

推理的形式结构记为{A1,A2,…,A k}A B推理正确，记为{ A1,A2,…,A k }⊨B推理无效，记为{ A1,A2,…,A k }⊭B注①推理正确，结论未必为真。

②推理只注重结构。

例判断下述推理的正确性。

(1) {p, p→q}⊢ q(2) {p, q→p}⊢ q解 (1) p∧(p→q)→q⇔p∧(¬p∨q)→q⇔(p∧¬p)∨(p∧q)→q⇔p∧q→q⇔¬ (p∧q)∨q⇔¬p∨(¬q∨q)⇔¬p∨1⇔1故{p, p→q }⊨ q(2) p∧(q→p)→q让q =0，可得q→p =1，再取p =1可得p∧(q→p)=1 由此得p∧(q→p)→q有成假赋值1 0，故{ p, q→p }⊭ q判断推理正确性：1．真值表法。

2．等值演算法。

3．主析取范式法。

4．构造证明。

例判断下述推理是否正确？（1）若a能被4整除，则a能被2整除。

a能被4整除。

所以a能被2整除。

（2）若下午气温超过30℃，则王小燕必去游泳。

若她去游泳，则她就不去看电影了。

所以，若王小燕没去看电影，则下午气温必超过了30℃。

解(1) p：a能被4整除q：a能被2整除前提：p→q，p结论：q推理的形式结构：{p→q，p} A q前面已证此推理正确。

(2) p：下午气温超过30℃q：王小燕去游泳r：王小燕去看电影前提：p→q, q→¬r结论：¬ r→p推理的形式结构：{p→q，q→¬r} A(¬r→p)因为，(p→q)∧(q→¬ r)→(¬r→p)⇔m1∨m3∨m4∨m5∨m6∨m7主析取范式显然不是重言式，故推理不正确。