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。

1.3.2 全功能联结词集

蕴涵等价式 说明条件联结词→可以用 和∨表示。1.1节除了介绍5个主要联结词，还介绍了↑、↓和⊕三个联结词。按照定义有

由此可见，↑、↓和⊕三个联结词可以用联结词 、∧和∨表示。

定义1.3.2 设 G 是一个联结词的集合，若任意一个命题都可用 G 中的联结词构成的命题公式来表示，则称 G 为 全功能联结词集 。如在 G 中去掉任何一个联结词，就不再具有这种特性，则称其为 最小全功能联结词集 。

可以证明， 、{↑}和{↓}都是全功能联结词集，而 、{↑}和{↓}都是最小全功能联结词集。

例1.3.7 证明：{↑}和{↓}是最小全功能联结词集。

证明

故{↑}和{↓}是最小全功能联结词集。

◀

上述等价关系式表明，只用一个↑或↓就可以实现联结词 、∧、∨、→、↔表示的逻辑关系。在数字电子技术中，可以用与非门实现↑的逻辑关系，用或非门实现↓的逻辑关系。因此，只用与非门或或非门组成的电路就可以实现任何逻辑运算。与非门和或非门的电路符号如图1.3.3所示。

例1.3.8 用只有一种与非门的逻辑电路实现图1.3.1的逻辑电路的逻辑关系。

解 图1.3.1所示逻辑电路的逻辑表达式为 。化简这个公式为只含有与非联结词的逻辑表达式

因此实现该逻辑关系的逻辑电路如图1.3.4所示。

1.3.3 对偶式

在1.3.1节所列的等价关系式中，公式2）～9）都是由两个公式组成的，这些成对出现的公式称为对偶式。对偶式的定义如下。

定义1.3.3 在仅含有联结词 、∧、∨的公式 A 中，将其中的∧换成∨、∨换成∧、1（或T）换成0（或F）、0（或F）换成1（或T），其他符号不变，得到的公式称为 A 的 对偶式 ，记为 A ^* 。

由定义可以看出， A ^* 的对偶式就是 A ，也就是对偶式是相互的。

例如， p ∨ q 和 p ∧ q 、 和 和 都互为对偶式。由于 ，而 和 互为对偶式，所以 p ↑ q 和 p ↓ q 也互为对偶式。

设 A （ p ₁ ， p ₂ ，…， p _n ）和 A ^* （ p ₁ ， p ₂ ，…， p _n ）互为对偶式，其中 p ₁ ， p ₂ ，…， p _n 是出现在 A 和 A ^* 中的全部的命题变元，则

例如，假设 A （ p ， q ）⇔ p ∧ q ，则

A ^* （ p ， q ）⇔ p ∨ q

而

所以

类似地，有

定理1.3.1 设 A 和 B 为两个命题公式， A 和 A ^* 、 B 和 B ^* 互为对偶式，若 A ⇔ B ，则 A ^* ⇔ B ^* 。

证明 因为

若

A （ p ₁ ， p ₂ ，…， p _n ）⇔ B （ p ₁ ， p ₂ ，…， p _n ）

则

即

则

A ^* （ p ₁ ， p ₂ ，…， p _n ）⇔ B ^* （ p ₁ ， p ₂ ，…， p _n ）

◀

例1.3.9 求公式 的对偶式。

解 公式 A 的对偶式 A ^* 为

公式 是重言式，而1的对偶式是0，所以，由对偶原理可以直接得知重言式 A 的对偶式 A ^* 是矛盾式。 7Gv8R1bJWym6a/0+OuIm1zeH6EctdGIikpy4yvpOgnTmCUNvux05vAipVWxtUVpd