2025 福州大学离散数学笔记

数理逻辑

命题

非真即假的封闭陈述句就是命题 (proposition)。一个命题的真值 (truth value) 表示命题的真假情况，本课程定义 1 为真，0 为假。

一个无法被分解的命题称为简单命题或原子命题 (atomic proposition)，简单命题通过联结词 (logical connectives) 联结得到复合命题 (compound propositions)

我们习惯上用字母 $p$, $q$, $r$, $s$, … 来表示命题变量 (propositional variables)，即表示命题的变量。

我们有 5 个联结词：

否定 (Negation)

令 $p$ 为一命题，则 $p$ 的否定记作 $\neg p$ ，指 “不是 $p$ 所指的情形”，$p$ 的否定与 $p$ 的真值相反。(NOT)

否定运算符的记号并没有统一的标准，只是 " $\neg$ " 比较常用而已

命题的否定也可以看作否定运算符 (negation operator) 作用在命题上的结果。

合取 (Conjunction)

令 $p$, $q$ 为命题，$p$, $q$ 的合取即命题 “$p$ 并且 $q$”，记作 “$p\land q$”，当 $p$, $q$ 皆为真命题时，$p\land q$ 为真，否则为假。(AND)

如果一个命题为假，那么整个合取式固定为假；如果一个命题为真，那么整个合取式的真值取决于另一个命题。

析取 (Disjunction)

令 $p$, $q$ 为命题，$p$, $q$ 的析取即命题 “$p$ 或 $q$”，记作 “$p\lor q$”，当 $p$, $q$ 皆为假命题时，$p \lor q$ 为假, 否则为真。(OR)

如果一个命题为真，那么整个析取式固定为真；如果一个命题为假，那么整个析取式的真值取决于另一个命题。

异或 (Exclusive or)

令 $p$, $q$ 为命题，$p$, $q$ 的异或（记作 $p\oplus q$）是这样的一个命题：当 $p$, $q$ 中恰好有一个为真时命题为真，否则为假。

换句话说，命题 $p$, $q$ 的真值相同则为假 (0) ，真值不同则为真 (1)。

联想到异或运算，其实是同一个概念，二进制位相同则为 0，二进制位不同则为 1。

和析取相比，异或排除了 $p$、$q$ 同时成立的情况，因此也称 “排斥或”。与之相对的，“析取” 也称 “相容或”

蕴涵 (Implication)

或称条件语句 (Conditional Statement)。

令 $p$, $q$ 为命题，蕴含 $p\rightarrow q$ 是命题 “如果 $p$，则 $q$”，当 $p$ 为真而 $q$ 为假时，条件语句 $p\rightarrow q$ 为假，否则为真。在蕴涵中，$p$ 称为假设（hypothesis，或前件 antecedent，前提 premise），$q$ 称为结论（conclusion，或后件 consequence）。

蕴含式中 $p$ 和 $q$ 的顺序很重要。如果交换 $p$ 和 $q$，会产生一个不同的命题。

常用的自然语言描述：

• 只要 $p$，就 $q$
• 因为 $p$，才 $q$
• $p$ 仅当 $q$
• 只有 $q$ 才 $p$
• 除非 $q$ 才 $p$
• 除非 $q$，否则非 $p$（$\neg q \rightarrow \neg p$，假言易位）

等价 (Biconditional)

如果 $p\rightarrow q$ 且 $q\rightarrow p$，则称 $p$ 和 $q$ 等价，即 $p\leftrightarrow q$，也叫双条件。等价式中的两个命题可以交换。

命题公式