吉林学院远程教育课件

吉林大学远程教育课件主讲人:杨凤杰学时：64(第七讲)离散数学1.3.3不可数集合

前面我们讨论的无穷集合都是可数集合，并且知道了在数轴上稠密的有理数集合也可以与自然数集合建立1-1对应关系，那么是不是所有的无穷集合都是可数集合呢？定理1.3.6全体实数做成的集合是不可数集合。证明：由定理1.3.2知,只要证明（０，１）区间内的实数不可数就可以了。若不然，我们可以把（０，１）区间内的数排成一个序列：

０.a11a12a13…０.a21a22a23…(2)０.a31a32a33…┆

我们考虑下面的数：０.r1r2…rk…(３)其中

１，当akk≠１rk=２，当akk＝１，k＝１，２，…

显然，（３）是（０，１）区间内的数,但它却不是序列(２)中的任一个数。事实上,对(２)中任一个数０.ak1ak2…akk…，因为rk≠akk,故０.ak1ak2…akk…≠０.r1r2…rk…与假设矛盾。故（０，１）区间内的实数不可数，所以实数集不可数。上述定理的证明方法，就是著名的“康托尔对角线法”，该方法在可计算理论中有广泛的应用。推论

实数集合R,区间(a,+)、[a,b]、[a,b)、（a,b]，a≠b都是不可数的，且与区间(0,1)等浓。我们仅看构造区间[0，1]与（0，1）之间1-1映射的例子。我们知道全体有理数的集合是可数的，于是（0，1）区间中的有理数是可数的，不妨将它们排成形式为（1）的序列。而闭区间[0，1]比区间（0，1）多两个数0，1，它们是有理数，于是可建立闭区间[0，1]中的有理数到区间（0，1）中的有理数的1-1映射σ1如下图。

