2007-2008(1B)离散数学期末试卷及答案

《离散数学》试卷共5页第1页安徽大学2007-2008学年第1学期《离散数学》期末考试试卷（B卷）（时间120分钟）开课院（系、部）姓名学号.题号一二三四五六七得分得分一、选择题（每小题2分，共20分）1．设522:P，:Q雪是黑的，842:R，:S太阳从东方升起，下列命题中真值为T的是（）A、RQP；B、SPR；C、RQS；D、)()(SQRP。2．下列命题公式中，为重言式的是（）A、)(RQP；B、)()(QPRP；C、)()(RQQP；D、))()(())((RPQPRQP。3．设xxL:)(是演员，xxJ:)(是老师，xyxA:),(钦佩y，命题“所有演员都钦佩某些老师”符号化为（）A、)),()((yxAxLx；B、))),()(()((yxAyJyxLx；C、)),()()((yxAyJxLyx；D、)),()()((yxAyJxLyx。4．设}{A，))((AB，以下各小题中不正确的有（）A、B}}{{；B、B}}}{{,{；C、B}}}{{,{；D、B}}}{,{},{{。5．设A，}}{,{B，则AB是（）。A、}}{{；B、}{；C、}}{,{；D、。6．设},,{cbaA，R,S,T是集合)(A上的二元关系。其中，}|,{yxyxR，}|,{yxyxS，}|,{AyxyxT。下列哪些命题为真？（）I.R是反自反、反对称和传递的II.S是反自反和对称的III.T是反自反和对称的A、仅I；B、仅II；C、I和II；D、全真。7．R是二元关系且4RR，则一定是传递的是（）A、4R；B、3R；C、2R；D、R。8．设1R和2R是非空集合A上的等价关系，确定下列各式，哪些是A上的等价关系（）A、1RAA；B、21RR；C、21RR；D、21RR。9．I是整数集合，函数f定义为：II，xxxf2)(，则f是：（）A、单射；B、满射；C、双射；D、非单射也非满射。10．下列集合中，哪个集合的基数与其他集合的基数不同（）A、nN（N为自然数集，Nn）；B、NN（N为自然数集）；C、RR（R为实数集）；D、x坐标轴上所有闭区间集合；得分《离散数学》试卷共5页第3页二、填空题（每小题2分，共32分）1．设P:小王走路，Q:小王听音乐，在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为：________________________；设:)(xFx是人，:),(yxHx与y一样高，在谓词逻辑中，命题“人都不一样高”的符号化形式为________________________________________________。2．设xxxM,121|{被2整除，}Zx，xxxN,121|{被3整除，}Zx，则NM________________________，NM________________________。3．在自然数集N中，偶数集为1N，奇数集为2N，则21NN=________________________，21NN=________________________。4．设集合}4,3,2,1{A上的二元关系}3,1,3,3,4,2,2,1{R，则)(Rr=________________________________________________；)(Rs=________________________________________________；)(Rt=________________________________________________；5．设}4,3,2,1{A，则A上共有多少个二元关系________________；其中有多少个等价关系________________；在等价关系中，商集为二元集（即有两个元素的集合）的有________________个。6．设}1,0{A，N为自然数集，是偶数是奇数xxxf,1,0)(。若AAf:，则f是__________射的，若ANf:，则f是__________射的。7．设函数AAf:，AB为A的子集。则下列集合之间的关系是))((1Bff____________B，))((1Bff____________B。三、综合题（第2小题16分，其它各小题8分，共48分）1．用等值演算方法，按要求求解。（8分）（1）求命题公式)()(pqqp的主析取范式；（4分）（2）求命题公式rqqp)(的主合取范式。（4分）得分《离散数学》试卷共5页第3页2．用推理规则证明：（第1小题6分，第二小题10分，共16分）（1）)(QP，RQ，R永真蕴含P。（6分）（2）前提：))()(())()((yRyMyxSxFx，))()((yRyMy；结论：))()((xSxFx。（10分）3．设}5,4,3,2,1{A，A上的篇序关系,5,3,3,4,2,4,1,4,2,3,2,1{RAI}5,4。（共8分）（1）作出篇序关系R的哈斯图；（2分）（2）令}5,3,2,1{B，求B的最大、最小、极大、极小元，上界，最小上界，下界，最大下界。（6分）4．设}9,...,3,2,1{A，在AA上定义关系R：Rdcba,,,当且仅当cbda，证明R是AA上的等价关系，并求出R]5,2[。（8分）5．设NNf:，NNg:均是函数，N为自然数集，且5403,2,1,01)(xxxxxxf，为奇数3为偶数2/)(xxxxg（共8分）①求fg。（2分）②fg是单射，满射吗？（2分）③设}2,1,0{A，求)(Afg。（2分）④设}2,1,0{B，求)()(1Bfg。（2分）《离散数学》试卷共5页第3页安徽大学2007-2008学年第1学期《离散数学》期末考试试卷答案（B卷）一、选择题（每小题2分，共20分）1.A；2.D；3.B；4.B；5C；6.D；7.B；8.D；9.A；10.A。二、填空题（每空2分，共32分）1.QP，)),()()((yxHyFxFyx；2.}12,6{，}10,8,4,2{；3.2N，；4.}4,4,2,2,1,1,3,1,3,3,4,2,2,1{，}1,3,2,4,1,2,3,1,3,3,4,2,2,1{，}3,3,4,2,4,1,3,1,2,1{；5.162（65536），15，7；6.双射，满射；7.，；三、综合题（第2小题16分，其它各小题8分，共48分）1．（1）解：)()()()(pqqppqqppqqppqqp)()()(（2分）)()()(qqpppqqp)()()()()(qpqppqpqqp)()()(qpqpqp（主析取范式）（4分）（2）FFrprqqprqqprqqp)()()()7,6,5,4,3,2,1,0()()()()(rqprqprqprqp)()()()(rqprqprqprqp（主合取范式）（4分）2．（1）证明：①)(QPP②QPT,①,E（1分）③QPT,②,E（2分）④RQP⑤RQT,④,E（3分）⑥RPT,③,⑤,I（4分）⑦RP⑧PT,⑥,⑦,I（6分）（2）证明：(1)))()((yRyMyP(2))()(cRcMES,(1)（1分）(3)))()((cRcMT,(2),E（2分）(4)))()((yRyMyEG，(3)（3分）(5))()((yRyMyT,(4),E（4分）(6)))()(())()((yRyMyxSxFxP(7)))()((xSxFxT,(5),(6),I（5分）(8)))()((xSxFxT,(7),I（6分）(9)))()((aSaFUS,(8)（7分）《离散数学》试卷共5页第3页12435(10))()(aSaFT,(9),E（8分）(11))()(aSaFT,(10),E（9分）(12)))()((xSxFxUG,(11)（10分）3．解：（1）偏序关系R的哈斯图为（2分）（2）B的最大元：无；最小元：无；（4分）极大元：2,5；极小元：1,3；（6分）下界：4；最大下界：4；上界：无；最小上界：无。（8分）4．证明：1）AAba,，abba，Rbaba,,,，即R自反。（2分）2）Rdcba,,,，则cbda，bcad，即adbc，从而Rbadc,,,，即R对称。（4分）3）Rdcba,,,，Rfedc,,,，则cbda，edfc，cedf，从而ebcecbcedafa，Rfeba,,,，即R传递。（6分）综上得出，R是等价关系。且}25,,|,{]5,2[baAAbabaR=}3,,|,{baAAbaba=}9,6,8,5,7,4,6,3,5,2,4,1{（8分）5．解（1）如下列出fg的对应关系x012345678…)(xf123456789…))((xfg313203334…从而得到NNfg:4062/321152,03)(xxxxxxxxfg为偶数且的奇数或大于等于（2分）（2）fg是满射的，但不是单射的。（4分）（3）}3,1{})2,1,0({fg。（6分）（4）}4,3,1{})2,1,0({)(1fg。（8分）