《离散数学（上）》试卷第1页共4页《离散数学（上）》考试试卷（B卷）（时间120分钟）院/系专业姓名学号题号一二三四五总分得分一、单选题（每小题2分，共20分）1.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为()A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q2.设个体域为{,}Dab,(,)(,)0FaaFab,(,)(,)1FbaFbb,则下列公式为真的是(）A.(,)xyFxy；B.(,)xyFxy；C.(,)xyFxy；D.(,)xyFxy?。3.设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于()A.(x)A(x)→BB.(x)A(x)→BC.A(x)→BD.(x)A(x)→(x)B4.对任意集合CBA,,，下列各式中一定成立的是（）A.)()()(CABACBA；B.)()()(CABACBA；C.)()()(CABACBA；D.)()(CBACBA。5.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是()A.R∪IAB.RC.R∪{〈c,a〉}D.R∩IA6.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取()A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}7.下列式子正确的是()A.∈B.C.{}D.{}∈8.以下命题公式中，为永假式的是()A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)9.设1和2是非空集合A的划分，则下列集合一定是A的划分的是（）A.12B.12C.12D.1211()10.设N和R分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合是（）A.RB.NNC.()ND.nN（nN）得分《离散数学（上）》试卷第2页共4页二、判断题（每小题2分，共10分。对的打√，错的打×）1.（）命题联结词集合{，，}是最小的全功能联结词集。2.（）（（PQ）（QR））（PR）为重言式。3.（）R是A上的二元关系，R是自反的，当且仅当r(R)=R。4.（）集合A上的等价关系确定了A的一个划分。5.（）R是集合A上的关系，R有传递性的充要条件是RoRR。三、填空题（每小空2分，共20分）1.设R是I上模2同余关系，则R对应的等价类有＿＿＿＿＿＿＿＿＿，＿＿＿＿＿＿＿＿＿＿＿。2.命题{{a}}{{a},3,4,1}的真值=____。3.公式))(),(()),()((xSzyRzyxQxPx的自由变元是,约束变元是。4.n个命题变元的真值有＿＿＿种不同的组合；n个命题变元可构造＿＿＿个不同的主析取范式。5.集合{1,2,3,4}A上有＿＿＿个不同的二元关系，＿＿＿个不同的等价关系。6.集合A上的关系{1,2,2,1,2,3}的传递闭包为＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。四、计算题（每小题10分，共30分）1.先化简含P、Q、R三个命题变元的命题公式G:((PQ)(PR))P，然后求G的主析取范式和主合取范式。2.设R是集合{1,2,3,4,5}A上的关系得分得分得分《离散数学（上）》试卷第3页共4页{(1,1),(1,3),(2,2),(2,5),(3,1),(3,3),(4,4),(5,2),(5,5)}R（1）画出R的关系图;（2）证明R是等价关系；（3）写出R的所有等价类。3.设,AR为偏序集，其中}20,,6,4,2{A，R是A上整除关系。(1)画出,AR的哈斯图；(2)求A的极大元和极小元；(3)令}12,8,6{B，求B的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界。五、证明题（每小题10分，共20分）得分《离散数学（上）》试卷第4页共4页1.设I为整数集合，函数:fIIII定义为：yxyxyxf*,),(，证明：f是单射的但不是满射的。2.用推理规则证明：{P∨Q,P→R,Q→S,R→(P∧Q)}蕴涵S。《离散数学（上）》参考答案第1页共2页安徽大学2009—2010学年第1学期《离散数学（上）》考试试题（B卷）参考答案及评分标准一、单选题（每小题2分，共20分）1.B；2.A；3.A；4.C；5.C；6.D；7.B；8.C；9.D；10.D。二、判断题（每小题1分，共10分。对的打√，错的打×）1.×；2.√；3.√；4.√；5.√。三、填空题（每小空2分，共20分）1.20或,2,0,2,,21或,3,1,1,3,；2.T或真或1；3.y,x；x,z；4.2n；22n；5.162或65536；15；6.{1,1,1,2,1,3,2,1,2,2,2,3}。四、计算题（每小题10分，共30分）1.化简命题公式G((PQ)(PR))P((PQ)(PR))P2分((PQ)(PR))P2分(PQ)(PR)P((PQ)P)(PR)P(PR)P2分G(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)(主析取范式)2分m4∨m5∨m6∨m77,6,5,43,2,1,0M0∧M1∧M2∧M3(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)(主合取范式)2分2.{(1,1),(1,3),(2,2),...
