发展战略 数理逻辑发展教案
第一讲 引言
一、课程内容
·数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并
能做适当的推理，这对程序设计等课程是极有用处的。
·集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专
业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。
·代数结构：对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学
过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等
代数结构的基本知识。
·图论：对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮
助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用
数学工具建立模型的思维方式。
·讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图
论。考试内容限于书中的内容和难度，但讲课内容不限于书中的内容和难度。
二、数理逻辑发展史
1. 目的
·了解有关的背景，加深对计算机学科的全面了解，特别是理论方面的了解，而不限于
将计算机看成是一门技术或工程性的学科。
·通过重要的历史事件，了解计算机科学中的一些基本思维方式和一些基本问题。
2. 数理逻辑的发展前期
·前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论
·初创时期——逻辑代数时期（17世纪末）
·资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技
术方面起到了相当重要的作用。
·人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。
·莱布尼兹(Leibniz, 1646~1716)完善三段论，提出了建立数理逻辑或者说理性演
算的思想：
·提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理
过程中的命题的含义内容的思考，将推理的规则变为演算的规则。
·使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义
分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。
·布尔(G. Boole, 1815~1864)代数：将有关数学运算的研究的代数系统推广到逻辑
领域，布尔代数既是一种代数系统，也是一种逻辑演算。
3. 数理逻辑的奠基时期
·弗雷格(G. Frege, 1848~1925)：《概念语言——一种按算术的公式语言构成的纯思
维公式语言》(1879)的出版标志着数理逻辑的基础部分——命题演算和谓词演算的正式建
立。
·皮亚诺(Giuseppe Peano, 1858~1932)：《用一种新的方法陈述的算术原理》(1889)提
出了自然数算术的一个公理系统。
·罗素(Bertrand Russell, 1872~1970)：《数学原理》(与怀特黑合著，1910, 1912,
1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义了类和关系的概念，
建立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引
出了数学（主要是算术）中的主要概念和定理。
·逻辑演算的发展：甘岑(G. Gentzen)的自然推理系统(Natural Deduction System)，
逻辑演算的元理论：公理的独立性、一致性、完全性等。
·各种各样的非经典逻辑的发展：路易斯(Lewis, 1883~1964)的模态逻辑，实质蕴涵怪
论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。
4. 集合论的发展
·看待无穷集合的两种观点：实无穷与潜无穷
·康托尔(G. Cantor, 1845~1918)：以实无穷的思想为指导，建立了朴素集合论
·外延原则（集合由它的元素决定）和概括原则（每一性质产生一集合）。
·可数集和不可数集，确定无穷集合的本质在于集合本身能与其子集一一对应。能
与正整数集合对应的集合是可数的，否则是不可数的。证明了有理数集是可数的，使用对角
线法证明了实数集合是不可数的。
·超穷基数和超穷序数
·朴素集合论的悖论：罗素悖论
·公理集合论的建立：ZFC系统
6. 第三次数学危机与逻辑主义、直觉主义与形式主义
·集合论的悖论使得人们觉得数学产生了第三次危机，提出了数学的基础到底是什么这
样的问题。
·罗素等的逻辑主义：数学的基础是逻辑，倡导一切数学可从逻辑符号推出，《数学原理》
一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。
·布劳维尔(Brouwer, 1881~1966)的直觉主义：数学是心灵的构造，只承认可构造的数
学，强调构造的能行性，与计算机科学有重要的联系。坚持潜无穷，强调排中律不能用于无
穷集合。海丁(Heyting)的直觉主义逻辑。
·希尔伯特(D. Hilbert)的形式主义：公理化方法与形式化方法，元数学和证明论，提
倡将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学
符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论，要数学建立在公理化基础上，
将各门数学形式化，构成形式系统，并证明其一致性，这是希尔伯特的数学纲领。
7. 数理逻辑的发展初期
·哥德尔(Godel, 1906~1978)不完全性定理：一个足够强大的形式系统，如果是一致的
则不是完全的，即有的判断在其中是不可证的，既不能断定其为假，也不能证明其为真。
·各种计算模型：哥德尔的递归函数理论，邱吉尔的演算，图灵机模型
·这些计算模型是计算机科学的理论基础，是计算机的理论模型。
三、预备知识
1. 集合的基本概念
·集合(set)：集合是数学中最基本的概念之一，不能以更简单的概念来定义(define)，
只能给出它的描述(description)。一些对象的整体就称为一个集合，这个整体的每个对象
称为该集合的一个元素(member或 element)。
·用大写字母 A, B, C等表示集合，用小写字母 a, b, c等表示集合的元素
·aA表示：a是集合 A的元素，或说 a属于集合 A
·aA表示：a不是集合 A的元素，或说 a不属于集合 A
·集合中的元素是无序的，不重复的。通常使用两种方法来给出一个集合：
·列元素法：列出某集合的所有元素，如：
·A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}表示所有小于 10的自然数所构成的
集合
·B = {a, b, …, z} 表示所有小写英文字母所构成的集合
·性质概括法：使用某个性质来概括集合中的元素，如：
·A = { n | n 是小于 10的自然数}
·C = { n | n 是质数} 表示所有质数所构成的集合
·集合由它的元素所决定，换句话说，两个集合 A和 B相等，记为 A = B，如果 A和 B
具有相同的元素，即 a属于集合 A当且仅当 a属于集合 B。
·子集(subset)：说集合 A是集合 B的子集，记为 AB，如果 a属于集合 A则 a也属于
集合 B。因此 A=B当且仅当 AB且 BA。说集合 A是集合 B的真子集(proper subset)，如
果 AB且 A不等于 B(A B)。
·空集(empty set)：约定存在一个没有任何元素的集合，称为空集，记为，有时也用{}
来表示。按子集的定义，空集是任何集合的子集(为什么？)。
·幂集(power set)：集合 A的幂集，记为 P(A)，是 A的所有子集所构成的集合，即：
·P(A) = { B | B A }
·例如，A = {0, 1}，则 P(A) = { {}, {0}, {1}, {0, 1} }
·显然，对任意集合 A，有 P(A)和 AP(A)
·补集(complement set)：集合 A的补集，记为 A，是那些不属于集合 A的元素所构成
的集合，即 A = {x | xA}。通常来说，是在存在一个全集 U的情况下讨论集合的补集。全
集 U是所讨论的问题域中所有元素所构成的集合。
·集合的并(union)：集合 A和 B的并 AB定义为：AB = {x | xA或者 xB}，集合
的并可推广到多个集合，设 A1, A2, …, An都是集合，它们的并定义为：
A1A2…An = {x | 存在某个 i，使得 xAi}
·集合的交(intersection)：集合 A和 B的并 AB定义为：AB = {x | xA而且 xB}，
集合的交也可推广到多个集合，设 A1, A2, …, An都是集合，它们的交定义为：
A1A2…An = {x | 对所有的 i，都有 xAi}
·集合的差(difference)：集合 A和 B的差 AB定义为：AB = {x | xA而且 xB}。
2. 关系和函数的基本概念
·有序对(ordered pair)：设 A和 B是两个集合，aA, bB是两个元素，a和 b的有序
对，记为<a, b>，定义为集合{{a}, {a, b}}。
·设<a1, b1>和<a2, b2>是两个有序对，可以证明<a1, b1> = <a2, b2>当且仅当 a1
= a2且 b1 = b2。(如何证？)
·有序对可推广到 n个元素，设 A1, A2, …, An是集合，a1A1, a2A2, …, anAn
是元素，定义有序 n元组(ordered n-tuple)<a1, a2, …, an>为<<a1, a2, …, an-1>, an>，
注意这是一个归纳(inductive)定义，将有序 n元组的定义归结为有序 n-1元组的定义。
·显然有<a1, a2, …, an> = <b1, b2, …, bn>当且仅当a1 = b1且a2 = b2且…且an
= bn。
·集合的笛卡尔积(cartesian product)：两个集合 A和 B的笛卡尔积 AB定义为：
AB = {<a, b> | aA且 bB}
·例如，设 A = {a, b, c}，B = {1, 2}，则：
AB = {<a, 1>, <a, 2>, <b, 1>, <b, 2>, <c, 1>, <c, 2>}
·笛卡尔积可推广到多个集合的情况，集合 A1, A2, …, An的笛卡尔积定义为：
A1A2…An = {<a1, a2, …, an> | a1A1且 a2A2且…且 anAn}
·集合之间的关系(relation)：定义 n个集合 A1, A2, …, An之间的一个 n元关系 R为
集 合 A1, A2, …, An的 笛 卡 尔 积 A1A2…An的 一 个 子 集 。 设 <a1, a2, …,
an>A1A2…An，若<a1, a2, …, an>R，则称 a1, a2, …, an间具有关系 R，否则称它们
不具有关系 R。特别地：
·当 A1 = A2 = … = An = A时，称 R为 A上的 n元关系。
·当 n = 2时，有 RA1A2，称 R为 A1与 A2间的一个二元关系(binary relation)。
这时若<a1, a2>R则简记为 a1Ra2，否则（即<a1, a2>R）记为 a1Ra2。通常研究得最多的是
二元关系，n元关系的许多性质可从二元关系的性质扩充而得到。如果没有特别指明的话，
说 R是一个关系则是指 R是一个二元关系。
·当 n = 1时，这时可认为 R是集合 A上满足某种性质的子集。
·关系的一些性质：设 R是 A上的二元关系：
·说 R是自反的(reflexive)，如果对任意的 aA有 aRa。
·说 R是反自反的(irreflexive)，如果对任意的 aA有 aRa。
·说 R是对称的(symmetric)，如果对任意的 a, bA有若 aRb则 bRa。
· 说 R是反对称的(antisymmetric)，如果对任意的 a, bA有若 aRb且 bRa则 a
= b。
·说 R是传递的(transitive)，如果对任意的 a, b, c A有若 aRb且 bRc则 aRc。
·说 R是等价关系(equivalence)，如果 R是自反的、对称的和传递的。
·集合之间的函数(function，或说映射 mapping)：定义集合 A到 B的函数 f是 A和 B
的笛卡尔积 AB的一个子集，且满足若<x, y>f及<x, z>f则 y = z。因此函数是 A和 B
之间的一个特殊的二元关系。通常记集合 A到 B的函数 f为 f : AB。
·函数 f : AB的定义域(domain)dom(f )定义为：
dom(f ) = {x | 存在某个 yB使得<x, y>f }
·函数 f : AB的值域(range)ran(f )定义为：
ran(f ) = {y | 存在某个 xA使得<x, y>f }
·若<x, y>f，通常记 y为 f(x)，并称 y为 x在函数 f下的像(image)，x为 y在
函数 f下的原像。
·函数也可推广到 n元的情形：f : A1A2…AnB，意味着：
·f是 A1A2…AnB的一个子集，且
·<x1, x2, …, xn, y> f且<x1, x2, …, xn, z> f则 y = z。
·函数的一些性质：设 f : AB是集合 A到 B的函数：
·说 f是全函数(total function)，若 dom(f )=A，否则称 f是偏函数(partial
function)。下面如果没有特别指明的话，都是指全函数。
·说 f是满射(surjection, 或说 f maps A onto B)，如果 ran(f ) = B，即对任意
的 yB都有原像。
·说 f是单射(injection，或说 f is one-one)，如果有 f (x1) = f(x2)则 x1 =
x2，即对任意的 yB，如果它有原像的话，则有唯一的原像。
·说 f是双射(bijection，或说 f是一一对应)，如果 f既是满射，又是单射，即对
任意的 yB，都有唯一的原像，同样根据全函数的定义，对于任意 xA都有唯一的像。这
时可以定义 f的逆函数(inverse function)，记为 f -1 : BA，f -1(y) = x当且仅当 f(x)
= y。显然 f -1也是双射。
·集合的基数(cardinal number)或说势：集合 A的基数记为|A|，且有：
·对于有限集合 A，令 A的基数为 A中元素的个数。
·定义无限集合，不直接定义基数，而是通过定义两个集合之间的等势关系来刻划
集合的基数或势，说集合 A和集合 B是等势的(equipotent)，如果存在一个从 A到 B的双射。
根据双射的性质，可以证明等势是集合上的一个等价关系。
·称与自然数集等势的集合为可列集(enumerable)，有限集和可列集统称为可数集
(countable)。
·设 A和 B是有限集合，有|P(A)| = 2|A|，|AB| = |A| |B|。
3. 小结
·下面以树的形式给出了以上主要概念之间的关系：
集合
子集 集合的补、并、交、差 有序对
幂集 笛卡尔积
关系
关系的自反、对称、传递性 函数
单射、满射、双射
4. 归纳定义和归纳证明
·一个集合的归纳定义(inductive definition)通常分为三步：
·归纳基：一些基本的元素属于该集合；
·归纳步：定义一些规则（或者说操作），从该集合中已有的元素来生成该集合的新
的元素；
·最小化：该集合中的所有元素都是通过基本元素以及所定义的规则生成的，换句
话说，该集合是由基本元素及规则所生成的最小的集合。
·自然数集 N的归纳定义：
[1].归纳基：0是一个自然数，即 0 N。
[2].归纳步：若 n是自然数，则 n的后继也是自然数。记 n的后继为 succ(n)，即
若 nN，则 succ(n)N。为方便起见，后面也记 n的后继为 n+1。
[3].最小化：所有的自然都通过步骤[1]和[2]得到，或者说自然数集是通过步骤[1]
和[2]得到的最小集合。
·这种定义方式可推广到对其他一些概念的定义，例如上述多个集合的并、交、笛卡尔
积以及多个元素的有序 n元组都可通过递归的方式定义。例如，对于多个集合的并可定义为：
·归纳基：A1A2 = {x | xA1或者 xA2}
·归纳步：A1A2…An = (A1A2…An-1) An
·这里不需要最小化，因为这里不是定义集合。
·数学归纳法：关于自然数的许多性质都可通过数学归纳法来证明，对于性质 R，如果
它对 0成立，而且如果对于 n成立的话，能够得到它对于 n+1也成立，那么性质 R对所有的
自然数成立。这种证明方法的正确性本身可通过自然数的归纳定义来得到证明：
·定义集合 S = {nN | 性质 R对 n成立}
·归纳基：根据上面的定义有 0S
·归纳步：根据上面的定义有如果 nS，则 n+1S，所以 S是满足上面自然数集的
归纳定义中的 1、2点的一个集合，而自然数集 N是满足这两点的最小集合，所以有 N S，
而显然有 SN，所以 S = N。
·数学归纳法举例：使用数学归纳法证明 1 + 2 + … + n = (n * (n+1))/2
·归纳基：当 n = 0时显然成立。
·归纳步：如果对于 n成立，则有 1 + 2 + … + n = (n * (n+1))/2（这称为归纳
假设），现在要证对于 n+1也成立。显然有：
1 + 2 + … + n + (n + 1) = (n * (n+1))/2 + (n+1) // 根据归纳假
设
= (n * (n+1) + 2 * (n+1))/2 = ((n+1) * ((n+1) + 1))/2
因此要证的公式对于 n+1成立，所以对于所有的自然数成立。
·显然在数学归纳法中，对于归纳基改为 R对于自然数 k成立，归纳步不变的话，则可
证明 R对于所有大于 k的自然数都成立。
·在数学归纳法中，也可将归纳步改为如果 R对于所有小于 n的自然数成立，则推出 R
对于 n也成立，即归纳步是假设对于所有小于 n的自然数性质 R成立来导出性质 R对于自然
数 n成立。这种形式的数学归纳法通常称为第二数学归纳法。
5. 形式系统
·形式系统的定义：一个形式系统 S由下列 4个集合构成：
·一个非空集合S，称为形式系统 S的字母表或说符号(Symbol)表；
·一个由S中字母的有限序列（字符串）所构成的集合 FS，称为形式系统 S的公式
(Formula)集；
·从 FS中选取一个子集 AS，称为形式系统 S的公理(Axiom)集；
·FS上有一个部分函数集RS = {Rn | Rn : FS FS … FS FS , n = 1, 2, …}，
称为形式系统 S的规则(Rule)集，其中 Rn : FS FS … FS FS是 n元的部分函数，我
们称其为 n元规则。
·形式系统中的定理(Theorem)：
·归纳基：t AS 是形式系统 S中的定理。
· 归纳步：t1, t2, …, tn是形式系统 S中的定理，而 Rn是 S中的规则，那么
Rn(t1, t2, …, tn)也是形式系统 S中的定理。
·对于形式系统中的规则 Rn : FS FS … FS FS，通常表示成下面的形式：
t1, t2, …, tn
Rn(t1, t2, …, tn)
·形式系统具有两个特征：
·形式化实际上是一个可机械实现的过程，在它里面，符号、规则和演算等被表示
得严密、精确。在形式系统 S中，只能使用字母表S中的符号，只承认公式集 FS中的符号
串的合理性，只能由公理集，根据规则推出有意义的东西来。
·形式系统一旦完成，就成了符号串及根据规则进行的符号串的改写，系统与一切
实际意义就毫不相干，或者说已经通过这种符号，从实际问题中抽象出了我们所需要研究的
内容。在形式系统内部，所能认识的只能是符号串及其改写，只能在形式系统外对这种符号
串及规则赋予意义。
·对象语言(Object language)与元语言(Meta language)：
·数理逻辑所研究的是“数学推理”，而使用的方法也是数学推理，所以有必要区分
这两个层次的推理。
·把作为研究对象的“推理”形式化，使用形式语言来表示作为研究对象的“推理”
的前提、结论和规则等，这种形式语言是我们所研究的对象语言。
·另一方面，关于形式系统的性质、规律的表达和作为研究方面的推理方式使用另
一种语言来表达，这个语言称为研究的元语言，通常使用半数学化的自然语言。
·形式语言的语法(Syntax)与语义(Semantic)：
·形式语言的语法是构成形式系统的公式集、公理集和规则集的法则。
·形式语言的语义是关于形式系统的解释和意思。
·形式语言本身没有含义，但我们在构造它们时是假想它们能代表某种意义的，特
别的当我们在选择形式系统的公理时，总是选择所研究的问题域中那些最为明显或最容易公
认为正确的性质。
6. 习题
1. 令集合 A = { n | n 10且 n 是奇数}，B = {n | n 10且 n是素数}，请回答下列
问题：
a) 请用列元素的方法列出集合 A和集合 B，请问集合 B是否是集合 A的子集？
b) 请计算 AB、AB、AB、AB以及 P(A)(即 A的幂集)。
2. 设关系 R = {<a, b> | a和 b是互质的自然数}，请问 R是自反的吗？对称的吗？传递
的吗？为什么？
3. 设 f : AB是函数，R是 A上的如下二元关系：R = {<a, b> | a, bA, f (a) = f
(b) }， 证明 R是 A上的一个等价关系。
4. 使用数学归纳法证明：12 + 22 + 32 + … + n2 = (n * (n + 1) * (2n + 1)) / 6
5. 设有函数 f : NN N，f(n) = <n, n+1>，请问 f是不是单射、满射或双射？
*6. 设 R1和 R2都是 A上的等价关系，请问 R1R2和 R1R2是否还是 A上的等价关系？如果
是请证明，否则请举一反例。
*7. 设 R是集合 A上的等价关系，aA，可定义：
a) [a] = {bA | aRb }，称[a]为 a关于 R的等价类；
b) A/R = {[a] | aA}，称 A关于 R的商集。
设函数 f : AA/R定义为对任意 aA有 f(a) = [a]，请问 R满足怎样的条件时 f是单
射？
*8 请给出<x, y, z>的集合方式的定义。若定义：[x, y, z] = {{x}, {x, y}, {x, y,
z}}，则如果有[x1, y1, z1] = [x2, y2, z2]是否意味着有 x1 = x2且 y1 = y2且 z1 = z2？
第二讲 数理逻辑
一、命题逻辑(Propositional Logic)
1. 内容概述
·简单命题与复合命题：什么是命题？命题联结词及其含义。
·命题公式与赋值：命题逻辑公式的归纳定义，命题公式的真值表。
·等值演算：命题公式的等值赋值，重要的等值式。
·命题联结词的完备集：通过等值演算得到命题联结词的完备集和极小完备集。
·命题公式的范式：析取范式与合取范式。
·命题演算系统：使用命题逻辑公式进行推理的形式系统。
·命题演算系统的语义与命题演算系统的元性质：注意区别形式系统的语法和语义。
2. 简单命题与复合命题
·命题(proposition)：经典命题逻辑中，称能判断真假但不能既真又假的陈述句为命题。
·命题对于命题逻辑来说是一个原始的概念，不能在命题逻辑的范围内给出它的精
确定义，只能描述它的性质。
·命题必须为陈述句，不能为疑问句、祈使句、感叹句等，例如下述句子为命题：
1. 3 是有理数 2. 8小于 10
3. 2是素数 4. 乌鸦是黑色的
下列句子不是命题：
1. 这个小男孩多勇敢啊！ 2. 乌鸦是黑色的吗？
3. 但愿中国队能取胜。 4. 请把门开一开！
下列句子不可能判断其为真或为假，所以也不是命题：
1. x + y > 10 2. 我正在撒谎
·命题必须具有真假值，从某种意义上来说，疑问句、祈使句、感叹句没有真假之
分。但能判断真假，并不意味着现在就能确定其是真还是假，只要它具有能够唯一确定的真
假值即可，例如下述陈述句是命题：
1. 明年的中秋节的晚上是晴天 2. 地球外的星球上存在生物
3. 21世纪末，人类将居住在太空 4. 哥德巴赫猜想是正确的
·经典命题逻辑不区分现在已确定为真，还是将来可能确定为真这种情况，处理与
时间有关的真值问题是时态逻辑的任务。经典命题逻辑也不区分是在技术上可以确定为真，
还是现在的技术条件下不可以确定为真的这种情况，只承认在技术上，或者说能给出某种方
法确定为真的那些东西才为真是直觉逻辑的观点。
·真命题和假命题：命题是为真或为假的陈述句，称这种真假的结果为命题的真值。如
果命题的真值为真，则称为真命题，否则称为假命题。
·命题常量与命题变量：使用符号来表示命题，通常用 p, q或带下标来表示命题常量或
者变量。如果命题符号 p代表命题常量则意味它是某个具体命题的符号化，如果 p代表命题
变量则意味着它可指代任何具体命题。如果没有特别指明，通常来说命题符号 p等是命题变
量，即可指代任何命题。
·简单命题与复合命题：不能分成更简单的陈述句的命题为简单命题或原子命题，否则
称为复合命题，复合命题使用命题联结词联结简单命题而得到。
·复合命题的联结词通常包括：
·设 p是任意命题，复合命题“非 p”称为 p的否定（非），记为 p。
·设 p和 q是任意命题，复合命题“p且 q”称为 p和 q的合取（与），记为 pq。
·设 p和 q是任意命题，复合命题“p或 q”称为 p和 q的析取（或），记为 pq。
·设 p和 q是任意命题，复合命题“如果 p则 q”称为 p蕴涵 q，记为 pq。
·设 p和 q是任意命题，复合命题“p当且仅当 q”称为 p与 q等价，记为 pq。
·上述定义中的非 (negation)、合取 (conjunction)、析取 (disjunction)、蕴涵
(implication)和等价(equivalence)是在命题逻辑中的术语，而引号中给出的复合命题是自
然语言中的典型用法。当然，命题逻辑中符号化形式的复合命题在自然语言中有许许多多的
表达方法，这也是为什么自然语言有歧义的原因，参见教材中的各例题，并注意以下几点：
·pq的逻辑关系是 pq为真当且仅当 p和 q中至少有一个为真。但自然语言中的
“或”既可能具有相容性，也可能具有排斥性。命题逻辑中采用了“或”的相容性。
·pq的逻辑关系是 pq为假当且仅当 p为真，而 q为假，称 p为蕴涵式的前件，
q为蕴涵式的后件。现实世界中的“如果…则…”与这种蕴涵有比较大的区别。简单命题逻
辑中的这种蕴涵常常称为“实质蕴涵”，相对应地有“严格蕴涵（p严格蕴涵 q，意味着 p为
真，则 q不可能为假）”、“相干蕴涵”等。实质蕴涵意味着可从假的前提推出任何命题来，
或两个不没有内在联系的命题之间存在蕴涵关系。
·将日常生活中的陈述句符号化为命题逻辑中的公式是在今后的程序编写等课程中应用
数理逻辑知识的重要基础。但就数理逻辑这门课程本身而言，我们只关心公式之间的真值关
系，而不关心公式所具体指代的命题。
·复合命题与简单命题之间的真值关系可用下表给出，其中 0代表假，1代表真：
p q p pq pq pq pq
0 0 1 0 0 1 1
0 1 1 0 1 1 0
1 0 0 0 1 0 0
1 1 0 1 1 1 1
3. 命题逻辑公式
【定义 】命题逻辑公式(propositional logic formula)由以下子句归纳定义：
[1].归纳基：命题常量或命题变量是命题逻辑公式，称为命题逻辑公式的原子项。
[2].归纳步：如果 A, B是逻辑公式，则(A)、(AB)、(AB)、(AB)和(AB)也
是命题逻辑公式。
[3].最小化：所有的命题逻辑公式都通过 1和 2得到。 □
在这里我们隐含地使用的字母表是大小写的英文字母、命题联结符和园括号。英文字母
还可带下标。其它的符号都不属于我们的符号表，即在命题逻辑公式中不能出现这些符号。
后面我们将命题逻辑公式简称为命题公式，或在没有二义的情况下进一步简称为公式。
【例子 】((p q) ((p) (q r)))是命题公式，它通过以下步骤生成：
1. p是公式； // 根据定义 的[1]
2. q是公式； // 根据定义 的[1]
3. (p q)是公式； // 根据定义 的[2]
4. (p)是公式； // 根据定义 的[2]
5. r是公式； // 根据定义 的[1]
6. (q r)是公式； // 根据定义 的[2]
7. ((p) (q r))是公式； // 根据定义 的[2]，以及 4, 6
8. ((p q) ((p) (q r)))是公式。 // 根据定义 的[2]，以及
3, 7
这种生成过程，可以形象地用下面的一棵树来表示：
((p q) ((p) (q r)))
(p q) ((p) (q r))
p q (p) (q r)
p q r
这种树在形式语言与自动机中就称为语法分析树。
【反例 】
·根据定义 ，p q不是公式，因为两边没有园括号
·根据定义 ，(p q r)不是公式，实际上，由定义 生成的公式，每个命
题联结符都会对应一对园括号。
·显然(pqr)、(q(rp)等都不是公式。
【定理 】设 R是某个性质，如果有：
[1].对于所有的原子项 p，都满足性质 R；
[2]. 如果对任意的公式 A和 B都满足性质 R，就有(A)、(AB)、(AB)、(AB)
和(AB)也满足性质 R。
那么，所有的公式 A就都满足性质 R。 □
该定理的证明类似数学归纳法的证明，很容易根据定义 得到。
【定义 】命题公式 A的复杂程度 deg(A)定义为：
[1].如果 A是原子项，则 deg(A) = 0；
[2].deg(A) = deg(A) + 1;
[3].deg(A * B) = max(deg(A), deg(B)) + 1，其中*代表、、、之一。
□
此定义等价于教材 p11的定义 。只不过我们在这里给出的是递归定义。使用归纳法，
我们可证明下面定理：
【定理 】deg(A)小于等于命题公式 A中的命题联结符号的数目。
【证明】根据命题公式 A的结构进行归纳证明：
1. 归纳基：如果 A是原子项，则根据定义 有 deg(A) = 0，显然定理成立。
2. 归纳步：假设定理对于命题公式 A和 B成立（归纳假设），记命题公式 A中的
命题联结符号数为 Sym(A)，即有 deg(A) Sym(A)和 deg(B) Sym(B)。那么由于 deg(A)
= deg(A) + 1，而 Sym(A) = Sym(A) + 1，所以定理对于A也成立。同样由于 deg(A *
B) = max(deg(A), deg(B)) + 1，而 Sym(A * B) = Sym(A) + Sym(B) + 1，因而有 deg(A
* B) Sym(A * B)，从而定理对所有的命题公式都成立。
□
【定理 】任意命题逻辑公式 A中出现相等数目的左右园括号，实际上，左右园括号
的个数都等于 A中的命题联结符号数。 □
【定理 】任意命题逻辑公式 A具有下列 6种形式之一，且只具有其中一种形式：
[1].A为原子项； [2].(A) [3].(AB)
[4].(AB) [5].(AB) [6].(AB) □
定理 的确切含义包括以下几点：
1. 任意命题公式必然具有上述 6中形式之一；
2. 这 6中形式都互不相同；
3. 如果(A)与(A1)相同，则必有 A与 A1相同；
4. 如果(A * B)与(A1 * B1)相同，则必有 A与 A1相同，且 B与 B1相同。
根据定理 和定理 ，我们不难明白例子 是如何得到该其中命题公式的语法分
析树的。实际上每个命题公式的最左边都是左园括号，如果从第二个符号不是左园括号，那
么这个公式只有一个命题联结符。否则找与第二个左园括号配对的右园括号，从而将命题公
式划分为这样的形式：((…) * (…))，如果原来的命题公式为根的话，那么左右两边的两
个命题公式分别为它的左右子树了，而且对这两个公式可作类似的分析，最后到原子项。
在后面，为了书写方便起见，我们省略最外边的括号，并规定各个命题联结符的优先级
别为大于，大于，大于，大于，从而可省略命题公式中一些不必要的园括号，
例如例子 中的公式可写为：p q p q r。不过在后面我们书写公式的原则
是尽量简便，但又能让读者容易理解。而有关命题公式的性质的讨论，则只针对可由上面定
义 所能生成的公式形式。
上面讨论的命题公式的语法结构，下面讨论命题公式的赋值。
【定义 】 对命题公式的一次真值赋值 t是从所有命题变量所组成的集合到集合{0,
1}的函数。实际上，对于某个命题公式 A来说，我们只关心 t在 A中的命题变量上的值。这
里我们假定存在一个所有命题变量所组成的集合 U，或者说我们所有命题公式中的变量都取
之于集合 U，我们记命题公式 A中的所有命题变量所组成的集合为 Var(A)。设有一个真值赋
值 t : U{0, 1}，而对于命题公式 A的真值赋值来说，我们只关心 t在 Var(A)上的值。
【例子 】对于命题公式 A = ((p q) ((p) (q r)))，有：
Var(A) = {p, q, r}
这里不妨假定 U = Var(A)，真值赋值就是一个函数 t : {p, q, r}{0, 1}，例如可令：
t(p) = 0, t(q) = 1, t(r) = 0
【定义 】命题公式 A在真值赋值 t : U{0, 1}下的真值 t(A)递归定义如下：
[1].如果命题公式 A是一个命题常量 p，则如果 p为真，t(A) = 1，否则 t(A) =
0；
[2].如果命题公式 A是一个命题变量 p，则 t(A) = t(p)
[3].若 t(A) = 0则 t(A) = 1，否则 t(A) = 0。
[4].若 t(A) = t(B) = 1，则 t(AB) = 1，否则 t(AB) = 0。
[5].若 t(A) = t(B) = 0，则 t(AB) = 0，否则 t(AB) = 1。
[6].若 t(A) = 0或者 t(B) = 1，则 t(AB) = 1，否则 t(AB) = 0。
[7].若 t(A) = t(B)，则 t(AB) = 1，否则 t(AB) = 0。
【例子 ，续】对于命题公式 A = ((p q) ((p) (q r)))，及真值赋值
函数 t：
t(p) = 0, t(q) = 1, t(r) = 0
有：
1. t(p) = 0, t(q) = 1;
2. t(p q) = 1; // 根据定义 的[5]
4. t(p) = 1; // 根据定义 的[3]
5. t(r) = 0;
6. t(q r) = 0; // 根据定义 的[4]
7. t((p) (q r)) = 0; // 根据定义 的[7]
8. t((p q) ((p) (q r))) = 0; // 根据定义 的[6]
因此命题公式 A在上述真值赋值下的真值 t(A)是 0。
不难看出，定义与上一节中给出的复合命题与简单命题之间的真值关系表是一致的。
而且从上面的例子与例 的比较也可看出，对于命题公式的真值，可根据该命题公式的生
成步骤来得到。
命题公式的真值只与命题公式中所出现的命题变量的真值赋值有关，如果命题公式中含
有 n个命题变量，则对这些命题变量的真值赋值共有 2n种不同情况，可通过一个表，列出
在这所有情况下命题公式的真值，这种表称为该命题公式的真值表，例如上述命题公式 A的
真值表为：
p q r
(pq
)
(p
)
(qr
)
((p)(qr
))
((pq)
((p)(qr)))
0 0 0 0 1 0 0 1
0 0 1 0 1 0 0 1
0 1 0 1 1 0 0 0
0 1 1 1 1 1 1 1
1 0 0 1 0 0 1 1
1 0 1 1 0 0 1 1
1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0
【定义 】如果命题公式 A在任意的真值赋值函数 t : U{0, 1}下的真值 t(A)都为
1,则称命题公式 A为永真式(tautology)（或称重言式）；如果命题共 A在任意的真值赋值函
数下的真值都为 0，则称 A为矛盾式(contradiction)；如果 A不是矛盾式，则称为可满足
式。
【例子 】根据命题公式 A = ((p q) ((p) (q r)))的真值表，我们知
该命题公式是可满足式，但不是永真式。而公式 B = ((p(qp))r)是永真式，其真值表
为：
p q r
(qp
)
(p(qp)) ((p(qp))r)
0 0 0 0 1 1
0 0 1 0 1 1
0 1 0 1 1 1
0 1 1 1 1 1
1 0 0 1 1 1
1 0 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1
而公式((((pq))q)r)（教材 14页简写为(pq)qr）是矛盾式，其真值表为：
p q r (pq)
((pq)
)
(((pq))
q)
((((pq))q)
r)
0 0 0 1 0 0 0
0 0 1 1 0 0 0
0 1 0 1 0 0 0
0 1 1 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0
1 1 0 1 0 0 0
1 1 1 1 0 0 0
【定义 】我们使用符号来表示一组命题公式所构成的集合。定义在真值赋值函
数 t : U{0, 1}下的真值 t()为：t() = 1当且仅当对中任意公式 A有 t(A) = 1，否
则定义 t() = 0(注意只要中存在某个公式 A使得 t(A) = 0，就有 t() = 0)。说是可
满足的，如果存在某个真值赋值函数 t使得 t() = 1，这时称 t满足。
【定义 】设是一组命题公式的集合，说命题公式 A是以为前提的永真式，如果
满足对任意满足的真值赋值函数 t都有 t(A) = 1，这时我们记为╞A。
注意在定义 中，如果为空集，则╞A表示 A为永真式，因为对于空集来说，显
然任意的真值赋值函数 t都满足它（因为中没有命题公式），从而╞A意味着对任意的真
值赋值函数 t都有 t(A) = 1，即 A为永真式。
4. 等值演算
【定义 】当 = {A1, A2, …, An}时，我们也记╞A为 A1, A2, …, An╞A。如
果有 A╞B且 B╞A，则称命题公式 A与 B等值，记为 AB。
实际上公式 A与 B等值记为 A╞╡B会更准确些，但教材采用了符号 AB，为了不会过
于混淆，我们也使用这种记号。实际上，根据定义 ，AB就意味着对任意的真值赋值
函数 t有 t(A) = 1当且仅当 t(B) = 1，也就是说对任意的 t有 t(A) = t(B)。从而定义
与教材中关于命题公式等值的定义是等价的，即有下述定理：
【定理 】AB当且仅当 AB是永真式。 □
使用真值表，不难证明下面的定理：
【定理 】设 A, B, C是任意的命题公式，有：
[1].双重否定律：A ((A))
[2].等幂律： A(AA) A(AA)
[3].交换律： (AB) (BA) (AB) (BA)
[4].结合律： ((AB)B) (A(BB)) ((AB)B) (A(BB))
[5].分配律： (A(BC)) ((AB)(AC)) (A(BC)) ((AB)(AC))
[6].德 摩 根 律 ： ((AB)) ((A)(B)) ((AB))
((A)(B))
[7].吸收律： (A(AB)) A (A(AB)) A
[8].零律： (A1) 1 (A0) 0
[9].同一律： (A 0) A (A1) A
[10]. 排中律： (A(A)) 1
[11]. 矛盾律： (A(A)) 0
[12]. 蕴涵等值式：(AB) ((A)B)
[13]. 等价等值式：(AB) ((AB)(BA))
[14]. 假言易位： (AB) ((B)(A))
[15]. 等价否定等值式：(AB) ((A)(B))
[16]. 归谬论： ((AB)(A(B))) (A)
□
要注意的是，上述定理中的 0代表真值为 0的任意命题常量，而 1代表真值为 1的任意
命题常量。
由于命题联结符号和都满足结合律，因此我们可有如下的简写：
A1A2…An
A1A2…An
根据以上简写，我们可推广定理 为以下定理 ：
【定理 】
[1].A1, A2, …, An╞A当且仅当╞((A1A2…An)A)。
[2].A1, A2, …, An╞A当且仅当╞((A1(A2(…(AnA)…))。
□
【引理 】设有 AA'和 BB'，则有：
[1].(A)(A')
[2].(AB)(A'B')
[3].(AB)(A'B')
[4].(AB)(A'B')
[5].(AB)(A'B')
□
根据引理 ，不难证明下面的置换规则：
【定理 】设有 BC，而 A'是命题公式 A通过使用 C替换 A中出现的某些 B（不需
要是替换所有的 B）而得到的命题公式，则有 AA'。
【证明】对命题公式 A的结构进行归纳。首先如果 B = A，则有 C = A'，从而有
AA'。
归纳基：如果 A是命题变量和命题常量，那么必有 B = A，因此定理成立。
归纳步：根据定理 ，命题公式 A必为如下 5种形式之一：A1, A1A2, A1A2,
A1A2, A1A2。设 A的形式为A1，如果 B = A则定理成立，否则必有 B出现 A1中，将 A1
中的 B用 C替换后得到的为 A1'，按归纳假设有 A1 = A1'，再根据引理 有A1 = A1'。
定理成立。若 A的形式为 A1 * A2，则如果 B = A则定理成立，否则必有 B出现在 A1或 A2中，
或同时出现在这两者中。设将 A1中的 B用 C替换后得到的为 A1'，而将 A2中的 B用 C替换
后得到的为 A2'，按归纳假设有 A1A1'和 A2 A2'，再根据引理 有 A1*A2A1*A2，即
定理成立。
□
【定义 】如果命题公式 A中只出现命题变量、命题常量、命题联结符号、和
则称为限制性（命题）公式。定义：
[1].对于限制性公式 A，将其中的命题联结符号换成，命题联结符号换成得
到的公式称为 A的对偶公式(dual formula)，记为 Aop。
[2].对于限制性公式 A，将其中出现的所有原子项（命题变量或命题常量）p换成p
得到的公式称为 A的内否式，记为 A。
【例子 】设公式 A = ((pq)(r))，则：
(1).A的对偶式 Aop = ((pq)(r))
(2).A的内否式 A = (((p) (q)) r)
【引理 】设公式 A、B都是限制性公式，有：
[1].(Aop)op A (A) A
[2].(A B)op Aop Bop (A B) A B
[3].(A B)op Aop Bop (A B) A B
[4].(Aop) (A)op
□
引理 中的(恒等号)表示两边的公式在（语法）形式上完全一样，例如(Aop)op
A表示对 A的对偶公式 Aop再做一次对偶操作得到的就是 A本身。而(Aop) (A)op表示对 A
做一次对偶操作得到 Aop，然后再求 Aop的内否式，得到的公式与先求 A的内否式，然后再做
对偶操作得到的公式完全一样，用代数学的术语来说，就是这两种操作可交换。
引理 很容易根据定义 证明，也可直观理解引理 所代表的含义。读者可
通过对一些公式求它的对偶式和内否式来验证引理 的每个恒等式，例如：
【例子 ，续】设公式 A = ((pq)(r))，则：
(1).Aop = ((pq)(r)), (Aop) = (((p)(q)) r)
(2).A = (((p) (q)) r), (A)op = (((p) (q)) r)
显然有(Aop) (A)op。
【定理 】设公式 A是任意的限制性公式，有：
[1].(A)op (Aop) (A) (A)
[2].(Aop) A
【证明】略 □
【推论 】设公式 A和 B都是限制性公式，有 A B则(Aop) (Bop)
【证明】根据引理 及(A) A不难得到 A B当且仅当A B。则：
(Aop) A B (Bop)
□
在定理 中已经看到了推论 的许多佐证，例如对于吸收律(A(AB)) A，
其中(A(AB))的对偶公式是(A(AB))，从而有(A(AB)) A，这与第二个
吸收律公式(A(AB)) A是相同的，因为 A、B代表任意命题公式。
【例子 】验证下列等值式
(1).((pq)r) ((qp)r)
(2).(p(qr)) ((pq)r)
(3).((pq)r) ((pr)(qr))
(4).((pq)r) ((pr)(qr))
(5).(p(qr)) ((pq)(pr))
(6).(p(qr)) ((pq)(pr))
【证明】证明的思路有两种，第一种思路是通过列真值表，可看到上述等值式的两边
在任何真值赋值下都有相同的真值，从而完成上述等值式的验证。读者不妨自己按照这种思
路进行证明。第二种思路是利用定理 中的基本等值式来证明。可以看到上述等值式主
要是关于蕴涵的等值式，证明关于蕴涵的等值式的方法是利用定理 中的[12]将蕴涵化
成只出现与、或、非的公式，再来验证它们的相等。
(1).((pq)r) ((pq)r) // 定理 中的[12]：蕴涵等值式
((pq))r // 定理 中的[12]：蕴涵等值式
(p(q))r // 德摩尔根律
((qp)r) // 的交换律
(2).(p(qr)) (p(qr)) // 蕴涵等值式
(p(qr)) // 蕴涵等值式
((pq)r) // 的结合律
((pq)r) // 德摩尔根律，反向运用
((pq)r) // 蕴涵等值式，反向运用
(3).((pq)r) ((pq)r) // 蕴涵等值式
((pq)r) // 德摩尔根律
((pr)(qr)) // 分配律与交换律
((pr)(qr)) // 蕴涵等值式
(5).(p(qr)) (p)(qr) // 蕴涵等值式
(p)(p)(qr) // 的幂等律
(pq)(pr) // 的交换律和结合律
(pq)(pr) // 蕴涵等值式
(4)(6)留作练习
□
【例子 】德摩尔根律的推广：
(1).(A1A2…An) (A1)(A2)…(An)
(2).(A1A2…An) (A1)(A2)…(An)
【证明】对 n实施数学归纳法，或直接从定理 [2]得到。
□
5. 联结词的完全集
【定义 】{0, 1}上的 n元函数 f : {0, 1}n{0, 1}就称为一个 n元真值函数。
联结词实际上一个一元真值函数：
f(0) = 1, f(1) = 0
而联结词、、和则都是二元真值函数：
f(0, 0) = 0, f(0, 1) = 0, f(1, 0) = 0, f(1, 1) = 1
f(0, 0) = 0, f(0, 1) = 1, f(1, 0) = 1, f(1, 1) = 1
f(0, 0) = 1, f(0, 1) = 1, f(1, 0) = 0, f(1, 1) = 1
f(0, 0) = 1, f(0, 1) = 0, f(1, 0) = 0, f(1, 1) = 1
反过来，一个真值函数就可看成一个真值联结词。设 f : {0, 1}n{0, 1}是一个 n元
真值函数，则可如下定义一个 n元真值联结词 Nf :
对于 n个命题变元 p1, p2, …, pn，命题公式 Nf(p1, p2, …, pn)在真值赋值函数<t1,
t2, …, tn>下的真值为 f(t1, t2, …, tn)。
显然互不相同的 n元真值函数的个数为 22n，因此可定义 22n个 n元真值联结词，例如 1
元真值函数有四个：
f1: 00, 10 f2: 00, 11 f3: 01, 10 f4: 01,
11
而 2元真值函数有 16个，可定义 16个真值联结词，而我们常用的只不过是其中的 4个。
现在的问题是，是否所有的真值函数都可使用常用的这 5个真值联结词来表示呢？
【定义 】设是联结词的一个集合，称为联结词的一个完全集，如果任意真值函
数 f都可用仅含中联结词的命题公式 A来表示，即对 A中命题变元的任意一个真值赋值
<t1, t2, …, tn>，A在<t1, t2, …, tn>下的真值为 f(t1, t2, …, tn)。
【定理 】{, , , }是联结词的一个完全集。
【证明】根据定义 只要证明对任意 n元真值函数都可由只含、、和的 n元
命题公式来表示即可。对真值函数的元数 n进行归纳证明。
归纳基：当 n = 1时，一元真值函数只有 4个，可分别用 p(p)、p、p和 p(p)
来表示，因此定理成立。
归纳步：假设当 n = k时定理成立，要证 n = k + 1定理也成立。设 f(x1, x2, …,
xk, xk+1)是一个 k+1元真值函数，定义如下两个 k元真值函数：
f1(x1, x2, …, xk) = f(x1, x2, …, xk, 0) f2(x1, x2, …, xk) =
f(x1, x2, …, xk, 1)
由归纳假设知 f1和 f2都可由只含、、和的 k元命题公式来表示，设它们分别可
由 A1和 A2表示，且假定 A1和 A2中的 k个命题变元为 p1, p2, …, pk。现在我们证 f可由 A
= ((pk+1)A1)(pk+1A2)表示，其中 pk+1是不同于 p1, p2, …, pk的一个命题变元。即要
证对命题变元 p1, p2, …, pk, pk+1的一个真值赋值<t1, t2, …, tk, tk+1>时，A的真值是
f(t1, t2, …, tk, tk+1)。当 tk+1 = 0时，即 pk+1被赋值为 0，这时((pk+1)A1)与 A1等值，
而(pk+1A2)的真值为 1，所以 A与 A1等值，而按归纳假设有 A1的真值为 f1(t1, t2, …,
tk)，即为 f(x1, x2, …, xk, 0)。同理可证当 tk+1 = 1时 A的真值是 f(x1, x2, …, xk, 1)，
从而 A的真值是 f(t1, t2, …, tk, tk+1)。
□
【推论 】{, }, {, }和{, }都是联结词的完全集。
【证明】1. 要证{, }是联结词的一个完全集，只要证任一命题公式可与一个只含
和的命题公式等值，事实上有：
(AB)((A)B) (AB)(((A)(B)))
2. {, }是联结词的一个完全集，因为：
(AB)(((A)(B))) (AB)((A)B)
3. {, }是联结词的一个完全集，因为：
(AB)(((A)(B))) (AB)((A)B)
事实上，上述每个集合都是极小的完全集，即不能再从集合中去掉任意一个联结词还能
保持是完全集。
□
【定理 】{, , , }不是联结词的完全集。
【证明】总取 0值的真值函数不能由只含此联结词集中的联结词的命题公式来表达，因
为这样的命题公式当所有命题变元都真值赋值为 1时真值为 1，不可能为 0。 □
6. 命题公式的范式
【定义 】将命题符号（代表命题变元或命题常量）或命题符号的否定统称为文字
(literal)。仅由有限个文字构成的析取式称为简单析取式。仅由有限个文字构成的合取式
称为简单合取式。
【例子 】文字、简单析取式与简单合取式：
(1) p, q等为文字，也是一个文字的简单析取式和简单合取式
(2) pq, p(q)等为两个文字的简单析取式，pq(r)为三个文字的简单析取
式
(3) pq, p(q)等为两个文字的简单合取式，pq(r)为三个文字的简单合取
式
【定理 】一个简单析取式是永真式当且仅当它同时含一个命题符号及其否定，一
个简单合取式是矛盾式当且仅当它同时含一个命题符号及其否定。 □
【定义 】由有限个简单合取式构成的析取式称为析取范式(disjunctive normal
form)，由有限个简单析取式构成的合取式称为合取范式(conjunctive normal form)。析取
范式和合取范式统称为范式(normal form)。
【例子 】析取范式和合取范式：
(1) (pq)(pq), (pr)(qrp)(rp)等是析取范式
(2) (pq)(pq), (pr)(qrp)(rp)等是合取范式
根据定义 知，一个析取范式的对偶式是合取范式，一个合取范式的对偶式是析取
范式。
【定理 】一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。一个
合取范式是永真式当且仅当它的每个简单析取式都是永真式。
【定理 】（范式存在定理）任意命题公式都存在与之等值的析取范式与合取范式。
求一个公式的范式的步骤如下：
[1].利用蕴涵等值式(AB)(AB)和等价等值式(AB)(AB)(AB)消除公式
中的联结词和，使得公式中只含有联结词、和。
[2].利用双重否定律AA和德摩尔根律将否定放到命题符号前。
[3].利用分配律，求析取范式利用对的分配律，求合取范式则利用对的分配律。
【例子 】求命题公式的析取范式和合取范式
(1).求(pq)(pr)的析取范式和合取范式
(2).求(pq)(pr)的析取范式和合取范式
【解答】(1)求(pq)(pr)的析取范式：
(pq)(pr)(pq)(pr) // 蕴涵等值式
(pq)(pr)(pp)(pr)(qp)(qr) // 双重否定律和分配律
(pr)(qp)(qr) // (pp)是矛盾式
显然(pq)(pr)的合取范式为(pq)(pr)。
(2)求(pq)(pr)的合取范式：
(pq)(pr)(pq)(pr) (pqp) (pqr)
显然(pq)(pr)的析取范式为(p)q(pr)。
注意：一个命题公式的合取范式和析取范式不具有唯一性。
【定义 】在含有 n个文字的简单合取式中，若每个命题符号和其否定不同时存在，
而二者之一必须出现且只出现一次，且第 i个命题变元或者否定出现在从左边算起的第 i个
位置上（若命题变元无下标，则按字典顺序排列），这样的简单合取式称为极小项。
极小项是特殊的简单合取式。含 n个文字的极小项中，由于每个命题变元以原形或否定
出现且仅出现一次，因此 n个命题变元共可产生 2n个不同的极小项。若在极小项中，将命
题变元的原形对应 1，否定对应 0，则每个极小项唯一地对应一个二进制数，该二进制数的
每一位正是使该极小项的真值为 1的真值赋值。
【例子 】两个命题变元 p, q生成的 4个极小项为：
pq对应 00，记为 m0 pq对应 01，记为 m1
pq对应 10，记为 m2 pq对应 11，记为 m2
由三个命题变元 p, q, r生成的 8个极小项为：
pqr对应 000，记为 m0 pqr对应 001，记为 m1
pqr对应 010，记为 m2 pqr对应 011，记为 m3
pqr对应 100，记为 m4 pqr对应 101，记为 m5
pqr对应 110，记为 m6 pqr对应 111，记为 m7
【定义 】若析取范式中的简单合取式都是极小项，则称该析取范式为主析取范式。
【定理 】任何命题公式存在唯一的主析取范式。
求一个公式的主析取范式是：
[1] 先求该公式的一个析取范式。
[2] 如果该析取范式的某个简单合取式 A中既不含某个命题变元 p，也不含它的否定
p，则该简单合取式变为如下形式：(Ap)(Ap)。
[3] 消除重复出现的命题变元或命题变元的否定，矛盾式及重复出现的极小项，并将每
个极小项的命题变元或其否定按下标顺序或字典顺序排列。
【例子 】求命题公式的主析取范式
(1).求(pq)(pr)的主析取范式
(2).求(pq)(pr)的主析取范式
【解答】(1)根据例子 知(pq)(pr)的一个析取范式是(pr)(qp)(qr)，
我们将其中的每个简单合取式展开为含有所有命题变元的极小项的析取：
(pr)展开为(pqr)(pqr) (qp)展开为(pqr)(pqr)
(qr)展开为(pqr)(pqr)
因此(pq)(pr)的主析取范式为(pqr)(pqr)(pqr)(pqr)，按
极小项所对应的二进制数的大小重新排列为(pqr)(pqr)(pqr)(pqr)。
(2)根据例子 知(pq)(pr)的一个析取范式为(p)q(pr)，将其中每个简单
合取式展开为含有所有命题变元的极小项的析取：
(p)展开为(pqr)(pqr)(pqr)(pqr)
q展 开 为 (pqr)(pqr)(pqr)(pqr) (pr)展 开 为
(pqr)(pqr)
因此(pq)(pr)的主析取范式为：
(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pq
r)
主析取范式也可从命题公式的真值表更容易地得到，对应地，根据命题公式的主析取范
式也可容易地构造其真值表、判定其类型（矛盾式、可满足式还是永真式）等。
关于极大项、主合取范式等有关内容学生根据教材自学。
作业：教材 p60的 9, 10, 11, 15, 17。
7. 命题演算系统
命题演算系统是研究利用命题逻辑公式进行推理的形式系统。这里的推理指的是前提和
结论之间的逻辑关系，因此这种形式系统本身不注重前提本身的正确性，而关心的是是否能
从前提有效地推出结论，讨论什么是结论的有效证明。前提本身的正确性要在赋予形式系统
一定的解释的基础上才能确定，这种解释可以说是形式系统的语义。命题演算系统作为一个
形式系统研究如何从公理，通过有限的规则来构造有效的证明，这种证明仅仅是符号的改写，
本身没有什么含义。
一个形式系统包括符号表、公式、公理及规则，符号表定义形式系统所使用的所有符号，
公式是符号表上字符串，公式定义哪些字符串是形式系统所研究的合法对象。公理是构造一
切证明的前提，公理本身的正确性在形式系统中不关心，认为是不证自明的公式。当然在构
造形式系统的时候，公理的选择是一定的外在依据的。规则是从公理出发构造形式系统中定
理的方法。定理就是从公理出发，使用规则能够构造出有效证明的公式，形式系统就是研究
能够得到什么定理。
【定义 】命题演算系统 P定义为：
1. P的符号表包括：
[1].命题变元：小写英文字母并可加下标
[2].联结词：、
[3].辅助符号：(, )（园括号）
2. P的公式归纳定义为：
[1].命题变元是公式
[2].若 A是公式，则(A)也是公式
[3].若 A和 B是公式，则(AB)也是公式
[4].所有公式都是通过有限次使用[1]、[2]和[3]得到。
3. P的公理有如下三类：
[A1]. (A(BA))
[A2]. ((A(BC))((AB)(AC))
[A3]. (((A)(B))(BA))
4. P的规则只有一条：
[M]. 分离规则：由 A和(AB)可得到 B
□
【注解】关于以上定义，需要注意以下几点：
1. 在系统 P中只使用联结词和，这使得系统 P比较简单，但也失去了使用另外三
个联结词、和的方便之处，为此可作如下约定，对于 P中公式 A和 B：
(AB)代表((A)B) (AB)代表(((A)(B))) (AB)代表((AB)(BA))
注意，、和不是系统 P的符号，只不过是为了使用方便而引入的符号。
2. 上述给出的公理是一种模式，其中每一条公理实际上代表了无限多个公式，因为其
中的 A, B, C是一个符号，实际上可代表任意的公式，例如对于[A2]，其中 A可代表 BC
得到：
(((BC)(BC))(((BC)B)((BC)C))
注意在使用公式 A替换公式 B的符号 C时，要将公式 A替换 B中所有的 C。同样分离规则也
是一个模式。
【定义 】命题演算系统 P中的证明是由 P中公式组成的一个序列：
A1, A2, …, An
使得对每个 i(1 i n)，下列两个条件之一成立：
(1).Ai是公理，或者
(2).Ai是由上述序列中 Ai之前的某两个公式 Aj, Ak(1 j, k n)应用分离规则(M)得
到。
此时 A1, A2, …, An称为 An的一个证明，而 An称为 P的一个内定理，记为├An。
□
【注解】关于以上定义，需要注意以下几点：
1. ├也不是 P中的符号，只是用├An来表明 An是一个内定理。
2. 所谓的用两个公式 Aj, Ak应用分离规则(M)得到，是指{Aj, Ak} = {Aj, AjAi}或
{Aj, Ak} = {Ak, AkAi}。
3. 若 A1, A2, …, An是 An的一个证明，则对每个 Ai(1 i n)都有├Ai。
4. P的每个公理都是 P中的内定理。
5. 要证明一个公式 A为 P的内定理，只要给出 A的证明序列即可。
【例子 】设 A, B是 P中的公式，证明：├(AB)(AA)
【证明】
(1).├A(BA) // 公理[A1]
(2).├(A(BA))((AB)(AA)) // 公理[A2]，其中 C用 A代替
(3).├(AB)(AA) // 分离规则(M)及(1)和(2)
【例子 】设 A是 P中的公式，证明：├(AA)
【证明】
(1).├A((BA)A) // 公理[A1]
(2).├(A((BA)A))((A(BA))(AA)) // 公理[A2]
(3).├((A(BA))(AA)) // 分离规则(M)及(1)和(2)
(4).├(A(BA) // 公理[A1]
(5).├(AA) // 分离规则(M)及(3)和(4)
【定理 】设 A, B, C是 P中的三个公式：
[1].若├A，且├AB，则├B
[2].若├AB，且├BC，则├AC
【证明】[1]就是分离规则。对于[2]，证明如下：
(1).├(BC)(A(BC)) // [A1]
(2).├(BC) // 前提
(3).├(A(BC)) // 分离规则
(4).├(A(BC))((AB)(AC)) // [A2]
(5).├(AB)(AC) // 分离规则
(6).├(AB) // 前提
(7).├(AC) // 分离规则
□
以后称此定理的[2]为传递规则(Tr)。
【例子 】证明：├(A)(AB)
【证明】
(1).├(A)((B)(A)) // [A1]
(2).├((B)(A))(AB) // [A3]
(3).├(A)(AB) // 传递规则
【例子 】证明：
[1].├(A)A
[2].├A(A)
【证明】[1]的证明如下：
(1).├(A)(AA) // 例子
(2).├(AA)(AA) // [A3]
(3).├(A)(AA) // 传递规则
(4).├(A(AA))((AA)(AA))// [A2]
(5).├(AA)(AA) // 分离规则
(6).├(AA) // 例子
(7).├(AA) // 分离规则
[2]的证明如下：
(1).├(A)(A) // [1]
(2).├(AA)(AA) // [A3]
(3).├AA // 分离规则
【注解】通过以上例子，我们可发现在构造公式的证明中可使用如下方法：
1. 可灵活地使用公理，公理中的每个符号代表的是无限多的公式，公理中某个符号的
所有出现可用某个公式替换。但这与教材 p43页的置换规则不同，教材没有为命题逻辑公式
的推理建立形式系统，而是根据命题逻辑公式的真值来讨论推理，因此有所谓的等值公式的
置换，而我们这里所定义的形式系统还没有涉及到真值赋值，这里的证明仅仅是符号的改写。
建立形式系统的方法更符合计算机的思维方式，因为程序从本质来说也是个形式系统，
计算机将输入变换到输出也只是符号的改写，至于程序员所认为的程序功能，是程序员赋予
程序的解释，这种解释计算机并不理解。也就是说，对于计算机学科，形式系统的推导和形
式系统的含义是分开的，正是这种分离，才使得形式系统的推导可由计算机来机械地完成，
而人们又可以赋予形式系统各种各样的解释来完成人们所需要的功能。
2. 可使用分离规则和传递规则来构造证明。
3. 可使用已经证明过的内定理作为前提，这相当于教材 p43页的结论引入规则。
4. 教材中所讨论的推理是在某种前提下的推理，下面我们在命题演算系统 P中来定义
这种推理。
【定义 】设是 P中的一个公式集，称 P中的公式序列：
A1, A2, …, An
为前提下推出 An的一个证明，如果对每个 i(1 i n)，下列三个条件之一成立：
(1).Ai是公理，或者
(2).Ai，或者
(3).Ai是由上述序列中 Ai之前的某两个公式 Aj, Ak(1 j, k n)应用分离规则(M)得
到。
此时记为├An。
□
【注解】对于上述定义，我们需要注意以下几点：
1. 中的公式不一定是 P中的公理或内定理，也不一定是有限集合。可以说是假设
的前提，在前提下的证明实际上是将中的公式当作“临时公理”的一个证明。
2. 易证：当 = 时，├A当且仅当├A，或者说├A就是没有前提的证明。
3. 易证：对 P中的任意公式 A及公式集和'，若'，且'├A，则有├A。
4. 易证，若 A，则有├A。
【例子 】证明：{A, B(AC)}├(BC)
【证明】
(1).A // 前提
(2).A(BA) // 公理[A1]
(3).(BA) // 分离规则: (1)和(2)
(4).(B(AC)) // 前提
(5).(B(AC))((BA)(BC)) // 公理[A2]
(6).(BA)(BC) // 分离规则: (4)和(5)
(7).(BC) // 分离规则: (3)和(6)
下面利用上述定义和定理来形式化地讨论教材 p42中给出的推理定律的正确性。这里形
式化的含义是不通过对公式的真值讨论，而只是根据 P系统的公理和分离规则来证明那些推
理定律，当然证明时允许使用我们已经证明过的内定理。为此，我们首先给出命题演算系统
中最重要的一条定理，即演绎定理，通过演绎定理可将在某个前提下的证明与 P系统中的
内定理相联系起来，并简化内定理的证明。
【定理 （演绎定理）】设是 P中的公式集，A和 B是 P中的两个公式，若{A}├
B，则├AB。
【证明】略。 □
【定理 （演绎定理的逆定理）】设是 P中的公式集，A和 B是 P中的两个公式，
若├AB，则{A}├B。
【证明】略。 □
由以上两个定理，我们得到：
【推论 】{A1, A2, …, An}├A当且仅当├(A1(A2…(AnA)…))
□
当 = {A1, A2, …, An}时，我们通常将├A写为 A1, A2, …, An├A。
根据演绎定理，分离规则可表示为 A, AB├B，或用内定理表示为├A((AB)B)。
对于传递规则，可推广为：
【定理 】设是 P中的公式集，A1, A2, …, An为 P中的公式，若有├A1, ├
A2, …, ├An，且 A1, A2, …, An├A则├A。
【证明】略。 □
对于上述定理 , , 的证明可参考王悍贫编著的《离散数学第一分册
——数理逻辑》（北京大学出版社，1997）的 p70-75。我们可将├A1, ├A2, …, ├An
简记为├A1, A2, …, An。
【例子 】证明：{AB, A}├ (B)
【证明】
(1). (A)A // 例
(2).A // 前提
(3).A // (1)使用演绎定理，然后使用分离规
则
(4). AB // 前提
(5).B // 分离规则
(6).B(B) // 例
(7).B // 演绎定理及分离规则
由此可得：├(AB)(AB)，又由于├(AB)(BA)（公理[A3]）
得到├(AB)(BA)。
【例子 】证明：├A(B(AB))
【证明】
(1).├A((AB)B) // 分离规则的内定理形式
(2).├((AB)B)(B(AB)) // 例子
(3).├(B(AB)) // 传递规则
【定理 】合取的引入和消除：
[1].A, B├AB // 合取的引入
[2].AB├A, B（这代表 AB├A及 AB├B）。 // 合取的消除
【证明】首先注意到 AB是(AB)的简写，即(AB)的简写。要证明[1]，根据
演绎定理知就是要证明├A(B(AB))，这由例子 可得（将其中的B换成 B即
可）。要证明[2]，只要证明 AB├A即可，因为 AB├B可同理得证。要证明 AB├A，按演
绎定理，即要证├((AB))A，而根据例子 有├(A)(AB)，而根据公理[A3]
有├(A)(AB)(((AB))A)，根据传递规则有├((AB))A，再根
据例子 有├(AA)，再根据传递规则得├((AB))A。
□
实际上教材中的符号就是这里的├，再根据定理 就有教材 p42的假言推理就是
分离规则，合取的化简就是定理 ，拒取式就是例子 ，假言三段论就是传递规则。
下面给出关于析取的规则的证明，为此我们先给出下面几个例子：
【例子 】证明：AB, AB, A├C
【证明】
(1).A // 前提
(2).AB // 前提
(3).B // 分离规则
(4).AB // 前提
(5).B // 分离规则: (1)和(4)
(6).B(BC) // 例子
(7).BC // 分离规则: (5)和(6)
(8).C // 分离规则: (7)和(3)
该例子的直观含义是，如果从命题 A能推出 B及 B的否定，那么 A能推出任何公式。由
此可得到├(AB)((AB)(AC))。
【例子 】证明：AB, AB├B
【证明】
(1).(AB)(BA) // 例子
(2).AB // 前提
(3).BA // 分离规则
(4).(AB)(BA) // 公理[A3]
(5).AB // 前提
(6).BA // 分离规则: (4)和(5)
(7).(BA)((BA)(B(AB))) // 例子
(8).(BA)(B(AB)) // 分离规则: (3)和(7)
(9).B(AB) // 分离规则: (6)和(8)
(10). (B(AB))((AB)B)) // 公理[A3]
(11). (AB)B // 分离规则: (9)和(10)
(12). B // 分离规则: (2)和(11)
该例子的直观含义是，如果命题 B既能从 A推出，又能从A推出，那么 B就是永真的。
由此可得到├(AB)((AB)B)。
这样我们可证明关于析取的重要定理：
【定理 】析取的引入和消除：
[1].A├AB, A├BA // 析取的引入，教材 p42中的附加定律
[2].AB, CB, AC├B // 析取的消除
【证明】注意 AC是(AC)的简写，那么根据演绎定理，[1]的前一个式子就是例子
，后一个式子则是公理[A1]。而[2]的证明如下：
(1).AC // 前提 AC
(2).CB // 前提
(3).AB // 分离规则
(4).AB // 前提
(5).B // 例子
□
根据演绎定理，定理 的[2]也可陈述为，若有 A├B，且 C├B，那么有 AC├B。根
据该定理，我们可得到教材 p42中关于析取的其他定律：
【例子 】证明：
[1].AB, B├A // 析取三段论
[2].AB, CD, AC├BD // 构造性二难推理
【证明】[1]的形式是AB, B├A，这可证明如下：
(1).(AB)(BA) // 公理[A3]
(2).AB // 前提
(3).BA // 分离规则
(4).B // 前提
(5).A // 分离规则
(6).AA // 例子
(7).A // 分离规则
[2]的证明如下：
(1).AB // 前提
(2).BBD // 定理 ，析取的引入
(3).ABD // 分离规则
(4).CBD // 与(1)~(3)类似
(5).AC // 前提
(6).BD // 定理 ，析取的消除
【例子 】证明：├(AA)A
【证明】只要证(AA)├A
(1).A(A(AA)) // 例子
(2).(A(A(AA)))((AA)(A(AA))) //公理[A2]
(3).((AA)(A(AA))) //分离规则
(4).AA // 前提
(5).A(AA) // 分离规则: (3)和(4)
(6).(A(AA))((AA)A) // 公理[A3]
(7).(AA)A // 分离规则: (5)和(6)
(8).A // 分离规则: (4)和(7)
【例子 】证明：AB, AB├A
【证明】
(1).(AB)((AB)(AA)) // 例子
(2).(AB) // 前提
(3).(AB)(AA) // 分离规则
(4).AB // 前提
(5).(AA) // 分离规则: (3)和(4)
(6).(AA)A // 例子
(7).A // 分离规则: (5)和(6)
读者可很容易地看出，教材 p46的附加前提证明法就是演绎定理的特殊形式，而归谬法
则相当于例子 .
最后我们来讨论命题演算系统的元问题，即该形式系统的可靠性、一致性和完备性。可
靠性是指命题演算系统 P中的内定理是否都是永真式，一致性是指 P是否存在公式 A，使得├
A和├(A)都成立，如果存在这样的公式，则由例子 知 P可推出任何公式，这时 P便
没有任何意义。完备性是指 P是否能推出命题逻辑公式的所有永真式。下面定理说明 P是可
靠的、一致的和完备的。
【定理 】对于 P的任意一个公式 A，若有├A，则 A是一个永真式。 □
【定理 】不存在 P的一个公式 A，使得├A和├(A)都成立。 □
【定理 】若 A是 P的永真式，则有├A。 □
有了定理 之后，要看一个公式 A是否是内定理，只要使用真值表的方法检查 A是
否是永真式即可。定理 表明我们在这里构造的形式系统与教材中的推理理论是完全一
致的，但正如前面所指出的，形式系统的构造才是计算机学科的核心思想。关于命题逻辑的
推理理论的实际应用关键在于将实际中的陈述句符号化，具体的例子请读者自己参考教材。
作业：教材 p63-64的 23, 24, 25。
7. 命题逻辑的推理理论
命题逻辑的推理理论就是利用命题逻辑公式研究什么是有效的推理。
推理是从前提出发推出结论的思维过程，前提是已知的命题公式，结论是从前提出发应
用推理规则推出的命题公式。
如果前提是真命题，从前提出发推出结论的推理过程严格遵守推理规则，则推出的结论
也是真命题。
在命题逻辑中，不注重前提和结论的真假性，而关心从前提推出结论的推理过程的正确
性，即主要研究推理的规则。
【定义 】称蕴涵式(A1A2…Ak)B为推理的形式结构，A1, A2, …, Ak为推理的
前提，B为推理的结论。若(A1A2…Ak)B为永真式，则称从前提 A1, A2, …, Ak推出结
论 B的推理正确（或说有效），B是 A1, A2, …, Ak的逻辑结论或称有效结论，否则称推理
不正确。若从前提 A1, A2, …, Ak推出结论 B的推理正确，则记为(A1A2…Ak)B。
直观地看，(A1A2…Ak)B就是说，如果 A1, A2, …, Ak都正确，则 B也正确。
判断推理是否正确就是验证相应的蕴涵式是否是永真式，其方法包括：
·使用真值表
·等值演算法
·求主析取范式法
【例子 】教材 p39例 ，要点：将各种命题符号化，然后使用上述各种方法判
断相应的蕴涵式是否是永真式。
【定义 】证明是一个描述推理过程的命题公式序列 A1, A2, …, An，其中的每个命
题公式或者是已知的前提，或者是由某些前提应用推理规则得到的结论，满足这样条件的公
式序列 A1, A2, …, An称为结论 An的证明。在证明中常用的推理规则有 3条：
[1].前提引入规则：在证明的任何步骤都可以引入已知的前提；
[2].结论引入规则：在证明的任何步骤都可以引入这次已经得到的结论作为后续证明的
前提；
[3].置换规则：在证明的任何步骤上，命题公式中的任何子公式都可用与之等值的公式
置换，得到证明的公式序列的另一公式。
使用命题逻辑公式进行推理还有其他一些推理规则，这些规则建立在下面一些推理定律
上：
【定理 】推理定律是命题逻辑的一些永真蕴涵式，重要的推理定律有：
[1].附加律： A(AB) // 或称为析取的引入
[2].化简律： (AB)A, (AB)B // 或称为合取的消除
[3].假言推理： (AB)AB // 或称为分离规则
[4].拒取式： (AB)BA
[5].析取三段论：(AB)BA
[6].假言三段论：(AB)(BC)(AC) // 或称为传递规则
[7].等价三段论：(AB)(BC)(AC)
[8].构造性二难：(AB)(CD)(AC)(BD)
【注解】
1. 这些推理定律都是永真式，可用判断命题公式是否是永真式的方法加以证明。
2. 这些推理定律之间不是独立的，其中一些定律可从另外一些定律推出，正如我们在
命题演算系统中所讨论的，最基本的定律应该命题演算的公理及分离规则。对于上面给出的
这些定律，最重要的是附加律、分离规则、传递规则、拒取式等。正如教材 p44的例
所证明的，构造性二难规则可使用传递规则、置换规则等证明。而拒取式与析取三段论实际
上等价，因为(AB)(AB)，那么根据拒取式有(AB)BA，而AA。
3. 实际上这些推理定律中的符号 A, B, C可代表任意公式，即将推理定律中某个符号
的所有出现用另外一个命题公式代入，那么得到的也是永真式，这个规则可称为代入规则。
注意代入规则与置换规则不同。
【定理 】根据定理 的推理定律得到，在证明中可使用以下一些推理规则：
[1].假言推理规则（分离规则）：若有 AB和 A，则可得到 B。（注意证明是命题公式
的序列，因此这里的意思是，如果序列中出现 AB和 A，则可在该序列中添加公式 B，或换
句话，按照证明的意思就是，如果有前提 AB和 A，则可得到结论 B）
[2].附加规则：若有 A，则可得到 AB。
[3].化简规则：若有 AB，则可得到 A，也可得到 B。
[4].拒取式规则：若有 AB和B，则可得到A。
[5].假言三段论（传递规则）：若有 AB及 BC，则可得到 AC
[6].析取三段论规则：若有 AB和B，则可得到 A。
[7].构造性二难规则：若有 AB，CD和 AC，则可得到 BD。
[8].合取引入规则：若有 A和 B，则可得到 AB。
【注解】
1. 假言推理规则就是最常用的推理方法，例如，如果天下雨(A)，地就是湿的(B)，现
在天下雨，所以地是湿的。
2. 附加规则、化简规则及合取引入规则的直观含义很简单。
3. 拒取式规则就是通常所使用的反证法，即从 A可推出 B，但如果我们已经有了 B的
否定(B)作为前提，那么我们就有理由相信A是成立的。例如，如果天下雨地就是湿的
(AB)，但现在地没有湿(B)，所以天没有下雨(A)。
4. 假言三段论表明推理的传递性，也是常用的一种三段论（亚里斯多德的《工具论》
中共总结出 24中三段论的形式），例如，如果天下雨(A)，路就会很难走(B)，路很难走，我
上学就会迟到(C)，所以如果天下雨我上学就会迟到。
5. 析取三段论本质上与拒取式一致，但在逻辑上通常称为选言推理，或者更通俗地称
为排除法，例如，今天我要么去开会(A)要么去上课(B)，我不去上课(B)，所以我去开会
(A)。实际上这里假定前提 AB已罗列了所有可能情况，因为这只是一种推理模式，因此这
种假定是合理的，具有一般性。
6. 构造性二难推理是析取三段论的推广，例如如果派小王参加比赛(A)我们就可得到
第一名(B)，如果派小张参加比赛(C)就可得到第三名(D)，我们要么派小王去比赛，要么派
小张去比赛，所以我们不是得到第一名就是得到第三名。一种极端的二难推理形式是，有
AB和AB，那么就可得到 B，因为 AA是永真的。
【例子 】教材 p44例 ，该例子的前提和结论都是符号化的命题公式。如何从
前提构造地证明结论没有固定的程式，这里也很难从结论到推到前提，需要敏锐的直觉和丰
富的经验。
【例子 】教材 p45例 ，该例子需要先将命题符号化。
教材 p46的附加前提证明法相当于下面的演绎定理：
【定理 ，演绎定理】(A1A2…AkA)B当且仅当(A1A2…Ak)AB。
利用演绎定理，许多命题公式，特别是蕴涵式的证明可得到简化，我们可将蕴涵式的前
件作为前提引入来进行证明。
【例子 】教材 p46例 ，该例子需要先将命题符号化，要证明的结论是一个蕴
涵式，可将蕴涵式的前件作为已知的前提来构造蕴涵式的后件的证明。
【例子 】验证下述推理是否正确：
或者逻辑学难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑学并不难学。
因此如果许多学生喜欢逻辑，那么数学并不难学。
【解答】先将命题符号化，首先抽取的基本命题包括：
A: 逻辑学难学 B: 有少数学生不喜欢逻辑学 C: 数学容易学
则前提是 AB，CA，要证明的结论是BC，可进行如下的验证：
(1).B // 按照演绎定理，引入结论的前件B作为前提
(2).AB // 已知的前提
(3).A // (1)和(2)及析取三段论
(4).CA // 已知的前提
(5).C // (3)和(4)及拒取式
得到结论的后件，因此从前提可有效地推出结论，因此整个推理正确。
归谬法是反证法的推广，特别适合结论是否定式的时候。它基于下述定理：
【定理 】 (A1A2…Ak)B当且仅当(A1A2…AkB)是永真式，或者说
(A1A2…Ak)B当且仅当(A1A2…AkB)是矛盾式。
【例子 】教材 p48的例 。
最后给出一些综合的例子。
【例子 】教材 p57的例
【例子 】构造下列推理的证明
前提：AB, BC, AD, D，结论：C(AB)
【解答】
根据合取引入规则，因为已经有前提 AB，所以只要推出结论 C即可：
(1).AD // 已知的前提
(2).D // 已知的前提
(3).A // 拒取式
(4).AB // 已知的前提
(5).B // 析取三段论
(6).BC // 已知的前提
(7).C // 分离规则
作业：教材 p63-64的 23, 24, 25。
二、一阶逻辑(First-order Logic)
1. 概述
·一阶逻辑讨论的内容与命题逻辑类似，一阶逻辑又称为谓词逻辑(Predicate Logic)。
·为什么要引入一阶逻辑？因为简单命题需要进一步分析，才能更好地反映现实世界中
人们所使用的推理模式。
·一阶逻辑的基本概念：个体、函数、谓词、量词，在一阶逻辑中符号化命题。
·一阶逻辑公式及其解释（赋值）
·一阶逻辑公式的等值演算与范式
·一阶逻辑公式的推理理论：使用一阶逻辑公式进行推理。
2. 一阶逻辑的基本概念
命题逻辑中，命题是最基本的单位，不再分解，不再考虑命题内部各成份之间的关系，
这样忽略了命题本身的丰富内含，使得有些直觉上很正确的推理在命题逻辑中无法描述。
【定义 】一阶逻辑中，命题被分解为个体和谓词两部分。个体(individuals)是指
可独立存在的客体，可以是一个具体的事物，也可以是一个抽象的概念。而谓词(predication)
是用来刻划个体词的性质及事物关系的词。
【注解】
1. 一阶逻辑建立在命题逻辑之上，当命题逻辑中的命题具有丰富的内含时，需要一阶
逻辑公式来符号化它。
2. 命题是陈述句，在自然语言中，通常陈述句有主语、谓语和宾语，主语和宾语都可
能是个体，而谓语及其相连的宾语通常被看成是谓词。（参考书中的例子）
3. 在一阶逻辑中还可描述对个体所进行的某种变换，即引入所谓函词，例如命题：
的平方是非负数
其中是一个体，的平方也是一个体，它通过对做某种操作（变换）而得到，为了刻划这
种变换，引入所谓函词的概念。
4. 函词与谓词不同，函词作用在个体上，而产生另一个个体，而谓词作用在个体上之
后产生的是一个命题。例如上面命题中，“…的平方”是函词，而“…是非负数”则是一个
谓词。“的平方”是一个体，而“的平方是非负数”则是一个命题。
5. 所谓的个体常项是表示具体或特定的个体的个体词，而个体变项是表示抽象或泛指
的个体词。个体变项的取值范围称为个体域，后面看到当个体域不同时，一阶逻辑公式的含
义不同。为了使公式有一致的含义，可引入一个全总域，表示宇宙间所有个体所组成的域。
在某些情况下，全总域也可指所讨论的问题范围内的所有个体。
6. 表示具体性质或关系的词称为谓词常项，表示抽象性质或关系的词称为谓词变项。
7. 在一阶逻辑中，谓词变项和谓词常项的区别并不重要，正如在命题逻辑中，命题常
项和命题变项的区别不重要一样，这是因为在一阶逻辑中不能对谓词做某些变换（操作），
或者说在一阶逻辑上不能在谓词集合上定义函数。但在个体域上可定义函数，因此个体常项
与个体变项的区别显得比较重要。
8. 实际上，所谓一阶逻辑的“一阶”的含义就是指其中的函数只能作用在个体上，或
者说其中的变量只能代表取值于个体，如果允许函数作用在谓词上，则变成二阶或高阶（进
一步允许函数作用在函数本身上）逻辑。
9. 可以说，一阶逻辑一个很重要的特点是在个体域上引入了变量。个体变量既可作为
谓词作用的对象也可作为函数作用的对象。一阶逻辑中的阶的含义在某种意义上是指个体处
于 0阶，而对个体的判断（即命题）处于一阶，一阶逻辑中的函数作用于 0阶的个体而得到
个体，而谓词作用于个体得到处于一阶的命题。
10. 谓词可包含的个体变项个数称为谓词的元数，例如“…是非负数”是一元谓词，而“…
和…是好朋友”是二元谓词。通常来说，二元以上的谓词比较少见，而且通常可用二元谓词
来表示。
【例子 】分析命题中的个体和谓词，并将命题在一阶逻辑中符号化：教材例
【定义 】在一阶逻辑中用量词(quantifier)来刻划参与判断的个体的数量。对于谓
词所作用的个体数量，一阶逻辑只关心两种情况，一种情况是谓词作用个体域中所有的个体，
这时用全称量词(universal quantifier)(使用符号'')来刻划，一种情况是谓词作用个体
域中某些个体，这时用存在量词(existential quantifier)(使用符号'')来刻划。
【注解】
1. 一阶逻辑中，不关心个体的具体数量，而只关心谓词是作用于个体域中的所有个体，
还是某些个体。显然如果谓词不作用于个体域中任何个体，则可用存在量词再加上否定来表
示。
2. 在一阶逻辑中量词只限制被谓词所作用的个体的数量，它不限制被函数作用的个体
数量，实际上函数总是存在自己的定义域和值域，它可作用域在定义域中的任意个体。
3. 量词与个体域总是联系在一起的，因此使用不同的个体域，同一命题可能在一阶逻
辑中有不同的符号化形式，但总可使所有的个体变量的个体域为全总域，并通过引入合适的
特性谓词来从全总域中分离出可使用量词限制的合适个体域来。教材 p70页的例子。注意所
谓全总域，有时可认为讨论范围内的所有个体所组成的集合。
4. 量词是有顺序的，不能将量词的顺序随意颠倒。教材 p71页的说明。实际上，谓词
中的个体变项也是有顺序的，例如“…比…跑得快”，表示为 F(x, y)，即“x比 y跑得快”，
显然 x和 y不能随意颠倒。
【例子 】在一阶逻辑中将命题符号化，教材例 、例 、例 、例
【例子 】将下列命题符号化：
[1].凡是有理数都可写成分数
[2].教室里有同学在讲话
[3].对于任意的 x, y，都存在唯一的 z，使得 x+y=z
[4].在我们班中，并非所有同学都能取得优秀成绩
[5].有一个整数大于其他每个整数
[6].任给 > 0，存在 > 0，如果|x-a|<，则|f (x)-b|<
【解答】
[1].令谓词 Q(x)表示 x是有理数，F(x)表示 x可写成分数，则符号化为：
(x)(Q(x)F(x))
注意不是(x)(Q(x)F(x))，更不是((x)Q(x))F(x)
[2].令谓词 S(x)表示 x在教室里，T(x)表示 x在讲话，则符号化为：
(x)(S(x)T(x))
注意不是(x)(S(x)T(x))，更不是 S(x)(x)(T(x))
[3].符号化为：(x)(y)(z)((x+y = z) (u)((u = x + y) (u = z)) )
[4].令谓词 C(x)表示 x在我们班中，E(x)表示 x能取得优秀成绩，则符号化为：
((x)(C(x)E(x)))
此命题与“我们班中存在不能取得优秀成绩的同学”等价，该命题可符号化为：
(x)(C(x)E(x))
由此可知((x)(C(x)E(x)))和(x)(C(x)E(x))等值，即全称量词和存在量词存
在某种等值变换关系。
[5].用 Z(x)表示 x是一个整数，则可符号化为：
(x)(Z(x) (y)(Z(y) (x>y) ) )
[6].符 号 化 为 ： ()(( > 0)( )(( >0) ((|x-a|< ) (f
(x)-b|<)) ) )
【例子 】将下列命题符号化：
[1].每一个有理数都是实数
[2].某些实数是有理数
[3].不是没一个实数都是有理数
[4].存在偶素数
[5].会叫的狗未必会咬人
[6].每个人的外祖母都是他母亲的母亲
[7].任何自然数的后继数必大于零
[8].有些液体能溶解任何金属
[9].任何金属均可溶解于某种液体中
[10]. 没有不犯错误的人
[11]. 小莉是非常聪明和美丽的
[12]. 小李是一个田径运动员
【解答】（请同学们下载后，先思考，课堂上讲解）
【例子 】将下列公式翻译成自然语言，并确定其真值，这里假定个体域是正整数：
[1].(x)(y)G(x, y)，其中 G(x, y)表示：x * y = y。
[2].(x)(y)F(x, y)，其中 F(x, y)表示：x + y = y。
[3].(x)(y)H(x, y)，其中 H(x, y)表示：x + y = x。
[4].(x)(y)L(x, y)，其中 L(x, y)表示：x * y = x。
[5].(x)(y)M(x, y)，其中 M(x, y)表示：x * y = 1。
[6].(x)(y)N(x, y)，其中 N(x, y)表示：y = 2 * x。
【解答】（请同学们下载后，先思考，课堂上讲解）
【例子 】给定下述谓词，请把下列公式翻译成自然语言：
P(x): x是素数 E(x): x是偶数
Q(x): x是奇数 N(x, y): x可以整除 y
[1].P(5)
[2].E(2)P(2)
[3].(x)(N(2, x)E(x))
[4].(x)(E(x)N(x, 6))
[5].(x)(E(x) N(2, x))
[6].(x)(E(x)(y)(N(x, y)E(y)))
[7].(x)(P(x)(y)(Q(y)N(y, x)))
[8].(x)(Q(x)(y)(E(y)N(y, x)))
【解答】（请同学们下载后，先思考，课堂上讲解）
作业：教材 p101-102的 1, 2。
3. 一阶逻辑公式及解释
每个系统有它自己的符号表，由这些符号表所构成的某些符号串是该系统中的语言，也
是我们所研究的目标语言。
【定义 】一阶逻辑语言的符号包括：
[1].个体常项：通常用排在前面的小写字母表示，a, b, c, …, ai, bi, ci, …
[2].个体变项：通常用排在后面的小写字母表示，x, y, z, …, xi, yi, zi, …
[3].函数符号：通常用排在中间的小写字母表示，f, g, h, …, fi, gi, hi, …
[4].谓词符号：通常用排在中间的大写字母表示，F, G, H, …, Fi, Gi, Hi, …
[5].量词符号：全称量词、存在量词
[6].联结符号：、、、、
[7].辅助符号：(、)、,(逗号)
【注解】
1. 上述符号可分为两大类，一类是非逻辑符号，包括个体常项、函数符号、谓词符号
等，一类是逻辑符号，包括个体变项、量词符号、联结符号、辅助符号等。
2. 在命题逻辑只有逻辑符号，而没有任何非逻辑符号，命题逻辑中的命题常项和命题
变量的区分是非本质的，对于命题逻辑本身来说没有什么意义，正如在一阶逻辑中，谓词常
项和谓词变项的区分也是非本质的，对于一阶逻辑来说没有什么意义，但个体常项和个体变
项的区分是本质的，对于一阶逻辑来说有重要的意义。
3. 一阶逻辑中的逻辑符号对于将一阶逻辑应用于任何问题时都是通用的、不变的，而
其中的非逻辑符号则在不同的应用问题（或者说不同的讨论范围）中有所不同，可以变化，
因此一阶逻辑语言的表达能力是非常强的，它可通过采用不同的非逻辑符号来增强自己的表
达能力。
【定义 】一阶逻辑语言的项(term)递归定义为：
[1].个体常项和个体变项是项；
[2].若 f (x1, x2, …, xn)是 n元函数，t1, t2, …, tn是 n个项，则 f (t1, t2, …,
tn)是项；
[3].一阶逻辑语言的所有项都通过有限次使用上述两步生成。
【定义 】一阶逻辑语言的合式公式(well-formed formula)递归定义为：
[1].若 F(x1, x2, …, xn)是 n元谓词，t1, t2, …, tn是 n个项，则 F(t1, t2, …, tn)
是合式公式，此类合式公式称为原子公式；
[2].若 A、B是合式公式，则(A)、(AB)、(AB)、(AB)、(AB)也是合式公式；
[3].若 A是合式公式，则(x)A、(x)A也是合式公式；
[4].一阶逻辑语言的所有公式都通过有限次使用上述步骤生成。
通常用 r, s, t, ri, si, ti, …等表示项，而用 A, B, C, …Ai, Bi, Ci, …表示合式
公式。
【注解】
1. 一阶逻辑语言的合式公式随着采用不同的非逻辑符号而不同，但对于不同的非逻辑
符号采用相同的方式构造公式，一旦非逻辑符号确定之后，则一阶逻辑公式也就确定下来了，
所以可以说一阶逻辑公式是某个非逻辑符号集生成的语言。
2. 虽然说采用不同的非逻辑符号可生成不同的一阶逻辑公式，但所有一阶逻辑公式的
逻辑符号是相同的，而我们在这里对一阶逻辑的讨论只是讨论这些逻辑符号的性质，而与非
逻辑符号无关，则我们的讨论对于任意的非逻辑符号生成的一阶逻辑公式都是成立的。
3. 一阶逻辑语言的直观意义容易理解：“符号表”相当于英语的字母表，“项”相当
于单词或词组，它们不表达完整的判断，还只是代表个体，而“公式”则代表完整的句子。
而其中的函数符号用来构造复杂的个体（项），谓词符号则用来构造最原子的公式。
4. 在定义 的[4]中，没有要求个体变项 x一定要出现在合式公式 A中，因此下述
符号串都是合式公式：(x)F(x, y)、(z)F(x, y)。
5. 可通过假设联结符号及量词之间的优先级而去掉一些括号，使得公式的书写更为简
洁，约定：
(1).公式的最外层括号可省略；
(2).联结词的优先级高于，而高于，高于，高于，所以公式：
F(x, y)Q(y, z)F(y, z)G(y, x)Q(x, z)F(y, z)
表示：(((((F(x, y))Q(y, z))(F(y, z)))G(y, x))(Q(x, z)F(y, z)))，
但通常在书写时也不可将所有的括号省略，应该既比较简洁，又比较容易理解，例如上述公
式可写成：
((F(x, y)Q(y, z)F(y, z)) G(y, x)) (Q(x, z)F(y, z))
由于一阶逻辑语言的公式比较复杂，其中的括号比较多，请注意讲究书写的方法。
(3).A1A2…An-1An表示(A1(A2…(An-1An)…))。
(4).量词的优先级高于任何联结符号，所以(x)A、(x)A可分别写成xA、xA，
但要注意明确量词的辖域（下面定义什么是辖域）。
【定义 】称公式(x)A中的 A为量词(x)的辖域(scope)，称公式(x)A中的 A为
量词(x)的辖域。称变元 x在公式 A中的某处出现是约束出现，如果该出现处于量词(x)
或(x)的辖域内，或者就是量词中的 x。若 x在公式 A中的某处出现不是约束出现，则此出
现称为自由出现。
【例子 】(教材 p76的例 。)指出下列公式中，各量词的辖域以及变元的自由出
现和约束出现：
[1].x(F(x, y, z)yG(x, y))
[2].xF(x, y)G(x, y)
[3].xy(F(x)G(y)H(x, y))
【解答】
[1].量词x的辖域为：(F(x, y, z)yG(x, y))，而量词y的辖域为 G(x, y)。变
元的自由出现和约束出现分别为：
x (F( x, y, z) y G(x, y))
约束 约束 自由 自由 约束 约束 约束
[2].量词x的辖域为：F(x, y)。变元的自由出现和约束出现分别为：
x F( x, y) G(x, y)
约束 约束 自由 自由 自由
[3].量 词 x的 辖 域 为 ： y(F(x)G(y)H(x, y))， 量 词 y的 辖 域 为
(F(x)G(y)H(x, y))。变元的自由出现和约束出现分别为：
x y (F(x) G(y)H(x, y))
约束 约束 约束 约束 约束 约束
【定义 】设变元 x在公式 A中出现，如果 x在 A中的所有出现都是约束出现，则称
x为 A的约束变元(bounded variable)，否则称 x为 A的自由变元(free variable)。
【注解】
1. 变元 x在公式 A中可同时有约束出现和自由出现两种情况，而只有当 x的所有出现
都是约束出现时，称 x为 A的约束变元。
2. 为了明确起见，我们通常在用字母 A, B, C, …表示一阶逻辑公式时，同时列出该
公式中的自由变元，而写成 A(x1, x2, …, xn)等，表示公式 A中的所有自由变元皆在 x1,
x2, …, xn中。
3. 为了清晰起见，通常运用换名规则和替换规则使得公式 A满足下列条件：
(1).所有变元在公式 A中要么自由出现，要么约束出现，不要既有自由出现，又有约束
出现。
(2).所有量词后面采用的约束变元互不相同。量词后面的约束变元只在它的辖域里有意
义，处于其辖域以外的同名变元与该约束变元实际上无关。所以不同量词采用不同约束变元
是可以的，而且也是必要的。进一步变元的辖域实际上是可嵌套的，例如对于公式：
x(F(x)x(G(x)F(x)))
其中量词x的辖域为：(F(x)x(G(x)F(x)))，而量词x的辖域为(G(x)F(x))。实际
上在子公式(G(x)F(x))中的 x被量词x约束，而不是被量词x约束。实际上，上述公式
等价于：
x(F(x)y(G(y)F(y)))
在使用一阶逻辑公式符号化命题时，要小心地选择变元，以使得到的公式满足上述两个
条件。
【定理 】约束变元换名规则和自由变元替换规则：
[1].换名规则：对于公式(x)A或(x)A，设变元 y不在 A中出现，则将其中(x)或(x)
改为(y)或(y)，且将 A中出现的所有 x都改为 y，得到公式(y)A或(y)A与原公式等价。
[2].替换规则：对于公式 A(x)，设 y不在 A中出现，将其中所有自由出现的 x改为 y，
得到公式 A(y)与原公式等价。
【注解】
1. 这里的等价于后面要讲的等值（目前可参考命题逻辑公式的等值）不一样，等值建
立在某种解释下，而这里的等价只与语法有关，换名规则和替换规则只是在某种意义上说明
公式中使用的变元是可任意选择的，选择不同的变元对于公式的本质没什么改变，就象在编
写同一程序时，不同的程序员给具有同样功能的变量起不同名字一样，不影响程序本身的功
能。
【例子 】使用换名规则和替换规则变换下列公式，使得满足定义 的注解 3中的
两个条件：
[1].(x)((P(x)R(x))S(x))(x)(P(x)Q(x))
[2].(x)(P(x)Q(x))(x)R(x)S(x)
[3].(x)P(x)(x)Q(x)((x)P(x)Q(x))
【解答】首先确定量词的辖域，然后确定变元的约束出现和自由出现，再进行变换：
[1].(x)的辖域是((P(x)R(x))S(x))，其中的 x都是约束出现，而(x)的辖域是
(P(x)Q(x))，其中的 x是约束出现。为了使得不同量词后面的变元不同，可将
(x)(P(x)Q(x))中的 x换名为 y，得到：(x)((P(x)R(x))S(x))(y)(P(y)Q(y))。
[2].(x)的辖域是(P(x)Q(x))，其中的 x是约束出现，而(x)的辖域是 P(x)，其中
的 x是约束出现，而最后 S(x)中的 x是自由出现。为了满足上述两个条件，可将(x)R(x)
中的 x换名为 y，而将 S(x)中的 x替换为 z，得到：(x)(P(x)Q(x))(y)R(y)S(z)。
[3].第一个(x)的辖域是 P(x)，而(x)的辖域是 Q(x)，第二个(x)的辖域是 P(x)，
而最后 Q(x)中的 x是自由出现。为满足上述两个条件，可将(x)Q(x)中的 x换名为 y，而将
(x)P(x)中 的 x换 名 为 z， 最 后 将 Q(x)中 的 x替 换 为 u， 得 到 ：
(x)P(x)(y)Q(y)((z)P(z)Q(u))。
【定义 】如果公式 A没有自由变元，则称公式 A为闭公式(closed formula)。
一阶逻辑公式的含义（解释）显然比命题逻辑公式要复杂得多，因为一阶逻辑公式有非
逻辑的符号。对于一阶逻辑公式的解释依赖于一阶逻辑公式所基于的非逻辑符号。
设有非逻辑符号集 L，它由三部分组成 L = C F P：
(1).个体常项所组成的集合 C = {c1, c2, …, cn, …}；
(2).函数符号所组成的集合 F = { f1, f2, …, fn, …}，每个函数 fi有一个元数 n，
表明它是 n元函数；
(3).谓词符号所组成的集合 P = {F1, F2, …, Fn, …}，每个谓词 Fi有一个元数 n，表
明它是 n元谓词。
由该非逻辑符号集 L生成的项可记为 Term(L)，生成的公式可记为 Form(L)。为了确定
Form(L)中公式的真值，先要给出非逻辑符号集 L的解释。
【定义 】非逻辑符号集 L的一个解释[[L]]由四个部分组成：
[1].一个非空集合 D，D称为解释[[L]]的论域；
[2].对于 C的个体常项 c，其解释为[[c]] D是 D中的某个元素；
[3].对于 F的 n元函数 f，其解释是 D上的一个 n元函数：[[f ]] : DnD；
[4].对于 P的 n元谓词 F，其解释是 D上的一个 n元关系：[[F]] Dn(= D .. D)
【注解】
1. 定义 所给出的解释方法是对非逻辑符号集的一种最直观的解释，称为非逻辑
符号集 L的塔斯基(Tarski)语义，塔斯基是研究语义学的一个最有名的学者，这种语义解释
方法在各种自然语言及形式语言的语义研究中也被广泛使用。
2. 对 L的一个解释也可看成是为 L构造了一个模型，研究一个形式语言的模型的有关
内容构成了数理逻辑的一个重要分支：模型论(Model Theory)。
3. 教材 p79的定义 给出的定义实际是一个不严谨的、直观的定义，因为教材在此
之前没有引进函数、关系等概念。该定义的本质与我们这里的定义是一致的，因此根据书上
的记号，我们也用符号 I来表示某个解释。要说明的是，教材例 中所给定的谓词 F的为
F(2) = 0, F(3) = 1，实际上是表示 F = {3}D1(={2, 3})，是一个一元关系，而 G(2, 2)
= G(2, 3) = G(3, 2) = 1, G(3, 3) = 0，表明 G = {<2, 2>, <2, 3>, <3, 2>} D1D1，
是一个二元关系。
4. 给定一阶语言，我们可以构造它的一个解释，我们也可以给定一个解释所需的东西，
然后研究公式的真值，这种研究实际上从某种意义说是对解释的形式化研究。
5. 只给出解释还不能确定 Form(L)中的公式的真值，因为公式中可能存在自由变元，
必需为这些自由变元指派具体的个体，不指定具体的个体，则带有自由变元的公式还不能成
为命题逻辑的公式。教材 p81例 中的(5)没有真值就是因为它存在自由变元。
6. 以下定义 到定义 为选学内容，读者如果不理解则可按书上的更直观的定
义来学习定义 以后的内容。
【定义 】给定非逻辑符号集 L的一个解释[[L]]，其论域为 D。设公式集 Form(L)中
出现个体变元集为 Var = {x1, x2, …, xn, …}。公式集 Form(L)在解释[[L]]下的一个指派
是函数 : Var D，(xi)称为 xi在指派下的值。
【假定与记号】个体变元指派了值之后，就可以归纳定义项的值。在本节后面的定义中，
我们总是假定非逻辑符号集是 L，它生成的项集合为 Term(L)，生成的公式集为 Form(L)，
公式集 Form(L)中出现个体变元集为 Var = {x1, x2, …, xn, …}。L的一个解释是[[L]]，
其论域为 D，Form(L)在该解释下的一个指派是。
【定义 】项 t在指派的值(t) D归纳定义为：
[1].若 t是个体变元 xi，则(t) = (xi)；
[2].若 t是个体常项 c，则(c) = [[c]]；
[3].若 t是 f (t1, t2, …, tn)， 则 ( f(t1, t2, …, tn)) = [[f ]]((t1),
(t2), …, (tn))
注意在对指派的定义 中，定义了对出现在 Form(L)中每个个体变元都指派一个值，
但实际上，只要对 Form(L)中的自由变元指派值就可以了。不过如果指派只定义在自由变
元上，则不好归纳定义项 t的值了，因为无法断定项 t中的变元是自由变元还是约束变元。
为了区分指派对约束变元和自由变元的定义的不同，引入如下概念：
【定义 】设是在上述假定与记号下的指派，xi是一个个体变元，a D，定义 Form(L)
在解释[[L]]下的指派[xi /a]是：
[1].[xi /a](xj) = a，若 i = j（即 xj就是 xi），否则：
[2].[xi /a](xj) = (xj)
直观地来说，[xi /a]与的区别在于当为个体变元xi指派值时不指派为原来的值(xi)，
而指派为 a，而对其它个体变元的值指派完全与 一样。有了这个定义之后，可定义 Form(L)
中的公式在指派下的真值：
【定义 】定义 Form(L)中的公式 A在指派下的真值归纳定义为：
[1].若 A是原子公式 F(t1, t2, …, tn)时，则 A为真当且仅当<(t1), (t2), …,
(tn)> [[F]]；
[2].若 A是(B)时，则 A为真当且仅当 B为假；
[3].若 A是(BC)时，则 A为真当且仅当 B和 C都为真；
[4].若 A是(BC)时，则 A为假当且仅当 B和 C都为假；
[5].若 A是(BC)时，则 A为假当且仅当 B为真且 C为假；
[6].若 A是(BC)时，则 A为真当且仅当 B和 C的真值相同；
[7].若 A是(x)B时，则 A为真当且仅当对每个 aD有 B在指派[x /a]下都为真；
[8].若 A是(x)B时，则 A为真当且仅当存在某个 aD使得 B在指派[x /a]下为真。
【注解】
1. 显然，定义指派指派[x /a]的目的是当个体变元 x被量词约束时，能够给出量词
的适当解释。实际上，指派只对自由变元有意义，可以证明当两个指派对 Form(L)中出现
的自由变元的值的指派相同时，任意 Form(L)中的公式在这两个指派下的真值相同。从而对
于闭公式来说，指派就不是必须的了。这也就是书中 p81所说的闭公式在任意解释下都是命
题的精确含义。
2. 显然[2]~[6]的定义与命题逻辑中的公式真值定义相同，关键在于谓词与量词的解
释。直观地看谓词被解释成关系，从而原子公式的真值取决于相应的项是否属于该关系。
3. 显然上述定义中，任意公式的真值在指派下是非真则假，我们也按命题逻辑公式
中的习惯，若公式 A在指派下的真值为真，则记(A) = 1，否则记(A) = 0。公式 A在指
派下的真值为真，也可称指派满足 A。
【定义 】说公式 A在解释 I中为真，如果对于解释 I下的任意指派有(A) = 1；
说公式 A在解释 I中为假，如果对于解释 I下的任意指派有(A) = 0。说公式 A是永真式（重
言式），如果 A在任意解释中都为真；说 A是矛盾式，如果 A在任意解释中都为假；如果 A
不是矛盾式，则称 A是可满足式。
【注解】
1. 定义 的含义是，Form(L)中的 A是永真式，当且仅当对于 L的任意解释下的任
意指派，A的真值都为真；Form(L)中的 A是矛盾式，当且仅当对于 L的任意解释下的任意
指派，A的真值都为假；Form(L)中的 A是可满足式，当且仅当存在 L的一个解释，该解释
下存在一个指派，A的真值为真。
2. 定义 是教材 p81定义 的精确化，由于教材没有引进解释，所以它定义 A
是可满足式，当且仅当存在一个解释使得 A为真，实际上多数的文献（例如陆钟万的著作）
是说，只要存在一个解释中的一个指派使得 A为真，则 A是可满足式。不过一阶逻辑中，可
满足式的定义并不是很重要。
3. 显然在一阶逻辑中判断一个公式是否是永真式，比命题逻辑中判断一个公式是否是
永真式要难得多，这是因为公式的非逻辑符号有无穷多的解释。
4. 到这里为止，读者可以继续按照书上的定义来理解永真式、矛盾式，下面我们先讨
论教材中的例 、例 ，然后讨论永真式的判定方法。
【例子 】（教材 p79例 ）给定解释 I：
[1].论域 D = {2, 3}；
[2].D中特定元素 a = 2；
[3].一元函数 f : DD为 f (2) = 3, f (3) = 2；
[4].一元谓词 FD: F = {3}、二元谓词 GDD: G = {<2, 2>, <2, 3>, <3, 2>}、二
元谓词 LDD: L = {<2, 2>, <3, 3>}.
在这个解释下，求下列公式的真值：
(1).x(F(x)G(x, a))
(2).x(F(f(x))G(x, f(x))
(3).xyL(x, y)
(4).yxL(x, y)
【解答】上述公式都是闭公式，所以不涉及任何指派可确定这些公式的真值：
(1).x(F(x)G(x, a))为真当且仅当对于每个 dD = {2, 3}，有 F(d)G(d, a)为真，
而 a = 2，所以x(F(x)G(x, a))为真当且仅当有(F(2)G(2, 2)) F(3)G(3, 2)为真，
而 2F，所以 F(2)为假，所以(F(2)G(2, 2)) F(3)G(3, 2)为假，所以x(F(x)G(x,
a))为假。
(2).x(F(f(x))G(x, f(x))为 真 ， 当 且 仅 当 存 在 某 个 dD = {2, 3}， 使 得
(F(f(d))G(d, f(d))为真，即如果有(F(f(2))G(2, f(2))为真或者(F(f(3))G(3, f(3))
为真，则x(F(f(x))G(x, f(x))为真，即x(F(f(x))G(x, f(x))的真值与((F(3)G(2,
3)) ((F(2)G(3, 2))相同，即为真。
(3).xyL(x, y)为真当且仅当对于每个 dD = {2, 3}，有yL(d, y)为真，即当且仅
当对于某个 eD = {2, 3}，有 L(2, e)L(3, e)为真，即当且仅当(L(2, 2) L(2, 3))
(L(3, 2)L(3, 3))为真，即xyL(x, y)为真。
(4).yxL(x, y)为真当且仅当对于某个 dD有xL(x, d)为真，即(xL(x, 2))
xL(x, 3)为真，即当且仅当(L(2, 2) L(3, 2)) (L(2, 3) L(3, 3))为真，所以
yxL(x, y)的真值为假。
【注解】
1. 从上述例子可以看出，从某种意义看，全称量词是合取的推广，而存在量词是析取
的推广。
2. 从(3)和(4)可以看出，量词是有顺序的。
【例子 】（教材 p79例 ），此处不再详细讨论，只想说明两点：
1. 例中的(5)不是命题，是因为它有自由变元，没有给这些自由变元指派值，所以不
能确定其真值。
2. 教材说例中的(6)是命题，其实也是不确切的，严格地来说，它也不是命题，只不
过因为对于任意的 x, y有 x y = y x，才说它是真命题，实际上是xy(x y = y
x)为真。
一阶逻辑公式是否是永真式、矛盾式是很难断定的，但有一类特殊的一阶逻辑公式可很
容易地判定它的类型（是永真式还是矛盾式）。
【定义 】设 A0是含命题变元 p1, p2, …, pn的命题逻辑公式，A1, A2, …, An是
一阶逻辑公式，用 Ai(1 i n)替换 A0中的 pi的处处出现所得到的一阶逻辑公式 A称为命
题逻辑公式 A0的替换实例。
【定理 】命题逻辑中的永真式的任意替换实例在一阶逻辑中都是永真式；命题逻
辑中的矛盾式的任意替换实例在一阶逻辑中都是矛盾式。
【注解】
1. 定义 和定义 揭示了命题逻辑和一阶逻辑之间的联系。实际上命题逻辑中
的命题可用一阶逻辑中的 0元谓词（不带个体变项的谓词，参见教材 p68）来符号化，因此
从某种意义上来说，一阶逻辑是命题逻辑的推广，而且对于命题逻辑的等值演算、推理理论
在一阶逻辑中都可使用，不过使用时，要么是针对替换实例，要么是针对不含量词和个体变
项的公式而已。
【例子 】（教材 p82例 ）
【例子 】（教材 p83例 ），对于此例，有如下说明：
1. 对于某些简单的公式，特别对于简单的闭公式，可在假定给定任意解释的前提下该
公式的真值都为真（或者为假）来证明该公式是永真式（或矛盾式）。
2. 要证明一个公式是可满足式，只要找到一个解释，一个自由变元的指派使得该公式
的真值为真即可。同时为了证明它不是永真式，只要找一个解释，一个自由变元的指派使得
该公式的真值为假即可。
【定理 】设 A(x)和 B(y)是任意的两个一阶逻辑公式：
1. A(x)是永真式当且仅当 A(x)是矛盾式，A(x)是矛盾式当且仅当 A(x)是永真式；
2. A(x)B(y)是永真式当且仅当 A(x)和 B(y)都是永真式；A(x)B(y)是矛盾式当且仅
当 A(x)或 B(y)是矛盾式；
3. A(x)B(y)是永真式当且仅当 A(x)或 B(y)是永真式；A(x)B(y)是矛盾式当且仅当
A(x)和 B(y)都是矛盾式；
4. A(x)B(y)是永真式当且仅当 A(x)是矛盾式，或者 A(x)和 B(y)都是永真式；
A(x)B(y)是矛盾式当且仅当 A(x)是永真式而且 B(y)是矛盾式；
5. 若 A(x)是永真式，且 A(x)B(y)是永真式，则 B(y)是永真式；
6. A(x)是永真式当且仅当(x)A(x)是永真式；
7. A(x)是永真式，则(x)A(x)是永真式。
【注解】
1. 定理 的 1~5实际上是定理 的更准确形式，从定理 可证明定理
；
2. 定理 中的 A(x)和 B(y)中的自由变元是示意性质的，实际上，这两个公式的自
由变元可以相同，也可以有多个，即 A(x)和 B(y)实际上代表任意的一阶逻辑公式。
3. 根据定理 的 6和 7，我们可来判断一些特殊公式的类型，例如由命题逻辑公
式 AA是永真式，得到 A(x)A(x)也是永真式，从而(x)(A(x)A(x))和(x)(A(x)A(x))
也是永真式。
4. 一阶公式类型还可根据下面的等值演算，将其变换成某个命题逻辑公式的替换实例
而判断它是否为永真式或矛盾式，例如 P(x)(y)(G(x, y)P(x))是永真式，因为根据下
面的等值演算，它与(y)(P(x) (G(x, y)P(x)))等值，而 P(x)(G(x, y)P(x))是命
题逻辑的永真式 A(BA)的替换实例。
作业：教材 p102~103的 3、5、7，选作 4、6、8
4. 一阶逻辑的等值演算与前束范式
【定义 】设 A和 B是一阶逻辑中任意的两个公式，若 AB是永真式，则称 A与 B
等值，记为 AB，称 AB为等值式。
由于命题逻辑中的永真式的替换实例是永真式，因此在定理 中所给出的等值式的
替换实例都是一阶逻辑的等值式。下面定理给出与量词有关，一阶逻辑特有的一些等值式：
【定理 】一阶逻辑中特有的等值式：
[1].在有限个体域 D = {a1, a2, …, an}中消除量词：
(1).(x)A(x) A(a1)A(a2)…A(an)
(2).(x)A(x) A(a1)A(a2)…A(an)
[2].量词否定等值式：
(1).(xA(x)) x(A(x))
(2).(xA(x)) x(A(x))
[3].量词辖域的收缩与扩张等值式：下述等值式中，变元 x不在 B中出现
(1).x(A(x)B) (xA(x)) B
(2).x(A(x)B) (xA(x)) B
(3).x(A(x)B) (xA(x)) B
(4).x(BA(x)) B (xA(x))
(5).x(A(x)B) (xA(x)) B
(6).x(A(x)B) (xA(x)) B
(7).x(A(x)B) (xA(x)) B
(8).x(BA(x)) B (xA(x))
[4].量词分配等值式：
(1).x(A(x) B(x)) (xA(x)) (xB(x))
(2).x(A(x) B(x)) (xA(x)) (xB(x))
[5].量词顺序变换等值式：
(1).xy(A(x, y)) yx(A(x, y))
(2).xy(A(x, y)) yx(A(x, y))
【注解】
1. 这些公式都可应用于多个个体变元的情况，不过用于多个个体变元时，要小心。
2. 对于[1]，设 D = {a, b, c}，则：
(i).xyA(x, y) yA(a, y) yA(b, y) yA(c, y)
(A(a, a)A(a, b)A(a, c)) (A(b, a)A(b, b)A(b, c)) (A(c,
a)A(c, b)A(c, c))
(ii). xyA(x, y) yA(a, y) yA(b, y) yA(c, y)
(A(a, a)A(a, b)A(a, c)) (A(b, a)A(b, b)A(b, c)) (A(c,
a)A(c, b)A(c, c))
(iii). xyA(x, y) yA(a, y) yA(b, y) yA(c, y)
(A(a, a)A(a, b)A(a, c)) (A(b, a)A(b, b)A(b, c)) (A(c,
a)A(c, b)A(c, c))
(iv). xyA(x, y) yA(a, y) yA(b, y) yA(c, y)
(A(a, a)A(a, b)A(a, c)) (A(b, a)A(b, b)A(b, c)) (A(c,
a)A(c, b)A(c, c))
3. 对于[2]，推广到多个个体变元的情况有：
(i).(x1x2…xnA(x1, x2, …, xn)) x1((x2…xnA(x1, x2, …,
xn)))
x1x2((…xnA(x1, x2, …, xn))) x1x2…xn(A(x1, x2, …, xn))
(ii). (x1x2…xnA(x1, x2, …, xn)) x1x2…xn(A(x1, x2, …,
xn))
(iii). (xyA(x, y)) x((yA(x, y))) xy(A(x, y))
(iv). (xyA(x, y)) x((yA(x, y))) xy(A(x, y))
4. 注意[3]的条件，B中不出现变元 x，但对于等值式的左边，如果 x在 B中约束出现，
则可先使用换名规则将 x换成其它合式的变元，然后使用该等值式，例如：
(i).(xA(x)) (xB(x)) (xA(x)) (yB(y)) x(A(x)
(yB(y)))
xy(A(x) B(y)) // 最后一步假设 y不在 A(x)中出现
(ii). (xA(x)) (xB(x)) (xA(x)) (yB(y)) y((xA(x))
B(y))
yx(A(x) B(y)) // 最后一步假设 x不在 B(y)中出现
(iii). (xA(x)) (xB(x)) (xA(x)) (yB(y)) x(A(x)
(yB(y)))
xy(A(x) B(y)) // 最后一步假设 y不在 A(x)中出现
注意由(ii)和(iii)得到：yx(A(x) B(y)) xy(A(x) B(y))。实际上，量
词的顺序不能随意变换只有在两个不同的量词所约束的变元出现在同一个谓词时。所以对于
量词顺序的改变要具体情况具体分析！例如，我们还可得到：
(iv). (xA(x)) (yB(y)) x(A(x) (yB(y))) xy(A(x)
B(y))
y((xA(x)) B(y)) yx(A(x) B(y))
由于运用等值式的顺序不会改变等值关系，因此在运用量词辖域的扩张等值式，肯定会
产生许多不同的量词约束顺序来。
如果等值式左边的 B中约束出现 x，也还可以使用换名规则将 x换成其它合式的个体变
元，注意这时实际上出现了量词辖域的嵌套问题，我们需要更加小心处理：
(v).x(A(x) xB(x)) x(A(x) yB(y)) xA(x) yB(y)
xy(A(x) B(y))
总的来说，[3]中的条件精确来说，应该是说 B中不自由出现变元 x，但因为当 B中约
束出现 x时，容易产生混淆，所以书中没有明确指出 B中可以约束出现 x。
5. 对于[4]，也可推广到多个变元的情况：
(i).x1x2…xn(A(x1, x2, …, xn) B(x1, x2, …, xn))
(x1x2…xnA(x1, x2, …, xn)) (x1x2…xnB(x1, x2, …, xn))
(ii). x1x2…xn(A(x1, x2, …, xn) B(x1, x2, …, xn))
(x1x2…xnA(x1, x2, …, xn)) (x1x2…xnB(x1, x2, …, xn))
容易理解对有分配律，是因为从某种意义上来说是的扩充，同样对有分配律，
也是因为从某种意义上来说是的扩充。但虽然对有分配律，对却没有分配律，这是
因为，设个体域 D = {a, b, c}：
x(A(x)B(x)) (A(a)B(a)) (A(b)B(b)) (A(c)B(c))
(A(a)B(a)) (A(b)B(b)) (A(c)B(c))
(A(a)A(b)A(c)) (B(a)A(b)A(c)) (A(a)B(b)A(c))
(B(a)B(b)A(c))
(A(a)A(b)B(c)) (B(a)A(b)B(c)) (A(a)B(b)B(c))
(B(a)B(b)B(c))
而 (xA(x)) (xB(x)) (A(a)A(b)A(c)) (B(a)B(b)B(c))
显然这两者不等值，但可以看出，如果 (xA(x)) (xB(x))是永真式，则
x(A(x)B(x))是永真式，或者说(xA(x)) (xB(x)) x(A(x)B(x))是永真式，这
就是后面的量词分配推理定律。同样，读者可验证对于等值演算来说，对没有分配律。
6. 对于[5]，推广到三个变元的情况是：
(i).xyz(A(x, y, z)) yxz(A(x, y, z)) yzx(A(x, y, z))
xzy(A(x, y, z)) zxy(A(x, y, z)) zyx(A(x, y, z))
(ii). xyz(A(x, y, z)) yxz(A(x, y, z)) yzx(A(x, y,
z))
xzy(A(x, y, z)) zxy(A(x, y, z)) zyx(A(x, y, z))
当约束变元的量词不同时，即不能随意变换量词的顺序，上面已经讨论过这种情况。
7. 上述所有等值式中，A(x)既可代表任意只有自由变元 x的公式，也可理解 A为任意
的一元谓词，同理 A(x, y)既可看成是有两个自由变元 x, y的任意一阶逻辑公式，也可看
成任意的二元谓词。
读者理解了上述注解之后，对于教材 p85~87的例 ~例 应该是容易理解的了。
【定义 】设 A为一阶逻辑公式，若 A具有如下形式：
Q1x1Q2x2…QnxnB
则称 A为前束范式(prenex normal form)。其中 Qi(1 i n)是或，B为不含量词的公式。
【定理 】对于任意的一阶逻辑公式 A，都存在与之等值的前束范式。
【注解】
1. 这里不给出该定理的严格证明，但下面的注解说明对于每种类型的一阶逻辑公式如
何求它的前束范式，从而非严格地证明了该定理。
2. 求一个公式的前束范式，无非是通过等值式将其所有的量词移到整个公式的前面。
根据一阶逻辑公式的归纳定义，可将公式的形式分为以下几种：
(i).量词与否定：(xA(x))、(xA(x))
(ii). 量词与析取：xA(x)yB(y)、xA(x)yB(y)、xA(x)yB(y)、xA(x)yB(y)
(iii). 量词与合取：xA(x)yB(y)、xA(x)yB(y)、xA(x)yB(y)、xA(x)yB(y)
(iv). 量 词 与 蕴 涵 ： xA(x)yB(y)、 xA(x)yB(y)、 xA(x)yB(y)、
xA(x)yB(y)
(v).量词与等价：xA(x)yB(y)、xA(x)yB(y)、xA(x)yB(y)、xA(x)yB(y)
对于(v)中的公式总可变换为蕴涵与合取的形式，因为可归结为(iii)和(iv)的情况。当
然蕴涵也可变换为非与析取，但由于蕴涵的重要性（在推理理论中需要使用）所以在这里也
讨论与蕴涵有关的公式。
如果析取和合取的某一分支，或蕴涵式的前件或后件没有量词，则可简单地使用量词辖
域的扩张等值式，将量词移到整个公式的前面。所以下面只讨论都有量词的情况。
2. 显然，对于公式(xA(x))，将其变换为x(A(x))，而对于公式(xA(x))，将
其变换为x(A(x))，使得量词移到整个公式的前面。
3. 对于公式xA(x)yB(y)，由于对析取没有分配律，所以只能变换为：
xA(x)yB(y) xy(A(x) B(y))
对于公式xA(x)yB(y)，由于对析取有分配律，所以可变换为：
xA(x)yB(y) xA(x)xB(x) x(A(x) B(x))
注意运用此变换的前提是 B(y)中不出现 x，如果 B(y)中出现 x，则可使用换名规则
（如果 x是约束出现）或者是替换规则（如果 x是自由出现）先将 x变为其他变换符号。
显然对于公式xA(x)yB(y)、xA(x)yB(y)都只能变换为：
xA(x)yB(y) xy(A(x) B(y))、xA(x)yB(y) xy(A(x)B(y))
4. 对于公式xA(x)yB(y)，由于对合取没有分配律，所以只能变换为：
xA(x)yB(y) xy(A(x) B(y))
对于公式xA(x)yB(y)，由于对合取有分配律，所以可变换为：
xA(x)yB(y) xA(x)xB(x) x(A(x)B(x))
注意运用此变换的前提是 B(y)中不出现 x，如果 B(y)中出现 x，则可使用换名规则
（如果 x是约束出现）或者是替换规则（如果 x是自由出现）先将 x变为其他变换符号。
显然对于公式xA(x)yB(y)、xA(x)yB(y)都只能变换为：
xA(x)yB(y) xy(A(x)B(y))、xA(x)yB(y) xy(A(x)B(y))
5. 对于公式xA(x)yB(y)则可做如下变换：
xA(x)yB(y) x(A(x)yB(y)) xy(A(x) B(y))
对于公式xA(x)yB(y)则可做如下变换：
xA(x)yB(y) x(A(x)yB(y)) xy(A(x)B(y))
对于公式xA(x)yB(y)则可做如下变换：
xA(x)yB(y) xy(A(x) B(y))
对于公式xA(x)yB(y)则可做如下变换：
xA(x)yB(y) xy(A(x) B(y))
6. 注意，上述公式中，合取（析取）的两个分支，和蕴涵的前件与后件选取的约束变
元不同，当约束变元相同时，且又不能运用对的分配律和对的分配律时则可使用换名
规则，使得约束变元不同。
7. 对于任意的一阶逻辑公式，可反复使用上述变换得到它的前束范式，一阶逻辑公式
的前束范式不唯一。
【例子 】（教材 p88例 ）
【例子 】求下列公式的前束范式：
[1].xF(x, y) yF(x, y)
[2].yF(x) xF(y)
[3].xyF(x, y) xyF(x, y)
[4].xF(x, y) (xG(x) yF(y, z))
【解答】
[1].xF(x, y) yF(x, y) xF(x, u) yF(v, y) xy(F(x, u)
F(v, y))
显然不能变换为：xy(F(x, y) F(x, y))。
[2].yF(x) xF(y) yF(u) xF(v) yx(F(u) F(v)) F(u)
F(v)
xy(F(x) F(y))
[3].xyF(x, y) xyF(x, y) xyF(x, y) uvF(u, v)
x(yF(x, y) uvF(u, v)) xy(F(x, y) uvF(u, v))
xyuv(F(x, y) F(u, v))
[4].xF(x, y) (xG(x) yF(y, z)) xF(x, u) (vG(v) yF(y,
z))
xF(x, u) (vy(G(v) F(y, z))) xvy(F(x, u) (G(v)
F(y, z)))
作业：教材 p103~104的 9、10
5. 一阶逻辑的推理理论
一阶逻辑的推理形式与命题逻辑相同：
【定义 】称蕴涵式(A1A2…Ak)B为推理的形式结构，A1, A2, …, Ak为推理的
前提，B为推理的结论。若(A1A2…Ak)B为永真式，则称从前提 A1, A2, …, Ak推出结
论 B的推理正确（或说有效），B是 A1, A2, …, Ak的逻辑结论或称有效结论，否则称推理
不正确。若从前提 A1, A2, …, Ak推出结论 B的推理正确，则记为(A1A2…Ak)B。
通过对命题逻辑公式进行替换，一阶逻辑的推理可使用命题逻辑的推理规则，下面先将
命题逻辑中的推理规则罗列如下：
【定义 】证明是一个描述推理过程的一阶公式序列 A1, A2, …, An，其中的每个一
阶公式或者是已知的前提，或者是由某些前提应用推理规则得到的结论，满足这样条件的公
式序列 A1, A2, …, An称为结论 An的证明。在证明中常用的推理规则有 3条：
[1].前提引入规则：在证明的任何步骤都可以引入已知的前提；
[2].结论引入规则：在证明的任何步骤都可以引入这次已经得到的结论作为后续证明的
前提；
[3].置换规则：在证明的任何步骤上，一阶公式中的任何子公式都可用与之等值的公式
置换，得到证明的公式序列的另一公式。
使用一阶逻辑公式进行推理还有其他一些推理规则，这些规则建立在下面一些推理定律
上：
【定理 】推理定律是一阶逻辑的一些永真蕴涵式，重要的推理定律有：
[1].附加律： A(AB) // 或称为析取的引入
[2].化简律： (AB)A, (AB)B // 或称为合取的消除
[3].假言推理： (AB)AB // 或称为分离规则
[4].拒取式： (AB)BA
[5].析取三段论：(AB)BA
[6].假言三段论：(AB)(BC)(AC) // 或称为传递规则
[7].等价三段论：(AB)(BC)(AC)
[8].构造性二难：(AB)(CD)(AC)(BD)
【定理 ，演绎定理】(A1A2…AkA)B当且仅当(A1A2…Ak)AB。
【定理 】 (A1A2…Ak)B当且仅当(A1A2…AkB)是永真式，或者说
(A1A2…Ak)B当且仅当(A1A2…AkB)是矛盾式。
在一阶逻辑中，可使用上述推理定律的替换实例而进行推理，而定理 中所给出的
每个等值式都得到 2条推理定律，除此之外，一阶逻辑中还有如下的推理定律：
【定理 】一阶逻辑中特有的推理定律：
[1].(xA(x)) (xB(x)) x(A(x) B(x))
[2].x(A(x) B(x)) (xA(x)) (xB(x))
[3].x(A(x) B(x)) (xA(x)) (xB(x))
[4].x(A(x) B(x)) (xA(x)) (xB(x))
以及下面的推理规则，不过这些规则的使用需要满足一定的条件：
【定理 】一阶逻辑中特有的推理规则：
[1].全称量词消除规则（UI规则）：
(i).xA(x) A(y)
(ii). xA(x) A(c)
成立的条件是：
(1).x是 A(x)的自由变元；
(2).在(i)中，y为不在 A(x)中约束出现的变元，y可以在 A(x)中自由出现，也可
在证明序列中前面的公式中出现。
(3).在(ii)中，c任意的个体常项，可以是证明序列中前面公式所指定的个体常项。
[2].全称量词引入规则（UG规则）：
A(y) xA(x)
成立的条件是：
(1).y在 A(y)中自由出现；
(2).替换 y的 x要选择在 A(y)中不出现的变元符号；
[3].存在量词引入规则（EG规则）：
A(c) xA(x)
成立的条件是：
(1).c在是特定的个体常项；
(2).替换 c的 x要选择在 A(c)中不出现的变元符号；
[4].存在量词消除规则（EI规则）
xA(x) A(c)
成立的条件是：
(1).c是特定的个体常项，c不能在前面的公式序列中出现；
(2).c的不在 A(x)中出现；
(3).A(x)中自由出现的个体变元只有 x；
【注解】
1. 我们在这里给出的推理规则成立条件与教材 p91~93所给出的形式略有不同，我们
认为我们所给出的条件更为明确和实用，下面说明这种区别。
2. 对于[1]，y可以在 A(x)中自由出现，即实际上可有：xA(x, y) A(y, y)。全
称量词引入规则表明，如果证明序列中得到的公式 A含有自由出现的变元符号，则可引入使
用全称量词约束该变元的相应公式，而如果证明序列中得到的公式 A如果前面是全称量词所
约束的变元，那么可去掉这些全称量词，引入这些变元作为自由出现的相应公式。因此从某
种意义上来说，A中自由出现的变元与用全称量词约束这些变元是等值的，这正是定理
的(6)所表明的等值式。
3. 对于[1]的(ii)式，c是任意的个体常项，我们特别指出，它可以是在证明序列的
前面公式中出现的个体常项符号，这一点有助于进行推理。
4. 对于[2]，取代 y的 x可以在 A(y)中自由出现，但通常这样做是令人费解的，因此
我们约定选择不在 A(y)中出现的变元符号来替换 y。
5. 对于[3]，其中的 c通常是在证明序列的前面公式所得到的特定个体常项。
6. 对于[4]，我们特别强调所选取的 c不能是证明序列中前面公式所指定某个特定个
体常项，这一点对于进行推理很重要，常见的推理错误都是在应用存在量词消除规则时选取
在前面中已经指定的某个特定个体常项。根据这一点，我们知道在进行推理时，往往要先使
用 EI规则，确定一个个体常项 c，然后可将该个体常项中用于 UI规则和 EG规则中。不能
先使用 UI规则或 EI规则确定一个个体常项 c，然后再用于 EI规则中。
7. 最后，上述规则只能对辖域为整个公式的量词使用，不能对出现在公式中间的量词
使用。
【例子 】教材 p94~95的例 、例 、例
【例子 】指出下列推导中的错误，并加以改正：
[1].(1).(x)P(x)Q(x) // 前提
(2).P(y)Q(y) // 全称量词消除规则
[2].(1).P(a)Q(b) // 前提
(2).(x)(P(x)Q(x)) // 存在量词引入规则
[3].(1).P(x)Q(c) // 前提
(2).(x)(P(x)Q(x)) // 存在量词引入规则
[4].(1).(x)(P(x)Q(x)) // 前提
(2).P(a)Q(b) // 全称量词消除规则
[5].(1).(x)P(x) // 前提
(2).P(c) // 存在量词消除规则
(3).(x)Q(x) // 前提
(4).Q(c) // 存在量词消除规则
[6].(1).(x)(y)(x > y) // 前提
(2).(y)(z > y) // 全称量词消除规则
(3).(z > c) // 存在量词消除规则
(4).(x)(x > c) // 全称量词引入规则
(5).c > c // 全称量词消除规则
【解答】
[1].量词x的辖域为 P(x)，而非 P(x)Q(x)，所以不能直接使用全称量词消除规则。
[2].前提中的个体 a和 b不同，不能一次同时使用存在量词引入规则，正确的推理可以
为：
(1).P(a)Q(b) // 前提
(2).x(P(x)Q(b)) // 存在量词引入规则
(3).yx(P(x)Q(y)) // 存在量词引入规则
[3].在使用存在量词引入规则时，替换个体 c的变元应选择在公式中没有出现的变元符
号，正确的推理是：
(1).P(x)Q(c) // 前提
(2).(y)(P(x)Q(y)) // 存在量词引入规则
[4].在使用量词消除规则时，应使用个体替换量词所约束的变元在公式中的所有出现，
正确的推理是：
(1).(x)(P(x)Q(x)) // 前提
(2).P(a)Q(a) // 全称量词消除规则
[5].第二次使用存在量词消除规则时，所指定的特定个体应该在证明序列以前的公式中
不出现，正确的推理是：
(1).(x)P(x) // 前提
(2).P(c) // 存在量词消除规则
(3).(x)Q(x) // 前提
(4).Q(d) // 存在量词消除规则
[6].由(2)得到(3)不能使用存在量词消除规则，因为(2)中含有除 y以外的自由变元 z。
【例子 】将下列命题符号化，并研究其推理是否正确
[1].每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他
是优等生。因此，如果小张是大学生，他就是理科生；
[2].没有不守信用的人是可以信赖的；有些可以信赖的人是受过教育的。因此，有些受
过教育的人是守信用的。
[3].所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数既不
是有理数，也不是无理数。
[4].每个旅客或者坐头等舱或者坐二等舱；每个旅客当且仅当他富裕时坐头等舱；有些
旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等舱。
【解答】
[1].个体域取全总域，要引入的谓词包括：
P(x): x 是一个大学生；Q(x): x是文科生； S(x): x 是理科生；T(x): x 是优
等生。
要引入的个体常项是：c : 小张。因此前提可符号化为：
x(P(x)(Q(x)S(x)))、x(P(x)T(x))、Q(c)T(c)
结论符号化为：P(c)S(c)，验证该结论的公式序列为：
(1).x(P(x)(Q(x)S(x))) // 前提
(2).P(c)(Q(c)S(c)) // 全称量词消除规则
(3).P(c) // 附加前提
(4).Q(c)S(c) // 分离规则
(5).Q(c)T(c) // 前提
(6).Q(c) // 合取的消除
(7).S(c) // 析取三段论，(4)和(6)
[2].因为每个句子都对人做了限制，因此不必引入“...是人”的特性谓词，而可直接
取个体域是所有的人，要引入的谓词包括：
P(x): x 是守信用的人；Q(x): x是可信赖的人；S(x): x是受过教育的人
前提可符号化为：(x(P(x) Q(x)))、x(Q(x) S(x))。
结论可符号化为：x(S(x) P(x))，验证该结论的公式序列为：
(1).x(Q(x) S(x)) // 前提
(2).Q(c) S(c) // 存在量词消除规则
(3).Q(c) // 合取的消除
(4).S(c) // 合取的消除，(2)
(5).(x(P(x) Q(x))) // 前提
(6).x(P(x) Q(x)) // 等值替换规则
(7).P(c) Q(c) // 全称量词消除规则，使用(2)中个体 c
(8).P(c) // 析取三段论，(3)和(7)
(9).P(c) S(c) // 合取的引入，(4)和(8)
(10). x(S(x) P(x)) // 存在量词引入规则
[3].同样因为每个句子都是对数作了限制，引入我们不需要使用全总域，而使用的个体
域为所有的数。这样要引入的谓词包括：
Q(x): x 是有理数；R(x): x是实数；N(x): x是无理数；C(x): x是虚数
前提可符号化为：x(Q(x)R(x))、x(N(x)R(x))、x(C(x) R(x))
结论可符号化为：x(C(x) (Q(x) N(x))，验证该结论的公式序列如下：
(1).x(Q(x)R(x)) // 前提
(2).Q(x)R(x) // 全称量词消除规则
(3).x(N(x)R(x)) // 前提
(4).N(x)R(x) // 全称量词消除规则
(5).x(C(x) R(x)) // 前提
(6).C(x) R(x) // 全称量词消除规则
(7).C(x) // 附加前提
(8).R(x) // 分离规则，(6)和(7)
(9).Q(x) // 拒取式，(8)和(2)
(10). N(x) // 拒取式，(8)和(4)
(11). Q(x) N(x) // 合取的引入
(12). C(x)(Q(x) N(x) // 附加前提规则，(7)和(11)
(13). x(C(x) (Q(x) N(x)) // 全称量词引入规则
[4].通过分析发现，我们不能使用个体域为所有的旅客，只能使用全总域，而引入下列
谓词：P(x): x是旅客；Q(x): x坐头等舱；R(x): x坐二等舱；S(x): x是富裕的。
前提可符号化为：
x(P(x)(Q(x)R(x)))、 x(P(x)(Q(x)S(x)))、 x(P(x)S(x))、
(x(P(x)S(x)))
结论可符号化为：x(P(x)R(x))，验证该结论的公式序列如下：
(1).(x(P(x)S(x))) // 前提
(2).x(P(x)S(x)) // 等值替换规则
(3).P(c)S(c) // 存在量词消除规则
(4).P(c) // 合取的消除
(5).S(c) // 合取的消除，(3)
(6).x(P(x)(Q(x)R(x))) // 前提
(7).P(c)(Q(c)R(c)) // 全称量词消除规则，使用(3)中个体 c
(8).Q(c)R(c) // 分离规则，(4)和(7)
(9).x(P(x)(Q(x)S(x))) // 前提
(10). P(c)(Q(c)S(c)) // 全称量词消除规则，使用(3)中
个体 c
(11). Q(c)S(c) // 分离规则，(4)和(11)
(12). Q(c)S(c) // 合取的消除
(13). Q(c) // 拒取式，(12)和(5)
(14). R(c) // 析取三段论，(13)和(8)
(15). P(c) R(c) // 合取的引入，(4)和(14)
(16). x(P(x)R(x)) // 存在量词的引入
作业：教材 p104~105的 11、12、13、16，选作 14、15
第三讲 集合论
一、集合的基本概念和运算
1. 集合的基本概念
·集合(set)：集合是数学中最基本的概念之一，不能以更简单的概念来定义(define)，
只能给出它的描述(description)。一些对象的整体就称为一个集合，这个整体的每个对象
称为该集合的一个元素(member或 element)。
·用大写字母 A, B, C等表示集合，用小写字母 a, b, c等表示集合的元素
·aA表示：a是集合 A的元素，或说 a属于集合 A
·aA表示：a不是集合 A的元素，或说 a不属于集合 A
·集合中的元素是无序的，不重复的。通常使用两种方法来给出一个集合：
·列元素法：列出某集合的所有元素，如：
·A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}表示所有小于 10的自然数所构成的
集合
·B = {a, b, …, z} 表示所有小写英文字母所构成的集合
·性质概括法：使用某个性质来概括集合中的元素，如：
·A = { n | n 是小于 10的自然数}
·C = { n | n 是质数} 表示所有质数所构成的集合
·集合由它的元素所决定，换句话说，两个集合 A和 B相等，记为 A = B，如果 A和 B
具有相同的元素，即 a属于集合 A当且仅当 a属于集合 B。
·子集(subset)：说集合 A是集合 B的子集，记为 AB，如果 a属于集合 A则 a也属于
集合 B。因此 A=B当且仅当 AB且 BA。说集合 A是集合 B的真子集(proper subset)，如
果 AB且 A不等于 B(A B)。
·空集(empty set)：约定存在一个没有任何元素的集合，称为空集，记为，有时也用{}
来表示。按子集的定义，空集是任何集合的子集(为什么？)。
·幂集(power set)：集合 A的幂集，记为 P(A)，是 A的所有子集所构成的集合，即：
·P(A) = { B | B A }
·例如，A = {0, 1}，则 P(A) = { {}, {0}, {1}, {0, 1} }
·显然，对任意集合 A，有 P(A)和 AP(A)
·补集(complement set)：集合 A的补集，记为 A，是那些不属于集合 A的元素所构成
的集合，即 A = {x | xA}。通常来说，是在存在一个全集 U的情况下讨论集合的补集。全
集 U是所讨论的问题域中所有元素所构成的集合。
2. 集合的基本运算
·集合的并(union)：集合 A和 B的并 AB定义为：AB = {x | xA xB}，集合的
并可推广到多个集合，设 A1, A2, …, An都是集合，它们的并定义为：
A1A2…An = {x | i(xAi)}
·集合的交(intersection)：集合 A和 B的并 AB定义为：AB = {x | xA xB}，
集合的交也可推广到多个集合，设 A1, A2, …, An都是集合，它们的交定义为：
A1A2…An = {x | i(xAi)}
·集合的相对补：集合 B对 A的相对补集 AB定义为：AB = {x | xA xB}。集合
B对全集 U的相对补集记为~B，称为 B的绝对补集。
·集合的对称差：集合 A和 B的对称差 AB定义为：AB = (AB)(BA)，对称差的一
个等价定义是：AB = (AB) (AB)
·集合的运算可使用文氏图形象地表示。
·集合的运算中，~优先于并、交、相对补及对称差，后面四种运算的顺序由括号决定。
作业：教材 p132的 3、4、6
3. 集合恒等式
·集合的基本恒等式包括幂等律、结合律、交换律、分配律、同一律、零律、排中律、
矛盾律、吸收律、德·摩尔根律、双重否定律，其中最重要的恒等式有：
吸收律： A(AB) = A A(AB) = A
德·摩尔根律： A(BC) = (AB)(AC) A(BC) = (AB)(AC)
·例 、例 表明证明集合恒等式的一个重要方法是，如果要证明集合 A = B，即
可证明对任意的 xA有 xB，且对任意的 xB有 xA。
·其它的一些有关集合运算的性质：
(AB)A(AB)BA(AB)B(AB)(AB)A
AB (AB) = B (AB) = A (AB) = (AB) = (A ~B)
AB = BA A(BC) = (AB)C A = A AA =
AB = AC B = C
·例 、例 、例 运用上述性质来证明集合的恒等式。
4. 有穷集合的计数
·含有有限个元素的集合称为有穷集合（有限集合，finite set），有限集合 A的元素个
数通常记为|A|。
·A的幂集 P(A)的元素个数有如下等式：| P(A)| = 2|A|。
·使用文氏图再加上列方程组，求解方程组的办法可解决许多有关集合计数的问题，例
、例 采用了这种方法。
·集合计数中一个很重要的定理称为容斥原理，其简单形式如下：
|AB| = |A| + |B| |AB|
|ABC| = |A| + |B| + |C| |AB| |BC| |AC| + |ABC|
设 U为全集，|~A| = |U| |A|
·使用容斥原理求解例 ：
设：A = 会打排球的人、B = 会打网球的人、C = 会打篮球的人，即按题意有：
|A| = 12, |B| = 6, |C| = 14, |AC| = 6, |BC| = 5, |ABC| = 2
根据容斥定理有：|ABC| = |A| + |B| + |C| |AB| |BC| |AC| + |ABC|，
即：
|ABC| = 14 + 12 + 6 - |AB| - 5 - 6 + 2,
即|ABC| = 23 - |AB|，而且根据题意有：|B(AC)| = 6，即：
|(BA)(CB)| = |(BA)| + |(CB)| - |ABC| = 5 + |(AB)| - 2 = 6，
即|(AB)| = 3，所以|ABC| = 20，所以不会打这三种球的人为 25 - 20 = 5人。
5. 例题分析
作业：教材 p133~135的 8、9、11、13
