3 联结词与真值表

There is no royal road to logic, and really valuable ideas can only be had at the price of close attention.Charles Peirce, How to Make Our Ideas Clear, 1878

命题逻辑(propositional logic),也称语句逻辑(sentential logic),是从联结词和复合句的角度讨论逻辑蕴涵、可演绎性和一致性。这意味着我们会忽略很多常见的东西,如主词、谓词和量词等。命题和语句其实还是有区别的,但我们在这门课里暂时不加区分(技术用语除外)。用「命题」方便时用「命题」,用「语句」或「句子」方便时用「语句」或「句子」。

论说的前提和结论都由陈述句(declarative sentence)构成,我们的信念也由陈述句表达。那么,什么是陈述句呢?直观上我们似乎都知道陈述句是什么样的句子,但要对这个问题提供一个严格而准确的答案是不容易的。目前,我们可以满足于一个简单化的答案:对于任何一个语句 \(\varphi\),如果我们问「\(\varphi\) 是真的吗?\(\varphi\) 是假的吗?」是有意义的,那么我们就称 \(\varphi\) 为陈述句。(Hodges, 1977)针对本书讨论的句子,我们有两个预设:

  1. 我们讨论的句子只限于陈述句。
  2. 我们讨论的陈述句只限于非真即假的陈述句。

如果一个句子是真的,我们也说该句子的真值是真;如果一个句子是假的,我们也说该句子的真值是假。真和假统称为真值(truth-values)。用这个概念来重复上面的第一个预设,那就是:我们讨论的语句都有真值;用它来重复上面第二个预设,那就是:我们讨论的真值只有两个。

学过「逻辑导论」的读者,对本章大部分内容是熟悉的,这里权当复习一次。不过,我们并不假设读者学过「逻辑导论」。本章的内容是自足的,无须预设任何大学课程。当然,没学过「逻辑导论」的读者,可能要比学过「逻辑导论」的读者多花些时间或气力。

3.1 联结词与复合句

3.1.1 联结词

命题联结词(propositional connectives),也作语句联结词(sentential connectives),又称命题算子(propositional operators)语句算子(sentential operators)。直观地说,它们是带空格(序列)的表达式,使得以陈述句填入这些空格的结果总是陈述句。通常,我们将命题联结词简称为联结词

例 3.1 (下面的表达式都是联结词)

  1. \(\underline{\hspace{5em}}\),并且\(\underline{\hspace{5em}}\)
  2. (虽然)\(\underline{\hspace{5em}}\),但是\(\underline{\hspace{5em}}\)
  3. (或者)\(\underline{\hspace{5em}}\),或者\(\underline{\hspace{5em}}\)
  4. 并非\(\underline{\hspace{5em}}\)
  5. 如果\(\underline{\hspace{5em}}\),那么\(\underline{\hspace{5em}}\)
  6. 只要\(\underline{\hspace{5em}}\),(就)\(\underline{\hspace{5em}}\)
  7. \(\underline{\hspace{5em}}\),除非\(\underline{\hspace{5em}}\)
  8. 既然\(\underline{\hspace{5em}}\),(就)\(\underline{\hspace{5em}}\)
  9. 因为\(\underline{\hspace{5em}}\),所以\(\underline{\hspace{5em}}\)
  10. 之所以\(\underline{\hspace{5em}}\),是因为\(\underline{\hspace{5em}}\)
  11. 可以想像\(\underline{\hspace{5em}}\)
  12. 张三相信\(\underline{\hspace{5em}}\)
  13. 李四认为\(\underline{\hspace{5em}}\)
  14. 王五知道\(\underline{\hspace{5em}}\)
  15. 政客们喜欢说\(\underline{\hspace{5em}}\)
  16. 从平民的角度看,\(\underline{\hspace{5em}}\)

对每个自然数 \(n > 0\),如果一个联结词有 \(n\) 个空格,通常就称它是 \(n\) 元联结词。习惯上,当说到联结词时,人们更喜欢只提联结词表达式中的文字(或符号)而省略那些空格。比如,人们会说「并且」是联结词,意思是说「\(\underline{\hspace{2em}}\)并且\(\underline{\hspace{2em}}\)」是联结词;人们也会说「如果–那么」是二元联结词,意思是说「如果\(\underline{\hspace{2em}}\)那么\(\underline{\hspace{2em}}\)」是二元联结词。

有些读者可能会认为,对联结词的上述简单说法有点怪。比如,

例 3.2 (联结算子)

  1. 如果张三和李四是同学,那么\(\underline{\hspace{2em}}\)
  2. 相信太阳绕着地球转的人认为\(\underline{\hspace{2em}}\)

是带空格的表达式,并且以陈述句填入空格的结果总是陈述句。所以按上述说法,它应该是个一元联结词。可是,说这样的表达式是联结词,总觉得有点怪。读者可以用例 3.1 中的联结词造出很复杂的复合句,然后还原若干个空格,从而得到很多与例 3.2 第〇条类似的例子;读者也可以找到例 3.1 中没有的符合关于联结词的上述说法的「怪」例子,如例 3.2 第一条。

如果觉得例 3.2 的例子怪,大概是因为它们都包含陈述而我们称它们为联结,但中又似乎不该有。当然,常用的和我们将仔细讨论的联结词都是(或都对应于)自然语言中的词或词组,而且「联结词」看上去也应是指有联结功能的词组。但是,常用联结词是词或词组这个事实,不应限制我们对联结词的一般情况的讨论,而且我们也可以给联结词取其他名称,比如「联结算子」等(「联结词」的使用只是沿袭惯例)。

其实,我们讨论的联结词不过是陈述句集合上的某种函数(运算):对每个这样的 \(n\) 元函数,一旦给定有序的 \(n\) 个陈述句作为其自变量的取值,该函数的值是个唯一的陈述句,亦即由给定陈述句依次填入联结词的空格序列所得到的句子。

说到函数,读者一定熟悉自然数集合上的加法运算 +。我们知道它是二元函数:任给两个自然数 \(k\)\(n\),一定有唯一的自然数,它是 \(k\)\(n\) 和,即 \(k+n\)。如果我们把 \(k\) 固定,比如说令 \(k=3\),那么 \(3+n\) 还是不是自然数集合上的运算呢?当然还是。

再来看例 3.2 联结词的「怪」例子,它们很像 \(3+n\) 这样的函数:将二元联结词「如果–那么」的第一个元的值固定为「张三和李四是同学」,其结果就是陈述句集合上的一元函数;同理,将二元联结词「相信\(\underline{\hspace{2em}}\)的人认为\(\underline{\hspace{2em}}\)。」中的第一个元的值固定为「太阳绕着地球转」,其结果也是陈述句集合上的一元函数。

3.1.2 复合句和简单句

直观地说,复合句(compound sentence)是其中到联结词的陈述句。不是复合句的陈述句叫做简单句(simple sentence)

读者应注意(use)与(mention)的区别。了联结词的语句是复合句,仅仅到而没用到联结词的语句不是复合句。这也就是为什么我们没有说复合句是包含联结词或联结词出现的陈述句,而说复合句是其中到联结词的陈述句。比如

例 3.3 (联结算子) 张三喜欢用『但是』,但是从来不在该用的地方用。

这句话第二个「但是」是被作联结词的,第一个「但是」只是被到,没有被用作联结词。所以,「张三喜欢用『但是』」不是复合句——虽然其中有联结词「但是」,但它只是被提到而没有被用到。「用」和「提」的区别是语言哲学中讨论的问题。很多人习惯用引号表示「提」,但这种方法也不是完全没有缺陷的。我们这里大体上遵循这个习惯。当然,可以被提的不限于联结词。

说得具体一些,复合句是用联结词联结某些句子而形成的句子。由此可知,复合句中的某些部分本身也会是陈述句。例如:

例 3.4 (下面的句子都是复合句)

  1. 如果王五是赵六的表哥,那么王五比赵六年长。
  2. 虽然王五是赵六的表哥,但赵六比王五高。
  3. 王五不是赵六的表哥。(并非王五是赵六的表哥。)
  4. 有可能王五是赵六的表哥。
  5. 王五不相信赵六是他的表哥。
  6. 假如王五只有六岁,他就会认为赵六是他的表哥。
  7. 王五认为或者赵六是洪七的表哥或者洪七是赵六的表哥。

作为复合句的部分而出现的陈述句,既可以是简单句,也可以是复合句。下面几个句子中的每一个,都是其后的复合句的部分,但只有第一个才是简单句:

例 3.5 (简单句与复合句的出现)

  1. 赵六是洪七的表哥。
  2. 王五知道赵六是洪七的表哥。
  3. 王五不知道赵六是洪七的表哥。
  4. 李四相信王五不知道赵六是洪七的表哥。
  5. 张三认为李四相信王五不知道赵六是洪七的表哥。
  6. 牛二宣称张三认为李四相信王五不知道赵六是洪七的表哥。

3.1.3 复合句的子句

上面讨论复合句的部分时,我们虽然还没有用「子句」和「真子句」这些词,但已经涉及相应的概念了。既然复合句是用联结词联结某些句子而形成的句子,那么简单地说,那些被联结的句子就是它的真子句;相反,简单句不是用联结词联结某些句子而形成的,从而简单句没有真子句。

一个句子 \(\varphi\) 的子句既是 \(\varphi\) 的一部分又是完整的句子,但既是 \(\varphi\) 的部分又是完整句子的表达式却未必是 \(\varphi\) 的子句。比如复合句

例 3.6 张三想起李四的表哥是王五。

它的子句「李四的表哥是王五」既是例 3.6 的部分又是完整的句子。然而,表达式「张三想起李四」同样既是例 3.6 的部分又是完整的句子,但它不是例 3.6 的子句。例 3.6 是由联结词「张三想起」联结句子「李四的表哥是王五」而形成的,「张三想起李四」并不是用来合成例 3.6 的句子,所以它不应该是例 3.6 的子句。

其实,即使简单句中也可以有某个真部分,它本身能组成一个完整的句子。如简单句

例 3.7 张三在学校里学习很用功。

表达式「张三在学校里学习」既是例 3.7 的部分又是个完整的句子。显然,简单句的部分不能是它的真子句。假如说例 3.7 有子句「张三在学校里学习」,那就像是说「逻辑」这个词中包含了「四」「维」「车」「口」「耳」这些词。

一个词当然可以包含另一个词,组成「合成词」。如「逻辑课程」这个词包含了「逻辑」和「课程」两个词。通常我们可以说「逻辑」的笔划中包含了「四」「维」「车」「口」「耳」这些字的笔划,但这不同于说「逻辑」这个包含了「四」「维」「车」「口」「耳」这些词。如同「category」这个词,它并没有包含「cat」「a」「at」「ate」等词,尽管拼法(spelling)中有这些字母组合。

通常人们说,复合句是「包含其他句子的句子」,简单句是「不包含其他句子的句子」。从以上讨论可知,这只是大概的说法。易见,按这种说法,「张三在学校里学习」也不是简单句,因为它包含了「张三在学校」这样的句子。有些教科书的确把复合句定义为「包含其他句子的句子」,把简单句定义为「不包含其他句子的句子」,同样也只是大概的说法,不能太当真。自然,假如对「包含」做出足够的限制,关于复合句和简单句的这种说法也许能说通。不过那些书中并没有这种限制。

那么,应该如何把握复合句的子句和真子句呢?设 \(\varphi\)\(\psi\) 都是完整的句子。\(\psi\)\(\varphi\)真子句(proper subsentence),如果以空格替换 \(\varphi\) 中的 \(\psi\),其结果是一个联结词\(\psi\)\(\varphi\)子句(subsentence)如果 \(\psi\)\(\varphi\) 的真子句或者 \(\psi=\varphi\). 直观地,说 \(\psi\)\(\varphi\) 的真子句,是说 \(\psi\)\(\varphi\) 的一个(真)部分,并且如果将 \(\varphi\) 中的这一部分换成任何其他句子,其结果都还是完整的句子。

根据这个说明,「张三想起李四」不是例 3.6 的真子句。因为「张三和李四是好朋友」是句子,用它替换例 3.6 中的「张三想起李四」,其结果是「张三和李四是好朋友的表哥是王五」,这结果显然不是一个句子。显然,「张三想起李四」也不是例 3.6 的子句。

类似地,将「张三和李四是好朋友」替换例 3.7 中的「张三在学校里学习」,其结果是「张三和李四是好朋友很用功」,这个结果也不是句子。所以「张三在学校里学习」不是例 3.7 的(真)子句。

复合句的(真)子句当然是它的(真)部分。如果觉得真子句从「部分」的角度容易理解,那么请记住:它是该复合句的一部分,并在句中被某联结词联结。

3.1.4 主联结词和直接子句

3.1.4.1 主联结词

借助直观,我们可以明白什么是一个联结词在某复合句中的一个出现。简单地说,它是指该联结词及其在句中所处的一个位置。这个概念显然可以精确化。比如,我们可以用自然数表示句子中的位置。余下的就简单了。一个联结词在同一复合句中可以出现多次。下面例句中都有同一联结词多次岀现的情况:

例 3.8 (联结词的出现) 李四知道有理数和自然数一样多,然而他不知道实数比有理数多。
例 3.9 (联结词的出现) 如果张三听说过无穷集是分大小的,那么他大概也听说过实数比有理数多;但是如果他没听说过无穷集有可数无穷集和不可数无穷集,那么他很可能认为无穷是不可比的。

一个联结词被称为一个复合句的主联结词(major connective, main operator),如果它在该句中的某个出现不是在该句子的任何真子句中,并且它不是由多元联结词经用句子(或联结词)填入其空格得到的联结词。如果我们把一个复合句看作是由简单句经联结词一步步构造起来的,那么,在构造过程的最后一步,我们使用的联结词就是这个复合句的主联结词。比如「李四知道有理数和自然数一样多」「李四不知道实数比有理数多」是例 3.8 复合句的真子句,并且例 3.8 的其他真子句都出现在这两个句中;然而,例 3.8 中的「然而」(唯一一次出现)却没有出现在这些句子中。所以,「然而」是例 3.8 的主联结词。类似地,「但是」是例 3.9 的主联结词。

例 3.10 (联结词的出现) 王五相信,如果老师能给出足够的理由说明实数比有理数多,他也会相信实数比有理数多。
例 3.11 (联结词的出现) 如果实数比自然数多,那么,如果有理数又和自然数一样多,则实数就比有理数多。

3.10 中「王五相信」的第一个出现决定了它是该句的主联结词,而第二个出现(「他相信」)与它是主联结词无关。类似地,例 3.11中「如果」的第一个出现决定了它是该句的主联结词,而其第二个出现与它是主联结词无关。

