离散数学中的原子命题

原子命题是一种陈述，它包含一个可以为真或为假的值。例如：

这个例子中有三个句子是命题。其中第一个句子是假或无效的，而最后两个句子是真或有效的。

现在我们解释一些不是命题的句子，这意味着它们有多个真值或没有真值。

例如

这个例子中有三个句子不是命题，因为第一个句子可能是假或真，因为“a”的值没有指定，所以我们无法确定它是真还是假，除非我们指定值，而后两个句子没有真值。

我们可以通过在句子前面加上以下内容来轻松确定任何给定句子是否为命题：

添加此内容后，我们将检查该句子是否符合语法。现在我们将使用命题变量来避免写出完整的命题。命题变量可以用小写字母表示，例如 x、y、z 等。如果我们定义一个命题变量而不是一个完整的句子，我们必须这样定义：

还有另一种选择。我们可以写一个类似 wing_flaps_are_up 的句子，这样命题变量的含义就显而易见了。

连接词

现在我们将解释连接词，它将帮助我们创建复杂的命题。各种连接词如下所示：

1. 与 (∧)
2. 或 (∨)
3. 否定/非 (¬)
4. 蕴涵 / 如果-则 (⊃ 或 →)
5. 当且仅当 (⇔)

与 (∧)

如果我们用“and”这个词组合两个命题并形成第三个命题，它将被称为原始命题的合取/与。假设 X 和 Y 是两个原子命题变量。当 X 和 Y 都为真时，这些变量的命题为真。X 和 Y 的合取如下所示：

带有AND (∧)连接的运算可以用真值表总结。真值表的思想表明，公式的行为可以在公式中包含的原始命题的所有可能解释下进行描述。

假设一个公式包含 n 个不同的原子命题。在这种情况下，真值表将包含该公式的 2ⁿ 行。原因是每个命题只能在两个值中取一个值。它们可以是真或假。

我们将用 F 表示假，T 表示真。现在 X ∧ Y 的真值表如下所示：

示例

我们将假设命题 X =“今天是个晴天”和 Y =“今天是星期四”。X ∧ Y 是“今天是个晴天，而且今天是星期四”。这个命题仅在晴朗的星期四为真，而在任何其他晴天或不是星期四的晴天时为假。

或 (∨)

如果我们用“or”这个词组合两个命题并形成第三个命题，它将被称为原始命题的析取。假设 X 和 Y 是两个原子命题变量。当 X 和 Y 都为真，或者 X 为真，或者 Y 为真时，这些变量的命题为真。X 和 Y 的析取如下所示：

X ? Y 的真值表如下所示：

示例

我们将假设命题 X =“今天是个晴天”和 Y =“今天是星期四”。X ∨ Y 是“今天是个晴天，或者是星期四”。这个命题在晴天或任何星期四为真，在不是晴天且不是星期四时为假。

蕴涵或如果-则 (→)

在数学中，许多句子包含以下形式：

我们可以用另一种方式说：

命题逻辑中有一个连接词，即 if-then。此连接词的目的是将两个命题组合成一个新的命题，称为蕴涵或原始命题的条件，用于捕捉此类陈述的含义。

假设 X 和 Y 是两个原子命题变量。当 X 为真且 Y 为假时，除了这种情况之外，这些变量的命题在所有情况下都为真。X 和 Y 的蕴涵如下所示：

X → Y 的真值表如下所示：

if-then 运算符 (→) 非常重要，也最难理解。因此，我们可以这样理解 X → Y：如果 X 为假，则无论 Y 的值如何，X → Y 都为真。

示例

我们将假设命题 X =“今天是个晴天”和 Y =“今天是星期四”。X → Y 是“如果今天是晴天，那么今天是星期四”。当不是晴天，或者今天是晴天且是星期四时，这个命题为真；当今天是晴天但不是星期四时，这个命题为假。

当且仅当 (⇔)

这里，X ⇔ Y 被称为双条件逻辑连接词。在数学中，还有一种陈述形式说：