0,1,a1,a2,…,an,……a1,a2,a3,a4,…,an+2，…令区间[0，1]中的无理数到区间（0，1）中的无理数的1-1映射σ2为自己应成自己。则映射σ=σ1∪σ2为区间[0，1]到区间（0，1）的1-1映射。从而区间[0，1]与（0，1）等浓。我们设实数集合的基数为c。定理1.3.7设A1，A2，…，An,…是互不相交的集合序列，它们的基数都是c，则的基数也是c。即可数个基数为c的集合的并集基数仍为c。证明：设In=[n-1,n),则当m≠n时，Im∩In=。因为In(n=1,2,…)的基数是c，故存在1-1映射σ1，σ2，…，使得σn(In)=An。令σ=，则σ是=[0，+）到的1-1映射。从而与[0，+）等浓，由推论知其基数为c。实际上还有更进一步的结果：可数个基数为c的集合的直积基数仍为c。从而R2，Rn的基数都是c。定理1.3.8集合Ａ的元素不能与Ａ的所有子集建立１－１映射。证明：假设σ为A到A的所有子集作元素的集合上的1—1映射。令Ｂ＝x|xA并且xσ(x)于是，存在唯一一个元素bA,使得σ(b)＝Ｂ若bＢ，则由Ｂ的定义知，bσ(b),即bB,矛盾。若bＢ,即bσ(b），于是由Ｂ的定义知，bB，矛盾。因此，在Ａ与Ａ的所有子集作元素的集合之间，不能建立１－１映射。有了这个结论，我们就可以构造基数任意大的集合。如|R||2R|||…。我们知道集合基数的关系是一个全序关系，把大于等于0的基数分别记为0，1，2，3，…，满足0

1

2

3…。假设1=c，著名的“连续统问题”是：即能否找到一实数集的子集，它是不可数集合，但又不能与实数集合建立一一对应。现在已经证明了：证明连续统假设成立是不可能的；证明它不成立也是不可能的。因此，所谓“连续统问题”在现在的数学理论框架之中是不能判定的。第二章

命题逻辑数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁地表达出各种推理的逻辑关系，因此，数理逻辑一般又称为符号逻辑。数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。下面两章将介绍数理逻辑最基本的内容：命题逻辑和谓词逻辑。§2.1命题以及逻辑联结词2.1.1命题

语言的单位是句子，句子可以分为疑问句、祈使句、感叹句、与陈述句等，其中只有陈述句具有真假意义，其他类型的句子无所谓真假。命题逻辑研究的对象是命题。所谓命题是指一句有真假意义的话。例如，“北京是中国的首都”是命题，而且它是真的；“长春是中国最大的城市”是命题，但它是假的。“关门!”，“你上哪?”这种命令和问话不是命题。需要注意的是,一个句子本身是否能分辨真假与我们是否知道它的真假是两回事。也就是说,对于一个句子，有时我们可能无法判断它的真假,但这个句子本身却是有真假的。例如：(1)1960年长春春城电影院放映了国产故事片“白毛女”。(2)太阳系外有宇宙人。(1)和(2)都是命题。(1)是对过去的事情进行判断，虽然我们一时很难分辨它的真假,但这句话本身是有其真假的。对于(2),目前人们尚无法确定其真假,但从事物的本质而论,句子本身是可分辨真假的,这类语句也称为命题。下面,命题用大写英文字母P,Q,…,P1,P2,…,表示。如果一个命题是真的，就说它的真值是1；如果一个命题是假的，就说它的真值是0。我们也用1代表一个抽象的真命题，用0代表一个抽象的假命题。2.1.2逻辑联结词

当我们用命题组成新的句子的时候，使用了语法中的逻辑联结词，下面我们介绍五种逻辑联结词（或称命题的五种运算）。我们将会看到，它们和自然语言里的联结词是有所不同的，它们是自然语言里的联结词的逻辑抽象。若干个原子命题通过命题逻辑联结词而构成的新命题称为复合命题。

定义2.1.1设P是一个命题，命题“P是不对的”称为P的否定，记以P，读作非P。P是真的当且仅当P是假的。例如，P：上海是一个城市。P：上海不是一个城市。定义2.1.2设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以PQ，读作P或Q。规定PQ是真的当且仅当P，Q中至少有一个是真的。例如，P：今天下雨，Q：今天刮风，PQ：今天下雨或者刮风。自然语言中的“或者”一词有不可兼的意思。例如，“我到北京出差或者到广州去度假”表示的是二者只能居其一，不会同时成立。按照联结词“”的定义，当P，Q都为真时，PQ也为真，因此，“”所表示的“或”是“可兼或”，对于“不可兼或”，我们不可以用来表示。定义2.1.3设P，Q是两个命题，命题“P并且Q”称为P，Q的合取，记以PQ，读作P且Q。规定PQ是真的当且仅当P和Q都是真的。例如，P：22=5，Q：雪是黑的，PQ：22=5并且雪是黑的。

定义2.1.4设P，Q是两个命题，命题“如果P，则Q”称为P蕴涵Q，记以PQ。规定，PQ是假的当且仅当P是真的而Q是假的。例如，P：f(x)是可微的，Q：f(x)是连续的，PQ：若f(x)是可微的，则f(x)是连续的。显然,由定义知,当P是真的,Q是真的时,命题PQ是真的。这和日常生活中语言“如果…则…”的意思是一致的。但由定义知,如果P是假命题,则不管Q是什么命题,命题“如果P，则Q”在命题逻辑中都被认为是真命题。例如,P:22=5,Q:雪是黑的，于是,命题“如果22=5,则雪是黑的”是真命题。这是和人们日常生活中语言不一致的地方。

定义2.1.5设P,Q是两个命题,命题“P当且仅当Q”称为P等价Q,记以PQ。规定,PQ是真的当且仅当P,Q或者都是真的，或者都是假的。例如，P：a2+b2=a2,Q：b=0，PQ：a2+b2=a2当且仅当b=0。利用上面介绍的这五种逻辑联结词，我们可以把许多日常语句符号化。1、字体安装与设置如果您对PPT模板中的字体风格不满意，可进行批量替换，一次性更改各页面字体。在“开始”选项卡中，点击“替换”按钮右侧箭头，选择“替换字体”。（如下图）在图“替换”下拉列表中选择要更改字体。（如