不难看出,对每一个(没有歧义的)复合句,都有唯一的联结词,它在该句中的某个出现使得它成为该句的主联结词。一个句子中的主联结词决定了该句子的基本(命题)结构或基本(命题)形式

3.1.4.2 直接子句

不仅同一个联结词在一个复合句中可以出现多次,同一个句子也可以作为子句在一个复合句中出现多次。易见,我们可以精确地刻画任何表达式(联结词、子句、词和字等)在一复合句中的出现。

例 3.12 (直接子句) 实数比有理数多,但是张三不相信实数比有理数多。

\(\psi\)\(\varphi\) 的真子句。 \(\psi\) 被称为 \(\varphi\) 的一个直接子句(direct subsentence),如果 \(\psi\)\(\varphi\) 中的某个出现不是在 \(\varphi\) 的任何其他真子句中的出现。简单地说,\(\varphi\) 的直接子句就是 \(\varphi\) 的主联结词联结的那些子句。像例 3.12 中的「实数比有理数多」,它是例句的真子句,而且它的第一个(左侧的)出现不在例句的任何其他真子句中,所以它是例 3.12 的一个直接子句。类似地,「张三不相信实数比有理数多」也是例 3.12 的一个直接子句。注意:「实数比有理数多」之所以是例句的直接子句,是因为它的第一个出现;它的第二个出现(右侧的)是在例句的真子句「张三不相信实数比有理数多」中的出现,与它是例句的直接子句无关。

自然,如果一个复合句的直接子句本身也是复合句,它也会有自己的主联结词和自己的直接子句。

例 3.13 (直接子句) 李四相信实数比有理数多,但是张三不相信实数比有理数多。

「李四相信实数比有理数多」「张三不相信实数比有理数多」都是例 3.13 的直接子句,而「实数比有理数多」不再是例 3.13 的直接子句。显然,例 3.13 的上述直接子句都是复合句,它们又都有自己的直接子句:「实数比有理数多」是「李四相信实数比有理数多」的直接子句,而「张三相信实数比有理数多」是「张三不相信实数比有理数多」的直接子句。

复合句的主联结词和直接子句密切相关。一个复合句的主联结词,虽然可能在该复合句中出现多次,但使它成为该句主联结词的那个出现,一定联结了该句的全部直接子句。

3.2 真值、非真值函数联结词

3.2.1 真值函数联结词

对任意的联结词,如果以它为主联结词的复合句的真值完全由该句的直接子句的真值来决定,那么这个联结词就是真值函数联结词(truth-functional connective)

例 3.14 (真值函数联结词)

  1. 并非\(\underline{\hspace{2em}}\)
  2. 如果\(\underline{\hspace{2em}}\),那么\(\underline{\hspace{2em}}\)
  3. \(\underline{\hspace{2em}}\)并且\(\underline{\hspace{2em}}\)
  4. (或者)\(\underline{\hspace{2em}}\)或者\(\underline{\hspace{2em}}\)
  5. \(\underline{\hspace{2em}}\)当且仅当\(\underline{\hspace{2em}}\)
  6. it is not the case that \(\underline{\hspace{2em}}\)
  7. if \(\underline{\hspace{2em}}\), then \(\underline{\hspace{2em}}\)
  8. \(\underline{\hspace{2em}}\) and \(\underline{\hspace{2em}}\)
  9. (either)\(\underline{\hspace{2em}}\) or \(\underline{\hspace{2em}}\)
  10. \(\underline{\hspace{2em}}\) if and onIy if \(\underline{\hspace{2em}}\)

3.2.2 非真值函数联结词

如果一个联结词不是真值函数联结词,它就是一个非真值函数联结词(non-truth-functional connective);换言之,如果以它为主联结词的复合句的真值不能完全由该复合句的直接子句的真值来决定,那么它就是一个非真值函数联结词。

例 3.15 (非真值函数联结词)

  1. 因为\(\underline{\hspace{2em}}\),所以\(\underline{\hspace{2em}}\)
  2. 之所以\(\underline{\hspace{2em}}\),是因为\(\underline{\hspace{2em}}\)
  3. 可以想像\(\underline{\hspace{2em}}\)
  4. 张三相信\(\underline{\hspace{2em}}\)
  5. 李四认为\(\underline{\hspace{2em}}\)
  6. 王五知道\(\underline{\hspace{2em}}\)
  7. 政客们喜欢说\(\underline{\hspace{2em}}\)
  8. 从平民的角度看,\(\underline{\hspace{2em}}\)

要说明一个联结词不是真值函数联结词,可以去构造以它为主联结词且满足下列条件的两个复合句:

  1. 这两个复合句的真值不同;
  2. 这两个复合句中对应的直接子句的真值相同。

例 3.16 「张三相信」不是真值函数联结词:

  1. 张三相信地球围绕着太阳转。
  2. 张三相信 \(2+2=4\)

假定张三生活在天文学极不普及而简单的加减法已普及的年代或地区。那么,他会相信 \(2+2=4\) 而不相信地球围绕着太阳转,也就是说,上述两个复合句一真一假。但是,这两个复合句中对应的直接子句(「地球围绕着太阳转」和「\(2+2=4\)」)却具有相同的真值(都是真的)。

为什么这样做就可以说明给定的联结词不是真值函数联结词?要说明给定的联结词不是真值函数联结词,只需要说明它不满足真值函数联结词的定义。在例 2.15 中,两个复合句中对应的直接子句(「地球围绕着太阳转」和「\(2+2=4\)」)真值相同,但经「张三相信」联结而分别形成的两个复合句却有不同的真值。这说明两个复合句的直接子句的真值不能完全决定复合句的真值,那么根据真值函数联结词的定义,联结直接子句而构成复合句的主联结词「张三相信」就不是真值函数联结词。

例 3.17 「自从\(\underline{\hspace{2em}}\)\(\underline{\hspace{2em}}\)」不是真值函数联结词:

  1. 自从爱因斯坦提出相对论,科学家对宇宙的看法较牛顿时期有很大变化。
  2. 自从刘邦打败了项羽,很多中国人喜欢看足球。

凭借直观,我们会认为例 3.17 第一个句子是真的,而第二个句子是假的;但是这两个复合句的所有直接子句都是真的。这就是说,以「自从」为主联结词的复合句的真值不能完全由其直接子句的真值决定。所以,「自从」不是真值函数联结词。

从现在起,除非有特别说明,我们讨论的联结词将只限于真值函数联结词。

3.2.3 常用的真值函数联结词符号

参见上表,我们用下述符号表示本课程讨论的真值函数联结词:

  1. \(\neg\):否定,并非\(\underline{\hspace{2em}}\)
  2. \(\wedge\):合取 ,并且\(\underline{\hspace{2em}}\)
  3. \(\vee\):析取, \(\underline{\hspace{2em}}\)或者\(\underline{\hspace{2em}}\)
  4. \(\rightarrow\):蕴涵 ,如果\(\underline{\hspace{2em}}\)那么\(\underline{\hspace{2em}}\)
  5. \(\leftrightarrow\):等值 , \(\underline{\hspace{2em}}\)当且仅当\(\underline{\hspace{2em}}\)

\(\neg\) 为否定号,称主联结词为 \(\neg\) 的复合句为否定句;其余类推。

文科学生可能不太熟悉「当且仅当」这个词,它相当于「等价于」。「\(\varphi\) 当且仅当 \(\psi\) 」的意思是:如果 \(\varphi\) 那么 \(\psi\) 并且如果 \(\psi\) 那么 \(\varphi\)。「\(\varphi\) if and only if \(\psi\)」的意思就是:\(\varphi\) if \(\psi\),and \(\varphi\) only if \(\psi\)(其中「\(\varphi\) only if \(\psi\)」和「if \(\varphi\) then \(\psi\)」意思相同)。

3.3 符号化

无论读者是否对命题逻辑层次的符号化(symbolization)已有了解,这种符号化毕竟是相当简单的,所以我们只简略地说说。

3.3.1 联结词对应符号

学习符号化的目的之一,就是要通过分析自然语言的句子,把握这些句子的逻辑结构。在这一学习过程中,学生需要通过自己的练习,逐步弄清哪些联结词与哪些联结词的意义相当或相近。下面这个列表当然是不完全的。其实,完全的列表也不是必要的。

  1. \(\neg\) :并非,并不,不,……
  2. \(\wedge\) : 并且,但是,可是,然而,且,而,却,不是–而是,……
  3. \(\vee\):或,或者,或者–或者,要么–要么,不是–就是,(除非),……
  4. \(\rightarrow\):如果,如果–那么,若–则,只要,一旦,(否则,除非),……
  5. \(\leftrightarrow\):当且仅当,(等价于),……

3.3.2 符号化的基本操作过程

相对于真值函数联结词简单的句子,是指那些没有主联结词或没有使用真值函数联结词做主联结词的句子,包括简单句、以非真值函数联结词为主联结词的句子以及由(隐蔽的)量词决定了其基本结构的句子等等。(量词将在谓词逻辑章节中讨论。关于相对于真值函数联结词简单的句子,上述说明只是一种直观的说法,并不是定义。)由于我们现在不讨论非真值函数联结词和量词等的符号化,遇到有这种结构的句子就只能和简单句一样处理。从现在起,除非有特别说明,简单句都指相对于真值函数联结词简单的句子。

以下是命题逻辑符号化的基本步骤:

  1. 确认所有简单的句子及其否定。
  2. 如果需要,对句子进行复述,即在不改变句子意思的前提下对句子表面结构做小的改动。
  3. 用小写的文字母代换简单句,或者用给出的「辞典」中的字母来代换它们。(用不同的字母代换不同的简单句。如果有同一个简单句的多次出现,确保用相同字母代换相同简单句的所有出现。)
  4. 确认所有的联结词,并「由内至外」或「由外至内」逐步把句子符号化。

这里用「辞典」这个词只是为了方便。这里的辞典解释的不是词,而是一个个命题变号。倘若用「原子句典」倒是可以避免误会,但这个词太怪了,只好还是用「辞典」。

例 3.18 如果张三或李四惹怒了王五,那么,赵六不会替王五打抱不平而洪七会高兴地大吃大喝。

解剖层次嵌套,例 3.18 的「辞典」或「原子句典(集)」为:

  1. \(p\):张三惹怒了王五。
  2. \(q\):李四惹怒了王五。
  3. \(r\):赵六会替王五打抱不平。
  4. \(s\):洪七会高兴地大吃大喝。

例 3.19 3.18 由内至外符号化:

  1. 如果 \(p\) 或者 \(q\),那么,\(\neg r\)\(s\).
  2. 如果 \((p \lor q)\),那么 \((\neg r \land s)\).
  3. \((p \lor q) \rightarrow (\neg r \land s)\).

3.18 由外至内符号化:

  1. 如果 \(p\) 或者 \(q\),那么,\(\neg r\)\(s\).
  2. \(p\) 或者 \(q\)),\(\rightarrow\)\(\neg r\)\(s\)).
  3. \((p \lor q) \rightarrow (\neg r \land s)\)

自然语言由于种种因素在表达上不很「规范」,有些表达式(词的组合)单独拿出来不是句子,但可以被复述成句子。比如例 3.3 中有「从来不在该用的地方用」这一表达式。如果把它从例 3.3 中抽岀来看,并不能说它是完整的句子;但我们知道,它可以被复述成「张三从来不在该用『但是』的地方用『但是』。」例 3.3 经这样复述后可以表达为:

张三喜欢用「但是」,但是张三从来 不在该用「但是」的地方用「但是」。

虽然略显繁琐,但只是修辞问题而不是语法问题,还能忍受。

3.3.3 几种特殊情况

有些复合句的字面结构甚至更难处理。如

例 3.20 张三只有加倍努力学习,才能通过下次考试。

句中的「只有\(\underline{\hspace{2em}}\)才(有)\(\underline{\hspace{2em}}\)」表达了某种条件句的结构,应该是个联结词。(「只有–才」在很多情况下是量词,这将在 §13.6(P.234)中讨论。)如果我们在「只有\(\underline{\hspace{2em}}\)才(有)\(\underline{\hspace{2em}}\)」的空格中填入陈述句,得到的结果有时很怪,比如:「只有张三加倍努力,才有张三能通过下次考试」。这就需要分析句子的各部分及其关系,甚至需要用文字上与原句相差较大的复述来显示句子的结构。像例 3.20 是说「张三加倍努力学习」是「张三能通过下次考试」的必要条件,所以它可以复述成「如果张三不加倍努力学习,他就不能通过下次考试」。当然,也可以复述成「如果张三能通过下次考试,那么他加倍努力学习了」。

「只有 \(p\) 才(有)\(q\)」的符号化结果是「\(\neg p \rightarrow \neg q\)」或「\(q \rightarrow p\)」。

「只有–才」作联结词时很像文的 “only if.” “\(p\) only if \(q\),”only if \(q\), \(p\)" 和 “if \(p\) then \(q\)” 意思相同。

另一个常见而又有点特殊的联结词是「除非」。比如

例 3.21 李四下午不会去听讲座,除非他学过数理逻辑。

