离散数学本科期末考试试题及答案

离散数学本科期末考试试题及答案考试时间：______分钟总分：______分姓名：______一、选择题（本大题共5小题，每小题3分，共15分。在每小题给出的四个选项中，只有一项是符合题目要求的。请将所选项前的字母填在答题卡相应位置。）1.设集合A={1,2,3,4}，B={2,4,6,8}，C={3,4,5,6}，则(A∪B)∩C=?(A){1,2,3,4,5,6}(B){2,4,5,6}(C){3,4,5,6}(D){2,4}2.下列关系式哪个是正确的？(A)<1,2>∈{(x,y)|x<y}(B)<2,1>∈{(x,y)|x≤y}(C){(1,2),(2,3)}是函数(D){(x,y)|x²+y²=1}是函数3.设函数f:Z→Z定义为f(x)=x+1，则f的逆函数f⁻¹(x)=?(A)x-1(B)x+1(C)-x+1(D)-x-14.下列命题形式中，哪个是永真式（重言式）？(A)(p∧¬q)→p(B)p→(p∨q)(C)(p→q)∧(q→p)(D)¬(p∧q)↔(¬p∨¬q)5.设有集合A和B，如果存在一个从A到B的bijection（双射），则称A和B具有相同的基数。下列哪个选项正确描述了可数无穷集？(A)自然数集N是不可数的。(B)有理数集Q是不可数的。(C)实数集R是可数的。(D)空集是可数的。二、填空题（本大题共5小题，每小题4分，共20分。请将答案填写在答题卡相应位置。）6.如果一个图G有n个顶点，m条边，且G是连通的，但不包含任何环路，则m=______。7.根据鸽巢原理，如果将10只鸽子放入9个鸽巢，那么至少有一个鸽巢中至少有______只鸽子。8.计算组合数C(10,6)=______。9.谓词逻辑公式∀x∃yP(x,y)的意思是______。10.设集合A={a,b,c}，则A上所有等价关系的个数是______。三、解答题（本大题共6小题，共65分。请将解答过程写在答题卡相应位置。）11.（10分）设A,B,C是集合，证明：若A⊆B且B⊆C，则A⊆C。（注：请使用集合公理化定义或已学过的集合性质进行证明）12.（10分）给定命题公式p,q,r。写出下列命题公式的析取范式（DisjunctiveNormalForm,DNF）和合取范式（ConjunctiveNormalForm,CNF）。(p∨q)→(r∧¬p)13.（10分）设G是一个无向图，顶点集V(G)={v₁,v₂,v₃,v₄,v₅}，边集E(G)={<v₁,v₂>,<v₁,v₃>,<v₂,v₄>,<v₃,v₄>,<v₄,v₅>}。(1)画出该图G。(2)求图G的邻接矩阵A。(3)计算矩阵A²，并解释A²中位于第2行第4列的元素a₂⁴的含义。14.（10分）一个班级有30名学生，其中18人喜欢数学，15人喜欢物理，10人既喜欢数学又喜欢物理。求：(1)只喜欢数学的人数。(2)只喜欢物理的人数。(3)至少喜欢数学或物理中一门的人数。(4)使用容斥原理进行计算，并解释其正确性。15.（15分）定义一个数列a₁,a₂,a₃,...如下：a₁=1,a₂=2，对于n≥3，aₙ=aₙ₋₁+aₙ₋₂。(1)写出这个数列的前10项。(2)证明对于所有n≥3，aₙ是偶数。（提示：可考虑用数学归纳法）16.（10分）解释什么是图G的生成树。给定一个连通无向图G（无需画出），假设G有n个顶点和m条边。写出G的生成树所具有的性质，并说明为什么G必须至少有n-1条边才能有生成树。试卷答案一、选择题1.B2.A3.A4.B5.B解析：1.(A∪B)={1,2,3,4,6,8},(A∪B)∩C={2,4,6}2.<1,2>满足x<y，故∈{(x,y)|x<y}。<2,1>不满足x≤y，故∉{(x,y)|x≤y}。{(1,2),(2,3)}中<1,2>和<2,3>的第一个分量不同，不是函数。{(x,y)|x²+y²=1}中如<0,1>和<0,-1>，第一个分量相同但第二个分量不同，不是函数。故选A。3.f(1)=2,f(2)=3,...,f(n)=n+1。f⁻¹(2)=1,f⁻¹(3)=2,...,f⁻¹(n)=n-1。即f⁻¹(x)=x-1。故选A。4.(p∧¬q)→p等价于¬(p∧¬q)∨p，根据德摩根律等价于¬p∨q∨p，根据幂等律等价于¬p∨q。此式为永真式。p→(p∨q)等价于¬p∨(p∨q)，根据结合律等价于¬p∨p∨q，根据幂等律等价于T（永真）。(p→q)∧(q→p)是p↔q，不是永真式。¬(p∧q)↔(¬p∨¬q)是p↔q的对偶式，也不是永真式。故选B。5.N和Q都是可数的（可列出其元素与N一一对应）。R是不可数的（康托尔diagonalargument证明）。空集是有限集，也是可数的。故选B。二、填空题6.n-1解析：对于一个连通无环图，任何添加一条边都不会形成环路。要使得图仍然无环，每次添加边必须连接两个不同的连通分支。从一个单点开始，每添加一条边将一个连通分支连接到已有图中，增加一个连通分支。因此，要连接n个顶点形成n个连通分支（每个顶点一个），需要添加n-1条边。这是树的基本性质。7.2解析：根据鸽巢原理，如果每个鸽巢最多有1只鸽子，那么最多能放9只鸽子。现在放了10只，多出1只鸽子，这只鸽子必须放入某个已经有鸽子的鸽巢中，导致该鸽巢至少有1+1=2只鸽子。或者计算：至少有1只鸽子在1个鸽巢，剩下9只鸽子在9个鸽巢，鸽巢原理说明至少有一个鸽巢有9只，另一个有1只，总数至少为9+1=10只。再放1只，至少有一个鸽巢变成10+1=11只。但题目问的是“至少”，根据最坏情况，将10只鸽子分到9个鸽巢，鸽巢原理保证至少有一个鸽巢至少有⌈10/9⌉=2只鸽子。8.210解析：C(10,6)=C(10,4)=10!/(6!*4!)=(10*9*8*7)/(4*3*2*1)=10*3*7=210。9.对于所有x，存在一个y使得P(x,y)为真。解析：∀x∃yP(x,y)的标准翻译是"Forallx,thereexistsaysuchthatP(x,y)holdstrue."这表示该谓词关系P在其定义域内对于任意元素x，总能找到至少一个元素y满足P(x,y)的条件。10.8解析：集合A={a,b,c}有3个元素。一个等价关系是A×A的一个划分。A×A有3²=9个元素{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)}。要形成一个划分，需要将这9个元素分成非空子集（块），且各块内部元素视为等价。等价关系R必须包含对角线元素，即(a,a),(b,b),(c,c)必须在同一块。剩下的6个元素{(a,b),(a,c),(b,a),(b,c),(c,a),(c,b)}可以任意配对形成块（配对数为C(6,2)），或者单独成块，或者任意组合。计算方法：先固定对角线元素为一块，有1种方式。然后对剩余6个元素进行划分。6个元素分成非空集合的划分数为Bell数B₃=15。但B₃计算了包含空集的情况，实际等价关系数是Stirling数S(6,1)+S(6,2)+S(6,3)=1+15+60=76。或者更直接地，考虑非对角线元素的配对方式。将6个元素分成0个2元素块（即6个单元素块）：C(6,0)*1=1种。分成1个2元素块和4个单元素块：C(6,2)*1=15种。分成2个2元素块和2个单元素块：C(6,2)*C(4,2)/2!=15*6/2=45种（除以2!是因为两个2元素块是无序的）。分成3个2元素块：C(6,2)*C(4,2)*C(2,2)/3!=15*6*1/6=15种（除以3!是因为三个2元素块是无序的）。分成4个2元素块：C(6,2)*C(4,2)*C(2,2)/4!=15*6*1/24=3.75（非整数，不可能）。分成5个2元素块：不可能。分成6个2元素块：不可能。总计：1+15+45+15=76。但更常见的简化计算是考虑对角线固定后，6个非对角线元素形成的等价类数等于2的6次方减去分离情况（即每个元素自成一类，只有对角线连接），或者直接计算2^(n(n-1)/2)，这里n=3,2^(3*2/2)=2^3=8。这个8是指对角线元素形成1块，非对角线6个元素形成k块，k可以为0,1,2,3,4,5,6。故8种。三、解答题11.证明：假设A⊆B且B⊆C。根据集合包含的定义，对于任意元素x，如果x∈A，则x∈B。又因为x∈B且B⊆C，所以x∈C。由于x的任意性，这说明对于任意x∈A，都有x∈C。根据集合包含的定义，A⊆C。证毕。12.DNF:(p∧¬q)∨(p∧r∧¬p)∨(¬p∧q∧r)CNF:(p∨¬q∨r)∧(¬p∨q∨r)解析：(1)(p∨q)→(r∧¬p)等价于¬(p∨q)∨(r∧¬p)（蕴涵式转化）等价于(¬p∧¬q)∨(r∧¬p)（德摩根律）这是析取范式，也是合取范式。(2)析取范式(DNF)：要求是合取项（与项）的析取（或项）。即(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧¬r)∨(¬p∧q∧r)∨(p∧¬q∧¬r)∨(p∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r)。合取范式(CNF)：要求是析取项（或项）的合取（与项）。即(¬p∨¬q∨¬r)∧(¬p∨¬q∨r)∧(¬p∨q∨¬r)∧(¬p∨q∨r)∧(p∨¬q∨¬r)∧(p∨¬q∨r)∧(p∨q∨¬r)∧(p∨q∨r)。（注：题目中的公式(p∨q)→(r∧¬p)与给出的DNF/CNF结构似乎不一致，这里按标准转换方法给出结果。如果题目意图是求原公式的DNF/CNF，则需要先化简公式。）13.(1)```v1--1--v2\|\/\/1--1--v4||1//v3--1--v5```(2)邻接矩阵A(V(G)={v1,v2,v3,v4,v5}):A=|01100||10010||00010||01101||00010|(3)A²=A*A:A²=|01100||01100||21110||10010|*|10010|=|11110||00010||00010||11110||01101||01101||12211||00010||00010||11110|A²中位于第2行第4列的元素a₂⁴=1。根据邻接矩阵的定义，aᵢⱼ表示顶点vᵢ到顶点vⱼ的长度为2的路径的数量。a₂⁴=1表示从顶点v₂到顶点v₄存在长度为2的路径。查看图：v₂--1-->v₄(长度1)和v₂--1-->v₃--1-->v₄(长度2)。确实存在一条长度为2的路径v₂-v₃-v₄。因此a₂⁴=1。14.(1)只喜欢数学的人数=喜欢数学的人数-既喜欢数学又喜欢物理的人数=18-10=8人。(2)只喜欢物理的人数=喜欢物理的人数-既喜欢数学又喜欢物理的人数=15-10=5人。(3)至少喜欢数学或物理中一门的人数=总人数-既不喜欢数学也不喜欢物理的人数=总人数-(总人数-喜欢数学的人数-喜欢物理的人数+既喜欢数学又喜欢物理的人数)=30-(30-18-15+10)=30-7=23人。或者使用容斥原理：|M∪P|=|M|+|P|-|M∩P|=18+15-10=23人。