电大《离散数学》期末复习模拟试题及参考答案资料小抄.doc

电大离散考试模拟试题及答案一、填空题 1 设集合A,B，其中A1,2,3, B= 1,2, 则A - B_; r(A) - r(B) _ .2. 设有限集合A, |A| = n, 则 |r(A×A)| = _.3. 设集合A = a, b, B = 1, 2, 则从A到B的所有映射是_ _, 其中双射的是_.4. 已知命题公式GØ(P®Q)R，则G的主析取范式是_.5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为_，分枝点数为_.6 设A、B为两个集合, A= 1,2,4, B = 3,4, 则从AÇB_; AÈB_;AB _ .7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是_, _, _.8. 设命题公式GØ(P®(QÙR)，则使公式G为真的解释有_，_, _.9. 设集合A1,2,3,4, A上的关系R1 = (1,4),(2,3),(3,2), R1 = (2,1),(3,2),(4,3), 则R1·R2 = _,R2·R1 =_,R12 =_.10. 设有限集A, B，|A| = m, |B| = n, 则| |r(A´B)| = _.11 设A,B,R是三个集合，其中R是实数集，A = x | -1x1, xÎR, B = x | 0x < 2, xÎR,则A-B = _ , B-A = _ , AB = _ , .13. 设集合A2, 3, 4, 5, 6，R是A上的整除，则R以集合形式(列举法)记为_ _. 14. 设一阶逻辑公式G = "xP(x)®$xQ(x)，则G的前束范式是_ _.15.设G是具有8个顶点的树，则G中增加_条边才能把G变成完全图。16. 设谓词的定义域为a, b,将表达式"xR(x)$xS(x)中量词消除，写成与之对应的命题公式是_.17. 设集合A1, 2, 3, 4，A上的二元关系R(1,1),(1,2),(2,3), S(1,3),(2,3),(3,2)。则R×S_, R2_.二、选择题1 设集合A=2,a,3,4，B = a,3,4,1，E为全集，则下列命题正确的是( )。(A)2ÎA (B)aÍA (C)ÆÍaÍBÍE (D)a,1,3,4ÌB.2 设集合A=1,2,3,A上的关系R(1,1),(2,2),(2,3),(3,2),(3,3)，则R不具备( ).(A)自反性(B)传递性(C)对称性(D)反对称性1234563 设半序集(A,)关系的哈斯图如下所示，若A的子集B = 2,3,4,5,则元素6为B的( )。(A)下界 (B)上界(C)最小上界 (D)以上答案都不对4 下列语句中，( )是命题。(A)请把门关上 (B)地球外的星球上也有人 (C)x + 5 > 6 (D)下午有会吗？5 设I是如下一个解释：Da,b, 则在解释I下取真值为1的公式是( ).(A)$x"yP(x,y) (B)"x"yP(x,y) (C)"xP(x,x) (D)"x$yP(x,y).6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( ).(A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6).7. 设G、H是一阶逻辑公式，P是一个谓词，G$xP(x), H"xP(x),则一阶逻辑公式G®H是( ).(A)恒真的 (B)恒假的 (C)可满足的 (D)前束范式.8 设命题公式GØ(P®Q)，HP®(Q®ØP)，则G与H的关系是( )。(A)GÞH (B)HÞG (C)GH (D)以上都不是.9 设A, B为集合，当( )时ABB.(A)AB(B)AÍB(C)BÍA(D)ABÆ.10 设集合A = 1,2,3,4, A上的关系R(1,1),(2,3),(2,4),(3,4), 则R具有( )。(A)自反性 (B)传递性(C)对称性 (D)以上答案都不对11 下列关于集合的表示中正确的为( )。(A)aÎa,b,c (B)aÍa,b,c(C)ÆÎa,b,c (D)a,bÎa,b,c12 命题"xG(x)取真值1的充分必要条件是( ).(A) 对任意x，G(x)都取真值1. (B)有一个x0，使G(x0)取真值1. (C)有某些x，使G(x0)取真值1. (D)以上答案都不对.13. 设G是连通平面图，有5个顶点，6个面，则G的边数是( ).(A) 9条 (B) 5条 (C) 6条 (D) 11条.14. 设G是5个顶点的完全图，则从G中删去( )条边可以得到树.(A)6 (B)5 (C)10 (D)4.15. 设图G的相邻矩阵为，则G的顶点数与边数分别为( ).(A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8.三、计算证明题1.设集合A1, 2, 3, 4, 6, 8, 9, 12，R为整除关系。(1) 画出半序集(A,R)的哈斯图；(2) 写出A的子集B = 3,6,9,12的上界，下界，最小上界，最大下界；(3) 写出A的最大元，最小元，极大元，极小元。2. 设集合A1, 2, 3, 4，A上的关系R(x,y) | x, yÎA 且 x ³ y, 求 (1) 画出R的关系图；(2) 写出R的关系矩阵.3. 设R是实数集合，s,t,j是R上的三个映射，s(x) = x+3, t(x) = 2x, j(x) x/4,试求复合映射st，ss, sj, jt，sjt.4. 设I是如下一个解释：D = 2, 3, abf (2)f (3)P(2, 2)P(2, 3)P(3, 2)P(3, 3)32320011试求 (1) P(a, f (a)P(b, f (b);(2) "x$y P (y, x).5. 设集合A1, 2, 4, 6, 8, 12，R为A上整除关系。(1) 画出半序集(A,R)的哈斯图；(2) 写出A的最大元，最小元，极大元，极小元；(3) 写出A的子集B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.6. 设命题公式G = Ø(PQ)(Q(ØPR), 求G的主析取范式。7. (9分)设一阶逻辑公式：G = ("xP(x)$yQ(y)"xR(x)，把G化成前束范式.9. 设R是集合A = a, b, c, d. R是A上的二元关系, R = (a,b), (b,a), (b,c), (c,d),(1) 求出r(R), s(R), t(R)；(2) 画出r(R), s(R), t(R)的关系图.11. 通过求主析取范式判断下列命题公式是否等价：(1) G = (PQ)(ØPQR) (2) H = (P(QR)(Q(ØPR)13. 设R和S是集合Aa, b, c, d上的关系，其中R(a, a),(a, c),(b, c),(c, d), S(a, b),(b, c),(b, d),(d, d).(1) 试写出R和S的关系矩阵；(2) 计算RS, RS, R1, S1R1.四、证明题1. 利用形式演绎法证明：PQ, RS, PR蕴涵QS。2. 设A,B为任意集合，证明：(A-B)-C = A-(BC).3. (本题10分)利用形式演绎法证明：ØAB, ØCØB, CD蕴涵AD。4. (本题10分)A, B为两个任意集合，求证：A(AB) = (AB)B .参考答案一、填空题1. 3; 3,1,3,2,3,1,2,3. 2. .3. a1= (a,1), (b,1), a2= (a,2), (b,2),a3= (a,1), (b,2), a4= (a,2), (b,1); a3, a4.4. (PØQR).5. 12, 3. 6. 4, 1, 2, 3, 4, 1, 2. 7. 自反性；对称性；传递性.8. (1, 0, 0), (1, 0, 1), (1, 1, 0).9. (1,3),(2,2),(3,1); (2,4),(3,3),(4,2); (2,2),(3,3).10. 2m´n.11. x | -1x < 0, xÎR; x | 1 < x < 2, xÎR; x | 0x1, xÎR.12. 12; 6.13. (2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6).14. $x(ØP(x)Q(x).15. 21.16. (R(a)R(b)(S(a)S(b).17. (1, 3),(2, 2); (1, 1),(1, 2),(1, 3). 二、选择题 1. C. 2. D. 3. B. 4. B.5. D. 6. C. 7. C.8. A. 9. D. 10. B. 11. B. 13. A. 14. A.15. D三、计算证明题1. (1)(2) B无上界，也无最小上界。下界1, 3; 最大下界是3.(3) A无最大元，最小元是1，极大元8, 12, 90+; 极小元是1.2.R = (1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4).(1) (2)3. (1)sts(t(x)t(x)+32x+32x+3.(2)sss(s(x)s(x)+3(x+3)+3x+6,(3)sjs(j(x)j(x)+3x/4+3, (4)jtj(t(x)t(x)/42x/4 = x/2,(5)sjts(jt)jt+32x/4+3x/2+3.4. (1) P(a, f (a)P(b, f (b) = P(3, f (3)P(2, f (2)= P(3, 2)P(2, 3)= 10= 0. (2) "x$y P (y, x) = "x (P (2, x)P (3, x) = (P (2, 2)P (3, 2)(P (2, 3)P (3, 3)= (01)(01)= 11= 1.5. (1)(2) 无最大元，最小元1，极大元8, 12; 极小元是1.(3) B无上界，无最小上界。下界1, 2; 最大下界2.6. G = Ø(PQ)(Q(ØPR)= Ø(ØPQ)(Q(PR)= (PØQ)(Q(PR)= (PØQ)(QP)(QR)= (PØQR)(PØQØR)(PQR)(PQØR)(PQR)(ØPQR)= (PØQR)(PØQØR)(PQR)(PQØR)(ØPQR)= m3m4m5m6m7 = S(3, 4, 5, 6, 7).7. G = ("xP(x)$yQ(y)"xR(x)= Ø("xP(x)$yQ(y)"xR(x)= (Ø"xP(x)Ø$yQ(y)"xR(x)= ($xØP(x)"yØQ(y)"zR(z)= $x"y"z(ØP(x)ØQ(y)R(z)9. (1) r(R)RIA(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R)RR1(a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(R)RR2R3R4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)；(2)关系图:11. G(PQ)(ØPQR)(PQØR)(PQR)(ØPQR)m6m7m3å (3, 6, 7)H = (P(QR)(Q(ØPR)(PQ)(QR)(ØPQR)(PQØR)(PQR)(ØPQR)(PQR)(ØPQR)(PQØR)(ØPQR)(PQR)m6m3m7å (3, 6, 7)G,H的主析取范式相同，所以G = H.13. (1) (2)RS(a, b),(c, d),RS(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d), R1(a, a),(c, a),(c, b),(d, c),S1R1(b, a),(d, c).四 证明题1. 证明：PQ, RS, PR蕴涵QS(1) PRP(2) ØRPQ(1)(3) PQP(4) ØRQQ(2)(3)(5) ØQRQ(4)(6) RSP(7) ØQSQ(5)(6)(8) QSQ(7)2. 证明：(A-B)-C = (AB)C = A(BC)= A(BC)= A-(BC)3.证明：ØAB, ØCØB, CD蕴涵AD(1) AD(附加)(2) ØABP(3) BQ(1)(2)(4) ØCØBP(5) BCQ(4)(6) CQ(3)(5)(7) CDP(8) DQ(6)(7)(9) ADD(1)(8)所以 ØAB, ØCØB, CD蕴涵AD.4. 证明：A(AB) = A(AB)A(AB)(AA)(AB)Æ(AB)(AB)AB而 (AB)B= (AB)B= (AB)(BB)= (AB)Æ= AB所以：A(AB) = (AB)B.请您删除一下内容，O(_)O谢谢！【China's 10 must-see animations】The Chinese animation industry has seen considerable growth in the last several years. It went through a golden age in the late 1970s and 1980s when successively brilliant animation work was produced. Here are 10 must-see classics from China's animation outpouring that are not to be missed. Let's recall these colorful images that brought the country great joy. Calabash Brothers Calabash Brothers (Chinese: 葫芦娃) is a Chinese animation TV series produced by Shanghai Animation Film Studio. In the 1980s the series was one of the most popular animations in China. It was released at a point when the Chinese animation industry was in a relatively downed state compared to the rest of the international community. Still, the series was translated into 7 different languages. The episodes were produced with a vast amount of paper-cut animations. Black Cat Detective Black Cat Detective (Chinese: 黑猫警长) is a Chinese animation television series produced by the Shanghai Animation Film Studio. It is sometimes known as Mr. Black. The series was originally aired from 1984 to 1987. In June 2006, a rebroadcasting of the original series was announced. Critics bemoan the series' violence, and lack of suitability for children's education. Proponents of the show claim that it is merely for entertainment. Effendi "Effendi", meaning sir and teacher in Turkish, is the respectful name for people who own wisdom and knowledge. The hero's real name was Nasreddin. He was wise and witty and, more importantly, he had the courage to resist the exploitation of noblemen. He was also full of compassion and tried his best to help poor people. Adventure of Shuke and Beita【舒克与贝塔】 Adventure of Shuke and Beita (Chinese: 舒克和贝塔) is a classic animation by Zheng Yuanjie, who is known as King of Fairy Tales in China. Shuke and Beita are two mice who don't want to steal food like other mice. Shuke became a pilot and Beita became a tank driver, and the pair met accidentally and became good friends. Then they befriended a boy named Pipilu. With the help of PiPilu, they co-founded an airline named Shuke Beita Airlines to help other animals. Although there are only 13 episodes in this series, the content is very compact and attractive. The animation shows the preciousness of friendship and how people should be brave when facing difficulties. Even adults recalling this animation today can still feel touched by some scenes. Secrets of the Heavenly Book Secrets of the Heavenly Book, (Chinese: 天书奇谈) also referred to as "Legend of the Sealed Book" or "Tales about the Heavenly Book", was released in 1983. The film was produced with rigorous dubbing and fluid combination of music and vivid animations. The story is based on the classic literature "Ping Yao Zhuan", meaning "The Suppression of the Demons" by Feng Menglong. Yuangong, the deacon, opened the shrine and exposed the holy book to the human world. He carved the book's contents on the stone wall of a white cloud cave in the mountains. He was then punished with guarding the book for life by the jade emperor for breaking heaven's law. In order to pass this holy book to human beings, he would have to get by the antagonist fox. The whole animation is characterized by charming Chinese painting, including pavilions, ancient architecture, rippling streams and crowded markets, which fully demonstrate the unique beauty of China's natural scenery. Pleasant Goat and Big Big Wolf【喜洋洋与灰太狼】 Pleasant Goat and Big Big Wolf (Chinese:喜羊羊与灰太狼) is a Chinese animated television series. The show is about a group of goats living on the Green Pasture, and the story revolves around a clumsy wolf who wants to eat them. It is a popular domestic animation series and has been adapted into movies. Nezha Conquers the Dragon King（Chinese: 哪吒闹海） is an outstanding animation issued by the Ministry of Culture in 1979 and is based on an episode from the Chinese mythological novel "Fengshen Yanyi". A mother gave birth to a ball of flesh shaped like a lotus bud. The father, Li Jing, chopped open the ball, and beautiful boy, Nezha, sprung out. One day, when Nezha was seven years old, he went to the nearby seashore for a swim and killed the third son of the Dragon King who was persecuting local residents. The story primarily revolves around the Dragon King's feud with Nezha over his son's death. Through bravery and wit, Nezha finally broke into the underwater palace and successfully defeated him. The film shows various kinds of attractive sceneries and the traditional culture of China, such as spectacular mountains, elegant sea waves and exquisite ancient Chinese clothes. It has received a variety of awards. Havoc in Heaven The story of Havoc in Heaven（Chinese: 大闹天宫）is based on the earliest chapters of the classic story Journey to the West. The main character is Sun Wukong, aka the Monkey King, who rebels against the Jade Emperor of heaven. The stylized animation and drums and percussion accompaniment used in this film are heavily influenced by Beijing Opera traditions. The name of the movie became a colloquialism in the Chinese language to describe someone making a mess. Regardless that it was an animated film, it still became one of the most influential films in all of Asia. Countless cartoon adaptations that followed have reused the same classic story Journey to the West, yet many consider this 1964 iteration to be the most original, fitting and memorable, The Golden Monkey Defeats a Demon【金猴降妖】 The Golden Monkey Defeats a Demon (Chinese: 金猴降妖), also referred as "The Monkey King Conquers the Demon", is adapted from chapters of the Chinese classics "Journey to the West," or "Monkey" in the Western world. The five-episode animation series tells the story of Monkey King Sun Wukong, who followed Monk Xuan Zang's trip to the West to take the Buddhistic sutra. They met a white bone evil, and the evil transformed human appearances three times to seduce the monk. Twice Monkey King recognized it and brought it down. The monk was unable to recognize the monster and expelled Sun Wukong. Xuan Zang was then captured by the monster. Fortunately Bajie, another apprentice of Xuan Zang, escaped and persuaded the Monkey King to come rescue the monk. Finally, Sun kills the evil and saves Xuan Zang. The outstanding animation has received a variety of awards, including the 6th Hundred Flowers Festival Award and the Chicago International Children's Film Festival Award in 1989. McDull【麦兜】 McDull is a cartoon pig character that was created in Hong Kong by Alice Mak and Brian Tse. Although McDull made his first appearances as a supporting character in the McMug comics, McDull has since become a central character in his own right, attracting a huge following in Hong Kong. The first McDull movie McMug Story My Life as McDull documented his life and the relationship between him and his mother.The McMug Story My Life as McDull is also being translated into French and shown in France. In this version, Mak Bing is the mother of McDull, not his father. 9