当前位置：文档之家› (完整版)关于集合与集合论

(完整版)关于集合与集合论

第一章关于集合与集合论

在许多数学教材上都会见到这样一种说法：集合论是现代数学的基础，集合概念是数学的基本概念。那么为什么会有这种说法呢？这种说法的依据是什么呢？在这一章，我们将对此给出一种解释。

在本章的第1节，将简要重温一些与集合论相关的基本概念与符号，其中大多数的概念与符号用法是每一个高中生都应当熟悉的。在第2节，本书作者对集合论的意义及其产生的思想渊源进行了介绍和分析，其中有些是作者个人的观点，仅供读者参考。最后两节则是在讲一些基本逻辑常识的基础上，介绍了较为规范的集合表示方法以及用集论语言定义的某些重要数学概念。

§1. 集合论中的常见概念与符号

1.1. 集合概念与属于关系

在集合论中，“集合”这个概念是作为不定义的基本概念，以符号“∈”表示的“属于”关系，也是不定义关系。在朴素集合论中，人们用日常语言给集合概念和属于关系以直观说明。其中最常见的是集合论创始人康托的说法：“将一些明确的（确定的）、彼此有区别的、具体的或理念中抽象的对象看作一个整体，便叫作一个集合。”在本书的前三章，便以康托的这个描述作为“集合”概念含义的说明。理解这个说明，主要注意如下几点.

（1）当我们提到一个集合时，这个集合自身是作为一个整体被看待的；

（2）集合是由可以确定的一些对象个体汇集而成的，也就是说，必须可以清晰判定任何一个对象个体是否在这些对象个体之中，并且可以明确区分开这些对象个体中任何两个不同的对象个体。

（3）在朴素集合论中，集合中的元素既可以是物理世界中的对象，也可以是我们头脑中形成的观念对象。比如：将“北京大学2002年所有在籍学生的全体”作为一个集合，其元素都是具体现实的人（在籍学生）；将“所有实数的全体” 的对象，作为一个集合，其元素（实数）便是由理念抽象的对象组成的集合。作为数学理论，集合论所讨论的集合，基本上都是由人类理念在其抽象过程中产生的对象汇集而成的。只有在将数学应用于现实时，才会涉及到由现实物理世界中的对象作为元素组成的集合。因此，在理解作为数学理论的集合论时，一定要适应抽象的思维方式和观念对象的建构方式。

如果以符号A 表示一个集合，a 表示一个对象个体，假如a 在那些汇集为集合A 的对象个体之中，我们称a 属于A ，记为A a ∈，否则记为A a _

∈。如果A a ∈，称a 是A 的元素，也称集合A 含a 。按照上面的理解，若A 与B 是两个集合，当我们可以判定（证明）A 的元素也都是B 的元素或者可以判定没有任何一个A 中的元素不属于B ，我们称A 被B 所包含，或集合B 包含A ，记为B A ?。集合，注：请读者注意在本书中对“含”与“包含”这两个词汇的不同用法。当B A ?且A B ?时，我们便认为A 与B 是两个完全相同的集合，记为A ＝B ，这时A 与B 作为集合被看作是同

一个对象。如果B A ?，且A ≠B 可以明确记作B A ≠

?，称A 是B 的真子集。 1.2 . 集合运算及某些特殊集合的符号表示

我们假设读者已经熟悉常见的集合运算（的表示方法）及其满足的运算律。这里只将其列出，不给出详细的解释和验证。在下列各式中，将符号,,,,,i i B A B A X A 均表示集合，I 表示指标集。

（1）集合的常见运算

ⅰ）集合的并：A A B A A i ∈

∈??? , , I i ； ⅱ）集合的交；A A B A A i I i ∈

∈??? , , ； ⅲ）集合的差：B A \；

