第一编集合论.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Peking University,*,第一编 集合论,第一章 集合,1,Peking University,1.1 预备知识（,prerequisites）,命题逻辑和谓词逻辑是数理逻辑中最基本的内容。,十九世纪中后期，德国数学家莱布尼兹、英国数学家布尔和逻辑学家怀海特、罗素为数理逻辑的产生和发展有突出贡献。,从二十世纪40年代起，数理逻辑成为计算机科学的重要基础理论之一。如布尔代数在计算机硬件设计中发挥了重大作用；形式语言的研究为建立计算机语言提供了基础。,2,Peking University,命题和命题联结词,命题公式和真值表,命题等值式,命题推理定律,命题逻辑,3,Peking University,命题是客观上能判明真假的陈述句,。,当命题为真时，称,命题的真值,为“真”；否则，说命题的真值为“假”。用,T,或1表示“真”，用,F,或0表示“假”。,（,Proposition:a statement that is either true or false,but not both.）,所有这些命题，都应具有确定的真值。,4,Peking University,判断下列语句是不是命题:,(1)天气多好啊!,(2)你去哪里？,(3),X3。,(4)别的星球有生物。,(5),我正在说慌。,解,：,(1)是感叹句；(2)是疑问句；它们都不是命题。,(3)真假要视的值而定，因此这个语句无确定真值。它不是命题。,(4)的真实性目前还无法判明，但在客观上，是真是假，二者必居其一。因此它是命题。,(5)同样不能判明真假。如说该命题为真，但原语句却说“本命题为假”；如果说它为假，却又肯定了它(本命题)是真的，这样造成了自相矛盾的结果！这是所谓悖论。,5,Peking University,定义1,否定联结词,设为命题，复合命题非，叫的否定式，记作,。记号,叫,否定联结词,。,为真当且仅当为假。,例如，设,：,今天是星期二,。,则,：,今天不是星期二。,8,Peking University,定义2,合取联结词,设，表示两个命题，复合命题“且”叫命题与的合取，记作。记号叫合取联结词。为真，当且仅当，同时为真。,例,如，设,:2是素数。,:2是偶数。,R：2,是,奇,数。,则,：2,既,是素数又是偶数,。(,真值为真),R,：2,既,是素数又是,奇,数。(,真值为假),9,Peking University,定义3,析取联结词,设，为二命题，复合命题“或”称作与的析取，记作，叫析取联结词。为真，当且仅当，之中至少有一为真。,例,如，设,：2是素数。：2是偶数。,R：2,是,奇,数。,则,：2是素数,或2,是偶数,。(,真值为真),R,：2,是素数,或,2是,奇,数。(,真值为真),10,Peking University,2-30或今天天气很好。,他今天骑车或走路来上课。,从理科1号楼到图书馆要2分钟或4分钟。,相容或?,意思：,大约2分钟到4分钟,p,q,一个人不可能同时骑车又走路,11,Peking University,注：,“或”有两种标准用法，,张三或李四考了90分（相容“或,”）,第一节课上数学或者上英语,12,Peking University,定义4,蕴涵联结词,设，是二命题，复合命题“如，则”称为与的,蕴涵式,，记作,其中叫前件或前题，叫后件或结论。为真当且仅当真和假不同时成立,。,例,如，,如果明天天晴就开运动会,。,设,：明天天晴。:明天开运动会。,则原命题表示为：,。,13,Peking University,蕴涵式、蕴涵联结词,p,q,就,则,只要,仅当,才,只有,p,q,蕴涵符号,p,q,p,q,0,0,1,0,1,1,1,0,0,1,1,1,如果,如果明天下雨，我们就放假,明天不下雨,我们不放假,明天不下雨,我们放假,明天下雨,我们不放假,明天下雨,我们放假,14,Peking University,定义5 等价,联结词,设,为二命题，复合命题“当且仅当”称为与的,等价式,，记作,。,叫,等价,联结词，也记作,iff。,为真当且仅当,真值相同,。,例,如，,2+24当且仅当,雪是白的,。,设,：2+24。：,雪是白的,。,则原命题表示为：,。,15,Peking University,命题一般用大写英文字母表示。表示命题的符号叫,命题标识符,。,例如，用表示“雪是黑的”，记作“：雪是黑的”。,如果一个命题标识符表示某个确定的命题，则称为,命题常量,。特别地，真命题(用,T,表示)和假命题(用,F,表示)是命题常量。,如果一个命题标识符表示不确定的命题，则称为,命题变元,。,命题常量和命题变元,命题变元不是命题,。在命题演算中，对命题变元指定相应的真值(真或假)，称为对命题变元的,真值指派,。集合,T,F,是,命题变元的值域,。,16,Peking University,相应的真值表,17,Peking University,命题公式,设,P,和,Q,是任意两个命题，则下列命题都是复合命题,设,P,和,Q,是,命题变元,，则上述公式均称作,命题公式,。,P,和,Q,称作命题公式的分量。,18,Peking University,命题公式,(1)单个命题变元（或常元）是命题公式；,(2)若,A,是命题公式，则(,A,),是命题公式；,(3)若,A,B,是命题公式，则（,A,B,），（,AB,）,(,AB),(A B),也是命题公式；,(4)只有有限次应用(1)-(3)形成的符号串才是命题公式。,注意：命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一个值。,19,Peking University,真值表(,truth table),定义,设为一命题公式，,P,1,P,2,，,P,n,为出现在中的所有命题变元，简记为,（,P,1,P,2,，,P,n,）,。,给命题变元,P,1,P,2,，,P,n,指定一组真值，称为对的一个指派或一个赋值。含有个命题变元的命题公式,（,P,1,P,2,，,P,n,）,共有,n,个指派。将命题公式,（,P,1,P,2,，,P,n,）,在所有指派之下取值的情况列成表，叫的,真值表,。,20,Peking University,真值表,命题形式,A,在其所有可能的赋值下取得的值列成的表；,n,元真值函数,F,:0,1,n,0，1(,n,1)。,21,Peking University,联结词的,真值表,22,Peking University,A,的一个,赋值,:,n,个命题变元,成真赋值,成假赋值,重言式,（永真式,tautology）,P,P=1,矛盾式,（永假式,contradiction）,P,P=0,可满足式,23,Peking University,公式分类,重言式,矛盾式,可满足式,真！,假！,真真假假,重言式,等值演算,逻辑推理,24,Peking University,p,q,p,q,p,p,p,(p,q),p,0,0,1,0,1,0,1,1,0,1,1,0,0,0,1,1,1,1,0,1,赋值,可满足式 矛盾式 重言式,(,永假式,)(,永真式,),25,Peking University,等值式（等价公式）,给定两个命题公式（,P,1,P,2,，,P,n,）,和（,P,1,P,2,，,P,n,），,若对,P,1,P,2,，,P,n,的任一组真值指派，与的真值都相同，则称与等价或逻辑相等。记作,。,例4,构造命题公式,（,PQ）,和,P,Q,的真值表,。,对于、的任一种真值指派，,（,PQ）,与,P,Q,都有相同的真值，,所以这,两个命题公式是等价的。,26,Peking University,为书写方便而省略括号,公式最外层的括号可以省略,联结词运算优先级别,同一个联结词连续多次出现且无括号，则从左到右运算,省略括号不改变公式复杂性,、,、,、,、,27,Peking University,例题：,层次法构造真值表,(,p(pq),(p,q),(,p,(,p,q,),(,p,q,),(,p(,pq,),(,p,q,),(,p(pq),),(p,q),p,q,pq,p,q,p(pq),(,p,q),公式,0 0,0 1,1 0,1 1,0,0,0,1,0,1,1,1,0,0,1,1,1,0,0,0,1,1,0,0,真值表和真值函数,28,Peking University,等值式(,logical equivalences),29,Peking University,A,A,A,A,A,A,A,(B,C),(A,B),(A,C),A,(B,C),(A,B),(A,C),幂等律,交换律,结合律,分配律,A,B,B,A,A,B,B,A,(,A,B),C,A,(B,C),(A,B),C,A,(B,C),30,Peking University,德摩根律,(,AB)A B,(AB)A B,吸收律,A (AB)A,A (AB)A,31,Peking University,A,1,1,A,0,0,A,0,A,A,1,A,A,A,1,A,A,0,零律,同一律,排中律,矛盾律,(,对偶原理,:,-,互换,0,-,1,互换,),32,Peking University,A,A,A,B,A,B,A,B,(A,B),(B,A),双重否定律,蕴涵等值式,等价等值式,33,Peking University,A,B,A,B,A,B,B,A,(,A,B),(A,B),A,等价否定等值式,假言易位,归谬论,牢固记住并能熟练运用，,是学好离散数学的关键之一,34,Peking University,设是合式公式中的一个部分，且也是一个合式公式，则称是的,子公式,。,例,如，设：(,PQ)（Q(R,S)），,则,PQ、R,S、,S、Q(R,S),都是的子公式。,置换,规则,定理,（,置换,规则）：,设X是合式公式中的子公式，若是一个合式公式，且,，用置换中的，得到新的合式公式，则,。,证明：,与除替换部分外均相同，又由于替换部分,，即是说对任一指派，与真值相同，那么与对任一真值指派也应有相同的真值。故,。,35,Peking University,等值演算,：,由已知的等值式，应用置换规则推演出新的等值式的过程,。,等值演算,P(Q R),P,(,Q R),P,(,Q R),(,P,Q)R,(,P,Q)R,(,P,Q)R,36,Peking University,给定命题公式(,P,1,P,2,，,P,n,)，,如果用某个命题公式,B,i,取代中的某个变元,P,i,，,并且用,B,i,取代中出现的所有,P,i,，,这样得到的命题公式称为命题公式的,代入实例,。,例,如，设：,P(QP)，,用(,R,S),取代中的命题变元得：(,R,S)(Q(R,S)，,是的代入实例。,代入,规则,定理,（代入规则）：,一个重言式的代入实例仍然是一个重言式,。,证明：,由于重言式的真值与真值指派无关，故对同一命题变元,都用某个,命题公式,代替,，该重言式的真值仍为。,例,证明(,PS)R),(PS)R),为重言式,证：,因,P,P,T，,根据,代入规则,(,PS)R),(PS)R),T,37,Peking University,命题逻辑推理,1.,推理的形式结构,前提,:,A,1,A,2,A,k,结论,:,B,推理的形式结构,:,(,A,1,A,2,A,k,),B,38,Peking University,推理定律,39,Peking University,(1),附加律,A,(A,B),前提,:,A,结论,:,A,B,A,(A,B),是永真式,40,Peking University,(2),化简律,(,A,B),A,(A,B),B,前提,:,A,B,结论,:,A,(A,B),A,是永真式,41,Peking University,(3),假言推理,(,A,B),A,B,前提,:,A,B,A,结论,:,B,(A,B),A),B,是永真式,42,Peking University,(4),拒取式,(,A,B),B,A,前提,:,A,B,B,结论,:,A,(A,B),B),(,A),是永真式,43,Peking University,(5),析取三段论,(,A,B),A,B,(A,B),B,A,前提,:,A,B,A,结论,:,B,(A,B),A),B,是永真式,44,Peking University,(6),假言三段论,(,A,B),(B,C),(A,C),前提,:,A,B,B,C,结论,:,A,C,(A,B),(B,C),(A,C),是永真式,45,Peking University,(7),等价三段论,(,A,B),(B,C),(A,C),前提,:,A,B,B,C,结论,:,A,C,(A,B),(B,C),(A,C),是永真式,46,Peking University,(8),构造性两难,(,A,B),(C,D),(A,C),(B,D),前提,:,A,B,C,D,A,C,结论,:,B,D,47,Peking University,判断推理正确的方法,例,前提,:,p,(q,r),p,q,结论,:,r,方法一,:,推理的,形式结构,方法二,:,从前提,推演,结论,48,Peking University,方法一,(,形式结构是永真式,),(,p,(q,r),p,q,r,(,p,(,q,r,),p,q,r（,蕴涵等值式）,(,p,p,),(,q,r),p,),q,r（,分配律）,(,q,r),q),p,r （,零律，同一律，交换律）,(,q,q,),(r,q),p,r （,分配律）,(r,q,p),r,(r,q,p),r （,蕴涵等值式）,r,q,p,r,(,r,r,),q,p,1,49,Peking University,方法二,(,从前提,推演,结论,),(,p,(q,r),p,q,(p,(q,r),p),q,(q,r),q,（,假言推理）,r,50,Peking University,命题逻辑,命题和命题联结词,命题公式和真值表,命题等值式,命题推理定律,51,Peking University,命 题,等值演算,推理,命题逻辑,数学量,运算方式,数学表达式,命题,逻辑联结词,命题公式,计算表达式的值,真值表法,52,Peking University,谓词逻辑,在命题逻辑中，研究命题和命题的演算。命题演算的基本单位是原子命题。在命题演算中，原子命题不再分解。命题逻辑在推证中有很大的局限性，有些简单的论断也不能用命题逻辑进行推证。,例如，对著名的“苏格拉底三段论”就无法判断其正确性：“所有的人都是要死的。苏格拉底是人，所以苏格拉底是要死的。”,为了克服命题逻辑的局限性，就需要深入分析命题的内部的逻辑结构。为此，必须对原子命题作进一步的分解，引入谓词逻辑的概念。,53,Peking University,谓词逻辑,在命题逻辑中，研究命题和命题的演算。命题演算的基本单位是原子命题。在命题演算中，原子命题不再分解。命题逻辑在推证中有很大的局限性，有些简单的论断也不能用命题逻辑进行推证。,例如，对著名的“苏格拉底三段论”就无法判断其正确性：“所有的人都是要死的。苏格拉底是人，所以苏格拉底是要死的。”,为了克服命题逻辑的局限性，就需要深入分析命题的内部的逻辑结构。为此，必须对原子命题作进一步的分解，引入谓词逻辑的概念。,54,Peking University,谓词的概念与量词,谓词,公式与翻译,等价式、蕴含式,前束范式,谓词逻辑,55,Peking University,谓词的概念,命题是反映判断的句子。反映判断的句子由主语和谓语两部分组成。主语一般是客体；用以刻划客体性质或关系的部分即是谓语。,在命题中作为主语的客体称为,个体,。而,用以描述个体性质或几个个体间关系的部分称为,谓词,。,例如对“,张三是大学生”和“李四是大学生”,这两个命题，个体分别是“张三”和“李四”，,谓词,都是“是大学生”。在作符号化处理时，用表示“是大学生”，用表示“张三”，用表示“李四”。上述两个命题可分别表示为()和()，从而把命题中的主语和谓语分离开来。,56,Peking University,谓词的概念,(续),用谓词表达命题，必须包括,个体和谓词,两部分。一般地说，“是”类型的命题可用()表达。而表示两个或两个以上客体之间关系的命题，如“大于”，“在和之中”，可表示成(，)，(，)。这里表示“.大于.”，表示“,在,和,之中”。,表示一个个体的性质的谓词称为,一元谓词,，如（,e）。,而表述个个体相互关系的谓词称为,元谓词,，可表示为(,e,1,，e,2,，,，,e,n,)。,57,Peking University,个体域,对命题函数而言,，,客体变元的论述范围叫,个体域,，,将所有个体域的集合(即宇宙间的一切事物)称为,全总个体域,。,客体变元取值的范围对命题函数是否构成命题及命题的真值密切相关。,例如,用（）表示“是大学生”，如果的取值范围是某大学某班中的全体学生，则（）是永真式；如果的取值范围是某中学某班中的全体学生，则（）是永假式；如果的取值范围是某剧场中的观众，则（）的真值可真可假，因为观众中可能有大学生，也可能有非大学生,58,Peking University,量词,考虑命题“,所有的,人都是要死的,”和“,有些,人能活百岁以上,”的符号化问题，,除个体变元和谓词之外，还有,对个体在数量上的量化和约束,，如“所有的”和“有些”，称这种表示数量的词为,量词,。,用符号,表达“对所有的”，“对任一个”，“对每一个”等词，叫做,全称量词,。,例如，,“所有的人都是要死的”,。设,M(x):x,是人。,D(x):x,是要死的,。则命题可符号化为：,(,x)(M(x),D(x),。,用符号,表达“至少有一个”，“存在一个”，“对某些”等词，叫做,存在量词,。,例如，,“有些人能活百岁以上”,。设,M(x):x,是人。,L(x):x,能活百岁以上,。则命题可符号化为：,(,x)(M(x),L(x),。,59,Peking University,(1)个体域中所有有性质,F,的个体都有性质,G，,应符号化为,(2)个体域中存在有性质,F,同时有性质,G,的个体，应符号化为,60,Peking University,一阶谓词基本概念,个体（词）,个体域,全总个体域,谓词(,Predicate),量词(,quantifiers),全称量词(,universal quantifier),存在量词(,existential quantifier),61,Peking University,谓词公式,定义为,（1）,n,元谓词是一个谓词公式；,（2）若,A,是谓词公式，则（,A）,也是谓词公式；,（3）若,A，B,是谓词公式，则（,A,B）、（A,B）、（A,B）、（A,B）,也是谓词公式；,（4）若,A,是谓词公式且含有未被量化的个体变量,x，,则,xA(x)，,XA(x),也是谓词公式。,（5）有限次地使用（1）（4）所得到的也是谓词公式。,62,Peking University,指导变元：,xA(x)，,xA(x),中的,x,相应量词的辖域：,xA(x)，,xA(x),中的,A,约束出现：,x，,x,的辖域中，,x,的所有出现,自由出现：,A,中不是约束出现的变元,例：,(,x)(P(x)Q(x，y),谓词公式中的基本概念,63,Peking University,谓词公式的解释,谓词公式中含有个体变元和谓词变元。给定个体域，,将谓词公式中个体变元由确定的个体来取代，谓词变元由特定的谓词来取代，称为对谓词公式的赋值或,解释,。,对谓词公式作了这样的赋值之后，谓词公式成为命题。,例,求(,x)（P(x)Q(x)）,的真值，其中(,x)：x,等于1；(,x)：x,等于2；且个体域1,2。,解,：(,x)(P(x)Q(x),(P(1)Q(1)(P(2)Q(2),(,)(),64,Peking University,可满足公式,不可满足公式（永假式）,永真式,可真可假式（不确定式）,谓词公式,分类：,65,Peking University,等价式和蕴含式,定义,给定个体域,E,上的两个谓词公式和，若对和中的变项作同样的赋值，所得命题的真值都相同，则称谓词公式和在上是,等价,的，记作：,。,66,Peking University,谓词演算中的等价式和蕴含式的来源可分为如下几类：,1命题公式的推广,2.在有限个体域中消去量词,3.量词与联结词,之间的关系,量词辖域的扩张与收缩,量词分配的等值式,量词分配的蕴含式,67,Peking University,1命题公式的推广,用原子谓词公式取代命题演算等价公式中的各命题变元，命题演算的等价式就转化为谓词演算的等价式。例如：,A(x),A(x),(,x)A(x)(,x)B(x),(,x)A(x)(,x)B(x),68,Peking University,2在,有限个体域中,消去量词,xA(x),A(a,1,),A(a,2,),A(a,n,),xA(x),A(a,1,),A(a,2,),A(a,n,),69,Peking University,3量词与联结词,之间的关系,(,x)A(x),(,x),A(x)。,(,x)A(x),(,x),A(x)。,例如，设,A(x),表示“,x,今天来校上课”，则,A(x),表示“,x,今天没来校上课”。那麽，,对(1),“不是所有的人今天都来上课,(,x)A(x)”,与“有(存在)一些人今天没来上课(,x),A(x)”,在意义上是相同的。,对(2),“今天没有(不存在)来上课的人,(,x)A(x)”,与“所有的人今天都没来上课(,x),A(x)”,在意义上是相同的。,和式称为,量词转换律,。,这里,约定，出现在量词之前的否定不是否定该量词，而是否定被量化了的整个命题。例如，,(,x)A(x),(,(,x)A(x),),。,70,Peking University,等价式和蕴含式,(续),4量词辖域的扩张与收缩,(,x)A(x)B,(,x)（A(x)B）,(,x)A(x)B,(,x)（A(x)B）,(,x)A(x)B,(,x)（A(x)B）,(,x)A(x)B,(,x)（A(x)B）,当个体域为有限集,a,1,a,2,.,a,n,时，我们可以验证式：,(,x)A(x)B,(A(a,1,)A(a,2,).A(a,n,)B,(A(a,1,)B)(A(a,2,)B).(A(a,n,)B),(,x)(A(x)B)。,例,:证明,(,x)(A(x)B),(,x)A(x)B,证,：(,x)(A(x)B),(,x)(,A(x)B),(,x),A(x)B,(,x)A(x)B,(,x)A(x)B),71,Peking University,等价式和蕴含式,(续),5量词分配的等值式,(,x)(A(x)B(x),(,x)A(x)(,x)B(x),(,x)(A(x)B(x),(,x)A(x)(,x)B(x),式的左边表示“对于所有的，,A(x),和,B(x),都是真的”；右边表示“对于所有的，,A(x),是真的；同时对于所有的，,B(x),也是真的”。显然，这两个命题是等价的。例如，“联欢会上所有的人既唱歌又跳舞”和“联欢会上所有的人唱歌且所有的人跳舞”的意义相同。,式左边的命题可表述成“存在一个，能使()为真或者能使()为真”；右边的命题可表述成“存在使()为真，或者存在使()为真”。显然，这两个命题也是等价的。例如，“联欢会上有人唱歌或跳舞”和“联欢会上有人唱歌，或有人跳舞”的意义相同。,72,Peking University,等价式和蕴含式,(续),6,量词分配的蕴含式,(,x)A(x),(,x)B(x),(,x)(A(x)B(x),(,x)(,A(x)B(x),),(,x)A(x)(,x)B(x),例如，对式，“每一个人都唱歌或者每一个人都跳舞”，那么可以说“每一个人都唱歌或跳舞”。但反之不真。,对式，“有人既唱歌又跳舞”永真蕴含“有人唱歌且有人跳舞”。反之不真。,注意,：,全称量词,x,对于析取不服从分配律,：,(,x)(A(x)B(x),(,x)A(x)(,x)B(x),类似的情况是，,存在量词,对于合取不服从分配律,：,(,x)(A(x)B(x),(,x)A(x)(,x)B(x),73,Peking University,推理定律,74,Peking University,一阶谓词逻辑等值式与蕴含式,命题公式的推广,在有限个体域中消去量词等值式,量词否定等值式,量词辖域收缩与扩张等值式,量词分配等值式,量词分配蕴含式,75,Peking University,前束范式,定义,：一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，则称该公式叫做,前束范式,。,前束范式可记为如下形式,(,v,1,)(v,2,).(v,n,),其中“”表示量词,或,，,v,1,，v,2,，.，v,n,是客体变元，是不带量词的谓词公式。,例如，(,x)(,y)(,z)（Q(x,y)R(z)）,是前束范式。,76,Peking University,定理,任意一个谓词公式，均和一个前束范式等价。,证明：首先利用量词转化公式可将否定深入到变元和谓词公式的前面。其次利用量词辖域扩张可将量词移到全式的最前面，这样便得前束范式。,77,Peking University,换名规则,：将公式,A,中某量词辖域中出现的某个约束出现的个体变元及相应的指导变元,x，,都改成公式,A,中没出现过的,y,78,Peking University,命 题,等值演算,推理,基本要素,中心,谓词与量词,等值演算,推理,命题逻辑,谓词逻辑,数理逻辑框架,79,Peking University,小结,命题逻辑,命题和命题联结词,命题公式和真值表,命题等值式,命题推理定律,谓词逻辑,谓词的概念与量词,谓词,公式与翻译,等价式、蕴含式,前束范式,80,Peking University,作业,用真值表证明以下等价式和蕴涵式,2.不构造真值表证明1中各式,把下列命题符号化，并求前束范式,“所有运动员都钦佩某些教练”,证明,P7,定律(3),x(A(x),B(x),xA(x,),xB(x,),81,Peking University,