《逻辑学基础教程》版课件-第十章 命题逻辑

第十章命题逻辑

第一章命题逻辑

第一节命题逻辑概述

命题逻辑是数理逻辑的基础部分。它以简单命题为单位，研究命题经逻辑联结词构成的复合命题的逻辑性质以及关于复合命题之间的推理关系。概括地说，它研究逻辑联结词的逻辑性质和相应的推理关系。在命题逻辑中，研究命题时，只将命题分析到简单命题为止，对于简单命题中所包含的其他成分不再做分析。在命题逻辑中，重言式

（取值总为真的命题）为数无穷，它们表达了命题逻辑的逻辑规律。弄清这些重言式，对于掌握命题逻辑具有极为重要的意义。为了系统地掌握和研究这些逻辑规律，通常是将全部重言式包括在一个系统之中，用公理化的方法将全部命题逻辑规律系统化，从而得到一个形式系统。这个形式系统就是命题逻辑的公理系统，即命题演算。为了介绍命题逻辑的公理系统，

这一节我们需要下面的一些知识。一、命题逻辑联结词

一个有真假的语句称为命题。凡与客观情况符合的命题叫做真命题，否则称为假命题。如：

5是偶数。王楠是一个乒乓球运动员。

这些都是命题。其中“王楠是一个乒乓球运动员”与客观事实相符合，我们称它为一个真命题。而“5是偶数”与客观事实不符合，我们称它为一个假命题。如果我们令p、q等代表命题，并称它们为命题变项，那么，p可以表示“王楠是一个乒乓球运动员”，也可以表示“5是偶数”。命题变项取值的集合是｛真，假｝——真值的集合。即

真和假统称为真值。亦即真是真值，假也是真值。如果一个命题能正确反映客观世界，它就是真命题并取真值。否则，它就是假命题并取假值。在下面的讨论中，我们将撇开命题的其他属性，只把命题看作或真或假的语句。一般说来，一个命题，如果其中不再包含其他的命题成分，那么就称它为简单命题。例如，在前面所举的几个

命题中，“王楠是一个乒乓球运动员”，“5是偶数”等都是简单命题。一个命题，如果其中至少包含有一个其他命题，那么就称他为复合命题。如“2是素数并且3也是素数”，“并非3是偶数”等等，这些都是复合命题。前一个例子中包含两个简单命题，即“2是素数”和“3也是素数”。后面的例子中包含一个简单命题，即“3是偶数”。组成复合命题的那些命题叫作复合命题的支命题。

把几个支命题联结起来从而构成一个复合命题的词项叫做真值联结词。在该课程中，经常用到的真值联结词一共有五个。它们是：否定词（并非）、合取词（并且）、析取词（或）、蕴涵词（如果，则）和等值词（当且仅当）。关于其他联结词与日常语言中对应的联结词之间的区别，我们不再讨论。由于这五个联结词反映了思维中经常

出现的五种复合命题的真假关系，所以我们把这五个联结词叫做基本的真值联结词。由它们构成的真值形式分别叫做否定式（即：┑p,读作：并非p）、合取式（即：p

q，读作：p并且q）、析取式（即：p

q，读作：p或者q）、蕴涵式（即：p

q，读作：p蕴涵q）和等值式（即：p

q，读作：p等值于q）。它们所对应的真值表如下：

p┑p

真假假真pqp

qp

qp

qp

q真真真真真真真假假真假假假真假真真假假假假假真真二、真值形式

（一）真值形式任一真值形式都是由前面给出的五个真值联结词和五个基本的真值形式经过各种各样的相互组合所构成。反过来，利用五个真值联结词和五个基本的真值形式，我们可以构造出各种各样复杂的复合命题形式，即真值形式。这些命题形式

表达了所有的复合命题。对于复合命题的结构和逻辑特征的研究就可以归结到对这些复合命题的形式结构和逻辑规律的研究。下面给出一些稍复杂的真值形式的例子。例1┑（p

