离散数学基础

第一讲 引言

一、课程内容

·数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。 ·集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。 ·代数结构：对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等代数结构的基本知识。 ·图论：对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用数学工具建立模型的思维方式。 ·讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图论。考试内容限于书中的内容和难度，但讲课内容不限于书中的内容和难度。

二、数理逻辑发展史

1. 目的

·了解有关的背景，加深对计算机学科的全面了解，特别是理论方面的了解，而不限于将计算机看成是一门技术或工程性的学科。 ·通过重要的历史事件，了解计算机科学中的一些基本思维方式和一些基本问题。

2. 数理逻辑的发展前期

·前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论 ·初创时期——逻辑代数时期（17世纪末）

·资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。

·人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。

·莱布尼兹(Leibniz, 1646~1716)完善三段论，提出了建立数理逻辑或者说理性演算的思想：

·提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。

·使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。

·布尔(G. Boole, 1815~1864)代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。

3. 数理逻辑的奠基时期

·弗雷格(G. Frege, 1848~1925)：《概念语言——一种按算术的公式语言构成的纯思维公式语言》(1879)的出版标志着数理逻辑的基础部分——命题演算和谓词演算的正式建立。 ·皮亚诺(Giuseppe Peano, 1858~1932)：《用一种新的方法陈述的算术原理》(1889)提出

1

了自然数算术的一个公理系统。 ·罗素(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)不完全性定理：一个足够强大的形式系统，如果是一致的则不是完全的，即有的判断在其中是不可证的，既不能断定其为假，也不能证明其为真。 ·各种计算模型：哥德尔的递归函数理论，邱吉尔的?演算，图灵机模型 ·这些计算模型是计算机科学的理论基础，是计算机的理论模型。

2

三、预备知识

1. 集合的基本概念

·集合(set)：集合是数学中最基本的概念之一，不能以更简单的概念来定义(define)，只能给出它的描述(description)。一些对象的整体就称为一个集合，这个整体的每个对象称为该集合的一个元素(member或element)。

·用大写字母A, B, C等表示集合，用小写字母a, b, c等表示集合的元素 ·a?A表示：a是集合A的元素，或说a属于集合A

·a?A表示：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的子集，记为A?B，如果a属于集合A则a也属于集合B。因此A=B当且仅当A?B且B?A。说集合A是集合B的真子集(proper subset)，如果A?B且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)和A?P(A) ·补集(complement set)：集合A的补集，记为A，是那些不属于集合A的元素所构成的集合，即A = {x | x?A}。通常来说，是在存在一个全集U的情况下讨论集合的补集。全集U是所讨论的问题域中所有元素所构成的集合。 ·集合的并(union)：集合A和B的并A?B定义为：A?B = {x | x?A或者x?B}，集合的并可推广到多个集合，设A1, A2, …, An都是集合，它们的并定义为： A1?A2…?An = {x | 存在某个i，使得x?Ai} ·集合的交(intersection)：集合A和B的并A?B定义为：A?B = {x | x?A而且x?B}，集合的交也可推广到多个集合，设A1, A2, …, An都是集合，它们的交定义为： A1?A2…?An = {x | 对所有的i，都有x?Ai} ·集合的差(difference)：集合A和B的差A?B定义为：A?B = {x | x?A而且x?B}。

2. 关系和函数的基本概念

·有序对(ordered pair)：设A和B是两个集合，a?A, b?B是两个元素，a和b的有序对，记为，定义为集合{{a}, {a, b}}。

3

·设和是两个有序对，可以证明 = 当且仅当a1 = a2且b1 = b2。(如何证？) ·有序对可推广到n个元素，设A1, A2, …, An是集合，a1?A1, a2?A2, …, an?An是元素，定义有序n元组(ordered n-tuple)为<, an>，注意这是一个归纳(inductive)定义，将有序n元组的定义归结为有序n-1元组的定义。 ·显然有 = 当且仅当a1 = b1且a2 = b2且…且an = bn。 ·集合的笛卡尔积(cartesian product)：两个集合A和B的笛卡尔积A?B定义为： A?B = { | a?A且b?B} ·例如，设A = {a, b, c}，B = {1, 2}，则：

A?B = {, , , , , }

·笛卡尔积可推广到多个集合的情况，集合A1, A2, …, An的笛卡尔积定义为： A1?A2?…?An = { | a1?A1且a2?A2且…且an?An} ·集合之间的关系(relation)：定义n个集合A1, A2, …, An之间的一个n元关系R为集合A1, A2, …, An的笛卡尔积A1?A2?…?An的一个子集。设?A1?A2?…?An，若?R，则称a1, a2, …, an间具有关系R，否则称它们不具有关系R。特别地： ·当A1 = A2 = … = An = A时，称R为A上的n元关系。 ·当n = 2时，有R?A1?A2，称R为A1与A2间的一个二元关系(binary relation)。这时若?R则简记为a1Ra2，否则（即?R）记为a1Ra2。通常研究得最多的是二元关系，n元关系的许多性质可从二元关系的性质扩充而得到。如果没有特别指明的话，说R是一个关系则是指R是一个二元关系。 ·当n = 1时，这时可认为R是集合A上满足某种性质的子集。 ·关系的一些性质：设R是A上的二元关系： ·说R是自反的(reflexive)，如果对任意的a?A有aRa。 ·说R是反自反的(irreflexive)，如果对任意的a?A有aRa。 ·说R是对称的(symmetric)，如果对任意的a, b?A有若aRb则bRa。 · 说R是反对称的(antisymmetric)，如果对任意的a, b?A有若aRb且bRa则a = b。 ·说R是传递的(transitive)，如果对任意的a, b, c ?A有若aRb且bRc则aRc。 ·说R是等价关系(equivalence)，如果R是自反的、对称的和传递的。 ·集合之间的函数(function，或说映射mapping)：定义集合A到B的函数f是A和B的笛卡尔积A?B的一个子集，且满足若?f及?f则y = z。因此函数是A和B之间的一个特殊的二元关系。通常记集合A到B的函数f为f : A?B。 ·函数f : A?B的定义域(domain)dom(f )定义为： dom(f ) = {x | 存在某个y?B使得?f } ·函数f : A?B的值域(range)ran(f )定义为： ran(f ) = {y | 存在某个x?A使得?f } ·若?f，通常记y为f(x)，并称y为x在函数f下的像(image)，x为y在函数f下的原像。 ·函数也可推广到n元的情形：f : A1?A2?…?An?B，意味着： ·f是A1?A2?…?An?B的一个子集，且 ·? f且? f则y = z。

