第五讲命题逻辑.ppt

《第五讲命题逻辑.ppt》由会员分享，可在线阅读，更多相关《第五讲命题逻辑.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五讲命题逻辑现在学习的是第1页，共60页第一节 命题公式与真值函项第二节 命题公式之间的逻辑等值关系第三节 基本的有效推理式第四节 推理有效性的形式证明第五节 无效推理的证明现在学习的是第2页，共60页第一节命题公式与真值函项1.1 命题公式1.2 命题公式与真值函项现在学习的是第3页，共60页1.1命题公式初始符号命题变元：p，q，r，命题联结词：，辅助符号：（，）逻辑变元逻辑变元 逻辑常元逻辑常元 辅助符号辅助符号现在学习的是第4页，共60页第1类符号是逻辑变元，它们是抽象的命题代表，如果代表真命题，变元取值为真，如果代表假命题则取值为假。因此1类符号称作以真值为定义域的变元。第2类符号

2、是逻辑常元，它们有确定的逻辑解释因而能够表达某种确定的真假联系。第3类符号则是为避免歧义以构造合式命题公式所需要的辅助符号。现在学习的是第5页，共60页形成规则1、所有命题变元是命题公式；2、如果是命题公式，那么是命题公式3、如果、是命题公式，那么（），（）、（）和（）也是命题公式；4、只有符合以上3条的才是命题公式。现在学习的是第6页，共60页 pqr，pq，pq r从逻辑的角度看，命题公式是构造出来的，具体命题只是命题公式的例示，即命题公式的一个特例。如下具体命题都是命题公式“（pq）r”的例示：如果加温到了一定限度且加压到一定限度，那么空气可以液化。如果考试合格并且体验合格，那么就可以上

3、大学。现在学习的是第7页，共60页1.2命题公式与真值函项命题公式就相当于一个函数式，公式的值由变元的值唯一确定。命题公式是一个以真假为定义域，并且也以真假为值域的特殊函数。真假是命题的逻辑值，简称真值。因此，命题公式被称作真值函项。现在学习的是第8页，共60页1.2命题公式与真值函项我们可以看到，给定个命题变元，则有n种真假取值，然后构成2 n个真值函项。这些不同的真值函项分为三大类：恒真式。不论其中的变元取什么样的值，函项式的值恒为真。恒假式。无论其中的变元取什么样的值，函项式的值恒为假。协调式。既不是恒真式也不是恒假式函项式。显然，协调式在其变元的某些取值组合下为真，在另一些取值组合下又

4、为假的。因此。协调式的真假由变元的真假决定。现在学习的是第9页，共60页第二节命题公式之间的逻辑等值关系2.1命题公式之间的逻辑等值2.2几个重要的重言等值式2.3命题联结词的相互定义现在学习的是第10页，共60页2.1命题公式之间的逻辑等值逻辑等值的公式：表达同一真值函项的公式在任何情况下都具有相同的逻辑值，我们称这些公式是逻辑等值的公式。真值表：判定两个公式是否是逻辑等值的例1、判定命题公式“p q”与“(pq)”是否逻辑等值。例2、判定命题公式“(pq)r”与“p(q r)”是否逻辑等值。现在学习的是第11页，共60页2.1命题公式之间的逻辑等值如果两个公式是等值的，那么以这两个公式为子

5、公式构造一个等值式：（p q）（(pq)）。这个等值式是恒真的，由此可推知，一个等值式是重言式，那么它的两个子公式逻辑等值。如果一个等值式是重言式，那么我们就用符号“”代替等值联结“”。现在学习的是第12页，共60页2.2几个重要的重言等值式1、交换律 (pq)(q p)(pq)(q p)2、结合律(pq)r)(p(q r)(p q)r)(p(q r)3、德摩根律 (pq)pq；(pq)pq。现在学习的是第13页，共60页4、分配律 p(qr)(pq)(pr)p(qr)(pq)(pr)5、实质蕴涵（pq）（p q）6、假言易位（pq）（q p)7、移出律(pq)r p(q r)8、实质等值(p

6、q)(p q)(q p)9、双否律 p p 10、重言律p p p p p p现在学习的是第14页，共60页2.3命题联结词的相互定义“，”、“，”、“，”例、证明用“，”构造的命题公式可以定义所有五种基本命题公式。现在学习的是第15页，共60页第三节 基本的有效推理式3.1推理的有效性3.2基本的有效推理式现在学习的是第16页，共60页3.1推理的有效性（1）“如果张珊是中国公民并且她有选举权，那么张珊年满18岁。张珊是中国公民，但是她还没满18岁。所以，张珊没有选举权。”（2）“如果张珊是中国公民并且她有选举权，那么张珊年满18岁。张珊是中国公民，但是她还没满18岁。张珊没有选举权。”现在