q）。它表示：并非，p并且q。例2（┑q

┑p）。

它表示：如果非q，那么非p。例3（（p

q）

r）。它表示：如果p或q，那么r。例4（p

┑p）。它表示：p或非p。这是传统逻辑中排中律的形式结构。例5（p

q）

（q

p）。它表示：p且q，等值于，q且p。

还可以给出更多和更复杂的例子。但是更复杂的例子不容易解释，我们不再讨论了。一个具体的复合命题，不论它多么复杂，都有其形式结构，也都有相应的命题形式。如何求一个具体的复合命题的命题形式？下面将通过两个例子来说明。

例6某城市只有处理好污水，某城市才能搞好环境卫生。这是一个必要条件假言命题。解：令p：某城市能处理好污水；

q：某城市能搞好环境卫生。上面的命题可以表示为：只有p才q。这等于说，某城市不能处理好污水，那么某城市就不能搞好环境卫生。与此相应的命题形式为：（┑p

┑q）。

例7要么x＜y，要么x＞y，要么x=y。（这里x，y∈Q，Q是有理数集）这是一个不相容的析取命题。解：这个命题等于说：或者x＜y，或者x＞y，或者x=y，但是三者不能同时为真。与此相应的命题形式为：（（p

┑q

┑r）

（┑p

q

┑r）

（┑p

┑q

r））。这里，我们假设p：x＜y，q：x＞y，r：x=y。

综合例6和例7，求一个复合命题的命题形式，需要注意两点：第一，确定组成这个复合命题的命题成分即支命题，把不同的支命题代以不同的命题变项；第二，撇开语言方面比较丰富的内容，撇开支命题之间各种具体内容的关系，只以真假关系来分析给定的复合命题和它所含的支命题之间的联系，然后用五个真值联结词把命题变项联结起来，从而表示该复合命题与所含支命题之间的真假联系。

在求一个复合命题的真值形式时，我们使用了括号。括号是用来表示复合命题形式中结构关系的，括号内的命题形式是该复合命题形式的一个独立单位。为了以后讨论方便，我们约定最外层的一对括号可以省略。对于连续出现的→，我们采用右结合法。真值联结词的结合力依下列次序递增：

，

，

，

，┑。

(二)真值表方法

前面，我们曾用真值表给出了五个联结词的定义。这些真值表说明了相应的复合命题与所含支命题之间真假的关系，它们只是一些简单的形式。对于任一复杂的复合命题形式，我们可以利用五个基本联结词的真值表做出与其复合命题形式相应的真值表，从而说明它与所含的支命题之间的真假关系。任一复合命题，它的真值形式

都是由简单命题和五个联结词，经过有限次的各种各样的联结而逐步构成的。构成过程由简单到复杂，最后得到所要构成得形式。构造真值表的方法和真值形式的构成过程有密切的联系。（1）求作复杂命题形式的真值表真值表的构成包括以下三个步骤：1.找出给定形式里的所有简单命题，根据构成过程，由简而繁地将该形式

地各个组成部分排成一行，最后一个为此形式本身,从而决定该真值表的列数。2.列出该形式的所有简单命题的各个取真假值的情况，从而决定真值表的行数。3.根据五个联结词的真值表，求出各个组成部分的真值，最后列出此形式的真值。例：求作┑（p

q）的真值表。解：

pqp

q┑（p

q）真真真假真假假真假真假真假假假真例：求作（┑q

┑p）的真值表。解：

pq┑p┑q┑q

┑p

真真假假真真假假真假假真真假真假假真真真例：求作（p

q）

（q

p）的真值表。解：pqp

qq

p（p

q）

（q

p）真真真真真真假假假真假真假假真假假假假真例:求作：p

q

┑（┑p

┑q）的真值表。解：pq┑p┑q┑p

┑q┑（┑p

┑q）p