4

·函数的一些性质：设f : A?B是集合A到B的函数： ·说f是全函数(total function)，若dom(f )=A，否则称f是偏函数(partial function)。下面如果没有特别指明的话，都是指全函数。 ·说f是满射(surjection, 或说f maps A onto B)，如果ran(f ) = B，即对任意的y?B都有原像。 ·说f是单射(injection，或说f is one-one)，如果有f (x1) = f(x2)则x1 = x2，即对任意的y?B，如果它有原像的话，则有唯一的原像。 ·说f是双射(bijection，或说f是一一对应)，如果f既是满射，又是单射，即对任意的y?B，都有唯一的原像，同样根据全函数的定义，对于任意x?A都有唯一的像。这时可以定义f的逆函数(inverse function)，记为f -1 : B?A，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|，|A?B| = |A| ? |B|。

3. 小结

·下面以树的形式给出了以上主要概念之间的关系： 集合

子集 集合的补、并、交、差 有序对

幂集 笛卡尔积

关系

关系的自反、对称、传递性 函数

单射、满射、双射

4. 归纳定义和归纳证明

·一个集合的归纳定义(inductive definition)通常分为三步： ·归纳基：一些基本的元素属于该集合； ·归纳步：定义一些规则（或者说操作），从该集合中已有的元素来生成该集合的新的元素； ·最小化：该集合中的所有元素都是通过基本元素以及所定义的规则生成的，换句话说，该集合是由基本元素及规则所生成的最小的集合。 ·自然数集N的归纳定义： [1]. 归纳基：0是一个自然数，即0? N。 [2]. 归纳步：若n是自然数，则n的后继也是自然数。记n的后继为succ(n)，即

5

5. 联结词的完全集

【定义1.22】{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)在真值赋值函数下的真值为f(t1, t2, …, tn)。

显然互不相同的n元真值函数的个数为22n，因此可定义22n个n元真值联结词，例如1元真值函数有四个：

f1: 0?0, 1?0 f2: 0?0, 1?1 f3: 0?1, 1?0 f4: 0?1, 1?1

而2元真值函数有16个，可定义16个真值联结词，而我们常用的只不过是其中的4个。现在的问题是，是否所有的真值函数都可使用常用的这5个真值联结词来表示呢？

【定义1.23】设?是联结词的一个集合，称?为联结词的一个完全集，如果任意真值函数f都可用仅含?中联结词的命题公式A来表示，即对A中命题变元的任意一个真值赋值，A在下的真值为f(t1, t2, …, tn)。 【定理1.24】{?, ?, ?, ?}是联结词的一个完全集。 【证明】根据定义1.23只要证明对任意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+1?A2)表示，其中pk+1是不同于p1, p2, …, pk的一个命题变元。即要证对命题变元p1, p2, …, pk, pk+1的一个真值赋值时，A的真值是f(t1, t2, …, tk, tk+1)。当tk+1 = 0时，即pk+1被赋值为0，这时((?pk+1)?A1)与A1等值，而(pk+1?A2)的真值为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.25】{?, ?}, {?, ?}和{?, ?}都是联结词的完全集。 【证明】1. 要证{?, ?}是联结词的一个完全集，只要证任一命题公式可与一个只含?和?的命题公式等值，事实上有： (A?B)?((?A)?B) (A?B)?(?((?A)?(?B))) 2. {?, ?}是联结词的一个完全集，因为： (A?B)?(?((?A)?(?B))) (A?B)?((?A)?B) 3. {?, ?}是联结词的一个完全集，因为：

16

(A?B)?(?((?A)?(?B))) (A?B)?((?A)?B) 事实上，上述每个集合都是极小的完全集，即不能再从集合中去掉任意一个联结词还能保持是完全集。

□

【定理1.26】{?, ?, ?, ?}不是联结词的完全集。 【证明】总取0值的真值函数不能由只含此联结词集中的联结词的命题公式来表达，因为这样的命题公式当所有命题变元都真值赋值为1时真值为1，不可能为0。 □

6. 命题公式的范式

【定义1.27】将命题符号（代表命题变元或命题常量）或命题符号的否定统称为文字(literal)。仅由有限个文字构成的析取式称为简单析取式。仅由有限个文字构成的合取式称为简单合取式。

【例子1.8】文字、简单析取式与简单合取式： (1) p, ?q等为文字，也是一个文字的简单析取式和简单合取式 (2) p?q, p?(?q)等为两个文字的简单析取式，p?q?(?r)为三个文字的简单析取式 (3) p?q, p?(?q)等为两个文字的简单合取式，p?q?(?r)为三个文字的简单合取式 【定理1.28】一个简单析取式是永真式当且仅当它同时含一个命题符号及其否定，一个简单合取式是矛盾式当且仅当它同时含一个命题符号及其否定。 □ 【定义1.29】由有限个简单合取式构成的析取式称为析取范式(disjunctive normal form)，由有限个简单析取式构成的合取式称为合取范式(conjunctive normal form)。析取范式和合取范式统称为范式(normal form)。