ⅳ）集合的补：若X A ?记A X A C X \=，称A C X 为A 的补集（以X 为全集），当明确X 作为全集，不会引起混淆的情况下，将A C X 简记为C A ； ⅴ）对称差：)\()\(A B B A B A ?=?。

（2）集合运算所满足的运算律

（ⅰ）交换律：A B B A A B B A ?=??=? , ；

（ⅱ）结合律：)()()()(C B A C B A C B A C B A ??=????=?? , ；（ⅲ）分配律)()()()()()(C A B A C B A C A B A C B A ???=?????=?? , ；（ⅳ）迪摩根律：)\()\()(\)\()\()(\C A B A C B A C A B A C B A ?=??=? , ；（ⅴ）幂等律：A A A A A A =?=? , ；

（ⅵ）吸收律：A B A A A B A A =??=??)()( , ；

如果以X 为全集，还有

（ⅶ）同一律：A A A X A =?=?φ , ；

（ⅷ）零律：φφ=?=?A X X A ,

；（ⅸ）补余律：φ=?=?C C A A X A A , ；

（x ）双补律：A A C C =)(；

（xi ）推广迪摩根律：i I

i C i I i i I i C i I i A A A A ∈∈∈∈?=??=?)()( , 。

下面再介绍一种表示集合的并与交运算的方法。

设A 是一个集合，并且A 中的元素也是集合，我们定义

a A a A A

a A a ∈∈?=??=? , 。特别应当注意，只有当A 中元素也是集合的时候，A A ??与才是有意义的。其次，我们还规定：φφ?? , 没有意义。

最后我们引入一些常用集合的表示符号：

N 表示正整数集（以每个正整为其元素）；

Z 表示整数集；

Q 表示有理数集；

R 表示实数集；

[]b a ,表示以b a , 为端点的闭区间；

][b a ,表示以b a , 为端点的开区间；

]][[b a b a ,, , 分别表示左开右闭的和左闭右开的区间（以b a , 为端点）。

§2 集合论的内容和意义

我们总能看到这样的提法：集合论是现代数学的基础。但为什么集合论就是现代数学的基础呢？有些人困惑，像集合这样普通得不能再普通的概念，像各种集合运算（并、交、差）那样简单的运算关系并没有什么特别的困难。为什么集合论却是迟于微积分学二百年才产生呢？以至于有人认为集合论迟到了两千年。其实，要搞清这一点，就要先弄清“集合论”作为一门数学理论，它所研究的核心问题是什么，进而还要搞清数学的发展为什么要考虑这些问题。

2.1 集合论研究什么?

其实，要搞清集合论是干什么的并不困难。假设你面临有一群牛组成的集合，如果从纯数学的角度考虑，对此集合，你能干些什么呢？很显然，那就是“计数”。至于这些牛是否有口蹄疫，并不是数学家感兴趣的事。由此，可以得出结论，“集合论”所要研究的问题就是如何建立为集合（的元素）进行计数的理论。有些初学者依然可能困惑，为集合计数不是太简单了吗?小学生都会。是的，为有限集合计数大家都会，只要学过了自然数就行。但是集合论所研究的都是为“无限集”计数的理论。显然，这可不是一个简单的工作。从这个意义上讲，自然数理论可以看成是关于“有限”的集合论，而集合论可以看成“无限”的“自然数理论”，即自然数理论到无限（集）的推广。

于是就产生了第二个问题，人类的活动都是有限的，所谓“无限”是无法完成的。人们谈论无限时，都只是在说一个无法完成的过程。它有什么必要成为研究的对象呢？

为了说明这一点，有必要回顾高等数学（主要指微积分学）在发展过程中曾

面临的一些问题。

2.2 变量数学，导数与无穷小

许多人认为，微积分学的产生标志着从初等的常量数学时代进入到了高等的变量数学时代。这种以变量与常量来区分高等数学（微积分学）与初等数学的看法也许有以下几点依据。首先，微分学所研究的对象是函数。以当时人们的直观认识，可以认为是在研究各种变量之间的关系，而非常量（数）的运算关系；其次，从所产生的新方法来看，主要引进了像求导数这样的计算。而这个计算，又是以求解两个变量之商在变量趋于0时的生成结果．．．．

为目的的；最后，从表达的语言来看，人们是以直观的动态语汇来描述导数产生过程的。下面的几段论述源自微积分学的两位重要创立者，这些论述表明当时的人们是如何认识导数的。

牛顿认为导数是“量在其中消失的终极比，严格说来，不是终极量的比，而且它与无限减小的这些量所趋近的极限之差虽然能比任意给出的差更小，但是在这些量无限缩小以前既不能越过也不能达到这个极限。”而瞬时速度“既不是在物体达到最后位置、运动停止时之前的速度，也不是达到以后的速度，而是正在到达那一瞬间的速度（是无穷小的比）。即物体以这样的速度到达它的最后位置并且停止。同样的，就消失量的最后比来说，应理解为不是在量消失之前，也不是消失后，而是正当他们消失时的比。”

莱布尼茨认为：“一个过渡的状态或者这个消失的状态是可以设想的，其中实际上仍然没有出现完全相等或精致，……而是进入这样一种状态，即差小于任何给定的量，在这种状态下，得留一些差，一些速度，一些角度，但它们每一个都是无穷小。”莱布尼茨还认为：无穷小是一种理想元素，是一种有用的工具，它们有助于我们通过直观发现真理，而且这些无穷小也可遵循通常的四则运算法则进行运算。他们这些费力的解释是为了回答导数dx

dy 或)('t 是不是00的问题。这也是现代某些没能深刻理解极限概念的人所追问的问题。当时，一位著名的主观唯心主义哲学家贝克莱主教曾向微积分的拥护者们提出了类似的问题。当牛顿和莱布尼茨以无穷小之比来说明导数时，它们无法回答“无穷小”到底是个什么东西。一个不是0又比任何实数（的绝对值）都小的量还是数吗？显然不是，因为实数里面没有它。这个像幽灵一样的“无穷小量”一直困扰着当时的数学家们。这个思想上的困扰被人们称为数学史上的第二次危机。

2.3 标准极限理论的提出——数学思维公式和数学语言的转向

仔细分析前面牛顿和莱布尼茨的那些说法，笔者认为在他们的思想方式中有如下一些局限性。

（1）他们将现实的运动过程与人的思维抽象过程混为一谈。从而，其思想的表达都是用自然语言和直观的动态语汇进行描述。

（2）将导数运算与有限运算看成类似的，即认为最终比是变化过程中自然“生成”的，就如3+5=8一样，8是3于5合在一起才能实现的结果。这种认识

统治了相当长的时间，以至于人们会争议∑∞=-1)1(n n 到底是等于1，0，或是

1。后来，经过达朗倍尔、波尔查诺、柯西，尤其是维尔斯特拉斯等人的工作和思考，导数的“本质”逐渐地清晰起来。这源于极限概念的提出和完善化。最后形成标准化的即ε-语言的极限理论，彻底地澄清了原来在微积分学中的各种概念混乱。那么极限理论的引入是如何解决了“第二次危机”中的困难呢?它在数学发展方向上起到了什么样的作用呢？笔者将对此作一简要分析（后面的某些观点属于个人的看法，仅供参考）。

在任何一本系统讲授微积分的教材中，人们都可以看到ε-语言定义的极限概念。如果教材编写者写得清楚，我们都可以看出，所谓一个函数)(x f 在0x 点处的导数不过是差商0

0)()(x x x f x f x y --=??在x ?趋近于0（x 趋近于0x ）时的极限．．（如果存在）。而按极限的定义，这个极限（如果存在，记为a ）并不是上述x 趋近于0x 所“生成”的结果，而是事先已经“存在”的一个实数a ，当x 趋近于0x 时，差商也不断地“逼近”着这个事先就已存在于那里的数a 。同样，在数列{}N ∈n n x 有极限A 时，这个A 也是一个“事先在那里等候”的实数，极限概念完全回避了“x 是否到了0x ”以及“n 是否都已全部穷尽”这样的问题。

仔细核查ε-语言的极限概念，它起到了如下的作用：

（1）区别了人们的抽象思考过程与现实的运动过程，用可以进行逻辑分析的语言代替了直观动态描述。

（2）摆脱了过去在初等运算中形成的“计算结果生成观”，建立了“无限运算结果的逼近观”；

（3）将所讨论的对象，由无法进行逻辑分析的直观“变量变化”关系转化为两个具有一定结构（顺序与度量结构）的数集之间的结构关系，从而实现了数学对象的“静态”化。

正是以上的这些作用，大大改变了人们对数学的认识，尤其是对数学研究的界定方式及其相关关系的思考方式，并由此引起了数学语言的重要转向。原来以自然语言的动态语汇所给出的直观描述逐渐被人造语言的静态语汇所给出的形式规定所取代。

比如说，过去人们在求瞬时速度、曲线弧长和不规则图形的面积时，总是自然地认为是在求一个客观实在的量。但在现代的数学处理方式中，这些都是利用极限“定义”（规定）的形式对象（起码从纯数学的角度考虑）。

再比如，由于两千多年前爱利亚的芝诺提出的悖论，亚里士多德不愿意承认曲线是由点（或时间是由时刻）组成的，因此人们将曲线看成动点的轨迹。但是当极限概念建立以后，人们开始将目光转向实数点集的结构研究，曲线也就自然被描述成点的集合了。原来变动不居的动态对象，一旦被界定为是由点组成的集合，就完全成了可以进行逻辑分析的静态对象。

2.4 集合论产生的思想渊源

在标准的ε-语言的极限概念产生以前，人们很自然地从直观上想象连续函数基本上都是可导的（除去个别的尖点）。可是极限理论使得严格的逻辑分析取代了直观的想像。正是建立了极限理论的ε-语言定义方式的维尔斯特拉斯构造了处处连续而又处处不可导的函数。这些工作标志着数学开始从直观描述动态“变量的过程联系”，转化为逻辑分析静态“集合结构”的形式关注。然而，将动态的“变量”转化成静态的集合，其集合基本上都是无限集。人们为了消除“无穷小量”带来的矛盾，不得不考虑“无穷多（元素）”的集合。虽然在过去两千多年来，人们一直极力回避谈论无限集，但现在无法回避了。

极限概念的完善化，使得“常量”与“变量”的区别转化为“有限”与“无限”的区别。对数学分析而言，这也是与初等数学最根本的区别。因为判断极限是否存在，在一般情况下无非是判断两个具有一定结构的无限集之间的关系。但是，比较两个无限集的区别，最基本的比较应是集合元素的多少。所以，数学分析的深入（势必）将引起人们对无限集合的“计数”方法的关注。虽然，作为集合论创始人，康托是在研究三角级数展开式唯一性问题时考虑到无限集之间的比较方法问题，就具体问题而言，似乎有一定的偶然性。但以当时的数学发展进程而言，这个偶然却是必然之中的偶然。事实上，在康托之前，就有人在认真地探讨无限集的比较问题。当然，这并不能抹杀康托的功绩。康托是第一个全面冲破了过去陈旧观念束缚的人，因而才有了真正意义的创新并成功的建立了新的理论。

2.5集合论的作用

首先，由于集合论的建立，提供了在一定的逻辑基础上分析无限（集）的方法。因此，人们对无限集以及在无限集上的各种结构关系的研究可以不断深化。从而涉及的无限次集合运算的测度理论被建立起来，这成为建立实变函数，泛函分析，现代概率论以及其它一些现代数学理论分支的基石。

其次，当人们不再以恐惧的心理躲避无限集以后，将数学研究的对象描述成具有一定结构的集合，便成为自然而合理的选择。于是，集合论为绝大部份数学理论分支提供了可以统一使用的语汇，集合语言也就成了几乎所有经典理论数学的统一语言。

最后，在相当广泛地意义上，集合之间关系恰好反映了命题（函项）之间的逻辑关系。如果说人们一直在追求着数学在逻辑上的严密性，那么建立在集合论基础上的数学就几乎接近了人们所期待的标准。

综合上述理由，人们认为集合论是现代数学的基础也确是有道理的。

当然，集合论并没能为整个数学提供终极的基础，它也有一定的局限性。但若是抱着一种较为合理而不过分的期望，集合论为数学发展所提供的平台也算是相当牢固和宽广的。

§3集合语言与命题函项

上一节曾指出，标准极限理论的产生，使得原来数学中的量的变化过程被转化成静态的有结构关系的集合。于是，数学所考察的大量对象也都被描述成了集

合。于是集合论便为一般的数学分支提供了统一可用的语汇。这也是为何有人称集合论是一种语言的原因。但是，如何具体描述一个集合呢？有人说，集合的引入简化了许多逻辑关系。这话有一定的道理。但是，这一点是建立在能够正确描述集合的基础上的。如果不能正确地描述集合，或是不能正确理解对集合的描述，那么集合的引入不仅不能使数学中的逻辑关系清晰和简明，反而会带来大量的混乱。事实上我们在一些文献中，经常会见到不规范的集合描述，从而引起不必要的歧义和误解。为了说明集合表示方法，有必要介绍一点逻辑常识。

3.1逻辑学中的几个概念

（1）逻辑连接词与复合句

一般将一个完整的简单陈述句称为简单句。比如，“3是奇数”就是一个简单句。将若干个简单句连接起来可以组成一个复合的句子，比如，“3是奇数并且9是3的倍数”。此外我们还将一个简单句的否定形式称为复合句。在把一些简单句组合成一个复合句子时主要是利用一些连词。在现代符号逻辑中，规定了一些特定的符号来代替常用的连词，这些符号的引入使复杂句子的形式相对简洁，更为重要的是有助于对句子之间的形式关系进行程式化的分析，从而使逻辑代数化。常见的逻辑连接词有如下几种：

否定词（用符号?表示），其作用相当于自然语言中的“不是…”，“非…”。例如，“x不属于A”，就可以用逻辑符号记为)

?（当然也可以用A

x∈

x?表示）。析取词（用符号∨表示），相当于自然语言中的关联词“…或者…”。比如语句“x 属于A或者x属于B”就可以完全符号化为：B

∈。

∨

x∈

合取词（用符号∧表示），其作用相当于自然语句中的关联词“…而且…”。比如，语句“x属于A且x属于B”可用符号表示为：B

∈。

∧

x∈

蕴涵词（用符号→表示），其作用相当于自然语言中的关联词“若…则…”，“如果…，那么…”。比如语句：“如果x

-x”可用符号表示为

3，那么0

x。

→

逻辑联结词之间也有一种顺序，直观地说，顺序体现的是这些联结词与其它符号的“亲和力”。比如“B

∈”其实意味着这样的理解

∧

x∈

∈。一般地，亲和力最强的是?，然后依次是∧、∨、→。例A

∧

))

