第 一 篇 数 理 逻 辑

数理逻辑（mathematical logic） 是用数学的方法来研究人类推理过程的一门数学学科。 其显著特征是符号化和形式化， 即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划, 并基于符号串形式的演算来描述推 理过程的一般规律。 又称符号逻辑、现代逻辑。 逻辑演算四个分支： 公理集合论、证明论、模型论和递归论。

第 一 章 命题演算及其形式系统

第一章 命题演算及其形式系统 1.1 命题与联结词 1.2 重 言 式 1.3 范式 * 1.4 命题演算形式系统

第一章 命题演算及其形式系统 1.1.2 联结词 1.1.3 命题公式及其真值表 1.1.4 语句的形式化 1.1 命题与联结词 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.1 命题 1.1.2 联结词 1.1.3 命题公式及其真值表 1.1.4 语句的形式化

第一章 命题演算及其形式系统 1.2 重 言 式 1.2.1 重言式概念 1.2.2 逻辑等价式和逻辑蕴涵式 △1.2.3 对偶原理

第一章 命题演算及其形式系统 1.3.1 析取范式和合取范式 1.3.2 主析取范式与主合取范式 △1.3.3 联结词的扩充与归约 第一章 命题演算及其形式系统 1.3 范式 1.3.1 析取范式和合取范式 1.3.2 主析取范式与主合取范式 △1.3.3 联结词的扩充与归约

第一章 命题演算及其形式系统 1.4.1 证明、演绎和推理 △1.4.2 命题演算形式系统PC 1.4.3 自然推理系统ND 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.1 证明、演绎和推理 △1.4.2 命题演算形式系统PC 1.4.3 自然推理系统ND

第一章 命题演算及其形式系统 称作命题（propositions or statements） 当判断正确或符合客观实际时， 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.1 命题 我们把对确定的对象作出判断的陈述句 称作命题（propositions or statements） 当判断正确或符合客观实际时， 称该命题真（true）， 否则称该命题假（false）。

第一章 命题演算及其形式系统 称为原子命题或原子（atoms） 把由原子命题和逻辑联结词共同组成的 命题称为复合命题（compositive 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.1 命题 通常把不含有逻辑联结词的命题 称为原子命题或原子（atoms） 把由原子命题和逻辑联结词共同组成的 命题称为复合命题（compositive propositions or compound statements）

第一章 命题演算及其形式系统 否定词“并非” 合取词“并且” 析取词“或” 蕴涵词“如果……，那么……” 双向蕴涵词“当且仅当” 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 否定词“并非” 合取词“并且” 析取词“或” 蕴涵词“如果……，那么……” 双向蕴涵词“当且仅当”

第一章 命题演算及其形式系统 否定词（negation ）“并非”（not ）， ┐p 用符号“ ┐ ”表示。 p 1 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 否定词（negation ）“并非”（not ）， 用符号“ ┐ ”表示。 可用表1.1来规定否定词“┐”的意义: p ┐p 1 ┐p读作“并非p”或“非p”。

第一章 命题演算及其形式系统 合取词（ conjunction ）“并且”（and ）， 用符号“∧”表示。 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 合取词（ conjunction ）“并且”（and ）， 用符号“∧”表示。 可用表1.2来规定合取词“∧”的意义： p q p ∧q 1 p∧q读作“p并且q”或“p且q”

第一章 命题演算及其形式系统 析取词（disjunction）“或”（or ） 用符号“ ∨ ”表示。 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 析取词（disjunction）“或”（or ） 用符号“ ∨ ”表示。 可用表1.3来规定析取词“∨”的意义： p q p ∨q 1 p∨q读作“p或者q”、“p或q”。

第一章 命题演算及其形式系统 蕴涵词（implication)“如果…，那么…” （if…then…），用符号“ → ”表示。 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 蕴涵词（implication)“如果…，那么…” （if…then…），用符号“ → ”表示。 可用表1.5来规定该蕴涵词“ → ”的意义： p q p → q 1 p→q中的p称为蕴涵前件，q称为蕴涵后件。

