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

离散数学试卷（三）16一、填空20%（每空2分）1、设f，g是自然数集N上的函数xxgxxfNx2)(,1)(,，则)(xgf。2、设A={a，b，c}，A上二元关系R={a,a,a,b,a,c,c,c},则s（R）=。3、A={1，2，3，4，5，6}，A上二元关系}|,{是素数yxyxT，则用列举法T=；T的关系图为；T具有性质。4、集合}}2{},2,{{A的幂集A2=。5、P，Q真值为0；R，S真值为1。则))()(())((SRQPSRPwff的真值为。6、RRQPwff))((的主合取范式为。7、设P（x）：x是素数，E(x)：x是偶数，O(x)：x是奇数N(x,y)：x可以整数y。则谓词))),()(()((xyNyOyxPxwff的自然语言是。8、谓词)),,()),(),(((uyxuQzyPzxPzyxwff的前束范式为。二、选择20%（每小题2分）1、下述命题公式中，是重言式的为（）。A、)()(qpqp；B、))())(()(pqqpqp；C、qqp)(；D、qpp)(。2、rqpwff)(的主析取范式中含极小项的个数为（）。离散数学试卷（三）17A、2；B、3；C、5；D、0；E、8。3、给定推理①))()((xGxFxP②)()(yGyFUS①③)(xxFP④)(yFES③⑤)(yGT②④I⑥)(xxGUG⑤)())()((xxGxGxFx推理过程中错在（）。A、①-②;B、②-③;C、③-④;D、④-⑤;E、⑤-⑥4、设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件31SXSX且下X与（）集合相等。A、X=S2或S5；B、X=S4或S5；C、X=S1，S2或S4；D、X与S1，…，S5中任何集合都不等。5、设R和S是P上的关系，P是所有人的集合，},|,{的父亲是yxPyxyxR，},|,{的母亲是yxPyxyxS则RS1表示关系（）。A、},|,{的丈夫是yxPyxyx；B、},|,{的孙子或孙女是yxPyxyx；C、；D、},|,{的祖父或祖母是yxPyxyx。6、下面函数（）是单射而非满射。A、12)(,:2xxxfRRf；B、xxfRZfln)(,:；C、的最大整数表示不大于xxxxfZRf][],[)(,:；离散数学试卷（三）18D、12)(,:xxfRRf。其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。7、设S={1，2，3}，R为S上的关系，其关系图为则R具有（）的性质。A、自反、对称、传递；B、什么性质也没有；C、反自反、反对称、传递；D、自反、对称、反对称、传递。8、设}}2,1{},1{,{S，则有（）S。A、{{1,2}}；B、{1,2}；C、{1}；D、{2}。9、设A={1,2,3}，则A上有（）个二元关系。A、23；B、32；C、322；D、232。10、全体小项合取式为（）。A、可满足式；B、矛盾式；C、永真式；D、A，B，C都有可能。三、用CP规则证明16%（每小题8分）1、FAFEDDCBA,2、)()())()((xxQxxPxQxPx四、（14%）集合X={1,2,3,4,5,6,…}，R={x1,y1,x2,y2|x1+y2=x2+y1}。1、证明R是X上的等价关系。（10分）2、求出X关于R的商集。（4分）五、（10%）设集合A={a,b,c,d}上关系R={a,b,b,a,b,c,c,d}离散数学试卷（三）19要求1、写出R的关系矩阵和关系图。（4分）2、用矩阵运算求出R的传递闭包。（6分）六、（20%）1、（10分）设f和g是函数，证明gf也是函数。2、（10分）设函数STfTSg::，证明STf:有一左逆函数当且仅当f是入射函数。一、填空20%（每空2分）1、2(x+1)；2、}a,c,a,b,c,c,c,a,b,a,a,a{；3、3,6,2,6,2,4,5,1,3,1,2,1{；4、反对称性、反自反性；4、}}}2{},2,{{}},2{{}},2,{{,{；5、1；6、)()()(RQPRQPRQP；7、任意x，如果x是素数则存在一个y，y是奇数且y整除x；8、)),,(),(),((uyxQzyPzxPuzyx。二、选择20%（每小题2分）题目12345678910答案CCCCABDADC三、证明16%(每小题8分)1、①AP（附加前提）②BAT①I③DCBAP离散数学试卷（三）20④DCT②③I⑤DT④I⑥EDT⑤I⑦FEDP⑧FT⑥⑦I⑨FACP2、)()(())()(()()()()()(xxQxxPxQxPxxxQxPxxxQxxP本题可证①))((xxPP（附加前提）②))((xPxT①E③)(aPES②④))()((xQxPxP⑤)()(aQaPUS④⑥)(aQT③⑤I⑦)(xxQEG⑥⑧)()((xxQxxPCP四、14%1、证明：（1）自反性：yxyxXyx由于,,自反RRyxyx,,,（2）对称性：XyxXyx2211,,,时当Ryxyx2211,,,21121221yxyxyxyx也即即有对称性故RRyxyx1122,,,离散数学试卷（三）21（3）传递性：XyxXyxXyx332211,,,,时且当RyxyxRyxyx33222211,,,,,,)2()1(23321221yxyxyxyx即23123221)2()1(yxyxyxyx即1331yxyx有传递性故RRyxyx3311,,,由（1）（2）（3）知：R是X上的先等价关系。2、X/R=}]2,1{[R五、10%1、0000100001010010RM；关系图2、00000000101001012RRRMMM000000000101101023RRRMMM2340000000010100101RRRRMMMM,,4635RRRRMMMM0000100011111111432)(RRRRRtMMMMMt(R)={a,a,a,b,a,c,a,d,b,a,b,b,b,c.,b,d,c,d}。离散数学试卷（三）22六、20%1、（1）)}()(|,{)}()(|,{xgxfydomgdomfxyxxgyxfydomgxdomfxyxgf)}()(,|{xgxfdomgdomfxxdomhgdomfgfh令（2）)}()()(|,{xgxfxhydomgdomfxyxh使得若有对21,yydomhx)()()(,)()()(21xgxfxhyxgxfxhy21,)(yygf有是函数或由于)(xhyydomhx使得有唯一即也是函数gf。2、证明：ttfgTtgf)(,则对有一左逆若是入射所以是入射故ffg,。的左逆元是故则且若或只有一个值则对令若此时令使入射由定义如下是入射fgtsgtfgstfctsgSsTcsgTfstsgstfTtfTfsSTff,)()()()(,)()(,)()(,|,),(::,左逆函数为使必能构造函数入射即若fggf,,。