狭谓词演算的出发点
(一)初始符号
- 甲：变项
- 命题变项：小写拉丁字母
- $p, q, r, s, p_1, q_1, r_1, s_1, p_2, …$
- 个体变项：小写拉丁字母
- $u, v, w, x, y, z, u_1, v_1, …$
- 谓词变项：大写拉丁字母
- $F, G, H, P, Q, R, S, F_1, G_1, …$
乙：常项
- 命题联结词：¬，并非；$\bigvee$，或者
- 量词：(.x.x.)，全称；($\exists .x.x.$)，存在
丙：括号和逗点
- 左括号 “(”；右括号 “)”；逗点 “,”
有意义的符号序列是系统里的合式公式
合式公式(简称公式)是演算里的命题形式
语法符号
- 小写希腊字母 $\pi$，代表任一命题变项
- 大写希腊字母 $\Delta$，代表任一个体变项
- 大写希腊字母 $\Gama$
- 大写拉丁字母 $X, Y, Z$，代表任一符号序列
- 大写拉丁字母 $A, B, C, D, E$ 等，代表任一合式公式1
(二)形成规则
- 两个语法概念
- $\Delta$ 在X中是约束的当且仅当 $(\Delta)$ 或 $(\exists \Delta)$ 在X中出现
- $\Delta$ 在X中是自由的当且仅当 $\Delta$ 在X中出现并且 $\Delta$ 在X中不是约束的
狭谓词演算的形成规则有六条：
甲：一命题变项 $\pi$ 是一合式公式
乙：一谓词变项 $\Gama$ 后继有写在一堆括号内并用逗点分开的适当数目的个体变项是一合式公式
丙：若 $X$ 是合式公式，则 $¬X$ 是合式公式
丁：若 $X$和$Y$ 是合式公式，并且无一个体变项 $\Delta$，此 $\Delta$ 在二者之一中是约束的但在另一个中是自由的，则 $(X \bigvee Y)$ 是合式公式
戊：若 $X$ 为一合式公式并且 $\Delta$ 在其中是自由的，则 $(\Delta)X$ 和 $(\exists \Delta)X$ 是合式公式
己：只有适合以上各条的是合式公式
形成规则的制定要满足：
- 经过解释后合式公式是有意义的
- 公式的涵义是唯一的
丁条排除了一个个体变项在一公式的一部分是约束的但在另一部分是自由的这种情况
戊条排除了空的约束和重复的约束
量词的辖域：量词后面最短的合式公式
约束变量：变量的约束出现
- 变项 $\Delta$ 在公式的某一位置上约束出现当且仅当
- 在量词 $(.x.x.)$ 或 $(\exists .x.x.)$ 之中
- 在量词 $(\Delta)$ 或 $(\exists \Delta)$ 的辖域之中
自由变项：变项的自由出现
- 不是约束出现
(三)定义
- 甲：$(A \rightarrow B)$ 定义为 $(¬A \bigvee B)$
- 乙：$(A \bigwedge B)$ 定义为 $¬(¬A \bigvee ¬B)$
- 丙：$(A \leftrightarrow B)$ 定义为 $((A \rightarrow B) \bigwedge (B \rightarrow A))$
引入否定和析取以外的三个联结词
(四)公理
- (1) $├ ((p \bigvee p) \rightarrow p)$
- (2) $├ (p \rightarrow (p \bigvee q))$
- (3) $├ ((p \bigvee q) \rightarrow (q \bigvee p))$
- (4) $├ ((q \rightarrow r) \rightarrow ((p \bigvee q) \rightarrow (p \bigvee r)))$
- (5) $├ ((x)F(x) \rightarrow F(y))$
- (6) $├ (F(y) \rightarrow (\exists x)F(x))$
谓词演算的括号省略规则和命题演算是相同的
(五)变形规则
- 代入规则两个要求：
- 对一合式公式作代入的结果必须仍是一个合式公式
- 从普遍有效式出发，代入的结果必须还是普遍有效的
三条代入规则：
甲：命题变项代入规则
- 在公式A中出现的命题变项 $\pi$ 可由一公式B代入
- 代入必须在 $\pi$ 出现的一切位置上进行；代入结果可记为 $A \frac{\pi}{B}$
- 如果 $├ A$，则 $├ A \frac{\pi}{B}$
- 对B的要求：
- 若 $\Delta$ 在A中为自由变项，则B不得含有约束变现 $\Delta$
- 若 $\Delta$ 在A中为约束变项，则B不得含有自由变项 $\Delta$
- 若 $\Delta$ 在A中为约束变项且$\pi$又在$(\Delta)$或$(\exists \Delta)$的辖域中，则B中不得有约束变项 $\Delta$
三个要求都是为了避免代入的结果不合式；第二条保持普遍有效性
- 乙：自由个体变项代入规则
- 公式A中的自由个体变项 $\Delta_1$ 可由另一个体变项 $\Delta_2$ 代入
- 代入必须在 $\Delta_1$ 出现的一切位置上进行；代入结果可记为 $A \frac{\Delta_1}{\Delta_2}$
- 如果 $├ A$，则 $A \frac{\Delta_1}{\Delta_2}$
- 代入的要求：$\Delta_2$ 在A中不作为约束变项出现
- 保证代入结果合式和普遍有效性
丙：谓词变项代入规则
- 概念：
- 目式：在一n元谓词变项后面由n个个体变项组成的n元组是此谓词的目式
- 如 $R(x, y)$ 目式为 $(x, y)$
- 名式：表示一谓词的结构
- 同一谓词变项的不同出现可以跟随不同的目式，用语法变项n元谓词可写作 $R(\Delta_1, \Delta_2, …, \Delta_n)$
- 复合谓词：
- 含有自由个体变项的合式公式，其值随自由变项之值而定，此公式可看作其中某些个体变项的谓词，即复合谓词
- 语法符号：n元复合谓词 $B(\Delta_1, \Delta_2, …, \Delta_n)$, (n > 0); 其中自由个体变项不必不相同也不必按序出现
- 谓词代入规则：一公式A中的n元谓词变项 $\Gama(\Delta_1, \Delta_2, …, \Delta_n)$ 可处处代之以一复合谓词 $B(\Delta_1, \Delta_2, …, \Deltan, \Delta{n+1}, …, \Delta_{n+m}), (m > 0)$
- 代入结果可记为：$A \frac{$\Gama(\Delta_1, \Delta_2, …, \Delta_n)$}{$B(\Delta_1, \Delta_2, …, \Deltan, \Delta{n+1}, …, \Delta_{n+m})$}$
- 如果 $├ A$，则 $├ A \frac{$\Gama(\Delta_1, \Delta_2, …, \Delta_n)$}{$B(\Delta_1, \Delta_2, …, \Deltan, \Delta{n+1}, …, \Delta_{n+m})$}$
- 谓词代入要求：
- 代入结果必须是合式的
- A中的自由个体变项在代入后不得为B中的量词所约束
- 如果m > 0，$B(\Delta_1, \Delta_2, …, \Deltan, \Delta{n+1}, …, \Delta{n+m}), (m > 0)$ 中的变项 $\Delta{n+1}, …, \Delta_{n+m}$ 等在代入后不得为A中原有的量词所约束
丁：分离规则
- 从 $├ A$ 和 $├ A \rightarrow B$，可得 $├ B$
- 承认前件的假言推理
戊：后件概括规则
- 如果 $\Delta$ 在A中不出现，从 $├ A \rightarrow B(\Delta)$ 可得 $├ A \rightarrow (\Delta)B(\Delta)$
- 引入全称量词的规则
- 以下图式的推广
图式(n是有限的)：
$├ A \rightarrow B_1$
$├ A \rightarrow B_2$
…$├ A \rightarrow B_n$
$├ A \rightarrow B_1 \bigwedge B_2 \bigwedge … \bigwedge B_n$
- 己：前件存在规则
- 如果 $\Delta$ 在B中不出现，从 $├ A(\Delta) \rightarrow B$ 可得 $├ (\exists \Delta)A(\Delta) \rightarrow B$
图式(n是有限的)
$├ A_1 \rightarrow B$
$├ A_2 \rightarrow B$
…$├ A_n \rightarrow B$
$├ A_1 \bigvee A_2 \bigvee … \bigvee A_n \rightarrow B$
- 庚：约束个体变项易字规则
- 公式A中的一约束个体变项 $\Delta_1$，可由另一个体变项 $\Delta_2$ 替换
- 替换必须在一特定量词及其辖域内到处实现；若 $\Delta_1$在多个量词内出现，替换可以只在一量词及其辖域内进行，也可以在几个辖域内同时进行
- 替换的要求
- $\Delta_2$ 在A中不能作自由变项出现
- 若 $\Delta_2$ 在A中约束，则被替换的 $\Delta_1$ 不能在 $\Delta_2$ 的辖域中出现
辛：定义置换规则
- 定义的左右两方可以互相置换
定理的推演 语法规则 基本置换定理
命题演算是谓词演算的一个子系统
命题演算的出发点是谓词演算出发点的一部分
命题演算的定理也都是谓词演算的定理
- 定理101：$├ (x)(F(x) \bigvee ¬F(x))$
- 排中律
- 对一切x，x是F或者不是F
推演规则101 概括规则：从 $├ A(x)$，其中x自由出现，可得 $├ (x)A(x)$
- 定理102：$├ (x)F(x) \rightarrow (\exists x)F(x)$
- 如果一切个体都是F，那么有个体是F
- 全称蕴涵存在
定理103：$├ (x)(F(x) \bigwedge G(x)) \rightarrow (x)F(x) \bigwedge (x)G(x)$
定理104：$├ (x)F(x) \bigwedge (x)G(x) \rightarrow (x)(F(x) \bigwedge G(x))$
定理105：$├ (x)(F(x) \bigwedge G(x)) \leftrightarrow (x)F(x) \bigwedge (x)G(x)$
- 全称量词对于合取的分配律
定理106：$├ (x)(F(x) \rightarrow G(x)) \rightarrow ((x)F(x) \rightarrow (x)G(x))$
- 全称量词对于蕴涵的分配律
定理107：$├ (x)(F(x) \leftrightarrow G(x)) \rightarrow ((x)F(x) \leftrightarrow (x)G(x))$
- 全称量词对于等值的分配率
定理108：$├ (x)F(x) \bigvee (x)G(x) \rightarrow (x)(F(x) \bigvee G(x))$
- 关于全称量词对于析取能否分配的定理；逆命题不成立
定理109：$├ (\exists x)F(x) \leftrightarrow ¬(x)¬F(x)$
定理110：$├ (\exists x)¬F(x) \leftrightarrow ¬(x)F(x)$
定理111：$├ ¬(\exists x)¬F(x) \leftrightarrow (x)F(x)$
定理112：$¬(\exists x)F(x) \leftrightarrow (x)¬F(x)$
- 全称量词和存在量词的相互关系：
- 全称量词可以用存在量词和否定来定义
- 存在量词也可用全称量词和否定来定义
定理113：$├ (x)(F(x) \rightarrow G(x)) \rightarrow ((\exists x)F(x) \rightarrow (\exists x)G(x))$
- 如果凡F都是G，那么有F就有G
定理114：$├ (x)(F(x) \leftrightarrow G(x)) \rightarrow ((\exists x)F(x) \leftrightarrow (\exists x)G(x))$
- 如果F等值于G，那么有F等值于有G
推演规则102 谓词演算的基本置换定理
- 设
- $A(\Delta_1, …, \Delta_n)$ 和 $B(\Delta_1, …, \Delta_n)$ 为谓词演算的两个公式，其中除 $\Delta_1, …, \Delta_n$ 外无其它自由个体变项
- $\Phi(A)$ 为谓词演算的一合式公式，以B置换 $\Phi(A)$ 中的A得 $\Phi(B)$，$\Phi(B)$ 仍为一合式公式
- 如果 $├ A(\Delta_1, …, \Delta_n) \leftrightarrow B(\Delta_1, …, \Delta_n)$，则 $├ \Phi(A) \leftrightarrow \Phi(B)$
定理115：$├ (x)(p \bigvee F(x)) \rightarrow p \bigvee (x)F(x)$
定理116：$├ p \bigvee (x)F(x) \leftrightarrow (x)(p \bigvee F(x))$
定理117：$├ (x)(p \bigvee F(x)) \leftrightarrow p \bigvee (x)F(x)$
- 量词转置规律：全称量词对于析取的移置律
定理118：$├ (x)(p \bigwedge F(x)) \rightarrow p \bigwedge (x)F(x)$
定理119：$├ p \bigwedge (x)F(x) \rightarrow (x)(p \bigwedge F(x))$
定理120：$├ (x)(p \bigwedge F(x)) \leftrightarrow p \bigwedge (x)F(x)$
- 全称量词对于合取的移置律
定理121：$├ (x)(p \rightarrow F(x)) \leftrightarrow p \rightarrow (x)F(x)$
- 全称量词对于蕴涵的移置律
定理122：$├ (x)(F(x) \rightarrow p) \leftrightarrow (\exists x)F(x) \rightarrow p$
- 量词转移律：全称转换为存在
定理123：$├ (x)(y)R(x, y) \leftrightarrow (y)(x)R(x, y)$
- 全称量词的交换律：两个连接的全称量词可以任意交换，不影响公式真值
定理124：$├ (\exists x)(y)R(x, y) \rightarrow (y)(\exists x)R(x, y)$
- 重迭量词的特征；逆命题不真
定理125：$├ (x)(y)R(x, y) \rightarrow (x)R(x, x)$
推演规则103 谓词演算的求否定规则
- 设E为谓词演算的公式，其中 $\rightarrow$ 和 $\leftrightarrow$ 不出现
- E的否定式 $E^{-}$ 可用以下方法直接求得
- $\bigvee$ 被代以 $\bigwedge$
- $\bigwedge$ 被代以 $\bigvee$
- $(\Delta)$ 被代以 $(\exists \Delta)$
- $(\exists \Delta)$ 被代以 $(\Delta)$
- $¬\pi$ 被代以 $\pi$；$¬ \Gama(\Delta_1, …, \Delta_n)$ 被代以 $\Gama(\Delta_1, …, \Delta_n)$
- 不出现于部分合式公式 $¬ \pi$ 中的 $\pi$ 被代以 $¬ \pi$；不出现于部分合式公式 $¬ \Gama$ 中的 $\Gama(\Delta_1, …, \Delta_n)$ 被代以 $¬ \Gama(\Delta_1, …, \Delta_n)$
推演规则104 对偶规则
- 设A和B为谓词演算两个公式，$A^{}$ 和 $B^{}$ 是在A和B中
- 把 $\bigvee$ 和 $\bigwedge$
- 把 $(\Delta)$ 和 $(\exists \Delta)$ 互换
- 的结果，则
- 甲：从 $├ A \leftrightarrow B$，可得 $├ A^{} \leftrightarrow B^{}$
- 乙：从 $├ A \rightarrow B$，可得 $├ B^{} \rightarrow A^{}$
定理126：$├ (\exists x)(F(x) \bigvee G(x)) \leftrightarrow (\exists x)F(x) \bigvee (\exists x)G(x)$
定理127：$├ (\exists x)(F(x) \bigwedge G(x)) \rightarrow (\exists x)F(x) \bigwedge (\exists x)G(x)$
定理128：$├ (\exists x)(p \bigwedge F(x)) \leftrightarrow p \bigwedge (\exists x)F(x)$
定理129：$├ (\exists x)(p \bigvee F(x)) \leftrightarrow p \bigvee (\exists x)F(x)$
定理130：$├ (\exists x)(\exists y)R(x, y) \leftrightarrow (\exists y)(\exists x)R(x, y)$
定理131：$├ (\exists x)R(x, x) \rightarrow (\exists x)(\exists y)R(x, y)$
引用
- 《数理逻辑引论》，王宪钧，北京大学出版社