离散数学其次章

本文格式为Word版，下载可任意编辑——离散数学其次章

2.1等值式

一、等值式的概念

两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全一致时即代表了一致的命题。

设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有一致的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都一致。于是等价式AB应为重言式。

定义2.1设A,B式两个命题公式，若A,B构成的等价式A

B是等值的，记作A

B.

B为重言式，则称A与

定义中给出的符号不是联结词符，它是用来说明A与B等值（AB是重言式）的一种记法，因而是元语言符号。此记号在下文中频繁出现，千万不要将它与混为一谈，同时也要注意它与一般等号=的区别。判断等值式有如下方法：1.真值表

2.等值演算

3.范式

二、用真值表判断公式的等值

例2.1判断下面两个公式是否等值：

┐(p∨q)与┐p∧┐q

解用真值表法判断┐(p∨q)

(┐p∧┐q)是否为重言式。此等价式的真值表如表2.1

(┐p∧┐q)。

所示，从表中可知它是重言式，因而┐(p∨q)与┐p∧┐q等值，即┐(p∨q)

其实，在用真值表法判断AB是否为重言式时，真值表的最终一列（即AB的

真值表的最终结果）可以省略。若A与B的真值表一致，则AB，否则，AB（用来表示A与B不等值，也是常用的元语言符号）。

表2.1(p∨q)(┐p∧┐q)的真值表

例2.2判断以下各组公式是否等值：

（1）p→(q→r)与(p∧q)→r

（2）(p→q)→r与(p∧q)→r

解表2.2中列出了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)→r的真值表不同，因而它们不等值，即

(p→q)→r(p∧q)→r

表2.23个公式的真值表

三、等值演算

虽然用真值法可以判断任何两个命题公式是否等值，但当命题变项较多时，工作量是很大的。可以先用真值表验证一组基本的又是重要的重言式，以它们为基础进行公式之间的演算，来判断公式之间的是否等值。本书给出16组重要的等值式，希望读者牢牢记住它们。在下面公式中出现的A,B,C依旧是元语言符号，它们代表任意的命题公式。

1.双重否定律A┐┐A（2.1）2.幂等律AA∨A,A

A∧A（2.2）

3.交换律A∨BB∨A，A∧BB∧A（2.3）

4.结合律(A∨B)∨CA∨(B∨C)

(A∧B)∧CA∧(B∧C)（2.4）

5.分派律A∨(B∧C)(A∨B)∧(A∨C)（∨对∧的分派律）A∧(B∨C)

(A∧B)∨(A∧C)（∧对∨的分派律）6.德摩根律┐(A∨B)┐A∧┐B，┐(A∧B)┐A∨┐B（2.6）7.吸收律A∨(A∧B)A，A∧(A∨B)A（2.7）

8.零律A∨1

1,A∧00（2.8）

9.同一律A∨0A，A∧1

A（2.9）

10.排中律A∨┐A1（2.10）11.矛盾律A∧┐A0（2.11）12.蕴涵等值式A→B┐A∨B（2.12）

13.等价等值式(AB)(A→B)∧(B→A)（2.13）14.假言易位A→B┐B→┐A（2.14）15.等价否定等值式AB┐A┐B（2.15）

2.5）

（

16.归谬论

(A→B)∧(A→┐B)

┐A（2.16）

以上16组等值式包含了24个重要等值式。由于A,B,C可以代表任意的公式，因而以上各等值式都是用元语言符号书写的，称这样的等值式为等值式模式，每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式（2.12）中，取A=p，B=q时，得等值式

p→q┐p∨q

当取A=p∨q∨r，B=p∧q时，得等值式

(p∨q∨r)→(p∧q)┐(p∨q∨r)∨(p∧q)

这些具体的等值式都被称为原来的等值式模式的代入实例。每个具体的代入实例的正确性都可以用真值表证明之，而每个等值式模式可用归纳法证明之。

由已知的等值式可以推演出更多的等值式，简单快速推理，还需要一些保持等值性的规则。

置换规则设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式，若B

A，则Φ(B)

Φ(A).

此置换规则的正确性，可用归纳法证明之。

例如，在公式(p→q)→r中，可用┐p∨q置换其中的p→q，由蕴涵等值式可知，p→q┐p∨q，所以，

(p→q)→r┐(┐p∨q)→r

在这里，使用了置换规则。假使再一次地用蕴涵等值式及置换规则，又会得到

(┐p∨q)→r┐(┐p∨q)∨r

假使再用德摩根律及置换规则，又会得到

┐(┐p∨q)∨r(p∧┐q)∨r

再用分派律及置换规则，又会得到

(p∧┐q)∨r(p∨r)∧(┐q∨r)

将以上过程连在一起，得到

公式之间的等值关系具有自反性、对称性和传递性，所以上述演算中得到的5个公式彼此之间都是等值的。在演算的每一步都用到了置换规则，因而在以下的演算中，置换规则均不标出。

上述用等值式及等值规则进行推演的过程称为等值演算，这是数理规律的主要内容。