3.21 可以复述成:

  1. 如果李四没有学过数理逻辑,他下午不会去听讲座。(\(\neg q \rightarrow \neg p;~~ p \rightarrow q\)
  2. 或者李四下午不会去听讲座,或者他学过数理逻辑。(\(\neg p \lor q\)

所以,「除非」的符号化可以和「或者」一样,也可以和「如果不」一样。这就是说,

\(p\) 除非 \(q\)」的符号化结果是「\(p \lor q\)」或「\(\neg q \rightarrow p\)」。

3.21 本质与「今天要军训,除非今天下雨」的结构相同,但它是「\(\neg p\) 除非 \(q\)」的结构。所以,不应死记「\(p\) 除非 \(q\)」的符号化结果,而应理解并掌握「\(\underline{\hspace{1.5em}}\)除非\(\underline{\hspace{1.5em}}\)」这种句子结构的复述方式。「除非」大致与文中的联结词「unless」相仿。

3.3.4 论说的符号化

因为论说由句子组成,所以,只要明白如何将论说中各个句子符号化,那么整个论说的符号化应是水到渠成的事。不过,有一点要注意:对同一个论说中所有句子的符号化,都必须根据同一个「辞典」来进行。

例 3.22 将下列论说符号化:

  1. 如果蓷蒂是企鹅,那么蓷蒂是鸟。\(\hspace{2em}\) \(p \rightarrow q\)
  2. 蓷蒂不是鸟。\(\hspace{2em}\) \(\neg q\)
  3. \(\therefore\) 蓷蒂不是企鹅。\(\hspace{2em}\) \(\therefore \neg p\)

3.3.5 形式

我们说过一个论说的好坏在于它的形式的好坏,但对论说的形式是什么却说的很少。事实上,要想确切地说出论说的形式甚至命题的形式是什么,并不是一件容易的事。这里我们可以说一点点。

在我们把一个论说符号化之后,虽然使用的符号在符号化过程中被赋予了意义,但我们很容易赋予它们别的意义(联结词和 “\(\therefore\)” 除外),甚至很自然地把例 3.22 的符号化结果读作「如果 \(p\) 那么 \(q\),…」,而不读作「如果蓷蒂是企鹅那么蓷蒂是鸟,……」。这就是说,我们可以把例 3.22 中的 \(p\)\(q\) 看作能取不同句子为值的变元,而当我们这样做时,我们就是把例 3.22 右列看作例 3.22 左列的形式。通常,人们把一个论说的符号化结果称作该论说的形式(form),而事实上符号化也常被称作形式化(formalization)

在把命题或论说的符号化结果看作它们的形式时,我们要注意几点:

  1. 虽然此时 \(p\)\(q\) 等符号是可以取任意句子为值的变元,但 \(\neg\), \(\land\), \(\lor\), \(\rightarrow\), \(\leftrightarrow\) 却不是变元,他们固定地表示否定、合取、析取等联结词。
  2. 这里说的形式,不是根据自然语言句子中的字的排列,直接用符号替换组成句子和联结词的「字段」而得到的。这里又有两层意思:
  • 句子的形式不是通过机械的「字段/符号」替换就能得到的。(符号化过程中时常要做的复述已经说明了这一点。)
  • 符号化依赖于某种逻辑分析的理论

上述第二层意思需要一点解释。我们现在使用的逻辑分析理论是非常简单的,它只有表示简单句的符号和一些表示真值函数联结词的符号,而且所谓简单句是指相对于真值函数联结词简单的句子。基于这样一个简单理论,所谓形式当然是粗线条的。比如,按本章现有理论对下面的句子做符号化,

  1. 所有的企鹅都是不会飞的鸟。
  2. 张三相信,如果所有的企鹅都是不会飞的鸟,那么他的家乡就有不会飞的鸟。

其结果只是两个表示简单句的符号,但是这些句子的内部结构暗示着某种形式上的不同和联系。在§13.4.1(P.225)等章节中,我们会使用一个更丰富的逻辑分析理论来讨论命题与论说的形式问题。

3.3.6 形式化的波兰学派记法

如果一个形式语言的联结词用的是波兰学派记法(见表 2.0),那么这个语言就不需要括号。波兰学派记法中一元联结词 \(N\) 的使用规则和我们的 \(\neg\) 一样,但二元联结词 \(K, A, C, E\) 的使用规则不同,它们都位于由它们联结的两个直接子公式的左侧。具体地说,当我们使用波兰学派记法时,公式的形成规则是下面这几条(对比 §2.3.0(P.79)中的形成规则和例子):

  1. 所有的命题变号都是公式;
  2. 如果 \(\varphi\) 是公式,那么 \(N \varphi\) 也是公式;
  3. 如果 \(\varphi\)\(\psi\) 是公式,那么 \(K\varphi\psi, A\varphi\psi, C\varphi\psi, E\varphi\psi\) 也是公式;
  4. 只有这些是公式。

例 3.23 下面编号的都是公式而无编号的则都不是公式:

  1. \(p_{156}\)
  2. \(KNp_{75}p_{21}\)
  3. \(Cp_9Ap_{57}Ep_{23}p_{601}\)
  4. \(CCCCCp_{28}p_{28}p_{28}p_{28}p_{28}p_{28}\)
  • \(Kp_{13}\)
  • \(p_{822}Np_{822}\)
  • \(p_{69}CNp_{801}\)
  • \(Np_{28}Cp_{782}\)

3.4 命题逻辑的基本语法

3.4.1 形式语言 \(\mathscr{L_0}\)

从这一节开始,我们要使用形式语言这一概念。命题逻辑的形式语言通常由两部分组成:一是「初始符号」(primitive symbols),即无定义的符号;二是由这些符号根据一定的「形成规则」(formation rules)而形成的「公式」(formulas, formulae)。我们引入的第一个形式语言是 \(\mathscr{L}_0.\)

我们称 \(\mathscr{L}_0\) 的初始符号为 \(\mathscr{L}_0\)-符号\(\mathscr{L}_0\)-符号有三种:

  1. 命题变号:\(p_0\), \(p_1\), \(p_2, \cdots\);
  2. 联结词:\(\neg\), \(\wedge\), \(\vee\), \(\rightarrow\), \(\leftrightarrow\)\(\neg\) 为一元联结词,其余为二元联结词);
  3. 左右括号:(\(\hspace{2em}\)).

\(\mathscr{L}_0\)-符号中,联结词 \(\neg\), \(\wedge\), \(\vee\), \(\rightarrow\), \(\leftrightarrow\) 称为逻辑符号,命题变号称为非逻辑符号。命题变号也叫「命题变项」或「命题变元」。左右括号对于一个形式语言来说并不是必要的,但为了方便,我们仍把它们作为形式语言的初始符号,并称它们为「辅助符号」。

我们称 \(\mathscr{L}_0\) 的公式为 \(\mathscr{L}_0\)-公式,它们是由 \(\mathscr{L}_0\)-符号根据下列形成规则形成的符号串:

  1. \(\mathscr{L}_0\) 的所有命题变号都是 \(\mathscr{L}_0\)-公式;
  2. 如果 \(\varphi\)\(\mathscr{L}_0\)-公式,则 \(\neg \varphi\) 也是 \(\mathscr{L}_0\)-公式;
  3. \(\varphi\)\(\psi\)\(\mathscr{L}_0\)-公式,则 \((\varphi \land \psi), (\varphi \lor \psi), (\varphi \rightarrow \psi), (\varphi \rightarrow \psi)\) 都是 \(\mathscr{L}_0\)-公式;
  4. 只有这些是 \(\mathscr{L}_0\)-公式。

很多作者在我们用「公式」的地方用「合式公式」这个词(“well-formed formula” 或 “wff”)。这里用「公式」,是因为这里没有不合式的公式。

根据上述定义,下列 \(\mathscr{L}_0\)-符号串都是 \(\mathscr{L}_0\)-公式:

  1. \(p_{156}\)
  2. \((\neg p_{75} \land p_{21})\)
  3. \((p_9 \rightarrow (p_{57} \lor (p_{23} \rightarrow p_{601})))\)
  4. \((((((p_{28} \rightarrow p_{28})\rightarrow p_{28})\rightarrow p_{28})\rightarrow p_{28})\rightarrow p_{28})\)

下列 \(\mathscr{L}_0\)-符号串都不是 \(\mathscr{L}_0\)-公式:

  1. \(p_{13} \land\)
  2. \(p_{822} \neg p_{822}\)
  3. \((p_{69} \rightarrow \neg p_{801}))\)
  4. \((p_{28} \neg \rightarrow p_{782}))\)

为了讨论的方便,我们用 \(p, q, r, s\) 等表示 \(p_{0}, p_{1}, p_{2},...\) 中的前几个(如果不对它们做限制),必要时可再用 \(^\prime\), \(^{\prime\prime}\) 或上下标来区分不同的命题变号。我们将用 \(\varphi, \psi, \chi, \theta, \lambda\) 等小写的希腊字母(加 \(^\prime\), \(^{\prime\prime}\) 或上下标)表示 \(\mathscr{L}_0\)-公式,用 \(\Gamma, \Delta\) 等大写的希腊字母表示 \(\mathscr{L}_0\)-公式集合。

3.4.2 对象语言和元语言

初学者要学会分清「对象语言」和「元语言」。所谓对象语言(object Ianguage),是作为我们讨论对象的语言;所谓元语言(metalanguage),是我们讨论中使用的语言。比如,在一本文教科书里,文是对象语言。如果这本书是初级教科书,那么很可能中文就是元语言;而如果这本书是高级教科书,那么它的元语言很可能也是文。在本书中,元语言是中文加上一些符号(偶尔还有一点文),对象语言到目前为止就是 \(\mathscr{L}_0\)

注意:我们可以用 \(\varphi\)(或别的什么符号)表示对象语言里的某个公式(\(\mathscr{L}_0\)-公式),但那并不是说希腊字母 “\(\varphi\)” 是对象语言里的符号或公式。“\(\varphi\)” 是我们元语言里的符号,我们只是用它来表示某个 \(\mathscr{L}_0\)-公式。关于对象语言和元语言,现在只谈这些,进一步的讨论还会在§3.0.0(P.99)中出现。

这一章涉及的对象语言只有 \(\mathscr{L}_0\),所以在提到 \(\mathscr{L}_0\)-公式或 \(\mathscr{L}_0\)-公式集时,我们将尽可能省略前缀 “\(\mathscr{L}_0\)”,只说公式或公式集。

3.4.3 子公式和主联结词

公式的子公式(subformula)是出现在该公式中的公式(包括它自己)。如果 \(\psi\)\(\varphi\) 的子公式,且 \(\psi \neq \varphi\),那么 \(\psi\)\(\varphi\)真子公式(proper subformuIa)。一个公式的主联结词是该公式构造过程最后一步中使用的那个联结词,而它的直接子公式就是在这一步中主联结词联结的公式。严格地说,

  1. 对每个命题变号 \(p\)\(p\)\(p\) 的子公式;
  2. \(\varphi\) 的所有子公式和 \(\neg \varphi\) 都是 \(\neg \varphi\) 的子公式,\(\varphi\)\(\neg \varphi\) 的直接子公式,且 \(\neg\)\(\neg \varphi\) 的主联结词;
  3. \(\varphi\)\(\psi\) 的所有子公式和 \((\varphi \lor \psi)\) 都是 \((\varphi \lor \psi)\) 的子公式,\(\varphi\)\(\psi\)\((\varphi \lor \psi)\) 的直接子公式,且 \(\vee\)\((\varphi \lor \psi)\) 的主联结词;
  4. \(\varphi\)\(\psi\) 的所有子公式和 \((\varphi \land \psi)\) 都是 \((\varphi \land \psi)\) 的子公式,\(\varphi\)\(\psi\)\((\varphi \land \psi)\) 的直接子公式,且 \(\wedge\)\((\varphi \land \psi)\) 的主联结词;
  5. \(\varphi\)\(\psi\) 的所有子公式和 \((\varphi \rightarrow \psi)\) 都是 \((\varphi \rightarrow \psi)\) 的子公式,\(\varphi\)\(\psi\)\((\varphi \rightarrow \psi)\) 的直接子公式,且 \(\rightarrow\)\((\varphi \rightarrow \psi)\) 的主联结词;
  6. \(\varphi\)\(\psi\) 的所有子公式和 \((\varphi \leftrightarrow \psi)\) 都是 \((\varphi \leftrightarrow \psi)\) 的子公式,\(\varphi\)\(\psi\)\((\varphi \leftrightarrow \psi)\) 的直接子公式,且 \(\leftrightarrow\)\((\varphi \leftrightarrow \psi)\) 的主联结词;

以相同主联结词为公式分类,我们有公式的下列类名称:

  1. 命题变号称为 \(\mathscr{L}_0\)-原子公式(atomic formula)
  2. 形如 \(\neg \varphi\) 的公式(即以 \(\neg\) 为主联结词的公式)称为否定式(negation),俗称「\(\varphi\) 的否定」;
  3. 形如 \((\varphi \lor \psi)\) 的公式称为析取式(disjunction),俗称「\(\varphi\)\(\psi\) 的析取」,\(\varphi\)\(\psi\) 称为它的析取支(disjuncts)
  4. 形如 \((\varphi \land \psi)\) 的公式称为合取式(conjunction),俗称「\(\varphi\)\(\psi\) 的合取」。\(\varphi\)\(\psi\) 称为它的合取支(conjuncts)
  5. 形如 \((\varphi \rightarrow \psi)\) 的公式称为蕴涵式(implication)条件句(conditional)\(\varphi\) 称为它的前件(antecedent)\(\psi\) 称为它的后件(consequent)
  6. 形如 \((\varphi \leftrightarrow \psi)\) 的公式称为等值式(equivalence),亦称双(向)蕴涵式(bi-implication)双(向)条件句(biconditional)

3.4.4 括号的省略

为书写和阅读的方便,我们根据以下两条规则省略公式中的一些括号:

  1. 最外层的括号可以省略;
  2. 假定 \(\vee\)\(\wedge\) 的联结比 \(\rightarrow\)\(\leftrightarrow\) 优先,就像在做算术题时 \(\times\)\(\div\)\(+\)\(-\) 优先(或者说 \(\rightarrow\)\(\leftrightarrow\) 在做公式主联结词方面比 \(\vee\)\(\wedge\) 优先)。

例 3.24 下列符号串不是省略了括号的公式:

  1. \(p \land q \lor r\)
  2. \(p \rightarrow q \rightarrow r\)
  3. \(p \rightarrow q \lor r \rightarrow s\)
  4. \(p \rightarrow (q \lor r) \rightarrow s\)
  5. \(p \rightarrow q \rightarrow r \lor s\)

例 3.25 以下编号者为省略括号的公式,未编号者为对应未省略括号的公式:

  1. \((p \rightarrow q) \land r\)
  2. \(p \land q \rightarrow \neg r \land s\)
  3. \(p \lor q \rightarrow \neg(p \land q)\)
  4. \((p \lor q) \land r \rightarrow s\)
  5. \(((p \rightarrow q) \rightarrow r) \rightarrow s\)
  • \(((p \rightarrow q) \land r)\)
  • \(((p \land q) \rightarrow (\neg r \land s))\)
  • \(((p \lor q) \rightarrow \neg(p \land q))\)
  • \((((p \lor q) \land r) \rightarrow s)\)
  • \((((p \rightarrow q) \rightarrow r) \rightarrow s)\)

注意:一个符号串是否为省略了括号的公式,取决于特定作者或特定书籍对省略括号的约定。根据本书的约定,例 3.25 中(编号者)的符号串是公式而例 3.24 中的不是。但若按照其他约定,例 3.25 中的有可能不是公式而例 3.24 中的倒有可能是公式。比如,有的作者喜欢「右结合原则」,即同一种联结词连续出现时,右边的联结词比左边的优先。在这一约定下,例 3.24 中的第二个符号串就成了公式 \((p \rightarrow (q \rightarrow r))\) 的省略括号的写法。如果在我们上述约定的基础上再加「右结合原则」,那么例 3.24 中的第三个符号串也就成了公式 \((p \rightarrow ((q \lor r) \rightarrow s))\) 省略括号的写法。当然,还有很多不同的约定方法,这里就不一一介绍了。

3.4.5 语法和语义

语法(syntax)语义(semantics)的区别对学习当代逻辑至关重要。语法理论有时叫语形理论,它涉及符号组合和公式的结构,以及公式在结构或形式方面的各种关系,唯独不涉及这些符号和公式的意义。讨论符号和公式意义的理论称为语义理论。本节的上述内容和以后将讨论的公式的变换、公式序列(依规则)的生成等,都属于语法理论。