q

真真假假假真真真真假假真假真真真假真真假假真真真假假真真真假假真（2）联结词的完备性①｛┑，

｝是完备的。pq┑p┑q┑p

┑q┑（┑p

┑q）p

q真真假假假真真真假假真假真真假真真假假真真假假真真真假假∴p

q=df┑（┑p

┑q）

pq┑qp

┑q┑（p

┑q）p

q

真真假假真真真假真真假假假真假假真真假假真假真真∴

p

q=df┑（p

┑q）

p

q=df（p

q）

（qp

）②｛┑，

｝是完备的。pq┑p┑q┑p

┑q┑（┑p

┑q）p

q真真假假假真真真假假真真假假假真真假真假假假假真真真假假∴p

q=df┑（┑p

┑q）

同理可得：

p

q=df┑p

q

p

q=df（p

q）

（qp

）

③｛┑，

｝是完备的。

p

q=df┑p

qp

q=df┑（┑p

┑q）

p

q=df（p

q）

（qp

）（3）从给定的真值表确定真值形式

怎样从一个给定的真值表来确定该真值表所对应的真值形式呢?下面将介绍两种方法，一种叫写真法，另一种叫写假法。写真法：首先要在所给的真值表的最后一列里，找出所有取值为真的真值。如：

pqα

真真假真假真

假真真

假假假注：α表示该真值表对应的真值形式。

然后，在取值为真的这些行中，（1）如果命题变项的取值为真，则用合取号把它与其命题变项联结起来；（2）如果命题变项的取值为假，

则用合取号把它的否定与其命题变项联结起来。如：

pqα

真真假真假

真

---p

┑q

假真真

---┑p

q

假假假最后，再把所得的各部分的真值形式用析取号联结起来，这就是该真值表所对应的一个真值形式。如：

（p

┑q）

（┑p

q）。

上式为α的一个表达式。写假法：首先要在所给的真值表的最后一列里，找出所有取值为假的真值。如：

pqα

真真假真假真假真真假假假

然后，在取值为假的这些行中，（1）如果命题变项的取值为真，则用析取号把它的否定与其命题变项联结起来；（2）如果命题变项的取值为假，则用析取号把它与其命题变项联结起来。如：

pqα

真真假

---┑p

┑q

真假真假真真假假假

---p

q

最后，再把所得的各部分的真值形式用合取号联结起来，这就是该真值表所对应的一个真值形式。如：（┑p

┑q）

（p

q）。

上式也是α的一个表达式。在使用写真（假）法时，需要注意两点：第一，采用写真法时，不能写出在真值表最后一列的值全为假的情况，即写真法对此情况失效；采用写假法时，不能写出在真值表最后一

列的值全为真的情况，即写假法对此情况失效。第二，写真法常用于在真值表的最后一列的值中，真少于假的情况；写假法常用于在真值表的最后一列的值中，假少于真的情况。现在，对任意给定的真值形式，不管它多么复杂，我们都可以用真值表方法做出与它对应的真值表。反过来，对任意的真值表，我们可以采用写真法或写假法构造出相应的真值表达式。

例8构造下面真值表所对应的一个真值形式α。解：

pqrα

真真真假真真假真真假真假真假假假假真真真假真假假假假真假假假假真

用写真法写出的α的真值表达式为：（p

q

┑r）

（┑p

q

r）

（┑p

┑q

┑r）。用写假法写出的α的真值表达式为：

（┑p

┑q

┑r）

（┑p

q

┑r）

（┑p

q

r）

（p

┑q

r）

（p

q

┑r）。（三）真值函项

每一真值形式实际上都可以被看作一个函数，这个函数的自变元就是其中所含的命题变项，它的定义域和值域都是真值的集合，即｛真，假｝。也就是说，一个函数，如果其自身的值是真值，其自变元所取的值也是真值，这样的函数被称为真值函项。例如，p

