离散数学16.ppt

命题逻辑的推理理论?推理的形式结构?判断推理是否正确的方法?推理定律与推理规则?构造证明法 2推理的形式结构—问题的引入推理: 从前提出发推出结论的思维过程前提是指已知的命题公式,结论是推出的命题公式例如果天气凉快,. 所以小王没有去游泳. p:天气凉快, q:小王去游泳前提: (p????q)?p结论: ??q问题:如何判断推理的是否正确? 3推理的形式结构定义“A 1, A 2, …, A k推B”的推理正确当且仅当 A 1?A 2?…?A k?B为重言式. 若对于每组赋值, A 1?A 2?…?A k为假,或当A 1?A 2?…?A k为真时, B也为真, 则称由 A 1,A 2,…, A k 推B的推理正确, 否则推理不正确(错误) . 推理的形式结构: A 1?A 2?…?A k?B或前提: A 1, A 2, …, A k结论: B若推理正确,则记作: A 1?A 2?…?A k?B. 4判断推理是否正确的方法?真值表法?等值演算法?主析取范式法?构造证明法说明:当命题变项比较少时,用前 3个方法比较方便, 此时采用形式结构“A 1?A 2?…?A k?B”. 当命题变项比较多时,用构造证明法, 采用“前提: A 1, A 2, …, A k, 结论: B”. 5推理定律——重言蕴涵式重要的推理定律 A?(A?B ) 附加律(A?B ) ?A化简律(A?B)?A?B假言推理(A?B) ?? B??A拒取式(A?B) ?? B?A析取三段论(A?B)?(B?C ) ?(A?C ) 假言三段论(A?B)?(B?C ) ?(A?C ) 等价三段论(A?B)?(C?D)?(A?C ) ?(B?D ) 构造性二难 6推理定律(A?B)?(?A?B)?(A ?? A ) ?B构造性二难(特殊形式) (A?B)?(C?D)?( ?B ?? D ) ?(?A ?? C)破坏性二难说明: 若某推理符合某条推理定律,则它自然是正确的 A?B产生两条推理定律: A ? B, B ? A 7推理规则(1) 前提引入规则(2) 结论引入规则(3) 置换规则(4) 假言推理规则 A?B A ? B (5) 附加规则 A?A?B (6) 化简规则 A?B? A (7) 拒取式规则 A?B?B??A (8) 假言三段论规则 A?BB?C?A?C 8推理规则(11) 破坏性二难推理规则 A?BC?D?B ?? D??A ?? C (12) 合取引入规则 AB?A?B (9) 析取三段论规则 A?B?B?A (10) 构造性二难推理规则 A?BC?DA?C?B?D 9构造证明——直接证明法例构造下面推理的证明: 若明天是星期一或星期三,我就有课. 若有课, 今天必备课. 我今天下午没备课. 所以, 明天不是星期一和星期三. 解设p:明天是星期一, q:明天是星期三, r:我有课, s:我备课形式结构为前提: (p?q)?r, r?s, ?s结论: ?p ?? q 10 直接证明法证明①r?s前提引入②?s前提引入③?r①②拒取式④(p?q)?r前提引入⑤?(p?q ) ③④拒取式⑥?p ?? q⑤置换