离散数学第二章

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.2 3个公式的真值表

三、等值演算

虽然用真值法可以判断任何两个命题公式是否等值，但当命题变项较多时，工作量是很大的。可以先用真值表验证一组基本的又是重要的重言式，以它们为基础进行公式之间的演算，来判断公式之间的是否等值。本书给出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)∨┐p 1∨┐p 1

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

最后结果说明（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

类似可得

B2∧C3∧D10 B3∧C1∧D2p∧┐q∧r B3∧C2∧D10

于是，有同一律可知

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

但因为王教授不能既是上海人，又是杭州人，因而p,r必有一个假命题，即p∧┐q∧r0，于是

E┐p∧q∧┐r

为真命题，因而必有p,r为假命题，q为真命题，即王教授是上海人。甲说的全对，丙说对了一半，而乙全说错了。

读者应可以模仿该例判断引言中问题的正确性。

本文来源：https://www.bwwdw.com/article/vh3p.html