计算机科学的基础

第 12 章　命题逻辑

第 12 章　命题逻辑

本章要介绍命题逻辑，是种最初目的是为了模型推理的代数，其历史要追溯到亚里士多德的时代。在更近的时代里，这种代数和很多代数一样，是实用的设计工具。例如，第13章就展示了命题逻辑是如何应用到计算机电路设计中的。逻辑的第三个用途是作为编程语言和系统（比如Prolog语言）的数据模型。很多通过计算机进行推理的系统，包括定理证明程序、程序验证程序，以及人工智能领域的应用，都是用基于逻辑的语言实现的。这些语言一般都利用了“谓词逻辑”，它扩充了命题逻辑的功能，是更为强大的逻辑形式。我们将在第14章中介绍谓词逻辑。

12.1　本章主要内容

12.2节从直观上说明了命题逻辑是什么，以及它为何实用。12.3节介绍了用于逻辑表达式的代数，它使用布尔值操作数，并且用到对布尔（真/假）值进行运算的AND、OR和NOT这样的逻辑运算符。这种代数通常称为布尔代数，是以首先将逻辑表达为代数的逻辑学家乔治·布尔的名字命名的。然后我们还会了解以下内容。

  • 真值表是表示表达式逻辑意义的实用方式（12.4节）。

  • 可以把真值表转换为对应相同逻辑函数的逻辑表达式（12.5节）。

  • 卡诺图是一种用于简化逻辑表达式的实用制表技巧（12.6节）。

  • 存在数量丰富的“重言式”，或可用于逻辑表达式的代数法则（12.7节和12.8节）。

  • 命题逻辑的某些重言式让我们可以对“反证法”或“逆转命题法”这样的常用证明技巧加以解释（12.9节）。

  • 命题逻辑也是经得起“演绎”的。所谓演绎，就是写出一行行内容，其中每一行要么是给定的，要么是能由之前的某些行来验证的（12.10节）。大多数人在学习平面几何时都了解过这种证明模式。

  • 名为“分解”（resolution）的强大技巧有助于我们迅速作出证明（12.11节）。

12.2　什么是命题逻辑

山姆编写了如下含有if语句的C语言程序。

if (a < b || (a >= b && c == d)) ...　　　　　　(12.1)

莎莉指出，该if语句中的条件表达式可以写为如下更简单的形式。

if (a < b || c == d) ...　　　　　　(12.2)

莎莉是如何得出这一结论的？

她可能是按照如下方式推理的。假设a<b。那么参与OR运算的第一个条件在这两条语句中都为真，因此(12.1)和(12.2)这两条if语句中的then部分都会被接受。

现在假设a<b不成立。在这种情况下，只有当参与OR运算的第二个条件为真的情况下才会接受then部分。对语句(12.1)我们要询问

a >= b && c == d

是否为真。因为a<b为假，所以现在a>=b显然为真。因此，在(12.1)中，只有在c==d为真时才接受then部分。而对语句(12.2)，显然也是只有在c==d为真时才接受then部分。因此不管a、b、c、d的值分别是什么，要么是if语句都能带来接下来的then部分，要么是都不能。所以我们可以判断出莎莉是对的，简化过的条件表达式可以在不改变程序功能的情况下替换第一个表达式。

命题逻辑是让可以对逻辑表达式的真假进行推理的数学模型。我们将在12.3节中给出逻辑表达式的正式定义，不过现在可以把逻辑表达式视作对(12.1)和(12.2)这样的条件表达式的简化，这种简化抽象掉了C语言逻辑运算符求值次序的限制。

命题和真值

请注意，上述针对两个if语句的推理并不取决于a<b或相似的条件“意味着”什么。我们需要知道的只有条件a<b和a>=b是互补的，也就是说，当一个条件为真时另一个条件就为假，反之亦然。因此可以用符号p 替换语句a<b，用表达式NOTp替代a>=b，并用符号q 替换c==d。这里的符号p 和q 称为命题变量，因为它们可以代表任何“命题”，也就是任何可以具有某一真值（真或假）的语句。

逻辑表达式可以包含AND、OR和NOT这样的逻辑运算符。当逻辑表达式中逻辑运算符操作数的值已知时，表达式的值就可以通过下面这样的规则确定。

1. 当且仅当p 和q 都为真时，p AND q 为真，否则它为假。

2. 当p 为真，q 为真，或两者都为真时，p OR q 为真，否则它为假。

3. 如果p 为假，则NOT p 为真，如果p 为真，则它为假。

NOT运算符与C语言运算符!具有相同含义。运算符AND和OR分别类似于C语言的运算符&&和||，但存在技术差异。不过，只有在C语言表达式具有副作用时，这一细节才很重要。因为逻辑表达式的求值过程中是没有“副作用”的，所以可以把AND当作C语言运算符&&的同义词，把OR当作||的同义词。

例如，在(12.1)式中的条件可以写为逻辑表达式

p OR ((NOT p) AND q )

而(12.2)式可以写为p OR q。我们对(12.1)和(12.2)这两个if语句的推理证明了如下一般性命题

p OR ((NOT p) AND q)≡(p OR q )　　　　　　(12.3)

其中≡意味着“等价于”或“与……具有相同的布尔值”。也就是说，不管为命题变量p 和q 指定什么样的真值，≡的左边跟右边要么都为真，要么都为假。我们发现对上面的等价性而言，当p 为真或当q 为真时就都为真，而如果p 和q 都为假则为假。因此，我们得到了有效的等价。

因为p 和q 可以是任何命题，所以可以利用(12.3)式简化很多不同的表达式。例如，可以设p 为

a == b+1 && c < d

而q 为a == c || b == c。在这种情况下，(12.3)的左边就成了

(a == b+1 && c < d) || (12.4)
    ( !(a == b+1 && c < d) && (a == c || b == c))　　　　　　(12.4)

请注意，我们为p 和q 的值加上了括号，以确保得到的表达式组合正确。

(12.3)式告诉我们(12.4)式可以简化为(12.3)式的右边，也就是

(a == b+1 && c < d) || (a == c || b == c)

再举个例子，设p 是命题“天气晴朗”，而q 是命题“乔伊带着伞”，那么(12.3)的左边就成了

“天气晴朗，否则不是晴天但乔伊带着伞。”

而右边也表示同样的事情，就是

“天气晴朗，否则乔伊带着伞。”

命题逻辑不能做什么

命题逻辑是一种实用的推理工具，但它是有局限性的，因为它不能洞悉命题内部并利用命题间的关系。比如，莎莉写出了if语句

if (a < b="" &&="" a="">< c="" &&="" b="">< c)="" ...="">

然后山姆指出只要写成

if (a < b="" &&="" b="">< c)="" ...="">

就足够了。如果设p、q 和r 分别代表命题(a<b)、(a<c)和(b<c)，这样看起来山姆所说的就是

（p AND q AND r）≡(p AND r )

不过这一等价性并不总是存在。例如，假设p 和r 为真，而q 为假。那么右边就为真，而左边却为假。

山姆的简化结果是正确的，但这里并不是利用命题逻辑得到的。大家可能会回想起7.10节中介绍的<是一种具有传递性的关系。也就是说，只要p 和r 都为真，也就是a<b和b<c都成立，那么就有q 为真，即a<c成立。

第14章将介绍一种叫作谓词逻辑的更为强大的模型，它允许我们为命题附加参数。这种特权让我们可以利用<这样的运算符的特殊属性。对我们来说，可以把谓词视作第7章和第8章的集合论中关系的名称。例如，我们可以创建谓词lt 表示运算符<，并将p、q 和r 分别写为lt (a,b )、lt (a,c )和lt (b,c )。那么，根据表示lt 属性的合适法则，比如传递性，就可以得到

(lt (a,b ) AND lt (a,c ) AND lt (b,c ))≡(lt (a,b ) AND lt (b,c ))

其实，上式对任何满足传递律的谓词lt 都是成立的，而不仅是对谓词<成立。

12.3　逻辑表达式

正如12.2节中提到的，逻辑表达式可以按照以下方式递归地定义。

依据。命题变量以及逻辑常量TRUE和FALSE都是逻辑表达式，这些都是原子操作数。

归纳。如果E和F是逻辑表达式，那么

(a) E AND F。如果E 和F 都为TRUE，则该表达式的值为TRUE，否则为FALSE。

(b) E OR F。如果E 为TRUE、F 为TRUE或两者都为TRUE，则该表达式的值为TRUE，如果E 和F 都为FALSE，则该表达式的值为FALSE。

(c) NOT E。若E 为FALSE，则该表达式的值为TRUE，若E 为TRUE则其值为FALSE。

也就是说，逻辑表达式可以用二元中缀表达式AND和OR，以及一元前缀表达式NOT构建。与其他代数一样，我们需要用括号进行组合，不过在某些情况下，也可以利用运算符的优先级和结合性消除多余的括号对，正如我们在涉及这些逻辑运算符的C语言条件表达式中所做的那样。在12.4节中，将看到出现在逻辑表达式之外的更多逻辑运算符。

示例 12.1

下面是一些逻辑表达式的例子

1. TRUE

2. TRUE OR FALSE

3. NOT p

4. p AND (q OR r )

5. (q AND p) OR (NOT p )

在这些表达式中，p、q 和r 都是命题变量。

12.3.1　逻辑运算符的优先级

与其他类型的表达式一样，我们也可以为逻辑运算符指定优先级，而且可以利用这样的优先级消除某些括号对。我们已经看到的这些逻辑运算符的优先次序分别是NOT（最高），然后是AND，再是OR（最低）。虽然我们将会看到AND和OR具有结合性，怎样分组都无关紧要，但它们通常是从左组合的。而一元前缀运算符NOT只能从右起分组。

示例 12.2

NOT NOT p OR q被分组为(NOT (NOT p)) OR q。而NOT p OR q AND r 被分组为(NOT p ) OR (q AND r )。大家应该可以看出，AND、OR和NOT的优先级和结合性与算术运算符×、+和一元的-之间存在相似性。例如，本例所述的第二个表达式就可以类比为算术表达式 -p+q×r，它有着相同的分组方式，(-p)+(q×r )。

12.3.2　逻辑表达式的求值

当逻辑表达式中的所有命题变量都被赋予真值时，表达式本身也得到一个真值。我们可以像为算术表达式或关系表达式求值那样，为逻辑表达式求值。

这一过程通过对应逻辑表达式的表达式树可以得到最好的体现。图12-1就是对应逻辑表达式p AND (q OR r ) OR s 的表达式树。给定某一真值赋值，也就是，为各变量赋值TRUE或FALSE，可以从表示原子操作数的叶子节点开始。每个原子操作数要么是逻辑常量TRUE或FALSE之一，要么是根据真值赋值给定了TRUE或FALSE之中某一个值的变量。然后向上处理该表达式树。一旦某内部节点v 的子节点的值已知，就可以对这些值应用处在节点v 的运算符，并为节点v 产生真值。根节点的真值就是整个表达式的真值。

图 12-1　表示逻辑表达式p AND (q OR r ) OR s 的表达式树

示例 12.3

假设要为表达式p AND (q OR r ) OR s求值，其中p、q、r 和s 的真值赋值分别是TRUE、FALSE、TRUE和FALSE。我们首先要考虑图12-1中最低的内部节点，也就是表示表达式q OR r 的内部节点。因为q 为FALSE，而r 为TRUE，所以q OR r 的值为TRUE。

现在来处理带有AND运算符的节点。它的两个子节点分别对应表达式p 和q OR r，因此都具有值TRUE。所以表示表达式p AND (q OR r )的该节点的值也是TRUE。

最后，我们要继续处理带有运算符OR的根节点。我们已经得出它的左子节点的值为TRUE，而它的右子节点表示表达式s根据真值赋值其值为FALSE。因为TRUE OR FALSE求出的值是TRUE，所以整个表达式的值为TRUE。

12.3.3　布尔函数

任何表达式的“含义”都可以描述为从其参数的值到整个表达式的值的函数。例如，算术表达式x×(x+y)是接受x 和y（假如x 和y 是实数）的值，然后返回将两个参数相加并将和乘以第一个参数所得到的值。这一行为就类似如下C语言函数的行为

float foo(float x, float y)
{
    return x*(x+y);
}

在第7章中我们了解到，函数是定义域和值域有序对的集合。我们还可以把x×(x+y)这样的算术表达式表示为定义域为实数对且值域为实数的函数。该函数是由形如((x,y),x×(x+y))的有序对构成的。请注意，各有序对的第一个组分本身也是有序对(x,y)。该集合是无限集，它所含的成员类似((3,4),21)或((10,12,5),225)。

类似地，逻辑表达式的含义就是接受真值赋值作为参数，并返回TRUE或FALSE的函数。这样的函数就叫作布尔函数。例如，逻辑表达式

E：p AND (p OR q)

就类似如下C语言函数

BOOLEAN foo(BOOLEAN p, BOOLEAN q)
{
    return p && (p || q);
}

和算术表达式一样，布尔表达式也可以视作有序对的集合。各有序对的第一个组分是一种真值赋值，也就是以某指定次序为各命题变量给出真值的元组。而该有序对的第二个组分是表达式对应此真值赋值时的值。

示例 12.4

表达式E = p AND (p OR q)可以用由4个成员组成的函数表示。我们在表示真值时会把对应p的值放在对应q的值之前。那么((TRUE,FALSE),TRUE)就是将E表示为函数的集合中的一个有序对。它的含义是，当p为真且q为假时，p AND (p OR q)为真。我们可以通过示例12.3中所示的过程处理表示E的表达式树来确定该值。读者可以使用其他3种真值赋值为E求值，以此构建起E所表示的整个布尔函数。

12.3.4　习题

1. 针对所有可能的真值赋值，为以下表达式求值，从而将它们的布尔函数表示成集合论函数。

(a)p AND (p OR q)

(b)NOT p OR q

(c)(p AND q) OR (NOT p AND NOT q)

2. 编写C语言函数实现习题1中的逻辑表达式。

12.4　真值表

将布尔函数表示为真值表是很方便的，真值表中的各行对应着各参数真值所有可能的组合。表中有着对应各参数的列以及对应函数值的列。

图 12-2　对应AND、OR和NOT的真值表

示例 12.5

对应AND、OR和NOT的真值表如图12.2所示。这里用到了简略表示法，用1代表TRUE，用0代表FALSE，本章其他部分也将经常这样表示。因此对应AND的真值表就表示，当且仅当两个操作数都为TRUE时，结果才是TRUE，而第二个真值表则表示，当操作数有一个为TRUE或两个都为TRUE时，应用OR运算符的结果为TRUE，而第三个真值表说明，当且仅当操作数的值为FALSE时，应用NOT运算符的结果为TRUE。

12.4.1　真值表的大小

