命题演算

将重言式穷尽无遗地包括在一个整体(如公理系统)之内

公理系统和形式系统

公理系统：从一些公理出发根据演绎法推导出一系列定理形成的演绎系统

• 严格性：推理所遵循的规则必须是已经给出且十分明确的，没有不按已给定的规则而进行的推演，证明过程不得不自觉地附加上其它的前提或隐含的前提

• 现代公理系统选定公理时所依据的标准是能够充分地确定所处理的食物的特征，不会导致矛盾；真实性不必比由之导出的定理更为明显、直接

命题演算：命题逻辑的重言式所组成的公理系统

• 从一些作为初始命题的重言式出发，应用明确规定的推演规则，进而推导出一系列重言式的演绎体系

• 使用了表意的符号语言，完全形式化，是一个形式系统

形式系统：完全形式化了的公理系统

• 各种初始符号：是一个形式系统的字母，经解释后其中一部分是初始概念

• 形成规则：解释后有意义的符号序列称为合式的，合式公式/语句

• 公理(初始语句)

• 变形规则：规定如何从公理和已经推导出的一个或几个公式经过符号变换而推导出另一个公式(定理)

• 需要机械的方法(每一步都是按照某种事先给出的规则明确的而且在有穷步骤内能完成的方法)判定：

• • 任一符号是否为一初始符号
• • 任一符号序列是否合式
• • 任一公式是否为一公理
• • 任一公式是否能从给定公式根据变形规则得到
• • 任一有穷长的公式序列是否为一证明

语法与语义

• 研讨一个形式系统时处理的是语言和符号，讨论这种语言是也要使用语言
• • 对象语言：被讨论的语言(某种特定的人为的符号语言)
• • 语法语言(元语言)：讨论时所使用的语言

语法语言可以是自然语言，也可以是某种特定的科学技术语言

• 语法定理：用语法语言陈述的定理

• 语法理论：用语法语言所讲的关于对象语言的理论，简称语法

• 语义理论(语义学)：关于语言符号的意义和公式的真假的理论

命题演算的出发点

命题演算的初始概念主要是一些真值联结词，公理和定理都是重言式，所使用的推演方法是演绎法

语法

• 初始符号：

• 甲类：p, q, r, s, p_1, q_1, r_1, s_1, p_2, …

• 乙类：$¬$, $ \bigvee $

• 丙类：$($, $)$

• 1. 小写字母 $\pi$，语法变项，值为任一甲类符号
• 1. 大写拉丁字母 $X$, $Y$, $Z$，语法变项，值为任一符号序列
• 1. 大写拉丁字母 $A$, $B$, $C$, $D$, $E$，语法变项，值为任一合式的符号序列
• 1. 语法符号 $├$，表示紧接在后的公式是本系统所要肯定的

• 形成规则：

• 甲：一甲类符号 $\pi$ 是一合式公式

• 乙：如符号序列 $X$ 是合式公式，则 $¬X$ 是合式公式
• 丙：如符号序列 $X$ 和 $Y$ 是合式公式，则 $(X \bigvee Y)$ 是合式公式

• 丁：只有符合以上三条的符号序列才是合式公式

• 定义：

• 定义甲：$(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)))$

• 变形规则：

• 甲：代入规则，将合式公式A中出现的某一甲类符号 $\pi$ 处处都代以某一合式公式B，得到的合式公式 $A \frac{\pi}{B}$，称为代入

• • 由 $├ A$ 可得 $├ A \frac{\pi}{B}$

• 乙：分离规则，从 $├A$ 和 $├ (¬A \bigvee B)$ 可得 $├B$

• 丙：定义置换规则，定义的左右两方可互相替换

• 括号省略规则(一)：

• 甲：最外面的一对括号可以省略

• 乙：真值联结项的结合力可依次序递增：$\leftrightarrow$, $\rightarrow$, $\bigwedge$, $\bigvee$

语义

