2025年山大离散数学期末试题及答案

2025年山大离散数学期末试题及答案一、选择题（每题3分，共30分）1.设集合\(A=\{1,2,3\}\)，\(B=\{2,3,4\}\)，则\(A\capB\)等于（）A.\(\{1,2,3,4\}\)B.\(\{2,3\}\)C.\(\{1,4\}\)D.\(\varnothing\)答案：B。根据交集的定义，\(A\capB\)是由既属于\(A\)又属于\(B\)的所有元素组成的集合，所以\(A\capB=\{2,3\}\)。2.命题公式\((p\landq)\top\)是（）A.重言式B.矛盾式C.可满足式D.以上都不对答案：A。通过真值表法，列出\((p\landq)\top\)的真值表：|\(p\)|\(q\)|\(p\landq\)|\((p\landq)\top\)||---|---|---|---||\(T\)|\(T\)|\(T\)|\(T\)||\(T\)|\(F\)|\(F\)|\(T\)||\(F\)|\(T\)|\(F\)|\(T\)||\(F\)|\(F\)|\(F\)|\(T\)|对于命题变元\(p\)和\(q\)的所有可能赋值，公式的值都为真，所以该命题公式是重言式。3.设\(R\)是集合\(A\)上的等价关系，\(A=\{1,2,3\}\)，\(R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}\)，则\(A\)中元素\(3\)所在的等价类\([3]_R\)为（）A.\(\{1\}\)B.\(\{2\}\)C.\(\{3\}\)D.\(\{1,2,3\}\)答案：C。根据等价类的定义，对于集合\(A\)上的等价关系\(R\)，元素\(a\)所在的等价类\([a]_R=\{x\inA|(a,x)\inR\}\)。对于元素\(3\)，满足\((3,x)\inR\)的\(x\)只有\(3\)本身，所以\([3]_R=\{3\}\)。4.无向图\(G=(V,E)\)中，顶点\(v\)的度数\(d(v)\)是指（）A.与\(v\)相邻的顶点数B.与\(v\)关联的边数C.从\(v\)出发的边数D.到达\(v\)的边数答案：B。在无向图中，顶点的度数是指与该顶点关联的边的数目。5.设\(f:A\toB\)是一个函数，若对于任意的\(y\inB\)，都存在\(x\inA\)使得\(f(x)=y\)，则称\(f\)是（）A.单射B.满射C.双射D.以上都不对答案：B。满射的定义就是对于函数\(f:A\toB\)，\(B\)中的每一个元素在\(A\)中都有原像，即对于任意的\(y\inB\)，都存在\(x\inA\)使得\(f(x)=y\)。6.设\(G\)是一个\(n\)阶无向连通图，其边数为\(m\)，则\(m\)满足（）A.\(m\geqn-1\)B.\(m\leqn-1\)C.\(m=n-1\)D.\(m=n\)答案：A。根据无向连通图的性质，一个\(n\)阶无向连通图至少有\(n-1\)条边，当它是树时边数恰好为\(n-1\)，所以\(m\geqn-1\)。7.谓词公式\(\forallx(P(x)\toQ(x))\)中，\(\forallx\)的辖域是（）A.\(P(x)\)B.\(Q(x)\)C.\(P(x)\toQ(x)\)D.整个公式答案：C。在谓词公式中，量词后面括号内的公式就是该量词的辖域，所以\(\forallx\)的辖域是\(P(x)\toQ(x)\)。8.设\(A=\{a,b,c\}\)，\(A\)上的幂集\(\mathcal{P}(A)\)的元素个数为（）A.3B.6C.8D.9答案：C。若集合\(A\)有\(n\)个元素，则其幂集\(\mathcal{P}(A)\)的元素个数为\(2^n\)。因为\(A\)中有\(3\)个元素，所以\(\mathcal{P}(A)\)的元素个数为\(2^3=8\)。9.设\(G\)是一个有\(n\)个顶点的简单图，若\(G\)中任意两个不相邻的顶点的度数之和大于等于\(n-1\)，则\(G\)是（）A.欧拉图B.哈密顿图C.平面图D.二分图答案：B。根据哈密顿图的判定定理，若\(G\)是一个有\(n\)个顶点的简单图，且\(G\)中任意两个不相邻的顶点的度数之和大于等于\(n-1\)，则\(G\)是哈密顿图。10.设\(S=\{1,2,3\}\)，\(S\)上的运算\(\ast\)定义为：\(a\astb=\max\{a,b\}\)，则\((S,\ast)\)是（）A.半群B.独异点C.群D.阿贝尔群答案：A。-封闭性：对于任意\(a,b\inS\)，\(a\astb=\max\{a,b\}\inS\)，满足封闭性。-结合律：设\(a,b,c\inS\)，\((a\astb)\astc=\max\{\max\{a,b\},c\}=\max\{a,b,c\}\)，\(a\ast(b\astc)=\max\{a,\max\{b,c\}\}=\max\{a,b,c\}\)，满足结合律。但不存在单位元，所以\((S,\ast)\)是半群。二、填空题（每题3分，共15分）1.设集合\(A=\{1,2,3\}\)，\(B=\{2,3,4\}\)，则\(A\cupB=\)______。答案：\(\{1,2,3,4\}\)。根据并集的定义，\(A\cupB\)是由所有属于\(A\)或者属于\(B\)的元素组成的集合。2.命题公式\(\neg(p\landq)\)等价于______。答案：\(\negp\lor\negq\)。这是根据德摩根律，\(\neg(p\landq)\equiv\negp\lor\negq\)。3.设\(R\)是集合\(A=\{1,2,3\}\)上的关系，\(R=\{(1,2),(2,3),(3,1)\}\)，则\(R\)的传递闭包\(t(R)=\)______。答案：\(\{(1,2),(2,3),(3,1),(1,3),(2,1),(3,2),(1,1),(2,2),(3,3)\}\)。可以通过Warshall算法或者逐步推导来计算传递闭包。例如，因为\((1,2)\inR\)且\((2,3)\inR\)，所以\((1,3)\int(R)\)等。4.设无向图\(G\)有\(n\)个顶点，\(m\)条边，且\(G\)是连通图，则\(G\)的生成树有______条边。答案：\(n-1\)。连通图的生成树是一个连通且无回路的子图，对于\(n\)个顶点的无向连通图，其生成树的边数为\(n-1\)。5.设\(f:\mathbb{Z}\to\mathbb{Z}\)定义为\(f(x)=2x+1\)，则\(f\)是______（单射、满射、双射）。答案：单射。-单射证明：假设\(f(x_1)=f(x_2)\)，即\(2x_1+1=2x_2+1\)，移项可得\(2x_1=2x_2\)，从而\(x_1=x_2\)，所以\(f\)是单射。-满射判断：对于任意的\(y\in\mathbb{Z}\)，若\(y=2x+1\)，则\(x=\frac{y-1}{2}\)，当\(y\)为偶数时，\(x\notin\mathbb{Z}\)，所以\(f\)不是满射，也就不是双射。三、简答题（每题10分，共30分）1.画出集合\(A=\{1,2,3,4\}\)上的整除关系\(R\)的哈斯图，并指出该偏序集的极大元、极小元、最大元和最小元。解：-首先确定整除关系\(R=\{(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)\}\)。-哈斯图的绘制：将\(1\)画在最底层，\(2\)和\(3\)画在第二层，\(4\)画在第三层，\(1\)分别与\(2\)、\(3\)、\(4\)有连线，\(2\)与\(4\)有连线。-极大元：\(3\)，\(4\)。极大元是指在偏序集中没有比它更大的元素与之可比的元素。-极小元：\(1\)。极小元是指在偏序集中没有比它更小的元素与之可比的元素。-最大元：无。因为不存在一个元素能大于等于集合中的所有元素。-最小元：\(1\)。因为\(1\)小于等于集合中的其他所有元素。2.已知有向图\(G=(V,E)\)，其中\(V=\{v_1,v_2,v_3,v_4\}\)，\(E=\{(v_1,v_2),(v_2,v_3),(v_3,v_4),(v_4,v_1)\}\)，判断该有向图是否为强连通图、单向连通图和弱连通图，并说明理由。解：-强连通图：对于有向图\(G\)中任意两个顶点\(u\)和\(v\)，都存在从\(u\)到\(v\)的路径和从\(v\)到\(u\)的路径。在该有向图中，\(v_1\tov_2\tov_3\tov_4\tov_1\)，任意两个顶点之间都可以相互到达，所以该有向图是强连通图。-单向连通图：若对于有向图\(G\)中任意两个顶点\(u\)和\(v\)，至少存在从\(u\)到\(v\)或者从\(v\)到\(u\)的路径。因为是强连通图，必然满足单向连通图的条件，所以该有向图是单向连通图。-弱连通图：将有向图的边视为无向边后得到的无向图是连通的。把该有向图的边视为无向边后，得到的无向图是连通的，所以该有向图是弱连通图。3.用谓词逻辑符号化下列命题：“所有的大学生都喜欢学习，有的大学生喜欢运动”。解：设\(S(x)\)表示“\(x\)是大学生”，\(L(x)\)表示“\(x\)喜欢学习”，\(P(x)\)表示“\(x\)喜欢运动”。-“所有的大学生都喜欢学习”可符号化为\(\forallx(S(x)\toL(x))\)。-“有的大学生喜欢运动”可符号化为\(\existsx(S(x)\landP(x))\)。所以整个命题可符号化为\(\forallx(S(x)\toL(x))\land\existsx(S(x)\landP(x))\)。四、证明题（每题10分，共20分）1.证明：\((p\toq)\land(q\tor)\to(p\tor)\)是重言式。证明：方法一：真值表法列出\((p\toq)\land(q\tor)\to(p\tor)\)的真值表：|\(p\)|\(q\)|\(r\)|\(p\toq\)|\(q\tor\)|\((p\toq)\land(q\tor)\)|\(p\tor\)|\((p\toq)\land(q\tor)\to(p\tor)\)||---|---|---|---|---|---|---|---||\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)||\(T\)|\(T\)|\(F\)|\(T\)|\(F\)|\(F\)|\(F\)|\(T\)||\(T\)|\(F\)|\(T\)|\(F\)|\(T\)|\(F\)|\(T\)|\(T\)||\(T\)|\(F\)|\(F\)|\(F\)|\(T\)|\(F\)|\(F\)|\(T\)||\(F\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)||\(F\)|\(T\)|\(F\)|\(T\)|\(F\)|\(F\)|\(T\)|\(T\)||\(F\)|\(F\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)||\(F\)|\(F\)|\(F\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|对于命题变元\(p\)、\(q\)和\(r\)的所有可能赋值，公式的值都为真，所以该命题公式是重言式。方法二：逻辑等价推导\((p\toq)\land(q\tor)\to(p\tor)\)\(\equiv\neg((\negp\lorq)\land(\negq\lorr))\lor(\negp\lorr)\)（根据蕴含等值式）\(\equiv(\neg(\negp\lorq)\lor\neg(\negq\lorr))\lor(\negp\lorr)\)（根据德摩根律）\(\equiv((p\land\negq)\lor(q\land\negr))\lor(\negp\lorr)\)（根据德摩根律）\(\equiv(p\land\negq)\lor(q\land\negr)\lor\negp\lorr\)\(\equiv((p\land\negq)\lor\negp)\lor((q\land\negr)\lorr)\)\(\equiv((p\lor\negp)\land(\negq\lor\negp))\lor((q\lorr)\land(\negr\lorr))\)（根据分配律）\(\equiv(T\land(\negq\lor\negp))\lor((q\lorr)\landT)\)\(\equiv\negq\lor\negp\lorq\lorr\)\(\equiv(\negq\lorq)\lor\negp\lorr\)\(\equivT\lor\negp\lorr\)\(\equivT\)所以该命题公式是重言式。2.设\(G=(V,E)\)是一个无向连通图，\(T\)是\(G\)的一棵生成树，证明：\(G\)中任意一条不属于\(T\)的边\(e\)与\(T\)构成一个唯一的回路。证明：-存在性：设\(e=(u,v)\)是\(G\)中不属于\(T\)的边。因为\(T\)是\(G\)的生成树，所以\(T\)是连通的，在\(T\)中存在从\(u\)到\(v\)的唯一路径\(P\)。那么边\(e\)与路径\(P\)就构成了一个回路\(C\)。-唯一性：假设存在两个不同的回路\(C_1\)和\(C_2\)都由边\(e\)与\(T\)构成。那么\(C_1-e\)和\(C_2-e\)是\(T\)中两条不同的从\(u\)到\(v\)的路径，这与树中任意两个顶点之间存在唯一路径相矛盾。所以\(G\)中任意一条不属于\(T\)的边\(e\)与\(T\)构成一个唯一的回路。五、应用题（15分）某公司要在\(A\)、\(B\)、\(C\)、\(D\)四个城市之间建立通信网络，已知各城市之间铺设线路的费用如下表所示：||\(A\)|\(B\)|\(C\)|\(D\)||---|---|---|---|---||\(A\)|0|3|4|7||\(B\)|3|0|5|6||\(C\)|4|5|0|2||\(D\)|7|6|2|0|请用Pr