离散数学（一）——命题，逻辑公式与推理论证

一、基本概念

1.逻辑运算符

(1)逻辑与： $𝑝 \land 𝑞$ ，当且仅当 $𝑝, 𝑞$ 都为真时为真。
(2)逻辑或： $𝑝 \lor 𝑞$ ，当且仅当 $𝑝, 𝑞$ 至少一个为真时为真。
(3)逻辑否： $\neg 𝑝$ ，当且仅当 $𝑝$ 为假时为真。
(4)逻辑蕴涵： $𝑝 \to 𝑞$ ，当且仅当 $𝑝$ 为真， $𝑞$ 为假时为假。
(5)逻辑双蕴涵： $𝑝 \leftrightarrow 𝑞$ ，当且仅当 $𝑝, 𝑞$ 真值相同时为真。

2.自然语言(汉语)对照表

(1) $\neg 𝑝$ ：并非 $𝑝$ ；不是 $𝑝$ ； $𝑝$ 不对。

(2) $𝑝 \land 𝑞$ ：不仅 $𝑝$ 而且 $𝑞$ ；既 $𝑝$ 又 $𝑞$ ；虽然 $𝑝$ 但是 $𝑞$ ； $𝑝$ 和/且/并且 $𝑞$ 。

(3) $𝑝 \lor 𝑞$ ：或者 $𝑝$ 或者 $𝑞$ ；要么 $𝑝$ 要么 $𝑞$ ；可能 $𝑝$ 可能 $𝑞$ ； $𝑝$ 或 $𝑞$ 。

(4) $(𝑝 \land \neg 𝑞) \lor (\neg 𝑝 \land 𝑞)$ ： $𝑝$ 或 $𝑞$ 必居其一； $𝑝$ 与 $𝑞$ 不可兼得；只能是 $𝑝$ 或者 $𝑞$ 之一。

(5) $𝑝 \to 𝑞$ ：如果/只要 $𝑝$ 那么/则 $𝑞$ ；有 $𝑝$ 就有 $𝑞$ ；一旦 $𝑝$ 就 $𝑞$ ； $𝑝$ 意味着 $𝑞$ ；因为 $𝑝$ 所以 $𝑞$ ； $𝑝$ 是 $𝑞$ 的充分条件。

(6) $𝑞 \to 𝑝$ ：只有/除非 $𝑝$ 才 $𝑞$ ； $𝑝$ 是 $𝑞$ 的必要条件。

(7) $\neg 𝑝 \to 𝑞$ ： $𝑝$ 除非 $𝑞$ 。

(8) $𝑝 \to 𝑞$ ：除非 $𝑝$ 否则 $𝑞$ 。

(9) $\neg 𝑝 \to \neg 𝑞$ ：不/没有 $𝑝$ 不/没有 $𝑞$ 。

(10) $𝑝 \leftrightarrow 𝑞$ ： $𝑝$ 当且仅当 $𝑞$ ； $𝑝$ 等价于 $𝑞$ ；如果 $𝑝$ 就 $𝑞$ ，反之亦然； $𝑝$ 与 $𝑞$ 互为充要条件。

二、命题

1.命题的基本概念

定义 1.（命题）

命题是具有真假值的陈述句。但陈述句在两种情况下不具有真假值，也即不是命题：

(1)自相矛盾，通常称之为“悖论”。

(2)含有不确定的事物——数学上通常称之为“变量”——的句子。

命题可以由多个命题复合而成，这样的命题称之为复合命题。组成它的命题称为子命题。复合命题的真值应由子命题的真值唯一确定。

但有些命题不能再被分解为子命题的复合，这就称为原子命题。它通常是对一个事物性质的直接描述、或是对几个事物间关系的判断，不含有逻辑联结词。

对于复合命题而言，通过使用逻辑运算符将几个用字母表示的原子命题(命题变量符号)联结形成一个符号串，这个符号串就被称为命题逻辑公式，通常简称为逻辑公式或公式。

三、命题逻辑公式

1.公式的定义

对于一个命题逻辑公式，它在包含原子命题——通常用命题变量符号表示——的同时，还要包含逻辑运算符。

对于公式中的命题变量符号，用一个集合 $𝐕𝐚𝐫$ 来包含它们，称为命题变量符号集。其中的每一个元素，在表层是一个命题变量符号，在深层指代一个命题变量。