• 符号的解释

• 甲：甲类符号是命题变项

• 乙：乙类符号是真值联结词

• 丙：丙类符号是左、右符号

• 初始符号：

• 初始符号相当于自然语言里的字母(字母加下标)

• 形成规则：

• 初始符号的各种组合称为符号序列

• 合乎规则的符号序列称为合式的公式，简称公式

• • 经过解释后，合式公式是有意义的符号序列

• 形成规则实际上是合式公式的定义；根据甲、乙和丙三条构造起来的都是合式的，丁条说明只有只有符合甲、乙和丙三条的符号序列才是合式公式

• • 给定一符号序列，根据形成规则总可以在有穷步骤之内判定是不是合式的

• 定义：

• 除了初始符号外可以通过定义引入新的符号，如 $\rightarrow$, $\bigwedge$, $\leftrightarrow$

• 新符号的引入起着缩写和简化表达方式的作用(有助于思维)

• 新符号的引入也是概念的引入和分析(如真值蕴含与合取，虽不是初始符号却很重要)

• 定义是形成规则的补充

• • 具有 $A \rightarrow B$、$A \bigwedge B$、$A \leftrightarrow B$的形式的符号序列都是合式的(是合乎形成规则公式的另一种表达方式)

• 公理：

• (重言律)$((p \bigvee p) \rightarrow p)$：如果p或p是真的，那么p就是真的

• ($\bigvee$引入律)$(p \rightarrow (p \bigvee q))$：如果p是真的，那么p或q就是真的
• (析取交换律)$((p \bigvee q) \rightarrow (q \bigvee p))$：表示析取的左右两方可以互相交换，真值相等

• $((q \rightarrow r) \rightarrow ((p \bigvee q) \rightarrow (p \bigvee r)))$：如果一蕴涵式 $q \rightarrow r$ 是真的，那么 $(p \bigvee q) \rightarrow (p \bigvee r)$ 也是真的

• 变形规则：

• 从思维方面，公理系统里的推导是演绎；从符号方面，推导是符号序列的变换

• 代入规则

• • 只有命题变项p, q, r, s等才能被代入，其它多于一个符号的公式不能被代入；对于代入的公式B没有限制
• • 一个出现不止一次的变项代入时处处都用同一公式B代入
• 分离规则
• • 承认前件的假言推理
• 定义置换规律
• • 定义的左右双方真值相同，可以相互替换是很明显的
• • 两个公式的真值相等时才能相互置换

• 符号省略规则：

• 省略一些括号以简化

定理的推演

• 定理1(假言三段论/三段论原则)：$├ (q \rightarrow r) \rightarrow ((p \rightarrow q) \rightarrow (p \rightarrow r))$

• 定理2(同一原则)：$├ p \rightarrow p$

• 定理3(排中律)：$├ ¬p \bigvee p$

• 定理4(排中律)：$├ p \bigvee ¬p$

• 定理5(双重否定原则)：$├ p \rightarrow ¬¬p$

• 定理6：$├ ¬¬p \rightarrow p$

• 定理7(假言易位原则)：$├ (p \rightarrow q) \rightarrow (¬q \rightarrow ¬p)$

• 定理8(合取否定式的德摩根定理)：$├ ¬(p \bigwedge q) \rightarrow ¬p \bigvee ¬q$

• 定理9：$├ ¬p \bigvee ¬q \rightarrow ¬(p \bigwedge q)$

证明的简化 关于证明的语法规则

证明的定义：一个有穷的公式序列，其中每一公式都适合以下条件

1. 是一公理

2. 是一已证的定理

3. 由本序列里次序在前的一个公式经过代入或经过定义的置换得到

4. 由本序列里次序在前的前两个公式经过分离得到

5. 最后一个公式是所要证明的定理

• 推演的语法规则：

• 依以上定义写出的证明过于冗长

• 证明时常是简化了的，简化的根据是已证的定理和和变形规则，简化的结果是一些推演的语法规则

