电大离散数学期末综合复习资料小抄.doc

电大离散数学期末综合复习资料小抄一、判断题1. （ ）命题联结词，是最小联结词组。2. （ ）（PQ）P为矛盾式。3. （ ）（PQ）（QR）（PR）为重言式。4. （ ）A、B、C是任意命题公式，如果ACBC，一定有AB。5. （ ）若集合A上的二元关系R是对称的，RC一定是对称的。6. （ ）R是A上的二元关系，R是自反的，当且仅当r(R)=R。7. （ ）集合A上的等价关系确定了A的一个划分。8. （ ）有理数集是可数的。9. （ ）若函数f，g为入射则其复合函数也为入射。10. （ ）R是集合A上的关系，R有传递性的充要条件是RoRR。11. （ ）设是一个代数系统，且集合A中元素的个数大于1。如果该代数系统中存在幺元e和零元q，则eq。12. （ ）交换群必是循环群。13. （ ）一个群可以有多个等幂元。14. （ ）模格一定是分配格。15. （ ）每个有向图中，结点入度数总和等于结点出度总和。16. （ ）图G的邻接矩阵A，Al中的i行j列表示结点vi到vj长度为l路的数目。17. （ ）任何图中必有偶数个度数为奇数的结点。18. （ ）有向图中，它的每一个结点位于且只位于一个单侧分图中。19. （ ）任意平面图最多是四色的。20. （ ）不存在既有欧拉回路又有汉密尔顿回路的图。二、填空题1 设P：“天下雨”，Q：“他骑自行车上班”，R：“他乘公共汽车上班”。则命题“除非下雨，否则他就骑自行车上班”可符号化为 。“他或者骑自行车，或者乘公共汽车上班”可符号化为 2 设N(x)：x是自然数；J(x)：x是奇数；Q(x)：x是偶数，用谓词公式符号化命题“任何自然数不是偶数就是奇数”。3 设P(x)：x是运动员，Q(x)：x是教练。则命题“不是所有运动员都是教练”可符号化为。4 设D=a,b；P(a,a)=P(b,b)=T；P(a,b)=P(b,a)=F。则公式(x)($y)(P(x,y)P(y,x)的真值是。5 集合A=,的幂集P(A)为6 集合A=1,2，B=a,b,c,d，C=c,d,e，则A(B-C)为7 试用空集构成集合A（A）= 和B= ，使得AB且AB都成立。并且AB=。8 设A=1,2,3，R=,，传递闭包t(R)为 。9 设A=1,2,3，B=x,y，f：AB，则不同的函数个数为 个。10 Q为有理数集，Q上定义运算*为a*b=a+b-ab，则的幺元为 。11 代数系统，其中Sk=x|xZx=K，+为普通加法，则是一个半群的必要条件是 。12 设G为v个结点e条边的连通平面图，则面r等于 。13 一棵树有n2个结点度数为2，n3个结点度数为3，nk个结点度数为k，则度数为1的结点的个数为 。14 设T为根树，若每个结点的出度都小于等于m，则T称为 树，若除 外，每个结点的出度都等于m，则T称为完全m叉树。15 设是偏序集，如果A中任意两个元素都有 和 ，则称为格。三、解答题1. 将公式(PQ) (QR)(PR)化成与之等价且仅含、的公式。2. 将下列命题符号化：（1）他虽聪明但不用功。（2）除非你努力否则你将失败。（3）我们不能既划船又跑步（4）仅当你走我才留下。3. 用谓词表达式符号化下列命题：（1）所有老的国家选手都是运动员。（2）某些教练是年老的，但是健壮的。（3）任何自然数不是偶数就是奇数。（4）不是所有运动员都是教练。4. 求命题公式(PQ)的主合取范式。5. 求命题公式P(PQ)的主析取范式。6. 设集合A1, 2, 3，A上的关系R, （1）画出R的关系图；（2）写出R的关系矩阵；（2）问R具有关系的哪几种性质(自反、反自反、对称、反对称、传递)。7. 构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大下界但没有最小元。8. 以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。a) f: ZN, f(x)=x2+1b) f: NQ, f(x) = 1/xc) f: 1,2,3a,b,c, f=,d) f: NN, f(x)=2xe) f: RRRR, f(x,y)=9. 设S=1,2,3,4,6,12，D为S上的整除关系，（1）试写出该关系并画出哈斯图；（2）设子集B=2,3,6，试求B的最大元、最小元、极大元和极小元；（3）试求B的上界、上确界、下界和下确界。10. 设集合A有m个元素，B有n个元素，则A到B的关系有多少个？A到B的函数有多少个？11. 判定下列代数系统是否为群，请说明原因。（1），其中R为实数集，+为普通加法；（2），其中I为整数集，为普通乘法 12. 设群的运算表如下：*eabeeabaabebbea试写出的所有子群，及其相应的左陪集。13. 设G=，V=V1,V2,V3,V4的邻接矩阵：0 1 0 11 0 1 1 1 1 0 0 1 0 0 0 A(G)=（1）试画出该图。（2）V2的入度d-(V2)和出度d+(V2)是多少？（3）从V2到V4长度为2的路有几条？v1v3v2v5v414. 试求下面有向图的强分图、单侧分图和弱分图15. （1）画一个有欧拉回路和一条汉密尔顿回路的图。（2）画一个有欧拉回路，但没有汉密尔顿回路的图。（3）画一个没有欧拉回路，但有汉密尔顿回路的图。V1V2V3V4V54325112216. 下图给出的赋权图表示五个城市及对应两个城镇间公路的长度。是给出一个最优的设计方案使各城市间有公路连通。17. 设有一组权3、4、13、5、6、12，（1）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子的权）。（2）设上述权值分别对应英文字母b、d、e、g、o、y，试根据求得的最优树构造前缀码，并对二进制序列0100110110010001011译码。四、证明题1. A (BC),(EF)C,B(AS)BE2. 试证明命题公式为永真式。3. 试证明：(PQ) (PR) (QS) SR4. 用推理规则证明：(x)(P(x)Q(x) ($x) P(x)($y)(P(y)Q(y)5. 对所有集合A、B和C，有(AB)C=A(BC)，当且仅当CA。6. 若R和S是集合A上的等价关系，试证明RS也是A上的等价关系。7. 证明集合0,1和(0,1)是等势的。8. 设f: X-Y和g: Y-Z是函数，使得gf是一个满射，且g是一个入射。证明f是满射。9. 设,是两个群，在G1G2上定义运算为：=，证明是一个群。10. f是群到群的同态映射，e是G中的幺元则，f的同态核K=x|xG且f(x)=e构成的代数系统是的子群。11. 证明在格中，若abc，则（1）ab=bc（2）(ab)(bc)=b=(ab)(ac)12. 若有n个人，每个人恰有三个朋友，证明n必为偶数。13. 证明当且仅当G的一条边e不包含在G的回路中时，e才是G的割边。14. 画出K3,3图，并证明其不是欧拉图，也不是平面图。15. 设G为连通图，证明当且仅当边e是G的割边时，e才在G的每颗生成树中。16. 设T是非平凡的无向树，T中度数最大的结点有2个，它们的度数为k（k=2），证明：T中至少有2k-2片树叶。17. 设G=有11个结点，m条边，证明G或者其补图G是非平面图。部分参考答案一、判断题1. （错误）2. （正确）3. （正确）4. （错误）5. （正确）6. （正确）7. （正确）8. （正确）9. （正确）10. （正确）11. （正确）12. （错误）13. （错误）14. （错误）15. （正确）16. （正确）17. （正确）18. （正确）19. （正确）20. （错误）请您删除一下内容，O(_)O谢谢！【Chinas 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 Chinas animation outpouring that are not to be missed. Lets recall these colorful images that brought the country great joy. Calabash Brothers Calabash Brothers (Chinese: 葫芦娃) is a Chinese animation TV series produced byShanghaiAnimationFilmStudio. 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 childrens education. Proponents of the show claim that it is merely for entertainment. Effendi Effendi, meaning sir andteacher in Turkish, is the respectful name for people who own wisdom and knowledge. The heros 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 dont 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 books 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 heavens 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 Chinesepainting, including pavilions, ancient architecture, rippling streams and crowded markets, which fully demonstrate the unique beauty of Chinas 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 intomovies. 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 Kings feud with Nezha over his sons 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 storyJourney 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 byBeijingOpera 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 Zangs 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 Childrens Film Festival Award in 1989. McDull【麦兜】 McDull is a cartoon pig character that was created inHong Kongby 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.