我们可以通过使用双条件运算符 (⇔) 来理解上述陈述的含义。假设 X 和 Y 是两个原子命题变量。当 X 和 Y 都相同时，这些变量的双条件为真。这意味着 X 和 Y 都为假，或者 X 和 Y 都为真。X 和 Y 的双条件如下所示：

X ⇔ Y 的真值表如下所示：

如果 X ⇔ Y 为真，则 X 和 Y 被称为逻辑等价。

示例

我们将假设命题 X =“今天是个晴天”和 Y =“今天是星期四”。X ⇔ Y 是“如果今天是个晴天，当且仅当今天是星期四”。当不是晴天，或者不是星期四时，这个命题为假；如果不是晴天且不是星期四，或者如果今天是晴天且是星期四，则为真。

非 (¬)

前面考虑的所有四个连接词都是二元的，因为这四个连接词都接受两个参数。现在我们将考虑最后一个连接词“not”，它是一元的，因为它只接受一个参数。

我们可以用“not”这个词放在任何命题前面，形成第二个命题，它被称为原始命题的否定。假设 X 是一个原子命题。当 X 为假时，这个变量的命题为真。X 的否定如下所示：

¬X 的真值表如下所示：

示例

我们将假设命题 X =“今天是星期四”。X 的否定将是“今天不是星期四”。

重言式、一致式和不一致式

如果我们有一个公式，在不使用真值表的情况下，我们无法确定它是真还是假。我们通常需要分量原子命题的真值来确定给定的公式是否为真。

估值

赋值是用于提供每个原始命题真值的函数类型。使用赋值，可以确定任何公式的真假。

例如：假设有一个赋值 v，使得

现在我们将像这样计算 (x ∨ y) → z 的真值：

通过或 (∨) 连接的真值表，我们知道 F ∨ T = T。这就是第三行成立的原因。通过蕴涵 (→) 的真值表，我们知道 T → F = F。

重言式

如果一个公式在每次赋值下都为真，则称该公式为重言式。

例如：我们必须证明 [(X → Y) ∧ X] → Y 是一个重言式。该公式的真值表如下所示：

使用上面的真值表，我们证明了 [(X → Y) ∧ X] → Y 为真。这就是为什么它是重言式。

一致式或偶发式

如果一个公式在至少一次赋值下为真，则称该公式为一致式。

例如：我们必须证明 (X ∨ Y) ∧ (¬X) 是一致的。该公式的真值表如下所示：

使用上面的真值表，我们证明了 (X ∨ Y) ∧ (¬X) 既有真也有假。这就是为什么它是一致的。

不一致式或矛盾式

如果一个公式在每次赋值下都为假，则称该公式为不一致式。

例如：我们必须证明 (X ∨ Y) ∧ [(¬X) ∧ (¬Y)] 是一致的。该公式的真值表如下所示：

使用上面的真值表，我们证明了 (X ∨ Y) ∧ [(¬X) ∧ (¬Y)] 为假。这就是为什么它是不一致的。

命题等价

假设我们有两个陈述 X 和 Y。如果它们满足以下任一条件，则它们在逻辑上是等价的：

• 在第一个条件中，每个陈述的真值表具有相同的真值。
• 在第二个条件中，双条件陈述 X⇔Y 将是重言式。

例如：我们必须证明 ¬(X ∨ Y) 和 [(¬X) ∧ (¬Y)] 是等价的。使用第一种方法，上述陈述的真值表如下所示：

在上面的真值表中，我们可以看到 ¬(X ∨ Y) 和 [(¬X) ∧ (¬Y)] 这两个陈述是相同的。所以我们可以说这两个陈述是等价的。

现在我们将使用第二种方法——双条件——来测试这两个陈述。

在上面的真值表中，我们可以看到 [¬(X ∨ Y)] ⇔ [(¬X) ∧ (¬Y)] 是一个重言式，因为它对于其命题变量的每个值都为真。所以我们可以说这两个陈述是等价的。