• 推演规则1(析取交换)：从 $├ A \bigvee B$，可得$├ B \bigvee A$

• 推演规则2(附加)：从 $├ B \rightarrow C$，可得 $├ A \bigvee B \rightarrow A \bigvee C$

• 推演规则3(三段论)：从 $├ B \rightarrow C$ 和 $├ A \rightarrow B$，可得 $├ A \rightarrow C$

• 推演规则4(假言易位)：从 $├ A \rightarrow B$，可得 $├ ¬B \rightarrow ¬A$

• 推演规则5 基本置换规则：设已证 $├ A \rightarrow B$ 和 $├ B \rightarrow A$，并且以公式B置换 $\Phi (A)$ 中的公式A得 $\Phi (B)$，则可得 $├ \Phi(A) \rightarrow \Phi(B)$ 和 $├ \Phi(B) \rightarrow \Phi(A)$，因之，从 $├ \Phi(A)$ 可得 $├ \Phi(B)$

定理的推演(Continue)

• 定理10：$├ p \rightarrow q \bigvee p$

• 定理11：$├ ¬(p \bigvee q) \rightarrow ¬p \bigwedge ¬q$

• 定理12：$├ ¬p \bigwedge ¬q \rightarrow ¬(p \bigvee q)$

• 定理13：$├ p \bigwedge q \rightarrow q \bigwedge p$

• 定理14：$├ p \bigwedge q \rightarrow p$

• 定理15：$├ p \bigwedge q \rightarrow q$

• 定理16：$├ p \bigvee (q \bigvee r) \rightarrow q \bigvee (p \bigvee r)$

• 定理17：$├ p \bigvee (q \bigvee r) \rightarrow (p \bigvee q) \bigvee r$

• 定理18：$├ (p \bigvee q) \bigvee r \rightarrow p \bigvee (q \bigvee r)$

• 定理19：$├ p \bigwedge (q \bigwedge r) \rightarrow (p \bigwedge q) \bigwedge r$

• 定理20：$├ (p \bigwedge q) \bigwedge r \rightarrow p \bigwedge (q \bigwedge r)$

• 括号省略规则(二 结合括号的省略)：

• 根据 $\bigvee$ 和 $\bigwedge$ 的结合律，结合的次序和真值无关

• $(A_1 \bigvee … \bigvee An) \bigvee A{n+1}$ 可写作 $A_1 \bigvee … \bigvee An \bigvee A{n+1}$

• 对 $\bigwedge$ 可作同样的省略

• 定理21：$├ p \rightarrow (q \rightarrow p \bigwedge q)$

• 定理22(条件互易原则)：$├ (p \rightarrow (q \rightarrow r) \rightarrow (q \rightarrow (p \rightarrow r)))$

• 定理23(条件合取原则)：$├ (p \rightarrow (q \rightarrow r)) \rightarrow (p \bigwedge q \rightarrow r)$

• 定理24：$├ (p \bigwedge q \rightarrow r) \rightarrow (p \rightarrow (q \rightarrow r))$

• 定理25(条件融合原则)：$├ (p \rightarrow (p \rightarrow q)) \rightarrow (p \rightarrow q)$

• 定理26：$├ (p \rightarrow q) \rightarrow (p \rightarrow (p \rightarrow q))$

• 定理27(分配律)：$├ p \bigvee (q \bigwedge r) \rightarrow (p \bigvee q) \bigwedge (p \bigvee r)$

• 定理28：$├ p \bigvee q \bigwedge p \bigvee r \rightarrow p \bigvee (q \bigwedge r)$

• 定理29：$├ p \bigwedge q \bigvee r \rightarrow (p \bigwedge q) \bigvee (p \bigwedge r)$

• 定理30：$├ (p \bigwedge q) \bigvee (p \bigwedge r) \rightarrow p \bigwedge (q \bigvee r)$

