离散数学--第二章 命题逻辑的推理理论ppt课件.ppt

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

1、离散数学DiscreteMathematicsChenGuangxiSchoolofMathematicsandComputingScience第二章命题逻辑的推理理论目标:掌握推理形式结构熟练运用构造推理方法了解命题逻辑归结证明学习建议:与初中平面几何证明进行对比勤做练习第二章命题逻辑的推理理论第一节命题逻辑的推理演算第二节命题逻辑的归结推理方法第三节命题逻辑的公理系统第二章命题逻辑的推理理论推理是由前提出发推出结论的思维过程。前提是已知的命题公式，结论是由前提出发运用推理规则所推出的命题公式。设为前提，B是另一个命题公式，B是否为的结论

2、定义如下：第二章命题逻辑的推理理论【定义2.1.1】有效结论设是一个有限公式的集合，其中是命题公式，B是另一个公式，记├B为推理的形式结构。第二章命题逻辑的推理理论若公式为重言式，则称由前提得到结论B的推理是正确的或有效的，并且称B是前提的有效结论。若公式不是重言式，则称推理不正确。第二章命题逻辑的推理理论与用表示是重言式类似，用是重言式，不是联结词符。若推出B的推理正确，则记作称AB为蕴涵式。第二章命题逻辑的推理理论蕴涵式有下列性质：对任何公式A，有AA；(1)若AB，BC，则AC；(2)若AB，AC，则A(BC)；(3

3、)若BA，CA，则(BC)A。第二章命题逻辑的推理理论【定理2.1.1】AB当且仅当AB且BA。有些重要的重言蕴涵式称为推理定律，它们在推理理论中占有重要的地位。重要的重言蕴涵式主要有以下8条：1、附加律2、化简律3、假言推理(或分离规则)第二章命题逻辑的推理理论4、拒取式5、析取三段论6、假言三段论7、等价三段论8、构造性二难以上8条中，用得最多的是第三，第五和第六条。第二章命题逻辑的推理理论〖例2.1.1〗判断下列推理是否正确：（1）若今天是1号，则明天是3号。今天是1号。所以，明天是3号。（2）若今天是1号，则明天是3号

4、。明天不是3号。所以，今天不是1号。（3）若今天是1号，则明天是3号。若明天是3号，则后天是5号。所以，若今天是1号，则后天是5号。第二章命题逻辑的推理理论〖例2.1.1〗判断下列推理是否正确：（4）今天是1号或2号。今天不是1号。所以，今天是2号。（5）若今天是1号，则明天是3号。若今天是2号，则明天是6号。今天是1号或2号。所以，明天是3号或6号。第二章命题逻辑的推理理论解：设p：今天是1号。q：明天是3号。r：后天是5号。s：今天是2号。t：明天是6号。5个推理对应的形式结构分别为：(1)├q；(2)├﹁q；(3)├；(4)├s；(5

5、)├。第二章命题逻辑的推理理论在实际中的推理，恰好为8条推理定律的推理还是不多的，在大多数情况下，要证明推理正确，就是证明公式为重言式，其证明方法主要有以下几种：(1)真值表法将的真值表写出来。若真值表的最后一列全为1，说明为重言式，因而推理正确。否则，推理不正确。第二章命题逻辑的推理理论(2)等值演算法通过等值演算。若公式则说明推理正确。(3)主析取范式法若公式的主析取范式含全部2n个极小项，则说明推理正确。否则推理不正确。第二章命题逻辑的推理理论(4)构造证明法当前提与结论中命题变项较多时，前几种方法的工作量太大，不方便，而构造证明法较

6、为方便。构造证明法必须在给定的推理规则下进行。常用的推理规则有以下11条：(1)前提引入规则：在证明的任何步骤上，都可以引入前提。(2)结论引入规则：在证明的任何步骤上，所得中间结果都可以作为后继证明的前提。(3)置换规则：在证明的任何步骤上的公式中的子公式均可用与之等值的公式置换。第二章命题逻辑的推理理论(4)假言推理规则(或叫分离规则)：(5)附加规则：第二章命题逻辑的推理理论(6)化简规则：(7)拒取式规则：第二章命题逻辑的推理理论(8)假言三段论：(9)析取三段论规则：或者第二章命题逻辑的推理理论(10)构造性二难推理规则：(11)

7、合取引入规则：第二章命题逻辑的推理理论〖例2.1.2〗判断下列推理是否正确，并且给出证明。(1)若a是偶数，则b是奇数。或者a是偶数，或者a整除b。a是偶数。所以，b不是奇数。(2)因为今天我休息，所以我要到象鼻山公园或七星公园去玩。如果象鼻山公园的游人太多，我就不去象鼻山公园玩。今天我休息。象鼻山公园游人太多。所以，我去七星公园玩。第二章命题逻辑的推理理论解：(1)先将简单命题符号化。p：a是偶数，q：b是奇数，r：a整除b.再写出前提和结论。前提：结论：推理的形式结构为{}├第二章命题逻辑的推理理论①真值表法当前命题为：第二章命题逻辑的

8、推理理论②等值演算法由最后结果可知，有两个成假赋值，就是110和111，这与真值表的结果是一致的。第二章命题逻辑的推理理论③主析取范式法由主析取范式可知，不是重言式(不含极小项)