离散数学期末试卷A卷及答案

-1-《离散数学》试卷（A卷）专业年级班姓名学号题号一二三四五总分得分一、选择题（共5小题，每题3分，共15分）1、设A={1,2,3},B={2,3,4,5},C={2,3},则CBA)(为(C)。A、{1,2}B、{2,3}C、{1,4,5}D、{1,2,3}2、下列语句中哪个是真命题(A)A、如果1+2=3，则4+5=9；B、1+2=3当且仅当4+5≠9。C、如果1+2=3，则4+5≠9；D、1+2=3仅当4+5≠9。3、个体域为整数集合时，下列公式（C）不是命题。A、)*(yyxyxB、)4*(yxyxC、)*(xyxxD、)2*(yxyx4、全域关系AE不具有下列哪个性质（B）。A、自反性B、反自反性C、对称性D、传递性5、函数612)(,:xxfRRf是（D）。A、单射函数B、满射函数C、既不单射也不满射D、双射函数二、填充题（共5小题，每题3分，共15分）1、设|A|=4，|P(B)|=32，|P(AB)|=128，则|AB|=ˍˍ2ˍˍˍ.-2-2、公式)(QPQ的主合取范式为。3、对于公式))()((xQxPx，其中)(xP：x=1，)(xQ：x=2，当论域为{0,1,2}时，其真值为ˍˍˍ1ˍˍˍ。4、设A＝{1,2,3,4}，则A上共有ˍˍˍ15ˍˍˍˍ个等价关系。5、设A＝{a，b，c}，B={1,2},则|BA|=8。三、判断题（对的填T，错的填F，共10小题，每题1分，共计10分）1、“这个语句是真的”是真命题。（F）2、“张刚和小强是同桌。”是复合命题。（F）3、))(()(rqqpp是矛盾式。（T）4、)(TSRTRSR。（F）5、恒等关系具有自反性，对称性，反对称性，传递性。（T）6、若f、g分别是单射,则gf是单射。（T）7、若gf是满射，则g是满射。（F）8、若AB，则)()(APBP。（T）9、若R具有自反性，则1R也具有自反性。（T）10、BA并且BA不可以同时成立。（F）四、计算题（共3小题，每题10分，共30分）1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问（１）三门课程都不选的学生有多少？（２）只选修计算机课程的学生有多少？-3-1、解：设A：选数学课程，B：选计算机课程，C：选商贸课程。文氏图如下所示：则(1)三门课都不会选修的人有：260-(64+94+58)+(28+26+22)-14=106。(2)只选修计算机课程的学生有：94-12-14-8=60。2、给定解释I如下：(a)个体域D={3,4};(b)f(x)为f(3)=4,f(4)=3;(c)F(x,y)为F(3,3)=F(4,4)=0,F(3,4)=F(4,3)=1。求公式)))(),((),((yfxfFyxFyx在I下的真值。解:由消去量词不等式得：)))(),((),((yfxfFyxFyx(F(3,3)F(f(3),f(3)))(F(4,3)F(f(4),f(3)))(F(3,4)F(f(3),f(4)))(F(4,4)F(f(4),f(4)))(00)(11)(11)(00)1所以公式在I下的真值为1。3、设A={1,2,3}，求A上所有的等价关系。解：A的所有划分如下：π1={{1}，{2,3}}；π2={{2}，{1,3}}；π3={{3}，{1,2}}；π4={{1,2,3}}；π5={{1},{2},{3}}。则对应的等价关系如下:-4-R1={2,3,3,2}∪IA；R2={1,3,3,1}∪IA；R3={1,2,2,1}∪IA；R4=EA；R5=IA。五、证明题（共3小题，每题10分，共30分）1、符号化下列命题，并证明其有效性：三角函数都是都是周期函数；一些三角函数是连续函数。所以一些周期函数是连续函数。证明：设P(x)：x是三角函数；Q(x)：x是周期函数；S(x)：x是连续函数。上述句子符号化为：前提：))()((xQxPx、))()((xSxPx结论：))()((xSxQx①))()((xSxPxP②)()(aSaPES①③))()((xQxPxP④)()(aQaPUS②⑤)(aPT①化简⑥)(aST①化简⑦)(aQT④⑤假言推理⑧)()(aQaST⑥⑦合取⑨)()((xQxSxEG⑧2、设R表示Z×Z上的二元关系，当且仅当xy=uv时，便有x,yRu,v。证明R是Z×Z上的等价关系。证明：(1)自反性：对任意的x,yZ×Z，有xyxy，所以yxRyx,,R自反；(2)对称性：对任意的x,y,u,vZ×Z,若vuRyx,,uvxyxyuvyxRvu,,R对称；(3)传递性：对任意的对任意的x,y,u,v,w,tZ×Z,若vuRyx,,且twRvu,,uvxy且wtuvwtxy-5-twRyx,,R传递；所以R是等价关系。3、设yxyxyxfRRRRf,),(,:，证明f是双射函数。证明：（1）满射性：2,2,,vuvuRRvu使得vuvuvuf,)2,2(f满射。（2）单射性：RRvuyx,,,，有vuvuyxyxvufyxf,,),(),(vuyxvuyx,vyux,vuyx,,f单射综上所述，f双射。