离散第三章命题逻辑推理理论

第三题理工大学计算机学1主要内推理定自然推理系统自然推理系统2定义3.1设A1,A2,…,Ak,B为命题公式.若对于每组赋值，A1A2…Ak为假，或当提A1A2Ak推出结论B的推理是有效的或正确的,并称B是有效结论.推理的形式结构{A1,A2,…,Ak}若推理正确,记为 否则记为 3实{q,p→q}方法1：假定q(pq为1,则q为1,且(pq)为1。由于q为 (p→q)为1，则必须p为p为1方法2：假定p0,p为q为0,p→q0,q(p→qq为1,q0,q(pq为{q,p→q 4实{p→q,q}pp0011q0101(p→q)q1111{q,p→q 5推理的形式定理3.1由命题公式A1A2Ak推B的推理推理的形式结构若推理正确记为A1A2Ak前提A1A2结论6判断推理是否正确真值表等值演算7真值表A1,A2,…,Ak真值均1的行，对每一个这样的行B1,A1A2…AkB成立。或者B为0的行,在每个这样的行中A2Ak真值中至少有一个0，A1A2…AkB成立。8推理实B是否是下列前A1A2的有效结论A1:p A2: B A1:p A2: B A1:p A2: B p

0 0 9推理实例1若今天是1号，则明天是5号今天是1号所以,明天是5号.若今天是1号，则明天是5号明天是5号所以,今天是1号.推理实(1)若今天是1号，则明天是5号今天是1号.所以,明天是5号.解p：今天是1号，q：明天是5号(1)推理的形式结构:(pq)pq((pq)p)qp由定理3.1可知推理正推理实(2)若今天是1号，则明天是5号明天是5号所以,(pq)(pq)结果不含m1,故01是成假赋值，所以推理不正推理定律——A 附加(AB 化简(AB)A 假言推(AB)B 拒取(AB)B 析(AB)(BC 假(AB)(BC 等推理定律——(AB)(CD)(AC(BD)构造性二(AB)(AB)构造性二难(特殊形式 (AB)(CD)(BD)破坏性二10.每个等值式可产生两个推理定律实A 附加(AB 化简(AB)B 析实推理错若今天下雨，则我们今天将不野餐。若我们今天不野餐，则我们明天将野餐。因此，若今天下雨，则我们明天将野餐。()()() 假言自然推理系统定义 一个形式系统I包括下面四个部分非空的字母表，记作A(I)中符号构造的合式公式集，记作E(I)中一些特殊的公式组成的公理集,记推理规则集，记作记I=<A(I),E(I),AX(I),R(I其<A(I),E(I),AX(I),R(I)>是I的形式语言系统自然推理系统自然推理系统无公理即公理推理系统推出的结论是系统中的重言式,称作定理自然推理系统定义3.3自然推理系统P定义如下字母命题变项符号：pqrpiqiri联结词符号：括号与逗号：合式公式（同定义推理规结论置换规假言推理规 (6)化简规 ∴

推理规附加规 假 规

析 规A∴A推理规构造性二难规 (11)破坏性二难规(12)

在自然推理系统P设前提A1,A2,,Ak,结论B及公式序列C1,C2,Cl如果每一个Ci(1il)是某个Aj或者可由序列中前面的公式应用推理规则得到,并且Cl=B,则称这个公式序列是由A1,A2,,可以证明，存在由A1A2,Ak推出B的证明的充要条件是B是A1A2,Ak的有效结论，即A1A2AkB.说明证明的引理1:设AC1C2是公式如果AC1AC2则AC1引理2：如果ABBC，则A定理:设A是公式集合，B是一个公式。于是，从A证明出B的充要条件是B是A的有效结论。说明证明的证明：必要性，设存在从A推出B的证明，对任意Ci (i=1，…，k)，往证Ci是A的有效对i用归纳法 当i=1时，因C1A，显然,C1…C1是恒真公式，故AC1C1是A的有效结论。设i<n时，命题成立当i=n时，若CnA，则ACn说明证明的若Cn是某些Cj(j<n)的有效结论，不妨设(Cj1…Cjh)Cn 其中j1，…，jh都小于n由归纳假设知，ACjm，m=1，…，h。A(Cji…Cjh) ACn即Cn是A的有效结论，归纳完成说明证明的充分性，若B是A的有效结论，则存在如下其中C1，…，Ck是A中所有公C1…实例2若明天是星期一或星，我明天就有课.若我明天有课，今天必备课我今天没备课.解 设命题并符号设p：明天是星期一，q：明天是星r：我明天有课，s：我今天直接证明前提 rs,结论证 前提引 前提引 ①②拒取 前提引 ③④拒取 ⑤置附加前提证附加前提证明法欲前提：A1A2结论等价地证前提：A1A2Ak结论理由((附加前提证明法实例 构造下面推理的证2是素数或合数若2是素数，则π是无理数若π是无理数，则4不是素数.所以，如果4是素解p：2是素数，q：2是合数，rπ是无理数，s：4是素数前提：pq,pr,结论附加前提证明法实 (3)证 附加前提引 前提引 前提引 ①④拒取 前提引 归谬法（反证法归谬法(反证法欲前提：A1A2结论做提中加入B，推 理由:归谬法实例 前提：(pq)r,rs,s,结论 前提引 前提引 ②③拒 前提引 ④⑤析归谬法实 ⑥置 ①⑦析 前提引 ⑧⑨合

第三章习题自然推理系统归谬法(反证法基本要前提：A1A2结论熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）牢记P练：判断推理是否正1.(1)前提：pq,结论解推理的形式结构方法一：等值演算((pq)(易知10是成假赋值，不是重言式，所以推理不正确练解练解未含m2不是重言式推理不正确 解方法三真值表pq00001011011011011101不是重言式,方法四10是成假赋练(2)前提 结论(qr)(pr)(qp)推理正练习2：构造在系统P 或圆明园玩. .今天是周 游太多.所以,我们去圆明园或证明设p：今天是周六，q：到玩，前提 p,结论练习2解(3)证法一（直接证法 前提引 前提引 ①②假言推 前提引 前提引 ③⑥析 ⑦附练习2解(3)证法二（归谬法 1)2)假言推 4)5)假言推 3)6) 8)置 9)化r 10)合取引练习或是天晴,或是下雨若天晴,我去看若我去看,我就不看书m:天晴 q:下雨s:我看r:我看第一章命题逻 44of 1)2)拒取 3)4)拒取 6)置 7)置 8)化 5)9)析 CP规 第一章命题逻 45of请问谁 犯甲或乙偷盗了请问谁 犯解：命题符p：甲偷盗 u：午夜时屋里的灯光灭了请问谁 犯甲或乙偷盗了

p