离散数学第一章: 数理逻辑

数理逻辑

1. 断言与命题#

1.1 断言#

定义: 断言是一个陈述句。

1.2 命题#

定义: 命题是一个有明确真假的断言。

如果有的断言不可以被指定真假，比如”我说的是假的”，这种断言叫做”悖论”。

定义: 不能再被分解的最简单的命题叫做原子命题或本原命题。

命题之间可以用命题连接词连接，形成新的命题。

1.3 命题连接词#

运算顺序: $\neg \ > \ \wedge \ >\ \vee \> \ \to \ > \ \leftrightarrow$

否定连接词 $\neg$ #

合区词 $\wedge$ #

析取词 $\vee$ ：可兼或#

蕴含词 $\rightarrow$ #

$P \to Q$ 和以下说法均等价:

如果 $P$ ，那么 $Q$
$P$ 是 $Q$ 的充分条件
$Q$ 是 $P$ 的必要条件
$P$ 仅当 $Q$
$Q$ 每当 $P$

等值词 $\leftrightarrow$ #

$P \leftrightarrow Q \Leftrightarrow P\to Q \wedge Q \to P$

并且 $P \leftrightarrow Q$ 等价于:

$P$ 是 $Q$ 的充要条件
$Q$ 是 $P$ 的充要条件
$P$ 当且仅当 $Q$
$Q$ 当且仅当 $P$

1.4 命题公式#

若变元 $P$ 的值域为真值域 $\{True,False\}$ ，就叫做命题变元。

若常量值 $T/F$ 代表真值 $True$ 或 $False$ ，则 $T/F$ 称为命题常元。

定义: 单个命题变元和单个命题常元叫做原子公式。

归纳定义:
①. 单个原子公式是命题公式
②. 若 $P$ 和 $Q$ 都是命题公式，则…也是命题公式。
③. 只有有限步使用上述规则得到的公式才是命题公式。

上述归纳定义得出的公式也叫做合式公式。

1.5 命题的逻辑等价#

如果命题公式 $P$ 和 $Q$ 在所有指派下都具有相同的真值，则 $P$ 和 $Q$ 逻辑等价。

可记作 $P \Leftrightarrow Q$ ， $P$ 和 $Q$ 逻辑恒等。

2. 重言式(永真式)#

对于一个具有 $n$ 个变元的命题公式 $A(\alpha_1,\alpha_2,\cdots,\alpha_n)$ ,变元 $\alpha_i$ 的真值一共有 $2^n$ 种，每一种组合叫做一种指派。

定义: 对于每一种指派，如果命题公式 $A$ 的真值都是真，则命题公式 $A$ 是一个重言式(永真式)。

定义: 对于每一种指派，如果命题公式 $A$ 的真值都是假，则命题公式 $A$ 是一个矛盾式(永假式)。

定义: 对于不同指派，如果命题公式 $A$ 的真值有真有假，则命题公式 $A$ 是一个偶然式。

永真蕴含式和恒等式具有传递特性，即 $A \Rightarrow B, B \Rightarrow C$ ,则 $A \Rightarrow C$ ； $A \Leftrightarrow B, B \Leftrightarrow C$ ,则 $A \Leftrightarrow C$ 。
永真蕴含式有如下特性: $A \Rightarrow B, A \Rightarrow C$ ，则 $A \Rightarrow B \wedge C$ 。

2.1 代入规则: 重言式中的变元代入为任意公式#

一个永真式 $P(a_1,a_2,\cdots,a_n)$ 有 $n$ 个变元，则将其中任意变元所在的所有位置用任意公式代入后，得到另一永真式 $P'$ 。

注意，永真式使用代入规则后还是永真式，但是偶然式不一定！

2.2 替换规则: 用逻辑恒等式替换公式#

定义：若一个公式 $C$ 是公式 $P$ 中其中完整的一部分，则称 $C$ 是公式 $P$ 的子公式。

若存在逻辑恒等式 $C \Leftrightarrow D$ ，则可以将公式 $P$ 中的子公式 $C$ 替换为公式 $D$ ，如此得到公式 $P'$ ，且 $P \Leftrightarrow P'$ 。

2.3 对偶公式#

定义:

