离散数学中的推断理论

推理理论可以描述为从给定的一组前提分析公式的有效性。

论证的结构

论证可以定义为一系列语句。论证是前提和结论的集合。结论用于指示最后一句，前提用于指示所有剩余的语句。在结论之前，将放置符号 ∴。以下语法用于显示前提和结论

Premises: p1, p2, p3, p4, ….., pn
Conclusion: q

如果 (p₁∧ p₂ ∧ p₃ ∧ p₄ ∧ …… ∧ p_n) → q 表示一个拓扑，在这种情况下，该论证将被称为有效的，否则将被称为无效的。以下表达式用于显示论证

有效论证

有效论证可以描述为这样一种论证：如果其所有前提都为真，则其结论也为真。

例如

该论证属于以下形式

上述形式是有效的。无论变量被替换为何种命题，都不会改变这一点。这种形式称为有效论证形式。根据上述定义，如果一个有效论证形式包含

premises: p1, p2, p3, p4, ….., pn
conclusion: q

那么 (p₁ ∧ p₂ ∧ p₃ ∧ …. ∧ p_k) → q 是一个重言式。这意味着 ((p → q) ∧ p) → q 是一个重言式。

为了理解这个概念，我们需要了解量词，它们如下所述

量词

量词可以描述为用于确定给定谓词元素真值的语句集合。它还包含谓词，谓词可以描述为包含特定数量变量（项）的语句。量词基本有两种，如下所述

• 存在量词用符号 ∃ 表示。一般形式，它用单词“某些”、“存在”、“至少一个”来表示。
• 全称量词用符号 ∀ 表示。它用单词“所有”、“任何”、“一切”或“每个”来表示。

推理规则

我们可以借助简单的论证来构建更复杂的有效论证，这些简单的论证是基础。如果我们谈论论证的用法，那么有一些简单的论证已被确立为有效且非常重要。这些类型的论证称为推理规则。有各种类型的推理规则，如下所述

1. 肯定前件式 (Modus Ponens)

假设有两个前提 P 和 P → Q。现在，我们将使用肯定前件式推导出 Q，如下所示

示例

假设 P → Q =“如果我们有一个银行账户，我们就可以利用这项新政策。”

P =“我们有一个银行账户。”

因此，Q =“我们可以利用这项新政策。”

2. 否定后件式 (Modus Tollens)

假设有两个前提 P → Q 和 ¬Q。现在，我们将使用否定后件式推导出 ¬P，如下所示

示例

假设 P → Q =“如果我们有一个银行账户，我们就可以利用这项新政策。”

¬Q =“我们无法利用这项新政策。”

因此，¬P =“我们没有银行账户。”

3. 假言三段论 (Hypothetical Syllogism)

假设有两个前提 P → Q 和 Q → R。现在，我们将使用假言三段论推导出 P → R，如下所示

示例

假设 P → Q =“如果我的未婚夫来见我，我将不去办公室。”

Q → R =“如果我将不去办公室，我将不需要做办公室工作。”

因此，P → R =“如果我的未婚夫来见我，我将不需要做办公室工作。”

4. 析取三段论 (Disjunction Syllogism)

假设有两个前提 ¬P 和 P ∨ Q。现在，我们将使用析取三段论推导出 Q，如下所示

示例

假设 ¬P =“哈利的生日蛋糕不是草莓味的。”

P ∨ Q =“生日蛋糕要么是红丝绒味的，要么是什锦水果味的。”

因此，Q =“生日蛋糕是什锦水果味的。”

5. 附加式 (Addition)

假设有一个前提 P。现在，我们将使用附加式推导出 P ∨ Q，如下所示

示例

假设 P 是命题，“哈里是一个勤奋的员工”为真

这里 Q 是命题，“哈里是一个糟糕的员工”。

因此，“哈里要么是一个勤奋的员工，要么哈里是一个糟糕的员工”。

6. 简化式 (Simplification)

假设有一个前提 P ∧ Q。现在，我们将使用简化式推导出 P，如下所示

示例

假设 P ∧ Q =“哈里是一个勤奋的员工，他是办公室里最好的员工。”

