《《离散数期末复习》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《离散数期末复习》PPT课件.ppt（56页珍藏版）》请在金锄头文库上搜索。
1、离散数学期末复习大纲数理逻辑部分以判定推理为主：包括对给定合式公式属性的判定及熟练使用条规则进行有效推理。关系函数部分：以关系的基本概念、关系性质的形式化描述，等价关系和划分，偏序关系和哈斯图。函数掌握特种函数，满射、单射、双射函数相关的证明。代数系统部分：掌握代数系统的基本概念，包括子代数，代数系统的同态、同构，积代数和商代数的求法等，特殊代数系统掌握群相关的内容，如何求子群等。图论部分掌握图的基本概念，图的矩阵表示及矩阵携带的信息，重点掌握树相关的概念。平时成绩占分。针对各部分所做的练习。、求下列公式的主范式，并判定公式的属性。例1.1(pqr)(pqr)(pq)解：上式=(pqr)(pq
2、r)(pq)(r r)=(pqr)(pqr)(pqr)(pqr)=m7, m3, m1,m0其中表示析取。该公式含三个变元，与其等价的主析取范式四项，所以它是可满足的。例1.2 (p(qr)(p (q r)解：上式 (p(qr) (p(qr)= (pq)(pr)(pq)(pr)= (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr)=M4,M5, M6,M2, M3,M1其中表示合取。该公式是可满足的。 例1.3刚进入大学的小张与寝室里的其他三人聊天，这三个人根据小张的口音分别作出下述判断：甲说：小张不是苏州人，是上海人。乙说：小张不是上海人，是苏州人。丙说：
3、小张既不是上海人，也不是杭州人。小张听后，笑曰：你们三人有一人全说对了，有一人全说错了，还有一人对错各半。试用命题逻辑推断小张究竟是哪里人。解：首先符号化：设：小张是苏州人：小张是上海人：小张是杭州人根据题意有：甲：PQ,乙： Q P,丙： Q R分析小张只可能是其中一个城市的人或者不是这三个城市的人。 根据甲乙丙三人的说话内容可以判断：丙至少说对了一半，因此甲或乙必有一人全错了。若甲全错了，则有Q P即乙全对了。若乙全错了，则甲全对。所以丙必是一对一错。将小张的话符号化为：(PQ) (QR)(QR)(QP)(QR) (QR)T化简得：(PQR) ( PQR)小张不可能既是苏州人又是杭洲人，所
4、以只能是上海人。例1.4甲乙丙丁人中仅有两个人代表单位参加了市里的桥牌比赛，关于谁参加比赛，下列种说法都是正确的：甲和乙两人中有一人参加；若丙参加，则丁必参加；乙和丁两人中至多参加一人；若丁不参加，则甲也不参加。试判断哪两个人参加了比赛。解：符号化命题如下：设：甲参加了比赛；：乙参加了比赛：丙参加了比赛：丁参加了比赛依题意将1,2,3,4分别符号化为：(AB)(AB) (CD)(BD)(DA) T将上式化为主析取范式应有24=16个极小项即m0000, m0001, m0010, m0011, m0100, m0101,m0110, m0111, m1000, m1001, m1010, m1
5、011, m1100,m1101, m1110, m1111根据题意去掉不合法的得到的结论是甲和丁参加了比赛。例1.5当p，q，r，s四个人考试成绩出来后，有人问四个人中谁的成绩最好，p说“不是我”，q说“是s”，r说是“q”，s说“不是我”。四个人的回答只有一个人符合实际，问哪一位的成绩最好。若有两人成绩并列最好，是谁？解：令p: p的成绩最好；q：q的成绩最好；r：r的成绩最好；s：s的成绩最好。若只有p回答正确： p s q s若只有q回答正确： p s q s若只有r回答正确： p s q s若只有s回答正确： p s q s由于(p s q s) ( p s q s) ( p s q
6、 s) ( p s q s)= (p q s) (p q s)=(p q r s) (p q r s) (p q r s) (p q r s) 若只有一个人成绩最好，必是p q r s为真，即p成绩最好；若有两个人成绩并列最好，可能是p,s或者p,r练习：利用主范式判断下式的类型(pq) (qr) (p q) r)结果= M4,M6,M2该公式是可满足的、对下面的问题首先符号化，然后使用条规则进行有效推理证明。2.1每一个自然数不是奇数就是偶数，自然数是偶数当且仅当它能被2整除，并不是所有的自然数都能被2整除。因此，有的自然数是奇数。解法1：首先定义如下谓词：N(x):x是自然数Q(x):x是
7、奇数E(x):x是偶数I(x):x能被2整除于是问题可用符号表述为：(x)(N(x)(Q(x)E(x),(x)(N(x) E(x) I(x), (x)(N(x) I(x)，(x)(N(x) Q(x)推理证明过程如下：1 (x)(N(x) I(x) P规则2 (x)(N(x) I(x) T规则和13 N(a) I(a) ES规则和24 N(a) T规则和35 I(a) T规则和36 (x)(N(x)(Q(x)E(x) P规则7 N(a)(Q(a)E(a) US规则和 8 Q(a)E(a) T规则和9 (x)(N(x) E(x) I(x) P规则10 (N(a) E(a) I(a) US规则和 1
8、1 (N(a) E(a) T规则5和1012 N(a)E(a) T规则和1113 E(a) T规则4和1214 Q(a) T规则8和1315 N(a)Q(a) T规则4和1416(x)(N(x) Q(x) EG规则和15问题得证。解法2：采用反证法。证明过程如下1(x)(N(x) I(x)P规则2(x)(N(x) I(x) T规则和13 N(a) I(a) ES规则和24 N(a) T规则和35 I(a) T规则和36 (x)(N(x) Q(x) P规则(假设前提)7 (x)( N(x) Q(x) T规则和68 N(a) Q(a) US规则和9 Q(a) T规则和8 10 (x)(N(x)(Q
9、(x)E(x)P规则11 N(a)(Q(a)E(a) T规则和1012 Q(a)E(a) T规则4和1113 E(a) T规则9和12 14 (x)(N(x) E(x) I(x)P规则15 (N(a) E(a) I(a) US规则和14 16 N(a) E(a) T规则4和1317 I(a) T规则15和1618 I(a) I(a) T规则5和1719(x)(N(x) Q(x) F规则6和18问题得证 例2.2天鹅都会飞，而癞蛤蟆不会飞；所以癞蛤蟆不是天鹅。解：令TE(x):x是天鹅l(x):x是癞蛤蟆F(x):x会飞于是问题可符号化为：(x)(TE(x) F(x), (x)(l(x) F(x
10、)(x)(l(x) TE(x).证明过程如下：1(x)(l(x) TE(x) P规则(假设前提)2(x)(l(x) TE(x) T规则和3 l(a) TE(a) ES规则24 l(a) T规则35 TE(a) T规则36 (x)(TE(x) F(x) P规则7 TE(a) F(a) US规则和68 F(a) T规则5和79 (x)(l(x) F(x) P规则10 l(a) F(a) US规则和911 F(a) l(a) T规则和1012 l(a) T规则8和1113 l(a) l(a) T规则4和1214 (x)(l(x) TE(x) F规则和13问题得证。 例2.3 所有牛都有角，有些动物是
11、牛，所以有些动物有角解：设(x):x是牛(x):x有角 A(x):x是动物于是问题可描述成：(x)(x) (x),(x)(A(x)(x) (x)(A(x)(x)证明：、(x)(A(x)(x)P规则、A(a)(a) ES规则和、 A(a)T规则和、(a) T规则和、(x)(x) (x) P规则、(a) (a) US规则和、(a) T规则和、 A(a)J(a) T规则3和7、(x)(A(x)(x)EG规则和求解这一类问题时注意：把实际问题符号化时，全称量词对应逻辑联结词“”，存在量词对应逻辑联结词“”；推论时保证ES规则的首先使用。使用UG规则时，由ES规则引入的客体不能进行推广，即不能加全称量词
12、。请对39页上的第3题再做一次练习。、关系是笛卡尔积的子集，因此关系是集合，是以序偶为元素的集合。关系可以用关系图和关系矩阵来表示。关系是集合，所以集合上的运算可以平移到关系上来，但关系还有自己独特的运算：求逆运算，复合运算(也叫关系的合成运算)，关系的闭包运算等。设为X到Y的二元关系,S为Y到Z的二元关系：RoS=|(z)RSr(R)=RIxs(R)=RRt(R)= i=1nRi关系的性质：1) R是自反的(x)(xXR)2) R是反自反的(x)(xXR)3) R是不自反的(x)(y)(x,yXRR)4) R是对称的(x)(y)(x,yX R R)5) R是反对称的=(x)(y)(x,yXR
13、 Rx=y) 6) 是不对称的=(x1)(y1)(x2)(y2)(x1,y1,x2,y2XR R RR)7) R是可传递的=(x)(y)(z)(x,y,z XRRR)8) R是不可传递的=(x)(y)(z)(x,y,zRRRR) 空关系空关系vs空集上的关系空集上的关系空关系：对于任何集合空关系：对于任何集合A, 称空集为称空集为A上的空关系上的空关系.性质：若性质：若A非空，空关系是反自反的，对称的，反非空，空关系是反自反的，对称的，反对称的，可传递的；对称的，可传递的；若若A是空集，该空关系是自反的，反自反的，对称是空集，该空关系是自反的，反自反的，对称的，反对称的，可传递的的，反对称的，
14、可传递的空集上的关系：自反的，反自反的，对称的，反对称的，空集上的关系：自反的，反自反的，对称的，反对称的， 可传递的。在空集上可定义任意元关系。可传递的。在空集上可定义任意元关系。3-1设A=1,2,3,R是(A)上的二元关系，且R=|a,b(A),ab,则R不满足下列哪些性质？为什麽？1)自反性2)反自反性3)对称性4)反对称性5)传递性解：1)因为(A)，但所以R，即不满足自反性。2)因为1(A)但11=1即R，因此不是反自反的3)对任意x,y(A),若xy,即R,则yx即R即R满足对称性。 4)取x=1,2,y=1,3显然xy=1=yx即存在x,y并且RR但xy即不是反对称的。5)存在
15、x=1,y=1,2,z=2并且x,y,z(A)RR但R即R不满足可传递性。3-2设S为集合A上的二元关系，证明S是自反的，传递的，则SoS=S。其逆为真吗？证明：关系是序偶为元素的集合，所以我们可以把证集合相等的方法用到证关系的相等上来。即证SoSSSSoS即证明了SoS=S。对任意x,y,zA和SoS,由复合关系的定义知应有S和S,而S是可传递的，于是S,由x,z的任意性知SoSS，又是自反的和传递的，所以对任何S和S应有SoS即SSoS,于是有SoS=S。其逆不一定为真，例如设A=1,2,3S=,我们做的关系矩阵如下： 1 2 3 1 1 1 0Ms= 2 0 1 0 30 0 0于是MS
16、oS= Ms Ms= 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 = 0 1 0 = Ms 0 0 0显然不是自反的，主对角线不全是。 例3-3 设R是复数集合C上的关系，定义如下：R=| x,y C 且x-y=a+bi，其中，a,b均为非负整数试确定R的性质，并说明原因。解: (1)对于任意xC，因为x-x=0+0i，所以 R，因此R是自反的；(2)由(1)知, R，因此R不具有反自反性；(3) 取x=3+2i, y=2+i，此时x-y=1+i， R，但是y-x=-1+(-1)i，不属于R，因此R不是对称的；(4)任取x,y C，若 R且 R，x-y=
17、 a+bi, y-x=-a+(-b)i，则a,b,-a,-b都必须是非负整数，于是a=b=0，因而，x=y。R是反对称的。(5)对于任意的x,y,z C，若 R且 R，则x-y=a+bi(a和b都是非负整数), y-z=c+di(c,d都是非负整数)，于是x-z= (x-y)+(y-z)=(a+c)+(b+d)i，由于a+c,b+d都是非负整数，因此 R.由x,y,z取值的任意性可知，R是可传递的。故R具有自反性、反对称性、可传递性。3-4确定三角形之间的相似关系具有哪些性确定三角形之间的相似关系具有哪些性质。质。解：自反性、对称性、可传递性。3-5设R和S是集合Aa, b, c, d上的关系
18、，其中R, S,. 计算RS, RS, R1, S1R1 解法： RS=, RS= , R1=, S1R1=,解法2通过矩阵求 a b c d a 1 0 1 0 b 0 0 1 0MR= c 0 0 0 1 d 0 0 0 0 a b c d a 0 1 0 0 b 0 0 1 1 Ms= c 0 0 0 0 d 0 0 0 1RS= MR Ms= 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 = 0 0 0 0 0 0 0 1 0 0 0 0 RS= MR Ms= 1 0 1 0 0 1 0
19、0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 = 0 0 1 1 0 0 0 1 0 0 0 1R1=(MR)T= 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0S1=(MS)T= 0 1 0 0 0 1 0 1 S1R1 = MS1MR1 = 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0= 1 0 0 0 0 0 0 0 0 0 1 03-6 设设R和和S分别是集合分别是集合A和
20、集合和集合B上的等价关系，上的等价关系，令令T=,| R , S试证明：试证明：T是是AB上的等价关系。上的等价关系。证明： (1)任取AB，由于R和S是等价关系，因此，R, S，于是,T，于是T是自反的；(2) 任取,AB，若,T，则R , S，由于R和S都是等价关系，因此R，S，于是可得,T。由,的任意性可知，T是对称的；(3) 任取,AB，若,T且,T，则R , S，R , S。由于R和S是可传递的，因此R , S。于是可得,T。由,的任意性可知，T是可传递得。综上所述，T是AB上的等价关系。 3-7 设设A=a,b,c,d，R=,IA，(1)验证R是A上的等价关系；(2)求出商集A/R
21、。解： (1) 由于IAR，因此任取xA，R，R是自反的；由于R=RT，因此R是对称的；由于R, R,R, R; R, R, R,R，因此R是可传递的。因此R是A上的等价关系。(2)由于aR=a,c=cR, bR=b,d=dR, 因此A/R=aR,bR=a,c,b,d。3-8 设设R是偏序关系，指出下列运算后的关系是否是偏序关系，指出下列运算后的关系是否是偏序关系。是偏序关系。RS, RS, R-S, RS,RS解：(1)取A=a,b, R=, S=,，则R和S都是A上的偏序关系，而RS=, 不是反对称的， RS不是A上的偏序关系。(2)任取x A, 由R和S是偏序关系，知 R, S,因此 R
22、S, RS是自反的；任取x,y A, 若 RS, 且 RS，则 R, S, R, S，因为R和S都是反对称的，因此x=y，于是RS是反对称的；(2)（续）任取x,y,z A, 若 RS, 且 RS，则 R, S, R, S，因为R和S都是可传递的，因此 R, S，于是 RS, RS是可传递的。综上所述， RS是A上的偏序关系。(3)例子同(1)，R-S=，不具有自反性，因此R-S不是A上的偏序关系。(4)例子同(1)，RS=,，不具有自反性和反对称性，因此RS不是A上的偏序关系。(5)取A=a,b,c, R=,IA,S= , IA,则R和S都是A上的偏序关系，而RS=,，不具有反对称性，因此R
23、S不是A上的偏序关系。3-93-9设有函数设有函数f: II(I表示整数集表示整数集)，定义为，定义为f(x)=|x|-2x，试问，试问 f 是否为内射是否为内射(即单射即单射)，满射或双射？满射或双射？ 解：根据f的定义当x=0时，f(0)=0-0=0当x0时，f(x)=x-2x=-x (0)当x0)因此，有如下对应关系：x: -3 -2 -1 0 1 2 f(x): 9 6 3 0 -1 -2 可知f是内射，不是满射，不是双射。3-10 设有函数设有函数g: AB, h: AB，函数，函数f: BC，已知，已知fg=fh，且，且f是单射，试证明是单射，试证明g = h。证明：任取xA，令g
24、(x)=b1, h(x)=b2，则fg=f(b1), fh=f(b2)。由fg=fh可知，f(b1)=f(b2)。因为f是单射，因此b1=b2，即g(x)=h(x)。由x取值的任意性可知，g = h3-11 设有函数设有函数f: AB和和g: BC，使得，使得gf是一个是一个单射，且单射，且f是满射。证明是满射。证明g是一个单射。举出一个是一个单射。举出一个例子说明，若例子说明，若f不是满射，则不是满射，则g不一定是单射。不一定是单射。证明：任取b1,b2B，并设b1b2，因为f是满射，因此一定存在a1,a2A，使得f(a1)=b1, f(a2)=b2。由于b1b2，由函数的定义知a1a2。又
25、因为g是由B到C的函数，所以一定有c1,c2C，使得g(b1)=c1, g(b2)=c2。于是，gf(a1)=g(b1)=c1, gf(a2)=g(b2)=c2。因为gf是单射，且a1a2，因此c1c2，也就是g(b1)g(b2)。由b1,b2取值的任意性知，g是单射。举例如下：当f不是满射时，g不一定是单射。3-12设Aa,b,c,d,e，回答下列问题，并说明理由：1)A上共有多少种二元关系？2)上述二元关系中有多少个是等价关系？解1)A上的二元关系是AxA的子集，而 AxA的基数25，所以上有225种不同的二元关系。解2)等价关系和划分相对应，对于的划分有下面几种情形：(1)分成块的一种，
26、每块只含一个元素(2)分成块，其中一块含有个元素，另3块均含有个元素有：C52=10种(3)分成3块，其中2块含有2个元素,另一块含有1个元素有(1/2)C51 C42=15种分成3块，其中1块含有3个元素，另2块含有1个元素，共有C53=10种(4)分成2块，其中1块含有3个元素，另一块含有2个元素，共有C53=10种分成2块，其中1块含有4个元素，另一块含有个元素，共有C51=5种(5)分成1块，共有种。综上,A上的等价关系共有：1+10+15+10+10+5+1=52种3-13设A为含有n个元素的集合，则A上有多少个不同的等价关系？其中秩为2的划分有多少种？解：A上有多少种划分就有多少种
27、等价关系，令A上秩为i的划分的个数为f(i),则A上就共有：ni=1f(i)其中f(k)=(1/k!)(Cnt1Cn-t1t2Cn-t1-t2t3Cn-t1-t2tktk-1t1+t2+tk=nA上秩为2的划分共有(1/2)i=1n-1Cni=2n-1-13-14设f:AB的映射，指出满射和单射的条件及相应的个数：解：满射的条件是|A|B| 单射的条件是|B|A|设A中有m个元素，B中有n个元素，则m=n时，存在AB的双射函数n!个mn时，存在AB的满射函数个数为简单的求满射函数个数解题过程简单的求满射函数个数解题过程说明：m表示定义域A中元素的个数，n表示陪域B中元素的个数。思路：在所有映射
28、中刨除没有映满的情形。所有映射的总数为：nm个 未映满总数为：未映满可分为n-1种情况，即映满1个，映满2个等直到映满n-1个。所以未映满总数为n-1种情况的和。3-15 偏序集偏序集的哈斯图如下图，的哈斯图如下图，(1) 求集合求集合A的最大元素、最小元素、极大元素和的最大元素、最小元素、极大元素和极小元素极小元素(2) 求子集求子集b,c,d的上界、下界、上确界和下确界。的上界、下界、上确界和下确界。解： (1) 集合A的最大元素是a, 最小元素不存在，极大元素是a，极小元素为d和e；(2)子集b,c,d的上界是a，下界是d，上确界是a，下确界是d。 3-16 画出集合画出集合A=2,5,8,10,16,40上整除关系的上整除关系的hash图，并找出图，并找出A的最大成员、最小成员、极大成的最大成员、最小成员、极大成员、极小成员。员、极小成员。解：没有最大成员，也没有最小成员。极大成员是16，40，极小成员是2，5