对公式 $A(a_1,a_2,\cdots,a_n)$ ，定义其对偶公式 $A^*$ 为:

\begin{align} 公式A中: \\\\ \wedge 换为 \vee \\\\ \vee 换为 \wedge \\\\ T 换为 F \\\\ F 换为T \\\\ 得到新公式A^*(a_1,a_2,\cdots,a_n) \end{align}

定理: $\neg A(a_1,a_2,\cdots,a_n) = A^*(\neg a_1, \neg a_2,\cdots, \neg a_n)$

延申定理: 当 $A$ 和 $B$ 都为变元 $(a_1,a_2,\cdots,a_n)$ 的命题公式时:

A \to B \Leftrightarrow B^* \to A^* \\\\ A \leftrightarrow B \Leftrightarrow A^* \leftrightarrow B^*

3. 范式#

3.1 基本积与基本和#

定义：一些命题变元和一些命题变元的否定之积(合取)，称为基本积。
定理：当一个基本积是永假式，当且仅当这个基本积中包含 $P$ 和 $\neg P$ 。

定义：一些命题变元和一些命题变元的否定之和(析取)，称为基本和。
定理：当一个基本和是永真式，当且仅当这个基本和中包含 $P$ 和 $\neg P$ 。

3.2 析取范式和合取范式#

定义 $3.2.1$ ：如果存在一个由基本积的析取形成的公式 $A'$ 和公式 $A$ 等价，即:
$A \Leftrightarrow A' = A_1 \vee A_2 \vee \cdots \vee A_n$
其中 $A_i$ 为基本积，则称 $A'$ 是公式 $A$ 的析取范式(积之和)。其中含有最少运算符的析取范式叫做最简析取范式。(用卡诺图可化简)

定义 $3.2.2$ ：如果存在一个由基本和的合取形成的公式 $B'$ 和公式 $B$ 等价，即:
$B \Leftrightarrow B' = B_1 \wedge B_2 \wedge \cdots \wedge B_n$
其中 $B_i$ 为基本和，则称 $B'$ 是公式 $B$ 的合取范式(和之积)。其中运算符个数最少的合取范式叫做最简合取范式。(先求 $B^*$ 的最简析取式)

3.3 极小项和极大项#

定义 $3.3.1$ ：对于一个 $n$ 元命题公式 $A(a_1,a_2,\cdots,a_n)$ ，假如基本积中每个变元或该变元的逆不同时出现，并且只出现其中的一个，则这个基本积叫做命题公式 $A$ 的极小项。

显然 $n$ 元命题公式 $A(a_1,a_2,\cdots,a_n)$ 有且仅有 $2^n$ 个极小项，可以用二进制数对应这些极小项，对应用 $m_i$ 表示：

\begin{align} \neg a_1 \wedge \neg a_2 \wedge \cdots \wedge \neg a_n -----> 00\cdots0(m_0) \\\\ a_1 \ \ \wedge a_2 \ \wedge \cdots \wedge a_n \ \ -----> 11\cdots1(m_{2^n -1}) \end{align}

性质 $3.3.1$ ：
$m_i \wedge m_j \Leftrightarrow F(i \ne j) \\\\ \mathop{\vee}\limits_{i=0}^{2^n-1}m_i \Leftrightarrow T$

定义 $3.3.2$ ：对于一个 $n$ 元命题公式 $A(a_1,a_2,\cdots,a_n)$ ，假如基本和中每个变元或该变元的逆不同时出现，并且只出现其中的一个，则这个基本和叫做命题公式 $A$ 的极大项。

$n$ 元命题公式 $A(a_1,a_2,\cdots,a_n)$ 同样也有 $2^n$ 个极大项，也用二进制数表示极大项(表示方式和极小项相反)，但用 $M_i$ 表示:

\begin{align} a_1 \ \ \wedge a_2 \ \wedge \cdots \wedge a_n \ \ -----> 00\cdots0(M_{0}) \\\\ \neg a_1 \wedge \neg a_2 \wedge \cdots \wedge \neg a_n -----> 11\cdots1(M_{2^{n}-1}) \end{align}

