离散数学第二章-命题演算的推理理论-命题演算的公理系统.ppt

《离散数学第二章-命题演算的推理理论-命题演算的公理系统.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录（数理逻辑）第一章命题演算基础（6学时）第二章命题演算的推理理论（4学时）第三章谓词演算基础（5学时）第四章谓词演算的推理理论（5学时）第五章递归函数论（4学时）第二章命题演算的推理理论例判断下面各推理是否正确:(1)如果天气凉快,小王就不去游泳。天气凉快,所以小王没去游泳。(2)如果天气凉快,小王就不去游泳。天气不凉快,所以小王去游泳了。推理是否正确：形式化引入符号：P表示天气凉快，Q表示小王去游泳(1)如果天气凉快,小王就不去游泳。天气凉快,所以小王没去游泳。((PQ)P)Q(2)如果天气凉快,小王就不去游泳。天气不凉快,所以小王去游泳了。((PQ)P)

2、Q推理是否正确?考察主析取范式((PQ)P)Q=((PQ)P)Q=(PQ)PQ=(PQ)PQ=(PQ)PQ=(PQ)(P(QQ))(Q(PP))=(PQ)(PQ)(PQ)(QP)=m0∨m2∨m3∨m1永真公式推理是否正确?考察主析取范式((PQ)P)Q=((PQ)P)Q=(PQ)PQ=(PQ)PQ=(PQ)PQ=(PQ)(P(QQ))(Q(PP))=(PQ)(PQ)(QP)=m0∨m1∨m2非永

3、真公式推理是否正确：真值表PQ((PQ)P)Q((PQ)P)QTTTTTFTTFTTFFFTT((PQ)P)Q为永真公式而((PQ)P)Q不是永真的。三段论三段论可用三段论表示((PQ)P)Q如下：PQ大前提P小前提Q结论例如果今天下雨，则运动会将推迟举行；今天下雨；运动会将推迟举行。逻辑推理由前提推出结论（前提与结论都是命题，可真可假）演绎推理归纳推理归纳推理从真的前提出发，得到的结论只能够要求它与前提是协调的，但不一定是真的。它基于对特殊的代表的有限观察，或基于对反复再现的现象的模式的有限观察，用公式表达规律。所有观察到的乌鸦都是黑的。所

4、以所有乌鸦都是黑的。演绎推理可推导性——当前提的真蕴涵结论的真时，称前提和结论之间有可推导性关系，即前提和结论之间的推理是正确的。演绎推理——前提和结论之间有可推导性关系的这种推理。前提和结论间的形式关系(而不考虑内容)如果1+1=3，则雪是黑的。1+1=3。雪是黑的。该推理过程正确,但不意味着前提与结论正确第二章命题演算的推理理论2.1命题演算的公理系统2.1.1公理系统的组成部分2.1.2公理系统的推理过程2.2命题演算的假设推理系统2.3命题演算的归结推理法2．1命题演算的公理系统给出若干条永真公式(称为公理)，再给出若干条由永真公式推出永真公式的推理规则，由它们出发推出一切

5、永真公式的系统。了解公理系统的构成规则和推理形式，培养读者构造公理系统及利用该公理系统进行推理的能力。2．1．1公理系统的组成部分一、语法部分㈠基本符号公理系统所允许出现的全体符号的集合㈡公理㈢规则二、语义部分㈠基本符号命题变元P，Q，R，……等字母表示命题变元联结词、、、、是联结词括号(，)是括号合式公式(1)任何命题变元均是公式；(2)如果P为公式，则P为公式；(3)如果为P，Q为公式，则PQ，PQ，PQ，PQ为公式；(4)当且仅当经过有限次使用(1),(2),(3)所组成的符号串才是公式。推出符┣表示其后的公式为永真公式(教材中遗漏)㈡公理公理1PP公理

6、2(P(QR))(Q(PR))公理3(PQ)((QR)(PR))公理4(P(PQ))(PQ)公理5(PQ)(PQ)公理6(PQ)(QP)公理7(PQ)((QP)(PQ))调头传递凝缩与有关㈡公理公理8(PQ)P公理9(PQ)Q公理10P(Q(PQ))公理11P(PQ)公理12Q(PQ)公理13(PR)((QR)((PQ)R))公理14(PQ)(QP)公理15PP与∧有关与∨有关与有关常用推理定律(详见耿素云《离散数学》)P(P∨Q)附加(P∧Q)P化简((PQ)∧P)Q假

7、言推理((PQ)∧Q)P拒取式((A∨B)∧A)B析取三段论((AB)∧(BC))(AC)假言三段论((AB)∧(BC))(AC)等价三段论(AB)∧(CD)∧(A∨C)(B∨D)构造性二难常用推理定律(详见方世昌的《离散数学》)P(P∨Q)加法式(P∧Q)P简化式((PQ)∧P)Q假言推理((PQ)∧Q)P拒取式((A∨B)∧A)B析取三段论((AB)∧(BC))(AC)(假言)前提三段论(AB)∧(C