公式中除了命题变量符号之外，必然要有逻辑运算符与助记运算顺序的符号，它们分别是 $\neg, \land, \lor, \to, \leftrightarrow, (,)$ 。其中左右圆括号用于标明运算顺序。这些符号组成的集合与命题变量符号集 $𝐕𝐚𝐫$ 的并集，称为命题逻辑公式的符号集。

在给定命题变量符号集 $𝐕𝐚𝐫$ 的情况下，可以相应地构造一个包含所有相应命题逻辑公式的集合，记为 ${ℱ︀}_{𝐕𝐚𝐫}$ 。通常通过归纳法定义之：

定义 2.（命题逻辑公式）

(1)归纳基：每个命题变量都是命题逻辑公式。
(2)归纳步：若

𝐴, 𝐵

是命题逻辑公式，那么：

(\neg 𝐴), (𝐴 \land 𝐵), (𝐴 \lor 𝐵), (𝐴 \to 𝐵), (𝐴 \leftrightarrow 𝐵)

都是命题逻辑公式。

在通常意义下，命题变量符号集 $𝐕𝐚𝐫$ 中包含的命题变量都应是原子命题，用小写字母(可添加下标)来表示；命题逻辑公式用大写字母(可添加下标)来表示。在归纳定义下，公式 $𝐴$ 能且只能处于以下六种形式中的一种：

(1)原子公式： $𝐴$ 是某个原子命题。
(2)否定式： $𝐴 = \neg 𝐵$ ， $𝐴$ 为 $𝐵$ 的否定。
(3)合取式： $𝐴 = 𝐵 \land 𝐶$ ， $𝐴$ 为 $𝐵$ 和 $𝐶$ 的合取。
(4)析取式： $𝐴 = 𝐵 \lor 𝐶$ ， $𝐴$ 为 $𝐵$ 和 $𝐶$ 的析取。
(5)蕴涵式： $𝐴 = 𝐵 \to 𝐶$ ， $𝐴$ 为 $𝐵$ 对 $𝐶$ 的蕴涵。其中， $𝐵$ 称为 $𝐴$ 的前件或前提， $𝐶$ 称为 $𝐴$ 的后件或结论。
(6)双蕴涵式： $𝐴 = 𝐵 \leftrightarrow 𝐶$ ， $𝐴$ 为 $𝐵$ 和 $𝐶$ 的双蕴涵。有时也称之为双条件式。

注 1.（合取与析取的直观理解）

所谓“合”取，即是合并，两者都要考虑，也即都为真时整体才为真；

所谓“析”取，即是分析、选择，两者考虑其一，也即只需有一个为真时整体就为真。

2.公式的简写

如果仅使用左右圆括号来标示运算顺序，对于书写和阅读都有不小的困难。因此规定逻辑运算符的优先级。与四则运算类似，越简单的运算符优先级越高——例如单目运算符必然优先于双目运算符。逻辑运算符的优先级是(从高到低)：

\neg, \land, \lor, \to, \leftrightarrow

其中，由于某些双目运算符不具有两端变量的可交换性，故而需要规定双目运算符的结合性。 $\land, \lor, \leftrightarrow$ 是从左至右结合； $\to$ 是从右至左结合。其中，所谓从左至右结合是指：当一个变量处于两个相同的双目运算符中间时，它参与左边的运算符；从右至左结合则相反。

3.公式的真值

命题逻辑公式的语义是指，在给定命题变量的基础上如何确定公式的真值。按照上述，公式的真值自然要由其包含的原子命题与逻辑联结词来确定。从而给出真值赋值函数的定义：

定义 3.（真值赋值函数）

给定命题变量符号集

𝐕𝐚𝐫

，它的一个真值赋值函数是从

𝐕𝐚𝐫

到真值集

𝟐 = {𝟎, 𝟏}

的一个函数

𝜎 : 𝐕𝐚𝐫 \to 𝟐

。

在给定真值赋值函数的情况下，自然可以确定任意公式 $𝐴 \in {ℱ︀}_{𝐕𝐚𝐫}$ 的真值，记为 $𝜎 (𝐴)$ 。

公式 $𝐴$ 的真值表，是以表格的形式给出公式在任意真值赋值函数下的真值。从而含有 $𝑛$ 个命题变量的公式的真值表必有 $2^{𝑛}$ 行。

对于公式 $𝐴$ ，若在任意真值赋值函数 $𝜎 : 𝐕𝐚𝐫 \to 𝟐$ 下总有：
(1) $𝜎 (𝐴) = 1$ ，称 $𝐴$ 为永真式，或重言式；
(2) $𝜎 (𝐴) = 0$ ，称 $𝐴$ 为矛盾式，或永假式。
若 $𝐴$ 不处于以上两种状态，则称为偶然式；若 $𝐴$ 不是矛盾式，则说它是可满足的。