性质 $3.3.2$ ：
$M_i \vee M_j \Leftrightarrow T(i \ne j) \\\\ \mathop{\wedge}_{i=0}^{2^n-1}M_i \Leftrightarrow F$

性质 $3.3.3$ ：
$\neg m_i \Leftrightarrow M_i \\\\ \neg M_i \Leftrightarrow m_i$

3.4 主析取范式和主合取范式#

定义 $3.4.1$ ：如果一个析取范式中的基本积全都是极小项，那么这个析取范式叫做主析取范式。

定义 $3.4.2$ ：如果一个合取范式中的基本和全都是极大项，那么这个合取范式叫做主合取范式。

每一个命题公式 $A$ 都对应一个真值表，也对应一个主析取范式和主合取范式。

对于 $n$ 元命题 $A(a_1,a_2,\cdots,a_n)$ 共有 $2^n$ 个极大项/极小项，可以组合出 $2^{2^n}$ 种主合取范式/主析取范式/真值表，因此一共有 $2^{2^n}$ 种 $n$ 变元命题。

4. 连结词的扩充与规约#

4.1 连结词的扩充#

二元运算还可以定义有意义的几个运算：

\begin{align} 与非: P\uparrow Q &\Leftrightarrow \neg P \vee \neg Q \\ 或非: P\downarrow Q &\Leftrightarrow \neg P \wedge \neg Q \\ 异或: P \oplus Q &\Leftrightarrow P \wedge \neg Q \vee \neg P \wedge Q \\ 蕴含否定: P \nrightarrow Q & \Leftrightarrow \neg (P\rightarrow Q) \Leftrightarrow \neg(\neg P \vee Q) \Leftrightarrow P \wedge \neg Q \end{align}

定理 $4.1.1$ 与非 $\uparrow$ 可交换，不可结合。

定理 $4.1.2$ 或非 $\downarrow$ 可交换，不可结合。

定理 $4.1.3$ 异或 $\oplus$ 可交换，可结合。且 $\wedge$ 在 $\oplus$ 上可以分配。

定理 $4.1.4$ 等值 $\leftrightarrow$ 可交换，可结合。且 $\vee$ 在 $\leftrightarrow$ 上可以分配。

4.2 连结词的规约#

定义 $4.2.1$ 如果某个连结词集合能够表示任意命题，则称此连结词集合是全功能的。

定理 $4.2.1$ 某个连结词集合是全功能的当且仅当它可以完全表示另一个全功能集合中的连结词。

\{\neg,\wedge\},\{\neg,\vee \}是全功能的

\{\neg,\rightarrow\},\{\neg,\nrightarrow\}是全功能的(\neg P\rightarrow Q \Leftrightarrow P \vee Q, P \nrightarrow \neg Q \Leftrightarrow P \wedge Q)

\{F,\rightarrow\},\{T,\nrightarrow\}也是全功能的(P \rightarrow F \Leftrightarrow \neg P, T \nrightarrow P \Leftrightarrow \neg P)

\{\uparrow\},\{\downarrow\}是全功能的

但 $\{\wedge,\vee,\rightarrow,\leftrightarrow\}$ 的所有子集， $\{\leftrightarrow,\neg\},\{\oplus,\neg\},{\neg}$ 是非全功能的。

4.3 其他主范式#

用极小项的 $\oplus$ 和(异或和)能得到和主析取范式类似的主异或范式。(最多只有一个极小项为0)
用极大项的 $\leftrightarrow$ 积(等值积)能得到和主合取范式类似的主等值范式。(最多只有一个极大项为1)

5. 推理规则和证明方法#

5.1 有效结论#

定义: 若 $H_1 \wedge H_2 \wedge H_3 \wedge \cdots \wedge H_n \Rightarrow C$ ，则称 $C$ 为 $H_1,H_2,H_3,\cdots,H_n$ 的有效结论

注意: $有效结论 \ne 正确结论$ ，因为还有 $H_1 \wedge H_2 \wedge H_3 \wedge \cdots \wedge H_n$ 的正确性。只是推理是正确的。

5.2 推理规则#

不太容易想到的几个推理规则(永真蕴含式):