7、学习的是第17页，共60页第三节基本的有效推理式3.1推理的有效性推理是一个包含特殊词项的命题集合，根据这样的词项，我们可以区分出前提和结论。推理的有效性是由推理的形式决定的。它表现为作为前提的命题同作为结论的命题之间的一种逻辑关联性，这种逻辑关联取决于构成推理的命题的形式结构特征。现在学习的是第18页，共60页如果前提真时结论必然是真的，我们就称前提和结论之如果前提真时结论必然是真的，我们就称前提和结论之间有必然的逻辑联系。这种联系保证了推理决不会出现间有必然的逻辑联系。这种联系保证了推理决不会出现前提真而结论假的情况。因此，可以由前提的真来保证前提真而结论假的情况。因此，可以由前提的真来保

8、证结论真，由前提可靠有效地推演出结论的可靠。前提和结论真，由前提可靠有效地推演出结论的可靠。前提和结论之间具有必然逻辑联系的推理就是有效推理。结论之间具有必然逻辑联系的推理就是有效推理。如果前提和结论之间不具有必然的逻辑联系，那么前如果前提和结论之间不具有必然的逻辑联系，那么前提真时结论是否为真不能确定，即不能由前提的真有提真时结论是否为真不能确定，即不能由前提的真有效地推导出结论真，这样的推理就是无效推理。效地推导出结论真，这样的推理就是无效推理。现在学习的是第19页，共60页推理：推理：设命题序列设命题序列=是一个是一个推理形式，其中推理形式，其中p1,p2.pn是前提，是前提，q是结论。

9、是结论。是一个有效的推理式，当且仅当，是一个有效的推理式，当且仅当，如果如果p1,p2.pn真那么真那么q一定为真。一定为真。是无效推理式，如果至少有一个是无效推理式，如果至少有一个的代换示例使得的代换示例使得p1,p2.pn真但真但q假假。现在学习的是第20页，共60页根据合取式的逻辑特征：根据合取式的逻辑特征：pq p合取消去合取消去简记为简记为-合取引入合取引入简记为简记为+Pqpq3.2 3.2 基本的有效推理式基本的有效推理式小张喜爱音乐，小张喜爱音乐，小张喜爱体育，小张喜爱体育，所以，小张不但喜爱音乐，也喜爱体育。所以，小张不但喜爱音乐，也喜爱体育。小张既有优点，也有缺点，小张既有

10、优点，也有缺点，所以，小张是有优点的。所以，小张是有优点的。现在学习的是第21页，共60页根据析取式的逻辑特征：根据析取式的逻辑特征：选言三段论选言三段论简记简记-p q p q附加规则附加规则简记简记+p p q3.2 基本的有效推理式基本的有效推理式或者李某是嫌疑犯，或者王某是嫌疑犯或者李某是嫌疑犯，或者王某是嫌疑犯(或者二者或者二者都是都是)；李某不是嫌疑犯；李某不是嫌疑犯；所以，王某是嫌疑犯。所以，王某是嫌疑犯。发烧可由肺炎引起；发烧可由肺炎引起；所以，发烧或者可由肺炎引起或者可由感冒引起。所以，发烧或者可由肺炎引起或者可由感冒引起。现在学习的是第22页，共60页根据蕴涵式的逻辑特征：

