长江大学08级离散试卷A答案

1、 一 判断题(每小题1分，共 15分)1、 若图G是自对偶的，则e=2v-2 (T)2、 “离散数学是很有趣的一门课程”，这句话是命题。（T）3、 函数的复合既能交换也能结合。（F）4、 如果ACBC，则AB（F）5、 设G=<V,E>为连通图，且eE,则当e是G的割边时，e才在G的每棵生成树中。（T）6、 是合式公式。（T）7、 任何阶数为4的群都是阿贝尔群。（T）8、 设G是简单连通图，且有v个结点，e条边，若G是平面图，则e3v-6。（T）9、 一个循环群的生成元是唯一的。（F）10、 有任意集合A、B，则f(AB)f(A)f(B)且f(A)f(B)f(AB)。（F）11、

2、（F）12、 对任意集合A，B，C，如果AB以及BC，则AC。（F）13、 整数集上的同余类是对整数集的一个划分。（T）14、 有限半群中存在等幂元。（T）15、 设<A,*>是一个代数系统，且|A|>1，若该代数系统中存在幺元和零元，则幺元与零元相等。（F）二 、选择题(每小题2分，共 22分)1、 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，则该树有（D）片树叶。A.6 B. 7 C. 8 D.92、图1中v1到v4 长度为2的路有（A）条A. 1 B. 2 C. 3 D.4图13、设A=1，2，3，4，B=a，b，c，d，f定义为：<1,a>

3、;,<2,b>,<3,c>,<4,d>，则f（D）。 A.不是函数 B.仅为入射函数 C.仅为满射函数 D.是双射函数 4、设F(x)：x是乌鸦；G(x,y)：x与y一般黑，则“天下乌鸦一般黑”可以符号化为：(A)A.B.C.D.5、给定下列谓词公式，则是矛盾式的公式为（C）A.B. C.D.6、设有下列四个集合，偏序关系为整除，则是全序关系的为（D）A. 3,5,15 B.1,2,3,6,12C.3,4,12 D.3,9,27,547、设集合P=x1，x2，x3，x4，x5上的偏序关系如图2所示，则下列说法中正确的是（A）A、P的最大元素为x1 ，无最小元

4、素，极小元素为x4，x5 ，极大元为素x1 B、P无最大元素，也无最小元素，极小元素为x4，x5 ，极大元为素x1 C、P的最大元素为x1 ，无最小元素，也无极小元素 ，极大元为素x1 D、P的最大元素为x1 ，最小元素为x4，x5，极小元素为x4，x5 ，极大元为素x1 图28、集合A=a，b，c，A上的关系R=（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c），则R具有关系的（B）性质。A、自反性 B、对称性 C、反对称性 D、传递性9、下面给出的一阶逻辑等价式中，（B）是错的。10、一个公式在等价意义下，下面哪个写法是唯一的（C）。A析取范式 B合取范式

5、C主析取范式 D以上答案都不对11、已知图G的相邻矩阵为 A(G) 则G有（A）。 A. 5点，8边 B. 6点，7边 C. 5点，7边 D. 6点，8边A(G)=三 、填空题(每空2分，共 30分)1、 n为奇数时，无向完全图Kn是欧拉图。n为时，无向完全图Kn仅存在欧拉通路而不存在欧拉回路。2、 如图2，则k(G)= 2 (G)= 2 (G)= 2 图23、 假设X和Y是有穷集合，则从X到Y存在入射的必要条件是|X| |Y| ，且f(x1)=f(x2)时必有x1=x2。4、 设P表示命题“8是偶数”，Q表示命题“糖果是甜的”，则命题PQ的反换式所表示的含义是如果8不是偶数，则糖果不是甜的。

6、5、 （PQ）R的对偶式为（PQ）R。6、设P(x)表示x是聪明的，M(x)表示x是人，则命题“尽管有人聪明，但未必一切人都聪明”可以符号化为：7、集合a,a的幂集为：，a，a，a，a8、令R=<1,2>,<3,4>,<2,2>和S=<4,2>,<2,5>,<3,1>,<1,3>，则<1,5>,<3,2>,<2,5>9、设A=a,b,c，R是A上的二元关系，且给定R=<a,b>,<b,c>,<c,a>，则r(R)=<a,b>,&