\begin{align} (P \to Q) \wedge \neg Q \Rightarrow & \neg P \\ (P \to Q) \wedge (Q\to R) \Rightarrow & P \to R \\ (P \to Q) \wedge (R \to S) \wedge (P \vee R) \Rightarrow & Q \vee S \\ (P \to Q) \wedge (R \to S) \wedge (\neg Q \vee \neg S) \Rightarrow& \neg P \vee \neg R \end{align}

以及重要的两个特殊推理规则:

\begin{align} &1. 可以在推理的任何时刻引入前提条件。 &(P规则)\\ &2. 如果之间的推理过程中的一条或多条公式永真蕴含S，则可以把S引入推理过程。&(T规则) \end{align}

5.3 证明方法#

5.3.1 $P \to Q$ 形式的证明方法#

所有证明几乎都可以化为 $P \to Q$ 形式的证明，比如 $P \vee Q \Leftrightarrow \neg P \to Q$ 。

这种形式的证明可以用：

证明 $P$ 永假（无义证明法）
证明 $Q$ 永真（平凡证明法）
假定 $P$ 为真，证明 $Q$ 为真（直接证明法）
假定 $\neg Q$ 为真，证明 $\neg P$ 为真（间接证明法，逆反证明法）
$P$ 的主析取范式极小项的集合 $S_P\subseteq$$S_Q$ （Q的主析取范式极小项的集合)
$P$ 的主合取范式极大项的集合 $S'_P \supseteq S'_Q$ （Q的主合取范式极大项的集合)

5.3.2 $P_1 \wedge P_2 \wedge P_3 \wedge \cdots \wedge P_n \to Q$ 形式的证明方法#

属于 $P \to Q$ 的一种特殊情况，当然可以用 $P \to Q$ 形式的证明方法。

5.3.2.1 间接证明法的部分情况#

除此之外还可以将转化为 $\neg Q \to \neg P_1 \vee \neg P_2 \vee P_3 \vee \cdots \vee \neg P_n$ 。因为:

\neg P_i \to \neg P_1 \vee \neg P_2 \vee P_3 \vee \cdots \vee \neg P_n

所以如果能证明:

\neg Q \to \neg P_i

也就能证明 $\neg Q \to \neg P_1 \vee \neg P_2 \vee P_3 \vee \cdots \vee \neg P_n$ ，即 $P_1 \wedge P_2 \wedge P_3 \wedge \cdots \wedge P_n \to Q$ 。属于是间接证明法的推广。

5.3.2.2 反证法#

假设有命题变元 $P_1,P_2,\cdots,P_n$ 的命题公式 $\{H_1,H_2,\cdots,H_n\}$ 。

定义 $\{H_1,H_2,\cdots,H_n\}$ 的一致性: 若存在一种 $P_1,P_2,\cdots,P_n$ 的指派使得 $H_1\wedge H_2 \wedge \cdots \wedge H_n$ 为真，则称 $\{H_1,H_2,\cdots,H_n\}$ 一致，否则不一致。
另一种定义方法：
$H_1\wedge H_2 \wedge \cdots \wedge H_n \Rightarrow F$
则 $\{H_1,H_2,\cdots,H_n\}$ 不一致，反之则一致。

逆反证明法(归谬法):
若要证明 $P_1 \wedge P_2 \wedge P_3 \wedge \cdots \wedge P_n \to Q$ ，可以证明 $\{P_1,P_2,\cdots,P_n,\neg Q\}$ 不一致。即证明: $P_1 \wedge P_2 \wedge P_3 \wedge \cdots \wedge P_n \wedge \neg Q \Rightarrow F$ 。也就是假定结论为假，和前提矛盾。

5.3.3 $P_1 \wedge P_2 \wedge P_3 \wedge \cdots \wedge P_n \to (P \to Q)$ 形式的证明方法#

有永真恒等式：

S \to (P \to Q) \Leftrightarrow S \wedge P \to Q

故：

P_1 \wedge P_2 \wedge P_3 \wedge \cdots \wedge P_n \to (P \to Q) \Leftrightarrow \\ P_1 \wedge P_2 \wedge P_3 \wedge \cdots \wedge P_n \wedge P \to Q