11、根据蕴涵式的逻辑特征：分离规则分离规则简记简记MPpq p q逆分离规则逆分离规则简记简记MTpq q p二难推理二难推理(CD)(pq)(rs)pr qs假言三段论假言三段论简记简记HSpq qr pr3.2 基本的有效推理式基本的有效推理式(pq)(rs)q s p r破坏式二难推理破坏式二难推理(DD)现在学习的是第23页，共60页第四节推理有效性的形式证明4.1 推理有效性与命题演算4.2 有效推理的形式证明4.3 等值替换规则4.4 条件证明规则C.P4.5 间接证明规则RAA4.6 证明重言式现在学习的是第24页，共60页4.1 推理有效性与命题演算对于简单的复合命题推理，我们可以

12、直接根据这些基本有效式来判定推理是否有效。但是对于复杂的推理这样就不够了。例1 如果商品短缺日益严重，那么物价会上涨。如果存在生产过剩，那么物价不会上涨。如果存在通货膨胀威胁，那么财政控制将继续。如果政府改组，那么财政控制将取消。或者存在生产过剩，或者政府改组。因此，商品短缺不会日益严重，或者不再存在通货膨胀威胁。现在学习的是第25页，共60页4.1 推理有效性与命题演算命题演算系统建立命题演算系统有两种方法：一是公理化方法，一是自然演绎方法。公理化的命题演算系统是在形式语言基础上增添公理和变形规则建构起来的。自然演绎系统，没有公理，只有一系列推理规则。它是引入特定前提为假设，根据推理规则推演

13、出结论而建构起来的演算系统。现在学习的是第26页，共60页4.2有效推理的形式证明在命题演算系统中对推理有效性的证明称作形式证明。现在给出自然演绎系统中形式证明的定义：形式证明的定义 一个形式证明是一个命题公式序列A1,A2,An。其中任一的Ai（1i n）或者是前提，或者是由前面的公式根据推理规则得到的。序列的最后一个公式An恰好是结论。现在学习的是第27页，共60页4.2有效推理的形式证明自然演绎系统形式证明是建立在推理规则基础之上的。这些规则大约可分为四部分：一是基本推导规则，二是等值替换规则，三是条件证明规则，四是间接证明规则。现在学习的是第28页，共60页根据合取式的逻辑特征：根据合

14、取式的逻辑特征：pq p分解式分解式简记为简记为-组合式组合式简记为简记为+Pqpq根据析取式的逻辑特征：根据析取式的逻辑特征：选言三段论选言三段论简记简记-P qp q附加式附加式简记简记+P P q根据蕴涵式的逻辑特征：根据蕴涵式的逻辑特征：分离式分离式简记简记MPpq p q逆分离式逆分离式简记简记MTpq q p二难推理二难推理CD(pq)(rs)pr qs假言三段论假言三段论简记简记HSpq qr pr一、基本推导规则：一、基本推导规则：(pq)(rs)q s p r破坏式二难推理破坏式二难推理DD现在学习的是第29页，共60页例1 如果商品短缺日益严重，那么物价会上涨。如果存在生产

15、过剩，那么物价不会上涨。如果存在通货膨胀威胁，那么财政控制将继续。如果政府改组，那么财政控制将取消。或者存在生产过剩，或者政府改组。因此，商品短缺不会日益严重，或者不再存在通货膨胀威胁。解：设“商品短缺日益严重”为A，“物价会上涨”为B，“存在生产过剩”为C，“存在通货膨胀威胁”为D，“财政控制将继续”为E，“政府改组”为F。首先将该推理形式化，在此基础上建立该推理有效性的形式证明。现在学习的是第30页，共60页 A B P C B P D E P F E P C F P /AD（C B）（F E）+B E CD（A B）（D E）+AD DD现在学习的是第31页，共60页我们还看到，整个形式

16、证明的内容可分为三部分：第一部分是序号，它既标示了命题公式出现的顺序，这些序号同时又是在它后面出现的那个公式的代表。第二部分是若干个命题公式，它们或者是前提，或者是由前面的公式根据推理规则得到的。第三部分则是一些根据，它说明每个命题公式在为什么在形式证明中出现。形式证明的这三个构成部分缺一不可。现在学习的是第32页，共60页4.3等值替换规则例:(AB)C AC 运用八条基本规则不能建立有关这个推理的形式证明。等值替换规则实际上就是引入一些逻辑等值式作为推理规则，并规定在形式证明中，等值式两边的公式可以相互替换使用。现在学习的是第33页，共60页二、置换规则二、置换规则交换律交换律(Com)：

