离散数学期中试卷及答案

离散数学期中试卷及答案一、选择题（每题2分，共20分）1.集合{1,2,3}的子集个数是（）。A.3B.4C.7D.8答案：D2.命题“若x>0，则x²>0”的逆否命题是（）。A.若x²≤0，则x≤0B.若x²>0，则x>0C.若x≤0，则x²≤0D.若x²≤0，则x≤0答案：A3.函数f:A→B是单射的，当且仅当（）。A.f(A)=BB.f是满射C.对于任意的x₁,x₂∈A，若x₁≠x₂，则f(x₁)≠f(x₂)D.对于任意的y∈B，存在唯一的x∈A，使得f(x)=y答案：C4.以下哪个图是连通图（）。A.一个有5个顶点的环图B.一个有5个顶点的路径图C.一个有5个顶点的完全图D.一个有5个顶点的星形图答案：C5.若一个图G是二分图，则（）。A.G中不存在奇数环B.G中不存在偶数环C.G中不存在环D.G中存在奇数环答案：A6.以下哪个命题是真命题（）。A.所有的鸟都会飞B.所有的金属都是导电的C.所有的人都是自私的D.所有的水都是有毒的答案：B7.以下哪个命题是假命题（）。A.存在一个实数x，使得x²=1B.对于所有的实数x，x²≥0C.存在一个实数x，使得x²=-1D.对于所有的实数x，x²+x+1>0答案：C8.以下哪个命题是永真命题（）。A.p∧(¬p)B.p∨(¬p)C.p→(p∧q)D.p→(¬p)答案：B9.以下哪个命题是永假命题（）。A.p∧(¬p)B.p∨(¬p)C.p→(p∧q)D.p→(¬p)答案：A10.以下哪个命题是矛盾命题（）。A.p∧(¬p)B.p∨(¬p)C.p→(p∧q)D.p→(¬p)答案：A二、填空题（每题2分，共20分）1.集合{1,2,3}的幂集是{∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}。2.命题“若x>0，则x²>0”的逆命题是“若x²>0，则x>0”。3.函数f:A→B是满射的，当且仅当对于任意的y∈B，存在至少一个x∈A，使得f(x)=y。4.一个图是连通的，当且仅当图中任意两个顶点之间都存在路径。5.一个图是二分图，当且仅当该图的顶点可以被分成两个不相交的集合，使得每条边的两个端点分别属于这两个集合。6.命题“所有的鸟都会飞”的否定是“存在一个鸟不会飞”。7.命题“所有的金属都是导电的”的否定是“存在一个金属不导电”。8.命题“存在一个实数x，使得x²=1”的否定是“对于所有的实数x，x²≠1”。9.命题“对于所有的实数x，x²≥0”的否定是“存在一个实数x，使得x²<0”。10.命题“存在一个实数x，使得x²=-1”的否定是“对于所有的实数x，x²≠-1”。三、解答题（每题10分，共60分）1.证明：若一个图G是二分图，则G中不存在奇数环。证明：假设G中存在一个奇数环C。由于G是二分图，我们可以将G的顶点分成两个不相交的集合U和V，使得每条边的两个端点分别属于U和V。由于C是一个奇数环，我们可以从C中的任意一个顶点出发，沿着C的边走一圈，最终回到出发点。在这个过程中，我们会发现，我们从一个集合出发，经过奇数次边后，回到了另一个集合。这与我们的假设矛盾，因为我们在经过奇数次边后，应该回到原来的集合。因此，我们的假设不成立，G中不存在奇数环。2.证明：若一个图G是连通图，则G中任意两个顶点之间都存在路径。证明：假设G中存在两个顶点u和v，它们之间不存在路径。由于G是连通图，我们可以从任意一个顶点出发，沿着G的边走，最终到达G中的任意一个顶点。但是，由于u和v之间不存在路径，我们无法从u到达v，也无法从v到达u。这与G是连通图的假设矛盾。因此，我们的假设不成立，G中任意两个顶点之间都存在路径。3.证明：若一个函数f:A→B是单射的，则对于任意的x₁,x₂∈A，若x₁≠x₂，则f(x₁)≠f(x₂)。证明：假设f不是单射的，即存在x₁,x₂∈A，使得x₁≠x₂，但是f(x₁)=f(x₂)。这与单射的定义矛盾，因为单射的定义是对于任意的x₁,x₂∈A，若x₁≠x₂，则f(x₁)≠f(x₂)。因此，我们的假设不成立，若一个函数f:A→B是单射的，则对于任意的x₁,x₂∈A，若x₁≠x₂，则f(x₁)≠f(x₂)。4.证明：若一个函数f:A→B是满射的，则对于任意的y∈B，存在至少一个x∈A，使得f(x)=y。证明：假设f不是满射的，即存在y∈B，对于所有的x∈A，都有f(x)≠y。这与满射的定义矛盾，因为满射的定义是对于任意的y∈B，存在至少一个x∈A，使得f(x)=y。因此，我们的假设不成立，若一个函数f:A→B是满射的，则对于任意的y∈B，存在至少一个x∈A，使得f(x)=y。5.证明：若一个命题p是永真命题，则p∨(¬p)是永真命题。证明：永真命题的定义是对于所有的可能情况，命题都是真的。因此，对于永真命题p，p是真的。根据逻辑或的定义，p∨(¬p)也是真的，因为逻辑或只要有一个是真的，整个表达式就是真的。因此，p∨(¬p)是永真命题。6.证明：若一个命题p是永假命题，则p∧(¬p)是永假命题。证明：永