离散数学考试试题(A卷及答案)
- 格式:doc
- 大小:655.00 KB
- 文档页数:5
离散数学考试试题(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且|A|=n,|B|=m,求A到B的二元关系数是多少?A到B的函数数是多少?
解:因为|P(A×B)|=2|A×B|=2|A||B|=2mn,所以A到B的二元关系有2mn个。因为|BA|=|B||A|=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,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元,求有多少儿童没有乘坐过其中任何一种。
解设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合,|A∩B∩C|=20,|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|=55,|A|+|B|+|C|=70/0.5=140。
由容斥原理,得
|A∪B∪C|=|A|+|B|+|C|―|A∩B|―|A∩C|―|B∩C|+|A∩B∩C|
所以
|A∩B∩C|=75-|A∪B∪C|=75-(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|)+|A∩B∩C|=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是自反关系,所以
的。
∀x、y∈A,若
∀x、y、z∈A,若
总之R∩S是等价关系。
2)因为x∈[a]R∩S⇔
所以[a]R∩S=[a]R∩[a]S。
七(10分)设A、B、C、D是集合,f是A到B的双射,g是C到D的双射,令h:A×C→B×D且∀∈A×C,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()=
2)再证h是单射。
∀
综合1)和2),h是双射。
八、(12分)
证明:1)∀a,b∈G,a∆b=a*u-1*b∈G,运算是封闭的。
2)∀a,b,c∈G,(a∆b)∆c=(a*u-1*b)*u-1*c=a*u-1*(b*u-1*c)=a∆(b∆c),运算是可结合的。
3)∀a∈G,设E为∆的单位元,则a∆E=a*u-1*E=a,得E=u,存在单位元。
4)∀a∈G,a∆x=a*u-1*x=E,x=u*a-1*u,则x∆a=u*a-1*u*u-1*a=u=E,每个元素都有逆元。
所以
九、(10分)已知:D=
解:D的邻接距阵A和可达距阵P如下:
0 1 0 1 0 1 1 1 1 1
0 0 1 0 0 1 1 1 1 1
A= 0 0 0 1 1 P= 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 1 1 1 1
十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。
解:最优二叉树为