离散数学
一、命题逻辑
1.1 命题符号化和联结词
能判断真假的 陈述句 叫做 命题 。
- 称判断为正确的命题的 真值(值) 为 真
- 称判断为错误的命题的真值为 假
Tip
这朵花多好看呀!为感叹句
x + y > 5没有确定的真值，不为命题
明年10月1日是晴天为命题，真值唯一
类似于明年10月1日是晴天这样的简单陈述句无法再拆分，称为 简单命题 / 原子命题 ，用\(p,q,r,...,p_i,q_i,r_i,...\)表示,称为 命题符号化
简单命题的真值是确定的，因而称作 命题常项 / 命题常元 ，例如：明年10月1日是晴天
对于真值可以变化的简单陈述句，称为 命题变项/命题变元 ，例如：对于x + y > 5，当x,y的值确定后真值也就确定了
一个符号表示命题常项还是命题变项，一般由上下文决定。额外注意，命题变项不是命题
真值联结词/逻辑联结词：
| 联结词 | 符号 | 作用 |
|---|---|---|
| 否定联结词 | ¬ | 非操作 |
| 合取联结词 | ∧ | 与操作 |
| 析取联结词 | ∨ | 或操作 |
| 蕴涵联结词 | → | 前真后假时为 假 ；10->0 |
| 等值联结词 | ↔ | 前后真值相同时为 真 |
Tip
李平不是不聪明，而是不用功
\(p\)表示李平聪明，\(q\)表示李平用功，此命题用符号表示为：\(¬(¬p)∧(¬q)\)
只要天不下雨，我就骑车上班
\(p\)表示天下雨，\(q\)表示骑车上班，此命题用符号表示为\(¬p→q\)，当且仅当\(p=0,q=0\)时为 假
2 + 2 = 4当且仅当 3 不是奇数
\(p\)表示2+2=4，\(q\)表示3 是奇数，此命题用符号表示为\(p↔¬q\)，当\(p=1,q=0\)时为 真
1.2 命题公式及分类
为了更深入地研究，需要把命题常项换成命题变项，称这样的式子为 合式公式
合式公式是由命题变项、联结词、圆括号组成的字符串。有如下 定义
- 单个命题变项 \(p,q,r,...,p_i,q_i,r_i...\)是合式公式
- 如果\(A\)为合式公式，则\((¬A)\)也为合式公式
- 如果\(A、B\)为合式公式，则\((A∧B)、(A→B)、(A↔B)、(A∨B)\)都是合式公式
总而言之，“只要是由命题变项和逻辑联结词，依照形式逻辑的语法规则构成的表达式，就是合式公式。
合式公式又称命题公式，简称 公式
命题公式的层次
- 若 \(A\) 是单个命题变项，则称 \(A\) 是 0 层公式。
- 称 \(A\) 是 \(n+1\) 层公式\((n≥0)\)是指 \(A\) 符合下列情况之一：
- \(A=¬B\)，\(B\) 是 n 层公式。
- \(A=B∧C\)，其中 \(B、C\) 分别为 \(i\) 层和 \(j\) 层公式，且 \(n=max(i,j)\)
- \(A=B∨C\)，其中 \(B、C\) 的层次同
2.2。 - \(A=B→C\)，其中 \(B、C\) 的层次同
2.2。 - \(A=B ↔ C\), 其中 \(B、C\) 的层次同
2.2。
Tip
例如，\(¬p∨q，p∧q∧r，¬(¬p∧q)→(r∨s)\) 分别为2层、2层、4层命题公式。
设 \(A\) 为一个命题公式，\(p_1, p_2, …, p_n\) 为出现在 \(A\) 中的所有命题变项。给 \(p_1, p_2, …, p_n\)指定一组真值，称为对 \(A\) 的一个 赋值 或 解释 。
若指定的一组真值使 A 的值为真，则称这组真值为 A 的 成真赋值 ；若使 A 的值为假，则称这组真值为 A 的 成假赋值 。
将命题公式\(A\)在所有赋值之下取值的情况列成表，称为\(A\)的 真值表
设A为一个命题公式
- 若A在所有赋值下取值均为 真 ，则称为 重言式 / 永真式
- 若均为 假 ，则称为 矛盾式 / 永假式
- 若至少存在一组成真赋值，则称为 可满足式
1.3 等值演算
给定\(n(n≥1)\)个命题变项，可产生无穷多个命题公式，而那些具有相同真值表的命题公式便是等值演算讨论的问题。
\(n\)个命题变项只能生成\(2^{2^n}\)个真值不同的命题公式
若等价式\(A↔B\)为重言式，那么称\(A\)与\(B\)为 等值 的，记作\(A⇔B\)
等值演算法
| 定律/公式 | 逻辑等式 | 名称解释 |
|---|---|---|
| 双重否定律 | \(¬¬A ⇔ A\) | 否定两次等于没否定 |
| 幂等律 | \(A ∨ A ⇔ A\) \(A ∧ A ⇔ A\) |
同一个命题重复并无影响 |
| 交换律 | \(A ∨ B ⇔ B ∨ A\) \(A ∧ B ⇔ B ∧ A\) |
“或、与”运算交换位置不变 |
| 结合律 | \((A ∨ B) ∨ C ⇔ A ∨ (B ∨ C)\) \((A ∧ B) ∧ C ⇔ A ∧ (B ∧ C)\) |
“或、与”运算可以任意结合 |
| 分配律 | \(A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C)\) \(A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C)\) |
与、或之间可相互分配 |
| 德摩根律 | \(¬(A ∨ B) ⇔ ¬A ∧ ¬B\) \(¬(A ∧ B) ⇔ ¬A ∨ ¬B\) |
否定分配到括号内需改变运算符 |
| 吸收律 | \(A ∨ (A ∧ B) ⇔ A\) \(A ∧ (A ∨ B) ⇔ A\) |
强的条件吸收弱的条件 |
| 零律 | \(A ∨ 1 ⇔ 1\) \(A ∧ 0 ⇔ 0\) |
与“真”或得真，与“假”且得假 |
| 同一律 | \(A ∨ 0 ⇔ A\) \(A ∧ 1 ⇔ A\) |
与“假”或无效，与“真”且无效 |
| 排中律 | \(A ∨ ¬A ⇔ 1\) | 命题非真即假，必有其一 |
| 矛盾律 | \(A ∧ ¬A ⇔ 0\) | 命题不可能既真又假 |
| 蕴涵等值式 | \(A → B ⇔ ¬A ∨ B\) | “如果…那么…”等价于“非前件或后件” |
| 等价等值式 | \(A ↔ B ⇔ (A → B) ∧ (B → A)\) | 等价等于双向蕴涵 |
| 假言易位 | \(A → B ⇔ ¬B → ¬A\) | 逆否命题与原命题等价 |
| 等价否定等值式 | \(A ↔ B ⇔ ¬A ↔ ¬B\) | 命题等价则其否定也等价 |
1.4 范式
仅由有限个命题变项或其否定构成的析取式称为 简单析取式 ；类似于数电的最简或式的\(m_i\)
仅由有限个命题变项或其否定构成的合取式称为 简单合取式 ；类似于数电的最简和式\(M_i\)
仅由有限个简单析取式构成的析取式称为 析取范式
仅由有限个简单合取式构成的析取式称为 合取范式
Tip
如果公式\(A\)的析取范式中的简单合取式全是极小项，则称该析取范式为 主析取范式 ；类似于数电的最简或式
主合取范式 类似，不做赘述
1.5 联结词全功能集
设S式一个联结词集合，如果任一真值函数都可以用仅含 \(S\) 中的联结词的命题公式表示，则称 \(S\) 为 全功能集
↑称作 与非联结词 ；↓称作 或非联结词
| 联结词 | 等价 |
|---|---|
| \(p↑q\) | \(¬(p∧q)\) |
| \(p↓q\) | \(¬(p∨q)\) |
1.6 组合电路
数电已学，不加赘述
1.7 推理理论⭐
推理 是从前提推出结论的思维过程； 前提 是指已知的命题公式， 结论 是指从前提触发应用推理规则推出的命题公式。
定义如下：
Important
定义 1.20
若\((A_1 \land A_2 \land \cdots \land A_k)\ \to\ B\)为重言式，则称 \((A_1, A_2, \ldots, A_k)\) 推出结论 \(B\) 的推理 正确 ；
\(B\) 是\((A_1, A_2, \ldots, A_k)\) 的 逻辑结论 或 有效结论 。
称\((A_1 \land A_2 \land \cdots \land A_k)\ \to\ B\)为由前提 \((A_1, A_2, \ldots, A_k)\) 推出结论 \(B\)的推理的 形式结构 。
因而，若前提\(A_1,A_2,\ldots,A_k\),推出结论B的推理正确，也记作 $$ (A_1\land A_2 \land \ldots \land A_k) \Rightarrow B $$ 判断推理是否正确就是 判断一个蕴含式是否是重言式
Tip
如果我上街，我一定去新华书店。我没上街，所以我没去新华书店
设\(p\)：我上街；\(q\)：我去新华书店
前提：\(p \to q,\neg p\)
结论：\(\neg q\)
推理的形式结构为 $$ ((p \to q)\land \neg p) \to \neg q $$ 经过一系列计算，该式等价于\(p\lor \lnot q\)，非 重言式 ，即推理不正确
证明推理正确的证明方法——构造证明法
重要的 推理定律 如下：
| 定理 | 名字 | 含义解释 | 直观理解 |
|---|---|---|---|
| \((A \Rightarrow (A \lor B))\) | 附加 | 如果 (A) 成立，那么“(A) 或 (B)”也一定成立。 | “我会去图书馆 → 我会去图书馆或看电影”。 |
| \(((A \land B) \Rightarrow A)\) | 化简 | 如果 (A) 和 (B) 同时为真，那么单独 (A) 也为真。 | “我去图书馆并且下雨 → 我去图书馆”。 |
| \((((A \to B)\land A)\Rightarrow B)\) | 假言推理 | 如果“若 A 则 B”是真的，且 A 也是真的，那么可以推出 B。 | “如果下雨就带伞，并且现在下雨 → 我带伞”。 |
| \((((A \to B)\land \lnot B)\Rightarrow \lnot A)\) | 拒取式 | 如果“若 A 则 B”是真的，但 B 假了，那么 A 也一定是假。 | “如果下雨就带伞，但我没带伞 → 没下雨”。 |
| \((((A\lor B)\land \lnot A) \Rightarrow B)\) | 析取三段论 | 如果“要么 A 要么 B”，但 A 不成立，那么 B 必然成立。 | “我今天要么学习要么打游戏，我没学习 → 我打游戏”。 |
| \((((A \to B)\land(B\to C))\Rightarrow (A\to C))\) | 假言三段论 | A推出B，B推出C；那么 A 可以直接推出 C | “如果考上研究生就能进实验室，如果进实验室就能拿项目 → 考上研究生就能拿项目”。 |
| \((((A \leftrightarrow B)\land(B \leftrightarrow C))\Rightarrow(A \leftrightarrow C))\) | 等价三段论 | 如果 A 等价于 B，且 B 等价于 C，那么 A 也等价于 C。 | “A ≡ B，B ≡ C → A ≡ C”。比如“x 是偶数 ↔ x 能被 2 整除”，“x 能被 2 整除 ↔ x 的平方是偶数” → “x 是偶数 ↔ x 的平方是偶数”。 |
| \(((A \to B)\land(C\to D)\land(A\lor C)\Rightarrow (B\lor D))\) | 构造性二难 | 如果“若 A 则 B”，且“若 C 则 D”，而且我们知道“要么 A 要么 C”，那么结论就是“要么 B 要么 D”。 | “如果今天下雨就带伞，如果今天晴天就戴墨镜，而今天不是下雨就是晴天 → 我要么带伞要么戴墨镜”。 |
证明 是一个描述推理过程的命题公式序列。其中，对于每个命题公式，或者是已知的前提，或者是由前面的命题公式应用推理规则得到的结论
常用 推理规则 如下：
| 规则 | 内容说明 |
|---|---|
| 前提引入规则 | 在证明的任何一步，都可以引入前提。 |
| 结论引入规则 | 在证明的任何一步，前面已证明的结论都可作为后续证明的前提。 |
| 置换规则 | 在证明的任何步骤，命题公式中的任何子命题公式都可以用与之等值的命题公式置换。例如：可用 \((\lnot p \lor q)\) 置换 \((p \to q)\)。 |
常用 推理定律 如下
\(A_1,A_2,\ldots,A_k \vdash B\)表示\(B\)是\(A_1,A_2,\ldots,A_k\) 的逻辑结论
| 定律 | 逻辑形式 | 说明 |
|---|---|---|
| 假言推理 | \((A \to B, A \vdash B)\) | 肯前推后 |
| 附加规则 | \((A \vdash A \lor B)\) | 单命题可推出“或”命题 |
| 化简规则 | \((A \land B \vdash A)\) | 合取式可化简 |
| 拒取式 | \((A \to B, \lnot B \vdash \lnot A)\) | 否后否前 |
| 假言三段论 | \((A \to B, B \to C \vdash A \to C)\) | 链式推理 |
| 析取三段论 | \((A \lor B, \lnot A \vdash B)\) | 排除法 |
| 构造性二难 | \((A \to B, C \to D, A \lor C \vdash B \lor D)\) | 二选一推出二选一 |
| 合取引入规则 | \((A, B \vdash A \land B)\) | 单个命题可以并合 |
构造法证明常用的两种技巧
附加前提证明法
即\((A_1\land A_2\land\ldots A_k)\to(A\to B)\)转化为\((A_1\land A_2 \land \dots A_k \land A)\to B\)
原本结论中的前件\(A\)变为了前提，称\(A\)为附加前提。
如果可以证明后式为重言式，则前式也为重言式。
Tip
例1.23 用附加前提证明法证明下面推理
前提：\(p\to(q\to r),\lnot s \lor p,q\)
结论：\(s\to r\)
证明：
归谬法
由于 \(A_1,A_2,\ldots,A_n\to B \Leftrightarrow \lnot(A_1\land A_2\land \ldots \land A_n \land \lnot B)\)
那么若\(A_1,A_2,\ldots,A_n\)与\(\lnot B\)不相容，则说明\(B\)是公式\(A_1,A_2,\ldots,A_n\)的逻辑结论。
回忆：矛盾式即表明该式各元素不相容
Tip
例1.24 构造下面推理的证明
前提：\(p\to(\lnot(r\land s)\to \lnot q),p,\lnot s\)
结论：\(\lnot q\)
证明：
由⑨得出了矛盾，根据归谬法说明推理正确
1.8 题例分析
此部分略
1.9 本章小结
在本章中，我们围绕 命题逻辑 展开了系统学习，主要内容可以归纳如下：
- 命题与真值 ：理解命题的定义，区分命题常项与命题变项，并掌握命题的真值特征。
- 逻辑联结词与命题公式 ：学习否定、合取、析取、蕴涵、等值等联结词，能够构造合式公式并判定其层次。
- 等值演算与范式 ：通过等值演算，掌握常见的逻辑等值式（德摩根律、分配律等），并学习合取范式、析取范式及主范式的概念。
- 推理理论 ：明确推理的形式结构，学习常见推理定律（假言推理、拒取式、析取三段论、构造性二难等），并掌握了构造证明、归谬法等基本证明方法。
- 推理规则与证明技巧 ：熟悉前提引入、结论引入、置换规则等推理规则，能够在逻辑证明中合理运用。
二、一阶逻辑
在前一章中，我们已经系统地学习了 命题逻辑 ，它通过
命题变项与逻辑联结词的组合，为逻辑推理提供了形式化工具。然而，命题逻辑在表达能力上仍存在明显局限：它只能把“整体陈述”作为分析单位，却无法揭示陈述内部的对象与关系。例如，“所有学生都喜欢数学”与“张三喜欢数学”，在命题逻辑中仅能作为两个独立命题对待，二者之间的内在联系无法刻画。因此，我们必须引入更强大的逻辑体系—— 一阶逻辑 。一阶逻辑通过 谓词 和 量词 的引入，能够刻画个体的性质与对象间的关系，使逻辑推理从“整体真值”扩展到“对象层面”。因此， 一阶逻辑 也成为 谓词逻辑
课本中提到“苏格拉底三段论”。内容如下：
- p：凡是人都是要死的
- q：苏格拉底是人
- r：所以苏格拉底是要死的
上述推理可表示为 \((p\land q)\to r\)。此式并非 重言式 ，但在客观事实上是正确的。
根本原因是，在命题逻辑中，只能把“凡是人都是要死的”作为一个简单命题，而失去了它的内在含义。
2.1 一阶逻辑基本概念（一阶逻辑的命题符号化）
依旧从凡是人都要死的这句话入手，它分为三个部分：
- “凡是”是所有的、每个的意思
- 所有的什么呢？就是“人”这个特殊的对象
- “是要死的”是一种性质
总结来说，这句话的意思为所有的这种对象都有这种性质。而为了形式化的描述这些，一阶逻辑中引入了 量词、个体词和谓词 3个概念。量词暂时按下不表
-
个体词 ：是指可以独立存在的客体，可以是一个具体的事物，也可以是一个抽象的概念
张三、李四、人、花、自然数、\(\sqrt2\)、思想、定理等都可作为个体词
-
谓词 ：刻画个体词的性质或个体词之间关系的词
\(\sqrt2\)是无理数；张三 是程序员 ；小李 比 小赵 高2厘米
标注的地方就为谓词。前两个谓词表示个体词性质，后一个谓词表示两个个体词之间的关系
对于 个体词
-
个体常项 ：表示具体的、特定的个体。用小写字母 \(a,b,c\dots\) 表示。
-
个体变项 ：表示抽象的或泛指的个体。用小写字母 \(x, y, z, \dots\) 表示。
-
个体域（论域） ：是个体变项取值的范围。
-
可以是有限集合，如 \(\{1,2,3,4\}, \{a,b,c\}, \{计算机,2,狮子\}\)。
-
也可以是无限集合，如自然数集、实数集等。
-
全总个体域 ：如果没有特别说明，个体域默认为“宇宙间的一切事物”，称为全总个体域。
对于 谓词
-
谓词常项 ：表示具体性质或关系的谓词。用大写字母 \(F, G, H, \dots\)表示。
例：\(F(x)\) 表示“x 是无理数”。
-
谓词变项 ：表示抽象或泛指的谓词。也用大写字母 \(F,G,H,…\)表示，具体是常项还是变项需看上下文。
个人认为，这两个其实就是具体函数和抽象函数之分
-
谓词的形式
-
单个体谓词 ：一个个体变项与谓词组成，如 \(F(x)\)。
-
多元谓词 ：多个个体变项与谓词组成，如 \(L(x,y)\)，表示关系。
例：\(L(x,y)\) 可表示 “x 比 y 高 2 厘米”。
接下来，根据 包含多少个个体词 ，提出了 谓词的元数 这一概念
- 元谓词 ：谓词中包含的个体词个数称为 元数 ；含\(n(n≥1)\)个个体词的谓词叫做 \(n\)元谓词
- 其中\(n=1\)时，表示某个个体的性质；\(n≥2\)时，表示个体间的关系
Note
谓词本身不是命题
单独的谓词\(P(x_1,x_2,\ldots,x_n)\)不是命题；必须指定个体项替代个体变项才能称为命题
0元谓词
指不带个体变项的谓词；其实就是常项命题，真假值固定
总结一下：谓词按元数分为 0 元（命题）、1 元（性质）、2 元及以上（关系）。只有将个体代入谓词，才能形成命题。
Tip
例2.1 将下列命题用 0 元谓词符号化
（1）2是素数且是偶数
（2）如果2大于3，则2大于4
（3）如果A比B高，B比C高，则A比C高
解
(1)设\(F(x):x为素数\)、\(G(x):x为偶数\)、\(a:2\)
则：\(F(a)\land G(a)\)
(2)设\(L(x,y):x大于y\)、\(a:2,b:3,c:4\)
则：\(L(a,b)\to L(a,c)\)
(3)设\(H(x,y):x比y高\)、\(a:A,b:B,c:C\)
则：\(H(a,b)\land H(b,c) \to H(a,c)\)
对于 量词
全称量词 ：对应日常语言中的“一切”“所有”“任意”等词语，用 \(\forall\) 表示，\(\forall x\) 表示对个体域里的所有个体
\(\forall x F(x)\) 表示个体域里所有个体都有性质\(F\)
存在量词 ：对应日常语言中的“有一个”“存在”“至少有一个”，用 \(\exists\) 表示， \(\exists x\) 表示存在个体域里的个体
\(\exists xF(x)\) 表示存在个体域中的个体具有性质\(F\)
符号化
符号化 必须 要明确个体域，否则会出现指代不明的情况
举个例子，如下：
Note
考虑以下两个问题的符号化
(1)所有人都是要死的
(2)有的人活到百岁以上
第一种情况，考虑个体域D为人类集合
(1)\(\forall x F(x)\);其中，\(F(x)：x\)是要死的；此命题为真命题
(2)\(\exists x G(x)\);其中，\(G(x):x\)活到百岁以上；此命题为真命题
第二种情况，考虑个体域D为全总个体域
(1)不能符号化，因为这将表明宇宙间一切事物都会死，与原命题不符
(2)不能符号化，因为这将表明宇宙间的一切事物存在百岁以上，与原命题不符
补丁怎么打呢？引入一个新的谓词，将人分离出来
于是在全总个体域的情况下，以上命题可以这样叙述
(1)对所有个体而言，如果它是人，则它是要死的
(2)存在着个体，它是人并且活百岁以上
符号化如下：
增设新谓词\(M(x):x是人\)
(1)\(\forall x(M(x)\to F(x))\)
(2)\(\exists x(M(x)\land G(x))\)
这个引入的新谓词称作 特性谓词
使用量词时的注意事项
书上给出提示，在使用量词的时候，应当注意以下内容
-
在不同的个体域中，命题符号化的形式可能不一样，如上文中的例子
-
如果事先没有给出个体域，都应该以 全总个体域 为个体域
-
在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的，如上文例子
-
个体域和谓词的含义确定后，n元谓词要转化为命题至少需要n个量词
-
当个体域为有限集时，如 \(D=\{\ a_1, a_2,\ldots,a_n\}\) 由量词的意义可以卡出，对于任意的谓词 \(A(x)\) ，都有
- \(\forall xA(x)\Leftrightarrow A(a_1)\land A(a_2)\land \ldots \land A(a_n)\)
-
如 \(\exists xA(x)\Leftrightarrow A(a_1)\lor A(a_2)\lor \ldots \lor A(a_n)\)
-
多个量词同时出现的时候，不可以随意颠倒顺序，颠倒后可能与原含义不同
例如：“对任意的x，存在y，使得\(x+y=5\)” 和 “存在y，使得任意x，都有\(x+y=5\)” 天差地别
2.2 一阶逻辑合式公式及解释
上一节介绍了一阶逻辑命题符号化，本节给出一阶逻辑中合式公式的形式定义
以下定义个人认为了解即可，不必太在意
定义2.1 字母表：
- 个体常项：\(a, b, c, \cdots, a_i, b_i, c_i, \cdots, i \geq 1\)；
- 个体变项：\(x, y, z, \cdots, x_i, y_i, z_i, \cdots, i \geq 1\)；
- 函数符号：\(f, g, h, \cdots, f_i, g_i, h_i, \cdots, i \geq 1\)；
- 谓词符号：\(F, G, H, \cdots, F_i, G_i, H_i, \cdots, i \geq 1\)；
- 量词符号：\(\forall, \exists\)；
- 联结词符：\(\lnot, \land, \lor, \rightarrow, \leftrightarrow\)；
- 圆括号和逗号：\(( \ ,\ ) , \ ,\)
定义 2.2 项的递归定义：
- 个体常项和变项是项；
- 若 \(\varphi(x_{1}, x_{2}, \cdots, x_{n})\) 是任意 \(n\) 元函数，\(t_{1}, t_{2}, \cdots, t_{n}\) 是项，则 \(\varphi(t_{1}, t_{2}, \cdots, t_{n})\) 也是项；
- 只有有限次地使用 (1)、(2) 生成的符号串才是项。
例如：
- \(a, b, x, y\)
- \(f(x,y) = x + y\)
- \(g(x,y) = x - y\)
- \(h(x,y) = x \cdot y\)
等都是项。
又如：
- \(f(a, g(x,y)) = a + (x-y)\)
- \(g(h(x,y), f(a,b)) = x \cdot y - (a+b)\)
等也都是项。
定义 2.3 设 \(R(x_{1}, x_{2}, \cdots, x_{n})\) 是任意的 \(n \ (n \geq 1)\) 元谓词，\(t_{1}, t_{2}, \cdots, t_{n}\) 是项，则称 \(R(t_{1}, t_{2}, \cdots, t_{n})\) 为 原子公式 。
简单来说，就是没有经过逻辑联结词操作的公式。\(R(x,y)\)是原子公式；\(\lnot R(x,y)\)不是原子公式
定义 2.2 和定义 2.3 中的 \(\varphi\) 和 \(R\) 都不是字母表中的符号，它们分别代表任意的函数和任意的谓词，这与在第 1 章中用 \(A, B\) 等表示任意的命题公式一样。
类似于抽象函数的概念
定义 2.4 合式公式的定义如下：
- 原子公式是合式公式；
- 若 \(A\) 是合式公式，则 \((\lnot A)\) 也是合式公式；
- 若 \(A, B\) 是合式公式，则 \((A \land B), (A \lor B), (A \to B), (A \leftrightarrow B)\) 也是合式公式；
- 若 \(A\) 是合式公式，则 \(\forall x A, \ \exists x A\) 也是合式公式；
- 只有有限次地应用 (1)～(4) 构成的符号串才是合式公式。
在一阶逻辑中，合式公式又称 谓词公式 ，简称公式。为简单起见，合式公式的最外层圆括号可以省去。
定义 2.5 在合式公式 \(\forall x A\) 和 \(\exists x A\) 中，称 \(x\) 为 指导变项 ，称 \(A\) 为相应量词的 辖域 。 在辖域中，\(x\) 的所有出现称为 约束出现 （即 \(x\) 受相应量词指导变项的约束）； \(A\) 中不是约束出现的其他变项的出现称为 自由出现 。
总而言之：约束出现 = 被量词 \(\forall\) 或 \(\exists\) 控制的变量；自由出现 = 没有被量词控制的变量
例：公式：\(\forall x \ (P(x) \rightarrow Q(y))\) 其中：
- 约束变量 是\(x\)
- 辖域 是\((P(x) \rightarrow Q(y))\)
- \(x\) 在 \(P(x)\) 中是 约束出现
- \(y\) 在 \(Q(y)\) 中没有被量词约束，所以 \(y\) 是 自由出现 。
Note
⭐其中，存在一种现象：\(\exists x F(x) \land G(x,y)\)
在 \(\exists x F(x)\) 中，x是指导变项，\(\exists\) 的辖域是 \(F(x)\)，x是约束出现；\(G(x,y)\) 中，\(x、y\) 是自由出现
在整个公式中，\(x\)的第一次出现是约束出现，第二次出现是自由出现。
很容易指导，这样子的方式会产生不必要的混淆，因此提出了 换名规则 ：将指导变项及其辖域中所有约束出现替换成公式中没有出现的个体变项符号
也就是把这个重复的字母，全部换一个不一样的
比如，我们可以将上式换为：\(\exists z F(z) \land G(x,y)\)；这样就避免了出现既是约束出现又是自由出现的个体变项
定义2.6 若公式\(A\)中无自由出现的个体变项，则称\(A\)是 封闭的合式公式 ，简称为 闭式
例如：\(\forall x \ (P(x) \rightarrow Q(x,y))\)是闭式；\(\forall x \ (P(x) \rightarrow \exists y Q(x,y))\)不是闭式
在命题逻辑中，讨论公式的恒真、恒假以及可满足性等只需要考虑公式在所有可能的赋值下的取值
在一阶逻辑中为了进行类似的讨论，要给公式中出现的每个个体常项符号、函数变项符号和谓词变项符号“赋值”，这个过程叫做 解释
定义 2.7 一个解释 \(I\) 由下面 4 部分组成：
- 非空个体域 \(D\)；
- 给论及的每个个体常项符号指定一个 \(D\) 中的元素；
- 给论及的每个函数变项符号指定一个 \(D\) 上的函数；
- 给论及的每个谓词变项符号指定一个 \(D\) 上的谓词。
在使用解释 \(I\) 来解释公式 \(A\) 时： 采用指定的个体域 \(D\)； 并将 \(A\) 中的所有个体常项符号、函数变项符号、谓词变项符号分别替换成 \(I\) 指定的元素、函数及谓词。
其实简单来说，就是把式子的每个变量都给说明清楚，就是 解释
定义2.8 设 \(A\) 为一谓词公式：
- 如果 \(A\) 在任何解释和该解释下的任何赋值下都为真，则称 \(A\) 为 逻辑有效式 （或称 永真式 ）；
\(\forall x , (P(x) \lor \lnot P(x))\)
- 如果 \(A\) 在任何解释和该解释下的任何赋值下都为假，则称 \(A\) 为 矛盾式 （或称 永假式 ）；
\(\exists x , (P(x) \land \lnot P(x))\)
- 若至少存在一个解释和该解释下的一个赋值使 \(A\) 为真，则称 \(A\) 是 可满足式 。
\(\exists x , P(x)\)
定义2.9
设 \(A_{0}\) 是含命题变项 \(p_{1}, p_{2}, \cdots, p_{n}\) 的命题公式，\(A_{1}, A_{2}, \cdots, A_{n}\) 是 \(n\) 个谓词公式。 用 \(A_{i}\) 替代 \(p_{i}\)（\(1 \leq i \leq n\)），所得公式 \(A\) 称为 \(A_{0}\) 的 代换实例 。
例如： \(F(x) \to G(x)\)，\(\forall x F(x) \to \exists x G(x)\) 等都是 \(p \to q\) 的代换实例。
可以证明：
- 命题公式中的重言式的代换实例都是 永真式 ；
- 命题公式中的矛盾式的代换实例都是 矛盾式 。
就是把命题逻辑中的命题变项 \(p, q, \dots\) 用具体的一阶谓词公式替换掉。
2.3 一阶逻辑等值式与前束范式
和上一节差不多，也是一堆定理、定义、名词的堆砌
定义 2.10 设 \(A, B\) 是一阶逻辑中的两个公式，若 \(A \leftrightarrow B\) 为逻辑有效式， 则称 \(A\) 与 \(B\) 是 等值的 ，记作 \(A \Leftrightarrow B\)，称 \(A \Leftrightarrow B\) 为 等值式 。
一阶逻辑里的逻辑恒等式，无论什么情况，均等价 使用换名规则所得公式与原公式等值
一些重要等值式
| 名字 | 等值式 | 说明 |
|---|---|---|
| 量词否定等值式 | (1) \(\lnot \forall x A(x) \Leftrightarrow \exists x \lnot A(x)\) (2) \(\lnot \exists x A(x) \Leftrightarrow \forall x \lnot A(x)\) |
量词对偶律 |
| 量词辖域收缩与扩张等值式 | (1) ① \(\forall x (A(x) \lor B) \Leftrightarrow \forall x A(x) \lor B\) ② \(\forall x (A(x) \land B) \Leftrightarrow \forall x A(x) \land B\) ③ \(\forall x (A(x) \to B) \Leftrightarrow \exists x A(x) \to B\) ④ \(\forall x (B \to A(x)) \Leftrightarrow B \to \forall x A(x)\) (2) ① \(\exists x (A(x) \lor B) \Leftrightarrow \exists x A(x) \lor B\) ② \(\exists x (A(x) \land B) \Leftrightarrow \exists x A(x) \land B\) ③ \(\exists x (A(x) \to B) \Leftrightarrow \forall x A(x) \to B\) ④ \(\exists x (B \to A(x)) \Leftrightarrow B \to \exists x A(x)\) |
将量词从辖域中移出或移入，前提：\(B\) 中不含 \(x\) 的自由出现 |
| 量词分配等值式 | (1) \(\forall x (A(x) \land B(x)) \Leftrightarrow \forall x A(x) \land \forall x B(x)\) (2) \(\exists x (A(x) \lor B(x)) \Leftrightarrow \exists x A(x) \lor \exists x B(x)\) |
(1) 称为“\(\forall\) 对 \(\land\) 的分配” (2) 称为“\(\exists\) 对 \(\lor\) 的分配” |
| 量词交换等值式 | (1) \(\forall x \forall y \, A(x,y) \Leftrightarrow \forall y \forall x \, A(x,y)\) (2) \(\exists x \exists y \, A(x,y) \Leftrightarrow \exists y \exists x \, A(x,y)\) |
量词的次序可交换（同类量词之间） |
定义 2.11 设 \(A\) 为一谓词公式，如果 \(A\) 具有如下形式： \(Q_{1}x_{1} Q_{2}x_{2} \cdots Q_{k}x_{k} B\)则称 \(A\) 是 前束范式 ，其中 \(Q_{i}\)（\(1 \leq i \leq k\)）为 \(\forall\) 或 \(\exists\)， \(B\) 为不含量词的谓词公式。
例如：\(\forall x \exists y \, (F(x,y) \to G(x,y))\)、\(\exists x \forall y \forall z \, (F(x,y,z) \to G(x,y,t))\) 都是 前束范式 。
而\(\forall x F(x,y) \land \forall x G(x,y)\)、\(\forall x (F(x) \to \forall y (G(y) \to H(x)))\) 都 不是前束范式 。
此外，在一阶逻辑中， 任何合式公式 \(A\) 都存在与其等值的前束范式 ，称这样的前束范式为公式 \(A\) 的前束范式。
简单来说， 前束范式 = 所有量词都移到公式最前面，剩下的部分不含量词。