离散数学 - 命题逻辑

---

---

数学逻辑的规则规定了推理数学陈述的方法。希腊哲学家亚里士多德是逻辑推理的先驱。逻辑推理为许多数学领域以及计算机科学提供了理论基础。它在计算机科学中有很多实际应用，例如计算机器的设计、人工智能、编程语言的数据结构的定义等。

命题逻辑关注的是可以分配真值“真”和“假”的陈述。目的是分析这些陈述，无论是单独还是组合的方式。

命题逻辑 - 定义

命题是具有真值“真”或真值“假”的声明性语句的集合。命题由命题变量和连接词组成。我们用大写字母（A、B 等）表示命题变量。连接词连接命题变量。

下面给出了一些命题的例子：

• "人是凡人"，它返回真值“真”
• "12 + 9 = 3 – 2"，它返回真值“假”

以下不是命题：

• "A 小于 2"。这是因为除非我们给 A 一个特定的值，否则我们无法说该语句是真还是假。

连接词

在命题逻辑中，我们通常使用五个连接词，它们是：

• 或 ($\lor$)

• 与 ($\land$)

• 非/否定 ($\lnot$)

• 蕴涵/如果-那么 ($\rightarrow$)

• 当且仅当 ($\Leftrightarrow$).

或 ($\lor$) - 两个命题 A 和 B 的或运算（写成 $A \lor B$）如果命题变量 A 或 B 中至少有一个为真，则为真。

真值表如下：

与 ($\land$) - 两个命题 A 和 B 的与运算（写成 $A \land B$）如果命题变量 A 和 B 都为真，则为真。

真值表如下：

否定 ($\lnot$) - 命题 A 的否定（写成 $\lnot A$）当 A 为真时为假，当 A 为假时为真。

真值表如下：

蕴涵/如果-那么 ($\rightarrow$) - 蕴涵 $A \rightarrow B$ 是命题“如果 A，那么 B”。如果 A 为真而 B 为假，则它为假。其余情况为真。

真值表如下：

当且仅当 ($ \Leftrightarrow $) - $A \Leftrightarrow B$ 是双条件逻辑连接词，当 p 和 q 相同时为真，即两者都为假或两者都为真。

真值表如下：

重言式

重言式是对于其命题变量的每个值始终为真的公式。

示例 - 证明 $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ 是重言式

真值表如下：

我们可以看到 $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ 的每个值都是“真”，所以它是重言式。

矛盾

矛盾是对于其命题变量的每个值始终为假的公式。

示例 - 证明 $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ 是矛盾

真值表如下：

我们可以看到 $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ 的每个值都是“假”，所以它是矛盾。

或然

或然是对于其命题变量的每个值都有一些真值和一些假值的公式。

示例 - 证明 $(A \lor B) \land (\lnot A)$ 是或然

真值表如下：

我们可以看到 $(A \lor B) \land (\lnot A)$ 的每个值都既有“真”又有“假”，所以它是或然。

命题等价

如果满足以下两个条件中的任何一个，则两个语句 X 和 Y 在逻辑上是等价的：

• 每个语句的真值表具有相同的真值。

• 双条件语句 $X \Leftrightarrow Y$ 是重言式。

示例 - 证明 $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ 是等价的

使用第一种方法（匹配真值表）进行测试

在这里，我们可以看到 $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ 的真值相同，因此这些语句是等价的。

使用第二种方法（双条件）进行测试

由于 $\lbrack \lnot (A \lor B) \rbrack \Leftrightarrow \lbrack (\lnot A ) \land (\lnot B) \rbrack$ 是重言式，因此这些语句是等价的。

逆命题、否命题和逆否命题

蕴涵/如果-那么 $(\rightarrow)$ 也称为条件语句。它有两个部分：

• 假设，p
• 结论，q

如前所述，它表示为 $p \rightarrow q$。

条件语句示例 - “如果你做作业，你就不会受到惩罚。” 这里，“你做作业”是假设 p，“你不会受到惩罚”是结论 q。

逆命题 - 条件语句的逆命题是对假设和结论的否定。如果语句是“如果 p，那么 q”，则逆命题将是“如果非 p，那么非 q”。因此，$p \rightarrow q$ 的逆命题是 $ \lnot p \rightarrow \lnot q$。

示例 - “如果你做作业，你就不会受到惩罚”的逆命题是“如果你不做作业，你就会受到惩罚”。

否命题 - 条件语句的否命题是通过交换假设和结论来计算的。如果语句是“如果 p，那么 q”，则否命题将是“如果 q，那么 p”。$p \rightarrow q$ 的否命题是 $q \rightarrow p$。

示例 - “如果你做作业，你就不会受到惩罚”的否命题是“如果你不会受到惩罚，你就会做作业”。

逆否命题 - 条件语句的逆否命题是通过交换逆命题的假设和结论来计算的。如果语句是“如果 p，那么 q”，则逆否命题将是“如果非 q，那么非 p”。$p \rightarrow q$ 的逆否命题是 $\lnot q \rightarrow \lnot p$。

示例 - “如果你做作业，你就不会受到惩罚”的逆否命题是“如果你受到惩罚，你就没有做作业”。

对偶原理

对偶原理指出，对于任何真语句，通过将并集改为交集（反之亦然）并将全集改为空集（反之亦然）获得的对偶语句也为真。如果任何语句的对偶是语句本身，则称之为自对偶语句。

示例 - $(A \cap B ) \cup C$ 的对偶是 $(A \cup B) \cap C$

范式

我们可以将任何命题转换为两种范式：

• 合取范式
• 析取范式

合取范式

如果一个复合语句是通过对用或连接的变量（包括变量的否定）进行与运算而得到的，则该复合语句处于合取范式。就集合运算而言，它是通过对用并集连接的变量进行交集而得到的复合语句。

示例

• $(A \lor B) \land (A \lor C) \land (B \lor C \lor D)$

• $(P \cup Q) \cap (Q \cup R)$

析取范式

如果一个复合语句是通过对用与连接的变量（包括变量的否定）进行或运算而得到的，则该复合语句处于析取范式。就集合运算而言，它是通过对用交集连接的变量进行并集而得到的复合语句。

示例

• $(A \land B) \lor (A \land C) \lor (B \land C \land D)$

• $(P \cap Q) \cup (Q \cap R)$