试卷三试题与答案

试卷三试题与答案一、填空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的前束范式为。二、选择1、下述命题公式中，是重言式的为（）。A、)()(qpqp；B、))())(()(pqqpqp；C、qqp)(；D、qpp)(。2、rqpwff)(的主析取范式中含极小项的个数为（）。A、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][],[)(,:；D、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都有可能。三、用构造法证明1、FAFEDDCBA,2、)()())()((xxQxxPxQxPx四、集合X={1,2,3,4,5,6,…}，R={x1,y1,x2,y2|x1+y2=x2+y1}。1、证明R是X上的等价关系。2、求出X关于R的商集。五、设集合A={a,b,c,d}上关系R={a,b,b,a,b,c,c,d}要求1、写出R的关系矩阵和关系图。2、用矩阵运算求出R的传递闭包。答案一、填空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、反对称性、反自反性；5、}}}2{},2,{{}},2{{}},2,{{,{；6、1；7、)()()(RQPRQPRQP；8、任意x，如果x是素数则存在一个y，y是奇数且y整除x；8、)),,(),(),((uyxQzyPzxPuzyx。二、选择题目12345678910答案CCCCABDADC三、证明1、①AP（附加前提）②BAT①I③DCBAP④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四、1、证明：（1）自反性：yxyxXyx由于,,自反RRyxyx,,,（2）对称性：XyxXyx2211,,,时当Ryxyx2211,,,21121221yxyxyxyx也即即有对称性故RRyxyx1122,,,（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五、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}。