4.公式的等值演算

为了简化公式，总结出以下基本逻辑等值式模式：

表 1 基本逻辑等值式模式

序号	名称	等值式
1	同一律	$\begin{matrix} 𝐴 \land 1 \equiv 𝐴 \\ 𝐴 \lor 0 \equiv 𝐴 \end{matrix}$
2	零律	$\begin{matrix} 𝐴 \land 0 \equiv 0 \\ 𝐴 \lor 1 \equiv 1 \end{matrix}$
3	矛盾律	$𝐴 \land (\neg 𝐴) \equiv 0$
4	排中律	$𝐴 \lor (\neg 𝐴) \equiv 1$
5	双重否定律	$\neg (\neg 𝐴) \equiv 𝐴$
6	幂等律	$\begin{matrix} 𝐴 \land 𝐴 \equiv 𝐴 \\ 𝐴 \lor 𝐴 \equiv 𝐴 \end{matrix}$
7	交换律	$\begin{matrix} 𝐴 \land 𝐵 \equiv 𝐵 \land 𝐴 \\ 𝐴 \lor 𝐵 \equiv 𝐵 \lor 𝐴 \end{matrix}$
8	结合律	$\begin{matrix} 𝐴 \land (𝐵 \land 𝐶) \equiv (𝐴 \land 𝐵) \land 𝐶 \\ 𝐴 \lor (𝐵 \lor 𝐶) \equiv (𝐴 \lor 𝐵) \lor 𝐶 \end{matrix}$
9	分配律	$\begin{matrix} 𝐴 \land (𝐵 \lor 𝐶) \equiv (𝐴 \land 𝐵) \lor (𝐴 \land 𝐶) \\ 𝐴 \lor (𝐵 \land 𝐶) \equiv (𝐴 \lor 𝐵) \land (𝐴 \lor 𝐶) \end{matrix}$
10	吸收律	$\begin{matrix} 𝐴 \land (𝐴 \lor 𝐵) \equiv 𝐴 \\ 𝐴 \lor (𝐴 \land 𝐵) \equiv 𝐴 \end{matrix}$
11	德摩根律	$\begin{matrix} \neg (𝐴 \land 𝐵) \equiv (\neg 𝐴) \lor (\neg 𝐵) \\ \neg (𝐴 \lor 𝐵) \equiv (\neg 𝐴) \land (\neg 𝐵) \end{matrix}$
12	蕴涵等值式	$𝐴 \to 𝐵 \equiv \neg 𝐴 \lor 𝐵$
13	蕴涵等值式	$𝐴 \leftrightarrow 𝐵 \equiv (𝐴 \to 𝐵) \land (𝐵 \to 𝐴)$

5.公式的范式

由于逻辑且与逻辑或相较于(双)蕴涵更加基础，自然希望所有的公式能够对应一个标准的范式——仅含且及或。为此需要引入以下概念：

所谓文字，是指一个命题变量或其的否定。 ¹¹ 复习：合取是逻辑且，需要同时考虑；析取是逻辑或，选择其一考虑。

一个或多个文字的合取，称为简单合取式；相应地，一个或多个文字的析取，称为简单析取式。

而一个或多个简单合取式的析取，称为析取范式；相应地，一个或多个简单析取式的合取，称为合取范式。

应当注意，否定运算符只能出现在文字中。

有趣的是，单个文字可以看做一个简单合取式或简单析取式，而单个简单合取式或简单析取式也可以看做一个析取范式或合取范式(注意前后对应)。

若含有 $𝑛$ 个命题变量的合取式恰是 $𝑛$ 个文字的合取(每个文字都只对应一个命题变量)，那么此合取式称为极小项；相应地，含有 $𝑛$ 个命题变量的析取式恰是 $𝑛$ 个文字的析取，那么此析取式称为极大项。

注 2.（极小项与极大项的直观理解）

所谓极“小”项，它的每一个文字间以逻辑且连接，只要有一个为假整体即为假，真值容易取到0；所谓极“大”项，它的每一个文字间以逻辑或连接，只要有一个为真整体即为真，真值容易取到1。

含有 $𝑛$ 个命题变量的零个或多个极小项的析取，称为主析取范式；相应地，含有 $𝑛$ 个命题变量的零个或多个极大项的合取，称为主合取范式。

