离散数学样卷

《离散数学》样卷一、单选题（共20分）1．下列命题公式中，是重言式的是____________。A．Ø(ØpÚq)ÙqB.(p®q)«(ØpÚq)C.p∧qD.p®q2．设A、B、C为任意集合，下面命题为真的____________。A．A－(B∪C)＝(A－B)∩(A－C)B.若AÍB，则有~AÍ~BC.~(A∪B)=~A∪~BD.~(A∩B)=~A∩~B3．2个顶点非同构的无向树有__________棵。A.1B.2C.3D.44．含有3个元素的集合共有____C______不同的划分.A.3B.4C.5D.65．S是具有3个元素的集合，在S上可定义___________种不同的二元关系。A．512B.256C.128D.816．设A、B是集合，右图的文氏图的阴影部分的区域可用________表达式表示A.A∩BB.A∪BC.A-BD.(A∪B)-(A∩B)7．下面函数（）是单射而非满射。A、；B、；C、；D、。其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。8．用2面红旗、3面黄旗依次悬挂在一根旗杆中，可以组成____________种不同的标志。A.10B.12C.120D.249．下列各数组中，不能构成无向图度数列的是__________。A．1，1，1，2，3；B.2,2,2,2,2C.3,3,3,3D.1，2，3，4，510．一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有______4度结点。A、1；B、2；C、3；D、4。二、填空题（共20分）1．设p、q的真值为0；r的真值为1，则命题公式：p∨(q∧r)的真值是______________。2．设解释I为：个体域DI={2,3}，一元谓词F(x):F(2)=0,F(3)=1；G(x,y):G(i,j)=1,(i,j=2,3)在解释I下，公式："x(F(x)ÙG(x,2))的真值为_________________。3．已知无向树T中,有1个3度顶点,2个2度顶点,其余顶点全是树叶.则它有_____片树叶.4．若一个无向图中共有12条边，各顶点度数相同，则此图有_______________个顶点。5.画一个无向欧拉图，它有偶数个顶点和偶数条边。6．右图的平面嵌入中，面次为____________，次数最高的面的次数为____________。7．在n元集A上定义的二元关系中有_________个自反关系。三．计算题（20分）1．求命题公式：(pØ®q)®r的主析取范式和成真赋值。2.设A={a,b,c,d,e}，R={<a,b>,<b,c>,<d,c>,<c,d>,<b,e>,<e,e>}，求R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)。3.设f,g,h∈NN，且有求f∘f,g∘f,f∘g,h∘f,f∘g∘h。4.有向图D如图所示,求A,A2,A3,A4,求：D中长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？四．证明题（共20分）1．用等值演算法证明等值式：¬（A«B）Û（A∨B）∧¬（A∧B）2.证明：任何无向连通图都有生成树.3.证明：若R，S是对称的，则R∪S也是对称的。4.证明：设G为n阶m条边r个面的连通平面图，则n-m+r=2.五．应用题（共20分）1．符号化下面命题，并用谓词逻辑构造其推证结论的过程：每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科学生。2．求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？3.设A={1,2,3,4,5,6,7,8},A上的关系R如下定义：R={<x,y>|x,y∈A∧x≡y(mod3)}证明R为等价关系，并求A/R。4.已知如下图所示项目网络图，求(1)关键路径；(2)v0到v5的最短距离5.在通信中，设八进制数字出现的频率如下：0：25%，1：20%，2：15%，3：10%，4：10%，5：