q，┑（┑p

┑q）等都是真值函项。由此可知，每一个真值形式又都是一个真值函项。

现在，我们观察函数f（x）=x（x≠0）和g（x）=x2／x（x≠0）。虽然f（x）和g（x）所对应的函数表达式不同，但它俩的定义域相同，值域也相同。习惯上，我们把f（x）和g（x）看成是一个函数，即f（x）=g（x）（x≠0）。同样，虽然真值形式p

q和┑（┑p

┑q）不同，但它们的定义域和值域相同，即它们所含自变项的个数相同，并且真值表相同。

pqp

q

pq┑（┑p

┑q）真真真真真真真假假真假假假真假假真假假假假假假假我们把具有这种性质的两个真值形式称为同一类的真值函项。在同一类的真值函项中任意两个真值形式都是相互等值的。因此有，p

q等值于┑（┑p

┑q）。

当命题变项的数目给定之后，不同真值函项类的数目是有限的。当命题变项的数目为1时，设命题变项为p，p的真值共有两种，真和假。即

p

真假在p的每一种取值下，真值函项的取值各有两种，由此产生不同真值函项

类的数目有且只有2×2=4种，即

pf1（p）f2（p）f3（p）f4（p）

真真真假假假真假真假其中，f1（p）是一个常真的真值函项，f4（p）是一个常假的真值函项，f2（p）的取值与自变项p的取值一致，f3（p）的取值与p的值恰好相反。

f1（p），f2（p），f3（p）和f4（p）可分别表示为：

f1（p）：p

┑p；f2（p）：p；

f3（p）：┑p；f4（p）：p

┑p。

当命题变项的数目为2时，设命题变项为p和q，那么p与q组成的所有不同的真值组合共有2×2=22种，即

pqf（p，q）真真真/假真假真/假假真真/假假假真/假

对于变项p和q的每一种真值组合，真值函项f（p，q）的取值又各有两种真和假。因而当命题变项的数目为2时，所构成的不同的真值函项的数目有且只有2×2×2×2=24=16种。下面是这16种真值函项的真值表：

pqf1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16真真真真真真真真真真假假假假假假假假真假真真真真假假假假真真真真假假假假假真真真假假真真假假真真假假真真假假假假真假真假真假真假真假真假真假真假

f1至f16的真值表达式分别为：f1：p

┑p；f2：p

q；f3：q

p；f4：p；f5：

p

q；f6：q；f7：p

q；f8：p

q；f9：┑（p

q）；f10：┑（p

q）；f11：┑q；f12：┑（p

q）；f13：┑p；f14：┑（q

p）；f15：┑（p

q）；f16：┑（p

┑p）。

在f1这个真值函项类中，不仅有p

┑p，还有q

┑q，┑p

p，┑q

q以及所有与p

┑p逻辑等值的公式都在p

┑p的真值函项类中。反过来说，在真值表是：

pqf

真真真真假真假真真假假真

的真值函项类中，有无穷多个真值形式，在这无穷多个真值形式中，我们可以任意选择一个真值形式作为这一类真值函项的一个代表，比如选：p

┑p。当命题变项的数目为3时，设命题变项为p，q和r，则p，q，r所有不同的真值组合共有2×2×2=23=8种，即：

pqrf（p，q，r）真真真真/假真真假真/假真假真真/假真假假真/假假真真真/假假真假真/假假假真真/假假假假真/假

对于变项p，q和r的每一种组合，真值函项f（p，q，r）的取值又各有两种：真和假。因而当命题变项的数目为3时，所构成的不同的真值函有且只有

2×2×2×2×2×2×2×2=28=256

种。限于篇幅，略去这256种真值函项的真值表和真值表达式。

一般地，当命题变项有n个时，其中每一个命题变项有且只有两种取值。因此，n个命题变项的不同真

值组合共有：

2×2×2×…×2=2n