在固定命题变量出现顺序的情况下， $𝑛$ 个命题变量必然能构成 $2^{𝑛}$ 个极小项或极大项。从而允许我们以如下的方式对所有的极小项或极大项进行简约的表示：

(0) $0 \sim 2^{𝑛} - 1$ 共计 $2^{𝑛}$ 个十进制整数，这些整数都可以写为一个 $𝑛$ 位的二进制数(或称为编码)，恰好对应固定顺序的 $𝑛$ 个命题变量。每一位的 $0$ 或 $1$ 恰好可以描述其对应的命题变量是否被否定；
(1)对极小项而言，用小写 $𝑚$ 表示。每一种极小项必是 $𝑚_{0} \sim 𝑚_{2^{𝑛} - 1}$ 中的一个。二进制编码某位上的 $0$ 表示其对应的命题变量被否定；
(2)对极大项而言，用大写 $𝑀$ 表示。每一种极大项必是 $𝑀_{0} \sim 𝑀_{2^{𝑛} - 1}$ 中的一个。二进制编码某位上的 $1$ 表示其对应的命题变量被否定。

注 3.

例如，当 $𝑛 = 3$ ，那么 $𝑚_{1}$ 对应编码为001，展开写为 $\neg 𝑝 \land \neg 𝑞 \land 𝑟$ ； $𝑀_{6}$ 对应编码为110，展开写为 $\neg 𝑝 \lor \neg 𝑞 \lor 𝑟$ 。

这样的编码是有意义的。对于极小项而言，只有当某位对应的命题变量被赋值为此位的值时，整体才是真的。例如上述 $𝑚_{1}$ 只有在赋值 $𝜎 (𝑝) = 0, 𝜎 (𝑞) = 0, 𝜎 (𝑟) = 1$ 的情况下才为真；

对于极大项而言，只有当某位对应的命题变量被赋值为此位的值时，整体才是假的。例如上述 $𝑀_{6}$ 只有在赋值 $𝜎 (𝑝) = 1, 𝜎 (𝑞) = 1, 𝜎 (𝑟) = 0$ 的情况下才为假。

一个公式的主析取范式与它的主合取范式是互补的。这就是说，在主析取范式中已经出现的编码不会在主合取范式中出现。

注 4.

例如，当

𝑛 = 3

，若

𝐴

的主析取范式是

𝑚_{0} \lor 𝑚_{2} \lor 𝑚_{4} \lor 𝑚_{6}

，那么

𝐴

的主合取范式必是

𝑀_{1} \land 𝑀_{3} \land 𝑀_{5} \land 𝑀_{7}

。

四、推理

1.推理的有效性

推理，是指从一组命题(称作前提)得到一个命题(称作结论)的过程，一般记作：

𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛} ⟹ 𝐵

$𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛}$ 即是前提， $𝐵$ 即是结论。在这里，若：

(𝐴_{1} \land 𝐴_{2} \land \dots \land 𝐴_{𝑛}) \to 𝐵

是永真式，那么称此推理是有效的。通俗地说若所有前提都是真的，那么结论也必然是真的，或者全真的前提不可能导向假的结论，即有效推理是保真的。

注 5.

但是有效推理并不强制要求结论是真的——只要前提并非是全真的。结论不为真也不一定说明推理不是有效的。

2.推理规则

下列是常用的推理规则：

(1)假言推理，亦称为分离规则：

𝐴 \to 𝐵, 𝐴 ⟹ 𝐵

(2)假言易位，亦称为拒取式：

\begin{matrix} 𝐴 \to 𝐵, \neg 𝐵 ⟹ \neg 𝐴 \\ 𝐴 \to \neg 𝐵, 𝐵 ⟹ \neg 𝐴 \end{matrix}

(3)合取规则：

𝐴, 𝐵 ⟹ 𝐴 \land 𝐵

(4)化简规则：

𝐴 \land 𝐵 ⟹ 𝐴

(5)附加规则：

𝐴 ⟹ 𝐴 \lor 𝐵

(6)析取三段论规则：

\neg 𝐴, 𝐴 \lor 𝐵 ⟹ 𝐵

(7)假言三段论规则：

𝐴 \to 𝐵 ， 𝐵 \to 𝐶 ⟹ 𝐴 \to 𝐶

(8)双蕴涵推理规则：