• 定理31：$├ (p \rightarrow q) \bigwedge (p \rightarrow r) \rightarrow (p \rightarrow q \bigwedge r)$

• 推演规则6(等值构成规则)：从 $├ A \rightarrow B$ 和 $├ B \rightarrow A$ 可得 $├ A \leftrightarrow B$

• 定理32：$├ p \leftrightarrow ¬¬p$

• 定理33：$├ ¬(p \bigvee q) \leftrightarrow ¬p \bigwedge ¬q$

• 定理34：$├ ¬(p \bigwedge q) \leftrightarrow ¬p \bigvee ¬q$

• 定理35：$├ p \leftrightarrow p$

• 定理36：$├ (p \leftarrow q) \leftrightarrow (¬p \bigvee q)$

• 定理37：$├ (p \leftrightarrow q) \leftrightarrow (¬p \bigvee q) \bigwedge (¬q \bigvee p)$

• 定理38：$├ (p \leftrightarrow q) \rightarrow (¬p \leftrightarrow ¬q)$

求否定规则 对偶规则

• 求否定规则给出如何直接求一公式的否定式的方法
• • 用一公式的右上角加“-”的方法表示此公式的否定式
• • 根据等值式 $A \rightarrow B \leftrightarrow ¬A \bigvee B$ 和 $(A \leftrightarrow B) \leftrightarrow (¬A \bigvee B) \bigwedge (A \bigvee ¬B)$ 通过置换将 $\rightarrow$ 或 $\leftrightarrow$ 消去(假定讨论的命题公式无此二符号)

• 推演规则7(求否定规则)：

• • 设 $E$ 为一公式，在其中 $\rightarrow$ 和 $\leftrightarrow$ 不出现
• • 其否定式 $E^{-}$ 可用以下方法直接得到
• • (1) $\bigvee$ 被代以 $\bigwedge$
• • (2) $\bigwedge$ 被代以 $\bigvee$
• • (3) 不出现于部分公式 $¬ \pi$ 中的 $\pi$ 被代以 $¬ \pi$
• • (4) $¬ \pi$ 被代以 $\pi$
• • 例：公式 $(p \bigwedge ¬q) \bigvee r$ 的否定式是 $(¬p \bigvee q) \bigwedge ¬r$

• 对偶规则是推演规则；命题演算 $\bigvee$ 和 $\bigwedge$ 是对偶的，满足：

• • 可交换
• • 可结合
• • $\bigvee$ 对于 $\bigwedge$ 可分配，$\bigwedge$ 对于 $\bigvee$也可分配

• 可以从一个已证定理直接得到其对偶定理

• 推演规则8(对偶规则)：

• • 设 $A$、$B$为两个公式，在其中 $\rightarrow$ 和 $\leftrightarrow$ 不出现
• • $A^{}$ 和 $B^{}$ 是在 $A$ 和 $B$ 中把 $\bigvee$ 和 $\bigwedge$ 互换的结果，有
• • 甲：从 $├ A \rightarrow B$ 可得 $├ B^{} \rightarrow A^{}$
• • 乙：从 $├ A \leftrightarrow B$ 可得 $├ A^{} \leftrightarrow B^{}$

• 定理39：$├ p \leftrightarrow p \bigwedge (q \bigvee ¬q)$

• 定理40：$├ p \leftrightarrow p \bigvee (q \bigwedge ¬q)$

• 定理41：$├ p \rightarrow (q \rightarrow p)$

• 定理42：$├ p \leftrightarrow p \bigwedge (q \bigvee ¬q \bigvee r)$

• 定理43：$├ p \leftrightarrow p \bigvee (q \bigwedge ¬q \bigwedge r)$

• 定理44：$├ (p \leftrightarrow q) \leftrightarrow (p \bigwedge q) \bigvee (¬p \bigwedge ¬q)$

---

引用

1. 《数理逻辑引论》，王宪钧，北京大学出版社