【例子1.9】析取范式和合取范式： (1) (p?q)?(?p??q), (p?r)?(q??r?p)?(?r??p)等是析取范式 (2) (p?q)?(?p??q), (p?r)?(q??r?p)?(?r??p)等是合取范式 根据定义1.18知，一个析取范式的对偶式是合取范式，一个合取范式的对偶式是析取范式。

【定理1.30】一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。一个合取范式是永真式当且仅当它的每个简单析取式都是永真式。

【定理1.31】（范式存在定理）任意命题公式都存在与之等值的析取范式与合取范式。 求一个公式的范式的步骤如下：

[1]. 利用蕴涵等值式(A?B)?(?A?B)和等价等值式(A?B)?(?A?B)?(A??B)消除公式中的联结词?和?，使得公式中只含有联结词?、?和?。

[2]. 利用双重否定律??A?A和德摩尔根律将否定放到命题符号前。

[3]. 利用分配律，求析取范式利用?对?的分配律，求合取范式则利用?对?的分配律。 【例子1.9】求命题公式的析取范式和合取范式 (1). 求(?p?q)?(p?r)的析取范式和合取范式 (2). 求(p?q)?(p?r)的析取范式和合取范式 【解答】(1)求(?p?q)?(p?r)的析取范式： (?p?q)?(p?r)?(??p?q)?(?p?r) // 蕴涵等值式 ?(p?q)?(?p?r)?(p??p)?(p?r)?(q??p)?(q?r) // 双重否定律和分配律 ?(p?r)?(q??p)?(q?r) // (p??p)是矛盾式 显然(?p?q)?(p?r)的合取范式为(p?q)?(?p?r)。 (2)求(p?q)?(p?r)的合取范式： (p?q)?(p?r)?(?p?q)?(p?r)? (?p?q?p)? (?p?q?r) 显然(p?q)?(p?r)的析取范式为(?p)?q?(p?r)。

17

注意：一个命题公式的合取范式和析取范式不具有唯一性。 【定义1.32】在含有n个文字的简单合取式中，若每个命题符号和其否定不同时存在，而二者之一必须出现且只出现一次，且第i个命题变元或者否定出现在从左边算起的第i个位置上（若命题变元无下标，则按字典顺序排列），这样的简单合取式称为极小项。 极小项是特殊的简单合取式。含n个文字的极小项中，由于每个命题变元以原形或否定出现且仅出现一次，因此n个命题变元共可产生2n个不同的极小项。若在极小项中，将命题变元的原形对应1，否定对应0，则每个极小项唯一地对应一个二进制数，该二进制数的每一位正是使该极小项的真值为1的真值赋值。 【例子1.10】两个命题变元p, q生成的4个极小项为： ?p??q对应00，记为m0 ?p?q对应01，记为m1 p??q对应10，记为m2 p?q对应11，记为m2 由三个命题变元p, q, r生成的8个极小项为： ?p??q??r对应000，记为m0 ?p??q?r对应001，记为m1 ?p?q??r对应010，记为m2 ?p?q?r对应011，记为m3 p??q??r对应100，记为m4 p??q?r对应101，记为m5 p?q??r对应110，记为m6 p?q?r对应111，记为m7 【定义1.33】若析取范式中的简单合取式都是极小项，则称该析取范式为主析取范式。 【定理1.34】任何命题公式存在唯一的主析取范式。 求一个公式的主析取范式是： [1] 先求该公式的一个析取范式。 [2] 如果该析取范式的某个简单合取式A中既不含某个命题变元p，也不含它的否定?p，则该简单合取式变为如下形式：(A?p)?(A??p)。 [3] 消除重复出现的命题变元或命题变元的否定，矛盾式及重复出现的极小项，并将每个极小项的命题变元或其否定按下标顺序或字典顺序排列。

【例子1.11】求命题公式的主析取范式 (1). 求(?p?q)?(p?r)的主析取范式 (2). 求(p?q)?(p?r)的主析取范式

【解答】(1)根据例子1.9知(?p?q)?(p?r)的一个析取范式是(p?r)?(q??p)?(q?r)，我们将其中的每个简单合取式展开为含有所有命题变元的极小项的析取：

(p?r)展开为(p?q?r)?(p??q?r) (q??p)展开为(?p?q?r)?(?p?q??r) (q?r)展开为(p?q?r)?(?p?q?r)

因此(?p?q)?(p?r)的主析取范式为(p?q?r)?(p??q?r)?(?p?q?r)?(?p?q??r)，按极小项所对应的二进制数的大小重新排列为(?p?q??r)?(?p?q?r)?(p??q?r)?(p?q?r)。

(2)根据例子1.9知(p?q)?(p?r)的一个析取范式为(?p)?q?(p?r)，将其中每个简单合取式展开为含有所有命题变元的极小项的析取： (?p)展开为(?p?q?r)?(?p??q?r)?(?p?q??r)?(?p??q??r) q展开为(p?q?r)?(?p?q?r)?(p?q??r)?(?p?q??r) (p?r)展开为(p?q?r)?(p??q?r)

因此(p?q)?(p?r)的主析取范式为：

(?p??q??r)?(?p??q?r)?(?p?q??r)?(?p?q?r)?(p??q?r)?(p?q??r)?(p?q?r)

主析取范式也可从命题公式的真值表更容易地得到，对应地，根据命题公式的主析取范式也可容易地构造其真值表、判定其类型（矛盾式、可满足式还是永真式）等。 关于极大项、主合取范式等有关内容学生根据教材自学。

作业：教材p60的9, 10, 11, 15, 17。

18

7. 命题演算系统