有时人们谈论有意义的符号和无意义的符号。在逻辑学家们的笔下,「符号」多数时候是指没有被赋予意义的东西。比如,前面讨论的符号本身都是没有意义的。一旦赋予这些符号意义,我们就进入了语义理论。针对符号和公式的意义的讨论,包括公式的真假,统称为语义讨论。

为理解语法和语义的区别,我们来看下面几个表达式:

  1. \(1+1=2\)
  2. One pIus one is (equal to) two.
  3. 一加一等于二。

这些是不同语言中的句子,而不同语言有不同的符号和形成规则。(自然语言很难说有严格的形成规则,但大体上是有规则的。)所以,这些句子从语法上说是不同的。但是,根据通常的解释,它们的意思是相同的,或者说在语义上是相同的。再来看同一个语言中的例子:

  1. 张三打了李四一拳。
  2. 李四被张三打了一拳。

显然这两个句子的意思相同,即在语义方面相同。但是,第一句有八个字,而第二句却有九个字;第一句的前两个字是「张三」,而第二句的前两个字却是「李四」。所以,这两个句子在语法方面是不同的。

3.5 基本真值表和真值的计算

在这一节里,我们介绍真值表和公式真值的计算方法,然后在下一节用这种方法来讨论命题逻辑的一些基本语义概念。

3.5.1 联结词的语义解释

命题逻辑不涉及命题中不能由联结词表现出来的内部结构,所以在某种意义上说,命题逻辑是研究联结词的。

从语法角度看,联结词自然是「公式函数」,即从公式集合到公式集合的函数。这就是说,对每个联结词,每当给出公式作为「输入」,这个联结词确定了唯一的公式作为「输出」,即以该联结词为主联结词并以给定公式为直接子公式的公式。那么,诸如「并非」「并且」这样的联结词的意义(meaning)又是什么呢?我们说过,这些联结词是真值函数联结词。什么是真值函数(truth function)?真值函数是从真值集到真值集的函数。我们用 T 或 1 表示真,用 F 或 0 表示假。根据我们对真值的「二值」预设,真值函数就是从 \(\lbrace 1, 0\rbrace\)\(\lbrace 1, 0\rbrace\) 的函数。真值函数联结词之所以叫「真值函数联结词」,是因为从语义角度看,它们是真值函数。换句话说,真值函数联结词就是以真值函数为其解释的联结词。关于这一点,我们在 §3.3.0(P.115)和 §3.5(P.122)中还会讨论。

现在,我们先用比较直观的真值表(truth table)来讨论真值函数联结词。表 3.1 是关于五个真值函数联结词的基本真值表。