𝐴 \leftrightarrow 𝐵 ⟹ 𝐴 \to 𝐵 𝐴 \leftrightarrow 𝐵 ⟹ 𝐵 \to 𝐴

(9)等值置换规则：在(三、4.公式的等值演算)中出现的等值式模式 $𝐴 \equiv 𝐵$ ，都存在 $𝐴 ⟹ 𝐵$ 和 $𝐵 ⟹ 𝐴$ 。

注 6.（推理规则的直观理解）

假言推理：肯定蕴涵式的前提从而肯定结论；
假言易位：否定蕴涵式的结论从而否定前提；
合取：任意有限个的前提可以看做一个前提，并且需要同时考虑。实际反映了推理的有效性，即只有前提全真结论才为真；
化简：合取式的任一分支都能作为中间结论；
附加：前提为真，一定能保证包含前提的析取式为真；
析取三段论：类似于排除法，否定“或”条件中的某些分支从而肯定余下的分支；
假言三段论：

𝐵

是

𝐶

的前提，

𝐴

是

𝐵

的前提，那么

𝐴

是

𝐶

的前提；
双蕴涵推理：充要条件中的两个命题，可以互为前提和结论。

五、论证

1.论证

论证，或称为证明，用于验证推理 $𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛} ⟹ 𝐵$ 的有效性。它是指这样一个公式序列——以结论公式 $𝐵$ 结束：

\begin{aligned} (1) 𝐵_{1} \\ (2) 𝐵_{2} \\ ⋮ \\ (𝑚) 𝐵_{𝑚} = 𝐵 \end{aligned}

并且对于任意的 $1 \leq 𝑖 \leq 𝑚$ ，公式 $𝐵_{𝑖}$ 必是下列两种情况之一：
(1)是推理的前提之一，即 $𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛}$ 其中之一；
(2)是由此公式之前的有限个公式，通过推理规则(即四、2中内容)得到的。

一般而言为了便于阅读，会在每个公式之后注释说明此行公式的性质——即是前提，或是由某个推理规则得到。

注 7.（一个论证的例子）

例如对于双蕴涵推理，它属于派生规则——即可以由更“基础的”推理规则得到。这里示例它的论证过程：

论证 $𝐴 \leftrightarrow 𝐵 ⟹ 𝐴 \to 𝐵$ ：

\begin{cases} (1) 𝐴 \leftrightarrow 𝐵 \\ (2) (𝐴 \to 𝐵) \land (𝐵 \to 𝐴) \\ (3) 𝐴 \to 𝐵 \end{cases} \begin{cases} \ \ 前提 \\ \ \ (1) 等值置换 \\ \ \ (2) 化简规则 \end{cases}

2.论证的附加前提法

当推理的结论是蕴涵式时，仅靠“2.推理规则” 中 $(1) \sim (6)$ 的推理规则是无法论证的。但是由于：

𝐴 \to (𝐵 \to 𝐶) \equiv (𝐴 \land 𝐵) \to 𝐶

因而下列两个推理有效性是相同的：

\begin{matrix} 𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛} ⟹ 𝐵 \to 𝐶 \\ 𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛}, 𝐵 ⟹ 𝐶 \end{matrix}

此时论证使用下列的写法：

\begin{cases} (1) & 𝐵 \\ ⋮ \\ (𝑘) & 𝐶 \\ (𝑘 + 1) & 𝐵 \to 𝐶 \end{cases} \begin{cases} \ \ 附加前提 \\ \ \ 论证 𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛}, 𝐵 ⟹ 𝐶 \\ \ \ 需以 𝐶 作为上述论证的结束 \\ \ \ (1), (k) 附加前提法 \end{cases}

3.论证的反证法

当推理的结论是否定式时，下列两个推理有效性是相同的：

\begin{matrix} 𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛} ⟹ \neg 𝐵 \\ 𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛}, 𝐵 ⟹ 𝐶 \land \neg 𝐶 \end{matrix}

也就是，当结论不被否定时，与所有前提一起应构成一个矛盾式。此处的 $𝐶$ 应是推理过程中出现的任意一个公式。

此时论证使用下列的写法：

\begin{cases} (1) & 𝐵 \\ ⋮ \\ (𝑘_{1}) & 𝐶 \\ ⋮ \\ (𝑘_{2}) & \neg 𝐶 \\ ⋮ \\ (𝑚) & \neg 𝐵 \end{cases} \begin{cases} \ \ & 附加前提 \\ \ \ & (1), (𝑘_{1}), (𝑘_{2}) 反证法 \end{cases}