n个个。对于其中每一种命题变项的真值组合，真值函项的取值又各有两种，因而不同的真值函项共有

2×2×2×…×2=2

2n

2n个

种。总之，当命题变项的数目确定之后，不同真值函项的种类是有限的，而真值形式的个数是无限的。一个真值函项可以用不同的真值形式来表示。（四）重言式及其判定方法

1.重言式尽管真值形式的数目是无限的，但是在变项的数目给定之后，真值

函项的种类是有限的。从真值表的角度来讲，含有2个命题变项的真值形式，能并且只能做出16个不同的真值表。另外，从前面的讨论中可以看出，不同的真值函项按所取真值的不同，可以分为下面三类：第一类：永真的，即不论真值函项中所含变项取什么值，真值函项的值总为真。例如，p

﹁p。

第二类：有真有假的，即不论真值函项中所含变项取什么值，真值函项的值有时为真有时为假。例如，p

q。第三类：永假的，即不论真值函项中所含变项取什么值，真值函项的值总为假。如：┑（p

┑p），它们的真值表为：pq┑pp

┑pp

q┑（p

┑p）真真假真真假真假假真假假假真真真假假假假真真假假

习惯上，我们把具有第一类特征的真值形式叫做重言式。它所对应的真值函项叫做重言的真值函项。把具有第二类特征的真值形式叫做可满足式。把具有第三类特征的真值形式叫做不可满足式，或永假式，或矛盾式。在命题逻辑中，重言式是人们最感兴趣的，因为它所反映的是命题逻辑中的逻辑规律。从思维和形式结构上来说，可以将重言式分为以下三类：

第一类：有些重言式表示了命题逻辑的思维规律，如p

┑p是命题逻辑中的排中律，﹁（p

┑p）是命题逻辑中的不矛盾律。第二类：有些重言式还可以表示命题逻辑中正确的推理形式。如下面的推理：如果m2是偶数，则m是偶数；

m2

是偶数；所以，m是偶数。这是一个正确的假言推理。如果用合取号

将前提联结为合取式（p

q）

p，

再用蕴涵号

将前提（p

q）

p和结论q联结起来，构成蕴涵式（（p

q）

p）

q，则这一命题形式是重言式。推理的正确性是显然的。第三类：还有一些重言式是以等值形式出现的，它们又叫重言等值式。这些等值式也表现了命题逻辑的规律，其中有一些对逻辑演算是很重要的。借助这些规律可以形成重要的逻辑方法，如求范式等。

除了以上三类之外，还有一些重言式是和我们的实际思维关系不大的，或者说在我们的思维中一般不会出现以这类重言式为形式的命题和推理，但这些重言式在逻辑中仍然有重要的作用。它们往往是借助逻辑演算得到的，或者它们是逻辑演算的出发点或者中间环节。例如，一些命题演算的公理、定理以及在求证定理的过程中得到的公式等等。另外，还有一些重言式从结构上看是无作用或无意义的。它们在思维和逻辑中都不会出现，是人们为了一定的目的构成

的，如┑┑（p

┑p），┑（p

p）等等。不可满足式或永假式表示逻辑矛盾，它和重言式是相互对立的，所以下面的一些结论是显然的：（1）一个真值形式是重言式当且仅当它的否定是不可满足的。（2）一个真值形式是不可满足的当且仅当它的否定是重言式。（3）一个真值形式不是重言式当且仅当至少在它所含命题变项的一种取值下，其值

为假。（4）一个真值形式是可满足的当且仅当它不是不可满足的。（5）重言式一定是可满足的，反之不然。（6）不可满足式一定不是重言式，反之不然。

2.重言式的作用（1）判定两个真值形式是否等值

判定两个真值形式是否等值，就是判定一个等值式是否为重言式。换句话说，不论其中的命题变项取什么值，这两个真值形式的值总是同真或者同假。例如，我们已经知道，不论p，q各取什么值，p

q与┑（p