命题演算系统是研究利用命题逻辑公式进行推理的形式系统。这里的推理指的是前提和结论之间的逻辑关系，因此这种形式系统本身不注重前提本身的正确性，而关心的是是否能从前提有效地推出结论，讨论什么是结论的有效证明。前提本身的正确性要在赋予形式系统一定的解释的基础上才能确定，这种解释可以说是形式系统的语义。命题演算系统作为一个形式系统研究如何从公理，通过有限的规则来构造有效的证明，这种证明仅仅是符号的改写，本身没有什么含义。 一个形式系统包括符号表、公式、公理及规则，符号表定义形式系统所使用的所有符号，公式是符号表上字符串，公式定义哪些字符串是形式系统所研究的合法对象。公理是构造一切证明的前提，公理本身的正确性在形式系统中不关心，认为是不证自明的公式。当然在构造形式系统的时候，公理的选择是一定的外在依据的。规则是从公理出发构造形式系统中定理的方法。定理就是从公理出发，使用规则能够构造出有效证明的公式，形式系统就是研究能够得到什么定理。 【定义1.35】命题演算系统P定义为： 1. P的符号表包括： [1]. 命题变元：小写英文字母并可加下标 [2]. 联结词：?、? [3]. 辅助符号：(, )（园括号） 2. P的公式归纳定义为： [1]. 命题变元是公式 [2]. 若A是公式，则(?A)也是公式 [3]. 若A和B是公式，则(A?B)也是公式 [4]. 所有公式都是通过有限次使用[1]、[2]和[3]得到。 3. P的公理有如下三类： [A1]. (A?(B?A)) [A2]. ((A?(B?C))?((A?B)?(A?C)) [A3]. (((?A)?(?B))?(B?A)) 4. P的规则只有一条： [M]. 分离规则：由A和(A?B)可得到B

□

【注解】关于以上定义，需要注意以下几点： 1. 在系统P中只使用联结词?和?，这使得系统P比较简单，但也失去了使用另外三个联结词?、?和?的方便之处，为此可作如下约定，对于P中公式A和B： (A?B)代表((?A)?B) (A?B)代表(?((?A)?(?B))) (A?B)代表((A?B)?(B?A)) 注意，?、?和?不是系统P的符号，只不过是为了使用方便而引入的符号。 2. 上述给出的公理是一种模式，其中每一条公理实际上代表了无限多个公式，因为其中的A, B, C是一个符号，实际上可代表任意的公式，例如对于[A2]，其中A可代表B?C得到： (((B?C)?(B?C))?(((B?C)?B)?((B?C)?C))

注意在使用公式A替换公式B的符号C时，要将公式A替换B中所有的C。同样分离规则也是一个模式。

19

【定义1.36】命题演算系统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, Aj?Ai}或{Aj, Ak} = {Ak, Ak?Ai}。 3. 若A1, A2, …, An是An的一个证明，则对每个Ai(1? i ? n)都有├Ai。

4. P的每个公理都是P中的内定理。

5. 要证明一个公式A为P的内定理，只要给出A的证明序列即可。

【例子1.12】设A, B是P中的公式，证明：├(A?B)?(A?A)

【证明】 (1). ├A?(B?A) // 公理[A1] (2). ├(A?(B?A))?((A?B)?(A?A)) // 公理[A2]，其中C用A代替 (3). ├(A?B)?(A?A) // 分离规则(M)及(1)和(2) 【例子1.13】设A是P中的公式，证明：├(A?A) 【证明】 (1). ├A?((B?A)?A) (2). ├(A?((B?A)?A))?((A?(B?A))?(A?A)) (3). ├((A?(B?A))?(A?A)) (4). ├(A?(B?A) (5). ├(A?A) 【定理1.37】设A, B, C是P中的三个公式： [1]. 若├A，且├A?B，则├B [2]. 若├A?B，且├B?C，则├A?C 【证明】[1]就是分离规则。对于[2]，证明如下： (1). ├(B?C)?(A?(B?C)) (2). ├(B?C) (3). ├(A?(B?C)) (4). ├(A?(B?C))?((A?B)?(A?C)) (5). ├(A?B)?(A?C) (6). ├(A?B) (7). ├(A?C) 以后称此定理的[2]为传递规则(Tr)。 【例子1.15】证明：├(?A)?(A?B) 【证明】 (1). ├(?A)?((?B)?(?A)) (2). ├((?B)?(?A))?(A?B)

20

// 公理[A1] // 公理[A2]

// 分离规则(M)及(1)和(2) // 公理[A1]

// 分离规则(M)及(3)和(4)

// [A1] // 前提 // 分离规则 // [A2]

// 分离规则 // 前提 // 分离规则

□

// [A1] // [A3]

(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

46

第三讲 集合论

一、集合的基本概念和运算

1. 集合的基本概念

·集合(set)：集合是数学中最基本的概念之一，不能以更简单的概念来定义(define)，只能给出它的描述(description)。一些对象的整体就称为一个集合，这个整体的每个对象称为该集合的一个元素(member或element)。

·用大写字母A, B, C等表示集合，用小写字母a, b, c等表示集合的元素 ·a?A表示：a是集合A的元素，或说a属于集合A

·a?A表示：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的子集，记为A?B，如果a属于集合A则a也属于集合B。因此A=B当且仅当A?B且B?A。说集合A是集合B的真子集(proper subset)，如果A?B且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)和A?P(A) ·补集(complement set)：集合A的补集，记为A，是那些不属于集合A的元素所构成的集合，即A = {x | x?A}。通常来说，是在存在一个全集U的情况下讨论集合的补集。全集U是所讨论的问题域中所有元素所构成的集合。

2. 集合的基本运算

·集合的并(union)：集合A和B的并A?B定义为：A?B = {x | x?A ? x?B}，集合的并可推广到多个集合，设A1, A2, …, An都是集合，它们的并定义为：

A1?A2…?An = {x | ?i(x?Ai)} ·集合的交(intersection)：集合A和B的并A?B定义为：A?B = {x | x?A ? x?B}，集合的交也可推广到多个集合，设A1, A2, …, An都是集合，它们的交定义为： A1?A2…?An = {x | ?i(x?Ai)} ·集合的相对补：集合B对A的相对补集A?B定义为：A?B = {x | x?A ? x?B}。集合B对全集U的相对补集记为~B，称为B的绝对补集。

47

·集合的对称差：集合A和B的对称差A?B定义为：A?B = (A?B)?(B?A)，对称差的一个等价定义是：A?B = (A?B) ? (A?B) ·集合的运算可使用文氏图形象地表示。 ·集合的运算中，~优先于并、交、相对补及对称差，后面四种运算的顺序由括号决定。

作业：教材p132的3、4、6

3. 集合恒等式

·集合的基本恒等式包括幂等律、结合律、交换律、分配律、同一律、零律、排中律、矛盾律、吸收律、德·摩尔根律、双重否定律，其中最重要的恒等式有： 吸收律： A?(A?B) = A A?(A?B) = A 德·摩尔根律： A?(B?C) = (A?B)?(A?C) A?(B?C) = (A?B)?(A?C) ·例3.2、例3.3表明证明集合恒等式的一个重要方法是，如果要证明集合 A = B，即可证明对任意的x?A有x?B，且对任意的x?B有x?A。 ·其它的一些有关集合运算的性质：

(A?B)?A (A?B)?B A?(A?B) B?(A?B) (A?B)?A A?B ? (A?B) = B ? (A?B) = A ? (A?B) = ? (A?B) = (A? ~B) A?B = B?A A?(B?C) = (A?B)?C A?? = A A?A = ? A?B = A?C ? B = C

·例3.5、例3.6、例3.7运用上述性质来证明集合的恒等式。

4. 有穷集合的计数

·含有有限个元素的集合称为有穷集合（有限集合，finite set），有限集合A的元素个数通常记为|A|。 ·A的幂集P(A)的元素个数有如下等式：| P(A)| = 2|A|。 ·使用文氏图再加上列方程组，求解方程组的办法可解决许多有关集合计数的问题，例3.8、例3.9采用了这种方法。 ·集合计数中一个很重要的定理称为容斥原理，其简单形式如下：

|A?B| = |A| + |B| ? |A?B|

|A?B?C| = |A| + |B| + |C| ? |A?B| ? |B?C| ? |A?C| + |A?B?C| 设U为全集，|~A| = |U| ? |A| ·使用容斥原理求解例3.9：

设：A = 会打排球的人、B = 会打网球的人、C = 会打篮球的人，即按题意有： |A| = 12, |B| = 6, |C| = 14, |A?C| = 6, |B?C| = 5, |A?B?C| = 2

根据容斥定理有：|A?B?C| = |A| + |B| + |C| ? |A?B| ? |B?C| ? |A?C| + |A?B?C|，即： |A?B?C| = 14 + 12 + 6 - |A?B| - 5 - 6 + 2,

即|A?B?C| = 23 - |A?B|，而且根据题意有：|B?(A?C)| = 6，即：

|(B?A)?(C?B)| = |(B?A)| + |(C?B)| - |A?B?C| = 5 + |(A?B)| - 2 = 6，

即|(A?B)| = 3，所以|A?B?C| = 20，所以不会打这三种球的人为25 - 20 = 5人。

5. 例题分析

作业：教材p133~135的8、9、11、13

48

49

(3). ├(?A)?(A?B) // 传递规则

【例子1.16】证明：

[1]. ├(??A)?A [2]. ├A?(??A)

【证明】[1]的证明如下： (1). ├(??A)?(?A????A) // 例子1.15 (2). ├(?A????A)?(??A?A) // [A3] (3). ├(??A)?(??A?A) // 传递规则 (4). ├(??A?(??A?A))?((??A???A)?(??A?A))// [A2] (5). ├(??A???A)?(??A?A) // 分离规则 (6). ├(??A???A) // 例子1.13 (7). ├(??A?A) // 分离规则

[2]的证明如下： (1). ├(???A)?(?A) (2). ├(???A??A)?(A???A) (3). ├A???A

// [1] // [A3]

// 分离规则

【注解】通过以上例子，我们可发现在构造公式的证明中可使用如下方法： 1. 可灵活地使用公理，公理中的每个符号代表的是无限多的公式，公理中某个符号的所有出现可用某个公式替换。但这与教材p43页的置换规则不同，教材没有为命题逻辑公式的推理建立形式系统，而是根据命题逻辑公式的真值来讨论推理，因此有所谓的等值公式的置换，而我们这里所定义的形式系统还没有涉及到真值赋值，这里的证明仅仅是符号的改写。

建立形式系统的方法更符合计算机的思维方式，因为程序从本质来说也是个形式系统，计算机将输入变换到输出也只是符号的改写，至于程序员所认为的程序功能，是程序员赋予程序的解释，这种解释计算机并不理解。也就是说，对于计算机学科，形式系统的推导和形式系统的含义是分开的，正是这种分离，才使得形式系统的推导可由计算机来机械地完成，而人们又可以赋予形式系统各种各样的解释来完成人们所需要的功能。

2. 可使用分离规则和传递规则来构造证明。

3. 可使用已经证明过的内定理作为前提，这相当于教材p43页的结论引入规则。 4. 教材中所讨论的推理是在某种前提下的推理，下面我们在命题演算系统P中来定义这种推理。

【定义1.38】设?是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。

21

4. 易证，若A??，则有?├A。

【例子1.17】证明：{A, B?(A?C)}├(B?C)

// 前提 // 公理[A1] // 分离规则: (1)和(2) // 前提 // 公理[A2] // 分离规则: (4)和(5) // 分离规则: (3)和(6) 下面利用上述定义和定理来形式化地讨论教材p42中给出的推理定律的正确性。这里形式化的含义是不通过对公式的真值讨论，而只是根据P系统的公理和分离规则来证明那些推理定律，当然证明时允许使用我们已经证明过的内定理。为此，我们首先给出命题演算系统中最重要的一条定理，即演绎定理，通过演绎定理可将在某个前提?下的证明与P系统中的内定理相联系起来，并简化内定理的证明。 【定理1.39（演绎定理）】设?是P中的公式集，A和B是P中的两个公式，若??{A}├B，则?├A?B。

【证明】略。 □ 【定理1.40（演绎定理的逆定理）】设?是P中的公式集，A和B是P中的两个公式，若?├A?B，则??{A}├B。

【证明】略。 □ 由以上两个定理，我们得到：

【推论1.41】{A1, A2, …, An}├A当且仅当├(A1?(A2?…?(An?A)…)) □ 当? = {A1, A2, …, An}时，我们通常将?├A写为A1, A2, …, An├A。 根据演绎定理，分离规则可表示为A, A?B├B，或用内定理表示为├A?((A?B)?B)。 【证明】 (1). A (2). A?(B?A) (3). (B?A) (4). (B?(A?C)) (5). (B?(A?C))?((B?A)?(B?C)) (6). (B?A)?(B?C) (7). (B?C)

对于传递规则，可推广为： 【定理1.42】设?是P中的公式集，A1, A2, …, An为P中的公式，若有?├A1, ?├A2, …, ?├An，且A1, A2, …, An├A则?├A。

【证明】略。 □ 对于上述定理1.39, 1.40, 1.42的证明可参考王悍贫编著的《离散数学第一分册——数理逻辑》（北京大学出版社，1997）的p70-75。我们可将?├A1, ?├A2, …, ?├An简记为?├A1, A2, …, An。

【例子1.18】证明：{A?B, ??A}├ (??B)

【证明】 (1). (??A)?A // 例1.16 (2). ??A // 前提 (3). A // (1)使用演绎定理，然后使用分离规则 (4). A?B // 前提 (5). B // 分离规则 (6). B?(??B) // 例1.16 (7). ??B // 演绎定理及分离规则

由此可得：├(A?B)?(??A???B)，又由于├(??A???B)?(?B??A)（公理[A3]）得到├(A?B)?(?B??A)。

22

【例子1.19】证明：├A?(?B??(A?B))

【证明】 (1). ├A?((A?B)?B) // 分离规则的内定理形式 (2). ├((A?B)?B)?(?B??(A?B)) // 例子1.18 (3). ├(?B??(A?B)) // 传递规则

【定理1.43】合取的引入和消除：

[1]. A, B├A?B // 合取的引入 [2]. A?B├A, B（这代表A?B├A及A?B├B）。 // 合取的消除

【证明】首先注意到A?B是?(?A??B)的简写，即?(A??B)的简写。要证明[1]，根据

演绎定理知就是要证明├A?(B??(A??B))，这由例子1.19可得（将其中的?B换成B即可）。要证明[2]，只要证明A?B├A即可，因为A?B├B可同理得证。要证明A?B├A，按演绎定理，即要证├(?(A??B))?A，而根据例子1.15有├(?A)?(A??B)，而根据公理[A3]有├(?A)?(A??B)?((?(A??B))???A)，根据传递规则有├(?(A??B))???A，再根据例子1.16有├(??A?A)，再根据传递规则得├(?(A??B))?A。

□

实际上教材中的符号?就是这里的├，再根据定理1.43就有教材p42的假言推理就是

分离规则，合取的化简就是定理1.43，拒取式就是例子1.18，假言三段论就是传递规则。下面给出关于析取的规则的证明，为此我们先给出下面几个例子： 【例子1.20】证明：A??B, A?B, A├C 【证明】 (1). A // 前提 (2). A?B // 前提 (3). B // 分离规则 (4). A??B // 前提 (5). ?B // 分离规则: (1)和(4) (6). ?B?(B?C) // 例子1.15 (7). B?C // 分离规则: (5)和(6) (8). C // 分离规则: (7)和(3) 该例子的直观含义是，如果从命题A能推出B及B的否定，那么A能推出任何公式。由此可得到├(A?B)?((A??B)?(A?C))。 【例子1.21】证明：A?B, ?A?B├B

【证明】 (1). (A?B)?(?B??A) // 例子1.18 (2). A?B // 前提 (3). ?B??A // 分离规则 (4). (?A?B)?(?B???A) // 公理[A3] (5). ?A?B // 前提 (6). ?B???A // 分离规则: (4)和(5) (7). (?B??A)?((?B???A)?(?B??(A?B))) // 例子1.20 (8). (?B???A)?(?B??(A?B)) // 分离规则: (3)和(7) (9). ?B??(A?B) // 分离规则: (6)和(8) (10). (?B??(A?B))?((A?B)?B)) // 公理[A3] (11). (A?B)?B // 分离规则: (9)和(10)

23

(12). B // 分离规则: (2)和(11) 该例子的直观含义是，如果命题B既能从A推出，又能从?A推出，那么B就是永真的。由此可得到├(A?B)?((?A?B)?B)。 这样我们可证明关于析取的重要定理：

【定理1.44】析取的引入和消除：

[1]. A├A?B, A├B?A // 析取的引入，教材p42中的附加定律 [2]. A?B, C?B, A?C├B // 析取的消除 【证明】注意A?C是(?A?C)的简写，那么根据演绎定理，[1]的前一个式子就是例子

1.15，后一个式子则是公理[A1]。而[2]的证明如下：

(1). ?A?C // 前提A?C (2). C?B // 前提 (3). ?A?B // 分离规则 (4). A?B // 前提 (5). B // 例子1.21

□

根据演绎定理，定理1.44的[2]也可陈述为，若有A├B，且C├B，那么有A?C├B。根据该定理，我们可得到教材p42中关于析取的其他定律：

【例子1.22】证明： [1]. A?B, ?B├A // 析取三段论 [2]. A?B, C?D, A?C├B?D // 构造性二难推理

【证明】[1]的形式是?A?B, ?B├A，这可证明如下：

(1). (?A?B)?(?B???A) (2). ?A?B (3). ?B???A (4). ?B (5). ??A (6). ??A?A (7). A [2]的证明如下： (1). A?B (2). B?B?D (3). A?B?D (4). C?B?D (5). A?C (6). B?D 【例子1.23】证明：├(?A?A)?A 【证明】只要证(?A?A)├A

(1). (2). (3). (4). (5). (6).

// 公理[A3] // 前提 // 分离规则 // 前提 // 分离规则 // 例子1.16 // 分离规则

// 前提

// 定理1.44，析取的引入 // 分离规则 // 与(1)~(3)类似 // 前提

// 定理1.44，析取的消除

?A?(A??(?A?A)) // 例子1.15

(?A?(A??(?A?A)))?((?A?A)?(?A??(?A?A))) //公理[A2] ((?A?A)?(?A??(?A?A))) //分离规则 ?A?A // 前提 ?A??(?A?A) // 分离规则: (3)和(4) (?A??(?A?A))?((?A?A)?A) // 公理[A3]

24

(7). (?A?A)?A // 分离规则: (5)和(6) (8). A // 分离规则: (4)和(7) 【例子1.24】证明：?A?B, ?A??B├A

【证明】 (1). (?A?B)?((?A??B)?(?A?A)) // 例子1.20 (2). (?A?B) // 前提 (3). (?A??B)?(?A?A) // 分离规则 (4). ?A??B // 前提 (5). (?A?A) // 分离规则: (3)和(4) (6). (?A?A)?A // 例子1.23 (7). A // 分离规则: (5)和(6) 读者可很容易地看出，教材p46的附加前提证明法就是演绎定理的特殊形式，而归谬法则相当于例子1.24. 最后我们来讨论命题演算系统的元问题，即该形式系统的可靠性、一致性和完备性。可靠性是指命题演算系统P中的内定理是否都是永真式，一致性是指P是否存在公式A，使得├A和├(?A)都成立，如果存在这样的公式，则由例子1.20知P可推出任何公式，这时P便没有任何意义。完备性是指P是否能推出命题逻辑公式的所有永真式。下面定理说明P是可靠的、一致的和完备的。 【定理1.45】对于P的任意一个公式A，若有├A，则A是一个永真式。 □ 【定理1.46】不存在P的一个公式A，使得├A和├(?A)都成立。 □ 【定理1.47】若A是P的永真式，则有├A。 □ 有了定理1.47之后，要看一个公式A是否是内定理，只要使用真值表的方法检查A是否是永真式即可。定理1.47表明我们在这里构造的形式系统与教材中的推理理论是完全一致的，但正如前面所指出的，形式系统的构造才是计算机学科的核心思想。关于命题逻辑的推理理论的实际应用关键在于将实际中的陈述句符号化，具体的例子请读者自己参考教材。

作业：教材p63-64的23, 24, 25。

25

等值变换关系。 [5]. 用Z(x)表示x是一个整数，则可符号化为： (?x)(Z(x) ? (?y)(Z(y) ? (x>y) ) ) [6]. 符号化为：(??)((? > 0)?(?? )((? >0) ? ((|x-a|

【例子2.4】将下列命题符号化： [1]. 每一个有理数都是实数 [2]. 某些实数是有理数 [3]. 不是没一个实数都是有理数 [4]. 存在偶素数 [5]. 会叫的狗未必会咬人 [6]. 每个人的外祖母都是他母亲的母亲 [7]. 任何自然数的后继数必大于零 [8]. 有些液体能溶解任何金属 [9]. 任何金属均可溶解于某种液体中 [10]. 没有不犯错误的人 [11]. 小莉是非常聪明和美丽的 [12]. 小李是一个田径运动员

【解答】（请同学们下载后，先思考，课堂上讲解）

【例子2.5】将下列公式翻译成自然语言，并确定其真值，这里假定个体域是正整数： [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。 【解答】（请同学们下载后，先思考，课堂上讲解） 【例子2.6】给定下述谓词，请把下列公式翻译成自然语言： 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。

31

3. 一阶逻辑公式及解释

每个系统有它自己的符号表，由这些符号表所构成的某些符号串是该系统中的语言，也是我们所研究的目标语言。

【定义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. 一阶逻辑中的逻辑符号对于将一阶逻辑应用于任何问题时都是通用的、不变的，而其中的非逻辑符号则在不同的应用问题（或者说不同的讨论范围）中有所不同，可以变化，因此一阶逻辑语言的表达能力是非常强的，它可通过采用不同的非逻辑符号来增强自己的表达能力。

【定义2.4】一阶逻辑语言的项(term)递归定义为： [1]. 个体常项和个体变项是项；

[2]. 若f (x1, x2, …, xn)是n元函数，t1, t2, …, tn是n个项，则f (t1, t2, …, tn)是项； [3]. 一阶逻辑语言的所有项都通过有限次使用上述两步生成。

【定义2.5】一阶逻辑语言的合式公式(well-formed formula)递归定义为：

[1]. 若F(x1, x2, …, xn)是n元谓词，t1, t2, …, tn是n个项，则F(t1, t2, …, tn)是合式公式，此类合式公式称为原子公式；

[2]. 若A、B是合式公式，则(?A)、(A?B)、(A?B)、(A?B)、(A?B)也是合式公式； [3]. 若A是合式公式，则(?x)A、(?x)A也是合式公式；

[4]. 一阶逻辑语言的所有公式都通过有限次使用上述步骤生成。

通常用r, s, t, ri, si, ti, …等表示项，而用A, B, C, …Ai, Bi, Ci, …表示合式公式。 【注解】

1. 一阶逻辑语言的合式公式随着采用不同的非逻辑符号而不同，但对于不同的非逻辑符号采用相同的方式构造公式，一旦非逻辑符号确定之后，则一阶逻辑公式也就确定下来了，所以可以说一阶逻辑公式是某个非逻辑符号集生成的语言。

2. 虽然说采用不同的非逻辑符号可生成不同的一阶逻辑公式，但所有一阶逻辑公式的逻辑符号是相同的，而我们在这里对一阶逻辑的讨论只是讨论这些逻辑符号的性质，而与非逻辑符号无关，则我们的讨论对于任意的非逻辑符号生成的一阶逻辑公式都是成立的。

3. 一阶逻辑语言的直观意义容易理解：“符号表”相当于英语的字母表，“项”相当于单词或词组，它们不表达完整的判断，还只是代表个体，而“公式”则代表完整的句子。而其中的函数符号用来构造复杂的个体（项），谓词符号则用来构造最原子的公式。

32

4. 在定义2.5的[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). A1?A2?…?An-1?An表示(A1?(A2?…?(An-1?An)…))。 (4). 量词的优先级高于任何联结符号，所以(?x)A、(?x)A可分别写成?xA、?xA，但要注意明确量词的辖域（下面定义什么是辖域）。

【定义2.6】称公式(?x)A中的A为量词(?x)的辖域(scope)，称公式(?x)A中的A为量词(?x)的辖域。称变元x在公式A中的某处出现是约束出现，如果该出现处于量词(?x)或(?x)的辖域内，或者就是量词中的x。若x在公式A中的某处出现不是约束出现，则此出现称为自由出现。 【例子2.7】(教材p76的例2.6。)指出下列公式中，各量词的辖域以及变元的自由出现和约束出现：

[1]. ?x(F(x, y, z)??yG(x, y)) [2]. ?xF(x, y)?G(x, y) [3]. ?x?y(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))

? ? ? ? ? ? 约束 约束 约束 约束 约束 约束

【定义2.7】设变元x在公式A中出现，如果x在A中的所有出现都是约束出现，则称x为A的约束变元(bounded variable)，否则称x为A的自由变元(free variable)。

【注解】 1. 变元x在公式A中可同时有约束出现和自由出现两种情况，而只有当x的所有出现都是约束出现时，称x为A的约束变元。 2. 为了明确起见，我们通常在用字母A, B, C, …表示一阶逻辑公式时，同时列出该公

33

式中的自由变元，而写成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)))

在使用一阶逻辑公式符号化命题时，要小心地选择变元，以使得到的公式满足上述两个条件。

【定理2.8】约束变元换名规则和自由变元替换规则：

[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. 这里的等价于后面要讲的等值（目前可参考命题逻辑公式的等值）不一样，等值建立在某种解释下，而这里的等价只与语法有关，换名规则和替换规则只是在某种意义上说明公式中使用的变元是可任意选择的，选择不同的变元对于公式的本质没什么改变，就象在编写同一程序时，不同的程序员给具有同样功能的变量起不同名字一样，不影响程序本身的功能。

【例子2.8】使用换名规则和替换规则变换下列公式，使得满足定义2.7 的注解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))。

【定义2.9】如果公式A没有自由变元，则称公式A为闭公式(closed formula)。

34

一阶逻辑公式的含义（解释）显然比命题逻辑公式要复杂得多，因为一阶逻辑公式有非逻辑的符号。对于一阶逻辑公式的解释依赖于一阶逻辑公式所基于的非逻辑符号。 设有非逻辑符号集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的解释。

【定义2.10】非逻辑符号集L的一个解释[[L]]由四个部分组成： [1]. 一个非空集合D，D称为解释[[L]]的论域；

[2]. 对于C的个体常项c，其解释为[[c]]? D是D中的某个元素；

[3]. 对于F的n元函数f，其解释是D上的一个n元函数：[[f ]] : Dn?D； [4]. 对于P的n元谓词F，其解释是D上的一个n元关系：[[F]] ? Dn(= D ?..? D) 【注解】 1. 定义2.10所给出的解释方法是对非逻辑符号集的一种最直观的解释，称为非逻辑符号集L的塔斯基(Tarski)语义，塔斯基是研究语义学的一个最有名的学者，这种语义解释方法在各种自然语言及形式语言的语义研究中也被广泛使用。 2. 对L的一个解释也可看成是为L构造了一个模型，研究一个形式语言的模型的有关内容构成了数理逻辑的一个重要分支：模型论(Model Theory)。 3. 教材p79的定义2.7给出的定义实际是一个不严谨的、直观的定义，因为教材在此之前没有引进函数、关系等概念。该定义的本质与我们这里的定义是一致的，因此根据书上的记号，我们也用符号I来表示某个解释。要说明的是，教材例2.7中所给定的谓词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>} ?D1?D1，是一个二元关系。 4. 给定一阶语言，我们可以构造它的一个解释，我们也可以给定一个解释所需的东西，然后研究公式的真值，这种研究实际上从某种意义说是对解释的形式化研究。 5. 只给出解释还不能确定Form(L)中的公式的真值，因为公式中可能存在自由变元，必需为这些自由变元指派具体的个体，不指定具体的个体，则带有自由变元的公式还不能成为命题逻辑的公式。教材p81例2.8中的(5)没有真值就是因为它存在自由变元。 6. 以下定义2.11到定义2.14为选学内容，读者如果不理解则可按书上的更直观的定义来学习定义2.14以后的内容。

【定义2.11】给定非逻辑符号集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)在该解释下的一个指派是?。

【定义2.12】项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))

35

本文来源：https://www.bwwdw.com/article/txdh.html