资源描述：
《离散数学考试试题(a卷及答案)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、离散数学考试试题（A卷及答案）一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？1)((P®Q)∧Q)«((Q∨R)∧Q)2)Ø((Q®P)∨ØP)∧(P∨R)3)((ØP∨Q)®R)®((P∧Q)∨R)解：1)永真式；2）永假式；3)可满足式。二、（8分）个体域为{1，2}，求"x$y（x+y=4）的真值。解："x$y（x+y=4）Û"x（（x+1=4）∨（x+2=4））Û（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4））Û（0∨0）∧（0∨1）Û1∧1Û0三、（8分）已知集合A和B且
2、A
3、=n，
4、B
5、=m，求A
6、到B的二元关系数是多少？A到B的函数数是多少？解：因为
7、P(A×B)
8、=2
9、A×B
10、=2
11、A
12、
13、B
14、=2mn，所以A到B的二元关系有2mn个。因为
15、BA
16、=
17、B
18、
19、A
20、=mn，所以A到B的函数mn个。四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>
21、,<3,2>,<4,3>,<4,5>}t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}五、(10分)75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。解设、、分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，
22、∩∩
23、＝20，
24、∩
25、＋
26、∩
27、＋
28、∩
29、－2
30、∩∩
31、＝55，
32、
33、＋
34、
35、
36、＋
37、
38、＝70/0.5＝140。由容斥原理，得
39、∪∪
40、＝
41、
42、＋
43、
44、＋
45、
46、―
47、∩
48、―
49、∩
50、―
51、∩
52、＋
53、∩∩
54、所以
55、∩∩
56、＝75－
57、∪∪
58、＝75－(
59、
60、＋
61、
62、＋
63、
64、)＋(
65、∩
66、＋
67、∩
68、＋
69、∩
70、－2
71、∩∩
72、)＋
73、∩∩
74、＝75－140＋55＋20＝10没有乘坐过其中任何一种的儿童共10人。六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。解："x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。"x、y∈A，若
75、∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。5"x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。总之R∩S是等价关系。2）因为x∈[a]R∩SÛ∈R∩SÛ∈R∧∈SÛx∈[a]R∧x∈[a]SÛx∈[a]R∩[a]S所以[a]R∩S=[a]R∩
76、[a]S。七（10分）设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×C®B×D且"∈A×C，h()＝。证明h是双射。证明：1）先证h是满射。"∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是满射。2）再证h是单射。"、∈A×C，若h()＝h()，则<
77、f(a1),g(c1)>＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。综合1）和2），h是双射。八、（12分）是个群，u∈G，定义G中的运算“D”为aDb=a*u-1*b，对任意a,b∈G，求证：也是个群。证明：1）"a,b∈G，aDb=a*u-1*b∈G，运算是封闭的。2）"a,b,c∈G，（aDb）Dc=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=aD
78、（bDc），运算是可结合的。3）"a∈G，设E为D的单位元，则aDE=a*u-1*E=a，得E=u，存在单位元。4）"a∈G，aDx=a
