离散数学-24命题逻辑推理理论.ppt

《离散数学-24命题逻辑推理理论.ppt》由会员分享，可在线阅读，更多相关《离散数学-24命题逻辑推理理论.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.4 命题逻辑推理理论命题逻辑推理理论2.4.1 推理的形式结构推理的形式结构推理的前提与结论推理的前提与结论,正确推理正确推理推理定律推理定律2.4.2 自然推理系统自然推理系统P推理规则推理规则直接证明法直接证明法,附加前提证明法附加前提证明法,归谬法归谬法(反证法反证法),),归结证明法归结证明法1有效推理有效推理定义定义2.20 若对于每组赋值若对于每组赋值,A1 A2 Ak 为假为假,或者或者当当A1 A2 Ak为真时为真时,B也为真也为真,则称由前提则称由前提A1,A2,Ak推推B的的推理有效推理有效或或推理正确推理正确,并称并称B是是有效的结论有效的结论 由前提由前提A1,A2

2、,Ak 推出推出B 的推理正确当且仅当的推理正确当且仅当 A1 A2 AkB为重言式为重言式.2推理的形式结构推理的形式结构形式形式(1)A1 A2 AkB形式形式(2)前提前提:A1,A2,Ak 结论结论:B 推理正确记作推理正确记作 A1 A2 AkB判断推理是否正确的方法判断推理是否正确的方法:真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法构造证明法构造证明法3实例实例例例1 判断下面推理是否正确判断下面推理是否正确:(1)若若今今天天是是1号号,则则明明天天是是5号号.今今天天是是1号号.所所以以,明明天天是是5号号.解解 设设 p:今天是今天是1号号,q:明天是明天是5

3、号号 推理的形式结构为推理的形式结构为 (pq)pq证明证明 用等值演算法用等值演算法 (pq)pq (p q)p)q (pq)p)q pq q 1得证推理正确得证推理正确4实例实例(续续)(2)若若今今天天是是1号号,则则明明天天是是5号号.明明天天是是5号号.所所以以,今今天天是是1号号.解解 设设p:今天是今天是1号号,q:明天是明天是5号号.推理的形式结构为推理的形式结构为 (pq)qp证明证明 用主析取范式法用主析取范式法 (pq)qp (p q)qp (p q)q)p q p (pq)(pq)(pq)(p q)m0 m2 m3 01是成假赋值是成假赋值,所以推理不正确所以推理不正确

4、.5推理定律推理定律重言蕴涵式重言蕴涵式 A (A B)附加律附加律(A B)A 化简律化简律(AB)A B 假言推理假言推理(AB)B A 拒取式拒取式(A B)B A 析取三段论析取三段论(AB)(BC)(AC)假言三段论假言三段论(AB)(BC)(AC)等价三段论等价三段论(AB)(CD)(A C)(B D)构造性二难构造性二难(AB)(AB)B 构造性二难构造性二难(特殊形式特殊形式)(AB)(CD)(BD)(AC)破坏性二难破坏性二难6自然推理系统自然推理系统P自然推理系统自然推理系统P由下述由下述3部分组成部分组成:1.字母表字母表(1)命题变项符号命题变项符号:p,q,r,pi,

5、qi,ri,(2)联结词联结词:,(3)括号与逗号括号与逗号:(),2.合式公式合式公式3.推理规则推理规则(1)前提引入规则前提引入规则(2)结论引入规则结论引入规则(3)置换规则置换规则7自然推理系统自然推理系统P(续续)(7)拒取式规则拒取式规则 AB B A(8)假言三段论规则假言三段论规则 AB BC AC(4)假言推理规则假言推理规则 AB A B(5)附加规则附加规则 A A B(6)化简规则化简规则 A B A 8自然推理系统自然推理系统P(续续)(11)破坏性二难推理规则破坏性二难推理规则 AB CD BD AC(12)合取引入规则合取引入规则 A B A B(9)析取三段论

6、规则析取三段论规则 A B B A(10)构造性二难推理规则构造性二难推理规则 AB CD A C B D9直接证明法直接证明法例例2 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明:前提前提:p q,qr,ps,s结论结论:r(p q)证明证明 ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 qr 前提引入前提引入 r 假言推理假言推理 r(p q)合取合取推理正确推理正确,r(p q)是有效结论是有效结论10实例实例例例3 构造推理的证明构造推理的证明:若明天是星期一或星期三若明天是星期一或星期三,