假设某布尔函数具有k 个参数，那么该函数的真值赋值就是具有k 个元素的表，各元素要么为TRUE，要么为FALSE。计算对应k 个变量的真值赋值数就是4.2节中考虑过的为分配计数问题的例子。也就是说，我们可以为这k 个项每个项分配两个真值之一。这就和用两种可选颜色粉刷k 所房屋的问题是类似的，因此真值赋值的数目是2k。

因此含k 个参数的布尔函数对应的真值表有2k 行，每一行都对应一种真值赋值。例如，如果k=2，则真值表有4行，分别对应00、01、10和11，正如我们在图12-2中看到的对应AND和OR的真值表那样。

尽管涉及两三个变量的真值表相当小。但k 元函数对应2k行这一事实说明，不用等到k 变得特别大，绘制真值表就会很难了。例如，含10个参数的函数就有逾1000行。在后面几节中我们还将了解到，尽管真值表是有限的，而且原则上讲可以表示出我们想知道的与布尔函数有关的一切，但它们呈指数式增长的大小通常迫使我们寻找其他理解、比较布尔函数或为其求值的方法。

理解“蕴涵”

蕴涵（implication）运算符→的含义可能不那么直观，因为必须利用到“假蕴涵一切”的概念。我们不应该把→和因果关系混为一谈。也就是说，p→q 可能为真，但p 并不是在任何情况下都会“导致”q。例如，设p 是“天在下雨”，q 是“苏带着伞”。我们可以断言p→q 为真。而且看起来似乎就是下雨导致苏带上她的伞。不过，也有可能苏是那种不相信天气预报而且不会一直带上雨伞出门的人。

12.4.2　布尔函数数量的计算

含k个参数的布尔函数对应真值表的行数是以k呈指数增长的，而不同k元布尔函数的数量增长得更快。要计算k元布尔函数的数量，可以注意到，正如我们所见，每个这样的函数都是由具有2k行的真值表表示的。每一行都会被赋予一个值，要么为TRUE，要么是FALSE。因此，含k个参数的布尔函数的数量就与具有2个值的2k项的分配的数量相同。这一数字是22k。例如，当k=2时，就有222=16个函数，而对k=5，存在225=232，或者说是大约40亿个函数。

在含两个参数的16种布尔函数中，我们已经遇到过其中的两个：AND和OR。其他一些函数中有些是微不足道的，比如不管参数为什么值都为1的函数。不过，还有一些双参数函数是很实用的，而且我们将在本节之后的内容中看到它们。我们还看到了实用的单参数函数NOT，而且大家也经常会用到具有3个或更多参数的布尔函数。

12.4.3　更多逻辑运算符

还有以下4种双参数的布尔函数是非常实用的。

1. 蕴涵（implication），写为→。p→q 的含义是，“如果p 为真，那么q 为真。”对应→的真值表如图12-3所示。请注意，只有在p 一定为真而且q 一定为假的情况下，p→q 才可以为假。如果p 为假，那么p→q 恒为真，而且如果q 为真，则p→q 恒为真。

图 12-3　对应“蕴涵”的真值表

2. 等价（equivalence），写为≡，意思是“当且仅当”，即只有当p 和q 都为真或都为假时，才有p≡q。它的真值表如图12-4所示。另一种看待≡运算符的方式是，它表明左边和右边的操作数具有相同的真值。这就是12.2节中我们在声称p OR((NOT p) AND q)≡(p OR q)时所要表达的意思。

3. NAND运算符，或者说“与非”运算符，是首先对操作数应用AND，然后对得到的结果应用NOT运算符求补。p NAND q 就表示NOT (p AND q)。

4. 类似地，NOR运算符，或者说“或非”运算符，是先对操作数取OR，然后对得到的结果求补，p NOR q 就表示NOT (p OR q)。NAND和NOR的真值表也如图12-4所示。

{%}

图 12-4　对应等价、NAND和NOR的真值表

12.4.4　具有多个参数的运算符

一些逻辑运算符可以自然地扩展为接受两个以上参数。例如，不难看出AND是有结合性的，也就是(p AND q) AND r 等价于p AND (q AND r)。因此，形如p1 AND p2 AND…AND pk 的表达式能以任意次序组合，只有在p1、p2、…、pk 都为真TRUE时，它的值才为TRUE。因此我们可以把该表达式写为具有k 个参数的函数

AND(p1 , p2 , … , pk)

它的真值表如图12-5所示。正如我们所见，只有在所有参数都是1时，结果才是1。

图 12-5　对应k 参数AND的真值表

一些运算符的重要性

我们对k 元运算符AND、OR、NAND和NOR特别感兴趣的原因在于，这些运算符是特别容易以电子形式实现的。也就是说，它们是构建“门”（接受k 个输入并产生这些输入的AND、OR、NAND和NOR的电子电路）的简单方式。尽管底层电子技术的细节不在本书要介绍的范围之内，但其思路通俗来说，就是用两种不同的电压表示1和0（即TRUE和FALSE）。其他一些运算符，比如≡和→，就不是很容易用电子方式实现，而我们一般会使用若干个NAND或NOR门来实现它们。不过，NOT运算符既可看作单参数的NAND，也可看作单参数的NOR，因此也是“很容易”实现的。

同样，OR也是具有结合性的，我们可以把逻辑表达式p1 OR p2 OR … OR pk 表示成布尔函数OR (p1,p2,…pk)。对应k 元OR的真值表有2k 行，就像k 元AND的真值表那样。不过，对这一k 元OR的真值表来说，只有p1、p2、…、pk 都被赋值为0的第一行的值才是0，而其余2k-1行的值全为1。

二元运算符NAND和NOR是可交换但不可结合的。因此p1 NAND p2 NAND…NAND pk 这个不含括号的表达式是没有固有含义的。在讲到k 元NAND时，并不表示

p1 NAND p2 NAND…NAND pk

任何可能的分组。而是把NAND (p1,p2,…,pk )定义为

NOT(p1 AND p2 AND…AND pk )

也就是说，只有在p1、p2、…、pk 的值都为1时，NAND (p1,p2,…,pk )的值才是0，对其他2K-1种输入组合而言，其值都为1。

同样，NOR(p1,p2,…,pk )表示NOT (p1 OR p2 OR…OR pk )。只有在p1、p2、…、pk 的值全部是0时，它的值才是1，否则它的值为0。

12.4.5　逻辑运算符的结合性与优先级

我们将用到的优先级次序是

1. NOT（最高）

2. NAND

3. NOR

4. AND

5. OR

6. →

7. ≡（最低）

因此，举例来说，p → p ≡NOT p OR q 被分组为(p → p)≡((NOT p)OR q)。

正如我们之前提过的，AND和OR，以及≡，都是具有结合性和交换性的。如果有必要指定的话，一般会假设它们是从左起组合的。我们一般会明确地给出括号，以防出现歧义，不过→、NAND和NOR这样的运算符在两个或多个相同运算符组成的串中都是从左起组合的。

12.4.6　利用真值表为逻辑表达式求值

只要表达式E 中不含太多变量，利用真值表针对所有可能的真值赋值计算和展示E 的值就是一种方便的方法。我们首先有对应E 中各变量的列，然后是按照从下到上为E 的表达式树求值的次序对应E 各子表达式的列。

在对表示某些节点的值的列应用运算符时，我们会用一种简单的方式为对应该运算符的列执行运算。例如，如果希望对两列取AND，就在两列都为1的那行中放上1，并在其他行中放上0。要是为两列求OR，就要在其中一列或者两列都为1的那几行中放上1，并在其他行中放上0。如果要为一列取NOT，就是为该列求补，如果那列有0，则放上1，反之亦然。最后再举个例子，对两列应用→运算符，只有在第一列为1且第二列为0时，其结果才是0，结果中的其他各行都是1。

其他一些运算符的规则留作本节习题。一般而言，我们会通过一行行地对所在行中各值应用运算符，以对各列应用运算符。

示例 12.6

考虑表达式E：(p AND q) → (p OR r )。图12-6给出了对应该表达式及其子表达式的真值表。(1)、(2)、(3)这3列给出了变量p、q 和r 的值的所有组合。第(4)列给出了子表达式p AND q 的值，只要第(1)和第(2)列的值都是1，该列的值就是1。而第(5)列给出了子表达式p OR r 的值，在第(1)列或第(3)列为1，或者第(1)和第(3)列都为1时，第(5)列的值是1。最后，第(6)列表示整个表达式E的值。它是通过第(4)和第(5)列得到的，除了第(4)列为1且第(5)列为0的情况外，这列的值都是1。因为不存在这样的行，所以第(6)行全是1，也就是说不管参数是什么，E的真值都是1。正如我们将在12.7节中看到的，这样的表达式称为“重言式”。

图 12-6　对应(p AND q ) → (p OR r )的真值表

文氏图和真值表

真值表与7.3节中讨论过的表示集合运算的文氏图之间存在着相似性。首先，并集运算就类似于真值的OR，而交集则类似AND。我们将在12.8节中看到，这两对运算满足相同的代数法则。就像涉及k 个集合作为参数的表达式会把文氏图分成2k个区域那样，具有k 个变量的逻辑表达式也会形成具有2k 行的真值表。此外，在这些区域与这些真值表行之间也存在自然的对应。例如，具有变量p、q 和r 的逻辑表达式就对应涉及P、Q 和R 这3个集合的集合表达式。考虑对应这些集合的文氏图：

在这里，区域0对应不在P、Q、R 任意一个中的元素构成的集合。区域1则对应着在R 中但不在P 或Q 中的元素。一般地讲，如果考虑3位区域编号的二进制表示，比方说是abc，那么如果a=1，则表示元素在P 中，如果b=1则在Q 中，而如果c=1则在R 中。因此，编号为(abc)2的区域就对应着p、q、r 分别具有真值a、b、c 时真值表的那行。

在处理文氏图时，表示两个集合并集的区域会包含对应两者中任一集合的区域。与此相似的是，在为真值表中的列求OR时，我们会在第一列有1的行与第二列有1的行的并集中放上1。类似地，文氏图中表示集合交集的区域就是只取重在这两个集合中的区域，而为列求AND就是在第一列有1的行与第二列有1的行的交集中放上1。

逻辑运算符NOT与集合运算符没有太多对应。不过，如果将所有区域的并集想象成个“全集”，那么逻辑NOT对应着取走一些区域，并生成文氏图中剩余区域组成的集合，也就是从全集中减去给定的集合。

12.4.7　习题

1. 给出计算真值表中两列的(a) NAND；(b) NOR；(c) ≡的规则。

2. 为以下表达式及它们的子表达式计算真值表。

(a) (p → q)≡(NOT p OR q)

(b) p → (q → (r OR NOT p))

(c) (p OR q) → (p AND q)

3. * 逻辑表达式p AND NOT q 对应什么集合运算符？（见之前比较文氏图和真值表的短文。）

4. * 给出说明→、NAND和NOR不具结合性的例子。

5. ** 如果布尔函数f 满足f (TRUE , x2, x3, …, xk ) = f (FALSE , x2, x3, …, xk )，则说f 是不依赖第一个参数的。同样，如果f 的第i 个参数在TRUE和FALSE之间变换却不会使f 的值改变，就可以说f 是不依赖第i 个参数的。有多少双参数布尔函数是不依赖它们的第一个或第二个参数（或两个参数都不依赖）的？

6. * 为具有两个变量的16种布尔函数构建真值表。这些函数中有多少种具有交换性？

7. 二元异或（exclusive-OR）函数⊕的定义是，当且仅当只有其中一个参数为TRUE时其值为TRUE。

(a) 画出⊕的真值表。

(b) ⊕是否具有交换性？它是否具有结合性？

12.5　从布尔函数到逻辑表达式

现在考虑从真值表设计逻辑表达式的问题。从作为逻辑表达式规范的真值表开始，目标则是找到具有给定真值表的表达式。一般而言，可以利用无数个不同的表达式，我们往往将选择限制到特定的运算符集合中，而且通常会希望表达式从某种意义上讲是“最简单的”。

该问题是电路设计中的基础问题。表达式中的逻辑运算符可以被理解成电路的门，这样的话就存在从逻辑表达式到电子电路的直接转化，这种转化是通过第13章将要讨论的过程实现的。

图 12-7　一位加法器：(dz )2是x+y+c 的和

示例 12.7

正如我们在1.3节中看到的，可以用图12-7所示的这种一位加法器设计32位加法器。一位加法器会把两个输入位x 和y 与进位输入位c 相加，得到进位输出位d 与和值位z。

图12-8中的真值表给出了进位输出位d 与和值位z 的值，将其表示为对应8种输入值组合的x、y、c 的函数。如果x、y 和c 中至少有两个的值是1，进位输出位d 就是1，而只有在输入中没有1或者只有一个1时，才有d=0。如果x、y 和c 中有奇数个为1，和值位z 就是1，否则就是0。

 

x

y

z

d

z

0)

0

0

0

0

0

1)

0

0

1

0

1

2)

0

1

0

0

1

3)

0

1

1

1

0

4)

1

0

0

0

1

5)

1

0

1

1

0

6)

1

1

0

1

0

7)

1

1

1

1

1

图 12-8　对应进位输出位d 与和值位z 的真值表

我们要展示一种从真值表立即转换成逻辑表达式的一般性方法。不过，给定图12-8中进位输出函数d 的情况下，可以按照如下方式进行推理，构建对应的逻辑表达式。

(1) 从第3行和第7行可知，如果y 和c 都是1，则d 是1。

(2) 从第5行和第7行可知，如果x 和c 都是1，则d 是1。

(3) 从第6行和第7行可知，如果x 和y 都是1，则d 是1。

条件(1)可以用逻辑表达式y AND c模拟，因为y AND c 只有在y 和c 都是1时才为真。同样，条件(2)可以用x AND c 模拟，而条件(3)则可通过x AND y 模拟。

所有有d=1的行都是这3种情况中的某一行。因此可以写出一个逻辑表达式，它只要在这3个条件中至少有一个成立的情况下为真即可，也就是要为这3个表达式取逻辑OR：

(y AND c) OR (x AND c) OR (x AND y)　　　　　　(12.5)

这一表达式的正确性在图12-9中得到了验证。后4列分别对应子表达式y AND c、x AND c、x AND y和表达式(12.5)。

x

y

c

y AND c

x AND c

x AND y

d

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

0

1

1

1

0

0

1

1

0

0

0

0

0

0

1

0

1

0

1

0

1

1

1

0

0

0

1

1

1

1

1

1

1

1

1

图 12-9　对应进位输出表达式(12.5)及其子表达式的真值表

12.5.1　简化符号

在继续描述如何从真值表构建表达式之前，我们要对表示法进行一些有意义的简化。

1. 可以通过直接并列（也就是不使用任何运算符）表示AND运算符，就像表示乘法，以及第10章中表示串接时那样。

