1、第七讲第七讲 命题逻辑（下）命题逻辑（下）目目 录录v第一节第一节 命题公式与真值函项命题公式与真值函项v第二节第二节 命题公式之间的逻辑等值关命题公式之间的逻辑等值关系系v第三节第三节 基本的有效推理式基本的有效推理式v第四节第四节 推理有效性的形式证明推理有效性的形式证明v第五节第五节 无效推理的证明无效推理的证明第一节第一节 命题公式与真值函项命题公式与真值函项v1.1 命题公式命题公式v1.2 命题公式与真值函项命题公式与真值函项1.11.1命题公式命题公式v初始符号初始符号v命题变元：命题变元：p，q，r，v命题联结词：命题联结词：， v辅助符号：辅助符号： （，（， ）逻辑变元逻辑
2、变元 逻辑常元逻辑常元 辅助符号辅助符号v 第第1 1类符号是逻辑类符号是逻辑变元变元，它们是抽，它们是抽象的命题代表，如果代表真命题，变象的命题代表，如果代表真命题，变元取值为真，如果代表假命题则取值元取值为真，如果代表假命题则取值为假。因此这类符号称作以真值为定为假。因此这类符号称作以真值为定义域的变元。义域的变元。v 第第2 2类符号是逻辑类符号是逻辑常元常元，它们有确定，它们有确定的逻辑解释因而能够表达某种确定的的逻辑解释因而能够表达某种确定的真假联系。真假联系。v第第3 3类符号则是为避免歧义以构造类符号则是为避免歧义以构造合式命题公式所需要的合式命题公式所需要的辅助符号辅助符号。v
3、形成规则形成规则v1 1、所有命题变元是命题公式；、所有命题变元是命题公式；v2 2、如果、如果 是命题公式，那么是命题公式，那么是命题公式是命题公式v3 3、如果、如果 、 是命题公式，那么（是命题公式，那么（），），（ ）、（）、（）和（）和（）也是命）也是命题公式；题公式；v4 4、只有符合以上、只有符合以上3 3条的才是命题公式。条的才是命题公式。1.1命题公式命题公式 pqr，p q，pq r 这些都不是命题公式。这些都不是命题公式。v 从逻辑的角度看，命题公式是构造出从逻辑的角度看，命题公式是构造出来的，具体命题只是命题公式的例示，来的，具体命题只是命题公式的例示，即命题公式的一个
4、特例。即命题公式的一个特例。 如下具体如下具体命题都是命题公式命题都是命题公式“（pqpq）r r”的例的例示：示：v 如果加温到了一定限度且加压到一定限如果加温到了一定限度且加压到一定限度，那么空气可以液化。度，那么空气可以液化。v 如果考试合格并且体检合格，那么就可如果考试合格并且体检合格，那么就可以上大学。以上大学。（12007/1312007/13）1.21.2命题公式与真值函项命题公式与真值函项v 命题公式就相当于一个函数式，命题公式就相当于一个函数式，公式的值由变元的值唯一确定。公式的值由变元的值唯一确定。v 命题公式是一个以真假为定义命题公式是一个以真假为定义域，并且也以真假为值
5、域的特殊函域，并且也以真假为值域的特殊函数。真假是命题的数。真假是命题的逻辑值逻辑值，简称真，简称真值。因此，命题公式被称作值。因此，命题公式被称作真值函真值函项项。v 我们可以看到，给定个命题变元，则有我们可以看到，给定个命题变元，则有n n种真种真假取值，然后构成假取值，然后构成2 2 n n个真值函项。这些不同的真个真值函项。这些不同的真值函项分为三大类：值函项分为三大类：v 恒真式恒真式。不论其中的变元取什么样的值，函。不论其中的变元取什么样的值，函项式的值恒为真。项式的值恒为真。v 恒假式恒假式。无论其中的变元取什么样的值，函。无论其中的变元取什么样的值，函项式的值恒为假。项式的值恒
6、为假。v 协调式协调式。既不是恒真式也不是恒假式的函项。既不是恒真式也不是恒假式的函项式。显然，协调式在其变元的某些取值组合下为真，式。显然，协调式在其变元的某些取值组合下为真，在另一些取值组合下又为假。因此。协调式的真假在另一些取值组合下又为假。因此。协调式的真假由变元的真假决定。由变元的真假决定。1.21.2命题公式与真值函项命题公式与真值函项第二节第二节 命题公式之间的逻辑等值关系命题公式之间的逻辑等值关系v2.12.1、命题公式之间的逻辑等值、命题公式之间的逻辑等值v2.22.2、几个重要的重言等值式、几个重要的重言等值式v2.32.3、命题联结词的相互定义、命题联结词的相互定义v 逻
7、辑等值的公式：表达同一真值函项的逻辑等值的公式：表达同一真值函项的公式在任何情况下都具有相同的逻辑值，公式在任何情况下都具有相同的逻辑值，我们称这些公式是逻辑等值的公式。我们称这些公式是逻辑等值的公式。v真值表：判定两个公式是否逻辑等值真值表：判定两个公式是否逻辑等值v例例1 1、判定命题公式、判定命题公式“p p q q ”与与“ (pq) (pq) ”是否逻辑等值。是否逻辑等值。v例例2 2、判定命题公式、判定命题公式“(pq) r”(pq) r”与与“p(q r)”p(q r)”是否逻辑等值。是否逻辑等值。2.1、命题公式之间的逻辑等值、命题公式之间的逻辑等值v如果两个公式是等值的，那么
8、以这两个公如果两个公式是等值的，那么以这两个公式为子公式构造一个等值式：式为子公式构造一个等值式： （pp q q ）（ (pq) (pq)）。）。v 这个等值式是恒真的，由此可推知，一这个等值式是恒真的，由此可推知，一个等值式是重言式，那么它的两个子公式个等值式是重言式，那么它的两个子公式逻辑等值。逻辑等值。v如果一个等值式是如果一个等值式是重言式重言式，那么我们就用，那么我们就用符号符号“”代替等值联结代替等值联结“”。2.1、命题公式之间的逻辑等值、命题公式之间的逻辑等值2.22.2、几个重要的重言等值式、几个重要的重言等值式v1、交换律、交换律 (pq)(q p) (pq)(q p)v
9、2、结合律、结合律 (pq )r)(p ( q r) (p q ) r)(p ( q r)v3、德摩根律、德摩根律 (pq) pq； (pq) pq。4、分配律、分配律 p(qr) (pq)(pr) p(qr) (pq) (pr)5、实质蕴涵、实质蕴涵（pq） （ p q）理解：当前件假（理解：当前件假（ p p ）而后件真（）而后件真（q q）时时pqpq恒真。恒真。6、假言易位、假言易位 （pq） （ q p )理解：充分条件假言命题的否定后件理解：充分条件假言命题的否定后件式推理式推理2.2、几个重要的重言等值式、几个重要的重言等值式7、移出律、移出律 (pq) r p(q r)理解：假
10、言前件可以分先后出现。理解：假言前件可以分先后出现。8、实质等值、实质等值 (pq) (p q) (q p)理解：等值式分解为蕴涵和逆蕴涵。理解：等值式分解为蕴涵和逆蕴涵。9、双否律、双否律 p p 理解：二值逻辑。理解：二值逻辑。10、重言律、重言律 p p p； p p p理解：思维的重复反映理解：思维的重复反映2.2、几个重要的重言等值式、几个重要的重言等值式2.32.3、命题联结词的相互定义、命题联结词的相互定义v“ ，”、“ ，”、“ ，”v例：证明用例：证明用“ ，”构造的命题公式构造的命题公式可以定义所有五种基本命题公式。可以定义所有五种基本命题公式。 如：如： （pq） （p
11、q） （pq） （p q） （pq） ？ 3.13.1、推理的有效性、推理的有效性 3.2 3.2、基本的有效推理式、基本的有效推理式第三节第三节 基本的有效推理式基本的有效推理式v（1 1） “ “如果张珊是如果张珊是中国公民并且她有选中国公民并且她有选举权举权 ，那么张珊年，那么张珊年满满1818岁。张珊是中国岁。张珊是中国公民，但是她还没满公民，但是她还没满1818岁。岁。所以所以，张珊没，张珊没有选举权。有选举权。”v（2 2）“如果张珊是如果张珊是中国公民并且她有中国公民并且她有选举权选举权 ，那么张珊，那么张珊年满年满1818岁。张珊是岁。张珊是中国公民，但是她中国公民，但是她还没
12、满还没满1818岁。张珊岁。张珊没有选举权。没有选举权。” 3.1 3.1、推理的有效性、推理的有效性（pq r）（p r） q第三节第三节 基本的有效推理式基本的有效推理式 3.1 3.1推理的有效性推理的有效性v 推理是一个包含推理是一个包含特殊词项特殊词项的命题集合，根的命题集合，根据这样的词项，我们可以区分出前提和结论。据这样的词项，我们可以区分出前提和结论。v 推理的有效性是由推理的形式决定的。它推理的有效性是由推理的形式决定的。它表现为作为前提的命题同作为结论的命题之表现为作为前提的命题同作为结论的命题之间的一种间的一种逻辑关联性逻辑关联性，这种逻辑关联取决于，这种逻辑关联取决于构
13、成推理的命题的形式结构特征。构成推理的命题的形式结构特征。(12005/14)(12005/14)v 如果如果前提真时结论必然是真的前提真时结论必然是真的，我们就称前提，我们就称前提和结论之间有和结论之间有必然的逻辑联系必然的逻辑联系。这种联系保证了。这种联系保证了推理推理决不会出现前提真而结论假决不会出现前提真而结论假的情况。因此，的情况。因此，可以由前提的真来保证结论真，由前提可靠有效可以由前提的真来保证结论真，由前提可靠有效地推演出结论的可靠。前提和结论之间具有必然地推演出结论的可靠。前提和结论之间具有必然逻辑联系的推理就是有效推理。逻辑联系的推理就是有效推理。v 如果前提和结论之间不具
14、有必然的逻辑联系，如果前提和结论之间不具有必然的逻辑联系，那么前提真时结论是否为真不能确定，即不能由那么前提真时结论是否为真不能确定，即不能由前提的真有效地推导出结论真，这样的推理就是前提的真有效地推导出结论真，这样的推理就是无效推理。无效推理。 3.1 3.1、推理的有效性、推理的有效性v推理：推理： 设命题序列设命题序列=是一个推理是一个推理形式，其中形式，其中p1,p2.pn是前提，是前提，q是结论。是结论。v 是一个有效的推理式，当且仅当，如是一个有效的推理式，当且仅当，如果果p1,p2.pn真那么真那么q一定为真。一定为真。v 是无效推理式，如果至少有一个代换是无效推理式，如果至少有
15、一个代换示例使得示例使得p1,p2.pn真但真但q假假 。v “代换示例代换示例”这里指的是命题公式。这里指的是命题公式。根据合取式的逻辑特征：根据合取式的逻辑特征：pq p（q）合取消去合取消去简记为简记为-合取引入合取引入简记为简记为+Pqpq3.2 3.2 基本的有效推理式基本的有效推理式 小张喜爱音乐，小张喜爱体育，所小张喜爱音乐，小张喜爱体育，所以，小张不但喜爱音乐，也喜爱体育。以，小张不但喜爱音乐，也喜爱体育。小张既有优点，也有缺点，小张既有优点，也有缺点，所以，小张是有优点的。所以，小张是有优点的。根据析取式的逻辑特征：根据析取式的逻辑特征：选言三段论选言三段论简记简记-p q
16、p q附加规则附加规则简记简记+ p p q或者李某是嫌疑犯，或者王某是或者李某是嫌疑犯，或者王某是嫌疑犯嫌疑犯(或者二者都是或者二者都是)；李某不是嫌疑犯；李某不是嫌疑犯；所以，王某是嫌疑犯。所以，王某是嫌疑犯。发烧可由肺炎引起；发烧可由肺炎引起；所以，发烧或者可由肺炎引所以，发烧或者可由肺炎引起或者可由感冒引起。起或者可由感冒引起。(13(13上上/12)/12)3.2 3.2 基本的有效推理式基本的有效推理式 注意与注意与-的区别：是间接的（有两个前提）而不是直接的。的区别：是间接的（有两个前提）而不是直接的。根据蕴涵式的逻辑特征：根据蕴涵式的逻辑特征：分离规则（蕴涵分离规则（蕴涵消去）
17、消去）简记简记MPpq p q逆分离规则逆分离规则简记简记MTpq q p假言三段论假言三段论简记简记HSpq p qpq p p注意注意:也是间接的（需要有前件真作条件才能消去也是间接的（需要有前件真作条件才能消去） pqqr pr根据蕴涵式的逻辑特征：根据蕴涵式的逻辑特征：二难推理二难推理(CD)(pq) (rs) pr qs (pq) (rs) q s p r破坏式二难推破坏式二难推理理(DD)第四节、推理有效性的形式证明第四节、推理有效性的形式证明v4.1 、推理有效性与命题演算、推理有效性与命题演算v4.2、 有效推理的形式证明有效推理的形式证明v4.3、 等值替换规则等值替换规则v
18、4.4 、条件证明规则条件证明规则C.Pv4.5、 间接证明规则间接证明规则RAAv4.6、 证明重言式证明重言式4.1 4.1 推理有效性与命题演算推理有效性与命题演算v 对于简单的复合命题推理，我们可以直接根据这些对于简单的复合命题推理，我们可以直接根据这些基本有基本有效式效式来判定推理是否有效。但是对于复杂的推理这样就不够了。来判定推理是否有效。但是对于复杂的推理这样就不够了。 例例1 ： 如果商品短缺日益严重（），那么物价会上涨（）；如果商品短缺日益严重（），那么物价会上涨（）； 如果存在生产过剩（），那么物价不会上涨（如果存在生产过剩（），那么物价不会上涨（ ）；）； 如果存在通货膨
19、胀威胁（），那么财政控制将继续（）；如果存在通货膨胀威胁（），那么财政控制将继续（）； 如果政府改组（），那么财政控制将取消（如果政府改组（），那么财政控制将取消（ E）；）； 或者存在生产过剩（），或者政府改组（）；或者存在生产过剩（），或者政府改组（）； 因此，商品短缺不会日益严重（因此，商品短缺不会日益严重（ A），或者不再存在通货），或者不再存在通货膨胀威胁（膨胀威胁（ D）。）。 （A B）（ C B） （ D E）（ F E） C F （ A D）v命题演算系统命题演算系统v建立命题演算系统有两种方法：建立命题演算系统有两种方法： 一是公理化方法，一是自然演绎方法。一是公理化方法，
20、一是自然演绎方法。v 公理化的命题演算系统是在形式语言基础公理化的命题演算系统是在形式语言基础上上增添公理增添公理和变形规则建构起来的。和变形规则建构起来的。v 自然演绎系统，自然演绎系统，没有公理没有公理，只有一系列推，只有一系列推理规则。它是引入特定前提为假设，根据推理规则。它是引入特定前提为假设，根据推理规则推演出结论而建构起来的演算系统。理规则推演出结论而建构起来的演算系统。4.1 4.1 推理有效性与命题演算推理有效性与命题演算4.24.2有效推理的形式证明有效推理的形式证明v 在命题演算系统中对推理有效性的证明在命题演算系统中对推理有效性的证明称作形式证明。现在给出自然演绎系统中称
21、作形式证明。现在给出自然演绎系统中形式证明的定义：形式证明的定义：v 形式证明的定义形式证明的定义 ： 一个形式证明是一一个形式证明是一个命题公式序列个命题公式序列A1,A2,An。其中任一的。其中任一的Ai（1 i n）或者是）或者是前提前提，或者是由前面的，或者是由前面的公式根据推理规则得到的。序列的最后一公式根据推理规则得到的。序列的最后一个公式个公式An恰好是恰好是结论结论。v 自然演绎系统形式证明是建立在推理规则自然演绎系统形式证明是建立在推理规则基础之上的。基础之上的。这些规则大约可分为四部分：这些规则大约可分为四部分：v一是基本推导规则；一是基本推导规则；v二是等值替换规则；二是
22、等值替换规则；v三是条件证明规则；三是条件证明规则；v四是间接证明规则。四是间接证明规则。4.24.2有效推理的形式证明有效推理的形式证明根据合取式的逻辑特征：根据合取式的逻辑特征：pq p分解式分解式简记为简记为-组合式组合式简记为简记为+Pqpq根据析取式的逻辑特征：根据析取式的逻辑特征：选言三段论选言三段论简记简记- -P qp q附加式附加式简记简记+ P P q一、基本推导规则：一、基本推导规则： p根据蕴涵式的逻辑特征：根据蕴涵式的逻辑特征：分离式分离式简记简记MP（）pq p q逆分离式逆分离式简记简记MTpq q p二难推理二难推理CD(pq) (rs) pr qs假言三段论假
23、言三段论简记简记HSpq qr pr一、基本推导规则一、基本推导规则：(pq) (rs) q s p r破坏式二难推理破坏式二难推理DD显然，也有假言联言的构成式和破坏式推理。显然，也有假言联言的构成式和破坏式推理。v例例1 1 如果商品短缺日益严重，那么物价会上涨。如果商品短缺日益严重，那么物价会上涨。如果存在生产过剩，那么物价不会上涨。如果存在通如果存在生产过剩，那么物价不会上涨。如果存在通货膨胀威胁，那么财政控制将继续。如果政府改组，货膨胀威胁，那么财政控制将继续。如果政府改组，那么财政控制将取消。或者存在生产过剩，或者政府那么财政控制将取消。或者存在生产过剩，或者政府改组。因此，商品短
24、缺不会日益严重，或者不再存在改组。因此，商品短缺不会日益严重，或者不再存在通货膨胀威胁。通货膨胀威胁。v 首先将该推理形式化，在此基础上建立该推理有效首先将该推理形式化，在此基础上建立该推理有效性的形式证明。性的形式证明。v 解：设解：设“商品短缺日益严重商品短缺日益严重”为为A A，“物价会上涨物价会上涨”为为B B，“存在生产过剩存在生产过剩”为为C C，“存在通货膨胀威胁存在通货膨胀威胁”为为D D，“财政控制将继续财政控制将继续”为为E E，“政府改组政府改组”为为F F。 （A B）（ C B） （ D E）（ F E） C F （ A D） （A BA B）（ C C B B） （
25、 D ED E）（ F F E E） (C F) (C F) （ AA D D） A B P C B P D E P F E P C F P / A D（C B）（F E） + B E CD（A B）（D E） + A D DD 要善于观察要善于观察，从，从结论去倒推：看到结论去倒推：看到 A和和 D可从对可从对 和和 的的否定推出，而否定否定推出，而否定 和和 必须必须有有 B 和和 E ，其，其又可从对和的肯定得出，再看到又可从对和的肯定得出，再看到 C F刚好是刚好是 和和的前提，可以构成二难推理的前提，可以构成二难推理CD，推出，推出 又是对又是对 和和 的后件的否定，可以构成破坏式二
26、难推理的后件的否定，可以构成破坏式二难推理DD，推出，推出 A D 。v 我们还看到，整个形式证明的内容可分为我们还看到，整个形式证明的内容可分为三部分（三部分（三列三列）：）：v 第一部分是第一部分是序号序号，它既标示了命题公式出，它既标示了命题公式出现的顺序，这些序号同时又是在它后面出现现的顺序，这些序号同时又是在它后面出现的那个公式的代表。的那个公式的代表。v 第二部分是若干个第二部分是若干个命题公式命题公式，它们或者是，它们或者是前提，或者是由前面的公式根据推理规则得前提，或者是由前面的公式根据推理规则得到的。到的。v 第三部分则是一些第三部分则是一些根据根据，它说明每个命题，它说明每
27、个命题公式在为什么在形式证明中出现。形式证明公式在为什么在形式证明中出现。形式证明的这三个构成部分缺一不可。的这三个构成部分缺一不可。4.34.3等值替换规则等值替换规则v例例: (AB)C AC v运用八条基本规则不能建立有关这个推运用八条基本规则不能建立有关这个推理的形式证明。理的形式证明。v等值替换规则实际上就是引入一些逻辑等等值替换规则实际上就是引入一些逻辑等值式作为推理规则，并规定在形式证明中，值式作为推理规则，并规定在形式证明中，等值式两边的公式可以相互替换使用。等值式两边的公式可以相互替换使用。二、置换规则二、置换规则交换律交换律(Com)： 结合律结合律(Ass)： 德德摩根律
28、摩根律(Dem)： (pq) (pq) (pq) (pq)pq qp pq qpp(qr) (pq)rp(qr) (pq)r分配律分配律 (Dist):实质蕴涵律实质蕴涵律 (Impl) ：假言易位律（假言易位律（Tran):p(qr) (pq)(pr) ； p(qr) (pq)(pr)（pq） （ pq）（p q） （ q p）移出律移出律(Exp)：实质等值实质等值(Eq)： （， ）双否律双否律(DN)：（）重言律重言律(Taut)：pq r p (qr)pq (pq)(qp)p pp (p p)p (p p)v(AB)C ACv证：证： (AB)C P ACv (AB) C Implv
29、 ( A B) C DeMv ( A C) ( B C ) Distv A C -v A C Impl课堂练习课堂练习v一、运用真值表方法或命题演算形式证明方一、运用真值表方法或命题演算形式证明方法法, ,判定下列命题是不是等值命题。判定下列命题是不是等值命题。 vl l如果这匹马儿不吃饱草如果这匹马儿不吃饱草, ,那么这匹马儿不那么这匹马儿不能跑。能跑。v2 2或者这匹马儿吃饱草或者这匹马儿吃饱草, ,或者这匹马儿不能或者这匹马儿不能跑。跑。v3 3既要这匹马儿跑既要这匹马儿跑, ,又要这匹马儿不吃饱草，又要这匹马儿不吃饱草，这是办不到的。这是办不到的。(12007/14)(12007/14
30、)4.4 4.4 证明的方法证明的方法v一一 推理有效性的形式证明推理有效性的形式证明v( (一一) )条件证明规则条件证明规则v有了基本推导规则和等值替换规则还不足以为所有有了基本推导规则和等值替换规则还不足以为所有有效的复杂推理建立形式证明，例如下列推理有效的复杂推理建立形式证明，例如下列推理vAA（BCBC） （ABAB）（ACAC） 这个推理是有效的，但要证明其有效性还需要引入这个推理是有效的，但要证明其有效性还需要引入新的推理规则。因此我们引入新的推理规则。因此我们引入条件证明规则条件证明规则C.PC.P。引。引入这条规则还有一个作用，即可以简化证明过程。入这条规则还有一个作用，即可
31、以简化证明过程。v条件证明规则的根据：条件证明规则的根据：v有效推理的逻辑特征是：有效推理的逻辑特征是：前提真时结论必真前提真时结论必真，不，不存在有使其前提真而结论假的例示。如果我们以有效存在有使其前提真而结论假的例示。如果我们以有效推理的推理的前提的合取为前件前提的合取为前件，结论为后件结论为后件构造一个蕴涵构造一个蕴涵式，那么这个蕴涵式就不可能前件真而后件假。式，那么这个蕴涵式就不可能前件真而后件假。v 相反，如果推理式不是有效的，那么存在这样的相反，如果推理式不是有效的，那么存在这样的例示使得该例示使得该推理式前提真而结论假推理式前提真而结论假。因此，与这个推。因此，与这个推理式相应的
32、蕴涵式就不可能是重言式。理式相应的蕴涵式就不可能是重言式。4.4 4.4 证明的方法证明的方法 由此我们看到，如果用一个推理式前提的合取为由此我们看到，如果用一个推理式前提的合取为前件，结论为后件构造一个蕴涵式，那么这个推理前件，结论为后件构造一个蕴涵式，那么这个推理式与该蕴涵式之间存在这样一种等价关系：如果推式与该蕴涵式之间存在这样一种等价关系：如果推理式是有效的，那么蕴涵式是重言式；如果推理式理式是有效的，那么蕴涵式是重言式；如果推理式不是有效的，那么蕴涵式就不是重言式。不是有效的，那么蕴涵式就不是重言式。 v等值替换规则中的移出律等值替换规则中的移出律(Exp)指出，如下两个蕴指出，如下
33、两个蕴涵式是逻辑等值的：涵式是逻辑等值的：v (pq)r) (p(qr)v两个蕴涵式分别对应于如下推理式：两个蕴涵式分别对应于如下推理式：4.4 4.4 证明的方法证明的方法 (pq)r 对应于对应于 p(qr) 对应于对应于 p p q qr r 这两个推理式的区别在于：命题公式这两个推理式的区别在于：命题公式“q”在左边的推理式在左边的推理式中是中是前提前提，而在右边的推理式中是，而在右边的推理式中是结论结论的构成部分。就是说，的构成部分。就是说，右边的推理式比左边的少了一个前提右边的推理式比左边的少了一个前提“q”，并且它们有不同，并且它们有不同的结论：左边推理式的结论是的结论：左边推理
34、式的结论是“r”，右边推理式的则是，右边推理式的则是“qr”，“q”从前提中消去而变成了结论的前件。从前提中消去而变成了结论的前件。4.4 4.4 证明的方法证明的方法v 由于两个蕴涵式是逻辑等值的，即如果一个是重言由于两个蕴涵式是逻辑等值的，即如果一个是重言式，另一个也必是；一个不是重言式，另一个也必不式，另一个也必是；一个不是重言式，另一个也必不是。因此这两个推理式是等价的：如果一个推理式有是。因此这两个推理式是等价的：如果一个推理式有效，另一个必有效；一个是无效的，另一个也必无效。效，另一个必有效；一个是无效的，另一个也必无效。v条件证明规则条件证明规则C.P （）v pv v v qv
35、 pq4.4 4.4 证明的方法证明的方法v例例1 A（BC） （AB）（AC） 证明：证明： A（BC） Pv （AB）C Expv （BA）C Comv B（AC） Expv ABv A（AC） HSv （AA）C Expv AC Tautv （AB）（AC） - CP4.4 4.4 证明的方法证明的方法v由上例中我们看到，第步是将结论的前提作由上例中我们看到，第步是将结论的前提作为一个附加前提引入了形式证明中，到第步推出为一个附加前提引入了形式证明中，到第步推出了结论的后件，于是就了结论的后件，于是就运用运用CPCP规则消去这个附加规则消去这个附加前提前提，即以为前件为后件而得到，恰好是
36、，即以为前件为后件而得到，恰好是结论。结论。v我们在引入附加前提的同时就用线段标明了这个我们在引入附加前提的同时就用线段标明了这个附加前提的辖域。在辖域中出现的、和这几个附加前提的辖域。在辖域中出现的、和这几个公式依赖于和这两个前提。而公式出现在附加公式依赖于和这两个前提。而公式出现在附加前提的辖域之外，因为前提的辖域之外，因为CP规则的运用已经将从规则的运用已经将从前提中消去，就只依赖于前提了。前提中消去，就只依赖于前提了。4.4 4.4 证明的方法证明的方法v因此，标明辖域在条件证明规则因此，标明辖域在条件证明规则CP的的运用中有很重要的意义。我们规定，运用中有很重要的意义。我们规定，凡引
37、入凡引入附加前提附加前提必须标明该前提的辖域。而辖域没必须标明该前提的辖域。而辖域没有封闭，证明就不能结束，因为这时推演出有封闭，证明就不能结束，因为这时推演出的公式还依赖于附加前提，即依赖于给定前的公式还依赖于附加前提，即依赖于给定前提之外的东西。如果辖域已经封闭，那么在提之外的东西。如果辖域已经封闭，那么在辖域中出现的公式不能再作为推演的根据，辖域中出现的公式不能再作为推演的根据，因为我们必须保证推出的结论只依赖于给定因为我们必须保证推出的结论只依赖于给定的前提，不需要除前提外的其它东西。的前提，不需要除前提外的其它东西。v错误地运用条件证明规则举例：错误地运用条件证明规则举例：4.4 4
38、.4 证明的方法证明的方法v V U Pv UW Pv （ V X） W P VXv Vv U -v W -v （ V X） MTv V X DeMv VX Impl 注意：这个形式证明的错误在于注意：这个形式证明的错误在于附加前提附加前提的辖域没有的辖域没有封闭。虽然公式与结论有完全相同的形式，但它是出现封闭。虽然公式与结论有完全相同的形式，但它是出现在附加前提的辖域内，除给定前提外，它还依赖在附加前提的辖域内，除给定前提外，它还依赖于，而是原前提中没有的。于，而是原前提中没有的。（13上上/13) 这个证明只是在形式上不完善。只要修改一下，再增加这个证明只是在形式上不完善。只要修改一下，再
39、增加两步，就可以使它成为正确的形式证明两步，就可以使它成为正确的形式证明: V U P UW P （ V X） W P VX V U - W - （ V X） MT V X DeM V （V X ） - C.PC.P V （ V X） Impl （ V V）X Exp（12） VX Taut例例2 ：证明：证明 A （BD） B （C（CE）F） / AFv例例2 A （BD）v B （C（CE）F） / AF 证明：证明： A （BD） Pv B （C（CE）F） P v Av BD MPv B -v （C（CE）F MPv Cv CE +v C （CE） -CPv F MPv AF -CP
40、 观察到从观察到从A到到F有一系列中间环节，所以证明的方法就有一系列中间环节，所以证明的方法就是考虑如何把这些中间环节去掉，最后推出是考虑如何把这些中间环节去掉，最后推出AF。 (12005/15)v( (二二) )间接证明规则间接证明规则RAARAA v间接证明又叫做间接证明又叫做归谬证明归谬证明或或反证法反证法。这是一种在数学中经常用到的证明方法。这是一种在数学中经常用到的证明方法。当我们要证明某一定理时，当我们要证明某一定理时，先引入该定理先引入该定理的否定作为假设的否定作为假设，然后由这一假设，然后由这一假设推导出推导出矛盾矛盾。由于矛盾是不可能的，假设一定错。由于矛盾是不可能的，假设
41、一定错误，即该定理的否定不成立。由此就误，即该定理的否定不成立。由此就间接间接地地证明了该定理成立。证明了该定理成立。4.4 4.4 证明的方法证明的方法v间接证明规则就是根据这一思路得到的。当间接证明规则就是根据这一思路得到的。当我们为一有效推理建立形式证明时，我们为一有效推理建立形式证明时，不是直接去不是直接去证明由前提推演出结论，而是将证明由前提推演出结论，而是将结论的否定结论的否定作为作为一个补充前提引入形式证明。然后由扩充的前提一个补充前提引入形式证明。然后由扩充的前提集合推演出一个矛盾：即推演出一个形式为集合推演出一个矛盾：即推演出一个形式为“p p”的命题公式。由这个矛盾我们实际
42、上推的命题公式。由这个矛盾我们实际上推演出对这个补充前提的否定，即演出对这个补充前提的否定，即对结论的否定的对结论的否定的否定否定，再根据双否律，再根据双否律DN，就相当于推演出结论。，就相当于推演出结论。 亦即亦即反证法。反证法。4.4 4.4 证明的方法证明的方法v例例3 A（BC）v （BD）Ev DA / Ev证明：证明： A（BC） Pv （BD）E Pv DA P / E v E RAAv （BD） MTv B D DeMv D -v A -v BC MPv B -v B -v B B + E （ E） v在这个形式证明中，公式是结论在这个形式证明中，公式是结论“E”E”的否定，它
43、是作为补充前提引入证的否定，它是作为补充前提引入证明的。证明的最后一步是公式，它是一明的。证明的最后一步是公式，它是一个矛盾式，恒为假。如果推理是有效的，个矛盾式，恒为假。如果推理是有效的，前提真时结论必真。现在由于引入补充前前提真时结论必真。现在由于引入补充前提而推出了假结论，因此公式这个补提而推出了假结论，因此公式这个补充前提一定不成立。不成立即结论的否充前提一定不成立。不成立即结论的否定不成立，即定不成立，即“ E”E”，根据双否律推出，根据双否律推出“E”E”。“E”E”即结论，因此结论成立。即结论，因此结论成立。4.4 4.4 证明的方法证明的方法v 由例由例3可见，运用间接证明规则
44、就是将可见，运用间接证明规则就是将结论的结论的否定否定作为补充前提引入证明，最作为补充前提引入证明，最后推出矛盾。由此间接地证明结论成立，后推出矛盾。由此间接地证明结论成立，推理有效。推理有效。4.4 4.4 证明的方法证明的方法v( (三三) )证明重言式证明重言式 有一种命题的真是无条件的，不依赖于其它命题。有一种命题的真是无条件的，不依赖于其它命题。这样的命题就是重言式。形式证明同样适用于证明这样的命题就是重言式。形式证明同样适用于证明重言式。可以证明重言式。可以证明重言式是不需要任何前提就可以重言式是不需要任何前提就可以推演出的命题。推演出的命题。（通常的推理是协调式即可满足式，（通常
45、的推理是协调式即可满足式，即在一定前提下可以为真的复合命题）即在一定前提下可以为真的复合命题） 虽然证明重言式不需要任何前提，但建立形式证虽然证明重言式不需要任何前提，但建立形式证明需要有出发点。这意味着我们只能用明需要有出发点。这意味着我们只能用条件证明条件证明或者或者间接证明间接证明的方法来证明重言式，因为只有这两种方法的方法来证明重言式，因为只有这两种方法可以引入假设前提。我们以假设前提为出发点就能建可以引入假设前提。我们以假设前提为出发点就能建立重言式的形式证明立重言式的形式证明 。4.4 4.4 证明的方法证明的方法v用用条件证明方法条件证明方法证明重言式就是证明重言式就是先引入假设
46、前提先引入假设前提，然后逐步消去所有假设前提而推演出一个公式，这然后逐步消去所有假设前提而推演出一个公式，这个命题公式就是不依赖于任何前提的重言式。个命题公式就是不依赖于任何前提的重言式。v例例4 证明证明A（BA）是重言式。）是重言式。v证明：证明： Av A B +v BA Comv BA Implv A(BA) - CP4.4 4.4 证明的方法证明的方法v例例5 证明（证明（pq）p）q是重言式是重言式v证明：证明： （pq）pv pq -v p -v q MPv （pq）p）q - CP 用用间接证明方法间接证明方法证明重言式则是将所证证明重言式则是将所证公式的否定引入作为假设前提，
47、然后推出矛公式的否定引入作为假设前提，然后推出矛盾。否定一个公式将导致逻辑矛盾，那么这盾。否定一个公式将导致逻辑矛盾，那么这个公式一定是重言式个公式一定是重言式。 例例6 证明证明A（AB）是重言式）是重言式证明：证明： （A（AB）v （ A（AB） Implv A （AB） DeMv A （ A B） DeMv （A A） B Assv A A -v二二 无效推理的证明无效推理的证明v( (一一) )用真值表证明推理的无效性用真值表证明推理的无效性v 一个推理是有效的，我们可以为其建立一一个推理是有效的，我们可以为其建立一个形式证明。形式证明运用推理规则说明，个形式证明。形式证明运用推理规
48、则说明，结论是从前提推演出来的，因此前提真时结结论是从前提推演出来的，因此前提真时结论不可能假，推理当然就是有效的。论不可能假，推理当然就是有效的。v如果推理是无效的，那么运用推理规则如果推理是无效的，那么运用推理规则不可能从前提推演出结论。所谓不可能是指：不可能从前提推演出结论。所谓不可能是指：无论怎样推演都推不出无论怎样推演都推不出结论结论形式的命题公式。形式的命题公式。形式证明并没有规定推演到多少步就必须中形式证明并没有规定推演到多少步就必须中止。因此，止。因此，对于无效推理我们面临的是一个对于无效推理我们面临的是一个无法穷尽的推演过程无法穷尽的推演过程。这意味着。这意味着形式证明方形式
49、证明方法不能证明推理是无效的法不能证明推理是无效的。 我们的命题逻辑系统不仅要能证明有效推我们的命题逻辑系统不仅要能证明有效推理，而且还应该理，而且还应该证明推理的无效性证明推理的无效性。因此，。因此，必须给出证明无效推理的方法。必须给出证明无效推理的方法。v真值表是判定推理是否有效的可靠方法。真值表是判定推理是否有效的可靠方法。一个推理是有效的，那么前提真时结论必真。一个推理是有效的，那么前提真时结论必真。在真值表上表现为无论变元被赋予什么样的在真值表上表现为无论变元被赋予什么样的值，值，作为前提的命题公式真时，作为结论的作为前提的命题公式真时，作为结论的命题公式一定是真的命题公式一定是真的
50、。如果一个推理是无效。如果一个推理是无效的，其的，其前提真时结论可真可假前提真时结论可真可假。因此只要在。因此只要在真值表上真值表上找到一组变元的赋值使得前提真而找到一组变元的赋值使得前提真而结论假，那么推理就是无效的结论假，那么推理就是无效的。(12007/15)例例7 用真值表判定下列推理是否有效。用真值表判定下列推理是否有效。vC（AB），），AC / BCv证明：给出相应的真值表：证明：给出相应的真值表：vA B C AB C（AB） AC BCvT T T T T T T * T T F T T T FvT F T F F T TvT F F F T T TvF T T F F T
