离散数学期末复习大纲-PPT.pptx

离散数学期末复习大纲复 习 时 注 意准确掌握每个概念准确掌握每个概念灵活应用所学定理灵活应用所学定理注意解题思路清晰注意解题思路清晰证明问题时证明问题时,先用反向思维先用反向思维(从结从结论入手论入手)分析问题分析问题,再按正向思维再按正向思维写出证明过程写出证明过程、全书知识网络全书知识网络:图图论论篇篇同构同构同构同构格与布尔代数格与布尔代数半群半群,独异点独异点,群群,环环,域域代数系统篇代数系统篇n 元运算元运算命题逻辑命题逻辑谓词逻辑谓词逻辑集合初步集合初步二元关系二元关系函函 数数集合论篇集合论篇数理逻辑篇数理逻辑篇总 复 习复习重点复习重点(注注:标有标有*得内容得内容,对网络学院学生不作要求对网络学院学生不作要求)第一章第一章 命题逻辑命题逻辑1、联结词得定义联结词得定义(含义及真值表定义含义及真值表定义)、2、会命题符号化会命题符号化、3、永真式得证明永真式得证明、4、永真蕴涵式得证明永真蕴涵式得证明,记住并能熟练应用常用公式记住并能熟练应用常用公式、5、等价公式得证明等价公式得证明,记住并能熟练应用常用公式记住并能熟练应用常用公式、6、会写命题公式得范式会写命题公式得范式,*能应用范式解决问题能应用范式解决问题、7、熟练掌握命题逻辑三种推理方法熟练掌握命题逻辑三种推理方法、第二章第二章 谓词逻辑谓词逻辑1、准确掌握有关概念准确掌握有关概念、2、会命题符号化会命题符号化、(如如P60题题(2)3、掌握常用得等价公式和永真蕴涵式掌握常用得等价公式和永真蕴涵式、包括包括:带量词得公式在论域内展开式带量词得公式在论域内展开式,量词否定量词否定,量词辖域扩充量词辖域扩充,量词分配公式量词分配公式、4、会用等价公式求谓词公式得真值会用等价公式求谓词公式得真值、(如如P66题题(3)*5、会写前束范式会写前束范式6、熟练掌握谓词逻辑推理熟练掌握谓词逻辑推理、第三章第三章 集合论初步集合论初步1、集合得表示集合得表示,幂集幂集,全集全集,空集空集、2、集合得三种关系集合得三种关系(包含包含,相等相等,真包含真包含)得定义及证明得定义及证明、3、集合得五种运算及相关性质集合得五种运算及相关性质、*4、应用包含排斥原理应用包含排斥原理、第四章第四章 二元关系二元关系1、关系得概念关系得概念,表示方法表示方法、2、二元关系得二元关系得 性质得定义性质得定义,熟练掌握性质得判断及证明熟练掌握性质得判断及证明、3、掌握关系得复合掌握关系得复合,求逆及闭包运算求逆及闭包运算(计算方法及有关性计算方法及有关性质质)4、掌握等价关系得判断掌握等价关系得判断,证明证明,求等价类和商集求等价类和商集、*4、掌握相容关系定义掌握相容关系定义,简化图和简化矩阵简化图和简化矩阵,相容类相容类,最大相最大相容类容类,完全覆盖完全覆盖、5、偏序关系得判断偏序关系得判断,会画会画Hasse图图,会求一个子集得极小会求一个子集得极小(大大)元元,最小最小(大大)元元,上界与下界上界与下界,最小上界及最大下界、最小上界及最大下界、第六章第六章 函数函数1、函数得定义、函数得定义、2、函数得类型、函数得类型,会判断会判断,会证明、会证明、3、会计算函数得复合、会计算函数得复合(左复合左复合),求逆函数、知道有关性求逆函数、知道有关性质、质、*4、了解集合得特征函数、了解集合得特征函数,了解集合得基数了解集合得基数,可数集合、可数集合、第六章第六章 代数系统代数系统1、掌握运算得定义掌握运算得定义、2、熟练掌握二元运算得性质得判断及证明熟练掌握二元运算得性质得判断及证明、3、掌握代数系统得同构定义掌握代数系统得同构定义,会证明会证明、了解同构性质得保了解同构性质得保持持、4、了解半群了解半群,独异点独异点,*环和环和*域得概念域得概念、5、熟练掌握群熟练掌握群,子群子群,交换群交换群(会证明会证明),了解循环群了解循环群、*6,子群得陪集子群得陪集,Lagrange定理及其推论定理及其推论,(会应用会应用)、*第七章第七章 格与布尔代数格与布尔代数*1、掌握格得定义掌握格得定义,了解格得性质了解格得性质、*2、会判断格会判断格,分配格分配格,有补格和布尔格有补格和布尔格,*3、重点掌握两个元素得布尔代数得性质重点掌握两个元素得布尔代数得性质(10个个)、*4、会写两个元素得布尔表达式得范式会写两个元素得布尔表达式得范式、(实质是第一章实质是第一章得主析取和主合取范式得主析取和主合取范式)、第八章第八章 图论图论1、掌握图得基本概念掌握图得基本概念、(特别注意相似得概念特别注意相似得概念)2、熟练掌握图中关于结点度数得定理熟练掌握图中关于结点度数得定理、(会应用会应用)3、无向图得连通性得判定无向图得连通性得判定,连通分支及连通分支数得概念连通分支及连通分支数得概念、4、有向图得可达性有向图得可达性,强连通强连通,单侧连通和弱连通得判定单侧连通和弱连通得判定、求强求强 分图分图,单侧分图和弱分图单侧分图和弱分图、5、会求图得矩阵会求图得矩阵、6、会判定欧拉图和汉密尔顿图会判定欧拉图和汉密尔顿图、*7、会判定平面图会判定平面图,掌握欧拉公式掌握欧拉公式、*8、了解对偶图了解对偶图、9、掌握树得基本定义掌握树得基本定义,v和和e间得关系式、会画生成树间得关系式、会画生成树,会会求最求最小生成树、根树得概念小生成树、根树得概念,完全完全m叉树得公式叉树得公式,会画最优树会画最优树,*会会设计前缀码、设计前缀码、总 复 习复习重点复习重点第一章第一章 命题逻辑命题逻辑1、联结词得定义联结词得定义(含义及真值表定义含义及真值表定义)、2、会命题符号化会命题符号化、3、永真式得证明永真式得证明、4、永真蕴涵式得证明永真蕴涵式得证明,记住并能熟练应用常用公式记住并能熟练应用常用公式、5、等价公式得证明等价公式得证明,记住并能熟练应用常用公式记住并能熟练应用常用公式、6、会写命题公式得范式会写命题公式得范式,*能应用范式解决问题能应用范式解决问题、7、熟练掌握命题逻辑三种推理方法熟练掌握命题逻辑三种推理方法、第一章第一章 命题逻辑命题逻辑1 1、联结词联结词定义了六个逻辑联结词定义了六个逻辑联结词,分别是分别是:(1)否定否定“”(2)合取合取“”(3)析取析取“”(4)异或异或“”(5)蕴涵蕴涵“”(6)等价等价“”要熟练掌握这五个联结词在自然语言中所表示得含义以要熟练掌握这五个联结词在自然语言中所表示得含义以及它们得真值表得定义。及它们得真值表得定义。:否定否定 表示表示“不不”:合取合取 表示表示“不但不但,而且而且、”“并且并且”:析取析取 表示表示“或者可兼取得或或者可兼取得或”:异或异或 表示表示“或者不可兼取得或或者不可兼取得或”:蕴涵蕴涵 表示表示“如果如果,则则、”:等价等价 表示表示“当且仅当当且仅当”“充分且必要充分且必要”可以将这六个联结词看成六种可以将这六个联结词看成六种“运算运算”。联结词得定义联结词得定义(包括真值表和含义包括真值表和含义)、特别要注意特别要注意:“或者或者”得二义性得二义性,即要区分给定得即要区分给定得“或或”是是“可兼取得可兼取得或或”还是还是“不可兼取得或不可兼取得或 ”。“”得用法得用法,它既表示它既表示“充分条件充分条件”也表示也表示“必要条件必要条件”,即要弄清哪个作为前件即要弄清哪个作为前件,哪个作为后件哪个作为后件、P Q PQ PQ PQ PQ P Q F F F F T T F F T F T T F T T F F T F F TT T T T T T F 12大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流2、会命题符号化会命题符号化、例如例如 P:我有时间我有时间、Q:我上街我上街、R:我在家我在家、表示表示P是是Q得充分条件得充分条件:如果如果p,则则Q、只要只要P,就就Q、PQ 表示表示P是是Q得必要条件得必要条件:仅当仅当P,才才Q、只有只有P,才才Q、QP 如果如果P,则则Q;否则否则R、(PQ)(PR)3、永真式得证明永真式得证明、方法方法1、列真值表列真值表、(R(QR)(PQ)P 方法方法2、用公式得等价变换用公式得等价变换,化简成化简成T、例如证明例如证明(R(QR)(PQ)P是永真式是永真式、证证:上式上式(R(Q R)(PQ)P(PQP Q)(R(QR)(PQ)P (公式得否定公公式得否定公式式)(R(QR)(PQ)P)(结合律结合律)(R Q)(RR)(PP)(QP)(分配律分配律)(R Q)(QP)R QQP T(互补互补,同一律同一律)4、永真蕴涵式得证明永真蕴涵式得证明,记住常用得公式记住常用得公式、永真蕴涵式永真蕴涵式:AB是永真式是永真式,则称则称A永真蕴涵永真蕴涵B、(AB)方法方法1、列真值表列真值表、方法方法2、假设前件真假设前件真,推出后件真推出后件真、(即直接推理即直接推理)方法方法3、假设后件假假设后件假,推出前件假推出前件假、(即反证法即反证法)例证明例证明(P(QR)(PQ)(PR)是永真蕴涵式是永真蕴涵式、证证:假设后件假设后件(PQ)(PR)假假,则则PQ为为T,PR为为F,于于是是P为为T,R为为F,进而又得进而又得Q为为T、所以所以QR为为F,所以前件所以前件P(QR)为为F、所以所以(P(QR)(PQ)(PR)为为永真式永真式、对于给定一个题对于给定一个题,究竟是用哪种方法究竟是用哪种方法,原则上哪种都可以原则上哪种都可以、但是哪个方法简单但是哪个方法简单,要根据具体题而定要根据具体题而定、A B A B F F T F T T T F F T T T5、等价公式得证明等价公式得证明,记住常用得公式记住常用得公式、方法方法1、列真值表列真值表、方法方法2、用公式得等价变换用公式得等价变换、例如例如:证明证明 P(QR)(PQ)R P(QR)P(Q R)(PQ)R (P Q)R(PQ)R注意注意:不论是证明永真蕴涵式不论是证明永真蕴涵式,还是证明等价公式以及后边还是证明等价公式以及后边得求公式得范式得求公式得范式,命题逻辑推理命题逻辑推理,都应用都应用43页得公式。页得公式。必须记忆一些常用得公式必须记忆一些常用得公式 如如:P43表中得表中得永真蕴涵式永真蕴涵式:I1,I3,I9,I10,I11,I12,I13,等等 价价 公公 式式:E1 E16,E18,E19,E20,E21,6、命题公式得范式命题公式得范式1)析取范式析取范式:A1A2、An (n1)Ai(i=1,2、n)是是合取式、合取式、2)合取范式合取范式:A1A2、An (n1)Ai(i=1,2、n)是是析取式、析取式、3)析取范式与合取范式得写法、析取范式与合取范式得写法、4)小项及小项及小项得性质小项得性质、m3 m2 m1 m0 P Q PQ P Q PQ P Q 00 F F F F F T 01 F T F F T F 10 T F F T F F 11 T T T F F F6)大项及其性质大项及其性质、M0 M1 M2 M3 P Q PQ P Q PQ P Q 00 F F F T T T 01 F T T F T T 10 T F T T F T 11 T T T T T F7)主析取范式主析取范式:A1A2、An (n1)Ai(i=1,2、n)小项小项、8)主合取范式主合取范式:A1A2、An (n1)Ai(i=1,2、n)大项大项、9)、会写主析取范式和主合取范式会写主析取范式和主合取范式、求下面命题公式得范式求下面命题公式得范式:A(P,Q,R)(PQ)R方法方法1、列真值表列真值表、主析取范式主析取范式A(P,Q,R)(PQ)R(P Q R)(P QR)(PQR)(P QR)(PQR)主合取范式主合取范式A(P,Q,R)(PQ)R(P QR)(PQR)(P QR)P Q R (PQ)RF F F TF F T TF T F FF T T TT F F FT F T TT T F FT T T T方法方法2、用公式得等价变换用公式得等价变换、主析取范式主析取范式;A(P,Q,R)(PQ)R (PQ)R (P Q)R (P Q(R R)(P P)(Q Q)R)(P QR)(P Q R)(PQR)(P QR)(PQR)(P QR)(P Q R)(P QR)(PQR)(P QR)(PQR)主合取范式主合取范式:A(P,Q,R)(PQ)R (PQ)R (P Q)R(PR)(QR)(P(Q Q)R)(P P)QR)(PQR)(P QR)(P QR)已知已知A(P,Q,R)得主析取范式中含有如下小项得主析取范式中含有如下小项:m0,m3,m4,m5,m7求它得主合取范式、求它得主合取范式、解解:A(P,Q,R)得主合取范式中含有大项得主合取范式中含有大项:M1,M2,M6A(P,Q,R)(PQ R)(P QR)(P QR)*范式得应用范式得应用 如如P39习题习题(7),(8):安排工作安排工作(排课表排课表),判断比赛名次判断比赛名次,携带携带工具箱工具箱,7、会用三种推理方法会用三种推理方法,进行逻辑推理进行逻辑推理、会用三个推理规则会用三个推理规则:P,T,CP例如例如:证明证明 (AB)C)D(CD)A B1、直接推理直接推理:D P CD P C T I10 Q,(PQ)P(AB)C P (AB)T I12 Q,PQ P A B T E8 (PQ)P Q(AB)C)D(CD)A B2、条件论证条件论证:适用于结论是蕴涵式适用于结论是蕴涵式、A B ABA P(附加前提附加前提)(AB)C P A(BC)T E19 BC T I11 D P CD P C T I10 B T I12 AB CP (AB)C)D(CD)A B3、反证法反证法:(A B)P(假设前提假设前提)AB T E9(AB)C P C T I11 D P CD P C T I10C C T I9 第二章第二章 谓词逻辑谓词逻辑1、准确掌握有关概念准确掌握有关概念、2、会命题符号化会命题符号化、(如如P60题题(2)3、掌握常用得等价公式和永真蕴涵式掌握常用得等价公式和永真蕴涵式、包括包括:带量词得公式在论域内展开式带量词得公式在论域内展开式,量词否定量词否定,量词辖域扩充量词辖域扩充,量词分配公式量词分配公式、4、会用等价公式求谓词公式得真值会用等价公式求谓词公式得真值、(如如P66题题(3)*5、会写前束范式会写前束范式6、熟练掌握谓词逻辑推理熟练掌握谓词逻辑推理、第二章第二章 谓词逻辑谓词逻辑1、准确掌握有关概念准确掌握有关概念、客体客体:客体变元客体变元,谓词谓词,量词量词,量词后得指导变元量词后得指导变元,量词得辖域量词得辖域,约束变元与自由变元约束变元与自由变元,论域论域,全总个体域全总个体域,谓词公式谓词公式(WFF),命题函数命题函数,前束范式前束范式,2、会命题符号化会命题符号化、(如如P60题题(2)命题得符号表达式与论域有关。当论域扩大时命题得符号表达式与论域有关。当论域扩大时,需要添需要添加用来表示客体特性得谓词加用来表示客体特性得谓词,称此谓词为称此谓词为特性谓词特性谓词。特。特性谓词往往就是给定命题中量词后边得那个名词。如性谓词往往就是给定命题中量词后边得那个名词。如“所有自然数所有自然数、”、“有些大学生有些大学生、”。如何添加特性谓词如何添加特性谓词,这是个十分重要得问题这是个十分重要得问题,这与前边这与前边得量词有关得量词有关。如果如果前边是全称量词前边是全称量词,特性谓词后边是蕴含联结词特性谓词后边是蕴含联结词“”;如果如果前边是存在量词前边是存在量词,特性谓词后边是合取联结词特性谓词后边是合取联结词“”。另外有些命另外有些命题题里有得客体在句中没有明确得量里有得客体在句中没有明确得量词词 ,而在而在写它得符号表达式写它得符号表达式时时,必必须须把把隐隐含得量含得量词词明确得写出来明确得写出来、例如例如金子闪光金子闪光,但闪光得不一定都是金子但闪光得不一定都是金子、设设:G(x):x是金子、是金子、F(x):x闪光闪光、x(G(x)F(x)x(F(x)G(x)x(G(x)F(x)x(F(x)G(x)没有大学生不懂外语、没有大学生不懂外语、S(x):x是大学生、是大学生、F(x):x外语外语、K(x,y):x懂得懂得y、x(S(x)y(F(y)K(x,y)x(S(x)y(F(y)K(x,y)有些液体可以溶解所有固体有些液体可以溶解所有固体、F(x):x是液体、是液体、S(x):x是固体是固体、D(x,y):x可溶解可溶解y、x(F(x)y(S(y)D(x,y)每个大学生都爱好一些文体活动。每个大学生都爱好一些文体活动。S(x):x x是大学生是大学生,L(x,y):x x爱好爱好y,y,C(x):x x是文娱活动是文娱活动,P(x):x x是体育活动是体育活动、)x(S(x)y(C(y)P(y)L(x,y)3、掌握常用得等价公式和永真蕴涵式掌握常用得等价公式和永真蕴涵式、包括包括:带量词得公式在论域内展开式带量词得公式在论域内展开式,量词否定量词否定,量词辖域扩充量词辖域扩充,量词分配公式量词分配公式、设论域为设论域为aa1 1,a,a2 2,、,a,an n,则则 1)1)、xA(x)xA(x)A(aA(a1 1)A(a)A(a2 2)、A(aA(an n)2)2)、xB(x)xB(x)B(aB(a1 1)B(a)B(a2 2)、B(aB(an n)1)1)、xA(x)xA(x)x x A(x)A(x)2)2)、xA(x)xA(x)x x A(x)A(x)1)1)、xA(x)BxA(x)Bx(A(x)B)x(A(x)B)2)2)、xA(x)BxA(x)Bx(A(x)B)x(A(x)B)3)3)、xA(x)BxA(x)Bx(A(x)B)x(A(x)B)4)4)、xA(x)BxA(x)Bx(x(x)B)(x)B)5)5)、B B xA(x)xA(x)x(BA(x)x(BA(x)6)6)、B B xA(x)xA(x)x(BA(x)x(BA(x)7)7)、xA(x)BxA(x)Bx(A(x)B)x(A(x)B)8)8)、xA(x)BxA(x)Bx(A(x)B)x(A(x)B)1)1)、x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)2)2)、x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)3)3)、x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)4)4)、xA(x)xA(x)xB(x)xB(x)x(A(x)B(x)x(A(x)B(x)4、会用等价公式求谓词公式得真值会用等价公式求谓词公式得真值、(如如P66题题(3)例设论域为例设论域为1,2,A(x,y):x+y=xy,求求x yA(x,y)得真值、得真值、x yA(x,y)x y A(x,y)y A(1,y)y A(2,y)(A(1,1)A(1,2)(A(2,1)A(2,2)(T T)(T F)T*5、将下面谓词公式写成前束范式将下面谓词公式写成前束范式(xF(x,y)yG(y)xH(x,y)(xF(x,y)yG(y)xH(x,y)(去去)xF(x,y)yG(y)xH(x,y)(摩根摩根)xF(x,y)y G(y)xH(x,y)(量词否定量词否定)xF(x,z)y G(y)tH(t,z)(变元换名变元换名)x y t(F(x,z)G(y)H(t,z)(辖域扩充辖域扩充)6、熟练掌握谓词逻辑推理熟练掌握谓词逻辑推理、1)、注意使用注意使用ES、US、EG、UG得限制条件得限制条件,特别是特别是ES,UG2)、对于同一个客体变元对于同一个客体变元,既有带既有带 也有带也有带 得前提得前提,去量去量词时词时,应先去应先去 后去后去,这样这样才可以特指同一个客体才可以特指同一个客体 c、3)、去量词时去量词时,该量词必须是公式得最左边得量词该量词必须是公式得最左边得量词,且此量且此量词得前边无任何符号词得前边无任何符号,它得辖域作用到公式末尾。它得辖域作用到公式末尾。下面得作法是错误得下面得作法是错误得:正确作法正确作法:x xP P(x x)x xQ(x)P x xP P(x x)x xQ(x)P P P(c c)x xQ(x)US x xP P(x x)x xQ(x)T E或或 x xP P(x x)Q(c)ES x x P P(x x)x xQ(x)T E实际上实际上 x x得辖域扩充后得辖域扩充后 x(P P(x x)Q(x)T E 量词改成为量词改成为 x x P P(c c)Q(c)ES P P(c c)Q(c)TE下面得作法是错误得下面得作法是错误得:正确作法正确作法:x xP(x)P P(x)P x xP(x)PP(x)P P(c)US P(c)US x P(x)T E实际上实际上中量词不是中量词不是 P(c)ESP(c)ES x x而是而是 x x x x y yP(x,y)P P(x,y)P x x y yP(x,y)PP(x,y)P x xP(x,c)ES P(x,c)ES y yP(c,y)USP(c,y)US令令P(x,y):yP(x,y):y是是x x得得生母生母,显然显然是个假命题是个假命题4)、添加量词时添加量词时,也要加在公式得最左边也要加在公式得最左边,(即新加得量词即新加得量词前也无任何符号！前也无任何符号！)且其辖域作用到公式得末尾。且其辖域作用到公式得末尾。例如下面作法是错误得例如下面作法是错误得:x xP P(x x)Q(c)P x xP P(x x)y yQ(y)EG例如例如、证明下面推理得有效性证明下面推理得有效性、证明证明:x(A(x)x(A(x)D(x)D(x)P P A(a)A(a)D(a)D(a)ES ES A(a)A(a)T T I I D(a)D(a)T T I I x(x(A(x)(B(x)A(x)(B(x)C(x)C(x)P)P A(a)(B(a)A(a)(B(a)C(a)C(a)US)US B(a)B(a)C(a)C(a)T)T I I x(x(A(x)(C(x)D(x)A(x)(C(x)D(x)P)P A(a)(C(a)D(a)A(a)(C(a)D(a)US)US C(a)D(a)T I C(a)D(a)T I C(a)T I C(a)T I B(a)T IB(a)T I A(a)A(a)B(a)T IB(a)T I x(A(x)x(A(x)B(x)EG B(x)EG 第三章第三章 集合论初步集合论初步1、集合得表示集合得表示,幂集幂集,全集全集,空集空集、2、集合得三种关系集合得三种关系(包含包含,相等相等,真包含真包含)得定义及证明得定义及证明、3、集合得五种运算及相关性质集合得五种运算及相关性质、*4、应用包含排斥原理应用包含排斥原理、第三章第三章 集合论初步集合论初步基本概念基本概念:集合与元素集合与元素,子集与真子集子集与真子集,空集空集,全集全集,幂集幂集,并集并集,交集交集,相对补集相对补集(差集差集),绝对补集绝对补集(补集补集)1、集合得表示集合得表示,元素与集合得属于关系元素与集合得属于关系、集合得三种表示方法集合得三种表示方法:枚举法枚举法:一一列出集合中得元素一一列出集合中得元素、谓词描述法谓词描述法:用谓词描述集合中元素得性质用谓词描述集合中元素得性质、文氏图文氏图:用一个平面区域表示用一个平面区域表示、2、集合得三种关系集合得三种关系(被包含被包含,相等相等,被真包含被真包含)得定义及证明得定义及证明、A B x(xAxB)A=B A B B Ax(xAxB)A BA B ABx(xAxB)x(xB x A)3空集空集,全集全集,幂集幂集 空集空集:无元素得集合无元素得集合、x是矛盾式、是矛盾式、(空集是唯一空集是唯一得得)全集全集E:包含所讨论所有集合得集合包含所讨论所有集合得集合、(全集不唯一全集不唯一)xE是永真式是永真式 幂幂 集集:由由A得所有子集构成得集合、得所有子集构成得集合、P(A)=X|X A|P(A)|=2|A|4、掌握集合得五种运算及相关性质掌握集合得五种运算及相关性质、AB=x|xAxB xAB xAxB AB=x|xAxB xAB xAxB A-B=x|xAx B xA-B xAx B A=E-A=x|xEx A=x|x A xAx A A-B=A BA B=(A-B)(B-A)=x|(xAx B)(xBx A)A B=(AB)-(AB)例例1、已知全集已知全集E=,A E,计算计算:a)P()P()=()b)P(A)P(A)=()c)P(E)-P()=()解解:a)因为任何集合因为任何集合A,都有都有 A A=所以所以 P()P()=b)因为因为 A A,即即P(A)P(A)所以所以 P(A)P(A)=c)P(E)=,=P()=P()=,P(E)-P()=,-,=,例例2 证明各式彼此等价。证明各式彼此等价。PQ(PQ)(P Q)c)AB=B,AB=A,A B,B A、证明证明、AB=B x(xAB xB)x(x AB xB)(xAB x B)x(x A x B)xB)(xA xB)x B)x(x A x B)xB)x(x A xB)(x B xB)x(x A xB)x(xAxB)A Bx(xAxB)x(x Bx A)x(xBxA)B A 由由 AB=B 得得 A (AB)=A B A=A B 类似由类似由AB=A,可以推出可以推出AB=B 所以所以 AB=B AB=A 从而证得从而证得AB=B,AB=A,A B,B A 彼此等价。彼此等价。T例例3 证明证明:(A-B)-C=A-(BC)方法方法1、(A-B)-C=(A B)C=A(B C)=A(BC)=A-(BC)方法方法2、任取、任取x(A-B)-C(xAx B)x CxA(x Bx C)xA(xBxC)xA(xBC)xAx BC xA-(BC)所以所以(A-B)-C=A-(BC)例例4、令全集令全集E为信息学院得学生得集合为信息学院得学生得集合,C表示计算机专表示计算机专 业学生得集合业学生得集合,M表示学习了离散数学得学生得集合表示学习了离散数学得学生得集合,D表表示学习了数据结构课学生得集合示学习了数据结构课学生得集合,F表示一年级得学生得表示一年级得学生得集合、用集合得关系式表达下面句子、集合、用集合得关系式表达下面句子、“学习了离散数学和数据结构课得学生学习了离散数学和数据结构课得学生,一定是计算机一定是计算机专业得非一年级得学生专业得非一年级得学生”、解、解、(MD)(CF)例例4、在什么条件下在什么条件下,下面命题为真？下面命题为真？a)(A-B)(A-C)=A解、解、(A-B)(A-C)=(AB)(AC)=A(BC)=A(BC)=A-(BC)=A 所以满足此式得充要条件是所以满足此式得充要条件是:ABC=b)(A-B)(A-C)=解、解、(A-B)(A-C)=A-(BC)=充要条件是充要条件是:A BCc)(A-B)(A-C)=解、解、(A-B)(A-C)=(AB)(AC)=A(BC)=A(BC)=A-(BC)=充要条件是充要条件是:A BCd)(A-B)(A-C)=解、解、因为因为 当且仅当当且仅当A=B,才有才有A B=所以满足此式得充要条件是所以满足此式得充要条件是:A-B=A-C*例例5、用谓词逻辑推理证明用谓词逻辑推理证明对任何集合对任何集合A、B、C,如果有如果有A B且且 B C,则则A C。证明证明:x(xAxB)x(xB x A),x(xBxC)x(xC x B)x(xAxC)x(xC x A)x(xAxB)x(xB x A)P x(xAxB)T I x(xB x A)T I x(xBxC)x(xC x B)P x(xBxC)T I xAxB US xBxC US xAxC T I x(xAxC)UG xB x A ES xB T I x A T I xC T I xC x A T I x(xC x A)EG x(xAxC)x(xC x A)T I*有有14位学生参加考试位学生参加考试,9位同学数学得了优位同学数学得了优;5位同学物理位同学物理得了优得了优;4位同学化学得了优位同学化学得了优;其中物理和数学都得优得同其中物理和数学都得优得同学有学有4人人;数学和化学都得优得同学有数学和化学都得优得同学有3人人;物理和化学都得物理和化学都得优得同学有优得同学有3人人;三门都得优得同学有三门都得优得同学有2人人;问没有得到优得问没有得到优得有多少人有多少人?恰有两门得优得同学有多少人恰有两门得优得同学有多少人?解解、令令A、B、C分别表示数学、物理、化学得优同学集分别表示数学、物理、化学得优同学集合合、全集为全集为E、于是有于是有|E|=14|A|=9|B|=5|C|=4|AB|=4|AC|=3|BC|=3|ABC|=2|ABC|=|A|+|B|+|C|-|AB|-|BC|-|BC|+|ABC|=9+5+4-4-3-3+2=10 于是得到优得人数是于是得到优得人数是10人人、没有得到优得人数是没有得到优得人数是:14-10=4 人人恰有两门得优得人数恰有两门得优得人数:(|AB|-|ABC|)+(|BC|-|ABC|)+(|BC|-|ABC|)=4-2+3-2+3-2=4 第四章第四章 二元关系二元关系1、关系得概念关系得概念,表示方法表示方法、2、二元关系得二元关系得 性质得定义性质得定义,熟练掌握性质得判断及证明熟练掌握性质得判断及证明、3、掌握关系得复合掌握关系得复合,求逆及闭包运算求逆及闭包运算(计算方法及有关性计算方法及有关性质质)4、掌握等价关系得判断掌握等价关系得判断,证明证明,求等价类和商集求等价类和商集、*5、掌握相容关系得概念掌握相容关系得概念,关系图和矩阵得简化关系图和矩阵得简化,求相容类求相容类,最大相容类和完全覆盖最大相容类和完全覆盖、6、偏序关系得判断偏序关系得判断,会画会画Hasse图图,会求一个子集得极小会求一个子集得极小(大大)元元,最小最小(大大)元元,上界与下界上界与下界,最小上界及最大下界、最小上界及最大下界、注意本章证明题得证明过程得思路注意本章证明题得证明过程得思路一一、关系得概念关系得概念,表示方法表示方法,三个特殊关系三个特殊关系、1、集合得笛卡集合得笛卡 尔尔 积积 AB=|xAyB|A|=m,|B|=n|A|A|=m,|B|=n|AB|=mnB|=mn 设设A=0,1,B=a,b,求求A B。A B=,2、二二元关系得概念元关系得概念定义定义1:设设A、是集合、是集合,如果如果 AB,则称则称R是一个从是一个从A到到 B得二元关系。如果得二元关系。如果 R AA,则称则称R是是A上得二元上得二元关系关系、如果如果|A|=m|B|=n 则可以确定则可以确定2mn个从个从A到到B得不同关系、得不同关系、定义定义2:任何序偶得集合任何序偶得集合,都称之为一个二元关系。都称之为一个二元关系。3 3、关系得表示方法关系得表示方法1)1)、枚举法枚举法:即将关系中所有序偶一一列举出即将关系中所有序偶一一列举出,写在大括号内写在大括号内、如如:R=,2)2)、(描述法描述法)谓词公式法谓词公式法:即用谓词公式描述序偶中元素得关系。例如即用谓词公式描述序偶中元素得关系。例如 R=|xy3)3)、有向图法有向图法:1。2。3。4。ABabcR1:1。4。23R2:4)、矩阵表示法:(实际上就是图论中得邻接矩阵实际上就是图论中得邻接矩阵)设设A=a1,a2,am,B=b1,b2,bn是个有限集是个有限集,R AB,定义定义R得得mn阶阶矩阵矩阵 MR=(rij)mn,其中其中4、三个特殊关系三个特殊关系1)、空关系空关系:AB,(或或 AA),即无任何元素得关系即无任何元素得关系、它得关系图中只有结点它得关系图中只有结点,无任何边无任何边;它得矩阵中全是它得矩阵中全是0。2)、完全关系完全关系(全域关系全域关系):AB(或或AA)本身是一个从本身是一个从A到到B(或或A上上)得完全关系得完全关系、即含有全部序偶得关系。它得矩阵中全是即含有全部序偶得关系。它得矩阵中全是1。1 若若R 0 若若R(1im,1jn)rij=3)、恒等关系恒等关系IA:IA AA,且且IA=|xA称之为称之为A 上得恒等关系。上得恒等关系。例如例如A=1,2,3,则则IA=,A上得上得、完全关系、完全关系AA及及IA得关系图及矩阵如下得关系图及矩阵如下:MIA=1 0 00 1 00 0 1331。2。31。2。31 1 11 1 11 1 1331。2。30 0 00 0 00 0 033M=MAA=AAIA二二、关系得性质关系得性质:熟练掌握性质得判断及证明熟练掌握性质得判断及证明、1、自反性自反性定义定义:设设R是集合是集合A中得关系中得关系,如果对于任意如果对于任意xA都有都有 R(xRx),则称则称R是是A中自反关系。即中自反关系。即 R是是A中自反得中自反得x(x AxRx)2、反自反性反自反性定义定义:设设R是集合是集合A中得关系中得关系,如果对于任意得如果对于任意得xA都有都有 R,则称则称R为为A中得反自反关系。即中得反自反关系。即 R是是A中反自反得中反自反得x(x A R)3、对称性对称性定义定义:R是集合是集合A中关系中关系,若对任何若对任何x,yA,如果有如果有xRy,必有必有 yRx,则称则称R为为A中得对称关系。中得对称关系。R是是A上对称得上对称得x y(x A y A xRy)yRx)4、反对称性反对称性定义定义:设设R为集合为集合A中关系中关系,若对任何若对任何x,yA,如果有如果有xRy,和和 yRx,就就有有x=y,则称则称R为为A中反对称关系中反对称关系。R是是A上反对称得上反对称得x y(x A y A xRy yRx)x=y)x y(x A y A x y R)R)5、传递性传递性定义定义:R是是A中关系中关系,对任何对任何x,y,zA,如果有如果有xRy,和和yRz,就就 有有xRz,则称则称R为为A中传递关系。中传递关系。即即R在在A上传递上传递 x y z(x A y A z A xRy yRz)xRz)这这些性些性质质要求会判断要求会判断,会会证证明明、这这里特里特别别要注意得是要注意得是,这这些定些定义义都是都是蕴蕴涵式涵式,所以当所以当蕴蕴涵涵式当前件式当前件为为假假时时,此此蕴蕴涵式涵式为为真真,即此性即此性质质 成立成立!自反性自反性反自反性反自反性对称性对称性传递性传递性反对称性反对称性每个结点都有环每个结点都有环 主对角线全是主对角线全是1每个结点都无环每个结点都无环 主对角线全是主对角线全是0不同结点间如果有边不同结点间如果有边,则有方向相反的两条则有方向相反的两条边边.是以对角线为对称是以对角线为对称 的矩阵的矩阵不同结点间不同结点间,最多有一最多有一条边条边.以主对角线为对称以主对角线为对称的位置不会同时为的位置不会同时为1如果有边如果有边,则也有边则也有边.或者使得前件为假或者使得前件为假.如果如果aij=1,且且ajk=1,则则aik=1从关系得矩从关系得矩阵阵从关系得有向从关系得有向图图 性性质质判定判定:判断下面关系得性质判断下面关系得性质:1。2。1。2。1。2。1。2。3333R2R1R3R4自反性自反性 反自反性反自反性 对称性对称性 反对称性反对称性 传递性传递性 R1 Y N N Y Y R2 N Y N Y N R3 Y N Y N Y R4 Y N Y Y Y 1。2。1。2。1。2。1。2。3333R5R6R7R8自反性自反性 反自反性反自反性 对称性对称性 反对称性反对称性 传递性传递性 R5 N Y N Y Y R6 N N Y N N R7 N N N N N R8 N Y Y Y Y 关系性质当证明方法归纳关系性质当证明方法归纳:设设R是是A上关系上关系,1 1、证明证明R R得自反性得自反性:方法方法1 用自反定义证