2. OR运算符可以表示为+。

3. NOT运算符可以用上横线表示。这种约定在NOT应用到单个变量上时特别实用，我们经常把NOT p 写为\overline{p}。

示例 12.8

表达式p AND q OR r可以写为pq+r，表达式p AND NOT q OR NOT r 则可以写为p\overline{q}+\overline{r}。我们甚至可以将原始符号与简化符号混用。例如，表达式

((p AND q) → r ) AND (p → s)

可以写成(pq → r ) AND (p → s)，甚至可以写成(pq → r ) (p → s)。

使用这种新表示法的一个重要原因在于，这样可以让我们把AND和OR视作算术运算中的乘法和加法。因此可以应用诸如交换律、结合律和分配律这样的类似法则，在12.8节中我们将会看到这些法则适用于这些逻辑运算符，就像这些法则对相应的算术运算符所做的那样。例如，我们会看到p(q+r)可以被pq+pr 替换，然后被rp+qp 替换，不管涉及的运算符是AND和OR，还是乘法和加法。

因为有了这种简化符号，通常可以把表达式的AND称为积，把表达式的OR称为和。表达式的AND也可以称为合取（conjunction），而表达式的OR还可以叫作析取（disjunction）。

12.5.2　从真值表构建逻辑表达式

任何布尔函数都可以用使用AND、OR和NOT运算符的逻辑表达式表示。为给定的布尔函数找到最简单的表达式一般是很难的。不过，为布尔函数构建某一表达式却很容易，用到的技巧也很简单。首先从函数的真值表开始，构建形如

m1 OR m2 OR…OR mn

的逻辑表达式。各个mi 都是与真值表中让函数的值为1的某一行对应的。因此该表达式中项数与表示函数的那列中1的个数是相等的。这些mi 项都被叫作最小项（minterm），并具有下面将要描述的特殊形式。

要开始对最小项的解释，首先要提到文字（literal），这里的文字要么为单个命题变量（比如p），要么为求反变量（比如我们一般会写为p 的NOT p）。如果真值表中有k 列表示变量的列， 那么每个最小项都是由k 个文字的逻辑AND（或“积”）表示的。设r 是我们想为其构建最小项的某一行。如果变量p 在行r 的值是1，就选择文字p。如果p 在行r 的值是0，则选择p 作为文字。行r 的最小项就是各变量对应文字的积。明确地讲，如果所有变量都有真值表行r 中的值，那么最小项的值就只可能是1。

现在要通过为与函数值为1的行对应的最小项求逻辑OR（或“和”），来为函数构建表达式。得到的表达式具有“积的和”的形式，或者说它是析取范式（disjunctive normal form）。该表达式是正确的，因为只有在存在值为1的最小项时，它的值才是1，而除非变量的值对应着真值表中该最小项所在的那行，而且该行的值为1，否则该最小项不可能为1。

示例 12.9

我们来为由图12-8中的真值表所定义的进位输出函数d 构建析取范式。值为1的行的编号分别是3、5、6和7。第3行有x=1、y=1和c=1，因此该行的最小项是\overline{x} AND y AND c，可以将其简写为\overline{x}yc。类似地，第5行的最小项是x\overline{y}c，第6行的最小项是xy\overline{c}，而第7行的最小项是xyc。因此所需的对应d 的表达式就是这些表达式的逻辑OR，也就是

\overline{x}yc+x\overline{y}c+xy\overline{c}+xyc　　　　　　(12.6)

这一表达式要比(12.5)更复杂。不过，我们将在12.6节中看到如何得出表达式(12.5)。

同样，通过把对应第1、2、4和7行的最小项相加，可以为和值位z 构建逻辑表达式，得到

\overline{x}\ \overline{y}c+\overline{x}y\overline{c}+x\overline{y}\ \overline{c}+xyc

运算符的完全集

用来设计(12.6)式这样析取范式的最小项技术表明，逻辑运算符AND、OR和NOT的集合是完全集，就是说，每个布尔函数都具有只使用这3种运算符的表达式。不难证明NAND本身也是完全的。我们可以将涉及AND、OR和NOT的函数只用NAND表示成如下这样。

1. ( p AND q)≡(( p NAND q) NAND TRUE)

2. ( p OR q)≡(( p NAND TRUE ) NAND (q NAND TRUE ))

3. ( NOT p)≡(p NAND TRUE)

通过用合适的NAND表达式来替换用到AND、OR和NOT的地方，可以把任何析取范式转换成只涉及NAND的表达式。同样，NOR自身也是完全的。

由运算符AND和OR构成的集合就不是完全集。比方说，它们没法表示函数NOT。要知道原因，我们可以注意到AND和OR都是单调的，这就是说，在把任何一个输入从0变为1时，输出都不能从1变成0。可以通过对表达式的大小进行归纳，证明任何只有AND和OR运算符的表达式都是单调的。不过NOT显然不是单调的，因此没办法只用AND和OR表示NOT。

p

q

r

a

b

0

0

0

0

1

0

0

1

1

1

0

1

0

0

1

0

1

1

0

0

1

0

0

1

0

1

0

1

1

0

1

1

0

1

0

1

1

1

1

0

图 12-10　用于习题的两个布尔函数

12.5.3　习题

1. 图12-10是用变量p、q 和r 定义a 和b 这两个布尔函数的真值表，为这两个函数分别写出析取范式。

2. 为下列函数写出合取范式（见下面的附注栏“和的积表达式”）。

(a) 图12-10中的函数a。

(b) 图12-10中的函数b。

(c) 图12-8中的函数z。

和的积表达式

有两种方式可以把真值表转换成涉及AND、OR和NOT的表达式，这里的表达式将会是文字之和（逻辑OR）的积（逻辑AND）。这种形式就叫作“和的积”，或合取范式（conjunction normal form）。

对真值表的各行而言，我们可以定义最大项，它是与所在行中某一参数变量的值不相同的文字的和。也就是说，如果该行中变量p 的值是0，就使用文字p，如果那行中p 的值为1，就使用\overline{p}。因此，除非每个变量p 都具有该行指定给p 的值，否则最大项的值就是1。

因此，如果查看真值表中值为0的各行，并为这些行的最大项取逻辑AND，该表达式就只会在输入匹配函数值为0的某一行时值为0。这样一来，该表达式对其他各行而言值都为1，也就是对真值表中函数值为1的那些行来说都是1。例如，图12-8的真值表中，第0、1、2和4行对应d 的值为0。比方说，第0行的最大项就是x+y+c，而第1行的最大项就是x+y+\overline{c}，所以d 的合取范式就是

(x+y+c)(x+y+\overline{c})(x+\overline{y}+c)(\overline{x}+y+c)

该表达式与(12.5)和(12.6)式都是等价的。

3. ** 以下哪个逻辑运算符可以单独形成运算符完全集：(a)≡；(b)→；(c)NOR？在每种情况中都对自己的答案加以证明。

4. ** 在16个双变量的布尔函数中，有多少函数自身就是完全的？

5. * 证明，单调函数的AND和OR还是单调的。然后证明只含AND和OR运算符的表达式都是单调的。

12.6　利用卡诺图设计逻辑表达式

在本节中，我们要展示一种为布尔函数确定析取范式的制表技巧。用这种方法生成的表达式通常要比12.5节中通过为真值表中所有必要的最小项求逻辑OR这样的权宜之计所构建出的表达式更简单。

举例来说，在示例12.7中，我们为一位加法器的进位输出函数对应的表达式进行了专门设计。可以看到，有可能使用不是最小项的文字之积，也就是说，缺少与某些变量对应的文字。例如，可以用文字之积xy 来涵盖图12-8中的第(6)和第(7)两行，因为只有在变量x、y 和c 具有这两行中的某一行所表示的值时，xy 的值才是1。

同样，在示例12.7中，我们使用了表达式xc 来涵盖第(5)和第(7)行，并用yc 涵盖第(3)和第(7)行。请注意，所有3个表达式都涵盖了第7行。不过这并没有什么坏处。其实，假如分别只使用对应第(5)和第(3)行的最小项，也就是x\overline{y}c和\overline{x}yc，来替代xc 和yc，我们会得到正确的表达式，但它就要比示例12.7中得到的表达式xy+xc+yc 多两个运算符。

这里的基本概念就是，如果两个最小项唯一的区别是某一个变量的值相反，比如第(6)和第(7)行的xy\overline{c}和xyc，就可以通过取相同的文字并去掉那个有区别的变量，把两个最小项结合起来。这一结论遵从以下一般法则

(pq+\overline{p}q)\equiv q

要理解这一等价性，就要注意到如果q 为真，那么要么pq 为真。要么\overline{p}q为真。而且反过来，如果pq 或\overline{p}q有一个为真，那么一定有q 为真。

12.7节中介绍了验证这些法则的技巧，不过现在只要其直觉含义支撑其使用即可。还要注意到，该法则的使用并不仅限于最小项。例如，可以设p 是任意命题变量，而q 是任意的文字之积。你可以合并任何两个只有一个变量不同的文字积（一个积含有变量本身，另一个则含有其互补变量），用由相同文字组成的一个积代替这两个积。

12.6.1　卡诺图

有一种制图技巧，可以根据真值表设计析取范式，这种方法对最多含4个变量的布尔函数来说效果甚佳。这种思路就是把真值表写成名为卡诺图（Karnaugh map）的二维数组，该二维数组的项（或者说“点”）各自表示真值表中的行。通过让只有一个变量不同的行所对应的点保持邻接，可以把有用的文字积看作某些矩形，而这些矩形中的点的值都是1。

12.6.2　双变量卡诺图

最简单的卡诺图是对应双变量布尔函数的。各行对应着其中一个变量的值，而各列对应另一个变量的值。图中的项是0或1，取决于两个变量值的组合使函数的值为0还是为1。因此，该卡诺图是双变量布尔函数真值表的二维表示。

示例 12.10

在图12-11中，我们看到表示“蕴涵”函数p→q 的卡诺图。其中4个点分别对应着p 和q 的值4种可能的组合。请注意，除了p=1且q=0的情况之外，“蕴涵”的值都是1，因此，卡诺图中值为0的点只有对应p=1且q=0的那项，其他点的值都是1。

图 12-11　表示p→q 的卡诺图

12.6.3　蕴涵项

布尔函数f 的蕴涵项（implicant）是一些文字的积x，它满足的条件是：f 中变量的任何赋值组合都不能使x 为真且f 为假。例如，每一个让函数f 的值是1的最小项都是f 的蕴涵项。不过，其他积也可以是蕴涵项，我们将会了解如何从f 的卡诺图中解读这些蕴涵项。

示例 12.11

最小项pq 是图12-11中“蕴涵”函数的蕴涵项，因为让pq 为真的变量赋值组合（即p=1且q=0）也能使“蕴涵”函数为真。

再举个例子，\overline{p}本身也是“蕴涵”函数的蕴涵项，因为使为真的两种p 和q 赋值组合，也能让p→q 为真。这两种赋值组合分别是p=0且q=0，以及p=0且q=1。

蕴涵项涵盖了函数值为1的那些点。通过为涵盖了所有令函数值为1的点的蕴涵项取OR，就可以为布尔函数构建逻辑表达式。

示例 12.12

图12-12展示了对应“蕴涵”函数的卡诺图中的两个蕴涵项。较大的那个涵盖了两个点，对应着单个文字\overline{p}。这一蕴涵项涵盖了卡诺图中顶部的两个点，这两个点的值都是1。而较小的蕴涵项pq 涵盖了p=1且q=1的那个点。因为这两个蕴涵项加在一起涵盖了所有值为1的点，所以它们的和\overline{p}+pq就是与p→q 等价的表达式，也就是说(p\to q)\equiv(\overline{p}+pq)。

图 12-12　表示p→q 的卡诺图中的两个蕴涵项\overline{p}和pq

与卡诺图中的蕴涵项对应的矩形必须具有特殊的“外观”。对源自双变量函数的简单卡诺图来说，这些矩形只可能是下列之一。

1. 单个点；

2. 某行或某列；

3. 整个图。

卡诺图中的单个点对应着最小项，通过为该点所在行和列相应变量对应的文字求积，便可以得出其表达式。也就是说，如果该点所在的行或列是0，就可以分别为该行或该列对应的变量取反。如果该点在对应1的行或列中，就取对应的变量本身。例如，图12-12中较小的蕴涵项就在p=1的那行和q=1的那列中。这就是我们要用非否定文字p 和q 的积作为该蕴涵项的原因。

双变量卡诺图中行或列对应着两个对一个变量相同而对另一个变量相反的点。与之对应文字的“积”就减少为单个文字。剩下的这个文字具有共同值为这些点所共享的变量。如果该共同值是0，那么该文字就是否定的，而如果共享的值是1，该文字就是非否定的。因此，图12-12中较大的蕴涵项，即第一行，其中的点具有相同的p 值。该值是0，这样就说明为该蕴涵项使用文字积\overline{p}是合理的。

由整个图组成的蕴涵项是种特例。原则上讲，这对应着积退化为常数1，或者说TRUE的情况。显然，对应逻辑表达式TRUE的卡诺图在图中所有点的位置都是1。

12.6.4　质蕴涵项

如果布尔函数f 的蕴涵项x 在删除其中任何文字后不再为蕴涵项，则x 就是f 的质蕴涵项（prime implicant）。事实上，质蕴涵项就是所含文字尽可能少的蕴涵项。

请注意，这样的矩形越多，其积中文字的数量就越少。我们一般会选择用文字较少的积替换具有很多文字的积，文字较少的积涉及的运算符更少，因此“更加简单”。所以我们在选择若干蕴涵项涵盖卡诺图时最好只考虑那些质蕴涵项。

请记住，对应某给定卡诺图的每个蕴涵项都只由值为1的点组成。一个蕴涵项之所以是质蕴涵项，是因为使其大小翻番可能会迫使我们融入一个值为0的点。

示例 12.13

在图12-12中，较大的蕴涵项\overline{p}是质蕴涵项，因为唯一可能比它还大的蕴涵项是全图，而后者不可能是蕴涵项，因为全图中含有0。较小的蕴涵项pq 不是质蕴涵项，因为它被包含在只由1组成、同为该“蕴涵”卡诺图蕴涵项的第二列中。图12-13展示出了该“蕴涵”图仅有的质蕴涵项。1它们对应着积\overline{p}和q，而且它们可以进一步组成表达式\overline{p}+q，我们在12.3节中就注意到这一表达式是与p→q 等价的。

1一般来讲，可能有多个可以涵盖某给定卡诺图的质蕴涵项集合。

图 12-13　对应“蕴涵”函数的质蕴涵项\overline{p}和q

12.6.5　三变量卡诺图