(

)

如语句：“如果x是有理数而且y是整数，那么z不是实数”可表示为：

→

∈

∧

∈。

x∈

当A与B是表达正确（即合乎语法要求）的句式时，那么A

→

∨

∧,

也都是表达正确的句式。由此，利用上述逻辑联词，我们可以组成各种复杂的复合句式。

（2）命题与命题函项

一个能判断真假的陈述句称为一个命题。比如：“8是一个偶数”就是一个命题，且是真命题。现考察下面的陈述：x是一个偶数。如果我们将“（）是一个偶数”这个缺失主语的句式简记为)

(p，那么前一陈述句就可以表示为)8(p，

后一陈述句可表为)x(p。正如前述)8(p是一真命题，但是)x(p却不能判断真假，因为我们不知道x是什么。我们将这里的x称为个体变元，自然数8称为个体常元。直观理解，个体变元表示一个未定个体，在本质上)x(p与)

(p是一样的，都缺失明确而具体的主语。而所谓的个体常元则是一个具体而明确的对象。象)x(p这样的句式，不能判断真假，故不是一个命题。但若以一个个体常元，比如3来代换)x(p中的x便得一命题)3(p，我们知道)3(p是假命题。)x(p与函数表达式)

f有类似之处，比如，sinx经常表示一个“函数”，而不是数。但若以

π。源于这种相似处性，我们称)x(p这常元π代换x，便得一具体的数)0

(

sin=

种句式为“命题函项”（或命题函数）。除了含有一个个体变元符号的命题函项，还有含若干个个体变元的函项，比如，“x小于y”就是含两个变元的命题函项，将它简记为)

q。显然，只有当x与y都被个体常元（实数）代换之后，才会

得一命题。

（3）量词

是否有个体变元符号的句式就一定不是命题呢？不是的。比如，“任意一个实数x都小于3”就是一个命题，它是假命题。再比如，“存在一个实数x小于3”是一个真命题。看上去，这两个句式中也有个体变元x，为什么它们会成为命题呢？这可以从两个角度来分析。以第一句为例，它可以有两种解释：（1）“3是实数中最大的”、；（2）“实数集中每个元都小于3”。按第（1）个解释，这是对“3”所下的一个判断，按第（2）个解释，则是将整个实数集作为形式主语。也就是说这些句式并非是对一个个体变元x下什么判断。

数理逻辑中规定了两个特别的符号：?

?,，它们称为“量词符号”。其中“?”表示存在，“?”表示“任意一个”（或“对于任意一个”）。比如，)3

x就

表示“任意x，x小于3”，这里“x

?”（或“x?”）称为一个量词。

在组成复杂句式时，量词有十分重要的作用。假设A是一个表达正确的句式，则xA

?,也都是表达正确的句式（表达正确意指合于规定语法，并不意味命题xA?

本身的真）。

在有量词的句式中，特别要提到量词的辖域。以“)3

x”为例，后面

括号中的x与x

?中的x是表示同一对象的，于是在这个句式中的x都在量词“x

?”的辖域之内。一般规定，量词的辖域包括量词本身以及紧连量词的那个括号内的符号系列。比如，)

?，在)

y=中的x就不属于量词

∧

