离散数学复习规范.doc

2008年离散数学试题 一、单项选择题(本大题共15小题，每小题1分，共15分) 1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（　　　） A.(P∧Q B.(P→Q C.(P→(Q D.P→(Q 2.下列命题联结词集合中，是最小联结词组的是（　　　） A.{(， } B.{(，∨，∧} C.{(，∧} D.{∧，→} 3.下列命题为假命题的是（　　　） A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 5.若个体域为整数减，下列公式中值为真的是（　　　） A.x(y(x+y=0) B.(yx(x+y=0) C.xy(x+y=0) D.((x(y(x+y=0) 6.下列命题中不正确的是（　　　） A.x∈{x}-{{x}} B.{x}({x}-{{x}} C.A={x}∪x,则x∈A且x(A D.A-B=((A=B 7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（　　　） A.P(Q B.P(Q C.Q(P D.Q=P 8.下列表达式中不成立的是（　　　） A.A∪(B(C)=(A∪B) ( (A∪C) B.A∩(B(C)=(A∩B) ( (A∩C) C.(A(B)×C=(A×C) ( (B×C) D.(A-B) ×C=(A×C)-(B×C) 10.下列集合对所给的二元运算封闭的是（　　　） A.正整数集上的减法运算 B.在正实数的集R+上规定(为a(b=ab-a-b a,b∈R+ C.正整数集Z+上的二元运算(为x(y=min(x,y) x,y∈Z+ D.全体n×n实可逆矩阵集合Rn×n上的矩阵加法 11.设集合A={1，2，3}，下列关系R中不是等价关系的是（　　　） A.R={1,1,2,2,3,3} B.R={1,1,2,2,3,3,3,2,2,3} C.R={1,1,2,2,3,3,1,2} D.R={1,1,2,2,3,3,1,2,2,1,1,3,3,1,2,3,3,2} 13.设集合A={a,b, c}上的关系如下，具有传递性的是（　　　） A.R={a,c,c,a,a,b,b,a} B.R={a,c,c,a} C.R={a,b,c,c,b,a,b,c} D.R={a,a} 14.含有5个结点，3条边的不同构的简单图有（　　　） A.2个 B.3个 C.4个 D.5个 15.设D的结点数大于1，D=V,E是强连通图，当且仅当（　　　） A.D中至少有一条通路 B.D中至少有一条回路 C.D中有通过每个结点至少一次的通路 D.D中有通过每个结点至少一次的回路 二、填空题 16.设A={1,2,3}，B={3,4,5}，则A(A=___________，A(B=___________。 17.设A={1,2,3,4,5}，R(A×A，R={1,2，3,4,2,2}，则R的自反闭包r(R)=__________。 对称闭包t(R)=__________。 18.设P、Q为两个命题，德摩根律可表示为_____________，吸收律可表示为____________。 19.对于公式x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,当论域为{1,2}时，其真值为_____________ ,当论域为{0,1,2}时，其真值为_____________。 21.3个结点可构成_________个不同构的简单无向图，可构成________个不同构的简单有向图。 23.设图GV,E,V={v1,v2,v3,v4},若G的邻接矩阵，则deg-(v1)=_ ________, deg+(v4)=____________。 25.给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={1,2,3,4,2,2}, S={4,2,2,5,3,1,1,3}，则，。 三、计算题 26.设A={a,b,c,d}，A上的等价关系R={a,b,b,a,c,d,d,c}∪IA，画出R的关系图，并求出A中各元素的等价类。 27.构造命题公式(（P∨Q） （(P∧Q）的真值表。 28.求下列公式的主析取范式和主合取范式：P→（（Q→P）∧（(P∧Q）） 29.设A={a, b, c, d, e}，R为A上的关系，R={a, d，a, c，a, b, a, e, b, e,c, e, d, e}∪IA，试画A，R的哈斯图，并求A中的最大元，最小元，极大元，极小元。 30.给定图G如图所示，（1）G中长度为4的路有几条？其中有几条回路？（2）写出G的