当真值表中有3个变量时，我们可以使用图12-14这样两行四列的图，该图对应图12-8所示的进位输出真值表。请注意，与两个变量（本例中是变量y 和c）的值对对应的各列是按照一种特别的次序排列的。原因在于，我们希望邻接的列对应的真值赋值只有一个变量是不同的。假如按照一般的顺序00、01、10、11来排列，中间的两列就会有y 和c 两个变量是不同的。还要注意，第一列和最后一列也是“邻接的”，这样它们只有变量y 是不同的。因此，当我们选择蕴涵项时，可以把第一列和最后一列看作2×2的矩阵，而且可以把每行的第一个点和最后一个点当作1×2的矩阵。

图 12-14　对应进位输出函数的卡诺图，其中质蕴涵项是xc、yc 和xy

我们需要推导该三变量卡诺图有哪些矩形表示可能的蕴涵项。首先，许可的矩形必须对应文字的积。在任何积中，各变量只可能以如下3种方式之一出现：否定的、非否定的，或根本没有。当变量是否定的或非否定的时，它会让对应蕴涵项的点数减半，因为只有具有该变量合适的值的点才属于该蕴涵项。因此，蕴涵项中的点数总是2的乘方。因此，对各变量而言，许可的蕴涵项是满足以下条件之一的若干个点。

1. 只包含该变量等于0的点；

2. 只包含该变量等于1的点；

3. 该变量是什么值都没有区别。

从卡诺图中解读蕴涵项

不管涉及多少个变量，都可以取任一表示蕴涵项的矩形，并生成只对该矩形中的点来说为TRUE的文字积。如果p 是任意变量，那么

1. 如果该矩形中的每个点都有p=1，那么p 是该积中的文字。

2. 如果该矩形中的每个点都有p=0，那么p 是该积中的文字。

3. 如果该矩形中某些点有p=0，而另一些点有p=1，那么该积中没有变量p 的文字。

对三变量卡诺图而言，可以按照以下方式列举可能的蕴涵项。

1. 任何点。

2. 任何列。

3. 任何一对水平邻接的点，包含末端环回的情况，也就是各行的第1列和第4列构成的一对。

4. 任何行。

5. 任何由两列邻接列组成的2×2正方形，包括末端环回的情况，也就是第1和第4列。

6.整个图。

示例 12.14

对应进位输出函数的3个质蕴涵项如图12-14所示。我们可以将各质蕴涵项转换成文字之积，详细方法见上文附注栏内容“从卡诺图中解读蕴涵项”。对应的积是最左边的xc，垂直的yc 和最右边的xy。这3个表达式的和就是我们在示例12.7中用非正式方法得出的析取范式，你现在应该就明白这一表达式是怎么得出的了。

示例 12.15

图12-15展示了与三变量布尔函数NAND(p,q,r )对应的卡诺图。质蕴涵项有

1. 第一行，对应\overline{p}；

2. 前两行，对应\overline{q}；

3. 第1和第4列，对应\overline{r}。

因此该卡诺图的析取范式是\overline{p}+\overline{q}+\overline{r}。

图 12-15　NAND(p,q,r )的卡诺图，其中质蕴涵项是\overline{p}、\overline{q}和\overline{r}

12.6.6　四变量卡诺图

四参数函数可以用4×4的卡诺图表示，该图中两个变量对应各行，另两个变量对应各列。对图中的行和列，我们必须用到之前为三变量卡诺图的列排序时所用到的次序，得到的四变量卡诺图就如图12-16所示。对四变量卡诺图来说，行和列的邻接都要考虑到末端环回的情况。也就是说，顶部的行和底部的行是邻接的，最左的列和最右的列是邻接的。作为一个重要的特例，4个角上的点也形成了一个2×2的矩形，它们对应着图12-16中的文字之积\overline{q}\ \overline{s}（这不是图12-16中的蕴涵项，因为右下角是0）。

图 12-16　标示了质蕴涵项，对应“至多一个1”函数的卡诺图

四变量卡诺图中对应文字积的矩形分别为：

1. 任何点；

2. 任何两个水平或垂直方向上的邻接点，包含那些末端环回情况下的邻接点；

3. 任何行或列；

4. 任何2×2正方形，包括那些末端环回的情况，比如顶部的那行中的两个点，以及同两列中底部那行的两个点。正如之前提过的，图中4个角上点也是这种“正方形”的一个特例；

5. 任何2×4或4×2的矩形，包括那些末端环回的情况，比如第一列加上最后一列；

6. 整个图。

示例 12.16

图12-16展示了具有p、q、r、s 4个变量布尔函数对应的卡诺图，该函数在输入中至多有一个1时值才是1。其中有4个质蕴涵项，都是大小为2的，而且其中有两个是末端环回的。顶部那行的第一个点和最后一个点组成的蕴涵项中，两个点的p、q 和s 变量具有相同的值，而且各变量的共同值都是0。因此它的文字积就是\overline{p}\ \overline{qs}。而类似地，其他蕴涵项的积分别是\overline{p}\ \overline{q}\ \overline{r}、\overline{p}\ \overline{r}\ \overline{s}和\overline{qrs}。所以对应该函数的表达式为

\overline{p}\ \overline{q}\ \overline{r}+\overline{pqs}+\overline{p}\ \overline{rs}+\overline{qrs}

图 12-17　4个角组成的蕴涵项为质蕴涵项的卡诺图

示例 12.17

之所以选择图12-17中的卡诺图，是因为其中的1所具有的模式，而不是出于其函数所具有的显著特征。这幅图展示一个重点。5个质蕴涵项一起涵盖了所示的全部值是1的点，其中包括由4个角构成的蕴涵项（用虚线表示），而该蕴涵项的文字积表达式是\overline{qs}，另外4个质蕴涵项分别具有文字积\overline{pqr}、\overline{q}r\overline{s}、 p\overline{q}r和p\overline{rs}。

从目前为止的例子来看，我们可能会觉得，要为该图生成逻辑表达式，应该要将全部5个蕴涵项取逻辑OR。不过，片刻思考后你就会觉得，最大的蕴涵项\overline{qs}是多余的，因为所有的点都已经被其他4个质蕴涵项涵盖了。此外，它也是唯一一个可以消除的质蕴涵项，因为其他4个质蕴涵项都各自含有一个只由自身涵盖的点。例如，\overline{p}\ \overline{qr}就是唯一一个涵盖了第一行第二列那个点的质蕴涵项。因此下列表达式就是从图12-17所示的卡诺图得到的所需的析取范式。

\overline{pq}\ \overline{r}+\overline{p}r\overline{s}+p\overline{q}r+p\overline{rs}

12.6.7　习题

1. 为变量p、q、r 和s 的以下函数画出卡诺图。

(a) 如果p、q、r 和s 中有一个、两个或三个为TRUE，则该函数为TRUE，如果没有一个为TRUE或全部为TRUE，则该函数不为TRUE。

(b) 如果p、q、r 和s 中至多有两个为TRUE，则该函数为TRUE，如果有三个或四个为TRUE，则该函数不为TRUE。

(c) 如果p、q、r 和s 中有一个、三个或四个为TRUE，则该函数为TRUE，如果没有一个为TRUE或有两个为TRUE，则该函数不为TRUE。

(d) 由逻辑表达式pqr →s 表示的函数。

(e) 如果pqrs 所表示的二进制数字的值小于10，则该函数为TRUE。

2. 为习题1中的各个卡诺图找出除了最小项之外的蕴涵项。它们中有哪些是质蕴涵项？为各函数找出涵盖卡诺图中所有1的质蕴涵项之和。是否要用到所有的质蕴涵项？

3. 证明，布尔函数析取范式中的每个积都是该函数的蕴涵项。

4. *大家还可以根据卡诺图构造合取范式。首先要找到形成蕴涵项的那种矩形，不过这里矩形中的点要全部为0，而不是全部为1。这样的矩形可以称为“反蕴涵项”。我们可以为各反蕴涵项构造一个对所有除反蕴涵项所含点之外的点而言值为1的文字和。对各变量x 而言，如果相应的反蕴涵项只包含x=0的点，则该文字和中具有文字x，而如果相应的反蕴涵项中只有那些x=1的点，它就具有文字\overline{x}。否则，该文字和中不含有涉及x的文字。

5. 利用习题4得到的答案，为习题1中的各函数写出相应的合取范式。要让合取范式中包含尽可能少的文字和。

6. ** 在4×4的卡诺图中，有多少构成蕴涵项的(a)1×2(b)2×2(c)1×4(d)2×4矩形？假设变量分别是p、q、r 和s，把它们的蕴涵项描述成文字积的形式。

12.7　重言式

重言式（tautology）是指不管其命题变量的值如何，其值都为真的逻辑表达式。对重言式而言，真值表的所有行，或者说卡诺图中的所有点，都具有值1。简单的重言式例子包括

TRUE
p+\overline{p}
(p+q)\equiv(p+\overline{p}q)

重言式有很多重要用途。例如，假设形如E1≡E2这样的表达式是重言式。那么，只要在任何表达式中出现E1的实例，就可以用E2替换E1，而得到的表达式仍然表示相同的布尔函数。

图12-18a展示了包含子表达式E1的逻辑表达式F所对应的表达式树。而图12-18b则是用E2代替E1的相同表达式树。原因在于，我们知道两棵树中标记为n的节点，也就是对应E1和E2的表达式树的根节点，在两棵树中一定有着相同的值，因为有E1≡E2。而为两棵树中n以上的部分求值，显然会得出相同的值，这样就证明了两棵树是等价的。这种等价表达式可以彼此替换的能力通俗点讲就是“以相等换相等”。请注意，在其他的代数，诸如算术、集合、关系或正则表达式代数中，也可以把一个表达式替换为另一个具有相同值的表达式。

图 12-18　展示以相等换相等的表达式树

示例 12.18

考虑逻辑运算符OR的结合律，可以将其表示为表达式

((p+q)+r )≡(p+(q+r ))　　　　　　(12.7)

图12-19展示了对应各子表达式的真值表。而标号为E 的最后一列就表示整个表达式。不难看出，对应E 的每一行都具有值1，这说明表达式(12.7)是重言式。这样一来，只要我们看到形如(p+q)+r 的表达式，就可以直接将其替换为p+(q+r )。请注意，p、q和r可以代表任何表达式，只要两边的p、q 和r 各自使用了相同的表达式，可以保持一致即可。

p

q

r

p+q

(p+q)+r

q+r

p+(q+r )

E

0

0

0

0

0

0

0

1

0

0

1

0

1

1

1

1

0

1

0

1

1

1

1

1

0

1

1

1

1

1

1

1

1

0

0

1

1

0

1

1

1

0

1

1

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

1

1

图 12-19　证明OR的结合律的真值表

12.7.1　替换原则

正如我们在示例12.18中指出的，当给出涉及某些特定命题变量的法则时，该法则不仅适用于字面上的那些变量，而且可以用任何表达式来替换各变量。根本原因在于，在我们对重言式的一个或多个变量进行替换后，重言式还是重言式。这一事实称为替换原则（substitution principle）。2当然，我们必须用同样的表达式替换多次出现的同一个变量。

2不应该把替换原则与“以相等换相等”弄混。替换原则只适用于重言式，而在任何表达式中都能够以相等换相等。

示例 12.19

逻辑运算符AND的交换律可以通过证明逻辑表达式pq ≡qp 是重言式得到验证。要得到这一法则的一些实例，可以对该表达式进行替换。例如，可以用 r + s 替换p，并用\overline{r}替换q，得到等价式

(r+s)(\overline{r})\equiv(\overline{r})(r+s)

请注意，这里为每个被替换的表达式都加上了括号，以防因为运算符优先级约定而意外改变运算符的分组。在该情况中，r+s 两边的括号是必要的，但\overline{r}两边的括号则可以省略掉。

还有其他的替换实例如下。可以用r 替换p，而且不替换q，这样就得到rq ≡qr。可以只留下p，把q 替换为常量表达式1（TRUE），从而得到p AND 1≡1 AND p。不过，我们用r 代替式子中 出现的第一个p，并用另一个不同的表达式r+s 替换第二个p。也就是说，rq ≡q(r+s )不是重言式（如果s=q=1且r =0，它的值就是0）。

如果考虑表达式树，就可以看到替换原则一直成立的原因了。想象一下对应某个重言式的表达式树，比如图12-20所示的对应示例12.19中重言式的表达式树。因为该表达式是重言式，所以我们知道，不管为处于叶子节点处的命题变量指定什么真值，根节点的值都为真（只要我们为标号为某给定变量的各个叶子节点指定相同的真值）。

图 12-20　对应重言式 pq ≡qp 的表达式树

现在假设用具有表达式树Tp 的表达式替换p，并用具有表达式树Tq 的表达式替换q，一般来说，我们会为重言式的每个变量选择一棵树，并用为该变量选择的树替换对应该变量的所有叶子节点。3这样就得到了一棵类似图12-21所示的新表达式树。当为新树的变量指定真值时，作为树Tp 根节点的各个节点都有相同的值，因为任何这样的节点背后都执行了相同的求值步骤。

3作为特例，为某个变量x选择的树可能是标号为x的单个节点，就和没有对x 进行替换一样。

图 12-21　对图12-20中变量的替换

一旦图12-21中Tp 和Tq 这样的树的根节点完成求值，就得到与图12-20所示的原有的树根节点处变量相同的值。也就是说，不管我们为出现的那些Tp 算出什么样的值，它们一定是全部相同的，我们要取这个值，并将其指定给原有的树中标号为p 的叶子节点。我们还要为q 进行相同的处理，而且一般来说，要为出现在原有的树中的任何节点进行这一处理。因为原有的树表示重言式，所以可知为该树求值会在根节点得到值TRUE，而且新构造的树也能在根节点处生成值TRUE。因为不管为新树中的变量进行怎样的值替换，以上推理都能保持成立，所以可以得出结论：由新树表示的表达式也是重言式。

12.7.2　重言式问题

重言式问题就是测试某给定逻辑表达式是否等价于TRUE，也就是说，测试该表达式是否为重言式。有一种简单方式可以解决该问题。为该表达式构建真值表，其中每一行对应表达式中各变量的一种真值赋值。然后为该表达式的表达式树中各个内部节点创建一列，并按照合适的从下到上的次序，针对变量的各种真值赋值为各个节点求值。当且仅当对每种真值赋值而言整个表达式的值都是1（TRUE）时，该表达式是重言式。示例12.18就展示了这一过程。

12.7.3　重言式测试的运行时间