例2.3用等值演算法验证等值式：

(p∨q)→r

(p→r)∧(q→r)

证可以从左边开始演算，也可以从右边开始演算。现在从右边开始演算。

所以，原等值式成立。读者亦可从左边开始演算验证之。

例2.3说明，用等值演算法可以验证两个公式等值。但一般状况下，不能用等值演算法直接验证两个公式不等值。

例2.4证明：(p→q)→r

p→(q→r)

证方法一：真值表法。读者自己证明

方法二：观测法。易知，010是(p→q)→r的成假赋值，而010是p→(q→r)的成真赋值，所以原不等值式成立。

方法三：设A=(p→q)→r,B=p→(q→r)

先将A,B通过等值演算化成简单观测真值的状况，再进行判断。

A=(p→q)→r(┐p∨q)→r（蕴涵等值式）┐(┐p∨q)∨r（蕴涵等值式）(p∧┐q)∨r（德摩根律）

B=p→(q→r)┐p∨(┐q∨r)（蕴涵等值式）┐p∨┐q∨r（结合律）

简单观测到，000，010是A的成假赋值，而它们是B的成真赋值。

等值演算还能帮助人们解决工作和生活中的判断问题。

例2.5用等值演算判断以下公式的类型：

（1）(p→q)∧p→q

（2）(p→(p∨q))∧r

（3）p∧(((p∨q)∧┐p)→q)

解在以下的演算中没有写出所用的基本等值式，请读者自己填上。

（1）(p→q)∧p→q(┐p∨q)∧p→q┐((┐p∨q)∧p)∨q(┐(┐p∨q)∨┐p)∨q((p∧┐q)∨┐p)∨q((p∨┐p)∧(┐q∨┐p))∨q(1∧(┐q∨┐p))∨q(┐q∨q)∨┐p1∨┐p1

最终结果说明（1）中公式是重言式。（2）┐(p→(p∨q))∧r┐(┐p∨p∨q)∧r(p∧┐p∧┐q)∧r0∧r0

最终结果说明（2）中公式是矛盾式。（3）p∧(((p∨q)∧┐p)→q)p∧(┐((p∨q)∧┐p)∨q)p∧(┐((p∧┐p)∨(q∧┐q))∨q)p∧(┐(0∨(q∧┐p))∨q)p∧(┐q∨p∨q)p∧1

p

最终结果说明（3）中公式不是重言式，00，01都是成假赋值。并且也不是矛盾式，由于10，11都是成真赋值。

等值演算中各步得出的等值式所含命题变项可能不一样多，如（3）中最终一步不含q，此时将q看成它的哑元，考虑赋值时将哑元也算在内，因而赋值的长度为2，这样，可将（3）中各步的公式都看成含命题变项p,q的公式，在写真值表时已经探讨过类似的问题的。

从例2.5可知，用等值演算判断公式的类型式是不太便利的，特别是判断非重言式的可满足式就更不便利了。在下节中将给出更简单的方法。

例2.6在某次研讨会的中间休息时间，3名与会者根据王教授的腔调对他是哪个省市

的人进行了判断：

甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。

丙说王教授既不是上海人，也不是杭州人。

听完以上3人的判断后，王教授笑着说，他们3人中有一人说的全对，有一人说对了一半，另一人说的全不对。试用规律演算法分析王教授终究是哪里人？解设命题

p：王教授是苏州人。q：王教授是上海人。r：王教授是杭州人。

p,q,r中必有一个真命题，两个假命题，要通过规律演算将真命题找出来。设

甲的判断为A1=┐p∧q乙的判断为A2=p∧┐q丙的判断为A3=┐q∧┐r则

甲的判断全对B1=A1=┐p∧q

甲的判断对一半B2=((┐p∧┐q)∨(p∧q))甲的判断全错B3=p∧┐q乙的判断全对C1=A2=p∧┐q

乙的判断对一半C2=((p∧q)∨(┐p∧┐q))乙的判断全错C3=┐p∧q

丙的判断全对D1=A3=┐q∧┐r

丙的判断对一半D2=(q∧┐r)∨(┐q∧r))丙甲的判断全错D3=q∧r由王教授所说

E=(B1∧C2∧D3)∨(B1∧C3∧D2)∨(B2∧C1∧D3)∨(B2∧C3∧D1)∨(B2∨C1∧D2)∨(B3∧C2∧D1)

为真命题。而

B1∧C2∧D3=(┐p∧q)∧((┐p∧┐q)∨(p∧q))∧(q∧r)(┐p∧q∧┐q∧r)∨(┐p∧q∧p∧r)0

B1∧C3∧D2=(┐p∧q)∧(┐p∧q)∧((q∧┐r)∨(┐q∧r))(┐p∧q∨r)∨(┐p∧q∧┐q∧r)┐p∧q∧┐r

B2∧C1∧D3=((┐p∧q)∨(p∧q))∧(p∧┐q)∧(q∧r)(┐p∧q∧p∧┐q∧q∧r)∨(p∧q∧┐q∧r)0

类似可得