7、lt;b,c>,<c,a>,<a,a>,<b,b>,<c,c>10、设I是整数集合，R是同余模3的关系，则I/R=0R,1R,2R11、设谓词的定义域为，将表达式中的量词消除，写成与之等价的命题公式是 12、设P(x)：x是素数；E(x)：x是偶数；O(x)：x是奇数；N(x，y)：x可以整除y。则可以译成自然语言为：对于任意的x，如果x是素数，则存在一个y，y是奇数且y整除x。四 、证明题(第1，2题各5分，第3题8分，共 18分)1、如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊不吃

8、草。符号化该命题，并用推理理论证明之。 解：设P：马会飞；Q：羊吃草；R：母鸡是飞鸟；S：烤熟的鸭子还会跑。则上述语句可以符号化为：前提：结论：证明 采用直接证明方法（1）¬S P（2）RS P（3）¬R T（1），（2）I（4）PQR P（5）¬（PQ） T（3），（4）I（6）¬ P¬Q T（5）E（7）¬ Q T（6）I 2、证明：若X×Y=X×Z，且X不为空集，则Y=Z。证明：因为X×Y=X×Z，则X×YX×Z，且X×YX×Z又因为X不为空集，所以

9、有YZ，且YZ，所以Y=Z成立。3、设<A,*>是半群，e是左幺元且对每一个xA，存在xA，使得x*x=e。a) 证明：对于任意的a,b,cA，如果a*b=a*c，则b=c。b) 通过证明e是A中的幺元，证明<A,*>是群。证明：a)因为a*b=a*c，则a*a*b=a*a*c 即e*b=e*c 所以b=cb)对任一xA,则x*(x*e)=x*x*e=x*x，由a)可得x*e=x，又e是左幺元，所以e是幺元。即有e*x=x*e 则有x*x*x=x*x*x 所以有 x*x=x*x=e 即每个元素都有逆元所以<A,*>是群。五 、应用题(第1题5分，第2题10分

10、，共15 分)1、 双射函数是密码学中的重要工具，因为在密码体制中大都会同时涉及加密和解密，假设f是由表1定义的，即f(A)=D,f(B)=E,F(C)=S,等，试找出给定密文“ARDJYLRXBMB”对应的明文。 表1ABCDEFGHIJKLMDESTINYABCFGH 续表1NOPQRSTUVWXYZJKLMOPQRUVWXZ 解：表1给出了一个双射函数f，为了求出给定密文的明文，只需要求出f的逆函数f-1，按照f-1的对应关系依次还原出对应字母的原象就可以得到该密文对应的明文。由表1知f-1如下表所示：ABCDEFGHIJKLMHIJABKLMENOPQNOPQRSTUVWXYZFRST

11、UCDVWXYGZ则给定密文“ARDJYLRXBMB”对应的明文为“HUANGPUYIQI”2、 设按顺序排列的13张红心纸牌 A 2 3 4 5 6 7 8 9 10 J Q K经过1次洗牌后牌的顺序变为：3 8 K A 4 10 Q J 5 7 6 2 9问，再经过两次同样方式的洗牌后牌的顺序是怎么的？为什么？解：将洗牌的过程看成建立函数f的过程，即有f(A)=3,f(2)=8,f(3)=K,f(4)=A, f(5)=4,f(6)=10,f(7)=Q, f(8)=J,f(9)=5,f(10)=7,f(J)=6,f(Q)=2, f(K)=9.则求经过两次同样方式的洗牌后牌的顺序即为求f f f的值。则经过两次同样方式的洗牌后牌的顺序是9 6 5 K 3 Q 8 10 A 2 7 J 43、设有a,b,c,d,e,f,g七个人，他们分别会讲如下各种语言：a会讲英语；b会讲汉语与英语；c会讲英语、西班牙语和俄语；d会讲日语和汉语；e会讲德语和