如果表达式有k 个变量和n 个运算符，那么这种真值表就有2k 行和n 列需要填写。因此我们可以预期这种算法的简单实现要花O(2kn) 的时间。这一时间对只有两三个变量的表达式来说并不长，即便是对20个变量来说，用计算机也只需要几分钟就能完成测试。不过，对30个变量而言，有10亿行，就算是使用计算机，也几乎没法完成这一测试。这一结果是用到指数时间算法的典型下场。对较小的实例来说，一般看不出什么问题。但随着问题实例变大，突然间我们会发现，即使有着速度最快的计算机，也不可能在可以接受的时间内解决这个问题。

图 12-22　P 是可在多项式时间内解决的问题族，NP 是可在非确定多项式时间内解决的问题族，NPC 则是NP 完全问题族

固有的难解问题

重言式问题“E 是否为重言式”看似天生是指数时间的问题。也就是说，如果表达式E 中有k 个变量，所有已知解决重言式问题的算法的运行时间都是k 的指数函数。

存在这样一类称为NP完全问题的问题，其中包含了很多重要的优化问题，而没人知道如何在少于指数时间的时间内解决这些问题。很多数学家与科学家经过长时间的艰难尝试，试着为这些问题中至少一个问题找到运行时间少于指数时间的算法，不过这样的算法还没被找到过，而很多人现在怀疑根本不存在这样的算法。

可满足性问题（satisfiability problem）就是一个经典的NP完全问题，这个问题是说“是否存在一种真值赋值让逻辑表达式为真？”可满足性问题与重言式问题有着密切的关系，而且就像重言式问题一样，对可满足性问题来说，也没有比循环经历所有可能的真值赋值好更多的解决方案了。

要么所有的NP完全问题都具有少于指数时间的解决方案，要么所有的NP完全问题都没有这样的解决方案。因此各NP完全问题看似需要指数时间这一事实让我们更加相信这些问题天生是指数时间的问题。有很强的迹象表明这种简单的可满足性测试就是最好的做法了。

顺便提一句，NP代表“非确定多项式”（Nondeterministic Polynomial）。粗略地讲，“非确定”就意味着“猜测正确的能力”，正如10.3节中讨论过的。如果为针对某个大小为n的实例的解决方案给出一次猜测，我们可以在多项式时间（也就是对某常数c 而言的时间nc）内验证该猜测是正确的，就说该问题能在“非确定多项式时间内解决”。

可满足性是这种问题的一个例子。如果为变量给出一组声明（或者说猜测）为可以使表达式E 得到值1的真值赋值，我们可以将赋值代入操作数为E 求值，并在至多为E 的长度的二次方的时间内验证该表达式是否得到满足。

像可满足性问题这样可以通过猜测加上多项式时间的验证来“解决”的这类问题称为NP 问题。有一些NP 问题其实是相当简单的，不经过猜测就可以解决，而且只需要花输入长度的多项式的时间。不过，有很多NP 问题被证实非常难，而这些问题就是NP完全问题。（不要把这里表示“这类问题中最难”的“完全”，与之前表达式“能表示每个布尔函数”的“运算符完全集”中的“完全”弄混了。）

在多项式时间内不通过猜测就可以解决的问题族通常称为P。图12-22展示了P、NP 和NP完全问题之间的关系。如果任何NP完全问题在P 中，那么p=NP，我们会非常怀疑这种情况，因为所有已知的NP完全问题以及一些其他的NP 问题，都不会出现在P 中。没人相信重言式问题会在NP 中，不过它的难度不低于NP 中的任何问题（被称为NP 难题），而且如果重言式问题在p 中，那么有p=NP。

12.7.4　习题

1. 以下表达式中哪些是重言式？

(a) pqr →p+q

(b) ((p→q)(q→r ))→(p→r )

(c) (p→q)→p

(d) \bigl(p\equiv(q+r)\bigr)\to (\overline{q}\to pr)

2. * 假设有一种为逻辑表达式解决重言式问题的算法，说明如何用这种算法实现下列目的。

(a) 确定两个表达式是否等价。

(b) 解决有关可满足性的问题（见上文附注栏“固有的难解问题”）。

12.8　逻辑表达式的一些代数法则

在本节中，我们将列举一些实用的重言式。在各种情况中，我们都只陈述法则，而将重言式的验证工作留给读者通过构造真值表来完成。

12.8.1　等价的法则

首先要从一些与等价如何起效有关的结论开始。大家应该注意到等价性在这里的双重身份。它是我们在逻辑表达式中使用的众多运算符之一。不过，它也是表示两个表达式“相等”并能互相替换的符号。因此形如E1≡E2这样的重言式表明了一些与E1和E2有关的信息，即利用“相等可以由相等替换”的原则，它们在更大的表达式中是可以相互替换的。

此外，我们可以利用等价证明其他的等价。如果有一列表达式E1、E2、…、Ek，满足每个表达式都能通过相等换相等的替换从前一个表达式得到，那么在用相同的真值赋值为这些表达式求值时，它们会得到相同的值。这样一来，E1≡Ek 一定是重言式。

12.1 等价的自反性：p≡p。

正如我们要陈述的所有法则一样，替换原则是适用的，这样可以用任意表达式代替p。因此该法则表明任何表达式都是与自身等价的。

12.2 等价的交换律：(p≡q)≡(q≡p)。

非正式地讲，当且仅当q 等价于p 时有p 等价于q。根据替换原则，如果任一表达式E1与另一表达式E2等价，那么E2就等价于E1。因此E1和E2是可以互相替换的。

12.3 等价的传递性：((p≡q)AND(q≡r))→(p≡r)。

非正式地讲，如果p等价于q，而且q等价于r，那么p就等价于r。这条法则具有一个重要的推论，如果我们得出E1≡E2和E2≡E3是重言式，那么E1≡E3也是重言式。

12.4 否定的等价：(p\equiv q)\equiv(\overline{p}\equiv\overline{q})。

当且仅当两个表达式的否定等价时，这两个表达式是等价的。

12.8.2　类似算术的法则

在算术运算符+、×和一元减号与逻辑运算符OR、AND和NOT之间存在一种类比。因此以下法则应该不会让大家感到意外。

12.5 AND运算的交换律：pq≡qp。

非正式地讲就是，只有在qp 为真时，pq 才为真。

12.6 AND运算的结合律：p(qr )≡(pq)r。

非正式地讲，要为3个变量（或表达式）的AND分组，既可以先取前两个变量（或表达式）的AND，也可以先取后两个变量（或表达式）的AND。此外，加上法则12.5，我们可以证明任意一系列命题或表达式的AND都可以按照我们的意愿随意排列和分组——结果都是相同的。

12.7 OR运算的交换律：(p+q)≡(q+p)。

12.8 OR运算的结合律：(p+(q+r ))≡((p+q)+r )。

这一法则和法则12.7表明了任何表达式集的OR都可以随意分组。

12.9 AND对OR的分配律：p(q+r)≡(pq+pr)。

也就是说，如果我们希望为p 和两个命题或表达式的OR取AND，既可以先取OR，也可以对p 与各表达式先取AND，得到的结果是相同的。

12.10 1（TRUE）是AND的单位元：p AND 0≡p。

请注意，(1 AND p)≡p 也是重言式。我们不需要说出它，因为它可由替换原则和之前的法则得出。也就是说，可以在12.5（AND的结合律）中用1替换p 并用p 替换q，从而得到重言式(1 AND p)≡(p AND 1)。然后，应用12.3（等价的传递性），就得到(1 AND p)≡p。

12.11 0（FALSE）是OR的单位元：(p OR 1)≡p。

同样地，可以利用与12.10如出一辙的论证，得出(0 OR p)≡p。

12.12 0是AND的零元：(p AND 0)≡0。4

4当然(0 AND p)0也成立，我们之后不会再提到那些结合律的结果。

回想一下10.7节，运算符的零元是指这样一个常数，我们对该常数和任意值应用该运算符所得到的值都是该零元。请注意，在算术运算中，0是×的零元，但+是没有零元的。不过，我们会看到1是OR的零元。

12.13 双重否定的抵消：(NOT NOT p)≡p。

算术和逻辑运算符类比的利用

我们使用对应AND和OR的简写符号时，往往可以假装自己是在处理乘法和加法，正如我们在法则12.5到12.12中所使用的。这是种优势，因为我们对相应的算术运算法则是非常熟悉的。因此，大家应该能很快用pr+ps+qr+qs 或q(s+r )+(r+s)p 来替换(p+q)(r+s)。

更难也是更需要练习的部分就是应用那些与算术运算不相似的法则。比如德摩根律和OR对AND的分配律。例如，用(p+r )(p+s)(q+r )(q+s)替换pq+rs 是可以的，但要看出这是通过3次应用OR对AND的分配律，并利用交换律和结合律得到的，需要费一些思量。

12.8.3　AND和OR与加和乘的区别

还有很多法则表现出了AND和OR与算术运算符×和+的区别，这里要列举一些。

12.14 OR对AND的分配律：(p+qr)≡(p+q)(p+r ))。

就像AND可以对OR分配那样，OR也可以对AND分配。请注意，相似的算术形式，x+yz≡(x+y)(x+z)一般而言是不成立的。

12.15 1是OR的零元：(1 OR p)≡1。

请注意，相似的算术形式1+x=1一般来说是不成立的。

12.16 AND的幂等性：pp≡p。

回想一下，当运算符应用到某相同值的两个副本时，得到的结果还是该值，就说该运算符是幂等的。

12.17 OR的幂等性：p+p≡p。

请注意， ×和+都不是幂等的。也就是说，一般来说x×x=x 和x×x=x 都是不成立的。

12.18 吸收律。

这一法则有两个版本，取决于我们想消除的是多余的积还是多余的和。

(a) (p+pq)≡p

(b) p(p+q)≡p

请注意，如果在(a)中用任意文字积替换p，并用另一个文字积替换q，就可以说，在析取范式中，可以消除那些具有其他某个积所含文字之超集的积。较小的集合就被吸收到超集之中。在(b)部分中，我们对合取范式作出同样的说明，可以消除那些是其他某个和中文字之超集的和。

12.19 某些否定的消除。

(a) p(\overline{p}+q)\equiv pq

(b) p+\overline{p}q\equiv p+q

请注意，(b)就是我们在12.2节中解释莎莉的条件为何能替换山姆的条件时用到过的法则。

12.8.4　德摩根律

还有两条法则让我们可以把NOT压入AND和OR的表达式中，得到一个由各命题变量的否定组成的表达式。得到的表达式是应用到文字的AND-OR表达式。从直觉上讲，如果们为具有AND和OR的表达式取反，就可以把否定沿着表达式树向下压，随着该过程“翻转”运算符。也就是AND会变成OR，反之亦然。最后，否定到达叶子节点的位置，并停留在那里，除非它们遇到否定文字，在这种情况下，就要利用法则12.13消除两次否定。在构造新表达式时，一定要注意加上恰当的括号，因为在交换AND和OR时运算符的优先级改变了。

这些基本规则就叫“德摩根律”，它们是以下两个重言式。

12.20 德摩根律

(a) NOT(pq)\equiv\overline{p}+\overline{q}

(b) NOT(p+q)\equiv \overline{p}\ \overline{q}

(a)部分说明，只有在p 和q 之中至少有一个为假时，p 和q 才都不为真。而(b)部分说明，当且仅当p 和q 都为假时，p 和q 才都不为真。我们可以将这两条法则一般化，使其按照如下方式应用到任意数量的命题变量上。

(c) (NOT(p1p2…pk))≡(\overline{p}_1+\overline{p}_2+\cdots+\overline{p}_k)

(d) (NOT(p1+p2+…+pk))≡(\overline{p}_1\overline{p}_2\cdots\overline{p}_k)

例如，(d)说明当且仅当一系列表达式全为假时，它们才一个都不为真。

示例 12.20

我们已经在12.5和12.6节中了解到了如何为任意逻辑表达式构造析取范式。假设要从任意可以写成E1+E2+…+Ek，其中各Ei 都是文字的AND的表达式E开始。就可以构造NOT E 的合取范式，首先有

NOT(E1…E2+…+Ek)

然后应用德摩根律(d)，得到

(NOT(E1))(NOT(E2))…(NOT(Ek))　　　　　　(12.8)

现在设Ei 是文字积\overline{X}_{i1}\overline{X}_{i2}\dots\overline{X}_{ij_i}，其中各X要么是变量，要么是变量的否定。那么我们可以对NOT(Ei )，将其变为

\overline{X}_{i1}+\overline{X}_{i2}+\cdots+\overline{X}_{ij_i}

如果某个文字X 是否定变量，比方说是\overline{q}，那么利用法则12.13，消除双重否定，\overline{X}就应该被替 换成变量q 本身。在进行所有的改变之后，式(12.8)就变成了文字和的积。

例如，rs+\overline{r}\ \overline{s}就是只有在r≡s 时才为真的析取范式，也就是说，它可以视作利用AND、OR和NOT对等价进行的定义。以下公式是上式的否定，只有在r 和s 不等价，也就是r 和s 刚好只有一个为真时才为真。

NOT(rs+\overline{rs})　　　　　　(12.9)

现在对德摩根律(b)进行替换，用rs 替换p，并用\overline{r}\ \overline{s}替换q。那么(b)的左边就成了式(12.9)，而根据替换原则可知，式(12.9)等价于对(b)进行相同替换后的右边，也就是

NOT(rs)AND NOT(\overline{rs})　　　　　　(12.10)

现在我们可以应用(a)，其中用r 替换p 并用s 替换q，将NOT (rs)转换成\overline{r}+\overline{s}。同样，(a)告诉我们，NOT(\overline{r}\ \overline{s})与NOT(\overline{r})+NOT(\overline{s})是等价的。不过NOT(\overline{r})就等同于NOT(NOT(r ))，也就等价于r，因为双重否定是可以抵消的。同样NOT(\overline{s})也可以被s替代，因此式(12.10)等价于(\overline{r}+\overline{s})(r+s)。这是表示“r 和s 刚好只有一个为真”的合取范式。粗略地说，它表示“r 和s 至少有一个为假，而且r 和s 至少有一个为真。”显然，这种情况只有在r 和s 中刚好有一个为真时才会发生。

12.8.5　对偶性原理

在审视本节所介绍的法则时，我们会注意到一个奇特的现象：这些等价性似乎都是成对出现的，只不过其中的AND和OR角色互换了而已。例如，法则12.19的(a)部分和(b)部分就是这样的一对，而法则12.9和12.14也是这样的一对，后者就是两条分配律。在涉及常数0和1时，它们也必须互换，就像在12.10和12.11这两条有关单位元的法则中那样。