Table: (#tab:truthtable) 基本真值表

\[ \begin{array}{cc|ccccc} \hline \hline \varphi & \psi & \varphi \wedge \psi & \varphi \vee \psi & \varphi \rightarrow \psi & \varphi \leftrightarrow \psi & \neg \varphi \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & \\ \hline \hline \end{array} \]

根据表 3.1,无论 \(\varphi\) 是怎样的公式,如果 \(\varphi\) 是真的, \(\neg \varphi\) 就是假的;如果 \(\varphi\) 是假的,\(\neg \varphi\) 就是真的。这就是说,\(\neg \varphi\) 的真值完全取决于 \(\varphi\) 的真值。类似地,无论 \(\varphi\)\(\psi\) 是什么公式,如果 \(\varphi\)\(\psi\) 都是真的,\(\varphi \rightarrow \psi\) 就是真的;如果 \(\varphi\) 是真的而 \(\psi\) 是假的,\(\varphi \rightarrow \psi\) 是假的;……用 \(\land, \lor, \leftrightarrow\) 做主联结词的情况依此类推。

因为每个公式 \(\varphi\) 都是由命题变号经五个真值函数联结词构造出来的,所以,一旦 \(\varphi\) 中命题变号的真值确定了,\(\varphi\) 的真值就可以按照上述基本真值表一步步计算出来。

在计算公式的真值前,先把基本真值表 3.1 记住,就像做乘法运算前要先记住乘法口诀那样。记真值表时要记住这些组合情况与右侧真值的对应,仅仅简单地记住「合取:1, 0, 0, 0;析取:1, 1, 1, 0;…」并不是好办法,甚至可能导致误解。尝试记住下列命题:

  1. 一个否定式是真的,当且仅当它否定的公式是假的;
  2. 一个合取式是真的,当且仅当它的合取支都是真的;
  3. 一个析取式是真的,当且仅当它的析取支中至少有一个是真的;
  4. 一个蕴涵式是真的,当且仅当它的前件是假的或后件是真的;
  5. 一个等值式是真的,当且仅当它的两个直接子公式的真值相同。

由此,可以对应地得岀命题「一个否定式是假的,当且仅当它否定的公式是真的」等等。读者应试着把余下的几个对应命题找出来,见练习 2.3。

3.5.2 公式真值的计算

公式真值的计算方法分两类,一是用子公式的给定真值来计算公式的真值,二是用公式的真值表计算公式在各种可能情况下的真值。

3.5.2.1 以子公式的给定真值计算

我们先看如何用命题变号的给定真值来计算公式的真值。

例 3.26 \(p\) 的真值为 1,\(q\) 的真值为 0 并且 \(r\) 的真值为 1. 计算公式 \((p \rightarrow \neg q \land r) \rightarrow (p \lor r)\) 的真值。

Solution: 依据基本真值表 3.1 层层运算即可。先根据假设把命题变号的真值写在相应的命题变号下方,然后逐层推得结果。

\[ \begin{array}{c|ccc|c|c} \text{步骤} & (p & \rightarrow & \neg q \land r) & \rightarrow & (p \lor r)\\ \hline 0 & ~1 & & ~~0~~~~1 & &1~~~~1 \\ 1 & & & 1~~~~~~~~~~ & & ~1 \\ 2 & & & ~1 & & \\ 3 & & 1 & & & \\ 4 & & & & 1 & \end{array} \]

一个公式的真值的计算未必要从它的原子子公式开始——计算可以从它的其他子公式开始。比如,

例 3.27 \(\varphi\) 的真值为 1,\(\psi\) 的真值为 0 并且 \(\chi\) 的真值为 0. 计算公式 \((\varphi \rightarrow \neg \psi \land \chi) \rightarrow (\varphi \lor \chi)\) 的真值。
Solution: 与例 3.26 解法相同,易知其真值为 1.

3.26, 3.27 使我们明白:要计算出一个公式的真值,我们只需知道它的所有直接子公式的真值,而不一定要知道它的所有原子子公式的真值。其实,要计算出一个公式的真值,也未必要事先知道它的所有直接子公式的真值。

例 3.28 \(\varphi\) 的真值为 1 且 \(\psi\) 的真值为 0. 那么对任意公式 \(\chi\),根据(真值)表 2.1,以下结论是显然的:

  1. \(\varphi \lor \chi\) 的真值为 1,
  2. \(\chi \rightarrow \varphi\) 的真值为 1,
  3. \(\chi \land \psi\) 的真值为 0,
  4. \(\psi \rightarrow \chi\) 的真值为 1.
例 3.29 \(\varphi\) 的真值为 1 且 \(\psi\) 的真值为 0. 计算公式 \(\varphi \rightarrow(\varphi \rightarrow(\varphi \rightarrow(\varphi \vee(\chi \wedge \xi) \rightarrow \psi)))\) 的真值。

Solution: 与前几例并无区别。易知其真值为 0.

\[ \underbrace{\underset{1}{\varphi} \mathpunct{\smash{\underset{\mathbf{\underset{0}{\big\uparrow}}}{\rightarrow}}} \underbrace{(\underset{1}{\varphi} \mathpunct{\smash{\underset{\mathbf{\underset{0}{\big\uparrow}}}{\rightarrow}}} \underbrace{(\underset{1}{\varphi} \mathpunct{\smash{\underset{\mathbf{\underset{0}{\big\uparrow}}}{\rightarrow}}} \underbrace{\underbrace{(\underset{1}{\varphi} \mathpunct{\smash{\underset{\mathbf{\underset{1}{\big\uparrow}}}{\lor}}}\underbrace{(\underset{?}{\chi}\mathpunct{\smash{\underset{\mathbf{\underset{?}{\uparrow}}}{\land}}} \underset{?}{\xi})}_{?}}_{1} \mathpunct{\smash{\underset{\mathbf{\underset{0}{\big\uparrow}}}{\rightarrow}}} \underset{0}{\psi})}_{0})}_{0})}_{0}}_{0} \]
例 3.30 \(\psi\) 真值为 0. 计算公式 \(\psi_{0} \rightarrow\left(\psi_{1} \rightarrow\left(\psi_{2} \rightarrow(\chi \wedge \psi \rightarrow \xi)\right)\right)\) 的真值。
Solution: 原理与方法与前几例并无区别。易知 \(\chi \wedge \psi\) 真值为 0,则 \(\chi \wedge \psi \rightarrow \xi\) 真值为 1,那么无论前件真值为 1 或 0,公式真值始终为 1.

3.5.2.2 以公式的真值表计算

一旦会用子公式的真值来计算公式的真值,构造公式的真值表是件很简单的事——它不过是列出给定公式中的全部命题变号的所有「可能取值组合」,并根据它们计算和列出该公式在每一种可能情况下的真值。

对给定公式中的每个命题变号指定一个固定的真值,这样指定的结果称为这些命题变号的一个「可能取值组合」。若干命题变号的一个可能取值组合是从这些命题变号到 \(\lbrace 1,0\rbrace\) 的一个函数。因为每个命题变号的真值或为 1 或为 0,则 \(n\) 个命题变号的可能取值组合为 \(2^n\) 个。一个公式的真值表一定要包含该公式中命题变号的所有可能取值组合。在构造公式 \(\varphi\) 的真值表时,按惯例先在表的左侧排出 \(\varphi\) 中出现的所有命题变号,然后排列出它们的全部可能取值组合(的值),再把 \(\varphi\) 的各个子公式的真值从简单到复杂一步步计算出来。

公式的真值表通常有两种画法,第一种是在表的上方排出该公式的所有子公式,通过计算将这些子公式的真值列在它们的下方。

例 3.31 计算公式 \(p \wedge \neg q \rightarrow \neg p \vee q\) 在各种情况下的真值。
Solution: \[ \begin{array}{cc||l|l|l|c||c} \hline\hline p & q & \neg q & p \wedge \neg q & \neg p & \neg p \vee q & p \wedge \neg q \rightarrow \neg p \vee q\\ \hline 1 & 1 & 0 & ~~~0 & 0 & ~~~1 & \mathbf{1} \\[.7ex] 1 & 0 & 1 & ~~~1 & 0 & ~~~0 & \mathbf{0} \\[.7ex] 0 & 1 & 0 & ~~~0 & 1 & ~~~1 & \mathbf{1} \\[.7ex] 0 & 0 & 1 & ~~~0 & 1 & ~~~1 & \mathbf{1} \\ \hline\hline \end{array} \]

公式的真值表的第二种画法是在表上方只列出该公式(及其原子子公式),而把它的(非原子)子公式的值列在该子公式的主联结词之下。

例 3.32 计算公式 \((p \vee q) \wedge \neg r \rightarrow p \wedge (\neg q \vee r)\) 在各种情况下的真值。
Solution: \[ \begin{array}{ccc|ccl|c|ccccccc} \hline\hline p & q & r & (p \vee q) & \wedge & \neg r & \rightarrow & p & \wedge & (\neg q & \vee & r) \\ \hline 1 & 1 & 1 & 1 & 0 & 0 & \mathbf{1} & & 1 & 0 & 1 & \\[.7ex] 1 & 1 & 0 & 1 & 1 & 1 & \mathbf{0} & & 0 & 0 & 0 & \\[.7ex] 1 & 0 & 1 & 1 & 0 & 0 & \mathbf{1} & & 1 & 1 & 1 & \\[.7ex] 1 & 0 & 0 & 1 & 1 & 1 & \mathbf{1} & & 1 & 1 & 1 & \\[.7ex] 0 & 1 & 1 & 1 & 0 & 0 & \mathbf{1} & & 0 & 0 & 1 & \\[.7ex] 0 & 1 & 0 & 1 & 1 & 1 & \mathbf{0} & & 0 & 0 & 0 & \\[.7ex] 0 & 0 & 1 & 0 & 0 & 0 & \mathbf{1} & & 0 & 1 & 1 & \\[.7ex] 0 & 0 & 0 & 0 & 0 & 1 & \mathbf{1} & & 0 & 1 & 1 & \\ \hline\hline \end{array} \]

3.32 有意将公式中符号间的距离加大,以使读者清楚地看出:每个子公式的真值都列在该子公式的主联结词的下方。特别地,例 3.32 中「\(\rightarrow\)」之下那列真值,是公式 \((p \vee q) \wedge \neg r \rightarrow p \wedge (\neg q \vee r)\) 在各种情况下的真值。我们将一贯地将子公式的真值列于该子公式的主联结词之下,但不再加大公式中符号间的距离。从现在起,将只釆用公式真值表的第二种画法。

我们约定:凡谈到真值表中的真值时,我们用「行」表示该表中从左到右的真值序列,用「列」表示该表中从上到下的真值序列。

3.6 若干基本语义概念的真值表刻画

这一节里,我们用真值表方法介绍和讨论一些基本语义概念:重言蕴涵(重言后承)、重言等值、可满足性、重言式、矛盾式和或然式。我们对这些概念所做的真值表刻画,在某些教科书中就称为这些概念的定义。之所以我们不称这些刻画为定义,是因为这里的讨论不够严格。在 §3.1(P.101)中,我们要用真值指派给出这些概念的严格定义。

为了比较和讨论不同公式的真值情况,我们可以把不同的公式放到同一个真值表中。这样的真值表称为联合真值表。在公式 \(\varphi_0,...\varphi_n\) 的联合真值表中,我们要列出这些公式的所有原子子公式和它们的可能取值组合(的值),并且根据这些组合计算 \(\varphi_0,...\varphi_n\) 各自的真值。

3.6.1 论说形式的有效性

一个论说形式的前提和结论的联合真值表称为该论说形式的真值表。有了论说形式的真值表,引言中讨论的论说形式的好坏可以有更清楚的定义(下面的「有效」对应于「好」,「无效」对应于「坏」;参见§0.0(P.2)和§2.2(P.76)中的有关形式好坏的讨论。)

  1. 在一个论说形式的真值表中,前提都真而结论假的每一行,都称为该论说形式的反例
  2. 对任何一个论说形式,如果其真值表的任何一行都不是该论说形式的反例,那么这个论说形式是有效的(valid);否则,这个论说形式是无效的(invalid)
例 3.33 用真值表检验论说形式 \(p \rightarrow q, \neg q ~/\therefore \neg p\) 的有效性。

Solution: 这个论说形式的真值表中结论 \(\neg p\) 为假的只有第一行和第二行,但这两行中,前提里也总有一个是假的。所以,上述论说形式没有反例,是有效的论说形式。此例为最基本的蕴涵式否定后件推理,应用归谬赋值或自然演绎法同理可证。(对比例 3.37

\[ \begin{array}{cc|cl|l} p & q & p \rightarrow q, & \neg q & \neg p \\ \hline 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{array} \]
例 3.34 用真值表检验论说形式 \(p \rightarrow (q \rightarrow r), p \rightarrow q ~/\therefore p \rightarrow r\) 的有效性。

Solution: 根据下表,前提都真的每一行里结论也都真;所以,上述论说形式是有效的。

\[ \begin{array}{ccc|lc|c} p & q & r & p \rightarrow(q \rightarrow r), & p \rightarrow q & p \rightarrow r \\ \hline 1 & 1 & 1 & ~~~~1 & 1 & 1 \\ 1 & 1 & 0 & ~~~~0 & 1 & 0 \\ 1 & 0 & 1 & ~~~~1 & 0 & 1 \\ 1 & 0 & 0 & ~~~~1 & 0 & 0\\ 0 & 1 & 1 & ~~~~1 & 1 & 1 \\ 0 & 1 & 0 & ~~~~1 & 0 & 1 \\ 0 & 0 & 1 & ~~~~1 & 1 & 1\\ 0 & 0 & 0 & ~~~~1 & 1 & 1 \end{array} \]
例 3.35 用真值表检验论说形式 \(p \rightarrow q \lor \neg r, r \land q \rightarrow p ~/\therefore r \rightarrow \neg q\) 的有效性。

Solution: 这个论说形式真值表的第一行中,论说的前提都真而结论假,是该论说形式的反例;所以该论说形式是无效的。

\[ \begin{array}{ccc|lr|c} p & q & r & p \rightarrow q \vee \neg r, & r \wedge q \rightarrow p & r \rightarrow \neg q \\ \hline 1 & 1 & 1 & ~~~~1 & 1~~~~~ & 0~~~ \\ 1 & 1 & 0 & ~~~~1 & 1~~~~~ & 1~~~ \\ 1 & 0 & 1 & ~~~~0 & 1~~~~~ & 1~~~ \\ 1 & 0 & 0 & ~~~~1 & 1~~~~~ & 1~~~ \\ 0 & 1 & 1 & ~~~~1 & 0~~~~~ & 0~~~ \\ 0 & 1 & 0 & ~~~~1 & 1~~~~~ & 1~~~ \\ 0 & 0 & 1 & ~~~~1 & 1~~~~~ & 1~~~ \\ 0 & 0 & 0 & ~~~~1 & 1~~~~~ & 1~~~ \end{array} \]

读者在这里可能会有这样一个问题:我们在引言里曾说过,论说形式的好坏涉及该形式的所有特例,其数量显然无上界;而这里说的论说形式的有效性却只涉及 \(2^n\) 个可能的取值组合(假设其中只出现 \(n\) 个命题变号)。这两种说法如何能是「一回事」呢?

可以这样来理解这个问题:假定一个论说形式中出现 \(n\) 个命题变号,进而该论说形式的真值表有 \(2^n\) 行。这个论说形式的每个特例,都可以看作是以具体命题替换那些命题变号而得到的。替换的都是具体命题,因而它们的真值都是确定的,对应于 \(2^n\) 个可能取值组合中的一个。(\({\prod_{i=1}^{n}} (C_{2}^{1})_i = 2^{n}.\))这样,我们就把该论说形式的所有特例分成了 \(2^n\) 组,而每个特例的前提和结论的真值情况,都在该论说形式真值表的某一行中。当讨论这个真值表的任一行时,假如沿用引言中的术语,那么我们就会说,讨论涉及该论说形式的一组特例而非一个特例;当我们认定真值表的某一行是给定论说形式的反例时,假如沿用引言中的术语,那么我们就会说该论说形式有一组反例。

3.6.2 重言蕴涵

\(\varphi_0,...,\varphi_n\)\(\psi\) 为任意公式。\(\lbrace \varphi_0,...,\varphi_n \rbrace\) 重言蕴涵(tautologically implies) \(\psi\) 当且仅当在 \(\varphi_0,...,\varphi_n\)\(\psi\) 的联合真值表中,没有一行是 \(\varphi_0,...,\varphi_n\) 都真而 \(\psi\) 假,亦即在它们的联合真值表的每一行中,如果 \(\varphi_0,...,\varphi_n\) 的真值都是 1,那么 \(\psi\) 的真值也一定是 1. \(\psi\)\(\lbrace \varphi_0,...,\varphi_n \rbrace\)重言后承(tautological consequence)当且仅当 \(\varphi_0,...,\varphi_n\) 重言蕴涵 \(\psi\).(\(\lbrace \varphi_0,...,\varphi_n \rbrace\) tautologically implies \(\psi\)

易见,根据有效性和重言蕴涵的定义,下列两个命题等价:

  1. \(\lbrace \varphi_0,...,\varphi_n \rbrace\) 重言蕴涵 \(\psi\)
  2. \(\varphi_0,...,\varphi_n\) 为前提并以 \(\psi\) 为结论的论说形式是有效的。

在理论讨论中,「重言蕴涵」比「有效论说形式」使用得更多,尽管根据上述等价性,我们知道在命题逻辑部分,它们说的是一回事。(这里谈到的公式集合都是有穷集合,无穷集合的情况将在§3.1(P.101)中讨论。在谓词逻辑部分,重言蕴涵关系将让位于逻辑蕴涵关系,重言后承关系将让位于逻辑后承关系。)

例 3.36 \(\lbrace p \rightarrow (q \rightarrow r), p \rightarrow q \rbrace\) 重言蕴涵 \(p \rightarrow r\),而 \(r \rightarrow \neg q\) 则不是 \(\lbrace p \rightarrow q \lor \neg r, r \land q \rightarrow p \rbrace\) 的重言后承。
Solution: 分别见例 3.34 和例 3.35 中的真值表。
例 3.37 \(p \rightarrow q\) 重言蕴涵 \(\neg q \rightarrow \neg p.\)

Solution: \(p \rightarrow q\)\(\neg q \rightarrow \neg p\) 的联合真值表中,\(\neg q \rightarrow \neg p\) 只在第二行是假的,而 \(p \rightarrow q\) 在该行也是假的。这就是说,在该表的每一行中,如果 \(p \rightarrow q\) 是真的则 \(\neg q \rightarrow \neg p\) 也是真的。根据重言蕴涵的定义,\(p \rightarrow q\) 重言蕴涵 \(\neg q \rightarrow \neg p.\)(对比例 3.33

\[ \begin{array}{cc|c|ccc} p & q & p \rightarrow q & \neg q \rightarrow \neg p \\ \hline 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{array} \]
例 3.38 \(p \rightarrow q\) 不重言蕴涵 \(\neg p \rightarrow \neg q.\)

Solution: \(p \rightarrow q\)\(\neg p \rightarrow \neg q\) 的联合真值表中,\(p \rightarrow q\) 在第三行是真的,但 \(\neg p \rightarrow \neg q\) 在该行是假的。所以,根据重言蕴涵的定义 \(p \rightarrow q\) 不重言蕴涵 \(\neg p \rightarrow \neg q.\)

\[ \begin{array}{cc|c|ccc} p & q & p \rightarrow q & \neg p \rightarrow \neg q \\ \hline 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{array} \]

3.6.3 重言等值

\(\varphi\)\(\psi\) 为任意公式。\(\varphi\)\(\psi\) 重言等值(tautologically equivalent) 当且仅当在 \(\varphi\)\(\psi\) 联合真值表的任意一行中,\(\varphi\)\(\psi\) 有同样的真值,亦即在它们的联合真值表的每一行中,如果 \(\varphi\) 的真值是 1,则 \(\psi\) 的真值也是 1;并且如果 \(\varphi\) 的真值是 0,则 \(\psi\) 的真值也是 0.

根据重言蕴涵和重言等值的定义,易见下列命题等价:

  1. \(\varphi\)\(\psi\) 重言等值,
  2. \(\varphi\)\(\psi\) 相互重言蕴涵(\(\varphi\)\(\psi\) 各是对方的重言后承)。
例 3.39 \(p \rightarrow q \land p\)\(\neg q \rightarrow \neg p\) 重言等值。

Solution: \(p \rightarrow q \land p\)\(\neg q \rightarrow \neg p\) 在它们的联合真值表的每一行中真值都相同,因而由重言等值的定义得知两公式重言等值。

\[ \begin{array}{cc|c|c} p & q & p \rightarrow q \wedge p & \neg q \rightarrow \neg p \\ \hline 1 & 1 & 1~~~~~~~ & 1 \\ 1 & 0 & 0~~~~~~~ & 0 \\ 0 & 1 & 1~~~~~~~ & 1 \\ 0 & 0 & 1~~~~~~~ & 1 \end{array} \]
例 3.40 \(p \land \neg q\)\(\neg p \lor q\) 不重言等值。

Solution: \(p \land \neg q\)\(\neg p \lor q\) 的联合真值表中,\(p \land \neg q\) 在第一行是假的,而 \(\neg p \lor q\) 在同一行是真的。所以,根据重言等值的定义,这两个公式不是重言等值的。(事实上,在上述真值表中,\(p \land \neg q\)\(\neg p \lor q\) 在每一行的真值都不同;但是,对「不重言等值」来说,两公式在一行中真值不同已经足够了。)

\[ \begin{array}{cc|c|c} p & q & p \wedge \neg q & \neg p \vee q \\ \hline 1 & 1 & 0~~ & ~~~1 \\ 1 & 0 & 1~~ & ~~~0 \\ 0 & 1 & 0~~ & ~~~1 \\ 0 & 0 & 0~~ & ~~~1 \end{array} \]

3.6.4 可满足性

这里说的可满足性(satisfiability),就是§0.2(P.8)中说的语义一致性。设 \(\Gamma\) 为任意有穷的公式集合。\(\Gamma\)可满足的(satisfiable)当且仅当 \(\Gamma\) 中公式的联合真值表中存在某一行,在该行里 \(\Gamma\) 中的公式的真值都是 1. \(\Gamma\) 是不可满足的当且仅当它不是可满足的。设 \(\varphi\) 为任意公式。\(\varphi\)可满足的当且仅当 \(\lbrace \varphi\rbrace\) 是可满足的。\(\varphi\) 是不可满足的当且仅当 \(\lbrace \varphi\rbrace\) 不是可满足的。

例 3.41 \(\Gamma = \lbrace p \rightarrow p \land q, \neg p \rightarrow \neg p \land \neg q, p \lor q \rbrace\) 是可满足的。

Solution: 下述真值表的第一行中,\(\Gamma\) 中每个公式都是真的,所以由可满足性的定义知 \(\Gamma\) 是可满足的。

\[ \begin{array}{cc|llc} p & q & p \rightarrow p \wedge q, & \neg p \rightarrow \neg p \wedge \neg q, & p \vee q \\ \hline 1 & 1 & ~~~~1 & ~~~~~~~1 & 1 \\ 1 & 0 & ~~~~0 & ~~~~~~~1 & 1 \\ 0 & 1 & ~~~~1 & ~~~~~~~0 & 1 \\ 0 & 0 & ~~~~1 & ~~~~~~~1 & 0 \end{array} \]
例 3.42 \(\Gamma = \lbrace p \rightarrow p \land q, \neg p \rightarrow \neg p \land \neg q, \neg (p \rightarrow q) \rbrace\) 不是可满足的。

Solution: 下面是 \(\Gamma\) 中公式的联合真值表。在该表的第一行中 \(\neg (p \rightarrow q)\) 是假的,第二行中 \(p \rightarrow p \land q\) 是假的,第三行中 \(\neg p \rightarrow \neg p \land \neg q\) 是假的,第四行中 \(\neg (p \rightarrow q)\) 是假的。所以由定义知 \(\Gamma\) 是不可满足的。

\[ \begin{array}{cc|lll} p & q & p \rightarrow p \wedge q, & \neg p \rightarrow \neg p \wedge \neg q, & \neg(p \leftrightarrow q) \\ \hline 1 & 1 & ~~~~1 & ~~~~~~~1 & 0 \\ 1 & 0 & ~~~~0 & ~~~~~~~1 & 1 \\ 0 & 1 & ~~~~1 & ~~~~~~~0 & 1 \\ 0 & 0 & ~~~~1 & ~~~~~~~1 & 0 \end{array} \]

我们简要地介绍一些关于可满足性的命题,部分涉及可满足性与重言蕴涵的关系。这些命题都有简单的证明,其中一部分会在 §3.1(P.101)中讨论。请读者思考这些命题成立的理由(见习题 2.17)。

\(\Gamma = \lbrace \varphi_0,...,\varphi_n\rbrace\) 为任意有穷的公式集,\(\varphi\) 为任意公式。我们有:

  1. 如果 \(\Gamma\) 可满足,那么对任何公式集 \(\Delta\)\(\Gamma \cap \Delta\) 也可满足。(注:对所有集合 \(X\)\(Y\)\(X \cap Y = \lbrace x: x \in X ~\text{且}~ x \in Y \rbrace\),它是包含 \(X\)\(Y\) 的所有公共元素的集合,称为 \(X\)\(Y\)交(intersection)。)
  2. 如果 \(\Gamma\) 不可满足,那么对任何有穷公式集 \(\Delta\)\(\Gamma \cup \Delta\) 也不可满足。(注:对所有集合 \(X\)\(Y\)\(X \cup Y = \lbrace x: x \in X ~\text{或}~ x \in Y \rbrace\),它是包含 \(X\) 的所有元素和 \(Y\) 的所有元素的集合,称为 \(X\)\(Y\)并集(union)。)
  3. \(\Gamma \subseteq \Delta\),其中 \(\Delta\) 是任意有穷公式集。如果 \(\Delta\) 可满足则 \(\Gamma\) 可满足(如果 \(\Gamma\) 不可满足则 \(\Delta\) 不可满足)。(注:对所有集合 \(X\)\(Y\)\(X \subseteq Y\) 当且仅当 \(X\) 的所有元素都是 \(Y\) 的元素,\(X \subset Y\) 当且仅当 \(X \subseteq Y\) 并且 \(Y \nsubseteq X\)(并非 \(Y \subseteq X\))。当 \(X \subseteq Y\),我们称 \(X\)\(Y\)子集(subset),也称 \(Y\)\(X\)扩集(superset)扩充(extension)。当 \(X \subset Y\),我们称 \(X\)\(Y\)真子集(proper subset),也称 \(Y\)\(X\) 的真扩集或真扩充。注意:「\(X \subseteq Y\)」表达的是个命题,说的是 \(X\)\(Y\) 之间的某种关系;而「\(X \cap Y\)」「\(X \cup Y\)」和下面的「\(X - Y\)」不表达命题,只表示 \(X\)\(Y\) 在某些运算下的值——集合。)
  4. \(\Gamma \cup \lbrace \neg \varphi\rbrace\)不可满足当且仅当 \(\Gamma\) 重言蕴涵 \(\varphi\)
  5. 对任意 \(i \leqslant n\)\(\Gamma\) 不可满足当且仅当 \(\Gamma - \lbrace \psi_i\rbrace\) 重言蕴涵 \(\neg \psi_i\)。(注:对所有集合 \(X\)\(Y\)\(X - Y = \lbrace x: x \in X ~\text{且}~ x \notin Y \rbrace\),它是包含 \(X\) 的所有元素但不包含 \(Y\) 的任何元素的集合,称为 \(X\)\(Y\)差(difference),也称为 \(Y\)\(X\) 中的相对补(relative complement of \(Y\) in \(X\)。)
  6. 如果 \(\Gamma\) 不可满足,那么 \(\Gamma\) 重言蕴涵 \(\varphi\)
  7. 如果 \(\neg \varphi\) 不可满足,那么 \(\Gamma\) 重言蕴涵 \(\varphi\)
  8. 如果 \(\Gamma\) 重言蕴涵 \(\varphi\),并且 \(\Gamma\) 可满足,那么 \(\varphi\) 也可满足。
  9. 如果 \(\Gamma\) 重言蕴涵 \(\varphi\) 并且 \(\Gamma\) 重言蕴涵 \(\neg \varphi\),那么 \(\Gamma\) 不可满足。

3.6.5 重言式、矛盾式与或然式

根据公式在其真值表各行中的真值情况,我们把公式分成三类:重言式(tautology)、矛盾式(contradiction)与或然式(偶然式,contingency)。

  1. 公式 \(\varphi\)重言式(tautology)当且仅当在其真值表的每一行中,\(\varphi\) 的真值都是 1,即 \(\varphi\) 总是真的。
  2. 公式 \(\varphi\)矛盾式(contradiction)当且仅当在其真值表的每一行中,\(\varphi\) 的真值都是 0,即 \(\varphi\) 总是假的。(矛盾式也称不可满足式。)
  3. 公式 \(\varphi\)或然式(contingency)当且仅当在其真值表中,\(\varphi\) 的真值在某些行中是 1,而在另一些行中是 0,即 \(\varphi\) 有时真有时假。
例 3.43 \(p \rightarrow (q \rightarrow p)\) 是重言式。

Solution: 主联结词下方一列真值都是 1,所以 \(p \rightarrow (q \rightarrow p)\) 是重言式。

\[ \begin{array}{cc|l} p & q & p \rightarrow(q \rightarrow p) \\ \hline 1 & 1 & ~~~~1 \\ 1 & 0 & ~~~~1 \\ 0 & 1 & ~~~~1 \\ 0 & 0 & ~~~~1 \end{array} \]
例 3.44 \(p \land (p \rightarrow \neg p)\) 是矛盾式。

Solution: 主联结词下方一列真值都是 0,所以 \(p \land (p \rightarrow \neg p)\) 是矛盾式。

\[ \begin{array}{c|l} p & p \wedge(p \rightarrow \neg p) \\ \hline 1 & ~~~0 \\ 0 & ~~~0 \end{array} \]
例 3.45 \(p \rightarrow q \land p\) 是或然式。

Solution: 主联结词下方一列真值中有 1 也有 0,所以 \(p \rightarrow q \land p\) 是或然式。

\[ \begin{array}{cc|l} p & q & p \rightarrow q \wedge p \\ \hline 1 & 1 & ~~~~1 \\ 1 & 0 & ~~~~0 \\ 0 & 1 & ~~~~1 \\ 0 & 0 & ~~~~1 \end{array} \]

类似于讨论可满足性与重言蕴涵时的情况,我们只简要介绍些关于重言式、矛盾式与或然式之间的关系的命题,其中一部分会在 §3.1.3(P.104)中讨论。请读者思考下列命题成立的理由(另见习题 2.6-2.9)。

  1. 重言式的否定是矛盾式。
  2. 矛盾式的否定是重言式。
  3. 或然式的否定还是或然式。
  4. 重言式与重言式的合取是重言式。
  5. 重言式与矛盾式的合取是矛盾式。
  6. 重言式与或然式的合取是或然式。
  7. 矛盾式与矛盾式的合取是矛盾式。
  8. 矛盾式与或然式的合取是矛盾式。
  9. 或然式与或然式的合取或者是或然式,或者是矛盾式。

关于上面引入的各语义概念间的关系,我们同样只简单介绍而不做证明。另一些命题将在§3.1(P.101)中讨论。

易见,对所有公式 \(\varphi, \psi, \chi\),%公式 \(\varphi \land (\psi \land \chi)\)\((\varphi \land \psi) \land \chi\) 重言等值,公式 \(\varphi \lor (\psi \lor \chi)\)\((\varphi \lor \psi) \lor \chi\) 重言等值。

  1. \(\varphi \land (\psi \land \chi)\)\((\varphi \land \psi) \land \chi\) 重言等值
  2. \(\varphi \lor (\psi \lor \chi)\)\((\varphi \lor \psi) \lor \chi\) 重言等值

以下,我们省略一连串合取和一连串析取应有的括号,用 \(\varphi_{0} \wedge \cdots \wedge \varphi_{n}\) 表示 \(\left(\cdots\left(\varphi_{0} \wedge \varphi_{1}\right) \wedge \cdots \wedge \varphi_{n-1}\right) \wedge \varphi_{n}\),用 \(\varphi_{0} \vee \cdots \vee \varphi_{n}\) 表示 \(\left(\cdots\left(\varphi_{0} \vee \varphi_{1}\right) \vee \cdots \vee \varphi_{n-1}\right) \vee \varphi_{n}\)。在极限情况 \(n=0\) 时,\(\varphi_{0} \wedge \cdots \wedge \varphi_{n}= \varphi_{0} \vee \cdots \vee \varphi_{n}=\varphi_{0}\)。这就是说,当 \(\varphi_{0} \wedge \cdots \wedge \varphi_{n}\)\(\varphi_{0} \vee \cdots \vee \varphi_{n}\) 在讨论中出现而我们又要考虑主联结词时,我们可以按「左结合」的原则恢复括号。

\(\varphi, \psi, \varphi_{0},...,\varphi_{n}\) 为任意公式且 \(\Gamma = \lbrace \varphi_{0},...,\varphi_{n}\rbrace\)。请思考下列命题成立的理由(见习题 2.18):

  1. \(\varphi\) 重言蕴涵 \(\psi\) 当且仅当 \(\varphi \rightarrow \psi\) 是重言式;
  2. \(\varphi\) 重言等值于 \(\psi\) 当且仅当 \(\varphi \rightarrow \psi\) 是重言式,当且仅当 \(\psi \rightarrow \varphi\)\(\varphi \rightarrow \varphi\) 都是重言式;
  3. \(\Gamma\) 重言蕴涵 \(\psi\) 当且仅当 \(\varphi_{0} \land \cdots \land \varphi_{n} \rightarrow \psi\) 是重言式;
  4. \(\varphi_{0} \land \cdots \land \varphi_{n} \rightarrow \psi\)\(\varphi_{0} \land \cdots \land \varphi_{n-1} \rightarrow (\varphi_n \rightarrow \psi )\) 重言等值;
  5. 如果 \(\varphi\) 是重言式,那么 \(\Gamma\) 重言蕴涵 \(\varphi\)
  6. \(\Gamma\) 可满足当且仅当 \(\varphi_{0} \land \cdots \land \varphi_{n}\) 或者是或然式或者是重言式;
  7. \(\Gamma\) 不可满足当且仅当 \(\varphi_{0} \land \cdots \land \varphi_{n}\) 或者是或然式或者是矛盾式。
  8. 如果 \(\varphi\) 是重言式,那么 \(\Gamma\) 是可满足的当且仅当 \(\Gamma \cup \lbrace \varphi\rbrace\) 是可满足的;
  9. 如果 \(\varphi_i (i \leqslant n)\) 是重言式,那么 \(\Gamma\) 是可满足的当且仅当 \(\Gamma - \lbrace \varphi_i\rbrace\) 是可满足的;
  10. 如果 \(\varphi\) 是矛盾式,那么 \(\Gamma \cup \lbrace \varphi\rbrace\) 是不可满足的;
  11. 如果 \(\varphi_i (i \leqslant n)\) 是矛盾式,那么 \(\Gamma\) 是不可满足的。

3.6.6 简化真值表方法

我们知道,如果对一个包含 \(n\) 个命题变号的公式构造完整的真值表,其真值表有 \(2^n\) 行。随着 \(n\) 的增长,\(2^n\) 是以「指数」增长的。借助计算机,假定以 \(100,0000\) 行每秒的速度生成真值表,当 \(n=80\) 时,那就需要 \(2^{80} \mu \mathrm{s}\) 生成真值表,这个时间是多长呢?换算成以年为单位的话,大槪是 \(380\) 亿年,而宇宙至今也只存在了大槪 \(150\) 亿年,超过了宇宙到现在的存在时间!这也是现代理论计算机科学中最著名的难题。[Enderton,2001: 25]

所以,一旦公式(集)中出现 3 个或更多的命题变号,它们的真值表就会比较大,手工画起来常有困难。日常思维与语言中的论证,涉及的命题变号通常并不多,可以引入简化真值表方法判定一个论说形式是否有效。简化真值表方法有多种,这里只介绍其一。

用简化真值表法判别一个论说形式是否有效,通常可按以下方式来做:首先假设该论说形式的前提都真而结论假,然后根据它们的真值算出它们的直接子公式的真值,再进一步根据子公式的真值算出这些子公式的直接子公式的真值。(当遇到合取式为假或析取式为真等情况时,不能直接算出它们的直接子公式的真值而要分情况讨论。)在这一过程中,若遇到某公式既真又假,就可判定给出的论说形式是有效的;若没有遇到这种情况,则可判定该论说形式是无效的。在后一种情况下,能找到该论说形式中命题变号的一个可能取值组合,使得根据这个组合,该论说形式的前提为真而结论为假。

例 3.46 用简化真值表方法检验 \(p \rightarrow (q \rightarrow r), p \rightarrow q ~/ \therefore p \rightarrow r\) 是否有效。

Solution: 这个论证形式是有效的。假定这个论说形式不是有效的,我们得到一个矛盾:\(q\) 既真又假。\(q\) 不可能同时既真又假,所以给定的论说形式一定是有效的。见下表:

\[ \begin{array}{c|ll|c|c} \text{步骤} & p \rightarrow(q \rightarrow r), & p \rightarrow q & /\therefore p \rightarrow r & \text{步骤解说} \\ \hline 1 & ~~~~1 & ~~~~1 & ~~\quad0 & \text{假设论证形式无效}\\[0.4ex] 2 & & & ~~~\quad1~\quad0 & \text{推得结论中}~p, r~\text{真值}\\[0.4ex] 3 &1~~~~~~~~~~~~1~~0 & 1& & \text{推得前提中}~q \rightarrow r~\text{真值}\\[0.4ex] 4 &~~~~~~~~~~~\mathbf{0} & ~~~~~~~~\mathbf{1}& & \text{推得前提中}~q~\text{亦真亦假}\\ \end{array} \]
例 3.47 用简化真值表方法检验 \(p \rightarrow q \lor \neg r, r \land q \rightarrow p ~/ \therefore r \rightarrow \neg q\) 是否有效。

Solution: 这个论证形式是无效的。易见我们的假设不导致任何矛盾,所以当 \(p, q, r\) 都为真时,上述论说形式的前提为真而结论为假。所以,该论说形式是无效的。(本例中,作为蕴涵式后件的 \(q \lor \neg r\) 为真,则蕴涵式 \(p \rightarrow q \lor \neg r\) 一定为真,这与 \(p\) 的真值无关。)见下表:

\[ \begin{array}{c|ll|c|c} \text{步骤} & p \rightarrow q \lor \neg r, & r \land q \rightarrow p & /\therefore r \rightarrow \neg q & \text{步骤解说} \\ \hline 1 & ~~~~1 & ~~~~~~~~~~1 & ~~~~0 & \text{假设论证形式无效}\\[0.4ex] 2 & & & ~~~~~~~~1~~~~~~~~1 & \text{推得结论中} ~ r, q ~ \text{真值}\\[0.4ex] 3 &~~~~~~~~~~~1 & & & \text{推得前提中} ~q \lor \neg r~ \text{真值}\\[0.4ex] 4 & & ~~~1~~~~~1~~1& & \text{设} ~ p ~ \text{真,则} ~r \land q \rightarrow p~ \text{真}\\[0.4ex] 5 &~~~~1 & ~~~~~~~~~~1& ~~~~0 & \text{存在前提都真而结论假}\\ \end{array} \]

由于重言蕴涵和有效论说形式是「一回事」,所以我们就不再单独讨论如何用简化真值表方法判定一个公式集是否重言蕴涵某个公式。

要说明一个公式是重言式,我们可以假设它为假,再试图说明这不可能;而一旦这个假设没有导致矛盾,那么我们就会得到命题变号的一个可能取值组合,使得给定公式为假。类似地,要说明一个公式是矛盾式,我们可以假定它是真的,再试图说明这不可能;而一旦这个假设没有导致矛盾,那么我们就会得到命题变号的一个可能取值组合,使得给定公式为真。如果假设一公式为真没有导致矛盾,并且假设它为假也没有导致矛盾,那么该公式就一定是或然式。

例 3.48 \(\varphi\), \(\psi\), \(\chi\) 为任意公式。用简化真值表方法说明公式 \((\varphi \rightarrow \psi \wedge \chi) \rightarrow(\varphi \rightarrow \psi) \wedge(\varphi \rightarrow \chi)\) 是重言式。

Solution: 前几个例子中,每个公式的真值都足以确定它的直接子公式的真值。本例则不同。见下表:

\[ \begin{array}{c|l|c|c|c} \text{步骤} & (\varphi \rightarrow \psi \wedge \chi) & \rightarrow & (\varphi \rightarrow \psi) \wedge(\varphi \rightarrow \chi) & \text{步骤解说} \\ \hline 1 & ~~~~~~\mathbf{\color{red}1} & 0 & 0 & \text{假设重言式无效}\\[0.4ex] 2.1 &~1~~~~~~~0 & & ~1~~0~~0~~~~~~~~~~~~~~~~~~~~~ & \text{若} ~\varphi \rightarrow \psi~ \text{为假}\\[0.4ex] 2.2 &~~~~~~\mathbf{\color{red}0} & && \text{前提} ~\varphi \rightarrow \psi \wedge \chi~ \text{假}\\[0.4ex] 3.1 &~1~~~~~~~~~~~~~0 & & ~~~~~~~~~~~~~~~~~~~~1~~0~~0 & \text{若} ~\varphi \rightarrow \chi~ \text{为假}\\[0.4ex] 3.2 &~~~~~~\mathbf{\color{red}0} & & & \text{前提} ~\varphi \rightarrow \psi \wedge \chi~ \text{假}\\ \end{array} \]

如果上述蕴涵式是假的,它的前件一定是真的而后件一定是假的;然而,该前件的真不足以确定其直接子公式 \(\varphi\)\(\psi \land \chi\) 的真值,并且该后件的假也不足以确定其直接子公式 \(\varphi \rightarrow \psi\)\(\varphi \rightarrow \chi\) 的真值。所以,需要分两种情况讨论。后件是合取式,而合取式为假的情况有两种。两种情形皆导致矛盾,所以,上述公式一定是重言式。
例 3.49 用简化真值表方法说明下列公式是矛盾式: \((\neg(p \rightarrow r) \land (q \rightarrow \neg p)) \land (\neg q \rightarrow \neg p).\)

Solution: 有时,经验可以帮助我们避免「分情况讨论」的复杂局面。见下表:

\[ \begin{array}{c|lcc|c|c} \text{步骤} &(\neg(p \rightarrow r)& \land & (q \rightarrow \neg p)) & \land & (\neg q \rightarrow \neg p) \\ \hline 1 & &1 & & \mathbf{1}& 1\\[0.4ex] 2 &~1~~~~~~0 & &1~~~~ & & \\[0.4ex] 3 & ~~~~~~1 & & ~~~~0 & &~~~~~~~~~0 \\[0.4ex] 4 & & & \mathbf{0}~~~~~~~~~~~~ & &\mathbf{1}~~~~~~ \end{array} \]

假设上述合取式是真的,最终推得 \(q\) 既真又假,但这是不可能的。所以,上述公式一定是矛盾式。

在例 3.49 中,我们的思路是:在已确定 \(\neg(p \rightarrow r), q \rightarrow \neg p, \neg q \rightarrow \neg p\) 都为真时,选择蕴涵式的否定 \(\neg(p \rightarrow r)\) 来进一步求得蕴涵式前件 \(p\) 的真值 1. 假如我们选择的是蕴涵式 \(q \rightarrow \neg p\)\(\neg q \rightarrow \neg p\),那么我们就不得不分情况讨论,因为当时只能得到:或者其前件是假的或者其后件是真的。显然,选择 \(\neg(p \rightarrow r)\) 以求得 \(p\) 的真值 1,使我们避免了「分情况讨论」的复杂局面。这里运用了下述「经验规则」:

如果在某一步骤中得到 \(\neg (\varphi \lor \psi)\)\(\neg (\varphi \rightarrow \psi)\) 的真值为 1(或得到 \(\varphi \lor \psi\)\(\varphi \rightarrow \psi\) 的真值为 0),先用这一信息求得子公式 \(\varphi\)\(\psi\) 的真值。这样做往往可以简化确定其他子公式真值的过程。

运用简化真值表的方法,我们同样可以说明一个公式是或然式、非重言式或者非矛盾式等。具体例子省略,请读者去做练习。

第三章开始学习写证明。简化真值表方法虽然并不就是写证明,但它们的思路有时是类似的。从现在起应注意与证明有关的问题。

3.7 本章习题

练习 3.1 (说明下列联结词不是真值函数联结词)

  1. 因为\(\underline{\hspace{3em}}\),所以\(\underline{\hspace{3em}}\)
  2. 可以想像\(\underline{\hspace{3em}}\)
  3. 昨天\(\underline{\hspace{3em}}\)
  4. 张三相信\(\underline{\hspace{3em}}\)
  5. 李四认为\(\underline{\hspace{3em}}\)
  6. 王五知道\(\underline{\hspace{3em}}\)
  7. 政客们喜欢说\(\underline{\hspace{3em}}\)
  8. 从平民的角度看\(\underline{\hspace{3em}}\)

练习 3.2 (给出「辞典」,并将下列语句符号化)

  1. 不是所有的人都讲道理。
  2. 如果在选举时你不去投票,那么你就要忍受我选的白痴。
  3. 张三是李四的祖先当且仅当李四是张三的后代。
  4. 除非有奇迹出现,中国足球队 500 年内挤不进世界 16 强。
  5. 张三只有坚持锻炼才会有好身体;但并非只要他坚持锻炼就会有好身体。
  6. 如果张三一进大学就知道自己想做什么,那么,他大学期间不会浪费太多时间,而他的学习成绩也不会太差。
  7. 要么明天有海战,要么明天没有海战;但明天不必然有海战,而且明天也不必然没有海战。

练习 3.3 (给出「辞典」,将下列论说符号化,判断是否有效并给出理由)

  1. 如果今天是星期三,那么明天有逻辑课。因此,如果明天没有逻辑课,则今天不是星期三。
  2. 要么士兵拿破仑想当将军,要么士兵拿破仑不想当将军。如果士兵拿破仑想当将军,那么他不是一个好士兵。如果士兵拿破仑不想当将军,那么他也不是一个好士兵。所以,士兵拿破仑不是一个好士兵。
  3. 或者逻辑难学,或者没有多少学生喜欢它。如果数学容易学,那么逻辑不难学。因此,如果许多学生喜欢逻辑,那么数学并不容易学。
  4. 如果上帝死了,那么做什么坏事情都是可以的。如果做什么坏事情都是可以的,那么我考试作弊也是可以的。所以,如果上帝死了,我考试作弊是可以的。
  5. 花都是红的当且仅当李四不是色盲。花不都是红的。所以李四是色盲。
  6. 如果 \(a\) 是正整数,则 \(a\) 有唯一的后继,并且 \(a\) 有唯一的前驱。\(a\) 要么并非有唯一的后继,要么并非有唯一的前驱。所以 \(a\) 不是正整数。
  7. 如果我相信上帝,则如果上帝是存在的,我就有所得;如果上帝不存在,我也无所失。另一方面,如果我不相信上帝,则如果上帝存在,我有所失;如果上帝不存在,我无所得。因此,我如果相信上帝,我或者有所得,或者无所失;而如果我不相信上帝,则我或者有所失,或者无所得。
  8. 分析示例 32.1(P.427)中荆王免去士兵死罪的推理过程,并加以符号化。

练习 3.4 (填写空格,使下列命题都成立)

  1. 一个否定式是假的当且仅当\(\underline{\hspace{5em}}\)
  2. 一个合取式是假的当且仅当\(\underline{\hspace{5em}}\)
  3. 一个析取式是假的当且仅当\(\underline{\hspace{5em}}\)
  4. 一个蕴涵式是假的当且仅当\(\underline{\hspace{5em}}\)
  5. 一个等值式是假的当且仅当\(\underline{\hspace{5em}}\)

练习 3.5 (给出下列公式的真值表)

  1. \(\neg \neg p \rightarrow p\)
  2. \(p \rightarrow(\neg p \rightarrow q)\)
  3. \(p \rightarrow p \wedge q\)
  4. \(p \wedge q \rightarrow p \vee q\)
  5. \(p \vee q \rightarrow p \wedge q\)
  6. \(p \vee q \rightarrow \neg(p \rightarrow q\)
  7. \(p \wedge q \rightarrow \neg(p \rightarrow \neg q)\)
  8. \((p \rightarrow q) \rightarrow \neg(\neg q \rightarrow \neg p)\)
  9. \(\neg(p \vee q) \rightarrow \neg p \wedge \neg q\)
  10. \(\neg(p \wedge q) \rightarrow \neg p \vee \neg q\)
  11. \((p \rightarrow q) \vee(q \rightarrow p)\)
  12. \((\neg p \rightarrow q) \rightarrow((\neg p \rightarrow \neg q) \rightarrow p)\)
  13. \((p \rightarrow(q \rightarrow r)) \rightarrow((r \rightarrow q) \rightarrow(r \rightarrow p))\)
  14. \((p \leftrightarrow q) \leftrightarrow \neg(p \wedge q) \vee \neg(\neg p \wedge \neg q)\)
  15. \((p \vee q) \wedge(p \vee r) \rightarrow p \vee(q \wedge r)\)

练习 3.6 (判断下列说法的对错,并说明理由)

  1. 任一公式都或者是重言式,或者是矛盾式,或者是或然式;并且只能是这三种公式中的一种。
  2. 对任意公式集 \(\Gamma\) 和任意公式 \(\varphi\)\(\Gamma\) 或者重言蕴涵 \(\varphi\) 或者重言蕴涵 \(\neg \varphi\)
  3. 对任意公式 \(\varphi\)\(\psi\)\(\varphi\) 或者与 \(\psi\) 重言等价或者与 \(\neg \psi\) 重言等价。
  4. 对任意公式 \(\varphi\),或者 \(\varphi\) 可满足或者 \(\neg \varphi\) 可满足。

练习 3.7 (判断下列说法的对错) 在每个括号中画 \(\checkmark\) 或 ✗ 分别表明「可以是」和「一定不是」,并思考原因。如或然式与或然式的合取:(✗)重言式,(\(\checkmark\))矛盾式,(\(\checkmark\))或然式。它相当于说:或然式与或然式的合取可以是矛盾式,也可以是或然式,但一定不是重言式。(当然,如果正确的画法中有两个 ✗,那么第三个一定是画 \(\checkmark\),而且画 \(\checkmark\) 的地方一定可以读作「一定是」。想想为什么是这样。

  1. 重言式与重言式的析取:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  2. 重言式与矛盾式的析取:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  3. 重言式与或然式的析取:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  4. 以重言式为前后件的蕴涵式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  5. 以重言式为前件、矛盾式为后件的蕴涵式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  6. 以重言式为前件、或然式为后件的蕴涵式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  7. 以矛盾式为前、后件的蕴涵式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  8. 以矛盾式为前件、重言式为后件的蕴涵式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  9. 以矛盾式为前件、或然式为后件的蕴涵式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  10. 以或然式为前后件的蕴涵式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  11. 以或然式为前件、重言式为后件的蕴涵式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  12. 以或然式为前件、矛盾式为后件的蕴涵式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  13. 两端都是重言式的等值式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  14. 两端分别是重言式和矛盾式的等值式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  15. 两端分别是重言式和或然式的等值式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  16. 两端都是矛盾式的等值式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  17. 两端分别是矛盾式和或然式的等值式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。
  18. 两端都是或然式的等值式:(\(\underline{\hspace{1em}}\))重言式,(\(\underline{\hspace{1em}}\))矛盾式,(\(\underline{\hspace{1em}}\))或然式。

练习 3.8 \(\varphi\)\(\psi\) 为任意公式。判断下列命题的真假:

  1. \(\varphi \land \psi\) 是重言式当且仅当 \(\varphi\) 是重言式且 \(\psi\) 是重言式。
  2. \(\varphi \lor \psi\) 是重言式当且仅当或者 \(\varphi\) 是重言式或者 \(\psi\) 是重言式。
  3. \(\varphi \rightarrow \psi\) 是重言式当且仅当如果 \(\varphi\) 是重言式那么 \(\psi\) 是重言式。
  4. \(\varphi \leftrightarrow \psi\) 是重言式当且仅当或者 \(\varphi\)\(\psi\) 都是重言式或者 \(\varphi\)\(\psi\) 都不是重言式。
  5. \(\varphi\) 是重言式当且仅当 \(\neg \varphi\) 不是重言式。
  6. \(\varphi \land \psi\) 是矛盾式当且仅当 \(\varphi\) 是矛盾式且 \(\psi\) 是矛盾式。
  7. \(\varphi \lor \psi\) 是矛盾式当且仅当或者 \(\varphi\) 是矛盾式或者 \(\psi\) 是矛盾式。
  8. \(\varphi \rightarrow \psi\) 是矛盾式当且仅当如果 \(\varphi\) 是矛盾式那么 \(\psi\) 是矛盾式。
  9. \(\varphi \leftrightarrow \psi\) 是矛盾式当且仅当或者 \(\varphi\)\(\psi\) 都是矛盾式或者 \(\varphi\)\(\psi\) 都不是矛盾式。
  10. \(\varphi\) 是矛盾式当且仅当 \(\neg \varphi\) 不是矛盾式。
  11. \(\varphi \land \psi\) 是或然式当且仅当 \(\varphi\) 是或然式且 \(\psi\) 是或然式。
  12. \(\varphi \lor \psi\) 是或然式当且仅当或者 \(\varphi\) 是或然式或者 \(\psi\) 是或然式。
  13. \(\varphi \rightarrow \psi\) 是或然式当且仅当如果 \(\varphi\) 是或然式那么 \(\psi\) 是或然式。
  14. \(\varphi \leftrightarrow \psi\) 是或然式当且仅当或者 \(\varphi\)\(\psi\) 都是或然式或者 \(\varphi\)\(\psi\) 都不是或然式。
  15. \(\varphi\) 是或然式当且仅当 \(\neg \varphi\) 不是或然式。

练习 3.9 \(\varphi\)\(\psi\) 为任意公式。在每个括号中画 \(\checkmark\) 或 ✗ 表明「对」和「错」

  1. 如果 \(\varphi \leftrightarrow \psi\) 是重言式,那么 \(\varphi\) 是重言式当且仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  2. 如果 \(\varphi \leftrightarrow \psi\) 是重言式,那么 \(\varphi\) 是矛盾式当且仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  3. 如果 \(\varphi \leftrightarrow \psi\) 是重言式,那么 \(\varphi\) 是或然式当且仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  4. 如果 \(\varphi \leftrightarrow \psi\) 是矛盾式,那么 \(\varphi\) 是重言式当且仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  5. 如果 \(\varphi \leftrightarrow \psi\) 是矛盾式,那么 \(\varphi\) 是矛盾式当且仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  6. 如果 \(\varphi \leftrightarrow \psi\) 是矛盾式,那么 \(\varphi\) 是或然式当且仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  7. 如果 \(\varphi \leftrightarrow \psi\) 是或然式,那么。\(\varphi\) 是重言式当且仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  8. 如果 \(\varphi \leftrightarrow \psi\) 是或然式,那么 \(\varphi\) 是矛盾式当且仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  9. 如果 \(\varphi \leftrightarrow \psi\) 是或然式,那么 \(\varphi\) 是或然式当且仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。

练习 3.10 \(\varphi\)\(\psi\) 为任意公式。在每个括号中画 \(\checkmark\) 或 ✗ 表明「对」和「错」:

  1. 如果 \(\varphi \rightarrow \psi\) 是重言式,那么 \(\varphi\) 是重言式仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  2. 如果 \(\varphi \rightarrow \psi\) 是重言式,那么 \(\varphi\) 是矛盾式仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  3. 如果 \(\varphi \rightarrow \psi\) 是重言式,那么 \(\varphi\) 是或然式仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  4. 如果 \(\varphi \rightarrow \psi\) 是矛盾式,那么 \(\varphi\) 是重言式仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  5. 如果 \(\varphi \rightarrow \psi\) 是矛盾式,那么 \(\varphi\) 是矛盾式仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  6. 如果 \(\varphi \rightarrow \psi\) 是矛盾式,那么 \(\varphi\) 是或然式仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  7. 如果 \(\varphi \rightarrow \psi\) 是或然式,那么。\(\varphi\) 是重言式仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  8. 如果 \(\varphi \rightarrow \psi\) 是或然式,那么 \(\varphi\) 是矛盾式仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
  9. 如果 \(\varphi \rightarrow \psi\) 是或然式,那么 \(\varphi\) 是或然式仅当 \(\psi\) 是重言式(\(\underline{\hspace{1em}}\)),矛盾式(\(\underline{\hspace{1em}}\)),或然式(\(\underline{\hspace{1em}}\))。
练习 3.11 说明怎样用简化真值表方法证明一个公式重言蕴涵另一个公式,或重言等值于另一个公式。

在以下习题中,对所有公式 \(\varphi\)\(\psi\),我们以 \(\varphi \vDash_0 \psi\) 表示 \(\varphi\) 重言蕴涵 \(\psi\),以 \(\varphi_0,...,\varphi_n\) 表示 \(\lbrace \varphi_0,...,\varphi_n\rbrace\) 重言蕴涵 \(\psi\)

练习 3.12 \(\varphi, \psi, \chi\) 为任意公式。用(简化)真值表说明下列命题都成立:

  1. \(\varphi \vDash_{0} \varphi\)
  2. \(\psi \vDash_{0} \varphi \vee \psi\)
  3. \(\varphi, \psi \vDash_{0} \varphi \wedge \psi\)
  4. \(\varphi \vDash_{0} \varphi \rightarrow \varphi\)
  5. \(\varphi \vDash_{0} \psi \rightarrow \varphi\)
  6. \(\varphi, \varphi \rightarrow \psi \vDash_{0} \psi\)
  7. \(\psi, \neg \psi \vDash_{0} \varphi\)
  8. \(\varphi \vee \psi, \neg \psi \vDash_{0} \varphi\)
  9. \(\neg(\varphi \rightarrow \neg \psi) \vDash_{0} \varphi\)
  10. \(\neg(\varphi \rightarrow \neg \psi) \vDash_{0} \psi\)
  11. \(\varphi \rightarrow \neg \psi, \psi \vDash_{0} \neg \varphi\)
  12. \(\varphi \rightarrow \psi, \chi \rightarrow \varphi \vDash_{0} \chi \rightarrow \psi\)
  13. \(\varphi \wedge \psi \vDash_{0} \psi \wedge \varphi\)
  14. \(\varphi \vee \psi \vDash_{0} \psi \vee \varphi\)
  15. \(\varphi \wedge \psi \vDash_{0} \varphi \vee \psi\)
  16. \((\varphi \rightarrow \varphi) \rightarrow \psi \vDash_{0} \psi\)
  17. \(\neg \varphi \wedge \neg \psi \vDash_{0} \neg(\varphi \vee \psi)\)
  18. \(\neg \varphi \vee \neg \psi \vDash_{0} \neg(\varphi \wedge \psi)\)
  19. \(\varphi \leftrightarrow \psi, \varphi \vDash_{0} \psi\)
  20. \(\varphi \leftrightarrow \psi, \psi \vDash_{0} \varphi\)

练习 3.13 \(\varphi, \psi\) 为任意公式。用(简化)真值表说明下列每一组中的公式都是重言等值的:

  1. \(\varphi \rightarrow \psi, \neg \varphi \vee \psi, \neg(\varphi \wedge \neg \psi)\)
  2. \(\varphi \vee \psi, \neg(\neg \varphi \wedge \neg \psi), \neg \varphi \rightarrow \psi\)
  3. \(\varphi \wedge \psi, \neg(\neg \varphi \vee \neg \psi), \neg(\varphi \rightarrow \neg \psi)\)
  4. \(\varphi \leftrightarrow \psi,(\varphi \rightarrow \psi) \wedge(\psi \rightarrow \varphi),(\varphi \wedge \psi) \vee(\neg \varphi \wedge \neg \psi)\)

练习 3.14 用(简化)真值表说明下列各命题都不成立:

  1. \(p \vDash_{0} p \wedge q\)
  2. \(p \vee q \vDash_{0} p\)
  3. \(p \rightarrow q, q \vDash_{0} p\)
  4. \(p \rightarrow q \vDash_{0} q\)
  5. \(p \wedge q \vDash_{0}(p \rightarrow r) \wedge(q \rightarrow r)\)
  6. \(p \vee q \vDash_{0}(p \rightarrow r) \vee(q \rightarrow r)\)
  7. \(p \leftrightarrow q \vDash_{0} p\)
  8. \(p \leftrightarrow q \vDash_{0} q\)

练习 3.15 用(简化)真值表说明具有下列形式的公式都是重言式:

  1. \(\varphi \leftrightarrow \neg \neg \varphi\)
  2. \(\varphi \rightarrow(\psi \rightarrow \varphi)\)
  3. \(\varphi \rightarrow(\neg \varphi \rightarrow \psi)\)
  4. \(\neg \varphi \rightarrow \neg(\varphi \wedge \psi)\)
  5. \(\neg \psi \rightarrow \neg(\varphi \wedge \psi)\)
  6. \(\neg(\varphi \vee \psi) \leftrightarrow \neg \varphi \wedge \neg \psi\)
  7. \(\neg(\varphi \wedge \psi) \leftrightarrow \neg \varphi \vee \neg \psi\)
  8. \(\neg(\neg \varphi \rightarrow \psi) \rightarrow \neg \varphi\)
  9. \(\neg(\neg \varphi \rightarrow \psi) \rightarrow \neg \psi\)
  10. \((\varphi \rightarrow \psi) \rightarrow((\varphi \rightarrow \neg \psi) \rightarrow \neg \varphi)\)
  11. \((\varphi \leftrightarrow \psi) \rightarrow(\psi \leftrightarrow \varphi)\)
  12. \((\varphi \leftrightarrow(\psi \leftrightarrow \chi)) \leftrightarrow((\varphi \leftrightarrow \psi) \leftrightarrow \chi)\)
  13. \(\varphi \vee\left(\psi_{0} \wedge \cdots \wedge \psi_{k}\right) \leftrightarrow\left(\varphi \vee \psi_{0}\right) \wedge \cdots \wedge\left(\varphi \vee \psi_{k}\right)\)
  14. \(\varphi \wedge\left(\psi_{0} \vee \cdots \vee \psi_{k}\right) \leftrightarrow\left(\varphi \wedge \psi_{0}\right) \vee \cdots \vee\left(\varphi \wedge \psi_{k}\right)\)

练习 3.16 用(简化)真值表说明具有下列形式的公式都是矛盾式:

  1. \(\varphi \wedge \neg(\neg \varphi \rightarrow \psi)\)
  2. \((\varphi \rightarrow \neg \varphi) \wedge(\neg \varphi \rightarrow \varphi)\)
  3. \((\varphi \vee \psi) \wedge(\neg \varphi \wedge \neg \psi)\)
  4. \(\neg(\varphi \rightarrow \psi) \wedge \neg(\psi \rightarrow \varphi)\)
  5. \((\neg \varphi \rightarrow \neg \psi) \wedge \neg((\neg \varphi \rightarrow \psi) \rightarrow \varphi)\)
  6. \((\varphi \rightarrow(\psi \rightarrow \chi)) \wedge \neg((\varphi \rightarrow \psi) \rightarrow(\varphi \rightarrow \chi))\)
  7. \((\varphi \leftrightarrow \psi) \leftrightarrow(\neg \varphi \leftrightarrow \psi)\)
  8. \((\varphi \leftrightarrow \psi) \leftrightarrow(\varphi \leftrightarrow \neg \psi)\)

练习 3.17 用(简化)真值表说明具有下列形式的公式都是或然式:

  1. \(\varphi \rightarrow \psi\)
  2. \(\varphi \rightarrow \neg \neg \neg \varphi\)
  3. \((\psi \rightarrow \psi) \rightarrow \varphi\)
  4. \(\neg \varphi \rightarrow \neg(\varphi \vee \psi)\)
  5. \(\neg \psi \rightarrow \neg(\varphi \vee \psi)\)
  6. \((\neg \varphi \rightarrow \psi) \rightarrow((\varphi \rightarrow \psi) \rightarrow \neg \psi)\)
  7. \((\varphi \leftrightarrow \psi) \rightarrow \varphi \wedge \psi\)
  8. \((\varphi \leftrightarrow \psi) \rightarrow \neg \varphi \wedge \neg \psi\)

练习 3.18 \(\Gamma = \lbrace \varphi_0,...,\varphi_n\rbrace\) 为任意的有穷公式集,\(\varphi\) 为任意公式。给出下列命题成立的理由:

  1. 如果 \(\Gamma\) 可满足,那么对任何公式集 \(\Delta\)\(\Gamma \cap \Delta\)也可满足;
  2. 如果 \(\Gamma\) 不可满足,那么对任何有穷公式集 \(\Delta\)\(\Gamma \cup \Delta\)也不可满足;
  3. \(\Gamma \cup \lbrace \neg \varphi \rbrace\) 不可满足当且仅当 \(\Gamma\) 重言蕴涵 \(\varphi\)
  4. 对任意 \(i \leqslant n\)\(\Gamma\) 不可满足当且仅当 \(\Gamma - \lbrace \psi_i \rbrace\) 重言蕴涵\(\neg \psi_i\)
  5. 如果 \(\Gamma\) 不可满足,那么 \(\Gamma\) 重言蕴涵 \(\varphi\)
  6. 如果 \(\neg \varphi\) 不可满足,那么 \(\Gamma\) 重言蕴涵 \(\varphi\)
  7. 如果 \(\Gamma\) 重言蕴涵 \(\varphi\),并且 \(\Gamma\) 可满足,那么 \(\varphi\) 也可满足;
  8. 如果 \(\Gamma\) 重言蕴涵 \(\varphi\) 并且 \(\Gamma\) 重言蕴涵 \(\neg \varphi\),那么 \(\Gamma\) 不可满足。

练习 3.19 \(\varphi, \psi, \varphi_0,...,\varphi_n\) 为任意公式且 \(\Gamma = \lbrace \varphi_0,...,\varphi_n\rbrace\)。给出下列命题成立的理由:

  1. \(\varphi\) 重言蕴涵 \(\psi\) 当且仅当 \(\varphi \rightarrow \psi\) 是重言式;
  2. \(\varphi\) 重言等值于 \(\psi\) 当且仅当 \(\varphi \leftrightarrow \psi\) 是重言式,当且仅当 \(\psi \rightarrow \varphi\)\(\varphi \rightarrow \psi\) 都是重言式;
  3. \(\Gamma\) 重言蕴涵 \(\psi\) 当且仅当 \(\varphi_0 \land \cdots \land \varphi_n \rightarrow \psi\) 是重言式;
  4. \(\varphi_0 \land \cdots \land \varphi_n \rightarrow \psi\)\(\varphi_0 \land \cdots \land \varphi_{n-1} \rightarrow (\varphi_n \rightarrow \psi)\) 重言等值;(\(n \geqslant 1\)
  5. 如果 \(\varphi\) 是重言式,那么 \(\Gamma\) 重言蕴涵 \(\varphi\)
  6. \(\Gamma\) 可满足当且仅当 \(\varphi_0 \land \cdots \land \varphi_n\) 或者是或然式或者是重言式;
  7. \(\Gamma\) 不可满足当且仅当 \(\varphi_0 \land \cdots \land \varphi_n\) 是矛盾式;
  8. 如果 \(\varphi\) 是重言式,那么 \(\Gamma\) 是可满足的当且仅当 \(\Gamma \cup \lbrace \varphi \rbrace\) 是可满足的;
  9. 如果 \(\varphi_i (i \leqslant n)\) 是重言式,那么 \(\Gamma\) 是可满足的当且仅当 \(\Gamma - \lbrace \varphi_i \rbrace\) 是可满足的;
  10. 如果 \(\varphi\) 是矛盾式,那么 \(\Gamma \cup \lbrace \varphi \rbrace\) 是不可满足的;
  11. 如果 \(\varphi_i (i \leqslant n)\) 是矛盾式,那么 \(\Gamma\) 是不可满足的。

练习 3.20 将下列公式改写为使用波兰学派记法的公式。完成后,不看下列公式,把那些使用波兰学派记法的公式再改写成我们这个语言的公式,然后再和下列公式对照:

  1. \(p \rightarrow q \vee p\)
  2. \(p \rightarrow((p \rightarrow q) \rightarrow q)\)
  3. \(p \wedge \neg(\neg p \rightarrow q)\)
  4. \((p \rightarrow \neg p) \wedge(\neg p \rightarrow p)\)
  5. \((p \vee q) \wedge(\neg p \wedge \neg q)\)
  6. \(\neg(p \rightarrow q) \wedge \neg(q \rightarrow p)\)
  7. \((q \rightarrow q) \rightarrow p\)
  8. \(q \wedge \neg q \rightarrow p\)
  9. \((p \vee q) \wedge \neg q \rightarrow p\)
  10. \((q \rightarrow \neg p) \rightarrow(p \rightarrow \neg q)\)
  11. \((r \rightarrow(p \rightarrow q)) \rightarrow((r \rightarrow p) \rightarrow(r \rightarrow q))\)
  12. \(\neg p \wedge \neg q \rightarrow \neg(p \vee q)\)
  13. \(\neg p \vee \neg q \rightarrow \neg(p \wedge q)\)
  14. \((\neg p \rightarrow \neg q) \wedge \neg((\neg p \rightarrow q) \rightarrow p)\)
  15. \((p \rightarrow(q \rightarrow r)) \wedge \neg((p \wedge q) \rightarrow(p \vee r))\)
  16. \((p \leftrightarrow q) \rightarrow(\neg p \vee \neg q)\)
  17. \((\neg p \vee q) \rightarrow(p \wedge q \rightarrow \neg q)\)
  18. \((p \leftrightarrow q) \rightarrow \neg q \wedge \neg p\)



Editorial comments

有屁请在此处放,看看谁的屁更响。