$CP$ 规则: 证明 $P_1 \wedge P_2 \wedge P_3 \wedge \cdots \wedge P_n \to (P \to Q)$ 即证明 $P_1 \wedge P_2 \wedge P_3 \wedge \cdots \wedge P_n \wedge P \to Q$ 。这也叫做演绎定理。

通过 $CP$ 规则就转换为 $5.3.2$ 中的形式。

5.3.4 $P_1 \vee P_2 \vee P_3 \vee \cdots \vee P_n \to Q$ 形式的证明方法#

\begin{align} P_1 \vee P_2 \vee P_3 \vee \cdots \vee P_n \to Q &\Leftrightarrow\neg( P_1 \vee P_2 \vee P_3 \vee \cdots \vee P_n) \vee \neg Q \\ &\Leftrightarrow \mathop{\wedge}\limits_{i=1}^{n}(\neg P_i \vee Q) \end{align}

故此种形式只需要证明对于每一 $1\le i \le n$ ， $\neg P_i \vee Q$ 均为真即可。

5.4 有效结论的个数#

如果命题公式 $P$ 的主合取范式一共有 $m$ 个极大项，具有相同变元个数的不同有效结论的个数为 $2^m-1$ 个(不包含0个极大项的情况(永真))。
[ $P$ 的主合取范式极大项集合 $S_P \supseteq S_Q$ (Q的主合取范式极大项的集合)]

6. 谓词和量词#

6.1 谓词#

定义 $6.1.1$ 任何事物都可以被称为个体，比如函数，具体的数，用来表示个体的变元叫做个体变元。一般用小写字母表示。

定义 $6.1.2$ 用来刻画个体的性质或者是个体间的关系的模式叫做谓词命名式，简称谓词。一般用大写字母表示。如果表示的是 $n$ 个个体之间的关系，那么就叫做** $n$ 元谓词**，可以记为 $P(a_1,a_2,\cdots,a_n)$ 。
特性谓词是指描述个体属性的谓词，比如 $M(x):x是人$ 。

定义 $6.1.3$ 如果一个大写字母表示一个特定的谓词，那么就叫做谓词常元，如果代表一类任意的谓词，就叫做谓词变元。

只有单独的谓词或者是只有单独的个体都无法构成命题.

只有给谓词中的变元取定值或者是量化后才成为命题。其中变元的取值范围叫做变元的论述域或个体域。

6.2 量词#

量词分为全称量词 $\forall$ 和存在量词 $\exists$ 。

在谓词前加上量词就称为变元的量化(全称量化和存在量化)。量化的作用是约束变元。

关于特性谓词如何加入到量词中去，比如如何表示对于所有人/存在人:

\begin{align} &全称量词\forall中特性谓词作为\to的前件 \\ &存在量词\exists中特性谓词作为合取项 \end{align}

把所有变元都量化后的谓词也变成了命题公式。

有些特殊论述域的谓词的量化和命题其实是等价的，比如：

\begin{align} &对于有限论述域S=\{a_1,a_2,a_3,\cdots,a_n\} &\\ & &\forall xP(x) \Leftrightarrow \mathop{\wedge}_{i=1}^nP(a_i) \\ & &\exists xP(x) \Leftrightarrow \mathop{\vee}_{i=1}^nP(a_i) \\ &对于无限可数论述域S=\{a_1,a_2,a_3,\cdots\} & \\ & &\forall xP(x) \Leftrightarrow \mathop{\wedge}_{i=1}^{\infty}P(a_i) \\ & &\exists xP(x) \Leftrightarrow \mathop{\vee}_{i=1}^{\infty}P(a_i) \\ \end{align}

6.3 谓词公式#

谓词公式的定义方法和命题公式一样，都是采用归纳定义：

定义 $6.3.1$ 不包含任何命题连结词和量词的谓词是谓词演算的原子公式。

\begin{align} &1. 谓词演算的原子公式都是谓词演算公式。 \\ &2. 若A，B是谓词演算公式，则A\wedge B,A \vee B,A \to B,A\leftrightarrow B,\neg A,\forall xA,\exists xA都是谓词演算公式。\\ &3. 只有有限步使用1和2产生的公式才是为此演算公式。 \end{align}

6.4 自由变元和约束变元#

默认量词的约束范围是最近的最小子公式。

\forall xP(x) \to Q(x)