┑p）的值同真或者同假。因此，

p

q

┑（p

┑p）是重言式。此时，我们也称p

q与┑（p

┑p）是同一类的真值函项。而p

q┑

（p

┑p）为重言式等值。

又如：p

q

┑（┑p

┑q）是重言式等值式，因为p

q与┑（┑p

┑q）有相同的真值表：pq┑p┑q┑p

┑q┑（┑p

┑q）p

q

真真假假假真真真假假真假真真假真真假假真真假假真真真假假命题逻辑中常用的等值式有：（1）（p

q）

┑p

q

这个等值式刻画了

的特征，即“p蕴涵q，等值于，p假或q真”。（2）（p

q）

┑（p

┑q）这个等值式也刻画了

的特征，即“p蕴涵q，等值于，并非，p真并且q假”。（3）（p

q）

（p

q）

（q

p）这个等值式刻画了

的特征，即“p当且仅当q，等值于，p蕴涵q并且q蕴涵p”。（4）p

q

q

p

这是析取交换律，即“p或q，等值于，q或p”。（5）p

q

q

p

这是合取交换律，即“p并且q，等值于，q并且p”。（6）（p

q）

r

p

（q

r）这是析取结合律，即“（p或q）或r

，等值于，p或（q或r

）”。（7）（p

q）

r

p

（q

r）这是合取结合律，即“（p并且q）并且r

，等值于，p并且（q并且r

）”。（8）p

（q

r）

（p

q）（p

r）这是合取对析取的分配律，即“（p并且（q或r），等值于，（p并且q）或者（p并且r

）”。（9）p

（q

r）

（p

q）

（p

r）这是析取对合取的分配律，即“（p或（q并且r），等值于，（p或q）并且（p或r

）”。（10）┑（p

q）

┑p

┑q

这是德•摩根律之一，即“并非（p或q），等值于，非p并且非q”。（11）┑（p

q）

┑p

┑q

这是德•摩根律之一，即“并非（p并且q），等值于，非p或非q”。（12）p

┑┑p

这是双重否定原则，即“p，等值于，非非p”。（13）（p

q）（┑q

┑p）这是假言易位原则，即“p蕴涵q，等值于，非q蕴涵非p”。（2）判定一个推理形式是否正确判定一个推理形式是否正确，就是判定一个蕴涵式是否为重言式。一个推理由前提和结论两部分组成。如果一个推理形式是正确的，那么由前提真必然能得出结论真。因此，前提与结论之间的关系是蕴涵关系。所以，我们可以用一个蕴涵式来表示推理形式，而这个蕴涵式的前件是各个前提的合取，后件是结论。如果推理形式是正确的，那么相应的蕴涵式就是一个重言式。因为正确的推理形式是不依赖于

前提和结论的具体内容的，所以相应的蕴涵式必须对于所含命题变项的任何取值，取值总为真。观察下面的两个推理形式及相应的真值表：（1）如果p，那么q；所以，如果非q，那么非p。这是一个假言易位推理，和这个推理形式相应的蕴涵式为：（p

q）

（┑q

┑p）它的真值表为：pq┑p┑qp

q┑q

┑pα真真假假真真真真假假真假假真假真真假真真真假假真真真真真由于（p

q）（┑q

┑p）为重言式，所以，此推理形式是正确的。（2）如果p，那么q；非p；所以，非q。和这个推理形式相应的蕴涵式为：（（p

q）

┑p）

┑q它的真值表为：pq┑p┑qp

q（p

q）

┑pα

真真假假真假真真假假真假假真假真真假真真假假假真真真真真

由于（（p

q）

┑p）

┑q不是重言式，所以，此推理形式是不正确的。3.重言式的判定方法

(1)简化真值表方法

一个真值形式不论多么复杂，我们都可以用真值表方法判断它是不是一个重言式。但是，当它的构造比较复杂，或者所含命题变项的个数比较多时，构造它的真值表就是一件比较麻烦的事情。为此，这里给出一种比较简便的判定方法：简化

