河南电大离散数学期末复习题(历年考试题)

离散数学试题第1页共6页试卷代号：7737座位号河南广播电视大学2007-2008学年度第二学期期末考试离散数学试题2008年7月一、选题：在下列各题的备选答案中选择一个正确的。（每小题3分，共15分）1.下列各命题中正确的是A{a}∈{a,b,c,d};B{a}{a,b,c,d}Cф∈{a,b,c,d},D{a,b}∈{a,b,c,{a,b,c}}2.已知在集合A={1，2，3，4}上的二元关系R={（1，2），（2，3），（2，4），（3，4）},则R具有A自反性B对称性C传递性D以上都不对3.设命题公式G=P∧（乛QVR）则使G取真值为1的解释是A（0,1,0）B（1,0,0）C（0,1,1）D（1,1,0）4.设定义域是整数集,下列公式中真值为1的是A．)0(yxyxB.)0(yxxy)0(yxyxD.)0(yxyx5．设G是连通的平面图，有５个顶点，６个面，则G的边数是A．5B.6C.9D.11题号一二三四总分分数得分评卷人离散数学试题第2页共6页二、填空题：（每空3分，共36分）6．设集合A={a，b，d}，B={c，d}，则A∪B=__________，A∩B=__________，A-B=__________．7．设数在集合A={a,b,c,d}上的二元关系R={(a,a),(a,b),(b,d)},则R2=_______,R-1=________.8．合B上的等价关系P具有__________性，__________性和__________性．9．题公式H=Q→（R→S），则使公式H为假的解释是__________、__________、__________．10．一阶逻辑公式()(,)xyPxQxy的前束范式是三、计算题：（四小题共40分）11．（10分）。已知在集合A={1，2，3，4，5}上的二元关系R={（1，2），（3，4），（2，2）},S={（4，2），（2，5），（3，1），（1，3）},试求R·S，S·R，R2，S2,R(S·R)得分评卷人得分评卷人离散数学试题第3页共6页1(10分)设集合M={1，2，3，4，5},σ和τ是M上的两个置换：1234512345σ=τ=34521432511〉判断σ和τ的奇偶性；2〉把σ和τ分别写成对换的乘积；3〉用轮换形式写出στ,τσ。13．（10分）将公式G=乛（PVQ）（P∧Q）化为析取范式,合取范式。14．（10分）将一阶逻辑公G=xy(彐z(P(x,z)∧P(y,z))彐uQ(x,y,u)化为前束范式。离散数学试题第4页共6页四（9分）15．设有五个城市,u1，u2...u5,任意两城市之间的公路造价如下表（百万元），试求连接五个城市且造价最低的公路网，且求出最低造价。试卷代号：7737河南广播电视大学2007-2008学年度第二学期期末考试离散数学试题答案及评分标准2008年7月一、单选题：在下列各题的备选答案中选择一个正确的。（每题3分，共18分）1．B；2。D；3。B；4A；5。C。得分评卷人U1U2U3U4U5U1U2U3U4U50471610401381771303101683012101710120离散数学试题第5页共6页二、填空：（每题3分，共24分）6．{abcd},{d},{a,b}7.{(aa)(ab)(ad)},{(aa)(ba)(db)}8.自反，对称，传递。9。（101）（111）（100）10..,xyPxQxy三、计算题：（每题10分，共50分）11．（12分）解：RS=｛（1，5），（3，2），（2，5）｝；SR=｛（4，2），（3，2），（1，4）｝R2=｛（1，2），（2，2）｝；S2=｛（4，5），（3，3），（1，1）｝；R（SR）=｛（3，2）12．（16分）解：（2）23145.....,24135。（1）都是奇置换。（3）.12543.......;1253413．（12分）解：原式=QPPQQQQPPQPPQQPPQPQPQPQPQPQPQPQPQPQPQPQPQPQP………合取范式…………析取范式14．（10分）。解：原式=uyxQzyPzxPuyxQzyPzxPuyxQzyPzxPuyxQzyPzxPuzyxuzyxuzyxuzyx,,,,,,,,,,,,,,,,离散数学试题第6页共6页四、(8分)·u1410·u27·u5·u33·u4则最低造价为：3+4+7+10=24。