(

“x

?”的辖域。

另外，还要特别注意的量词的顺序。下面两个句子说明了量词顺序的重要性。设论域是人类，

①y x ??（y 是x 的父亲）。它的日常语言表示为：每个人有一父亲。

②x y ??（y 是x 的父亲），它的日常语言表示为：有一人是每个人的父亲。读者不难看出这两个命题的重大差异，尽管它们只是颠倒了两个量词的顺序。

如果一个变元符号x 在某个量词x ?或x ?的辖域之内，这个变元x 就称为约束变元，不是约束变元的变元称为自由变元。如果一个句式中没有自由变元，就称为“封闭句式”，或简称为“闭式”。从前面的例子，读者可以看出，一个正确表达的“闭式”就是一个“命题”。在通常情况下一个含有自由变元的句式（当然其表达方式要正确）就是一个命题函项而非一个命题。只有在特殊情况下，比如对特定的论域，由于该论域自身特殊性质的限定，使某些含自由变元的句式有时也能被看成命题。比如，以自然数集为论域，句式（x ≤0）就在某些场合下被认为是一个命题，但这个句式作为命题应等价于闭式“)0(x x ≤?”，或者说它只是看作x ?（x ≤0）的一种简写形式。另外，在数理逻辑中必约定，当)(x φ中有自由变元x ，又要将其看成命题，那么它就等价于)(x x φ?。

3.2.集合表示方法

表示一个具体集合的方法视情况而定，大体有两种方式。

（1）描述法（或概括原则）。这是最常见也是最正规的方式方法。它的标准形式为

{x ：)x (p }或{x |)x (p } （1）

其中x 是一个个体变元符号，)x (p 是仅以x 为自由变元的命题函项（在形式上是一个正确表达的只含有一个自由变元x 的句式），而且不是命题。当我们将一个具体对象，比如说是“8”（个体常项），代换)x (p 中x 得到一命题)8(p 。若)8(p 真，则对象“8”就是上述所表示集合的元素：若)8(p 为假，“8”就不是该集合的元素。在利用描述法表示一集合时，应注意以下几点：

ⅰ）{x ，)x (p }与{x ；)x (p }都是不正确的，容易引起误解。在x 与)x (p 之间只能用冒号或竖线来分隔。

ⅱ）一般来说，在（1）式中的)x (p 只能有且必须有一个自由变元。考察下面公式（设论域为自然数集）：

{x ：x ≤0}与{x ：x ?（x ≤0）}

显然前者是自然数集，而后者却没有给出任何具体的集合。再如{x ：y x <}也没有给出明确的集合。前面的问题出在x ?（x ≤0）无自由变元，本身是一命题，而后者多一个自由变元y ，即使将x 代换为常元，仍然无法判定真假。

在有特别约定的情况下，{x ：y x <}这样的表示也可能是有意义的。比如我们在行文中若有如下表述：“对任意R y ∈，记}:{y x R x x A y <∧∈=”，这时y A 的表达式是有意义的，但y A 的确定要由y 的具体取法所决定。事实上，上述的整段话是在规定一族集合，而不是一个集合。其中y 是在{x ：y x <}之外来确定的。

ⅲ）在表示坐标平面的坐标集（或平面中点的集合）时，会有如下表示方式 {y x y x <:),(} （2）

事实上，这个表示等价于

))},((,:{y x z y x R y R x z =∧<∈?∈? （3）

所以（2）式可以看成是（3）的简化形式。当然，以（2）来表达是可以的，但要注意，当表达集合中一个元素时，若出现了n 个变元符号，那么对应的命题函项中也就应当有同样多的自由变元符号。比如（2）式中的),(y x 就是由两个变元符号表示的元素，集合表示中的命题函项“y x <”就是两个自由变元。

讨论题：设论域是实数集合，试讨论下面的表达方式是否明确描述了一个集合。设A 是由一些实数组成的集合，

{N n n i A x x x x i i ∈=∈?;2,1,:21ΛΛ}

（4） {N n n i A x x x x i n ∈=∈?;2,1,:21ΛΛ} （5）

（2）列举法。严格说来，列举法不是很正规的方法，但却常用。在满足如下条件时我们可以用列举法表示集合：①所需表示的集合中的对象非常明确；②集合中的元素有限且很少，或者尽管无限但元素之间有明确的规律性关系。比如知道所要表示的集合是“数”的集合，那么{6,5,3}就表示由三个数所组成的集；{ΛΛ,2,,8,6,4,2n }表示由正偶数组成的集合。

这里提到“集合中的对象非常明确”这一点是必要的。考察下面两个表示：{1,1,1,0,0}与{1,0}。这两个集合是否是相同的呢？再比如{北京，中国的首都}与{北京}是否是相同的集合呢？如果不能明确所要表示的对象是什么，上述问题是无法准确回答的。如果是表达“数字符号”的集合，那么前者有5个符号，而后

者却只有2个符号，这两个集合是不相同的。第二个问题的判定也存在类似之处，读者可自己辨析。

（3）关于描述法的简化。在一些文献中会出现一种描述法的简化形式，比如用“实数”表示“x ：x 是实数”。一般说来，在前后文中能够使读者确切知道这种表示就是描述法的简化形式。利用这种表达方式也是可以的，但是在多数情况下，这种简化方式会引出歧义和混乱，所以应当慎用。

i ）如果没有明确的背景，{实数}可以导致三种不同的理解：由所有实数组成的集；由“实数”这个概念（或名词）组成的单元集；由所有实数组成的集为元素构成的集。

ii ）当所论数学内容涉及多层次集合时（如拓扑学、集合论等），上述简化表达极易造成集合层次的混乱，从而出现逻辑混乱。

（4）关于相异性原则。集合论研究的是如何为集合中元素计数的问题，也就是如何比较不同集合之间元素多少的问题。因此，如果同一个对象作为一个集合中的元素被两种或两种以上不同的方式表示，决不可将这个对象看成两个或两个以上的元素，而只能作为一个元素。比如在{x ：x 是三国时期的历史人物}这个集合中，“孔明”与“诸葛亮”作为历史人物只能是一个，也就是上述集合中的一个元素。再比如，对任意自然数d ，以自然数为元素的集合}:1{N n nd A d ∈+=中，当d 取0时，集合}1{0=A 就只是一个单元素集合。

相异性原则的根本含义是：不能将同一元素重复计算成多个元素。这个原则并不妨碍在表达时，可能对同一元素给出不同的描述。重要的问题是，明确集合的组成对象，并能区别其对象的异同。读者将会看到，在集合论内容展开过程中，元素的重复表示是难以避免的。

§4.集论语言与数学概念

我们在前面曾指出，集合论的建立是数学发展的需要，同时它也为数学提供了充分多的对象模型和语汇，从而使数学研究的对象可以被描述成静态的、能够进行逻辑分析的对象。本节将介绍一些十分重要的数学概念，它们都是用纯粹集论语言定义的。

当我们说“集合”概念是在数学中不定义的基本概念时，往往意味着其它没有被称为基本概念的数学概念，应当是被定义的。又因为只有“集合”（包括“∈”）不定义，那么，其它的对象也只能由“集合”来定义。我们已经十分熟悉一些数学所研究的对象被描述成集合，比如说各种数的集合、各种曲线等等。但是，当我们建立这些对象的时候，却是为了研究这些集合之间以及集合元素之间的关系，比如运算、顺序、映射等等。换句话说，这些关系往往是数学所要研究的更重要的“对象”。那么，什么是关系呢？

在日常生活中，“关系”一词的含义十分广泛，如果一定要解释其含义也要用到与其意思相同的其它词汇，所以也都是意会。在数学中，人们所具体考虑的是数学对象之间的联系，而数学对象又往往被描述为集合。所以数学中所说的“关系”也只是集合之间的关系。那么，如何利用集合概念定义关系概念呢？考虑一个正常生活的例子。比如说“夫妻关系”，当我们说某人a 与某人b 是夫妻关系时，即表明这两个人有夫妻关系。但“夫妻关系”本身当如何解释呢？其实“夫

妻关系”也就是所有夫妻所具有的共同的关系（属性）。如果将所有的“夫妻”都列举出来，也就将“夫妻关系”的含义穷尽了。而所有的“夫妻”也构成一个集合，比如我们记A 为男人集合，B 为女人集合，

=R {B y A x y x ∈∈,|),(并且x 与y 是夫妻}

这个R 就可以表示“夫妻关系”这个概念（的外延）了。利用外延（往往是一个集合）来定义一个概念，是近现代数学的主要定义方法。下面我们先给出一些准备概念，这些概念在数学中也是常用的。

4.1定义（序偶与无序偶）集合}},{},{{b a a 被记为),(b a ，称为由b a ,构成的序偶，集合},{b a 称为无序偶。

不难验证),(),(d c b a =当且仅当)()(d b c a =∧=，这也是),(b a 称为序偶的原因，它强调b a ,的顺序是很重要的，因为当b a ≠时),(),(a b b a ≠。

4.2定义（笛卡尔积）A ，B 是集合，集合

},|),{(B y A x y x B A ∈∈=?

称为A 与B 的笛卡尔乘积，也常简称为集合A 与B 的乘积。

虽然在正式的定义中，有序n 点组以及n 个集合的笛卡尔积是归纳定义的，比如

)),,((),,(z y x z y x =，

)),,,,((),,,,(121121n n n n x x x x x x x x --=ΛΛ.

但本书在这里n n n n A A A A A A A A ????=????--)(121121ΛΛ将不拘泥于过份严格的形式化描述，我们只规定

),(),,,(2121n n y y y x x x ΛΛ=当且仅当n n y x y x y x ===,,,2211Λ。

并由此规定

{}n n i i n i n A x A x A x A x x x x x A A A ∈∈∈∈=???,,,,,|),,,,,(22112121ΛΛΛΛΛ

并约定{}C z B y A x z y x C B A C B A ∈∈∈=??=??,,|),,()()(

注：如果按正式定义，感兴趣的读者可以检查，一般情况下，C B A ??)(与)(C B A ??中的元素是不相同的。但在本书中，这样的区别没有什么意义。为了方便，我们给出了上面的约定。但按正式定义方式，读者可以体会到像n 元有序

组，也被定义为一个集合了。

我们还可以引入无限多个集合的笛卡尔集。记

),,,()(21ΛΛi N i i x x x x =∈

并规定 N i i N i i y x ∈∈=)()( 当且仅当 i i y x N i =∈?, 。于是

{})(|)(i i N i i N i i

A x N i x A ∈∈?=∈∈∏

特别的，如果每个A A i =，则记

4434421ΛA

n n n i i A A A A A

个???==∏=1 N N i i A A

=∏∈

其实N i i x ∈)(表示的是一个点列，N A 则表示由A 中的元所能组成的所有点列的集合。

4.3定义（关系）设B A 、是集合，R 是B A ?的一个子集，则称R 是A 与B 之间的一个关系。如果B A =则称R 是集A 上的一个关系。

4.4定义设 B A R ?? ，C B H ??，记

{}R y x B y A x DomR ∈∈?∈=),(,|

{}R y x A x B y RanR ∈∈?∈=),(,|

{}R y x x y R ∈=-),(|),(1

{})),(),((,|),(H z y R y x B y z x R H ∈∧∈∈?=ο

DomR 与RanR 分别称为关系R 的定义域和值域；1-R 称为关系R 的逆关系，显然它是B 与A 之间的关系；R H ο称为关系R 与关系H 的复合关系，易知R H ο是A 与C 之间的关系。

4.5定义（关系的限制与遗传）设R 是A 与B 之间的关系，B B A A ??00, 记 {})(,|),(0000|00B A R B y A x R y x R B A ?=∈∈∈=?I

称00|B A R ?为关系R 在0A 与0B 上的限制。

{}00||),(0A x R y x B A R R A ∈∈=?=I ，

称0|A R 为R 在0A 上的限制。特别地，当00,A B A B == 时，称

)(00|00A A R R A A ?=?I 为关系R 在0A 上的遗传关系，

或称之为关系R 在0A 上的遗传关系。

我们还引入一些记法，目的是为了有时在叙述上的方便和直观。

当R y x ∈),(时，我们也记成xRy ，若B B A A B A R ????00 , , 记

[]{}xRy A x B y A R , 0:0∈?∈=

[]{}xRy B y A x B R , 001:∈?∈=-

另外，记

{}A x x x A ∈=?|),(，

称A ?为A A ?的对角线，也称A 上的恒同关系。当集合A 是确定的时，A ?可简记为?。

因为B A ??φ总是成立的，故φ可以看成A 与B 之间的一个关系，成为空关系，其实“空关系”所表示的是什么也没有的“关系”。

注意到当B A ?有很多元素时，A 与B 之间的关系也会有很多的。因为B A R ??当且仅当)(B A P R ?∈，不难看出，当B A H R ??,时H R H R H R \ , , I Y 等等也都是A 与B 之间的关系。在数学中，有许多关系是令人感兴趣的。但有几类关系是我们常要探讨和应用的。本节着重介绍三种类型重要的关系，它们分别是：

（1）映射；（2）一个集合上的等价关系；（3）一集合上的序关系。

1. 关于映射

映射（或函数）概念是数学中一个核心的概念。几乎所有的数学问题都与映射有关。比如，数学分析就是以“分析函数”为其主要课题。下面给出纯集论语言的映射定义。

4.6定义（映射）若关系B A f ??满足

1）A Domf =；

2）21212211)()),(()),((y y x x f y x f y x =→=∧∈∧∈

则称f 是A 到B 的一个映射，当f 是A 到B 的映射时，记为B A f →: （或

B A f →）

。另外，我们也用记法)(x f y =或者y x f

α（在不会引起歧义时简记为y x α）表示f y x ∈),(（或xfy ）

。回顾过去“映射”定义中用到的“对应法则”，在这里已经被一个满足两个条件的“关系”所替代了，而这个“关系”其实是一个集合。两个映射f 与g 是否相等完全决定于作为集合的f 与g 是否相等。假设

}{}{),(|),(),(|),(y x Q y x g y x P y x f == , 显然，这里的命题函项),(),(y x Q y x P 与相当于“对应法则”的描述，如果它们不同，可能意味着“对应”的操作程序（算法）不一定相同。但是如果g f =，那么两个映射就是相同的。这样的处理便清除了由“对应法则”的不同理解而造成的争议。

由于映射也是关系，所以前面关于值域，复合，限制等概念也都适用于映射，这里不再单独说明了。但是映射f 作为一种关系的逆关系1-f

却不见得是映射。

4.7定义若映射B A f →:满足

2121)()(x x x f x f =→= 则称f 是一个单射；若B Ranf =，则称f 为满射；当f 是既单且满的映射时，称f 是一双射。

若存在集A 到B 的双射，称A 与B 是集同构的，也称A 与B 是等势的（关于势的概念在后面将专门讨论）。读者很容易证明下面的结论。

4.8命题：映射B A f →:的逆关系1-f

是映射当且仅当f 是一个双射。为了不引起歧义，只有当1-f

是映射时，我们才用)(1y f x -=这样的记法表示1),(-∈f x y 。如果1-f

不是映射，则)(1y f -表示集合}{y x f Domf x =∈)(|。在应用符号)(1y f

-时，应对其含义作必要的交待。若B A f →:，B B A A ??00 ,

记 []{}[]{}0010)(:))((:B x f A x B f x f y A x B y A f ∈∈==∈?∈=- 。

[]0A f 称为0A 在f 之下的像集，[]01B f

-称0B 在映射f 之下的原像集。

注意：当A a ∈且A a ?时，[]a f a f 与)(所表示的对象是完全不同的，前者是Ranf 中的元素，后者是Ranf 的一个子集。

对任意的A ，A ?是A 到A 的一个映射。当我们将A ?看作映射时，记A ?为A Id ，

A A Id A →:称为恒同映射。显然对任意A x ∈，x x Id A =)(。

当A 与B 是集合时，引入如下集合：

}{的映射到是B A f f B A :=

称之为A 到B 的映射集。当}{1,0=B 时，我们记

}{21,0A A =

对任意2A f ∈，f 是A 到二元集}{1,0的一个映射。记}{1)(|=∈=x f A x A f ，显然[]}1{1-=f A f 且f 满足

???∈∈=f f A x A x x f , , 01)( 现对A 的任意一个子集C ，定义一个映射}{1,0:→A x A C ???∈∈=C x C x x x A

, , 01)( 称A C x 是子集C 的特征映射（C 作为A 的子集）。当明确所论子集是哪个集合的子集时，C 的特征映射可简记为C x 。由前面的讨论可知，任意2A f ∈，f 是子集f A 的特征映射。

4.9命题：A 是集合，则2A 与A 的幂集合)(A P 等势。

证明：定义2)(:A A P F →，任取)(A P C ∈，C x C F =)(。由前面的讨论，易于验证F 是一双射。■

由于任何集合的子集可由该子集的特征映射所唯一确定，因此人们经常用特征映射来表示一个子集，并将映射集2A 与A 的幂集合同样看待。

2. 集上的等价关系与元素的分类

我们在认识的过程中往往要按一定的性质将对象加以分类。设 ?}{I i A i ∈=|满足条件：∪?=X ，且?中两个不同的元素都是不相交的集合，则称?是X 的一个分划。如果我们认为分在一个类（是X 的子集）中的元素是相关的，我们就在X 上定义了一个关系，反过来，这个关系也可以决定的一个分划。那么能够决定X 的一个分划的关系应当满足什么条件呢？下面引入此种类型关系的定义。

4.10定义设A A R ??，..t s

1）R x x R ∈??),( , 即；

2）R z x R z y R y x R R R ∈∈∧∈?),(,),(),(则即 , ο；

3）R z y R y x R R ∈∈?-),(),(1 , 则即。

则称R 是A 上的一个等价关系。其中1），2），3）分别称为自反性，传递性和对称性。

4.11 例 (1) 设{}实矩阵是n n A A X ?=|，考虑下列X 上的关系。

{}的行列式的值

的行列式不大于B A B A R |),(1= {}是相似矩阵

与B A B A R |),(2=

}{1|),(3的秩是B A B A R -= }{的秩相等与B A B A R |),(4=

不难验证1R 与3R 不是等价关系，2R 与4R 是等价关系。

(2)设{}R R Q R ??∈-==y x y x R X |),( , ，则R 是实数集R 上的等价关系■

上面曾经讲过，定义X 上的等价关系是为了将X 的元素进行分类。现假设X X R ??是X 上的等价关系，X a ∈，记

[]}{R a x X x a R ∈∈=),(|（当R 已明确，可将[]R a 简记为[]a ）

称[]R a 为元素a 所在的R 等价类（或a 所在的等价类）。设R 与X 如上所述，容易验证下列事实

（1）[][]R R b a =当且仅当R b a ∈),(；

（2）R b a ∈),(当且仅当[][]φ=R R b a I ；

（3）记[]{})(|/R a A X a X A A R X =∈?∧?=，则R X X /=。

这里的R X /称为X 关于关系R 的商集。上面的（2）与（3）表明商集R X /恰好构成了X 的一个分划。反之，前面曾说明，若给定X 的一个分划，可利用分划定义X 上的一个关系（分在同一类的两个元相关）。读者不难验证，由此分划定义的关系也一定是一个等价关系。

3. 在集合上定义序关系

顺序关系是数学所要探讨的一种重要的结构关系。但顺序关系的结构类型是非常多的。抽象出其中共同特点便产生了顺序结构的数学定义。

4.12定义（序与序集）设R 是集合X 上的关系，满足

1）φ=?R I ，即)),((R x x x ∈?；

2）R R R ?ο，即R z y R y x ∈∧∈),(),(则R z x ∈),(。

称R 是X 上的偏序关系，),(R X 称为一个偏序集。在序关系是已确定的时候，“偏序集),(R X ”也简称为“偏序集X ”，偏序集也可简称为序集。

上述定义的偏序关系可以称为严格序关系，即没有反身性。人们习惯于用严格小于号表示这样的关系，比如以X <表示一个X 上定义的严格序关系。但也有人乐于用不严格的序关系。比如当R 或X <表示一个严格的偏序关系时，我们可以用R Y ?或X X

4.13命题：设H 是X 上的一个关系且H R H Y I ?==? , φ，若H 是X 上的一个严格偏序关系当且仅当R 满足下列条件：

1）R x x X x ∈∈?),( , ；

2）若, R z x R y x ∈∧∈),(),(则R z x ∈),(；

3）若R z y R y x ∈∧∈),(),(，则y x =。

证明留作练习。

正是由于4.13命题所给出的这样一种关系，有些文献也以4.13命题中的三个条件作为偏序关系所应满足的性质。不难看出，满足这些条件的关系相当于不严格序关系。就如我们平时在谈论数的大小关系时，有时用严格不等号“<”，有时用不严格不等号“≤”。在本书中，我们经常用),(L L <或),(L L ≤表示一个序集，其中“L <”则表示满足定义4.12中所列条件的严格偏序关系，而“L ≤”

则表示不严格序关系（满足4.13命题中的三个条件）。

4.14例：设X 是闭区间[]1,0上的所有连续函数所组成的集合

[]{})()(,1,0|),(1x g x f x g f R <∈?=

{}

??<=10102)()(|),(dx x g dx x f g f R {}??≤=101

3)()(|),(dx x g dx x f g f R 可以验证1R 和2R 都是偏序关系（严格），但3R 不是偏序关系。因为存在函数??=101

0)()(,,dx x g dx x f g f ，即3),(R g f ∈且3),(R f g ∈，但g f ≠。■

注：3R 只满足4.13命题中的第1）与第2）个条件。一般称这样的关系为预序关系。本书不专门讨论这类关系。

我们可以看出上面的1R 关系所定义的顺序并不能将X 中的元都排出大小（或先后），这也是这样的序被称为偏序（或部分序）关系的原因。

注：当我们说),(),,(),(),(),,(R X X X X X X X <≤<≤等是序集时，其中的符号R X X ,,,,<≤<≤都只表示一种序关系。至于这些序关系是如何定义的，要看其具体的规定。不能将这些符号单纯地理解成数的不等号。如果没有具体规定这些符号的意义，那么它们就只是满足4.12定义或4.13命题中所列的条件的关系。

4.15定义 ),(X X ≤是一个序集，若对任意y x X y x X ≤∈,,与x y X ≤中至少有一个成立，则称),(X X ≤是一个全序集。全序集也称为线性序集。

任何实数的子集，按通常数的大小关系都构成一个全序集。但在高等数学中，我们会遇到大量并非全序集的序集。

4.16定义设),(≤X 是一个序集，A a X A ∈?,，若任取a x A x ≤∈,成立（或

x a ≤）

，则称a 是A 中最大元（或最小元）；若任取a x A x ≠∈,且)(x a

如果A 中有最大元（或有最小元），以A max （或A min ）表示A 中最大元（或最小元）。

此外，设A 与),(≤X 如4.16定义中所述，记

{})(|)(x y A y x A ub ≤∈?=

{})(|)(y x A y x A db ≤∈?=

)(A ub 与)(A db 分别称为A 的上界集和下界集。若)(A ub 有最小元，记为A sup ，称为A 的上确界；若)(A db 有最大元，记为A inf ，称为A 的下确界。

对于序集的一个子集而言，是否存在它的最大元（最小元）、极大元（极小元）、上确界（下确界），要视序集的具体情况才能确定。一般而言，一个序集（子集）的极大元不一定是其最大元，但若它有最大元，那么它的最大元一定是一个极大元，同时也是其上确界。不过对一个全序集而言，它的极大元也就是它的最大元（练习）。

对集合论而言，最重要的序关系之一是良序关序。下节将专门介绍良序关系。

§5良序集，归纳法与自然数

5.1定义设),(≤X 是一个全序集，若X 的任意非空子集A 中都有最小元，则称),(≤X 为良序集，序关系“≤”称为一个良序关系。

5.2例依据我们过去了解的关于数的大小关系，正整数集N 是一个良序集，有理数集Q ，整数集R ，整数集Z ，实数集的任何一个非退化区间都不是良序集。

良序集最重要的特点之一是它与归纳法有着本质性的联系。

5.2定理设)(x P 是一个只含x 为自由变元的命题函项，),(≤X 是一个良序集。记0a 是X 中的最小元，如果

ⅰ）)(0a P 成立；

ⅱ）由任意{})(,|a P b x b x X x a ≠∧≤∈∈成立，可推得)(b P 成立，

那么对任意X 中的元c ，)(c P 成立。

注：按5.2定理中的符号约定，关于归纳法的较为形式化的表述如下：

)()))()))(((()((0x XP x y P x P y x X x a P ∈?→→→<∈?∧。

证明：反证，若存在)(,a P X a ∈不成立，则

{}φ≠∈=不成立)(|x P X x A

集合论与图论试题A

本试卷满分90分（06级计算机、信息安全专业、实验学院）一、判断对错（本题满分10分，每小题各1分）（正确画“√”，错误画“×”） 1．对每个集合A ，A A 2}{∈。（×） 2．对集合Q P ,，若?==Q P Q Q P ,，则P =?。（√） 3．设,,:X A Y X f ?→若)()(A f x f ∈，则A x ∈。（×） 4．设,,:Y B Y X f ?→则有B B f f ?-))((1。（×） 5．若R 是集合X 上的等价关系，则2R 也是集合X 上的等价关系。（√） 6．若:f X Y →且f 是满射，则只要X 是可数的，那么Y 至多可数的。（√） 7．设G 是有10个顶点的无向图，对于G 中任意两个不邻接的顶点u 和v, 均有9deg deg ≥+v u ，则G 是哈密顿图。（×） 8．设)(ij a A =是 p 个顶点的无向图G 的邻接矩阵，则对于G 的顶点i v , 有∑==p j ij i a v 1deg 成立。（√） 9. 设G 是一个),(q p 图，若1-≥p q ，则]/2[)(q p G ≤χ。（×） 10．图G 和1G 同构当且仅当G 和1G 的顶点和边分别存在一一对应关系。（×）

二.填空(本题40分，每空各2分) 1．设}},{,{φφ=S 则=S 2 }}}{,{}},{{},{,{φφφφφ 。 2．设B A ,是任意集合，若B B A =\，则A 与B 关系为 φ==B A 。 3．设1)(,0)()(,:};3,2{},1,0{},,,{===→===c f b f a f Y X f Z Y c b a X , 3)1(,2)0(,:==→g g Z Y g ,则)()(c f g a f g ，分别为 2，3 。 4．设X 和Y 是集合且X m =，Y n =，若n m ≤，则从X 到Y 的单射的个数为 !m C m n 。 5．设}2,1{},,,2,1{==B n X ，则从X 到Y 的满射的个数为 22-n 。 6．设)}2,4(),1,3(),3,2{()},4,3(),2,2(),2,1{(},4,3,2,1{===S R X ，则 =)(R S R )}2,3(),4,2(),4,1{( 。 7．设???? ??=???? ??=5123454321,415235432121σσ，则???? ??=235411234521σσ 。 8. 设)},(),,(),,{(},,,,{a c c b b a R d c b a X ==，则 )},(),,(),,(),,(),,(),,(),,(),,(),,{(b c a c a b c b c a b a c c b b a a R =+ 。 9. 设X 为集合且X n =，则X 上不同的自反或对称的二元关系的个数为 22222222n n n n n n +--+- 。 10．设}}{},{},,{{},,,,{d c b a A d c b a X ==是X 的一个划分，则由A 确定的 X 上的等价关系为 )},(),,(),,(),,(),,(),,{(d d c c a b b a b b a a 。 11．}10,,2,1{ =S ，在偏序关系“整除”下的极大元为 6，7，8，9，10 。 12．给出一个初等函数)(x f ，使得它是从)1,0(到实数集合R 的一一对应，这个函数为 x ctg π或-x ctg π或)2/(ππ-x tg 。 13. 设G 是),(p p 连通图，则G 的生成树的个数至多为 p 。

离散数学期末测试卷I及答案

离散数学期末测试卷I及答案第一部分、考试形式和时间答题时限：120 分钟考试形式：闭卷笔试第二部分、考试题型和得分构成一、选择题：对每一道小题,从其4个备选答案中选择最适合的一项,每小题2分,共10 道小题,20分。二、填空题：每空1分,共5道小题,10个空白处待填,10分。三、判断题：每一道小题均以陈述语句描述,对的打√,错的打х。每小题1分,共10 道小题,10分。四、综合题：每小题10分,共6道小题,60分。第三部分、考试复习范围一、选择题 1．含n个元素的集合A的幂集的元素个数为多少？答案：2n个。 2．数理逻辑的创始人是谁？

答案：莱布里茨。 3．设(R,+,?)是环,它有哪些特性？答案：1.(R,+)是阿贝尔群。2.(R,?)是半群。3.?对+可分配。 4．排中律满足哪些性质？答案：A ∧ 不成立。（不应同时否认一个命题（A ）及其否定（非A ）） x （F （x ）∨F （x ））对任何个体x 而言,x 有性质F 或没有性质F 。 5．什么是真命题？命题“如果雪是黑的,则1+1=0”是真命题吗？答案：真值为真的命题为真命题。命题“如果雪是黑的,则1+1=0”是真命题！解析：p:雪是黑的；q:1+1=0;如果雪是黑的,则1+1=0:p →q 。由于p 为假,所以无论的真值如何,“p →q ”的真值都为真。 6. 下列哪个等价公式有错？ A ．P Q Q P →?→； B ．P Q P Q →??∨； C ．P Q Q P →??∨；答案：A 7. 设G 为4阶有向图,度数列为（3,4,2,3）,若它的入度列为（1,2,2,1）, 则出度列为哪项？ A ．（1,2,1,2）； B ．（2,2,0,2）； C ．（2,1,1,2）．答案：B 解析：有向图中：度数=出度数+入度数。 8. 设{}{},3,4,S a φ=,则表示空元素属于S 怎样写？答案:?∈S 9. 什么是前束范式？下面哪个是前束范式？ A

北大集合论与图论往年考题.pdf

一、用真值表证明德*摩根律（证明其中一条即可）。二、设A,B,C是集合，试问在什么条件下(A-B)-C=A-(B-C)？给出证明。三、设A={a,b,c}，问A上有多少种不同的：二元关系？自反关系？对称关系？传递关系？等价关系？偏序关系？良序关系？四、用花括号和空集来表示1?2（注意?表示集合的叉乘）. 五、设R是实数集，Q是有理数集，试构造出R-Q与R之间的双射. 1．简单叙述构造的思路； 2．给出双射f：R-Q -> R 或f：R -> R-Q的严格定义。 2008年期末考题：一、在有向图中，如果存在从顶点u到顶点v的有向通路，则说u可达v；如果顶点u和顶点v互相可达，则说u双向可达v。回答下列问题： 1．顶点集上的可达关系是不是等价关系？为什么？ 2．顶点集上的双向可达关系是不是等价关系？为什么？ 3．对于上述两个关系，如果是等价关系，其等价类的导出子图称为什么？二、一棵树有13个顶点，除了3个2度顶点和若干个树叶之外，其余顶点都是5度。 1．求出5度顶点的个数（写出计算过程）； 2．画出所有互不同构的这种树。三、计算出右图中v1到v4长度为4的通路数（要写出计算过程的主要步骤），并写出一个最小支配集、一个最大团、一个最小边覆盖、一个最大匹配。四、如果一个图中所有顶点度数都为k，则称为k正则图。8阶3 正则简单图一定是平面图吗？一定不是平面图吗？为什么？五、证明：如果正则简单图G和补图G都是连通图，则G和G中至少有一个是欧拉图。六、证明：如果n阶（n≥3）简单图G中，对于任何1≤j,<2,3>,<3,2>, <3,4>}. (1) 给出R的矩阵表示, 画出R的关系图; (2) 判断R具有哪些关系性质(自反,反自反,对称,反对称,传递); (3) 求出R的自反闭包r(R), 对称闭包s(R), 传递闭包t(R). (用关系图表示) 三、设X,Y,Z是任意集合, 构造下列集合对之间的双射, 并给出是双射的证明. (1) Z(X?Y)与(Z X)Y ; (2) P(X?Y) 与P(X)?P(Y). (假设X?Y=?) 四、已知对每个自然数n, 都存在唯一后继n+=n?{n}. 证明: 对于每个非零自然数n, 都存在唯一前驱n-, 满足n=(n-)+. 五、设f: A→B是单射, g: B→A是单射, 证明: 存在集合C,D,E,F, 使得A=C?D, C?D=?, B=E?F, E?F=?, 并且f(C)=E, g(F)=D.

暨南大学离散数学周密试卷数理逻辑与集合论—参考试卷

暨南大学考试试卷一、填空题（共10小题，每小题2分，共20分） 1. 设命题 p ：罗素悖论的真值为假，q ：暨南大学的校训是信敏廉毅，r ：离散数学是计算机科学不可分割的一门基础课程，则复合命题: ()()()()() p q r q p r p ?∧?∨∧???→∨的真值为 ; 2. 下列各式中为永真式的有： (1) Q Q P P →→∧))(( (2) Q Q P →→)( (3) )(Q P P ∨→ (3) Q Q P P →∨∧?))(( (5) )(Q P Q ∧→

3. A 是个10元集合，B 是个2元集合，则集合A B 中元素的个数为 4. 设M(x)：x 是人，C(x)：x 很聪明，则命题：“尽管有人很聪明，但未必一切人都聪明。”可符号化为： 5. 设R(x)：x 是实数；L(x, y)：x 小于y ，则谓词公式： (()(()(,)))x R x y R y L x y ?→?∧用自然语言表述就是： 6. 设个体域为A={a, b, c}，消去公式()()xP x xQ x ?→?中的量词得到的与之等值的谓词公式为： 7. P(A)表示集合A 的幂集，则((()))P P P ? = 8. ())(B A B B A ?-??= 9. 设D 为同一平面上直线的集合，并且 // 表示两直线的平行关系，⊥表示两直线间的垂直关系，则 20// ＝，21⊥＝ 10.设 {}c ,b ,a A =，{} ,,,A R a b b a I =<><>?是A 上的等价关系, 设自然映射,R /A A :g →,那么()=a g 二、简答题（共4小题，每小题6分，共24分） 1.(1)求公式()()?∨?→??P Q P Q 的主析取式（要有过程）；（4分） (2)根据主析取式直接写出该公式的主合取式；（2分）

(完整版)高中生物概念大全

1.生命系统：能够独立完成生命活动的系统叫做生命系统。由大到小依次为生物圈、生态系统、群落、种群、个体、系统、器官、组织、细胞。 PAT:单细胞生物不具有系统、器官、组织层次，细胞即是个体；植物没有（消化、呼吸、循环等）系统；病毒是生物，但不是生命系统 2.病毒：是由一个核酸分子(DNA或RNA)与蛋白质构成的非细胞形态的营寄生生活的生命体。 3.原核细胞：是组成原核生物的细胞。这类细胞主要特征是没有以核膜为界的细胞核, 同时也没有核膜和核仁, 只有拟核，进化地位较低。分类：根据外表特征，可把原核生物粗分为“三菌三体”6种类型，即细菌（狭义的）、放线菌、蓝细菌、支原体、立克次氏体和衣原体。注：支原体是最小的细胞生命结构 4.真核细胞：指含有真核(被核膜包围的核)的细胞。其染色体数在一个以上,能进行有丝分裂。 5.显微结构：在普通光学显微镜中能够观察到的细胞结构。细胞中的结构如染色体、叶绿体、线粒体、中心体、核仁等结构的大小均超过0.2微米，用普通光学显微镜都能看到，因而这些结构属于细胞的显微结构。 6.亚显微结构：又称为超微结构。指在普通光学显微镜下观察不能分辨清楚的细胞内各种微细结构。(普通光学显微镜的分辨力极限约为0.2微米，细胞膜、内质网膜和核膜的厚度，核糖体、微体、微管和微丝的直径等均小于0.2微米，因而用普通光学显微镜观察不到这些细胞结构，要观察细胞中的各种亚显微结构，必须用分辨力更高的电子显微镜。) 能够在电子显微镜下看到的直径小于0.2微米的细微结构,叫做亚显微结构。 7.水：水是生命的源泉。人对水的需要仅次于氧气。人体细胞的重要成分是水，水占成人体重的60~70%，占儿童体重的80%以上。作用：水有利于体内化学反应的进行，在生物体内还起到运输物质的作用。水对于维持生物体温度的稳定起很大作用。结合水：水在细胞中以两种形式存在。一部分与细胞内的其他物质结合，叫结合水。结合水是细胞结构的组成成分。自由水：大部分以游离的形式存在，可以自由流动，叫自由水 8.无机盐：其中大量元素有钙Ca、磷P、钾Ka、硫S、钠Na、氯Cl、镁Mg，微量元素有铁、锌、硒、钼、氟、铬、钴、碘等无机盐作用：1）、是细胞的结构成分。有些无机盐是细胞内某些复杂化合物的重要组成部分。实例：Mg2＋是叶绿素分子必需的成分；Fe2＋是血红蛋白的主要成分；碳酸钙是动物和人体的骨、牙齿中的重要成分。（2）、参与并维持生物体的代谢活动。实例：哺乳动物血液中必须含有一定量的Ca2＋，如果某个动物血液中钙盐的含量过低就会出现抽搐。Ca2＋对于血液的凝固也是非常重要的，没有Ca2＋，血液就不能凝固。生物体内的无机盐离子必须保持一定的比例，这对维持细胞的渗透压和酸碱平衡是非常重要的，是生物体进行正常生命活动的必要条件。如HCO3－对于维持血液正常，pH值具有重要的作用。含Zn的酶最多，有七十多种酶的活性与Zn有关。Co是维生素B12的必要成分，参与核酸的合成过程。（3）、维持生物体内的酸碱平衡（4）、维持细胞的渗透压。尤其对于植物吸收养分有重要作用 9.糖类：麦芽糖、蔗糖、乳糖是双糖。葡萄糖和果糖是单糖。多糖：淀粉、纤维素和糖原作用：1 作为生物能源 2 作为其他物质生物合成的碳源 3 作为生物体的结构物质4 糖蛋白、糖脂等具有细胞识别、免疫活性等多种生理活性功能。 10.脂质：生物体中一大类不溶于水而溶于有机溶剂的有机化合物。分类：1. 油脂即甘油三酯或称之为脂酰甘油，是油和脂肪的统称。一般将常温下呈液态的油脂称为油，而将其呈固态时称为

离散数学集合论部分测试题

离散数学集合论部分综合练习本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, y∈A}，则R 的性质为（）． A．自反的B．对称的 C．传递且对称的D．反自反且传递的 8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b∈A , 且a +b = 8}，则R具有的性质为（）． A．自反的B．对称的 C．对称和传递的D．反自反和传递的 9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个． A．0 B．2 C．1 D．3 10．设集合A={1 , 2 , 3 , 4}上的二元关系 R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，