吉林学院远程教育PPT课件

.,1,吉林大学远程教育课件,主讲人:杨凤杰,学时：64,(第七讲),离散数学,.,2,1.3.3不可数集合前面我们讨论的无穷集合都是可数集合，并且知道了在数轴上稠密的有理数集合也可以与自然数集合建立1-1对应关系，那么是不是所有的无穷集合都是可数集合呢？定理1.3.6全体实数做成的集合是不可数集合。证明：由定理1.3.2知,只要证明（，）区间内的实数不可数就可以了。若不然，我们可以把（，）区间内的数排成一个序列：,.,3,.a11a12a13.a21a22a23(2).a31a32a33我们考虑下面的数：.r1r2rk()其中，当akkrk=，当akk，k，,.,4,显然，（）是（，）区间内的数,但它却不是序列()中的任一个数。事实上,对()中任一个数.ak1ak2akk，因为rkakk,故.ak1ak2akk.r1r2rk与假设矛盾。故（，）区间内的实数不可数，所以实数集不可数。上述定理的证明方法，就是著名的“康托尔对角线法”，该方法在可计算理论中有广泛的应用。,.,5,推论实数集合R,区间(a,+)、a,b、a,b)、（a,b，ab都是不可数的，且与区间(0,1)等浓。我们仅看构造区间0，1与（0，1）之间1-1映射的例子。我们知道全体有理数的集合是可数的，于是（0，1）区间中的有理数是可数的，不妨将它们排成形式为（1）的序列。而闭区间0，1比区间（0，1）多两个数0，1，它们是有理数，于是可建立闭区间0，1中的有理数到区间（0，1）中的有理数的1-1映射1如下图。,.,6,0,1,a1,a2,an,a1,a2,a3,a4,an+2，令区间0，1中的无理数到区间（0，1）中的无理数的1-1映射2为自己应成自己。则映射=12为区间0，1到区间（0，1）的1-1映射。从而区间0，1与（0，1）等浓。我们设实数集合的基数为c。定理1.3.7设A1，A2，An,是互不相交的集合序列，它们的基数都是c，则的基数也是c。即可数个基数为c的集合的并集基数仍为c。,.,7,证明：设In=n-1,n),则当mn时，ImIn=。因为In(n=1,2,)的基数是c，故存在1-1映射1，2，使得n(In)=An。令=，则是=0，+）到的1-1映射。从而与0，+）等浓，由推论知其基数为c。实际上还有更进一步的结果：可数个基数为c的集合的直积基数仍为c。从而R2，Rn的基数都是c。,.,8,定理1.3.8集合的元素不能与的所有子集建立映射。证明：假设为A到A的所有子集作元素的集合上的11映射。令x|xA并且x(x)于是，存在唯一一个元素bA,使得(b)若b，则由的定义知，b(b),即bB,矛盾。若b,即b(b），于是由的定义知，bB，矛盾。因此，在与的所有子集作元素的集合之间，不能建立映射。,.,9,有了这个结论，我们就可以构造基数任意大的集合。如|R|2R|。我们知道集合基数的关系是一个全序关系，把大于等于0的基数分别记为0，1，2，3，满足0123。假设1=c，著名的“连续统问题”是：即能否找到一实数集的子集，它是不可数集合，但又不能与实数集合建立一一对应。现在已经证明了：证明连续统假设成立是不可能的；证明它不成立也是不可能的。因此，所谓“连续统问题”在现在的数学理论框架之中是不能判定的。,.,10,第二章命题逻辑数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁地表达出各种推理的逻辑关系，因此，数理逻辑一般又称为符号逻辑。数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。下面两章将介绍数理逻辑最基本的内容：命题逻辑和谓词逻辑。,.,11,2.1命题以及逻辑联结词2.1.1命题语言的单位是句子，句子可以分为疑问句、祈使句、感叹句、与陈述句等，其中只有陈述句具有真假意义，其他类型的句子无所谓真假。命题逻辑研究的对象是命题。所谓命题是指一句有真假意义的话。例如，“北京是中国的首都”是命题，而且它是真的；“长春是中国最大的城市”是命题，但它是假的。“关门!”，“你上哪?”这种命令和问话不是命题。,.,12,需要注意的是,一个句子本身是否能分辨真假与我们是否知道它的真假是两回事。也就是说,对于一个句子，有时我们可能无法判断它的真假,但这个句子本身却是有真假的。例如：(1)1960年长春春城电影院放映了国产故事片“白毛女”。(2)太阳系外有宇宙人。(1)和(2)都是命题。(1)是对过去的事情进行判断，虽然我们一时很难分辨它的真假,但这句话本身是有其真假的。对于(2),目前人们尚无法确定其真假,但从事物的本质而论,句子本身是可分辨真假的,这类语句也称为命题。下面,命题用大写英文字母P,Q,P1,P2,表示。如果一个命题是真的，就说它的真值是1；如果一个命题是假的，就说它的真值是0。我们也用1代表一个抽象的真命题，用0代表一个抽象的假命题。,.,13,2.1.2逻辑联结词当我们用命题组成新的句子的时候，使用了语法中的逻辑联结词，下面我们介绍五种逻辑联结词（或称命题的五种运算）。我们将会看到，它们和自然语言里的联结词是有所不同的，它们是自然语言里的联结词的逻辑抽象。若干个原子命题通过命题逻辑联结词而构成的新命题称为复合命题。定义2.1.1设P是一个命题，命题“P是不对的”称为P的否定，记以P，读作非P。P是真的当且仅当P是假的。例如，P：上海是一个城市。P：上海不是一个城市。,.,14,定义2.1.2设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以PQ，读作P或Q。规定PQ是真的当且仅当P，Q中至少有一个是真的。例如，P：今天下雨，Q：今天刮风，PQ：今天下雨或者刮风。自然语言中的“或者”一词有不可兼的意思。例如，“我到北京出差或者到广州去度假”表示的是二者只能居其一，不会同时成立。按照联结词“”的定义，当P，Q都为真时，PQ也为真，因此，“”所表示的“或”是“可兼或”，对于“不可兼或”，我们不可以用来表示。,.,15,定义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)是连续的。,.,16,显然,由定义知,当P是真的,Q是真的时,命题PQ是真的。这和日常生活中语言“如果则”的意思是一致的。但由定义知,如果P是假命题,则不管Q是什么命题,命题“如果P，则Q”在命题逻辑中都被认为是真命题。例如,P:22=5,Q:雪是黑的，于是,命题“如果22=5,则雪是黑的”是真命题。这是和人们日常生活