在德摩根律中可以找到这一现象的解释。假设从重言式E1≡E2开始，其中E1和E2都是涉及运算符AND、OR和NOT的表达式。根据法则12.4，有NOT(E1)≡NOT(E2)也是重言式。现在应用德摩根律把否定压过AND和OR。我们要做的，就是将每个AND“反转”为OR，反之亦然。而且我们会把否定下移到各操作数处。如果遇到NOT运算符，就直接把这个“移动的”NOT移到该NOT运算符下方，直到遇到另一个AND或OR。例外就是当我们遇到否定的文字，比方说\overline{p}时。然后，我们把这个移动的NOT与已经存在的那个结合起来，留下操作数p。作为特例，若移动的NOT遇到常数0或1，就要为该常数取否，也就是(NOT 0)≡1和(NOT 1)≡0。

示例 12.21

我们来考虑重言式12.19(b)。首先要为两边取否，这样就得到了图12-23a所示的树。然后把否定压过等价两边的OR，将它们变成AND，NOT符号就出现在两个OR的各参数之上，如图12-23b所示。新的NOT中有3个在变量之上，所以它们的移动就停止了。而在AND之上的那个会将该AND反转成OR，并使NOT出现在它的两个参数之上。这样右边的参数就成了NOT q，而左边的参数NOT p就成了NOT NOT p，也就是p。得到的树如图12-23c所示。

图12-23c的树表示表达式\overline{p}(p+\overline{q})\equiv\overline{p}\ \overline{q}。要让该表达式变成法则12.19(a)的形式，就必须为这些变量取否。也就是说，要用\overline{p}替换p，并用\overline{q}替换q。当消除双重否定之后，剩下的就刚好是法则12.19(a)。

图 12-23　构造对偶表达式

12.8.6　涉及蕴涵的法则

这里还有若干实用的重言式，给出了→运算符的属性。

12.21 (p→q)AND(q→p)≡(p≡q)。

也就是说，当前仅当两个表达式互相蕴涵时，它们是等价的。

12.22 (p≡q)→(p→q)。

两个表达式的等价表明其中一个蕴涵另一个。

12.23 蕴涵的传递性：((p→q)AND(q→r ))→(p→r )。

也就是说，如果p 蕴涵q，而且q 蕴涵r，那么有p 蕴涵r。

12.24 可以把蕴涵用AND和OR表示出来，最简单的形式如下。

(a) (p\to q)\equiv(\overline{p}+q)。

我们会看到，很多情况下，要处理的表达式会形如“如果这个而且这个而且……，那么那个”。例如，Prolog语言和很多“人工智能”语言都依赖这种形式的“规则”。这些规则通常会写成(p1p2…pn)→q。通过以下等价，它们可以只用AND和OR表示出来。

(b) (p_1p_2\cdots p_n\to q)\equiv(\overline{p}_1+\overline{p}_2+\cdots+\overline{p}_n+q)。

也就是说，只要q 为真，或者这些p 中有一个或多个为假，该等价的左边和右边就都为真，否则这两边都为假。

12.8.7　习题

1. 通过构建真值表，验证法则12.1到12.24都是重言式。

2. 可以用表达式替换重言式中的任何命题变量，并得到另一个重言式。在法则12.1到法则12.24这些重言式中，用x+y 替换p，yz 替换q，并用\overline{x}替换r，得到新的重言式。如果需要的话，不要忘了给新换上的表达式加上括号。

3. 证明：

(a) p1+p2+…+pn 与pi 任意次序的和（逻辑OR）等价。

(b) p1p2pnpi 任意次序的积（逻辑AND）等价。

提示：2.4节中为加法展示过相似的结果。

4. * 利用本节给定的法则，把每一对表达式中的第一个表达式变形为第二个。为了减少工作量，在使用类似算术法则的法则12.5到12.13时，可以省略使用它们的步骤。例如，AND和OR的交换律和结合律是可以假定的。

(a) 把pq+rs 变形为(p+r )(p+s)(q+r )(q+s)。

(b) 把pq+p\overline{q}r变形为p(q+r )。

(c) 把pq+p\overline{q}+\overline{p}q+\overline{p}\ \overline{q}变形为1（该变形需要用到12.9节介绍的法则12.25）。

(d) 把pq→r 变形为(q→r )+(q→r )。

(e) 把NOT(pq→r )变形为pq\overline{r}。

5. * 利用之前的法则证明吸收律12.18(a)和12.18(b)，也就是说明只使用法则12.1到12.17就可以把p+pq 变形为p，并可以把p(p+q)变形为p。

6. 应用德摩根律，将以下表达式变形为NOT只作用于命题变量（也就是NOT只出现在文字中）的表达式。

(a) NOT(pq+\overline{p}r)

(b) NOT(NOT p+q(NOT(r+\overline{s})))

7. * 利用基本法则12.20(a)和(b)，通过对k的归纳证明一般化的德摩根律12.20(c)和(d)。然后，通过描述对应各表达式及其子表达式的真值表的样子，粗略验证这一一般化法则。

8. * 找出本节中相互对偶的法则对。

9. * 通过对n的归纳证明法则12.24(b)。

10. * 通过描述对应表达式及其各子表达式具有2n行的真值表，证明法则12.24(b)成立。

11. 使用吸收律以及AND和OR的交换律和结合律，简化以下表达式

(a) w\overline{x}+w\overline{x}y+\overline{z}\ \overline{x}w

(b) (w+\overline{x})(w+y+\overline{z})(\overline{w}+\overline{x}+\overline{y})(\overline{x})

12. * 通过给出一些特殊的数字使得类比的等式不成立，表明法则12.14到12.20的算术类比是不成立的。

13. * 如果从那些只含AND、OR和NOT运算符的逻辑表达式开始，可以把所有的NOT向下压，直到NOT全部紧邻命题之上，也就是说，表达式是文字的AND和OR。证明我们能做到这一点。提示：只要看到NOT，要么它紧邻另一个NOT之上（这种情况下可以根据规则12.13抵消这两个NOT），要么它在命题之上（这种情况下命题就得到满足了），再或者它在AND和OR之上（这种情况下可以利用德摩根律将其压到下一层）。不过，想通过对诸如标号为NOT的节点高度之和这样显见的“大小”度量进行归纳，证明最终可以得到所有NOT都在命题之上的等价表达式，是不可能行得通的。原因在于，在利用德摩根律将NOT向下压时，它会变成NOT，这个和可能增加。为了证明最终可以得到所有NOT都在命题之上的等价表达式，需要找到一种合适的“大小”度量，在把NOT压到AND或OR之下的方向上应用德摩根律时，这个大小度量总是递减的。找到这样的大小度量，并证明该声明。

12.9　重言式及证明方法

在12.6到12.8这3节中，我们已经看到了逻辑的一个方面：它作为设计理论的用途。在12.6节中，我们看到如何利用卡诺图为给定的布尔函数设计表达式，而在第13章中我们会看到这种方法论是如何用到开关电路设计中的，而开关电路是构建计算机和其他数字设备的基础。12.7节和12.8节为我们介绍了重言式，它们可以用来简化表达式，因此在为给定布尔函数设计优质表达式时，重言式是另一种重要工具。

逻辑的第二个重要用途将在本节中得到体现。当人们推理或证明数学命题时，他们会用到很多技巧来推进自己的论证，这些技巧包括：

1. 情况分析；

2. 换质位法；

3. 反证法；

4. 归约法。

本节中要定义这些技巧，展示它们各自是如何应用到证明中的。我们还会展示如何通过命题逻辑中的某些重言式来验证这些技巧。

12.9.1　排中律

首先要介绍一些表示与如何进行推理有关的基本事实的重言式。

12.25 排中律：(p+\overline{p})\equiv1是重言式。

也就是说，某事物要么为真，要么为假，不存在中间状态。

示例 12.22

作为法则12.25的应用，同时也利用到我们目前已经了解的若干其他法则，可以证明12.6节中用过的法则(pq+\overline{p}q)\equiv q。首先根据法则12.1，等价的自发性，用1 AND q 替换p，就有

(1 AND q)≡(1 AND q)

接着，通过法则12.25，可以“以相等换相等”，用p+\overline{p}替换上式左边的1，因此

((p+\overline{p})q)≡(1 AND q)

是重言式。对该等价的右边使用法则12.10，用q 替换1 AND q。然后对左边，我们使用12.9，AND对OR的分配律，进而利用法则12.5，AND的交换律，从而证实左边与pq+\overline{p}q等价。因此有

(pq+\overline{p}q)\equiv q

这正是我们想要的。

将排中律一般化，就得到了名为“情况分析”（case analysis）的证明技巧，其中我们想证明某表达式E。我们会取另一个表达式F，及其否定NOT F，并证明F和NOT F 都蕴涵E。因为F 肯定要么为真要么为假，所以我们就得出了E。情况分析的正式依据是如下重言式。

12.26 情况分析：((p\to q)AND(\overline{p}\to q))≡q。

也就是说，这两个实例是在p 为真和p 为假时发生的。如果q 被两个实例蕴涵，那么q 一定为真。我们把证明12.26可由12.25和其他已证明的法则得出这一任务留作本节习题。

12.27 p\overline{p}\equiv 0

命题及其否定不可能同时为真。这一法则在使用“反证法”时显得至关重要。我们很快就会在法则12.29中讨论这一证明技巧，而且在12.11介绍分解证明时也要提及。

12.9.2　换质位法

有时候我们想要证明p→q 这样的蕴涵，却发现证明\overline{q}\to\overline{p}这一被称为p→q 的质位变换命题的等价表达式要更加简单。这一原则可以用如下法则公式化。

12.28 质位变换法则（contrapositive law）：(p\to q)\equiv(\overline{q}\to\overline{p})。

示例 12.23

我们来考虑一个简单的例子，向大家展示可以如何利用质位变换法则。这个示例还表现了

命题逻辑在证明过程中的局限。逻辑只能完成部分工作，允许我们在不参考命题本身含义的情况下对命题进行推理。不过，要得到完整的证明，通常还必须指定一些参数，让它们指代各项的含义。对本例来说，我们需要知道像“质数”、“奇数”和“大于”这样与整数有关的概念的含义是什么。

我们要考虑下面3个与正整数x 有关的命题

a

“x>2”

b

“x是质数”

c

“x是奇数”

我们想要证明的定理就是ab→c，也就是

命题 “如果x 大于2且是质数，那么x 是奇数。”

首先要应用已经了解的一些法则，将表达式ab→c 变形为更方便证明的等价表达式。首先，我们要利用法则12.28将其变成质位变换命题的形式\overline{c}→NOT(ab)。然后利用德摩根律12.20(a)将NOT(ab)变形为\overline{a}+\overline{b}。也就是说，可以把该定理变形为\overline{c}\to(\overline{a}+\overline{b})。换句话说，需要证明

命题 “如果x 不是奇数，那么它要么不大于2，要么不是质数。”

我们可以把“不是奇数”替换为“是偶数”，“不大于2”替换成“小于等于2”，并把“不是质数”替换为“是合数”。因此要证明的是

命题 “如果x是偶数，则要么有x<2，要么有x是合数。”

现在已经将命题逻辑应用到极致了，接下来必须开始谈论这些项的含义了。如果x 为偶数，那么对某个整数y 而言有x=2y，这也就是x 为偶数的含义。因为在该证明中假设了x 为正整数，所以y 一定是大于等于1的。

现在可以使用情况分析了，分别考虑y=1和y>1这两种情况，因为我们论证过y≥1，所以这是仅有的两种情况。如果y=1，那么x=2，这样就证明了x≤2。如果y>1，那么x 是2和y 这两个都大于1的整数的积，这就表示x 是合数。因此我们证明了，如果x 是偶数，那么要么有x≤2（在y=1情况下），要么有x 是合数（在y >1的情况下）。

12.9.3　反证法

我们经常不是“直接”证明表达式E，而是利用更简单的方式，首先假设NOT E，然后利用矛盾（也就是表达式FALSE）进行证明。这种证明的依据是以下重言式。

12.29 反证法：(\overline{p}\to0)\equiv p。

粗略地讲，如果由\overline{p}可以得出0，也就是得出FALSE或引起矛盾，就和证明了p 是一样的。这一条法则其实是由其他法则得出的。如果用\overline{p}替换法则12.24中的p，用0替代其中的q，就得到如下等价

(\overline{p}→0)≡(NOT(\overline{p})+0)

根据法则12.13，双重否定可以抵消，于是就可以把NOT(\overline{p})替换为p，这样就有了

(\overline{p}\to 0)\equiv(p+0)

而法则12.11告诉我们，(p+0)=p，进一步替换就得出了

(\overline{p}\to 0)\equiv p

示例 12.24

现在重新考虑一下示例12.23中的命题a、b、c，在这里例子中我们假设x 是正整数，并分别断言x>2、x 是质数、x 是奇数。我们想要证明定理ab→c，因此可以用该表达式替换法则12.29中的p。那么\overline{p}\to 0就成了(NOT(ab→c))→0。

如果对第一个蕴涵使用法则12.24，就得到

(NOT(NOT(ab)+c ))→0

对里层的NOT应用德摩根律就得到(NOT(\overline{a}+\overline{b}+c))→0。再次利用德摩根律，并两次利用法则12.13消除双重否定，就将该表达式变成了(ab\overline{c})\to 0。

这就是命题逻辑所能做到的极限了，现在必须进行与整数有关的推理。我们必须从a、b和\overline{c}开始，并得出矛盾。换句话说，首先要假设x>2，x 是质数，而且x 是偶数，并一定要从这些假设中得出矛盾。

因为x 是偶数，所以可以说对某个整数y而言有x=2y。因为x>2，就一定有y≥2。不过这样一来，等于2y 的x 就是两个大于1的整数的积，也就是说x 是个合数。因此就证明了x 不是质数，也就是命题\overline{b}。因为给定了b，也就是x是质数，现在又有了\overline{b}，这样就有了b\overline{b}，而根据法则12.27，它是等于0，或者说为FALSE的。

于是证明了(NOT(ab→c))→0，根据法则12.29这就等价于ab→c。这样也就完成了反证法证明。

12.9.4　等价于真

下一种证明方法让我们可以通过以相等换相等，直到表达式归约为1（TRUE），证明该表达式是重言式。

12.30 通过等价于真证明：(p≡1)≡p。

示例 12.25

表达式rs→r表示，两个表达式的AND蕴涵了第一个表达式（而且根据AND的交换律，也蕴涵了第二个表达式）。可以通过以下一系列等价证明rs→r是个重言式。

rs → r
1) ≡ NOT(rs) + r
2) ≡ (\overline{r}+\overline{s}) + r
3) ≡ 1 + \overline{s}
4) ≡ 1

应用法则12.24，用AND和OR定义→，得到(1)。应用德摩根律得出(2)。利用法则12.7和12.8，重新排列各项，然后根据法则12.25用1替代r+\overline{r}，就得到了(3)。最后，应用法则12.13，1是OR的零元，这样就有了(4)。

12.9.5　习题

1. 证明法则12.25和12.27是相互对偶的。

2. * 我们想证明定理“如果x 是完全平方数而且x 是偶数，那么x 可以被4整除。”