7、我就有我就有课课.若若有有课课,今今天天必必需需备备课课.我我今今天天下下午午没没备备课课.所所以以,明明天天不是星期一和星期三不是星期一和星期三.解解 设设 p:明天是星期一明天是星期一,q:明天是星期三，明天是星期三，r:我有课，我有课，s:我备课我备课前提前提:(p q)r,rs,s结论结论:pq 11实例实例(续续)前提前提:(p q)r,rs,s结论结论:pq 证明证明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式(p q)r 前提引入前提引入 (p q)拒取式拒取式 pq 置换置换结论有效结论有效,即明天不是星期一和星期三即明天不是星期一和星期三12附加前提证明法

8、附加前提证明法欲证明欲证明 等价地证明等价地证明前提前提:A1,A2,Ak 前提前提:A1,A2,Ak,C结论结论:CB 结论结论:B理由理由:(A1 A2 Ak)(CB)(A1 A2 Ak)(C B)(A1 A2 Ak C)B (A1 A2 Ak C)B13实例实例例例4 构造下面推理的证明构造下面推理的证明:前提前提:p q,q r,rs结论结论:ps证明证明 p 附加前提引入附加前提引入 p q 前提引入前提引入 q 析取三段论析取三段论 q r 前提引入前提引入 r 析取三段论析取三段论 rs 前提引入前提引入 s 假言推理假言推理推理正确推理正确,ps是有效结论是有效结论14归谬法归

9、谬法(反证法反证法)欲证明欲证明前提：前提：A1,A2,Ak 结论：结论：B将将 B加入前提加入前提,若推出矛盾若推出矛盾,则得证推理正确则得证推理正确.理由理由:A1 A2 AkB (A1 A2 Ak)B (A1 A2 AkB)括号内部为矛盾式当且仅当括号内部为矛盾式当且仅当(A1 A2 AkB)为重言式为重言式15实例实例例例5 构造下面推理的证明构造下面推理的证明前提前提:(p q)r,rs,s,p结论结论:q证明证明 用归缪法用归缪法 q 结论否定引入结论否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式16实例实例(续续)(p q)r 前提引入前提引入 (p q

10、)析取三段论析取三段论 pq 置换置换 p 析取三段论析取三段论 p 前提引入前提引入 p p 合取合取推理正确推理正确,q是有效结论是有效结论17归结证明法归结证明法理由理由 (p q)(p r)(q r)(p q)(p r)(q r)(pq)(pr)q r (pq)q)(pr)r)(p q)(p r)1 1归结规则归结规则 A B A C B C18归结证明法归结证明法(续续)在自然推理系统在自然推理系统P中只需下述推理规则中只需下述推理规则:(1)前提引入规则前提引入规则(2)结论引入规则结论引入规则(3)置换规则置换规则(4)化简规则化简规则(5)合取引入规则合取引入规则(6)归结规则

11、归结规则19归结证明法的基本步骤归结证明法的基本步骤1.将每一个前提化成等值的合取范式将每一个前提化成等值的合取范式,设所有合取范式的设所有合取范式的全部简单析取式为全部简单析取式为A1,A2,At2.将结论化成等值的合取范式将结论化成等值的合取范式B1 B2 Bs,其中每个其中每个Bj是简单析取式是简单析取式3.以以A1,A2,At为前提为前提,使用归结规则推出每一个使用归结规则推出每一个Bj,1 j s4.由合取引入规则得到结论由合取引入规则得到结论B1 B2 Bs20实例实例例例6 用归结证明法构造下面推理的证明用归结证明法构造下面推理的证明:前提前提:(pq)r,rs,s结论结论:(p

12、q)()(p s)解解 (pq)r (p q)r (pq)r (p r)(q r)rs r s (pq)()(p s)()(p q)()(p s)()(pq)(p s)p(q s)推理可表成推理可表成前提前提:p r,q r,r s,s结论结论:p(q s)21实例实例(续续)前提前提:p r,q r,r s,s结论结论:p(q s)证明证明 q r 前提引入前提引入 r s 前提引入前提引入 q s 归结归结 s 前提引入前提引入 s0 0 置换置换 r00 归结归结 p r 前提引入前提引入 p00 归结归结 p 置换置换 p(q s)合取引入合取引入22实例：公安破案实例：公安破案一个公安人员审查一件盗窃案，已知的事实如下：A或B盗窃了钻石；若A盗窃了钻石，则作案时间不能发生在午夜前；若B证词正确，则在午夜时屋里灯光未灭；若B证词不正确，则作案时间发生在午夜前；午夜时屋里灯光灭了。谁盗窃了钻石呢？23