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

1,1.6 命题逻辑的推理理论,推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明法,2,推理的形式结构问题的引入,推理举例:(1)正项级数收敛当且仅当部分和有上界.(2)若ACBD，则AB且CD.推理:从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明:描述推理正确的过程.,3,推理的形式结构,定义 若对于每组赋值，或者A1A2 Ak 均为假，或者当A1A2Ak为真时,B也为真,则称由A1,A2,Ak推B的推理正确,否则推理不正确（错误）.“A1,A2,Ak 推B”的推理正确 当且仅当 A1A2AkB为重言式.推理的形式结构: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)若今天是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)B 构造性二难（特殊形式）(AB)(CD)(BD)(AC)破坏性二难,说明：A,B,C为元语言符号若某推理符合某条推理定律，则它自然是正确的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,构造证明附加前提证明法,欲证明 前提：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 合取请用直接证明法证明之,