(a) 指定代表该定理中提到的3个有关x 的条件的命题变量。

(b) 把该定理用这些命题正式地表示出来。

(c) 用命题变量的形式和口头描述的形式给出(b)小题得到命题的质位变换命题。

(d) 证明(c)小题得到的命题。提示：要注意到，如果x 不能被4整除，那么要么x 是奇数，要么x=2y 且y 是奇数。

3. * 用反证法证明习题2中的定理。

4. * 针对有关整数x 的命题“如果x3是奇数，那么x 是奇数”，重复习题2和习题3（不过在习题2的(a)小题中只讨论了两种情况）。

5. * 通过证明以下表达式等价于1（TRUE），证明它们是重言式。

(a) pq+r+\overline{q}\ \overline{r}+\overline{p}\ \overline{r}

(b) p+\overline{q}\ \overline{r}+\overline{p}r+q\overline{r}

6. * 通过对之前已经证明的法则（的实例）进行以相等换相等，证明法则12.26：情况分析。

7. * 将情况分析法则一般化为由k 个命题变量定义情况的情形，这些变量在所有2k个组合中可能为真或为假。那么验证k=2的情况的重言式是什么？对一般的k 来说呢？证明该重言式为何一定为真。

12.10　演绎

我们在12.6节到12.8节中看到了作为设计理论的逻辑，并在12.9节中看到了作为证明技巧的逻辑。现在，我们要看看逻辑的第三面：逻辑在演绎中的使用。演绎就是可以构成完整证明的一系列命题。学习过平面几何的话就应该对演绎证明很熟悉，在演绎证明中我们从某些前提（“给定条件”）开始，并经过一系列步骤证明结论，其中每一步都是由前一个步骤经过有限次数的推理（称为推理规则）得到的。我们在本节中会解释演绎证明的构成，并给出若干示例。

不巧的是，为重言式找到演绎证明是很难的。正如我们在12.7节中提过的，这是个“固有的难解”问题，是属于NP困难问题一类的。因此要找到演绎证明，要么靠运气，要么就要穷举查找。在12.11节中，我们会讨论分解证明，虽然在最坏情况下它和其他技巧一样也必须花上指数时间，但它看起来是对寻找证明方法的一种好的探索。

12.10.1　演绎证明的构成

演绎的应用

除了作为数学证明的根本组成，演绎证明或者说形式证明在计算机科学中也有很多用途。应用之一是自动证明定理（automated theORem proving）。存在一些这样的系统：通过搜索从前提行进到结论的步骤序列，从而确定定理的证明过程。有些系统会自行查找证明，而另一些则会与用户进行交互，接受提示并填补构成证明的步骤序列中存在的小间隙。有人认为，虽然要让这样的系统投入实际使用还有很长的路要走，但它们最终可以用于证明程序的正确性。

演绎证明的第二个用途是用在与推导计算相关的编程语言中。举个简单的例子，机器人在寻找通过迷宫的路径时，可以把可能的状态用通道中心位置的有限集表示出来。我们可以绘制一幅图，其中的节点表示这些位置，而弧u→v就意味着机器人可以从位置u直接前移到位置v，因为u 和v 表示的是邻接的通道。

还可以把这些位置想象成命题，其中u 代表“机器人可以到达位置u。”那么u→v 就不仅能被解释为一条弧，还可以解释为一种逻辑蕴涵，也就是说“如果机器人可以到达u，那么它可以到达v。”（请注意这里的“双关”，箭头符号既可以表示弧，也可以表示蕴涵。）我们很自然地要问：“机器人从位置a 可以到达哪些位置?”

如果取表达式a，以及所有对应邻接位置u 和v 的表达式u→v 作为前提，看看可以从这些前提证明哪些命题变量x，就可以把该问题用演绎的形式表示出来。在这种情况下，我们并非真正需要像演绎证明这般强大的工具，因为正如在9.7节中讨论过的，深度优先搜索就能完成任务。不过，还有很多相关的情形，使用图论方法不是很有效率，但问题可以用演绎的形式表示，并得到合理的解决方案。

假设给定了某些逻辑表达式E1、E2、…、Ek 作为前提，并希望得出形如另一个逻辑表达式E的结论。一般来说，结论和前提都不会是重言式，不过我们想要证明

( E1 AND E2 AND…AND Ek )→E　　　　　　(12.11)

是个重言式。也就是说，想要证明，如果前提E1、E2、…、Ek 为真，就能得到E 为真。

一种证明(12.11)的方式就是为其构造真值表，并检验其中各行是否都是1，这是验证重言式的例行检验。不过，出于如下两个原因，这样可能并不足够。

1. 正如上文提过的，如果表达式中存在太多的变量，重言式的检验就会变得非常棘手。

2. 更重要的是，尽管重言式的验证对命题逻辑来说能起效，但它不能检验更复杂逻辑系统（比如第14章中将要讨论的谓词逻辑）中的重言式。

通常可以通过给出演绎证明来证明(12.11)是重言式。演绎证明是若干行组成的序列，每一行要么是给定的前提，要么是由之前的一行或多行根据推理规则构造出来的。如果最后一行是E，就说这是从E1、E2、…、Ek 证明了E。

可以使用的推理规则有很多。唯一的要求就是，如果推理规则允许我们只要有表达式F1、F2、…、Fn 是证明中的行，就可以把表达式F 写为一行，就有

(F1 AND F2 AND … AND Fn)→F

一定是重言式。例如，

(a) 任何重言式都可以用作证明中的一行，而不管前面的行是什么。这一规则成立的原因在于，如果F 是重言式，那么证明中0行的AND蕴涵了F。请注意，按照约定，0个表达式的AND是1，而当F 为重言式时，1→F 就是重言式。

(b) 肯定前件式假言推理（modus ponens）的规则是说，如果E 和E →F 是证明中的行，就可以把F 添加为证明的行。肯定前件式假言推理是由重言式(p AND (p→q))→q 得出的，这里是用表达式E 代替了p 并用F 代替了q。唯一的微妙之处在于，我们不需要E AND E →F 这样一行，而是需要单独的两行，一行是E，一行是E →F。

(c) 如果E 和F 是证明中的两行，那么可以添加一行E AND F。这样做可行的原因在于(p AND q)→(p AND q)重言式，可以用任意表达式E 替换p，用F 替换q。

(d) 如果有E 和E ≡F 这两行，那么可以添加一行F。可以这样做的原因类似于肯定前件式假言推理，是因为E ≡F 蕴涵E →F。也就是说，(p AND (p≡q))→q 是重言式，而推理规则(d)是该重言式可替换出的实例。

无人喝彩的声音

我们常常需要理解为0个操作数应用运算符的极限情况，就像在推理规则(a)中所做的那样。我们断言，可以把0个表达式（或证明中的行）的AND当作具有真值1。这样的动机在于，除非F1、F2、…、Fn中有一个为假，否则F1 AND F2 AND…AND Fn为真。但是如果n=0，也就是一个F都没有，那么该表达式就不可能为假，因此很自然地将0个表达式的AND取为1。

我们要作出这样一个约定，只要对0个操作数应用运算符，得到的结果就应该是该运算符的单位元。因为可以预见0个表达式的OR是0，因为只要其中有一个表达式为真，多个表达式的OR就为真。同样，0个数字之和被取为0，而0个数字之积则被取为1。

示例 12.26

假设我们具有如下命题变量，具有表中所示的直觉含义。

r

“天在下雨。”

u

“乔伊带着伞。”

w

“乔伊被淋湿了。”

给定以下前提

r→u

“天在下雨，乔伊就会带着伞。”

u→w

“乔伊带着伞，所以他没被淋湿。”

r→w

“如果没下雨，乔伊是不会被淋湿的。”

现在要求证明\overline{w}，也就是，乔伊绝不会被淋湿。从某种意义上讲，这个问题不值一提，因为大家可以验证

((r→u)AND(u\to \overline{w})AND(\overline{r}\to \overline{w}))→\overline{w}

是个重言式。不过，还是可以利用12.8节介绍的一些代数法则，以及刚刚讨论过的一些推理规则，从前提证明\overline{w}。如果要处理形式比命题逻辑更为复杂的逻辑，或者是要处理涉及很多变量的逻辑表达式，就需要采取这种证明方式。图12-24展示了一种可能的证明方式，以及每个步骤进行下去的依据。

这种证明的大概思路是，利用情况分析，考虑天在下雨及没下雨这两种情况。根据第(5)行我们就证明了，如果天在下雨，那么乔伊不会被淋湿，而根据第(6)行，由给定的前提，说明如果没下雨，乔伊就不会被淋湿。第(7)到第(9)行结合了这两种情况，以得到我们想要的结论。

{%}

图 12-24　演绎证明的示例

12.10.2　演绎证明“起作用”的原因

回想一下，演绎证明首先有前提E1、E2、…、Ek并要添加额外的行（也就是表达式），这些行都蕴涵自E1 AND E2 AND…AND Ek 。我们所添加的每一行都蕴涵自之前的0条或更多行，或者是某一行前提。我们可以通过对目前为止已经添加的行的数目进行归纳，来证明 E1 AND E2 AND… AND Ek 蕴涵了证明过程中的每一行。要完成这一任务，需要两个涉及语言的重言式族。第一个重言式族是从→的传递性一般化而来的。对任何n，有：

((p→q1)AND(p→q2)AND…AND(p→qn)AND((q1q2…qn)→r))→(p-r )　　　　　　(12.12)

也就是说，如果p 蕴涵了各个qi，而且qi 一起蕴涵r，那么有p 蕴涵r。

我们可以通过以下推理得出(12.12)是重言式。(12.12)为假的唯一可能就是p →r 为假，而且左边那一串为真。不过p →r 只能在p 为真且r 为假时为假，所以我们要假设p 和\overline{r}为真。然后必须证明(12.12)的左边为假。

如果(12.12)的左边为真，那么其中由AND连接的各个子表达式都为真。例如，p→q1为真。因为我们假设p 为真，那么要让p→q1为真，就只可能是q1为真。同样，可以得出结论：q2、…、qn都为真。因此q1q2…qn→r 一定为假，因为我们假设r 为假，而且刚刚发现所有的qi 都为真。

首先假设(12.12)为假，因此得到右边一定为真，所以p 和\overline{r}都为真。然后可以得出，当p 为真且r 为假时，(12.12)的左边为假。但如果(12.12)的左边为假，则(12.12)本身为真，这样就得出了矛盾。因此(12.12)绝不可能为假，所以它是重言式。

要注意到，如果(12.12)中有n=1，就有了→的传递性的情况，也就是法则12.23。还有，如果n=0，那么(12.12)就成了(1→r)→r，这是个重言式。回想一下，当n=0时，按约定q1q2…qn 被取为AND的单位元，也就是1。

我们还需要一类重言式来证实可以为证明添加前提。它是对示例12.25中讨论过的重言式的一般化。我们声明，对任何满足1≤i≤m 的m 和i 来说，

(p1p2…pm)→pi　　　　　　(12.13)

是重言式。也就是说，一个或多个命题的AND蕴涵它们之中的任何一个。

表达式(12.13)之所以是重言式，是因为唯一让它为假的可能就是左边为真且右边(pi) 为假。但如果pi 为假，那么pi 和其他p 的AND必然为假，所以(12.13)的左边为假。但只要(12.13)的左边为假，它就为真。

现在可以证明，如果给定下列两个条件

1. 前提E1、E2、…、Ek；

2. 一组推理规则，满足只要这些推理规则允许我们写一行F，那么该行要么是Ei 中的某一个，要么对某组之前的行F1、F2、…、Fn，存在重言式

(F1 AND F2 AND…AND Fn)→ F

则对各行F，(E1 AND E2 AND…AND Ek) →F 一定是重言式。要对添加到证明中的行的数量进行归纳。

依据。我们以0行的情况作为依据。这一命题成立，因为它表示的是与证明中每行F 有关的信息，而且并没有这样的行需要讨论。也就是说，我们的归纳命题其实形如“如果F 为证明的一行，那么……”，而且我们知道如果条件为假，那么这样的“如果-那么”命题就为真。

归纳。对归纳部分而言，假设对之前的各行G，有

(E1 AND E2 AND…AND Ek)→G

是重言式。设F 是添加的下一行。就有两种情况。

演绎证明与等价证明

我们在12.8节和12.9节中看到的证明方式与12.10节研究的演绎证明有着不同的风格。不过，这两种证明都需要构建一系列的重言式，以得出所需的重言式。

在12.8节和12.9节中我们看到了等价证明，由一个重言式开始，通过各种替换得出另外的重言式。得到的所有重言式对某些表达式E 和F 而言具有E ≡F 的形式。这种证明风格会被用于三角学中，例如，在证明“三角恒等式”时会用到。

演绎证明也需要寻找重言式。唯一的区别在于，其中各个重言式都形如E →F，其中E 是前提的AND，而F是证明中我们实际要得出的行。事实上，我们不写出整个重言式只是一种表示上的便利，而非本质上的区别。我们也应该很熟悉这种证明方式，它常用于平面几何中的证明。

情况1：F是前提之一。那么 (E1 AND E2 AND…AND Ek)→F是重言式，因为它源自(12.13)，是m=k，而且对j=1、2、…、k，用Ej 替换各个pj 得到的。

情况2：F 是因为推理规则

(F1 AND F2 AND…AND Fn)→F

而被添加的，其中各个Fj 都是之前各行中的某一行。根据归纳假设

(E1 AND E2 AND…AND Ek)→Fj

对各个 j 而言都是重言式。因此，如果用Fj 替换(12.12)中的qj，用

E1 AND E2 AND…AND Ek

代替p，并用F 代替r，我们就会知道，对表达式E 和F 中变量的真值进行任何替换，都会使(12.12)的左边为真。因为(12.12)是重言式，所以每一种真值赋值都会让右边为真。而这里的右边是(E1 AND E2 AND…AND Ek)→F。由此可以得出，该表达式对每种真值赋值都为真，也就是说，它是个重言式。

我们现在已经得出了归纳的结论，而且证明了对证明中的每行都有

(E1 AND E2 AND…AND Ek)→F

特别要说的是，若证明中最后的那行是我们的目标E，就知道(E1 AND E2 AND…AND Ek)→E。

12.10.3　习题

1. * 从下列各小题给出的前提，分别给出对相应结论的证明。大家可以使用推理规则(a)到(d)。而对于重言式，只可以使用12.8节和12.9节中陈述过的法则，以及用“以相等换相等”的方式从这些法则的实例得到的重言式。

(a) 前提：p→q，p→r。结论：p→qr。

(b) 前提：p→(q+r )，p→(q+r )。结论：p→q。

(c) 前提：p→q，qr →s。结论：qr→s。

