北京语言大学信息科学学院本科生考试试题专用纸（答案） 考试课程 《离散数学》 A卷 2012年 7 月6 日 答卷时间： 110分钟 满分：100分 班级： 学号： 姓名： 1. Choose the best answer to each of the questions (5×4=20 points). 1) Which of the following are statements? ( C ) A. Is 11 a prime number? B. Study logic. C. If stock prices fall, then I will lose money. D.Take three aspirins. 2) The number of distinguishable permutations of the letters in the word ALABAMA is ( D ) A. 7! B. 7!/4 C.77 D. 7!/4! 3) Which of the following is a tautology? ( A ) A. (p?(p?q))?q; B. (p?(p?r)); C. (q?(p?q))?~p; D. (p?q)?r. 4) If m|xy and GCD(m,x)=1, then which of the following must be true? ( B ) (i)m|x and m|y; (ii) m|y; A. (i) only B. (ii) only C. (i) and (ii) D. neither (i) nor (ii) 5) Consider the statement: If m2 is odd, then m is odd. To prove this statement using the contrapositive, we begin by assuming that （ D） A.m is odd. B. m2 is even. C. m2 is odd. D. m is even. 2. Write your answers in space provided (5×4=20 points). 1) If |A|=m and |B|=n, then how many relations are there from A to B. 2mn ?100??, then the 2) Let A={1,2,3} and let R be the relations on A described by M??011??R?101???inverse of R is R 3) Give a Hasse diagram of a nondistributive lattice. 4) Find an explicit formula for the sequence defined by Cn?3Cn?1?2Cn?2with initial conditions C1?5and C2?3. Cn= Cn?7?2. 5) Find an exact cover for A={a,b,c,d,e,f,g} with respect to A1={a,b,e}, A2={a,b}, A3={a,e,f}, A4={d,f,g}, A5={c,d,e,g}, A6={c,e}. A2,A4,A6 3. (10 points) Using characteristic functions, prove that (A?B)?C?A?(B?C). Proof.f(A?B)?C(x)?fA?B(x)?fC(x)?2fA?B(x)fC(x) by Theorem 4 n?1?{(1,1),(2,2),(3,3),(3,2),(1,3)} ?(fA(x)?fB(x)?2fA(x)fB(x))?fC(x)?2(fA(x)?fB(x)?2fA(x)fB(x))fC(x) ?fA(x)?fB(x)?fC(x)?2fA(x)fB(x)?2fA(x)fC(x)?2fC(x)fB(x)?4fA(x)fB(x))fC(x) ………..8 points Similarly, fA?(B?C)(x)?fA(x)?fB(x)?fC(x)?2fA(x)fB(x)?2fA(x)fC(x)?2fC(x)fB(x)?4fA(x)fB(x))fC(x)第 1 页 / 共 2 页
, thus (A?B)?C?A?(B?C). ………..10 points 4. (10 points) Show that if any six numbers from 1 to 10 are chosen, then two of them will add to 11. Proof. Construct five different sets, each containing two numbers that add up to 11 as follows: A1={1,10}, A2={2,9}, A3={3,8}, A4={4,7}, A5={5,6}. Each of the six numbers chosen must belong to one of these sets. Since there are only five sets, the pigeonhole principle tells us that two of the chosen numbers belong to the same set. These numbers add up to 11. …..10 points 5.(10points) Let R={(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(3,4),(4,3)} and S={(1,1),(2,2),(3,3),(4,4),(5,5),(5,4)(4,5)} be equivalence relations on A={1,2,3,4,5}. Find the smallest equivalence relation containing R and S, and compute the partition of A that it products. ?Solution. The smallest equivalence relation containing R and S is (R?S), (R?S)={(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(3,4)(4,3),(5,4),(4,5)}. …..8 points The corresponding partition of A is then {{1,2},{3,4,5}}. …..10 points 6. (10 points) Let A={1,2,3,4,5,6,7,8} and p?????12345678??be a permutation ??34652187?of A. (1) Write p as a product of disjoint cycles. (2) Compute p2 (3) Compute p-1 k(4) Find the period of p, that is, the smallest positive integerksuch thatp?1A. Solution. (1) p=(1,3,6)(2,4,5)(7,8). (2) p2=(1,6,3)(2,5,4). (3) p-1= (1,6,3)(2,5,4) (7,8). (4)k=6. 7. (10 points) Let (A,R) be a poset, show that R satisfies the following conditions. (1) a?R(a)for all a?A. (2) If a?R(b), then R(a)?R(b). (3) If R(a)?R(b), then a?b. Proof. (1) Since aRa, we have a?R(a) .……………….. 3 points (2) If a?R(b), suppose that x?R(a), then aRx, using a?R(b), we have bRa, by transitivity of R, bRx, thus x?R(b) and R(a)?R(b) ……………….. 6 points (3) By (1), a?R(a)?R(b), thus bRa, similarly, aRb, using anti-symmetric property of R, a?b .……………….. 10 points 8. (5 points) Show that if a bounded lattice L with greatest element I and least element 0 has two or more elements, then I?0. Proof. If 0=I, for each element x in L, 0?x?I, thus 0?0?x?I?x?x and L={0}. This is a contradiction. .……………….. 5 points 9. (5 points) Show that a tree with n vertices has n-1 edges. Proof. Because a tree is a symmetric closure of a rooted tree (T,v0), Each vertex in T, other than v0, has in-degree one, and v0 has in-degree 0. Each an in-degree contribute a edge. So a tree with n vertices has n-1 edges. ……………….. 5 points 第 2 页 / 共 2 页
2012年北京语言大学离散数学期末考试A卷真题附答案
