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

离散数学试卷（十一）68一、填空20%（每小题2分）1、称为命题。2、命题P→Q的真值为0，当且仅当。3、一个命题含有4个原子命题，则对其所有可能赋值有种。4、所有小项的析取式为。5、令P（x）：x是质数，E（x）：x是偶数，Q（x）：x是奇数，D（x，y）：x除尽y.则)))(),(()((yEyxDyxEx的汉语翻译为。6、设S={a，b,c}则S6的集合表示为。7、P（P()）=。8、BA=。9、设R为集合A上的关系，则t（R）=。10、若R是集合A上的偏序关系，则R满足。二、选择20%（每小题2分）1、下列命题正确的有（）。A、若fg,是满射，则fg是满射；B、若fg是满射，则fg,都是满射；C、若fg是单射，则fg,都是单射；D、若fg单射，则f是单射。2、设f，g是函数，当（）时，f=g。A、)()(xgxfdomfx都有；B、gfdomfdomg且；C、的表达式相同与gf；D、rangefrangefdomfdomg,。3、下列关系，（）能构成函数。A、}10,|,{212121xxNxxxxf且；B、},,|,{2212121xxRxxxxf；C、},,|,{122121的素数的个数为小于xxNxxxxf；离散数学试卷（十一）69D、}|,{Rxxxf。4、下列函数（）满射；（）单射；（）双射（）；一般函数（）。A、2)(,:2xxfNNf；B、)3(mod)(,:xxfNNf（x除以3的余数）；C、奇数集偶数集xxxfNf01)(},1,0{:；D、52)(,:xxfRRf。5、集合A={1，2，3，4}上的偏序关系为，则它的Hass图为（）。6、设集合A={1，2，3，4，5}上偏序关系的Hass图为则子集B={2，3，4}的最大元（）；最小元（）；极大元（）；极小元（）；上界（）；上确界（）；下界（）；下确界（）。A、无，4，2、3，4，1，1，4，4；B、无，4、5，2、3，4、5，1，1，4，4；C、无，4，2、3，4、5，1，1，4，4；D、无，4，2、3，4，1，1，4，无。7、设R，S是集合A上的关系，则下列（）断言是正确的。A、SR,自反的，则SR是自反的；B、若SR,对称的，则SR是对称的；离散数学试卷（十一）70C、若SR,传递的，则SR是传递的；D、若SR,反对称的，则SR是反对称的8、设X为集合，|X|=n，在X上有（）种不同的关系。A、n2；B、2n；C、n22；D、22n。9、下列推导错在（）。①)(yxyxP②)(yzyUS①③)(zCzES②④)(xxxUG③A、②；B、③；C、④；D、无。10、“没有不犯错误的人”的逻辑符号化为（）。设H（x）：x是人，P（x）：x犯错误。A、))()((xPxHx；B、)))()(((xPxHx；C、)))()(((xPxHx；D、))()((xPxHx。三、命题演绎28%1、（10分）用反证法证明RSSQRPQP)()()(。2、（8分）用CP规则证明)()(),(SQPSQRRQP。3、（10分）演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。因此，虚数既不是有理数，也不是无理数。四、8%将)))()(()),(((xRzzQyxyPxwff化为与其等价的前束范式。五、8%A={a,b,c,d}，R={a,b,b,c,b,d,c,b}为A上的关系，利用矩阵乘法求R的传递闭包，并画出t（R）的关系图。离散数学试卷（十一）71六、证明16%1、（8分）设A={1，2，3，4}，在P（A）上规定二元关系如下：tstsR,|,{P（A）|)}||(|ts证明R是P（A）上的等价关系并写出商集P（A）/R。2、（8分）设f是A到A的满射，且fff，证明f=IA。一、填空20%（每小题2分）1、能够断真假的阵述句；2、P的真值为1，Q的真值为0；3、24=16；4、永真式；5、任意两数x、y,如果x是偶数且能除尽y，则y一定是偶数；6、S110={a,b}；7、}}}{,{}},{{},{,{；8、)(~)~(BABA；9、1iiR；10、自反性、反对称性、传递性二、选择20%（每小题2分）题目12345678910答案A、DBC、DC、D；A、D；D；BCAADCB、D三、命题演绎28%1、（10分）证明：⑴)(RSP（附加前提）⑵RST⑴E⑶QPP⑷QPT⑶E⑸SQP⑹SPT⑷⑸E⑺PST⑹E⑻)()(RPRST⑺I离散数学试卷（十一）72⑼RPT⑵⑻I⑽RPP⑾RPT⑽E⑿)(RPT⑾E⒀FT⑼⑿I2、（8分）①PP（附加前提）②)(RQPP③RQT①②I④)(SQRP⑤)(SQQT③④I⑥SQT⑤E⑦)(SQPCP3、证明：设Q（x）：x是有理数，R(x)：x是实数，N(x)：x是无理数，C(x)：x是虚数。前提：))()((xRxQx))()((xRxNx))()((xRxCx结论：))()()((xNxQxCx⑴))()((xRxQxP⑵)()(cRcQUS⑴⑶))()((xRxNxP⑷)()(cRcNUS⑶⑸))()((xRxCxP⑹)()(cRcCUS⑸⑺)()(cCcRT⑹E⑻)()(cCcQT⑵⑺I离散数学试卷（十一）73⑼)()(cCcNT⑷⑺I⑽))()(())()((cCcNcCcQT⑻⑼I⑾)()()(cNcQcCT⑽E⑿))()()((xNxQxCxUG⑾四、8%解：))()(),(()))())((),((()))())(((),(((()))())((()),(((xRzQyxPzyxxRzQzyxPyxxRzzQyxPyxxRzzQyxPyx五、8%解：00001100001011000000001011000010000000101100001000000010110000102RRRRMMMMRRRRMMMM00000010110000100000001011000010000011000010110023234000011000010110000000010110000100000001011000010RRRRMMMM0000111011101110432)(RRRRRtMMMMM离散数学试卷（十一）74所以t（R）={a,b,a,c,a,d,b,b,b,c,b,d,c,b,c,c,c,d}关系图为六、证明16%1、（8分）证明：⑴sP（A），由于||||ss，所以Rss,，即R自反的。⑵ts,P（A），若Rts,，则||||||||stts，Rst,，R是对称的。⑶uts,,P（A），若：RutRts,,且，即：||||||utsRusus,|,|||所以R是传递的。由⑴⑵⑶知，R是等价关系。P（A）/R={[]R，[{1}]R，[{1，2}]R，[{1，2，3}]R，[{1，2，3，4}]R}2、（8分）证明：因为f是满射，所以Aa，存在Aa1使得aaf)(1，又因为f是函数，所以)())((1afaff即)()(1afaff由fff所以)()(1afaf，又aaf)(1，所以aaf)(由a的任意性知：f=IA。