因此，“哈里是一个勤奋的员工”。

7. 连词

假设有两个前提 P 和 Q。现在，我们将使用合取式推导出 P ∧ Q，如下所示

示例

假设 P =“哈里是一个勤奋的员工”。

假设 Q =“哈里是办公室里最好的员工”。

因此，“哈里是一个勤奋的员工，哈里是办公室里最好的员工”。

8. 合取规则 (Resolution)

假设有两个前提 P ∨ Q 和 ¬P ∨ R。现在，我们将使用合取规则推导出 Q ∨ R，如下所示

示例

假设 P → Q =“如果我的未婚夫来见我，我将不去办公室”。

¬ P ∨ R =“如果我的未婚夫没有来见我，我将不需要做办公室工作”。

因此，Q ∨ R =“要么我将不去办公室，要么我将不需要做办公室工作”。

9. 构造性二难 (Constructive Dilemma)

假设有两个前提 (P → Q) ∧ (R → S) 和 P ∨ R。现在，我们将使用构造性二难推导出 Q ∨ S，如下所示

示例

假设 P → Q =“如果我的未婚夫来见我，我将不去办公室”。

R → S =“如果我的亲戚来了，我会告诉我的员工我将来的”。

P ∨ R =“要么我的未婚夫会来见我，要么我的亲戚会来”。

因此，Q ∨ S =“要么我将不去办公室，要么我会告诉我的员工我将来的”。

10. 破坏性二难 (Destructive Dilemma)

假设有两个前提 (P → Q) ∧ (R → S) 和 ¬Q ∨ ¬S。现在，我们将使用破坏性二难推导出 ¬P ∨ ¬R，如下所示

示例

假设 P → Q =“如果我的未婚夫来见我，我将不去办公室”。

R → S =“如果我的亲戚来了，我会告诉我的员工我将来的”。

¬Q ∨ ¬S =“要么我会去办公室，要么我会告诉我的员工我不会来”。

因此，¬P ∨ ¬R =“要么我的未婚夫不会来见我，要么我的亲戚不会来”。

带量词的推理规则

还有一些带量词语句的推理规则，如下所述

1. 全称实例化 (Universal Instantiation)

假设有一个前提 ∀x P(x)。现在，我们将使用全称实例化推导出 P(c)，如下所示

2. 全称泛化 (Universal Generalization)

假设对于任意 c，有一个前提 P(c)。现在，我们将使用全称泛化推导出 ∀x P(x)，如下所示

3. 存在实例化 (Existential Instantiation)

假设有一个前提 ∃x P(x)。现在，我们将使用存在实例化推导出某个元素 c 的 P(c)，如下所示

4. 存在泛化 (Existential Generalization)

假设对于某个元素 c，有一个前提 P(c)。现在，我们将使用存在泛化推导出 ∃x P(x)，如下所示

推理规则示例

示例 1

如果我的未婚夫来见我，我就会开心。

如果我的未婚夫不来见我，我就去办公室。

如果我去办公室，我就完成我的工作。

我们能得出结论，“如果我不开心，我就完成我的工作”吗？

解决方案：我们将通过识别命题并使用命题变量来表示它们来简化讨论，如下所示

P := 我的未婚夫来见我

Q := 我会开心

R := 我将去办公室

S := 我将完成我的工作

输入以上命题变量后，我们将得到以下前提和结论，如下所示

现在我们将使用推理规则，以便能够借助给定的假设推导出结论，如下所示

示例 2

我的办公室里的一名员工没有完成他每天的工作

我的办公室里的每个人都完成了他的月度文件。

我们能得出结论，“完成月度文件的人没有完成他每天的工作”吗？

解决方案：我们将通过识别命题并使用命题变量来表示它们来简化讨论，如下所示

C(x) := x 是我办公室的一名员工

B(x) := x 已完成他每天的工作

P(x) := x 完成了他的月度文件

输入以上命题变量后，我们将得到以下前提和结论，如下所示

现在我们将使用量词的推理规则，以便能够借助给定的假设推导出结论，如下所示