离散数学中的公式等价性

假设有两个公式X和Y。当X ↔ Y是重言式时，这两个公式称为等价。如果两个公式X ↔ Y是重言式，那么我们也可以写成X ⇔ Y，并且我们可以将这种关系读作X等价于Y。

注意：在公式的线性等价性方面，有一些需要注意的点，如下所述

• ⇔仅用于指示符号，它不是连接词。
• 如果X ↔ Y是重言式，那么X和Y的真值将始终相等。
• 等价关系包含两个性质，即对称性和传递性。

方法1：真值表法

在此方法中，我们将构建任意两个语句公式的真值表，然后检查这些语句是否等价。

示例1：在此示例中，我们需要证明X ∨ Y ⇔ ¬(¬X ∧ ¬Y)。

解决方案：X ∨ Y ⇔ ¬(¬X ∧ ¬Y)的真值表如下所示

正如我们所看到的，X ∨ Y和¬(¬X ∧ ¬Y)是重言式。因此X ∨ Y ⇔ ¬(¬X ∧ ¬Y)。

示例2：在此示例中，我们需要证明(X → Y) ⇔ (¬X ∨ Y)。

解决方案：(X → Y) ⇔ (¬X ∨ Y)的真值表如下所示

正如我们所看到的，X → Y和(¬X ∨ Y)是重言式。因此(X → Y) ⇔ (¬X ∨ Y)。

等价公式

有各种定律用于证明等价公式，如下所述

幂等律：如果只有一个语句公式，那么它将满足以下属性

结合律：如果有三个语句公式，那么它将满足以下属性

交换律：如果有两个语句公式，那么它将满足以下属性

分配律：如果有三个语句公式，那么它将满足以下属性

同一律：如果只有一个语句公式，那么它将满足以下属性

补律：如果只有一个语句公式，那么它将满足以下属性

吸收律：如果有两个语句公式，那么它将满足以下属性

德摩根定律：如果有两个语句公式，那么它将满足以下属性

方法2：替换过程

在此方法中，我们将假设一个公式A：X → (Y → Z)。公式Y → Z可以称为公式的一部分。如果我们用等价公式¬Y ∨ Z替换此公式的一部分，即Y → Z，那么我们将得到另一个公式，即B：X → (¬Y ∨ Z)。这是一个简单的过程，可以验证给定的公式A和B是否相互等价。借助替换过程，我们可以从A得到B。

示例1：在此示例中，我们需要证明{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z。

解决方案：在这里，我们将采取左侧部分，并尝试得到右侧部分。

现在我们将像这样使用结合律

现在我们将像这样使用德摩根定律

得证

示例2：在此示例中，我们需要证明{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y。

解决方案：在这里，我们将采取左侧部分，并尝试得到右侧部分。

得证

{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y

示例3：在此示例中，我们需要证明X → (Y → X) ⇔ ¬X → (X → Y)。

解决方案：在这里，我们将采取左侧部分，并尝试得到右侧部分。

得证

示例4：在此示例中，我们需要证明(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z。

解决方案：在这里，我们将采取左侧部分，并尝试得到右侧部分。

现在我们将像这样使用结合律和分配律

现在我们将像这样使用德摩根定律

现在我们将像这样使用分配律

得证

示例5：在此示例中，我们需要证明((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z)是重言式。

解决方案：在这里，我们将采取小部分并解决它们。

首先，我们将使用德摩根定律并得到以下结果

因此，

此外

因此

因此：

因此，我们可以说给定的公式是重言式。

示例6：在此示例中，我们需要证明(X ∧ Y) → (X ∨ Y)是重言式。

解决方案：(X ∧ Y) → (X ∨ Y)

现在我们将像这样使用德摩根定律

现在我们将像这样使用结合律和交换律

现在我们将像这样使用否定律

因此，我们可以说给定的公式是重言式。

示例7：在此示例中，我们需要写出一些陈述的否定，如下所述

1. 玛丽将完成她的学业，或接受XYZ公司的录用通知。
2. 哈利明天将去兜风或跑步。
3. 如果我取得好成绩，我的表哥就会嫉妒。

解决方案：首先，我们将像这样解决第一个陈述

1.假设X：玛丽将完成她的学业。

Y：接受XYZ公司的录用通知。

我们可以使用以下符号形式来表达这个陈述

X ∨ Y的否定如下所示

总之，给定陈述的否定将是

2.假设X：哈利将去兜风

Y：哈利明天将跑步

我们可以使用以下符号形式来表达这个陈述

X ∨ Y的否定如下所示

总之，给定陈述的否定将是

3.假设X：如果我取得好成绩。

Y：我的表哥就会嫉妒。

我们可以使用以下符号形式来表达这个陈述

X → Y的否定如下所示

总之，给定陈述的否定将是

示例8：在此示例中，我们需要借助德摩根定律写出一些陈述的否定。这些陈述如下所述

1. 我需要一套钻石首饰，值一对金戒指。
2. 你找到一份好工作，或者你找不到一个好伴侣。
3. 我工作量很大，我无法应付。
4. 我的狗去旅行，或者它会在屋子里弄得一团糟。

解决方案：借助德摩根定律，所有陈述的否定都将逐一描述如下

1. 我不想要一套钻石首饰，也不值得一对金戒指。
2. 你找不到一份好工作，你也会找不到一个好伴侣。
3. 我没有大量工作，我能应付。
4. 我的狗不去旅行，它也不会在屋子里弄得一团糟。

示例9：在此示例中，我们有一些陈述，我们需要写出这些陈述的否定。这些陈述如下所述

1. 如果下雨，那么去海滩的计划将被取消。
2. 如果我努力学习，我将在考试中取得好成绩。
3. 如果我参加深夜派对，我将受到父亲的惩罚。
4. 如果你不想和我说话，那么你必须拉黑我的号码。

解决方案：所有陈述的否定都将逐一描述如下

1. 如果去海滩的计划被取消，那么就会下雨。
2. 如果我在考试中取得好成绩，那么我就努力学习。
3. 如果我受到父亲的惩罚，那么我就去参加深夜派对。
4. 如果你必须拉黑我的号码，那么你就不想和我说话。

示例10：在此示例中，我们需要检查(X → Y) → Z和X → (Y → Z)是否逻辑等价。我们需要借助真值表和逻辑规则来简化这两个表达式，以证明我们的答案。

解决方案：首先，我们将使用方法1来检查(X → Y) → Z和X → (Y → Z)是否逻辑等价，如下所示

方法1：在这里，我们将假设以下

和

方法2：现在，我们将使用第二种方法。在此方法中，我们将使用真值表。

在此真值表中，我们可以看到(X → Y) → Z和X → (Y → Z)的列不包含相同的值。