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

《离散数学 命题逻辑的推理理论.ppt》由会员分享，可在线阅读，更多相关《离散数学 命题逻辑的推理理论.ppt（18页珍藏版）》请在三一办公上搜索。

1、1,1.6 命题逻辑的推理理论,推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明法,2,推理的形式结构问题的引入,推理:从前提出发推出结论的思维过程 前提是指已知的命题公式，结论是推出的命题公式例 如果天气凉快，小王就不去游泳.天气凉快.所以小王 没有去游泳.p:天气凉快，q:小王去游泳 前提：(p q)p 结论：q问题：如何判断推理的是否正确？,3,推理的形式结构,定义“A1,A2,Ak 推B”的推理正确 当且仅当 A1A2AkB为重言式.若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时,B也为真,则称由A1,A2,Ak推B的推理正确,否则推理不正确（错误）.推理的

2、形式结构:A1A2AkB 或 前提：A1,A2,Ak 结论：B 若推理正确，则记作：A1A2AkB.,4,判断推理是否正确的方法,真值表法等值演算法主析取范式法构造证明法 说明：当命题变项比较少时，用前3个方法比较方 便,此时采用形式结构“A1A2AkB”.当命题变项比较多时，用构造证明法，采用“前提:A1,A2,Ak,结论:B”.,5,实例,例 判断下面推理是否正确(1)若今天是1号，则明天是5号.今天是1号.所 以明天是5号.解 设 p：今天是1号，q：明天是5号.证明的形式结构为:(pq)pq证明（用等值演算法）(pq)pq(pq)p)q pqq 1得证推理正确,6,实例(续),(2)若

3、今天是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是成假赋值，所以推理不正确.,7,推理定律重言蕴涵式,重要的推理定律 A(AB)附加律(AB)A 化简律(AB)A B 假言推理(AB)B A 拒取式(AB)B A 析取三段论(AB)(BC)(AC)假言三段论(AB)(BC)(AC)等价三段论(AB)(CD)(AC)(BD)构造性二难,8,推理定律(续),(AB)(AB)(AA)B 构造性二

4、难（特殊形式）(AB)(CD)(BD)(AC)破坏性二难,说明：若某推理符合某条推理定律，则它自然是正确的AB产生两条推理定律:A B,B A,9,推理规则,10,推理规则(续),11,构造证明直接证明法,例 构造下面推理的证明：若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，明天不是星期一和星期三.解 设 p：明天是星期一，q：明天是星期三，r：我有课，s：我备课形式结构为 前提：(pq)r,rs,s 结论：pq,12,直接证明法(续),证明 rs 前提引入 s 前提引入 r 拒取式(pq)r 前提引入(pq)拒取式 pq 置换,13,构造证明附加前提证明法,欲

5、证明 前提：A1,A2,Ak 结论：CB等价地证明 前提：A1,A2,Ak,C 结论：B理由：(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B(A1A2AkC)B,14,附加前提证明法(续),例 构造下面推理的证明:2是素数或合数.若2是素数，则 是无理数.若 是无理数，则4不是素数.所以，如果4是 素数，则2是合数.用附加前提证明法构造证明解 设 p：2是素数，q：2是合数，r：是无理数，s：4是素数形式结构 前提：pq,pr,rs 结论：sq,15,附加前提证明法(续),证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论请用直接证明法证明之,16,构造证明归谬法（反证法）,欲证明 前提：A1,A2,Ak 结论：B将B加入前提，若推出矛盾，则得证推理正确.理由:A1A2AkB(A1A2Ak)B(A1A2AkB)括号内部为矛盾式当且仅当(A1A2AkB)为重言式,17,归谬法(续),例 构造下面推理的证明 前提：(pq)r,rs,s,p 结论：q证明（用归缪法）q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式,18,归谬法(续),(pq)r 前提引入(pq)析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取请用直接证明法证明之,