离散数学-命题逻辑

---

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

命题逻辑涉及可以分配真值“真”和“假”的陈述。目的是单独或以综合方式分析这些陈述。

介词逻辑 – 定义

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

下面给出了一些命题示例 -

• “Man is Mortal”，它返回真值“TRUE”
• “12 + 9 = 3 – 2”，返回真值“FALSE”

以下不是提案 -

• “A小于2”。这是因为除非我们给出 A 的具体值，否则我们无法判断该陈述是真还是假。

连接词

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

• 或 ($\lor$)

• 和（$\土地$）

• 否定/非 ($\lnot$)

• 蕴涵 / if-then ($\rightarrow$)

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

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

真值表如下 -

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

真值表如下 -

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

真值表如下 -

蕴涵 / if-then ($\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$ 的每个值都是“True”，这是一个同义反复。

矛盾之处

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

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

真值表如下 -

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

意外事件

偶然性是一个公式，它的命题变量的每个值都有一些真值和一些假值。

示例- 证明 $(A \lor B) \land (\lnot A)$ 是一个意外事件

真值表如下 -

我们可以看到 $(A \lor B) \land (\lnot A)$ 的每个值都有“True”和“False”，这是一个偶然性。

命题等价

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

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

• 双条件语句 $X \Leftrightarrow Y$ 是同义反复。

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

^{通过第一种}方法测试（匹配真值表）

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

通过第二种^方法测试（双条件）

由于 $\lbrack \lnot (A \lor B) \rbrack \Leftrightarrow \lbrack (\lnot A ) \land (\lnot B) \rbrack$ 是同义反复，因此语句是等效的。

逆、逆、反正

蕴涵 / if-then $(\rightarrow)$ 也称为条件语句。它有两个部分 -

• 假设，p
• 结论，q

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

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

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

示例- “如果你做作业，你不会受到惩罚”的反义词是“如果你不做作业，你就会受到惩罚”。

Converse - 条件语句的逆是通过交换假设和结论来计算的。如果语句是“If p, then q”，则相反的语句是“If q, then 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$

范式

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

• 连词范式
• 析取范式

连接范式

如果复合语句是通过用 OR 连接的变量（包括变量的否定）进行 AND 运算而得到的，则该复合语句是合取范式。从集合运算的角度来看，它是通过并联连接的变量之间进行交集得到的复合语句。

例子

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

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

析取范式

如果复合语句是通过与连接的变量（包括变量的否定）之间的或操作而获得的，则该复合语句是析取范式。从集合运算的角度来看，它是通过交集连接的变量之间通过Union得到的复合语句。

例子

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

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