第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 双向蕴涵词(two-way-implication)“当且仅当”（if and only if），用符号“  ”表示。 可用表1.6来规定该双向蕴涵词“  ”的意义： p q p q 1 pq读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。

第一章 命题演算及其形式系统 命题常元 命题变元 命题公式 指派 弄真与弄假 真值表（truth table） 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.3 命题公式及其真值表 命题常元 命题变元 命题公式 指派 弄真与弄假 真值表（truth table）

第一章 命题演算及其形式系统 命题常元（proposition constants）。 命题变元（proposition variable） 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.3 命题公式及其真值表 我们把表示具体命题及表示常命 题的p，q，r，s等与f，t统称为 命题常元（proposition constants）。 命题变元（proposition variable） 是以“真、假”或“1，0”为取值范围的变元， 它未指出符号所表示的具体命题 。

第一章 命题演算及其形式系统 ◆定义1.1 的意义： 1.1.3 命题公式及其真值表 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.3 命题公式及其真值表 ◆定义1.1 以下三条款规定了命题公式（proposition formula） 的意义： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么（┐A），（A∧B）， （A∨B），（A→B），（AB）也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串 是命题公式。

第一章 命题演算及其形式系统 对任意给定的命题变元p1,…,pn的一种取值 状况，称为指派或赋值（assignments） ， 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.3 命题公式及其真值表 对任意给定的命题变元p1,…,pn的一种取值 状况，称为指派或赋值（assignments） ， 用字母，等表示 当A对取值状况  为真时，称指派弄真A或是A的成真赋值，记为(A) = 1； 反之称指派弄假A或是A的成假赋值，记为  (A) = 0。