只有 $P(x)$ 的 $x$ 被约束，而 $Q(x)$ 中的 $x$ 仍自由。

约束变元和自由变元都是可更改名字的。但是我们一般更改约束变元的名字。

约束变元更改名字要保证：

约束范围内所有该变元都要一起更改。
更改后的变元名不能和约束范围内的其他变元冲突。

7. 谓词演算的永真公式和推理规则#

7.1 谓词公式的等价#

定义 $7.1.1$ 若谓词 $A$ 和谓词 $B$ 有公共论述域 $E$ ，且:
给 $A$ 和 $B$ 中的谓词变元赋予论述域上有意义的任意谓词
给 $A$ 和 $B$ 中的个体变元赋予论述域上有意义的任意个体
若谓词 $A$ 和 $B$ 的真值都一样，则称谓词 $A$ 和谓词 $B$ 遍及论述域 $E$ 等价。

定义 $7.1.2$ 若谓词 $A$ 和谓词 $B$ 在任意论述域上都等价，则称 $谓词A$ 和 $谓词B$ 等价。

7.2 谓词公式的永真#

定义 $7.2.1$ 若谓词 $A$ 在论述域 $E$ 上都进行谓词变元和个体变元的任意指派:
如果谓词 $A$ 的真值都为真，则称谓词 $A$ 在论述域 $E$ 上永真
如果至少存在一种指派使得谓词 $A$ 的真值为真，则称谓词 $A$ 在论述域 $E$ 上可满足
如果谓词 $A$ 的真值都为假，则称谓词 $A$ 在论述域 $E$ 上永假或不可满足

定义 $7.2.2$ 若谓词 $A$ 在任何论述域 $E$ 上都进行谓词变元和个体变元的任意指派:
如果谓词 $A$ 的真值都为真，则称谓词 $A$ 永真
如果至少存在一种指派使得谓词 $A$ 的真值为真，则称谓词 $A$ 可满足
如果谓词 $A$ 的真值都为假，则称谓词 $A$ 永假或不可满足

7.3 基本永真谓词公式#

7.3.1 量词的否定#

\begin{align} \neg \forall x P(x)\Leftrightarrow \exists x \neg P(x) \\ \neg \exists x P(x) \Leftrightarrow \forall x \neg P(x) \end{align}

7.3.2 量词的分配#

\begin{align} \forall x (P(x) \wedge Q(x)) &\Leftrightarrow \forall x(P(x)) \wedge \forall x (Q(x)) \\ \forall x(P(x)) \vee \forall x(Q(x)) &\Rightarrow\forall x(P(x) \vee Q(x)) \\ \exists x(P(x) \wedge Q(x)) &\Rightarrow \exists x(P(x)) \wedge \exists x(Q(x)) \\ \exists x(P(x) \vee Q(x)) &\Leftrightarrow \exists x(P(x)) \vee \exists x(Q(x)) \end{align}

7.4 基本谓词演算规则#

7.4.1 代入规则#

代入规则一般只对永真式有效。

在一个永真谓词公式中的一个自由变元 $\alpha$ 可以以另一个非约束变元个体变元 $\beta$ 替代，并且 $\alpha$ 出现的每一处都要用 $\beta$ 替代。
在一个永真谓词公式中的一个 $n$ 元命题公式 $P$ 可以用另一个至少 $n$ 元的命题公式 $Q$ 替代，只是这两个公式中的变元都不能是另一个公式中的约束变元。

7.4.2 替换规则#

替换规则一般针对两等价谓词。

若两谓词 $A$ 和 $B$ 等价，则在以 $A$ 作为子公式的 $C$ 中出现 $A$ 的任意地方(不必每一处)都用 $B$ 替代，得到公式 $C'$ ，那么 $C \Leftrightarrow C'$ 。

7.4.3 对偶规则#

定义 $7.4.1$ 对偶公式:
$把谓词A中的\vee和\wedge互换，\exists和\forall互换，T和F互换得到A的对偶公式A^*.$

有:

\begin{align} 1. 若A\Leftrightarrow B则A^*\Leftrightarrow B^* \\ 2. 若A \Rightarrow B则B ^*\Rightarrow A^* \end{align}