17、pq qp pq qp结合律结合律(Ass)：p(qr)(pq)r p(qr)(pq)r德德摩根律摩根律(Dem)：(pq)(pq)(pq)(pq)分配律分配律(Dist):p(qr)(pq)(pr)；p(qr)(pq)(pr)实质蕴涵律实质蕴涵律(Impl)：（pq）（pq）假言易位律（假言易位律（Tran):（p q）（q p）移出律移出律(Exp)：pq r p(qr)实质等值实质等值(Eq)：pq (pq)(qp)双否律双否律(DN)：p p重言律重言律(Taut)：p (p p)p (p p)现在学习的是第34页，共60页(AB)C AC证：(AB)C P AC (AB)C Impl

18、 (A B)C DeM (A C)(B C)Dist A C -A C Impl现在学习的是第35页，共60页作 业一、运用真值表方法,判定下列命题是不是等值命题。l如果这匹马儿不吃饱草,那么这匹马儿不能跑。2或者这匹马儿吃饱草,或者这匹马儿不能跑。3既要这匹马儿跑,又要这匹马儿不吃饱草,这是办不到的。1.pq；2.pq；3.(qp)。现在学习的是第36页，共60页4.4 证明的方法证明的方法一一 推理有效性的形式证明推理有效性的形式证明(一一)条件证明规则条件证明规则有了基本推导规则和等值替换规则还不足以为所有有效的复杂推理建有了基本推导规则和等值替换规则还不足以为所有有效的复杂推理建立形式

19、证明，例如下列推理立形式证明，例如下列推理AA（BCBC）（ABAB）（ACAC）这个推理是有效的，但要证明其有效性还需要引入新的推理规则。因这个推理是有效的，但要证明其有效性还需要引入新的推理规则。因此我们引入此我们引入条件证明规则条件证明规则C.PC.P。引入这条规则还有一个作用，即可。引入这条规则还有一个作用，即可以简化证明过程。以简化证明过程。现在学习的是第37页，共60页4.4 证明的方法证明的方法条件证明规则的根据：条件证明规则的根据：有效推理的逻辑特征是：前提真时结论必真，不存在有使其前有效推理的逻辑特征是：前提真时结论必真，不存在有使其前提真而结论假的例示。如果我们以有效推理的

20、前提的合取为前提真而结论假的例示。如果我们以有效推理的前提的合取为前件，结论为后件构造一个蕴涵式，那么这个蕴涵式就不可能前件，结论为后件构造一个蕴涵式，那么这个蕴涵式就不可能前件真而后件假。件真而后件假。相反，如果推理式不是有效的，那么存在这样的例示使得该推理相反，如果推理式不是有效的，那么存在这样的例示使得该推理式前提真而结论假。因此，与这个推理式相应的蕴涵式就不可能式前提真而结论假。因此，与这个推理式相应的蕴涵式就不可能是重言式。是重言式。现在学习的是第38页，共60页4.4 证明的方法证明的方法 由此我们看到，如果用一个推理式前提的合取为前件，结论为后件构造一由此我们看到，如果用一个推理

