DM-专题1：集合和二元关系.ppt

电子科技大学信息与软件工程学院SchoolofInformationandSoftwareEngineering,UESTC2016,集合论与二元关系,2,第一部分集合论,预备知识集合的基本概念属于、包含幂集、空集文氏图等集合的基本运算并、交、补、差等集合恒等式集合运算的算律、恒等式的证明方法,命题逻辑的基本概念,命题与联结词命题及其分类联结词与复合命题命题公式及其赋值,命题与真值命题：判断结果惟一的陈述句命题的真值：判断的结果真值的取值：真与假真命题与假命题注意：感叹句、祈使句、疑问句都不是命题陈述句中的悖论，判断结果不惟一确定的不是命题,命题与联结词,5,例1下列句子中那些是命题？(1)是有理数.(2)2+5=7.(3)x+53.(4)你去教室吗？(5)这个苹果真大呀！(6)请不要讲话！(7)2050年元旦下大雪.,假命题,命题概念,真命题,不是命题,不是命题,不是命题,不是命题,命题，但真值现在不知道,6,命题分类：简单命题（也称原子命题）与复合命题简单命题符号化用小写英文字母p,q,r,pi,qi,ri(i1)表示简单命题用“1”表示真，用“0”表示假例如，令p：是有理数，则p的真值为0，q：2+5=7，则q的真值为1p,q,r可表示命题常元或者变元,7,否定、合取、析取联结词,定义1.3设p,q为两个命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词.规定pq为假当且仅当p与q同时为假.,定义1.1设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作p，符号称作否定联结词.规定p为真当且仅当p为假.,定义1.2设p,q为两个命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作pq，称作合取联结词.规定pq为真当且仅当p与q同时为真.,8,例2将下列命题符号化.(1)吴颖既用功又聪明.(2)吴颖不仅用功而且聪明.(3)吴颖虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.,合取联结词的实例,9,解令p:吴颖用功,q:吴颖聪明(1)pq(2)pq(3)pq(4)设p:张辉是三好生,q:王丽是三好生pq(5)p:张辉与王丽是同学(1)(3)说明描述合取式的灵活性与多样性(4)(5)要求分清“与”所联结的成分,合取联结词的实例,10,例3将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王小红生于1975年或1976年.,析取联结词的实例,11,解(1)令p:2是素数,q:4是素数,pq(2)令p:2是素数,q:3是素数,pq(3)令p:4是素数,q:6是素数,pq(4)令p:小元元拿一个苹果,q:小元元拿一个梨(pq)(pq)(5)p:王小红生于1975年,q:王小红生于1976年,(pq)(pq)或pq(1)(3)为相容或(4)(5)为排斥或,符号化时(5)可有两种形式，而(4)则不能,析取联结词的实例,12,定义1.4设p,q为两个命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词.规定：pq为假当且仅当p为真q为假.,蕴涵联结词,(1)pq的逻辑关系：q为p的必要条件(2)“如果p,则q”有很多不同的表述方法：若p，就q只要p，就qp仅当q只有q才p除非q,才p或除非q，否则非p，(3)当p为假时，pq恒为真，称为空证明(4)常出现的错误：不分充分与必要条件,13,例4设p：天冷，q：小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.,蕴涵联结词的实例,pq,pq,pq,定义1.5设p,q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词.规定pq为真当且仅当p与q同时为真或同时为假.pq的逻辑关系：p与q互为充分必要条件,等价联结词,例5求下列复合命题的真值(1)2+24当且仅当3+36.(2)2+24当且仅当3是偶数.(3)2+24当且仅当太阳从东方升起.(4)2+24当且仅当美国位于非洲.(5)函数f(x)在x0可导的充要条件是它在x0连续.,1,0,0,1,0,命题公式,（1）单个命题命题常元或者变元是命题公式（2）若A是命题公式，A也是命题公式（3）若A,B是命题公式，则AB，AB，AB，AB也是命题公式（4）有限次应用（1）-（3）规则形成的符号串才是命题公式，或称命题形式，简称公式,命题公式,针对含变元的公式，可进行赋值成真赋值成假赋值重言式（永真式）矛盾式（永假式）可满足式,等值式与基本的等值式,等值式定义2.1若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式几点说明：定义中，A,B,均为元语言符号A或B中可能有哑元出现.例如，在(pq)(pq)(rr)中，r为左边公式的哑元.,基本的等值式,双重否定律AA幂等律AAA,AAA交换律ABBA,ABBA结合律(AB)CA(BC),(AB)CA(BC)分配律A(BC)(AB)(AC),A(BC)(AB)(AC)德摩根律(AB)AB(AB)AB吸收律A(AB)A,A(AB)A,基本的等值式,零律A11,A00同一律A0A.A1A排中律AA1矛盾律AA0蕴涵等值式ABAB等价等值式AB(AB)(BA)假言易位ABBA等价否定等值式ABAB归谬论(AB)(AB)A注意：要牢记各个等值式，这是继续学习的基础,等值演算,置换规则：设(A)是含公式A的公式，用公式B替换A，得到(B)。如果AB,则(A)(B)由已知等值式，应用置换规则，推演出新的等值式的过程，称为等值演算例：证明p(qr)和(pq)r等值（教材P2）,21,p,q,r,均表示命题.,联结词集为,，p,pq,pq,pq,pq为基本复合命题.其中要特别注意理解pq的涵义.反复使用,中的联结词组成更为复杂的复合命题.设p:是无理数，q:3是奇数，r:苹果是方的，s:太阳绕地球转则复合命题(pq)(rs)p)是假命题.,命题相关小结,联结词的运算顺序：,同级按先出现者先运算.,一阶谓词逻辑基本概念,在命题逻辑中，我们把命题分析到简单命题为止，而简单命题是不再进行分析的基本元素，因此，当推理涉及到简单命题的结构时，命题逻辑对此是无能为力的。例如下面的推理：所有的自然数都是实数，3是自然数。所以，3是实数。根据数学方面的知识，我们知道这个推理是正确的。然而，在命题逻辑中，这个推理的正确性是无法证明的，这是因为上述推理中的三句话均是简单命题，且各不相同，如果把它们形式化为命题逻辑中的公式，以p表“所有的自然数都是实数”，以q表“3是自然数”，以r表“3是实数”，则推理可以写为：(pq)r,一阶谓词逻辑基本概念,而(pq)r是一个可满足式，可知这个推理无法在命题逻辑推理理论中得到证明。另外，命题“所有的自然数都是实数”事实上隐含着“0是实数”，“1是实数”，“2是实数”，等无穷多个命题，单用一个p表示，很难体现这些。因此，为了能够进一步深入地研究推理，需要对简单命题做进一步的分析，将简单命题的结构分解为个体词、谓词、量词等，并讨论它们与推理之间的关系，这一部分的内容称为一阶逻辑(谓词逻辑)。,一阶谓词逻辑基本概念,首先我们将简单命题的结构分解成个体和谓词。个体(客体)我们讨论的对象。可以是具体的，也可以是抽象的。个体域(论域)个体所构成的非空集合。全总个体域(无限域)包含宇宙中一切事物的个体域谓词简单命题中，表示一个个体的性质或多个个体间的关系的词。之所以称之为谓词，是因为谓词和个体词一起构成了简单命题中的主谓结构。如：小王是学生。3是素数。2整除6。3位于2与5之间。,一阶谓词逻辑基本概念,上面这些简单命题中，小王、2、3、5、6均是个体，“是学生”，“是素数”，“整除”，“位于与之间”均是谓词。前两个谓词描述的是一个个体的性质，称为一元谓词；第三个表示两个个体之间的关系，称为二元谓词；第四个表示三个个体之间的关系，称为三元谓词。以此类推，我们将描述n(n2)个个体之间关系的谓词称为n元谓词。通常用大写字母F、G、H(可加下标)来表示谓词。如：F表示“是学生”；G表示“整除”；H表示“位于与之间”。,一阶谓词逻辑基本概念,这时F、G、H表示的是具体的谓词，称为谓词常元，否则，称为谓词变元。显然，单独的一个谓词(即使是谓词常元)并不能构成一个完整的句子，必须以个体词取代“”方能构成一个句子。通常用小写的英文字母a、b、c(可加下标)等表示个体：“小王是学生”可符号化为F(a)，其中a表示小王。若用b表示小李，则F(b)就表示“小李是学生”。若用c1表示2，用c2表示6，则G(c1，c2)就表示“2整除6”,一阶谓词逻辑基本概念,这里，a、b、c1、c2均是具体的个体，称为个体常元。一般我们用F(x)表示“x是学生”，其中的x称为个体变元(简称变元，亦称个体词)。类似地，我们也可用G(x，y)表示“x整除y”。由谓词符和变元符组成的符号串称为命题函数。只有谓词为常元并将其中的变元代以具体的个体后，才能构成命题。例如：“G(x，y)：x整除y。”并不是命题，但若取a：2，b：6，则G(a，a)，G(a，b)以及G(b，a)均是命题，前两个是真命题，第三个是假命题。G(a，a)、G(a，b)等称为0元谓词，它们不含个体变元，0元谓词即命题。,一阶谓词逻辑基本概念,注意(1)多元谓词中变元的顺序不同，表示的意义也不同。如G(x，y)表“x整除y”，而G(y，x)表“y整除x”。(2)在谓词逻辑中，、仍是联结词，其含义和用法与命题逻辑中的相同。【例】将下列语句形式化为谓词逻辑中的命题或命题函数。(1)小王是二年级大学生。(2)小王是李老师的学生。(3)如果xy且yx，则x=y。,一阶谓词逻辑基本概念,解：(1)令F(x)：x是大学生；G(x)：x是二年级的；a：小王。则原句形式化为：F(a)G(a)(2)令F(x，y)：x是y的学生；a：小王；b：李老师。则原句形式化为：F(a，b)(3)令F(x，y)：xy；G(x，y)：x=y。则原句形式化为(F(x，y)F(y，x)G(x，y),一阶谓词逻辑基本概念,此外，在一般的简单命题中，常有一些表示数量的词语，诸如“所有的”、“有一些”等等，用来表示谓词中的变量取自论域中的全体或部分个体，例如下面的两个陈述句：“对所有的xD，论断F(x)为真。”“对某些xD，论断F(x)为真。”在谓词逻辑中，我们用量词把它们形式化。,一阶谓词逻辑基本概念,1全称量词“”全称量词用来表示个体域中的全体。表自然语言中的“所有的”、“任意的”、“每一个”等等。如：“任意偶数均能被2整除。”句子可改写成：“在偶数集合中的任意的x，x能被2整除。”取个体域为偶数集，用F(x)表示“x能被2整除”，用x表示“任意的x”，则原句形式化为：xF(x),一阶谓词逻辑基本概念,注意xF(x)表示的是“在个体域中，任意的x均有F(x)这个性质”，这是一个可以确定真值的命题。当个体域D为有穷集时：xF(x)的真值为1，当且仅当对于每一个xD，均有F(x)真值为1；xF(x)的真值为0，当且仅当至少有一个x0D，使得F(x0)真值为0。,一阶谓词逻辑基本概念,2存在量词“”存在量词用来表示论域中的部分个体。表自然语言中的“存在着一些”、“至少有一个”、“有”等等。如：“我们班有人会吸烟。”句子可改写成：“在我们班有一些x，x会吸烟。”取个体域为“我们班的同学”，用G(x)表示“x会吸烟”，用x表示“有些x”，则原句形式化为：xG(x),一阶谓词逻辑基本概念,注意xG(x)表示的是“在个体域中，至少有一个x具有G(x)这个性质”，这是一个可以确定真值的命题。当个体域D为有穷集时，不妨设D=a1，a2，an：xG(x)的真值为0，当且仅当对于每一个xD，均有G(x)真值为0；xG(x)的真值为1，当且仅当至少有一个x0D，均有G(x0)真值为1。,一阶逻辑谓词概念总结,基本概念个体词、谓词、量词个体（个体词）所研究对象中可以独立存在的具体或抽象的客体（名词或代词充当）个体常项：具体的事务，用a,b,c表示个体变项：抽象的事物，用x,y,z表示各体域个体变项的取值范围有限个体域，如a,b,c,1,2无限个体域，如N,Z,R,全总个体域宇宙间一切事物组成,一阶逻辑谓词概念总结,谓词表示个体词性质或相互之间关系的词谓词常项：F:是人，F(a)：a是人谓词变项：F:具有性质F，F(x)：x具有性质Fn（n1）元谓词n=1，一元谓词表示性质n2，多元谓词表示事物之间的关系L(x,y)：x与y有关系L，L(x,y)：xy，（4）0元谓词不含个体变项的谓词命题常项或变项3.量词表示数量的词全程量词：“”，x存在量词：“”，x,一阶逻辑谓词概念总结,例：在一阶逻辑中将下面命题符号化人都爱美有人用左手写字个体域分别为(a)D=“人类集合”=x|x是人(b)D为全总个体域解：(a)（1）xG(x),G(x)：x爱美（2）xG(x),G(x)：x用左手写字(b)F(x)：x为人，G(x)：同(a)中,一阶逻辑谓词概念总结,例在一阶逻辑中将下面命题符号化正数都大于负数有的无理数大于有的有理数解注意：题目中没给个体域，一律用全总个体域（1）令F(x)：x为正数，G(y)：y为负数L(x,y)：xyx(F(x)y(G(y)L(x,y)xy(F(x)G(y)L(x,y)（以后讨论）（2）令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：xyx(F(x)y(G(y)L(x,y)xy(F(x)G(y)L(x,y)（以后讨论）,39,集合的基本概念,1.集合定义集合没有精确的数学定义理解：由离散个体构成的整体称为集合，称这些个体为集合的元素常见的数集：N,Z,Q,R,C等分别表示自然数、整数、有理数、实数、复数集合,2.集合表示法枚举法-通过列出全体元素来表示集合谓词表示法-是将集合中元素的共同属性描述出来文氏图-用于示意性地表示集合及其包含元素间的关系实例：枚举法自然数集合N=0,1,2,3,谓词法S=x|x是实数，x21=0,40,元素与集合,1.集合的元素具有的性质无序性：元素列出的顺序无关相异性：集合的每个元素只计数一次确定性：对任何元素和集合都能确定这个元素是否为该集合的元素任意性：集合的元素也可以是集合2元素与集合的关系隶属关系：或者3集合的树型层次结构,dA,aA,41,集合与集合,集合与集合之间的关系：,=,定义1.1ABx(xAxB)定义1.2A=BABBA定义1.3ABABABABx(xAxB)思考：和的定义注意和是不同层次的问题,42,空集、全集和幂集,1定义1.4空集：不含有任何元素的集合实例：x|xRx2+1=0定理1.1空集是任何集合的子集。证对于任意集合A，Ax(xxA)T(恒真命题)推论是惟一的,3.定义1.6全集E：包含了所有集合的集合全集具有相对性：与问题有关，不存在绝对的全集,2.定义1.5幂集：P(A)=x|xA实例：P()=,P()=,计数：如果|A|=n，则|P(A)|=2n.,43,集合的运算,初级运算集合的基本运算有定义1.7并AB=x|xAxB交AB=x|xAxB相对补AB=x|xAxB定义1.8对称差AB=(AB)(BA)=(AB)-(AB)定义1.9绝对补A=EA,44,文氏图,集合运算的表示,A,B,A,B,A,B,A,B,A,B,AB,AB,AB,AB,A,45,几点说明,并和交运算可以推广到有穷个集合上，即A1A2An=x|xA1xA2xAnA1A2An=x|xA1xA2xAnABAB=AB=AB=A,46,广义运算,1.集合的广义并与广义交定义1.10广义并A=x|z(zAxz)广义交A=x|z(zAxz)实例1,1,2,1,2,3=1,2,31,1,2,1,2,3=1a=a，a=aa=a，a=a,47,关于广义运算的说明,2.广义运算的性质(1)=，无意义(2)单元集x的广义并和广义交都等于x(3)广义运算减少集合的层次（括弧减少一层）(4)广义运算的计算：一般情况下可以转变成初级运算A1,A2,An=A1A2AnA1,A2,An=A1A2An3.引入广义运算的意义可以表示无数个集合的并、交运算，例如x|xR=R这里的R代表实数集合.,48,运算的优先权规定,1类运算：初级运算,，优先顺序由括号确定2类运算：广义运算和运算，运算由右向左进行混合运算：2类运算优先于1类运算,例1A=a,a,b，计算A(AA).解：A(AA)=a,b(a,ba)=(ab)(ab)a)=(ab)(ba)=b,49,有穷集合元素的计数,1.文氏图法2.包含排斥原理定理设集合S上定义了n条性质，其中具有第i条性质的元素构成子集Ai,那么集合中不具有任何性质的元素数为,推论S中至少具有一条性质的元素数为,50,实例,例2求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？,解尝试方法一：文氏图定义以下集合：S=x|xZ1x1000A=x|xSx可被5整除B=x|xSx可被6整除C=x|xSx可被8整除画出文氏图，然后填入相应的数字，但是A,B,C之间有交集，所以难以计算,A,B,C,200,166,125,8,33,25,41,51,实例,方法二利用容斥原理|S|=1000|A|=1000/5=200,|B|=1000/6=166,|C|=1000/8=125|AB|=1000/lcm(5,6)=1000/30=33|AC|=1000/lcm(5,8)=1000/40=25|BC|=1000/lcm(6,8)=1000/24=41|ABC|=1000/lcm(5,6,8)=1000/120=8=1000(200+166+125)+(33+25+41)8=600,52,集合恒等式,集合算律1只涉及一个运算的算律：交换律、结合律、幂等律,53,集合算律,2涉及两个不同运算的算律：分配律、吸收律,54,集合算律,3涉及补运算的算律：DM律，双重否定律,55,集合算律,4涉及全集和空集的算律：补元律、零律、同一律、否定律,2019/11/25,集合论与图论第3讲,56,对偶原理(dualprinciple),对偶式(dual):一个集合关系式,如果只含有,E,=,那么,同时把与互换,把与E互换,把与互换,得到的式子称为原式的对偶