真值表方法，也叫赋值归谬法。它是以真值表方法为基础的。这种方法特别适合于蕴涵式。简化真值表方法的主要思想是：不论该蕴涵式的命题变项各取什么值，都不能使它的前件为真后件为假。这种方法也就是反证法。具体做法是将所给蕴涵式的前件赋值真，后件赋值假。在这种赋值下，如果能导致矛盾的结果，从而就证明了该蕴涵式的前件真后件假是不可能的，因此要判定的蕴涵式就是一个重言式。如果不能导致矛盾的结果，那么所要判定的蕴涵

式就不是一个重言式。例9用简化真值表方法判断：（q

r）

（p

q

p

r）是否重言式。解：简化真值表略！当（q

r）

（p

q

p

r）为假时，得出p亦真亦假，这是不可能的。故（q

r）

（p

q

p

r）是一个重言式。例10用简化真值表方法判断：p

q

q

p是否重言式。解：简化真值表略！当p

q

q

p为假时，由q假，q真，矛盾。此式是一重言式。

例11用简化真值表方法判断：（（p

q）

┑p）

┑q是否重言式。

解：（（p

q）

┑p）

┑q┊①┊假┊（假设）②┊真┊假┊③真真┊真④假当p假q真时，（（p

q）

┑p）

┑q为假，故（（p

q）

┑p）

┑q不是重言式。

现在，做α：（（p

q）

┑p）

┑q的真值表：

pq┑p┑qp

q（p

q）

┑pα

真真假假真假真真假假真假假真假

真真假真真假

假假真真真真真

从上面的真值表也可以看出：当p假q真时，该公式的值为假。因此它不是重言式。这与用简化真值表方法得出的结论是一致的。

简化真值表方法还可以更简单一些。如：（（p

q）

┑p）

┑q

假①

（（p

q）

┑p）

┑q

真假假②①②（（p

q）

┑p）

┑q

真真真假假③②③①②（（p

q）

┑p）

┑q

真真真真假假假真

③④②③④①②③(2)真值树方法真值树方法也是一种用来判定一个给定的公式（命题形式）是否为重言式的方法。在很多场合中它比真值表和简化真值表方法更为有效。真值树的形状像一棵倒置的树。这棵树记做T。T的元素叫结点，每一结点上都放一个有穷的公式集。如图1-1所示，每个结点属于惟一的一层，层可以用自然数标明。如图1-1所示的真值树有3层，我们也可以说真值树的深度为3。这里Фij（i,j=0，1，2，3）是任意有穷的公式集。Ф00叫做真值树T的始点，Ф21叫做Ф11后继，Ф31叫做树T的一个终点。由Ф00，Ф11，Ф21和Ф31组成的这条道路叫真值树的一个分枝。不同结点上的公式集既可以相同，也可以不同。一棵真值树有几个终点，就有几个分枝。单个的Ф00也叫一棵真值树（退化的），它既是始点又是终点，它的结点只有一个。所以，这棵真值树只有一个分枝，就是它自身。T:Ф00

Ф11Ф12Ф13

Ф21Ф22Ф23

Ф31Ф32

真值树T长出新枝的规则如下：┑┑规则：如果在T的一个终止于结点Ф的分枝的公式中有一个公式┑┑α,则附加一个新的结点｛α｝作为Ф的后继，如下图所示。

┑┑规则：┊

︱

┑┑α

┊

︱

α

规则：如果在T的一个终止于结点Ф的分枝的公式中有一个公式α

β，则附加两个新的结点｛α｝和｛β｝作为Ф的后继，如下图所示。

规则：┊

︱

α

β

┊

αβ┑

规则：如果在T的一个终止于结点Ф的分枝的公式中有一个公式┑（α