第一章 命题演算及其形式系统 1.1.3 命题公式及其真值表 对一切可能的指派,公式A的取值可能用下表来描述，这个表 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.3 命题公式及其真值表 对一切可能的指派,公式A的取值可能用下表来描述，这个表 称为真指表（truth table） p q r q∧r p→(q∧r) ┐(p→(q∧r) 1

第一章 命题演算及其形式系统 1.1.4 语句的形式化 语句形式化主要是以下几个方面： ① 要准确确定原子命题，并将其形式化。 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.4 语句的形式化 语句形式化主要是以下几个方面： ① 要准确确定原子命题，并将其形式化。 ② 要选用恰当的联结词，尤其要善于识别自然语言中的 联结词（有时它们被省略），否定词的位置要放准确。 ③ 必要时可以进行改述，即改变原来的叙述方式， 但要保证表达意思一致。 ④ 需要的括号不能省略，而可以省略的括号， 在需要提高公式可读性时亦可不省略。 ⑤ 要注意语句的形式化未必是唯一的。

第一章 命题演算及其形式系统 1.2 重 言 式 1.2.1 重言式概念 ◆定义1.2 重言式 不可满足式 可满足式

第一章 命题演算及其形式系统 （satisfactable formula or contingency）。 1.2 重 言 式 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.1 重言式概念 对命题公式A，如果对A中命题变元的一切指派均弄真A，则A称为重言式（tautology）， 又称永真式. 如果至少有一个指派弄真A，则A称为可满足式 （satisfactable formula or contingency）。

第一章 命题演算及其形式系统 如果对A中命题变元的一切指派均 （contradiction or absurdity） 1.2 重 言 式 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.1 重言式概念 如果对A中命题变元的一切指派均 弄假A，则称A为不可满足式或矛盾式 （contradiction or absurdity） 或永假式 。

第一章 命题演算及其形式系统 （logically equivalent or equivalent）。 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.2 逻辑等价式和逻辑蕴涵式 ◆定义1.3 当命题公式AB为重言式时，称A逻辑等价于B， 记为A┝┥ B，它又称为逻辑等价式 （logically equivalent or equivalent）。 ◆定义1.4 当命题公式A→B为重言式时，称A逻辑蕴涵B， 记为A┝ B，它又称为逻辑蕴涵式 (logically implication)。

第一章 命题演算及其形式系统 1.2 重 言 式 性质： ◆定理1.1 （1）A┝┥B当且仅当┝ AB （2）A ┝ B当且仅当┝ A→B 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.2 逻辑等价式和逻辑蕴涵式 性质： ◆定理1.1 （1）A┝┥B当且仅当┝ AB （2）A ┝ B当且仅当┝ A→B （3）若A┝┥B，则B┝┥A （4）若A┝┥B，B┝┥C，则A┝┥C （5）若A┝ B，则┐B┝ ┐A （6）若A┝ B，B┝ C，则A┝ C （7）若A┝ B，A┝┥A'，B┝┥B'，则A'┝ B'

第一章 命题演算及其形式系统 表示将A中p的所有出现全部代换为公式B后 所得的命题公式（称为A的一个代入实例）， 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.2 逻辑等价式和逻辑蕴涵式 ◆定理1.2-----代入原理 （rule of substitution），简记为RS 设A为永真式，p为A中命题变元，A(B/p) 表示将A中p的所有出现全部代换为公式B后 所得的命题公式（称为A的一个代入实例）， 那么A(B/p)亦为永真式。

第一章 命题演算及其形式系统 （A的一部分，且自身为一公式）， 且C┝┥D。若将A中子公式C的某些 （未必全部）出现替换为D后得到公式B， 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.2 逻辑等价式和逻辑蕴涵式 ◆定理1.3-----替换原理 （rule of replacement ），简记为RR 设A为一命题公式，C为A的子公式 （A的一部分，且自身为一公式）， 且C┝┥D。若将A中子公式C的某些 （未必全部）出现替换为D后得到公式B， 那么A ┝┥ B。

第一章 命题演算及其形式系统 将A中符号∧，∨，t，f分别改换为∨，∧， f，t后所得的公式，那么称A*为A的对偶 （dual）。 第一章 命题演算及其形式系统 1.2 重 言 式 △1.2.3 对偶原理 ◆定义1.5 设公式A仅含联结词 ┐，∧，∨，A*为 将A中符号∧，∨，t，f分别改换为∨，∧， f，t后所得的公式，那么称A*为A的对偶 （dual）。

第一章 命题演算及其形式系统 1.2 重 言 式 △1.2.3 对偶原理 对偶原理 ◆定理1.4 设公式A中仅含命题变元p1,…,pn，及联结词┐，∧，∨，那么 A┝┥┐A*(┐p1/p1,…, ┐pn/pn) ◆定理1.5 设A，B为仅含联结词┐，∧，∨和命题变元p1,…,pn的命题公式，且满足A┝ B，那么有B*┝ A*。进而当 A ┝┥ B时有A* ┝┥ B*。 常把B*┝ A*，A* ┝┥ B*称为A┝ B和A ┝┥ B 的对偶式。

第一章 命题演算及其形式系统 析取子句(disjunctive clauses)：指文字或若干文字 第一章 命题演算及其形式系统 1.3 范式 1.3.1 析取范式和合取范式 文字(letters)：指命题常元、变元及它们的否定， 前者又称正文字，后者则称负文字。 析取子句(disjunctive clauses)：指文字或若干文字 的析取。 合取子句(conjunctive clauses)：指文字或若干文字的合取。 互补文字对(complemental pairs of letters) ： 指形如L，┐L（L为文字）的一对字符。

第一章 命题演算及其形式系统 （disjunctive normal form），如果 第一章 命题演算及其形式系统 1.3 范式 1.3.1 析取范式和合取范式 ◆定义1.6 命题公式A‘称为公式A的析取范式 （disjunctive normal form），如果 （1）A'┝┥A （2）A'为一合取子句或若干合取子句的析取。 ◆定义1.7 命题公式A‘称为公式A的合取范式 （conjunctive normal form）如果 （1）A'┝┥A （2）A'为一析取子句或若干析取子句的合取。

第一章 命题演算及其形式系统 设A为恰含命题变元p1,…,pn的公式。 公式A,称为A的主析（合）取范式 第一章 命题演算及其形式系统 1.3 范式 1.3.2 主析取范式与主合取范式 ◆定义1.8 设A为恰含命题变元p1,…,pn的公式。 公式A,称为A的主析（合）取范式 （majordisjunctive（conjunctive）normal form）， 如果A,是A的析（合）取范式，并且其每个 合（析）取子句中p1,…,pn均恰出现一次。

第一章 命题演算及其形式系统 可表示的，如果 称n元联结词h是用m 个联结词g1, g2,…, gm 第一章 命题演算及其形式系统 1.3 范式 △1.3.3 联结词的扩充与归约 ◆定义1.9 称n元联结词h是用m 个联结词g1, g2,…, gm 可表示的，如果 h(p1, p2,. . ., pn ) ┝┥A 而A中所含联结词仅取自g1, g2,. . ., gm。

词组（complete group of connectives）。 第一章 命题演算及其形式系统 1.3 范式 △1.3.3 联结词的扩充与归约 ◆定义1.10 当联结词组g1, g2,. . ., gm可表示所有 一元、二元联结词时，称其为完备联结 词组（complete group of connectives）。

第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.1 证明、演绎和推理 ◆定义1.11 公式序列A1, A2, …, Am称为Am的一个证明（proof）， 如果Ai(1 ≤ i ≤ m) 或者是公理，或者由Aj1 …, Ajk (j1,…,jki)用推理规则推得。当这样的证明存在时， 称Am为系统的定理（theorems），记为 ├*Am, ( 为所讨论的系统名),或简记为├Am 。

第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 以为前提的演绎（diduction），如果Ai(1≤i≤m) 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.1 证明、演绎和推理 ◆定义1.12 设为一公式集合。公式序列A1,A2,…,Am称为Am的 以为前提的演绎（diduction），如果Ai(1≤i≤m) 或者是  中公式，或者是公理，或者由 Aj1…,Ajk(j1,…,jki)用推理规则导出。当有这样的 演绎时，Am称为  的演绎结果，记为 ├*Am, ( 为所讨论的系统名)，或简记为├Am。 称  和  的成员为Am的前提(hypothesis)。

第一章 命题演算及其形式系统 若公式A是系统PC的定理，则A为永真式。 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 △1.4.2 命题演算形式系统PC ◆定理1.6 （合理性，sondness） 若公式A是系统PC的定理，则A为永真式。 若A是公式集  的演绎结果，那么A是 的逻辑结果。即 若├PC A，则┝ A .若 ├PC A，则 ┝ A . ◆定理1.7 PC是一致的，即没有公式A使得├PC A与 ├PC┐A同时成立。

第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 △1.4.2 命题演算形式系统PC ◆定理1.8 （完备性，completeness） 若公式A永真，则A必为PC的定理；若公式A是公式集  的逻辑结果，那么A必为  的演绎结果。即若┝ A，那么 ├PC A . 若 ┝ A，那么 ├PC A .

第一章 命题演算及其形式系统 对任意公式集  和公式A，B，├A→B当且仅当 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 △1.4.2 命题演算形式系统PC ◆定理1.9 （演绎定理） 对任意公式集  和公式A，B，├A→B当且仅当  A├ B（当  = 时，├A→B当且仅当A├ B，或A├ B）

第一章 命题演算及其形式系统 对任何公式集  和公式A，B ,若 ┐A├ ┐B，  ┐A├ B，那么 ├A 。 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 △1.4.2 命题演算形式系统PC ◆定理1.10 （归谬定理） 对任何公式集  和公式A，B ,若 ┐A├ ┐B，  ┐A├ B，那么 ├A 。 ◆定理1.11 （穷举定理） 对任何公式集，公式A，B，若{┐A}├ B， {A}├ B，则├ B。

第一章 命题演算及其形式系统 如果公式A是PC的定理，那么A也必定是ND的定理。 即├PC A蕴涵├ND A。 * 1.4 命题演算形式系统 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.3 自然推理系统ND ◆定理1.12 如果公式A是PC的定理，那么A也必定是ND的定理。 即├PC A蕴涵├ND A。