21、式前提的合取为前件，结论为后件构造一个蕴涵式，那么这个推理式与该蕴涵式之间存在这样一种等价关系：如果个蕴涵式，那么这个推理式与该蕴涵式之间存在这样一种等价关系：如果推理式是有效的，那么蕴涵式是重言式；如果推理式不是有效的，那么蕴推理式是有效的，那么蕴涵式是重言式；如果推理式不是有效的，那么蕴涵式就不是重言式。涵式就不是重言式。等值替换规则中的移出律等值替换规则中的移出律(Exp)指出，如下两个蕴涵式是逻辑等值的：指出，如下两个蕴涵式是逻辑等值的：(p q)r)(p(qr)两个蕴涵式分别对应于如下推理式：两个蕴涵式分别对应于如下推理式：现在学习的是第39页，共60页4.4 证明的方法证明的方法(

22、p q)r 对应于对应于 p(qr)对应于对应于 p p q qr r 这两个推理式的区别在于：命题公式这两个推理式的区别在于：命题公式“q”在左边的推理式中是前提，在左边的推理式中是前提，而在右边的推理式中是结论的构成部分。就是说，右边的推理式比左而在右边的推理式中是结论的构成部分。就是说，右边的推理式比左边的少了一个前提边的少了一个前提“q”，并且它们有不同的结论：左边推理式的结，并且它们有不同的结论：左边推理式的结论是论是“r”，右边推理式的则是，右边推理式的则是“qr”，“q”从前提中消去而变成了结论从前提中消去而变成了结论的前件。的前件。现在学习的是第40页，共60页4.4 证明的方

23、法证明的方法由于两个蕴涵式是逻辑等值的，即如果一个是重言式，另一个由于两个蕴涵式是逻辑等值的，即如果一个是重言式，另一个也必是；一个不是重言式，另一个也必不是。因此这两个推理也必是；一个不是重言式，另一个也必不是。因此这两个推理式是等价的：如果一个推理式有效，另一个必有效；一个是无式是等价的：如果一个推理式有效，另一个必有效；一个是无效的，另一个也必无效。效的，另一个也必无效。条件证明规则条件证明规则C.P p q pq现在学习的是第41页，共60页4.4 证明的方法证明的方法例例1 A（BC）（AB）（AC）证明：证明：A（BC）P （A B）C Exp （B A）C Com B（AC）Ex

24、p AB A（AC）HS （A A）C Exp AC Taut （AB）（AC）-CP现在学习的是第42页，共60页4.4 证明的方法证明的方法由上例中我们看到，第由上例中我们看到，第步是将结论的前提作为一个附加前提引入步是将结论的前提作为一个附加前提引入了形式证明中，到第了形式证明中，到第步推出了结论的后件，于是就运用步推出了结论的后件，于是就运用CPCP规则规则消去消去这个附加前提，即以这个附加前提，即以为前件为前件为后件而得到为后件而得到，恰好是结恰好是结论。论。我们在引入附加前提我们在引入附加前提的同时就用线段标明了这个附加前提的辖域。在的同时就用线段标明了这个附加前提的辖域。在辖域中

25、出现的辖域中出现的、和和这几个公式依赖于这几个公式依赖于和和这两个前提。而公这两个前提。而公式式出现在附加前提出现在附加前提的辖域之外，因为的辖域之外，因为CP规则的运用已经将规则的运用已经将从前从前提中消去，提中消去，就只依赖于前提就只依赖于前提了。了。现在学习的是第43页，共60页4.4 证明的方法证明的方法因此，标明辖域在条件证明规则因此，标明辖域在条件证明规则CP的运用中有很重要的意义。我的运用中有很重要的意义。我们规定，们规定，凡引入附加前提必须标明该前提的辖域。而辖域没有封闭，凡引入附加前提必须标明该前提的辖域。而辖域没有封闭，证明就不能结束，因为这时推演出的公式还依赖于附加前提，

26、即依赖证明就不能结束，因为这时推演出的公式还依赖于附加前提，即依赖于给定前提之外的东西。如果辖域已经封闭，那么在辖域中出现的公于给定前提之外的东西。如果辖域已经封闭，那么在辖域中出现的公式不能再作为推演的根据，因为我们必须保证推出的结论只依赖于给式不能再作为推演的根据，因为我们必须保证推出的结论只依赖于给定的前提，不需要除前提外的其它东西。定的前提，不需要除前提外的其它东西。错误地运用条件证明规则举例：错误地运用条件证明规则举例：现在学习的是第44页，共60页4.4 证明的方法证明的方法 V U P U W P （V X）W P VX V U -W -（V X）MT V X DeM VX Im

27、pl注意：注意：这个形式证明的错误在于附加前提这个形式证明的错误在于附加前提的辖域没有封闭。虽然的辖域没有封闭。虽然公式公式与结论有完全相同的形式，但它是出现在附加前提与结论有完全相同的形式，但它是出现在附加前提的辖域的辖域内，除给定前提内，除给定前提外，它还依赖于外，它还依赖于，而，而是原前提中没有是原前提中没有的。的。现在学习的是第45页，共60页4.4 证明的方法证明的方法例例2 A（B D）B（C（C E）F）/AF 证明：证明：A（B D）P B（C（C E）F）P A B D MP B -（C（C E）F MP C C E +C（C E）-CP F MP AF -CP现在学习的是第

28、46页，共60页4.4 证明的方法证明的方法(二二)间接证明规则间接证明规则RAARAA 间接证明又叫做间接证明又叫做归谬证明归谬证明或或反证法反证法。这是一种在数学中经常用到。这是一种在数学中经常用到的证明方法。当我们要证明某一定理时，先引入该定理的否定的证明方法。当我们要证明某一定理时，先引入该定理的否定作为假设，然后由这一假设推导出矛盾。由于矛盾是不可能的，作为假设，然后由这一假设推导出矛盾。由于矛盾是不可能的，假设一定错误，即该定理的否定不成立。由此就假设一定错误，即该定理的否定不成立。由此就间接地间接地证明了证明了该定理成立。该定理成立。间接证明规则就是根据这一思路得到的。当我们为一

29、有效推理建立形式证明间接证明规则就是根据这一思路得到的。当我们为一有效推理建立形式证明时，时，不是直接去证明由前提推演出结论，而是将结论的否定作为一个补充不是直接去证明由前提推演出结论，而是将结论的否定作为一个补充前提引入形式证明。然后由扩充的前提集合推演出一个矛盾：即推演出一前提引入形式证明。然后由扩充的前提集合推演出一个矛盾：即推演出一个形式为个形式为“p p”的命题公式。由这个矛盾我们实际上推演出对这个的命题公式。由这个矛盾我们实际上推演出对这个补充前提的否定，即对结论的否定的否定，再根据双否律补充前提的否定，即对结论的否定的否定，再根据双否律DN，就相，就相当于推演出结论。当于推演出结

30、论。现在学习的是第47页，共60页4.4 证明的方法证明的方法例例3 A（B C）（B D）E D A /E证明：证明：A（B C）P （B D）E P D A P/E E RAA （B D）MT B D DeM D COM，-A -B C MP B -B -B B +现在学习的是第48页，共60页4.4 证明的方法证明的方法在这个形式证明中，公式在这个形式证明中，公式是结论是结论“E”E”的否定，它是作为补充前提的否定，它是作为补充前提引入证明的。证明的最后一步是公式引入证明的。证明的最后一步是公式，它是一个矛盾式，恒为假。如果，它是一个矛盾式，恒为假。如果推理是有效的，前提真时结论必真。现

31、在由于引入补充前提推理是有效的，前提真时结论必真。现在由于引入补充前提而推出了假而推出了假结论，因此公式结论，因此公式这个补充前提一定不成立。这个补充前提一定不成立。不成立即结论的否定不成不成立即结论的否定不成立，即立，即“E”E”，根据双否律推出，根据双否律推出“E”E”。“E”E”即结论，因此结论成即结论，因此结论成立。立。由例由例3可见，运用间接证明规则就是将结论的否定作为补充前提引入可见，运用间接证明规则就是将结论的否定作为补充前提引入证明，最后推出矛盾。由此间接地证明结论成立，推理有效。证明，最后推出矛盾。由此间接地证明结论成立，推理有效。现在学习的是第49页，共60页4.4 证明的

32、方法证明的方法(三三)证明重言式证明重言式 有一种命题的真是无条件的，不依赖于其它命题。这样的命题就有一种命题的真是无条件的，不依赖于其它命题。这样的命题就是重言式。形式证明同样适用于证明重言式。可以证明重言式是是重言式。形式证明同样适用于证明重言式。可以证明重言式是不需要任何前提就可以推演出的命题。不需要任何前提就可以推演出的命题。虽然证明重言式不需要任何前提，但建立形式证明需要有出发点。这意味虽然证明重言式不需要任何前提，但建立形式证明需要有出发点。这意味着我们只能用着我们只能用条件证明条件证明或者或者间接证明间接证明的方法来证明重言式，因为只有的方法来证明重言式，因为只有这两种方法可以引

33、入假设前提。我们以假设前提为出发点就能建这两种方法可以引入假设前提。我们以假设前提为出发点就能建立重言式的形式证明立重言式的形式证明。现在学习的是第50页，共60页4.4 证明的方法证明的方法用条件证明方法证明重言式就是先引入假设前提，然后逐步消去用条件证明方法证明重言式就是先引入假设前提，然后逐步消去所有假设前提而推演出一个公式，这个命题公式就是不依赖于任所有假设前提而推演出一个公式，这个命题公式就是不依赖于任何前提的重言式。何前提的重言式。例例4 证明证明A（BA）是重言式。）是重言式。证明：证明：A A B +B A Com BA Impl A(BA)-CP现在学习的是第51页，共60页

34、4.4 证明的方法证明的方法例例5 证明（证明（pq）p）q是重言式是重言式证明：证明：（pq）p pq -p Com,-q MP （pq）p）q -CP 用间接证明方法证明重言式则是将所证公式的否定引入作为假设前提，用间接证明方法证明重言式则是将所证公式的否定引入作为假设前提，然后推出矛盾。否定一个公式将导致逻辑矛盾，那么这个公式一定是重然后推出矛盾。否定一个公式将导致逻辑矛盾，那么这个公式一定是重言式。言式。现在学习的是第52页，共60页4.4 证明的方法证明的方法例例6 证明证明A（A B）是重言式）是重言式证明：证明：（A（A B）（A（A B）Impl A （A B）DeM A （A

35、 B）DeM （A A）B Ass A A -现在学习的是第53页，共60页4.4 证明的方法证明的方法二二 无效推理的证明无效推理的证明(一一)用真值表证明推理的无效性用真值表证明推理的无效性一个推理是有效的，我们可以为其建立一个形式证明。形式证明一个推理是有效的，我们可以为其建立一个形式证明。形式证明运用推理规则说明，结论是从前提推演出来的，因此前提真时结运用推理规则说明，结论是从前提推演出来的，因此前提真时结论不可能假，推理当然就是有效的。论不可能假，推理当然就是有效的。如果推理是无效的，那么运用推理规则不可能从前提推演出结论。如果推理是无效的，那么运用推理规则不可能从前提推演出结论。所

36、谓不可能是指：无论怎样推演都推不出结论形式的命题公式。形所谓不可能是指：无论怎样推演都推不出结论形式的命题公式。形式证明并没有规定推演到多少步就必须中止。因此，对于无效推理式证明并没有规定推演到多少步就必须中止。因此，对于无效推理我们面临的是一个无法穷尽的推演过程。这意味着形式证明方法不我们面临的是一个无法穷尽的推演过程。这意味着形式证明方法不能证明推理是无效的。能证明推理是无效的。现在学习的是第54页，共60页4.4 证明的方法证明的方法 我们的命题逻辑系统不仅要能证明有效推理，而且还应该证明推理的无我们的命题逻辑系统不仅要能证明有效推理，而且还应该证明推理的无效性。因此，必须给出证明无效推

37、理的方法。效性。因此，必须给出证明无效推理的方法。真值表是判定推理是否有效的可靠方法。一个推理是有效的，真值表是判定推理是否有效的可靠方法。一个推理是有效的，那么前提真时结论必真。在真值表上表现为无论变元被赋予什那么前提真时结论必真。在真值表上表现为无论变元被赋予什么样的值，作为前提的命题公式真时，作为结论的命题公式一么样的值，作为前提的命题公式真时，作为结论的命题公式一定是真的。如果一个推理是无效的，其前提真时结论可真可假定是真的。如果一个推理是无效的，其前提真时结论可真可假。因此只要在真值表上找到一组变元的赋值使得前提真而结论。因此只要在真值表上找到一组变元的赋值使得前提真而结论假，那么推

38、理就是无效的。假，那么推理就是无效的。现在学习的是第55页，共60页4.4 证明的方法证明的方法例例7 用真值表判定下列推理是否有效。用真值表判定下列推理是否有效。C（A B），），A C /BC证明：给出相应的真值表：证明：给出相应的真值表：A B C A B C（A B）A C BCT T T T T T T *T T F T T T FT F T F F T TT F F F T T TF T T F F T TF T F F T F FF F T F F T TF F F F F F T现在学习的是第56页，共60页4.4 证明的方法证明的方法通过列举使推理形式前提真而结论假的赋值情况

39、，以证明推通过列举使推理形式前提真而结论假的赋值情况，以证明推理无效，这种方法被称作简化真值表方法。理无效，这种方法被称作简化真值表方法。例例8 判定如下推理是否有效：判定如下推理是否有效：如果水稻长得好，那么水分充足并且肥料充足。只要风调雨顺，这块地就水分充足。所以，如果水稻长得好，那么水分充足并且肥料充足。只要风调雨顺，这块地就水分充足。所以，只要风调雨顺，那么如果这块地肥料充足水稻就长得好。只要风调雨顺，那么如果这块地肥料充足水稻就长得好。证明：证明：首先将推理形式化：首先将推理形式化：令令“水稻长得好水稻长得好”为为A，“水分充足水分充足”为为B，“肥料充足肥料充足”为为C，“风调雨顺

40、风调雨顺”为为D，该推理的形式如下：该推理的形式如下：A（B C）DB D（CA）只要找到一组对变元的赋值，使得推理的前提真而结论假，就足以证明该推只要找到一组对变元的赋值，使得推理的前提真而结论假，就足以证明该推理是无效的。现将这组赋值列举如下：理是无效的。现将这组赋值列举如下：A B C D A（B C）DB D（CA）F T T T T T F现在学习的是第57页，共60页4.4 证明的方法证明的方法(二二)用归谬赋值法证明推理的有效或无效性用归谬赋值法证明推理的有效或无效性归谬赋值法的基本思路同间接证明方法类似。我们要证明一个推理归谬赋值法的基本思路同间接证明方法类似。我们要证明一个推

41、理是有效的，先假设它无效，这就是归谬。然后根据假设对前提和结是有效的，先假设它无效，这就是归谬。然后根据假设对前提和结论进行赋值，即给命题公式的变元指派确定的真值，以使得推理的论进行赋值，即给命题公式的变元指派确定的真值，以使得推理的前提真而结论假。如果找到这样一组的赋值使得假设成立，那么就前提真而结论假。如果找到这样一组的赋值使得假设成立，那么就说明推理是无效的。我们可以运用上述简化真值表方法把这一组赋说明推理是无效的。我们可以运用上述简化真值表方法把这一组赋值列出来，以证明推理的无效性。值列出来，以证明推理的无效性。如果找不到使假设成立的赋值，那么就说明假设不成立，推理是如果找不到使假设成

42、立的赋值，那么就说明假设不成立，推理是有效的。所谓找不到使假设成立的赋值是指，根据假设对前提和有效的。所谓找不到使假设成立的赋值是指，根据假设对前提和结论赋值必将导致矛盾，即不可避免地要对同一个变元既赋值结论赋值必将导致矛盾，即不可避免地要对同一个变元既赋值T又又赋值赋值F。现在学习的是第58页，共60页4.4 证明的方法证明的方法例例9 判定下列推理是否有效：判定下列推理是否有效：A（B C）（C D）F AF证明：证明：假定推理无效，然后根据假定对前提和结论假定推理无效，然后根据假定对前提和结论赋值：赋值：A（B C）（C D）F A F T T T T T F F F T F T F F现在学习的是第59页，共60页作 业二、将推理形式化并建立推理的有效性证明如果他主张减轻农民的赋税(A)，他将赢得农民的支持(B)。如果他主张政府增加对社会福利的投入(C)，他将赢得工人的支持(D)。如果他既赢得农民的支持又赢得工人的支持，他就肯定能当选(E)。但是他没有当选。所以，或者他不主张减轻农民的赋税，或者不主张政府增加对社会福利的投入。现在学习的是第60页，共60页