离散数学试卷及答案(9)

离散数学试卷（九）55一、填空30%（每空3分）1、选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A=。2、集合A={,{}}的幂集P(A)=。3、设A={1，2，3，4}，A上二元关系R={1，2，2，1，2，3，3，4}画出R的关系图。4、设A={1,2,2,4,3,3},B={1,3,2,4,4,2},则BA=。BA=。5、设|A|=3，则A上有个二元关系。6、A={1，2，3}上关系R=时，R既是对称的又是反对称的。7、偏序集RA,的哈斯图为，则R=。8、设|X|=n，|Y|=m则（1）从X到Y有个不同的函数。（2）当n,m满足时，存在双射有个不同的双射。9、2是有理数的真值为。10、Q：我将去上海，R：我有时间，公式)()(QRRQ的自然语言为。11、公式)()(QPPQ的主合取范式是。12、若},,,{21mSSSS是集合A的一个分划，离散数学试卷（九）56则它应满足。二、选择20%（每小题2分）1、设全集为I，下列相等的集合是（）。A、}|{是偶数或奇数xxA；B、)}2(|{yxIyyxB；C、)}12(|{yxIyyxC；D、},4,4,3,3,2,2,1,1,0|{xD。2、设S={N，Q，R}，下列命题正确的是（）。A、SSNN2,2则；B、SNSQQN则,；C、RNRQQN则,；D、SNSN则,。3、设C={{a},{b},{a,b}}，则SSCSCS与分别为（）。A、C和{a,b}；B、{a,b}与；C、{a,b}与{a,b}；D、C与C4、下列语句不是命题的有（）。A、x=13；B、离散数学是计算机系的一门必修课；C、鸡有三只脚；D、太阳系以外的星球上有生物；E、你打算考硕士研究生吗？5、RQP)(的合取范式为（）。A、RQP)(；B、)()(RQRP；C、)()()()()()(RQPRQPRQPRQPRQPRQPD、)()()()(RQPRQPRQPRQP。6、设|A|=n，则A上有（）二元关系。A、2n；B、n2；C、22n；D、nn；E、nn2。7、设r为集合A上的相容关系，其简化关系图（如图），则[I]r产生的最大相容类为（）；A、},{21xx；B、},,{321xxx；C、},{54xx；D、},,{542xxx[II]A的完全覆盖为（）。离散数学试卷（九）57A、},,,,{54321xxxxx；B、}},{},,,{},,{{5432121xxxxxxx；C、}},,{},,,{{542321xxxxxx；D、}},{},{},,{{54321xxxxx。8、集合A={1，2，3，4}上的偏序关系图为则它的哈斯图为（）。9、下列关系中能构成函数的是（）。A、)}10(),(|,{yxNyxyx；B、)}(),(|,{2xyRyxyx；C、)}(),(|,{2xyRyxyx；D、)}3mod(),(|,{yxIyxyx。10、N是自然数集，定义3mod)()(,:xxfNNf（即x除以3的余数），则f是（）。A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。三、简答题15%1、(10分)设S={1,2,3,4,6,8,12,24}，“”为S上整除关系，问：（1）偏序集,S　的Hass图如何？（2）偏序集},{S　的极小元、最小元、极大元、最大元是什么?2、（5分）设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数yxyxf),(，特定谓词yxyxF:),(，问公式))),(),,((),((zyfzxfFyxFzyxA的涵义如何？真值如何？离散数学试卷（九）58四、逻辑推理10%或者逻辑难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑并不难学。因此，如果许多学生喜欢逻辑，那么数学并不难学。五、10%设X={1,2,3,4,5}，X上的关系R={1,1,1,2,2,4,3,5,4,2}，用Warshall方法，求R的传递闭包t(R)。六、证明15%1、每一有限全序集必是良序集。（7分）2、设fg是复合函数，如果fg满射，则g也是满射。（8分）五、填空20%（每小题2分）1、)}1(),(|,{22yxRyxyxA；2、}}}{,{}},{{},{,{；3、见右图；4、{1,2,2,4,3,3,1，3，2,4,4,2}、{1,4,2,2}；5、29；6、{1,1,2,2,3,3；7、{a,b,a,d,a,e,b,d,b,e,a,c,a,f,a,g,c,f,c,g}AI；8、mn、n=m、n!；9、假；10、我将去上海当且仅当我有空；11、)()()()(QPQPQPQP；12、ASjiSSimiji1)2()()1(。六、选择20%（每小题2分）题目12345678910答案A、DCBA、EB、DCB、D；CABD七、简答题15%离散数学试卷（九）591、（10分）（1）≤={1,2,1,3,1,4,1,6,1,8,1,12,1,24,2,4,2,6,2,8，2,12,2,24,3,6,3,12,3,24,4,8,4,12,4,24,6,12,6,24,8,24,12,24}SIcovS={1,2,1,3,2,4,2,6,3,6,4,8,4,12,6,12,8,24,12,24}Hass图为（2）极小元、最小元是1，极大元、最大元是24。2、（5分）解：公式A涵义为：对任意的实数x,y,z，如果xy则(x-z)(y-z)A的真值为：真（T）。八、逻辑推理10%解：设P：逻辑难学；Q：有少数学生不喜欢逻辑学；R：数学容易学符号化：RQPRQP,证：①QPP②QPT①E③PRP④QRT②③I⑤RQT④E九、（10分）离散数学试卷（九）60解：0000000010100000100000011RMi1时，RM[1,1]=1,A=RMi2时，A[1,2]=A[4,2]=1A=0000001010100000100001011i3时，A的第三列全为0，故A不变i4时A[1,4]=A[2,4]=A[4,4]=1A=0000001010100000101001011i5时，A的第五行全为0，故A不变。所以t(R)={1,1,1,2,1,4,2,2,2,4,3,5,4,2,4,4}。十、证明15%1、（7分）证明：设},,,{21naaaA，,A全序集。若,A不是良序集，那么必有一子集)(BAB，在B中不存在最小元素，由于B是一有限集合，故一定可找出两元素x,y是无关的，由于,A是全序集。Ayx,所以x,y必有关系，矛盾。故,A必是良序集。2、（8分）证明：设ZXfgZYgYXf:,:,:，Zz由于ZXfg:满射，故必有Xx使得zxfg)(，由复合函数定义知，存在Yy使得yxf)(，又因为离散数学试卷（九）61g是函数，必对任Yy，必Zz使zyg)(，任每个z在g作用下都是Y中元素的一个映象，由Z的任意性，所以g是满射。