资源描述:
《离散数学考试试题r》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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到B
6、的二元关系数是多少?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>,<3,
21、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、=70
38、/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,若∈R∩S,则75、,y>∈R、∈S,因为R和S是对称关系,所以因∈R、∈S,因而∈R∩S,故R∩S是对称的。"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∩[a]S。七(10分)
76、设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)=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(bDc),运算是可结合的。3
78、)"a∈G,设E为D的单位元,则aDE=a*u-1*E=a,得E=u,存在单位元。4)"a∈G,aDx=a*