2. 说明以下内容为何是推理规则。如果E→F 是证明的一行，而且G 是任何表达式，那么我们可以添加E→(F OR G )这样一行。

12.11　分解证明

正如我们在本章前面的内容中提过的，寻找证明是个困难问题，而且因为重言式问题看起来是天生的指数时间问题，所以没有通行的方式可以使寻找证明变得简单。不过，有很多已知的只针对“典型”重言式的技巧，看起来对找寻证明所需的探索工作有所帮助。在本节中我们就要研究一条实用的推理规则——分解（resolution），它可能是这些技巧中最基本的一条了。分解是基于以下重言式的。

\bigl((p+q)(\overline{p}+r)\bigr)\to(q+r)　　　　　　(12.14)

这条推理规则的有效性是很容易验证的。想让它为假只有一种情况，就是q+r 为假，而且左边的表达式为真。如果q+r 为假，那么q 和r 都为假。假设p 为真，则\overline{p}为假。那么\overline{p}+r为假，而(12.14)的左边就一定为假。同样，如果p 为假，那么p+q 为假，还是说明(12.14)的左边为假。因此，不可能让(12.14)的左边为真且右边为假，所以可以得出(12.14)是个重言式。

应用分解的一般方式是把前提转换成子句，这些子句是文字的和（逻辑OR）。我们可以把各个前提都转换成子句的积。而我们的证明要以这些子句作为证明中的行开始，这样做的原因是各子句都是“给定的”。然后应用分解规则构造新的行，而这些行总能证明是子句。也就是说，如果(12.14)中的q 和r 各自被任意文字和所替代，那么q+r 也将是文字和。

在实际应用中，我们将通过删除重复来简化子句。也就是说，如果q 和r 都包含文字X，这种情况下就要从q+r 中删除X 的一个副本。之所以可以这样做，是因为有法则12.17、12.7和12.8，也就是OR的幂等性、交换律和结合律。一般而言，实用的看法是把子句看作文字的集合，而非文字的列表。结合律和交换律让我们可以按照任意方式排列文字，而幂等性则让我们可以消除重复。

还要消除那些含有互斥文字的子句。也就是说X 和\overline{X}在一个子句中出现，那么利用法则12.25、12.7、12.8和12.15，该子句等价于1，就不需要在证明中包含该子句。也就是说，根据法则12.25，(X+\overline{X})\equiv 1，而且根据零元法则12.15，1与任何逻辑表达式求OR都等价于1。

示例 12.27

考虑子句(a+\overline{b}+c)和 (\overline{d}+a+b+e)。我们可以让b 扮演(12.14)中p 的角色，那么q 就是\overline{d}+a+e，而r 就是a+c。请注意，我们已经重新进行了一些调整，把子句与(12.14)匹配起来。首先，第二个子句与(12.14)中的第一个子句p+q 已经匹配，而第一个子句是与(12.14)的第二个子句匹配的。此外，扮演p 的角色的变量一开始并未出现在我们的两个子句中，不过没关系，因为OR的交换律和结合律说明我们能够以任何次序重新排列子句。

如果我们的两个子句已经出现在证明中，则新子句q+r 也可以作为证明中出现的行，这个新子句就是(\overline{d}+a+e+a+c)。可以消除多余的a，将该子句简化为(\overline{d}+a+e+c)。

再举个例子，考虑子句(a+b)和(\overline{a}+\overline{b})。如果a是(12.14)中的p，而q 是b，r 是\overline{b}，就得出新子句(b+\overline{b})。该子句等价于1，因此不需要生成。

12.11.1　把逻辑表达式变成合取范式

为了让分解起作用，需要把所有的前提以及结论，变成和的积的形式，也就是“合取范式”。可以采取的方法有若干种，最简单的可能就是以下这些。

(1) 首先，要消除除了AND、OR和NOT之外的任何运算符。我们根据法则12.21把E ≡F 替换为(E→F )(F→E )。然后，根据法则12.24，把G→H 替换为NOT(G )+(H )。NAND和NOR也很容易分别用NOT后加上AND或OR来替代。事实上，因为AND、OR和NOT是运算符的完全集，所以可知任何逻辑运算符，包括那些本书中没有介绍的，都可以用只涉及AND、OR和NOT的表达式替换。

(2) 接下来，应用德摩根律把所有的否定向下压，直到它们根据12.8节中的法则12.13被其他否定抵消，或是只应用到命题变量上。

(3) 现在要应用OR对AND的分配律，把所有的OR压到所有AND之下。得到是由OR结合的文字，然后是由AND结合的表达式，这就是合取范式表达式。

示例 12.28

我们来考虑以下表达式

p+(q AND NOT(r AND(s-t ))

请注意，为了均衡考虑简洁性和清晰性，我们在这里和以后的表达式中会混用简化符号和原始符号。

第(1)步要求把s→t 替换为\overline{s}+t，给出只含AND、OR、NOT的表达式

p+(q AND NOT(r (\overline{s}+t )))

在第(2)步中，必须利用德摩根律把第一个NOT向下压。在接下来的一系列步骤中NOT到达了命题变量。

p+(q(\overline{r}+NOT(\overline{s}+t )))
p+(q(\overline{r}+(NOT \overline{s})(\overline{t})))
p+(q(\overline{r}+(s\overline{t})))

现在应用法则12.14，把第一个OR压到第一个AND以下。

(p+q)\Bigl(p+\bigl(\overline{r}+(s\overline{t})\bigr)\Bigr)

接下来要利用12.8节的法则12.8重新组合命题变量，从而把第二和第三个OR压到第二个AND之下。

(p+q)\bigl((p+\overline{r})+(s\overline{t})\bigr)

最后，再次利用法则12.14，所有的OR都在所有AND之下。得到的如下表达式就是合取范式。

(p+q)(p+\overline{r}+s)(p+\overline{r}+\overline{t})

12.11.2　利用分解的推理

我们现在看到了从前提E1、E2、…、Ek 找到E 的证明的一种方法，并了解了其大致脉络。把E 和E1、E2、…、Ek 分别转换为合取范式表达式F 和F1、F2、…、Fk 。我们要为一对对子句应用分解规则，因此要为证明添加新子句作为证明的行。然后，如果向证明中添加了F 的所有子句，就证明了F，从而也证明了E。

示例 12.29

假设以表达式(r\to u)(u\to \overline{w})(\overline{r}\to \overline{w})作为前提。请注意，该表达式是示例12.26中使用过的前提的AND。5设像示例12.26中那样，所需的结论是\overline{w}。我们可以根据法则12.24，替换掉这些→，把前提转换成合取范式。至此，得到的结果已经是合取范式，不需要进行进一步的处理。所需的结论\overline{w}已经是合取范式，因为任何单个文字都是子句，而单个子句就是子句的积。因此我们一开始有子句

5大家现在应该已经看到，不管是写成很多条前提，还是把它们用AND连接起来写出一条前提，都是可以的。

(\overline{r}+u)(\overline{u}+\overline{w})(r+\overline{w})

现在，假设要以r 扮演p 的角色，分解第一个和第三个子句，得到的子句就是u+\overline{w}。该子句可以与前提中的第二个子句一起被分解，以u 代替p，得到子句(\overline{w})。因为该子句就是所需的子句，所以任务就完成了。图12-25把证明过程展示为一系列语句，其中每一行都是一条子句。

图 12-25　(\overline{w})的分解证明

分解为何有效

一般来说，找到证明需要组织起从前提到结论这一系列行的运气或技巧。大家现在可能已经注意到，尽管很容易验证12.10节和12.11节中给出的证明是有效证明，而完成那些需要寻找证明的习题就要困难得多。一般来说，猜测示例12.29中那样为了生成某一子句或某些子句而要执行的一系列分解，并不比寻找证明简单多少。

不过，如果把分解与反证法结合起来，就像在示例12.30中那样，就可以看到分解的魔力。因为我们的目标子句是0，是“最小的”子句，突然间就有了搜寻“方向”的概念。这就是说，可以试着逐步证明更小的子句，以期最终能证明0。当然，这样的探索并不能确保成功。有时候，我们在开始缩小子句并最终证明0之前必须证明某个非常大的子句。

其实，分解是针对命题演算的完全证明过程。只要(E1E2…Ek )→E 是重言式，就可以从以字句形式表示的E1、E2、…、Ek 和NOT E 得出0。是的，这就是逻辑学家们为“完全”赋予的第三个含义。回想一下，其他两种含义分别是“能够表示任何逻辑函数的运算符集合”，以及“NP完全”中那样指“一类问题中最难的问题”。这里还是要说，存在这样的证明并不代表找到这样的证明很容易。

12.11.3　利用反证法的分解证明

将分解用作证明机制的一般方式与示例12.29中的情况多少有些区别。我们不是从前提开始并试着证明结论，而是从前提和结论的否定开始，试着得出不含文字的子句。这一子句的值为0，或者说FALSE。例如，如果我们有子句(p)和\overline{p}，就能以q=r=0应用(12.14)，得到子句0。

这种方式之所以有效，是因为12.9节中提到的法则12.19，或者说(\overline{p}\to 0)\equiv p。在这里，设p 是要证明的命题：对某些前提E1、E2、…、Ek 和结论E 而言，有(E1E2…Ek )→E。那么\overline{p}就是NOT((E1E2…Ek)→E )，或者利用法则12.24，就是NOT(NOT(E1E2…Ek)+E )。若干次应用德摩根律就可以得出p等价于E_1E_2\cdots E_k\overline{E}。因此，要证明p，可以改为证明\overline{p}\to 0，或者说是证明(E_1E_2\cdots E_k\overline{E})\to 0。也就是说，我们证明了前提和结论的否定一起蕴涵着矛盾。

示例 12.30

现在重新考虑示例12.29，不过这次要从3个前提子句和所需结论的否定——子句(w)——开始。0的分解证明如图12-26所示。利用反证法，可以得出这些前提蕴涵了所需的结论\overline{w}。

图 12-26　利用反证法的分解证明

12.11.4　习题

1. 利用真值表，验证表达式(12.14)是重言式。

a

某人的血型为A型

b

某人的血型为B型

c

某人的血型为AB型

o

某人的血型为O型

t

某人的血样进行测试T 的结果为阳性

s

某人的血样进行测试S 的结果为阳性

图 12-27　习题2的命题

2. 设命题具有如图12-27给定的含义，写出表示如下概念的子句或子句之积。

(a) 如果测试T 结果为阳性，那么此人的血型为A型或AB型。

(b) 如果测试S 结果为阳性，那么此人的血型为B型或AB型。

(c) 如果某人血型为A型，那么测试T 的结果为阳性。

(d) 如果某人血型为B型，那么测试S 的结果为阳性。

(e) 如果某人血型为AB型，那么测试T 和测试S 的结果都为阳性。提示：请注意，(\overline{c}+st)不是子句。

(f) 一个人的血型可能是A、B、AB或O其中的一种。

3. 利用分解，找到由习题(2)中可以得出的所有重要子句。大家应该忽略那些可以简化为1（TRUE）的无关紧要的子句，还要忽略那些文字是其他某个子句D 文字真超集的子句C。

4. 为12.10节的习题(1)给出使用了分解和反证法的证明。

12.12　小结

在本章中，我们已经看到了命题逻辑的要素，包括下列这些：

  • 基本运算符，AND、OR、NOT、→、≡、NAND和NOR；

  • 利用真值表表示逻辑表达式的含义，包括根据表达式构造真值表以及根据真值表构造表达式的算法；

  • 诸多应用到逻辑运算符的代数法则中的一部分。

我们还谈论了作为设计理论的逻辑，具体如下：

  • 卡诺图如何有助于我们为至多含4个变量的逻辑函数设计简单的表达式；

  • 逻辑代数法则有时候是如何用来简化逻辑表达式的。

然后，我们看到逻辑可以帮我们表示和理解常见的证明技巧，比如：

  • 利用情况分析进行证明；

  • 利用换质位法进行证明；

  • 利用矛盾进行证明（反证法）；

  • 利用对真实的归约进行证明。

最后，我们研究了演绎法，也就是一行行证明语句的构造，注意其中几点：

  • 存在大量推理规则，比如“肯定前件式假言推理”，让我们可以从证明中之前的行构造新一行；

  • 通过把证明的行表示为文字和，并把这些和以实用的方式组合，分解技巧通常能帮助我们迅速找到证明；

  • 不过，尚无已知算法可以保证在少于以表达式大小为指数的时间内找到表达式的证明；

  • 此外，因为重言式问题是“NP困难问题”，所以不存在少于指数时间的解决该问题的算法这一观点是非常可信的。

12.13　参考文献

对逻辑推理的研究可以追溯到亚里士多德的时代。Boole [1854]研究出了命题代数，而布尔代数正是由此而来。

Lewis和 and Papadimitriou [1979]对逻辑进行了稍微高级一些的处理，Enderton [1972]和 Mendelson [1987]是常见的数学逻辑处理，Manna和Waldinger [1990]从证明程序正确性的视角表现了逻辑这一主题。

Genesereth and Nilsson [1987]是从逻辑在人工智能中的应用这一视角来处理逻辑的。在该书中，大家可以看到更多与寻找证明的探索有关的内容，其中包括类似分解的技巧。把分解作为证明方法的原始论文是Robinson [1965]。

要了解更多难解问题的理论，请阅读Garey and Johnson [1979]。NP完全问题的概念是由Cook [1971]提出的，而论文Karp [1972]则明确了常见问题相应概念的重要性。

Boole, G. [1854]. An Investigation of the Laws of Thought, McMillan; reprinted by Dover Press, New York, in 1958.

Cook, S. A. [1971]. “The complexity of theorem proving procedures,” Proc. Third Annual ACM Symposium on the Theory of Computing, pp. 151–158.

Enderton, H. B. [1972]. A Mathematical Introduction to Logic, Academic Press, New York.

Garey, M. R. and D. S Johnson [1979]. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York.

Genesereth, M. R.and N. J. Nilsson [1987]. logical Foundations for Artificial Intelligence, Morgan-Kaufmann, San Mateo, Calif.

Karp, R. M. [1972]. “Reducibility among combinatorial problems,” in Complexity of Computer Computations (R. E. Miller and J. W. Thatcher , eds), Plenum, New York, pp. 85–103.

Lewis, H. R. and C. H. Papadimitriou [1981]. Elements of the Theory of Computation, Prentice-Hall, Englewood Cliffs, New Jersey.

Manna, Z. and R. Waldinger [1990]. The Logical Basis for Computer Programming (two Volumes), Addison-Wesley, Reading, Mass.

Mendelson, E. [1987]. Introduction to Mathematical Logic, Wadsworth and Brooks, Monterey, Calif.

Robinson, J. A. [1965]. “A machine-oriented logic based on the resolution principle,” J. ACM 12:1, pp. 23–41.

目录