1.3 命题演算的关系式

1.3.1 等价关系式

定义1.3.1 设A和B是两个命题（或命题公式），若A↔B是永真式，则称命题A和B逻辑等价，可记为A⇔B。

A↔B是永真式表示命题公式A和B在所有的赋值下都有相同的真值，也就是说命题公式A和B有相同的真值表。因此，可以用真值表判定两个命题是否等价。命题A和B等价当且仅当真值表中给出它们真值的两列完全相同。

例1.3.1 证明p→q和等价。

证明 表1.3.1是公式p→q和的真值表。

对于p和q的所有赋值，p→q和的真值都一样。见表1.3.1。

所以这两个公式等价，即。

◀

例1.3.2 证明p∧（q∨r）和（p∧q）∨（p∧r）逻辑等价。

证明 表1.3.2是公式p∧（q∨r）和（p∧q）∨（p∧r）的真值表。

可以看出公式p∧（q∨r）和（p∧q）∨（p∧r）有相同的真值表，所以它们是等价的。

◀

下面列出了一些重要的等价关系，它们都可以通过构造真值表来证明。在这些等价关系中，1表示真值为真的任意命题常量，0表示真值为假的任意命题常量。

德·摩根律的两个逻辑等价公式很重要，它给出了否定合取和析取的方法。等价式说明命题变元的合取的否定等价于命题变元的否定的析取。同理，等价式说明命题变元的析取的否定等价于命题变元的否定的合取。德·摩根律还可以扩展到多个变元，有如下表达式

或

上式可以用数学归纳法进行证明。

利用上面的等价关系式和置换规则，可以进行命题公式的等价运算、命题公式的化简及推理问题的证明等。

置换规则 若公式G中的一部分A（包含G中几个连续的符号）是公式，则称A为G的子公式；用与A逻辑等价的公式B置换A不改变公式G的真值。

利用已知的等价关系式，将其中的子公式用和它等价的公式置换可以推出其他一些等价关系式，这一过程称为命题的等价运算。利用命题的等价运算，可以判断两个命题是否等价，判断命题公式的类型及进行命题公式的化简等。

例1.3.3 证明p→（q→r）⇔（p∧q）→r。

证明

例1.3.4 利用命题的等价运算判断下列公式的类型。

1）

2）p∧（p→q）

3）

解

因此，1）为永假式，2）为可满足式，3）为永真式。

◀

例1.3.5 化简公式

解

例1.3.5是利用等价关系式对命题公式进行化简的示例，利用等价关系式还可以求逻辑电路的输出及对逻辑电路进行化简。

例1.3.6 对于图1.3.1所示的逻辑电路，可否用更简单的电路实现该逻辑关系？

解 首先写出图1.3.1所示逻辑电路的逻辑表达式，化简这个公式

因此，这个电路的输出是，可以用更简单的电路实现上面电路的逻辑功能，见图1.3.2。