β），则附加一个新的结点｛┑α，┑β｝作为Ф的后继，如下图所示。

┑

规则：

┊

︱┑（α

β）┊

︱

┑α,┑β

注意：（1）不一定只在各分枝的终点上才使用这些规则。（2）使用┑┑规则和┑

规则时，真值树不分杈，使用

规则时真值树分杈。（3）通常情况下，先使用不分杈的规则。例11构造┑（┑α

（┑β

α））的真值树。解：

┑（┑α

（┑β

α））∣┑┑α┑

规则┑（┑β

α）∣┑┑规则α∣┑

规则┑┑β┑α∣┑┑规则β

这棵真值树的深度为4，并且只有一个分枝。对公式┑（┑α

（┑β

α））或┑（┑β

α）等还可以再使用﹁

规则。但是继续使用﹁

规则，产生不出新的公式。因此，在这种情况下，我们就不再继续使用该公式来扩充此真值树。但要在该公式旁画√，表示该公式已经使用过了。于是我们规定：在某一分枝上的某一公式α在该分枝中用过了，如果不是下列情况之一：①α是┑┑β，而β不是该分枝的公式；②α是（β

γ），而β和γ都不是该分枝的公式；③α是┑（β

γ），而┑β和┑γ二者不同为该分枝的公式。一棵真值树的分枝是封闭的，如果有一个公式α，使得α和┑α都是该分枝的公式。公式α和┑α叫做用来封闭该分枝。对封闭的分枝，我们规定：在该分枝下方打叉，即×。

定理Ф的一棵真值树被称为Ф的一个反驳，如果它的所有分枝都是封闭的。反驳Ф就是构造Ф的一个反驳。特别地，如果┑α能被反驳，则α是一个重言式。例12用真值树方法证明：

┑（┑q

r）

（┑（┑p

q）

（┑p

r））

是一个重言式。证明：现在构造

┑（（┑q

r）

（┑（┑p

q）

（┑p

r）））

的一个反驳。

┑（┑（┑q

r）

（┑（┑p

q）

（┑p

r）））√

︱┑┑（┑q

r）√┑（┑（┑p

q）

（┑p

r））√

︱┑q

r√︱┑┑（┑p

q）√┑（┑p

r）√

︱┑p

q√︱

┑┑p√┑r︱p∕＼┑pq×∕＼┑qr××

因为我们能够构造┑（┑（┑q

r）

（┑（┑p

q）

（┑p

r）））的一个反驳，所以，┑（┑q

r）

（┑（┑p

q）

（┑p

r））是一个重言式。

由联结词

，

和

构成的公式，可以根据下面的等值式：（α

β）

┑（┑α

┑β）（α

β）

（┑α

β）（α

β）

（α

β）

（β

α）将它们转换成只用联结词┑和

表示的公式，然后再来构造真值树。另一方面也可以从┑┑规则，┑

规则和

规则中导出它们的规则，这些导出规则是：

规则：┑

规则：┊┊

︱︱α

β┑（α

β）┊┊

︱∕＼

α┑α┑ββ

规则：┑

规则：┊┊

︱︱α

β┑（α

β）┊︱∕＼α┑αβ┑β

规则：┑

规则：┊┊︱︱α

β┑（α

β）┊┊∕＼∕＼

α┑αα┑αβ┑β┑ββ例13用真值树方法证明（q

r）

（p

q

p

r）是一个重言式。证明：

┑（（q

r）

（p

q

p

r））√

︱q

r√┑（p

q

p

r）√

︱p

q√┑（p

r）√

︱┑p┑r∕＼┑qr∕＼×pq××

因为我们能够构造┑（（q

r）

（p

q

p

r））的一个反驳，所以（q

r）

（p

q

p

r）是一个重言式。例14用真值树方法判定

p

（p

（p

q））是否重言式。证明：┑（p

（p

（p

q）））√

︱p┑（p

（p

q））√∕＼┑p