下载文档原格式
南邮离散数学课后习题答案南京邮电大学离散数学课程是一门重要的数学基础课程，它涵盖了许多重要的离散数学概念和方法。
在学习这门课程时，我们经常会遇到一些难题，需要通过课后习题来巩固和加深对所学知识的理解。
然而，由于离散数学的题目类型繁多，解题方法各异，很多同学在课后习题中遇到了困惑。
为了帮助同学们更好地学习离散数学，我整理了一些常见课后习题的答案，供大家参考。
一、集合论1. 设A={1,2,3,4,5}，B={3,4,5,6,7}，C={2,4,6,8}，求(A∩B)∪C的元素个数。
答：首先求A∩B，即A和B的交集，得到{3,4,5}。
然后求(A∩B)∪C，即交集{3,4,5}与C的并集，得到{2,3,4,5,6,8}。
所以(A∩B)∪C的元素个数为6。
2. 设集合A={1,2,3,4,5}，B={3,4,5,6,7}，C={2,4,6,8}，求(A-B)∪C的元素个数。
答：首先求A-B，即A与B的差集，得到{1,2}。
然后求(A-B)∪C，即差集{1,2}与C的并集，得到{1,2,4,6,8}。
所以(A-B)∪C的元素个数为5。
二、关系与函数1. 设集合A={1,2,3,4,5}，B={3,4,5,6,7}，C={2,4,6,8}，定义关系R为A到B的映射，若R={(1,4),(2,5),(3,6),(4,7)}，求R的逆关系R^-1。
答：逆关系R^-1是由R中的有序对的元素颠倒位置得到的。
所以R^-1={(4,1),(5,2),(6,3),(7,4)}。
2. 设集合A={1,2,3,4,5}，B={3,4,5,6,7}，C={2,4,6,8}，定义函数f为A到B的映射，若f(1)=4，f(2)=5，f(3)=6，f(4)=7，求f的逆函数f^-1。
答：逆函数f^-1是由f中的元素的自变量和因变量颠倒位置得到的。
所以f^-1(4)=1，f^-1(5)=2，f^-1(6)=3，f^-1(7)=4。
三、图论1. 设G=(V,E)为一个无向图，V={A,B,C,D,E,F}，E={{A,B},{A,C},{B,C},{C,D},{D,E}}，求G的邻接矩阵。
Test of "Discrete Mathematical Structures"July 2003, Institute of Software at Nanjing University1. Prove or disprove (6 scores each):1.1 A,B,C are sets. If A⊂B and B⊆C, then A⊂C.1.2 (S,*) is a semigroup, if * satisfies cancellation property, then (S,*) is group.1.3 A,B,C are sets. If g f(f:A→B, and, g:B→C) is a bijection, then f and g are bothbijections.1.4 If (S,≼) is a totally-ordered set, then (S,≼) is a lattice.1.5 p,q,r are propositional variables. If (r⇒(q⇒p)) and (~p) are both true, then (~r)∨(~q)is true.2. Prove(10 scores each):2.1 N is the set of natural numbers. Define a relation ~ on P(N) as follows: X~Y if andonly if X⊕Y is a finite set. Then, ~ is an equivalence.2.2 L is a lattice, and X is a finite subset of L. Then, there exists an element t∈L,satisfying: for any x in L, x≼y for any y in X if and only if x≼t2.3 (A,*) is a semigroup, and there is an element a in A such that for every x in A, thereexist some u and v in A satisfying the relation: a*u=v*a=x. Then A has an identity.2.4 G is a group and a is a fixed element in G. Define a function f a: G→G, such thatf a(x)=a*x*a-1 for any x in G. Then, f a is an isomorphism.3. Select any 3 from the following, and give the solutions for them(10 scores each)3.1 Give the explicit formula for the Fibonacci sequence: f1= f2 =1; f n= f n-1+ f n-2 .3.2 The vertices of graph K mn can be divided into two sets V1,V2 with |V1|=m, and |V2|=n,and each vertex in V1 is adjacent to all vertices in V2, and vice versa, but no vertex is adjacent to any vertex in the same set. What are the conditions for the K mn to be an Eulerian graph or a Hamilton graph respectively. Why?3.3 Given 3 jugs without measuring signs on them. The largest one is full with exact 8liters of oil, and the other 2, with the capacities of 3 and 5 liters, are empty. Not using any other utensils, divide the oil into two parts with the same amount. How many pourings are needed at least? Solve the problem using a graph model.3.4 Find a maximum flow in the network shown below:《离散数学》期终试题南京大学软件学院 2003年7月1. 判断下列命题是否为真，并说明理由(每题6分):1.1A,B,C是集合。
