命题逻辑推理理论-离散数学.ppt
1,2.4 命题逻辑推理理论,2.4.1 推理的形式结构推理及其形式结构推理定律2.4.2 自然推理系统P自然推理系统的定义证明方法,2,2.4.1 推理的形式结构,一、什么是推理,定义2.19 设A1，A2，Ak，B都是命题公式，若对于每组赋值,A1A2 Ak为假,或者当A1 A2 Ak为真时，B也为真,则称由前提A1，A2，,Ak推B的推理有效或推理正确,并称B是有效的结论。,3,定理2.8 由前提A1,A2,Ak 推出B 的推理正确当且仅当 A1 A2 Ak B为重言式.,如果把（A1 A2 Ak）B为永真式记为：,上式的含义？,4,二、推理的形式结构,定义2.20 称（A1 A2 Ak）B为由前提 A1,A2,Ak推结论 B 的推理的形式结构。,推理的形式结构一般有以下三种：形式(1)A1 A2 Ak B 形式(2)前提:A1,A2,Ak 结论:B 形式(3)A1，A2，Ak B,5,真值表法等值演算法主析取范式法构造证明法,判断推理是否正确的方法:,真值表的方法参见P.67例2.23。,6,例1 判断下面推理是否正确:(1)若今天是1号,则明天是5号.今天是1号.所以,明天是5号.,7,例1(2)若今天是1号,则明天是5号.明天是5号.所以,今天是1号。,解 设 p:今天是1号,q:明天是5号 推理的形式结构为证明 用主析取范式法,这不是一个永真式，01是该公式成假的赋值，所以推理不正确。,8,三、推理定律重言蕴涵式,A(AB)附加律(AB)A 化简律(AB)A B 假言推理(AB)B A 拒取式(AB)B A 析取三段论(AB)(BC)(AC)假言三段论(AB)(BC)(AC)等价三段论(AB)(CD)(AC)(BD)构造性二难(AB)(AB)B 构造性二难(特殊形式)(AB)(CD)(BD)(AC)破坏性二难,9,注意：,（1）推理规则中出现的A、B、C 等是元语言符号；（2）直接引用而不需证明，只要说明所引用规则的名称；（3）24个永真公式每个都可以等效为2个推理规则。,10,2.4.2 自然推理系统P,自然推理系统P由下述3部分组成:1.字母表(1)命题变项符号:p,q,r,pi,qi,ri,(2)联结词:,(3)括号与逗号:(),2.合式公式3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则,11,自然推理系统P(续),12,自然推理系统P(续),13,直接证明法,例2 在自然推理系统P中构造下面推理的证明:前提:pq,qr,ps,s结论:r(pq)证明 ps 前提引入 s 前提引入 p 拒取式 pq 前提引入 q 析取三段论 qr 前提引入 r 假言推理 r(pq)合取推理正确,r(pq)是有效结论,14,实例,例3 构造推理的证明:若明天是星期一或星期三,我就有课.若有课,今天必需备课.我今天下午没备课.所以,明天不是星期一和星期三.解 设 p:明天是星期一,q:明天是星期三，r:我有课，s:我备课前提:(pq)r,rs,s结论:pq,15,实例(续),前提:(pq)r,rs,s结论:pq 证明 rs 前提引入 s 前提引入 r 拒取式(pq)r 前提引入(pq)拒取式 pq 置换结论有效,即明天不是星期一和星期三,16,附加前提证明法,欲证明 等价地证明前提:A1,A2,Ak 前提:A1,A2,Ak,C结论:CB 结论:B,理由:(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B(A1A2AkC)B,17,实例,例4 构造下面推理的证明:前提:pq,qr,rs结论:ps证明 p 附加前提引入 pq 前提引入 q 析取三段论 qr 前提引入 r 析取三段论 rs 前提引入 s 假言推理推理正确,ps是有效结论,18,归谬法(反证法),欲证明前提：A1,A2,Ak 结论：B将B加入前提,若推出矛盾,则得证推理正确.,理由:A1A2AkB(A1A2Ak)B(A1A2AkB)括号内部为矛盾式当且仅当(A1A2AkB)为重言式,19,实例,例5 构造下面推理的证明前提:(pq)r,rs,s,p结论:q证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式,20,实例(续),(pq)r 前提引入(pq)析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取推理正确,q是有效结论,21,课堂练习1,1、证明,2、证明,22,证,证明,前提附加前提、，假言推理前提、，拒取式、，析取三段论前提、，拒取式、，CP,23,证,证明,24,应用实例1 分析下列事实“如果我有很高的收入，那么我就能资助许多贫困学生；如果我能资助许多贫困学生，那么我很高兴；但我不高兴，所以我没有很高的收入。”试指明前提和结论，并给予证明。,课堂练习2,25,应用实例2 将下列条件作为前提，验证所得结论是否有效：明天或是天晴，或是下雨；如果是天晴，我去公园；如果我去公园，我就不看书。结论：如果我在看书，则天下雨。,26,本节习题,P.83:2.33（1）、（3）2.35 2.36（1）,
