离散数学英文试题A参考答案及评分标准

数理逻辑部分选择、填空及判断✓下列语句不是命题的（ A ）。

(A) 你打算考硕士研究生吗？ (B) 太阳系以外的星球上有生物。

(C) 离散数学是计算机系的一门必修课。

(D) 雪是黑色的。

✓命题公式P→(P∨⌝P)的类型是（ A ）(A) 永真式(B) 矛盾式(C) 非永真式的可满足式(D) 析取范式✓A是重言式，那么A的否定式是( A )A. 矛盾式B. 重言式C. 可满足式D.不能确定✓以下命题公式中，为永假式的是( C )A. p→(p∨q∨r)B. (p→┐p)→┐pC. ┐(q→q)∧pD. ┐(q∨┐p)→(p∧┐p)✓命题公式P→Q的成假赋值是( D )A. 00,11B. 00,01,11C.10,11D. 10✓谓词公式)xxP∧∀中，变元x是 ( B )R(,x)(yA. 自由变元B. 既是自由变元也是约束变元C. 约束变元D. 既不是自由变元也不是约束变元✓命题公式P→(Q∨⌝Q)的类型是( A )。

(A) 永真式 (B) 矛盾式(C) 非永真式的可满足式 (D) 析取范式✓设B不含变元x，)Ax→x∃等值于( A ))((BA. B( D. B∃)xA→x∃)((∃ C. Bx∧Ax( B. )∀)xA→xx∨)A(x(B✓下列语句中是真命题的是( D )。

A．你是杰克吗？ B．凡石头都可练成金。

C．如果2+2=4，那么雪是黑的。

D．如果1+2=4，那么雪是黑的。

✓从集合分类的角度看，命题公式可分为( B )A. 永真式、矛盾式B. 永真式、可满足式、矛盾式C. 可满足式、矛盾式D. 永真式、可满足式✓命题公式﹁p∨﹁q等价于( D )。

A. ﹁p∨qB. ﹁(p∨q)C. ﹁p∧qD. p→﹁q✓一个公式在等价意义下，下面写法唯一的是( D )。

(A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式✓下列含有命题p，q，r的公式中，是主析取范式的是( D )。

离散数学试题（A 卷答案）一、（10分）求(P ↓Q )→(P ∧⌝(Q ∨⌝R ))的主析取范式 解：(P ↓Q )→(P ∧⌝(Q ∨⌝R ))⇔⌝(⌝( P ∨Q ))∨(P ∧⌝Q ∧R ))⇔(P ∨Q )∨(P ∧⌝Q ∧R ))⇔(P ∨Q ∨P )∧(P ∨Q ∨⌝Q )∧(P ∨Q ∨R ) ⇔(P ∨Q )∧(P ∨Q ∨R )⇔(P ∨Q ∨(R ∧⌝R ))∧(P ∨Q ∨R ) ⇔(P ∨Q ∨R )∧(P ∨Q ∨⌝R )∧(P ∨Q ∨R ) ⇔0M ∧1M⇔2m ∨3m ∨4m ∨5m ∨6m ∨7m二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。

乙说：王教授不是上海人，是苏州人。

丙说：王教授既不是上海人，也不是杭州人。

王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。

试判断王教授是哪里人？解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。

则根据题意应有： 甲：⌝P ∧Q 乙：⌝Q ∧P 丙：⌝Q ∧⌝R王教授只可能是其中一个城市的人或者3个城市都不是。

所以，丙至少说对了一半。

因此，可得甲或乙必有一人全错了。

又因为，若甲全错了，则有⌝Q ∧P ，因此，乙全对。

同理，乙全错则甲全对。

所以丙必是一对一错。

故王教授的话符号化为：((⌝P ∧Q )∧((Q ∧⌝R )∨(⌝Q ∧R )))∨((⌝Q ∧P )∧(⌝Q ∧R ))⇔(⌝P ∧Q ∧Q ∧⌝R )∨(⌝P ∧Q ∧⌝Q ∧R )∨(⌝Q ∧P ∧⌝Q ∧R ) ⇔(⌝P ∧Q ∧⌝R )∨(P ∧⌝Q ∧R ) ⇔⌝P ∧Q ∧⌝R ⇔T因此，王教授是上海人。

三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。

证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。

--北京工商大学离散数学试卷(A)答案及评分标准题号 一 二三 四 五 六 七总分得分一、（30分）设A ={1,2,3,4}，给定A 上二元关系R 如下：R ={<1,1>, <1,2>, <2,3>, <3,3>, <4,4>}请回答以下各问题：1.写出R 的关系矩阵. （3分）2.画出R 的关系图. （3分）3.求包含R 的最小的等价关系，并写出由其确定的划分. （6分）4.分别用关系矩阵表示出R 的自反闭包r (R )、对称闭包s (R ). （6分）5.求传递闭包t (R ).（写出计算步骤）（6分）6.求R 2的关系矩阵. （3分）7.集合A 上最多可以确定多少个不同的二元关系？说明理由。

（3分）[解] (1)⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000010001000011R M 。

……（3分）（2） ……（3分）(3)法一：直接由等价关系与划分之间的一一对应可知，包含R 的最小等价关系为: {<1, 2>, <1, 3>, <2, 1>,<2, 3>, <3, 1> <3, 2>}∪I A , ……（3分） 对应的划分为{{1, 2, 3},{4}}. ……（6分） 法二：包含R 的最小的等价关系就是tsr (R ), 计算过程如下：⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=100001000110001110000100001000011000010001000011)(E M M R R r,100001100111001110000110001100011000010001100011][)()()(⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+=T R r R r R sr M M M ,3,10001110111011110000110011100111000011001110011)]([)()()]([2≥=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛⨯⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⨯=k M M M M k R sr R sr R sr R sr 从而,10000111011101111000011101110111100001110111011110000111011101111000011001110011432)]([)]([)]([)()(⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+++=R sr R sr R sr R sr R tsr M M M M M即}2,3,1,3,3,2,1,2,3,1,2,1{)(><><><><><><⋃=A I R tsr =包含R 的最小的等价关系， ……（3分） 故其对应的划分为{{1, 2, 3},{4}}. ……（6分） 法三：由于4=A ，包含R 的最小的等价关系就是4131211)()()()()()(----⋃⋃⋃⋃⋃⋃⋃⋃==R R R R R R R R I R rts R tsr A ,计算过程如下：⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=-⋃100001100101001110000110000100011000010001000011][1TR R R R M M M ⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=-⋃10000111011101111000011001010011)][(22)(21T R R R R M M M412131)()(33)(10000111011101111000011001010011)][(---⋃⋃⋃==⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=R R R R T R R R R M M M M M 考试纪律承诺本人自愿遵守学校考试纪律，保证以诚信认真的态度作答试卷。

Mock ExamNotes___________________________________________________________________________________ 1. There are 38 questions in this mock exam. The real exam will consist of about 25 questions that will be relatively similar to those here... that does not mean “identical” to those...2. If you do these well, you should have no big difficulties in the final exam.3. I encourage you to work these questions first on your own, without help, to see what you do or do not understand. You may seek help after that. Remember that no one will help you or give you hints during the exam. We will clarify the questions if something is not clear but not more than that.#01 - Page 13 #8Let p and q be the propositionsp : I bought a lottery ticket this week.q : I won the million dollar jackpot.Express each of these propositions as an English sentence.a) ￢p I did not buy a lottery ticket this week.b) p ∨q I bought a lottery ticket this week or I won the million dollar jackpot.c) p → q If I bought a lottery ticket this week then I won the million dollar jackpot.d) p ∧q I bought a lottery ticket this week and I won the million dollar jackpot.e) p ↔ q I bought a lottery ticket this week if, and only if, I won the million dollar jackpot.#02 - Page 15 #36Construct a truth table for each of these compound propositions.a) (p ∨q) ∨rp q r p ∨q(p ∨q) ∨rT T T T TT T F T TT F T T TT F F T TF T T T TF T F T TF F T F TF F F F Fc) (p ∧q) ∨r∧(p q)∧∨rp q r p qT T T T TT T F T TT F T F TT F F F FF T T F TF T F F FF F T F TF F F F Fe) (p ∨q)∧￢r∨∧￢rp q r p ∨q￢r(p q)T T T T F FT T F T T TT F T T F FT F F T T TF T T T F FF T F T T TF F T F F FF F F F T F#03 - Page 35 #9Show that each of these conditional statements is a tautology by using truth tables.c) ￢p → (p → q)p q￢p p → q￢p → (p → q)T T F T TT F F F TF T T T TF F T T Td) (p ∧q) → (p → q)∧p → q(p q) → (p → q)∧p q p qT T T T TT F F F TF T T T TF F T T Te) ￢(p → q) → pp q p → q￢(p → q)￢(p → q) → p T T T F TT F F T TF T T F TF F T F T#04 - DNFWrite the following proposition in disjunctive normal form:s = (r → p) → (p∧q)p q r r → p p∧q sT T T T T TT T F T T TT F T T F FT F F T F FF T T F F TF T F T F FF F T F F TF F F T F Fs=(p∧q∧r)∨(p∧q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧r)=(p∧q)∨(¬p∧r)#05 - Page 53 #8Let I (x) be the statement “x has an Internet connection” and C(x, y) be the statement “x and y have chatted over the Internet,” where the domain for the variables x and y consists of all students in your class. Use quantifiers to express each of these statements.b) Rachel has not chatted over the Internet with Chelsea.C(Rachel, Charles)e) Sanjay has chatted with everyone except Joseph.∀x(x ≠ Joseph → C(Sanjay, x))f ) Someone in your class does not have an Internet connection.∃x(￢I(x))i) Everyone except one student in your class has an Internet connection.!∃y[￢I(y) ∧∀x(x ≠ y → I(x))]j) Everyone in your class with an Internet connection has chatted over the Internet with at least one other student in your class.∃∀x yC(x, y)m) There is a student in your class who has chatted with everyone in your class over the Internet.∃x∀yC(x, y)#07 – Page 67 #27Determine the truth value of each of these statements if the domain for all variables consists of all real numbers.a) ∀x∃y(x2 = y) Truec) ∃x∀y(xy = 0)Truee) ∀x(x = 0 → ∃y(xy = 1))False∧x − y = 1)Falsei) ∀x∃y(x + y = 2 2j) ∀x∀y∃z(z = (x + y)/2)TrueUse rules of inference to show that the hypotheses “If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on,” “If the sailing race is held, then the trophy will be awarded,” and “The trophy was not awarded” imply the conclusion “It rained.”Define the following literals:r It rainsf It is foggys The sailing race will be heldd The lifesaving demonstration will go ont The trophy will be awardedThe premises are then∧P1(¬r ∨ ¬f) → (s d)P2s → tP3¬tand the conclusion isrThe proof proceeds as follows:1¬t P32s → t P23¬s Modus tollens with 1 and 2'∨Addition to 34¬s ¬d∧De Morgan's law5¬(s d)∨) → (s d)∧P16(¬r ¬f∨)Modus tollens with 5 and 67¬(¬r ¬f∧De Morgan's law8r f9r Simplification of 8#09 – Page 80 #27Use rules of inference to show that if ∀x(P(x) → (Q(x) ∧S(x))) and ∀x(P(x) ∧R(x)) are true, then∀x(R(x) ∧S(x)) is true.∀∧Premise1x(P(x) R(x))∧Universal instantiation2P(c) R(c)3P(c)Simplification from 24x(P(x) →∧Premise∀(Q(x) S(x)))∧Universal instantiation5P(c) → (Q(c) S(c))∧Modus ponens with 3 and 56Q(c) S(c)7S(c)Simplification from 68R(c)Simplification from 2∧Conjunction of 7 and 89R(c) S(c)∀∧Universal generalization10x(R(x) S(x))Prove that if n is a positive integer, then n is odd if and only if 5n + 6 is odd.First, assume that n is odd, so that n = 2k+1 for some integer k. Then 5n+6 = 5(2k+1)+6 = 10k + 11 = 2(5k + 5) + 1. Hence, 5n + 6 is odd. To prove the converse, suppose that n is even, so that n = 2k for some integer k. Then 5n + 6 = 10k + 6 = 2(5k + 3), so 5n + 6 is even. Hence, n is odd if and only if 5n + 6 is odd.#11 – Page 126 #19What is the cardinality of each of these sets?a) {a}1b) {{a}}1c) {a, {a}}2d) {a, {a}, {a, {a}}}3#12 – Page 126 #40Explain why (A × B) × (C × D) and A × (B × C) × D are not the same.The tuples in those sets do not have the same composition. The tuplets in (A × B) × (C × D) are pairs of pairs: ((x,y),(u,v)). However, the tuplets in A × (B × C) × D are ordered triplets with two singletons and a pair: (u, (x,y), v).#13 – Page 136 #27Draw the Venn diagrams for each of these combinations of the sets A, B, and C.b) (A ∩ B) ∪(A ∩ C)c) (A ∩ B) ∪(A ∩ C)#14 – Page 153 #22Determine whether each of these functions is a bijection from R to R.a) f (x) = −3x + 4Yesb) f (x) = −3x2 + 7No: elements greater than 7 have no preimages.c) f (x) = (x + 1)/(x + 2)No: -2 has no imaged) f (x) = x5 + 1YesFor each of these sequences find a recurrence relation satisfied by this sequence. (The answers are not unique because there are infinitely many different recurrence relations satisfied by any sequence.)a) a n= 3a n= a n-1c) a n= 2n + 3a n-1= 2(n - 1)+ 3 = 2n + 3 – 2 = a n – 2. This implies that a n= a n-1+ 2.f ) a n= n2 + n(e1)Here we have two independent terms with n. We will need two additional formulas:a n-1= (n-1)2 + n – 1 = n2 – 2n + 1 + n – 1 = n2 – n(e2)a n-2= (n-2)2 + n – 2 = n2 – 4n + 4 + n – 2 = n2 – 3n + 2(e3)From (e1) and (e2), we have a n – a n-1 = 2n(e4)From (e2) and (e3), we have a n-1 – a n-2 = 2n – 2(e5)From (e4) and (e5), we have a n – a n-1 – (a n-1 – a n-2) = a n – 2a n-1+ a n-2 = 2, or a n = 2a n-1– a n-2+ 2 g) a n= n + (−1)n(e1)a n-1 = n – 1 + (−1)n-1 = n – 1 – (−1)n(e2)From (e1) and (e2), we have a n – a n-1 = 1 + 2(−1)nor a n = a n-1 + 1 + 2(−1)nWe can split this into the odd an even n's:a2k = a2k-1 + 1a2k+1 = a2k− 1h) a n= n!a n = n a n-1#16 – Page 583 #30 (+ additional questions)Let R1 = {(1, 2), (2, 3), (3, 4)} and R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4)} be relations from {1, 2, 3, 4} to {1, 2, 3, 4}. Finda) R1∪R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4)} = R2b) R1 ∩ R2 = {(1, 2), (2, 3), (3, 4)} = R1c) R1 − R2 = ∅d) R2 − R1 = {(1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3)}e) R1 ◦ R2 = {(1, 2), (1, 3), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}f ) R2 ◦ R1 =g) Draw the graph of R1 ◦ R2.h) Find the reflexive, symmetric and transitive closures ofReflexive closure = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 4), (3, 4), (4, 4)}Symmetric closure = {(1, 2), (2, 1), (2, 3), (3, 2), (3, 3), (4, 3)}Transitive closure = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 1), (3, 4), (4, 1), (4, 2)}Let R be the relation consisting of all pairs (x, y) such that x and y are strings of uppercase and lowercase English letters with the property that for every positive integer n, the n th characters in x and y are the same letter, either uppercase or lowercase. Show that R is an equivalence relation.That definition basically means that two strings are equivalent if, and only if, they have the same length and every corresponding characters x i and y i are the same letter, either lower or upper case.Let c and C stand for the lower and upper cases of a same letter in the English alphabet.Clearly k, x∀k = x k. So (x, x) ∈ R.So R is reflexive.If (x,y)∈ R, then k, x∀k∈ {c, C} and y k∈ {c, C}. So (y, x) ∈ R also. So R is symmetric.If (x,y)∈ R and (y,z)∈ R, then [x k∈ {c, C}, y k∈ {c, C}] and [y k∈ {c, C}, z k∈ {c, C}], which implies that [x k∈ {c, C},z k∈ {c, C}]. So (x, z) ∈ R. So R is transitive.Therefore R is an equivalence relation.#18 – Page 631 #34Answer these questions for the poset ({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72}, |).a) Find the maximal elements.27, 48, 60, 72b) Find the minimal elements.2, 9c) Is there a greatest element?Nod) Is there a least element?Noe) Find all upper bounds of {2, 9}.18,36 72f ) Find the least upper bound of {2, 9}, if it exists.18g) Find all lower bounds of {60, 72}.2, 4, 6, 12h) Find the greatest lower bound of {60, 72},if it exists.12#19 – Group TheoryConsider the set G={a1+a2√3 | a1,a2∈ℚ∧a1a2≠0}with the usual multiplication operation.a) Show that G is a group by verifying the axioms of closure, associativity, existence of an identity element, and existence of an inverse element for every element. Specify what the identity element is and the form an an inverse element.1. Closure: Let a,b∈G. Then ab=(a1+a2√3)(b1+b2√3)=(a1b1+3a2b2)+(a1b2+a2b1)√(3)∈G2 Associativity: Let a ,b ,c ∈G . Then (ab )c =[(a 1+a 2√3)(b 1+b 2√3)]c=[(a 1b 1+3a 2b 2)+(a 1b 2+a 2b 1)√(3)](c 1+c 2√3)=[(a 1b 1+3a 2b 2)c 1+3(a 1b 2+a 2b 1)c 2]+[(a 1b 1+3a 2b 2)c 2+(a 1b 2+a 2b 1)c 1]√(3)=a 1b 1c 1+3a 2b 2c 1+3a 1b 2c 2+3a 2b 1c 2+[a 1b 1c 2+3a 2b 2c 2+a 1b 2c 1+a 2b 1c 1]√(3)=[a 1(b 1c 1+3b 2c 2)+3a 2(b 1c 2+b 2c 1)]+[a 2(b 1c 1+3b 2c 2)+a 1(b 1c 2+b 2c 1)]√(3)=(a 1+a 2√3)[(b 1c 1+3b 2c 2)+(b 1c 2+b 2c 1)√(3)]=a [(b 1+b 2√3)(c 1+c 2√3)]=a (bc )3. Identity element. Let this element be e =e 1+e 2√. Thenea =(e 1+e 2√3)(a 1+a 2√3)=(e 1a 1+3e 2a 2)+(e 1a 2+e 2a 1)√(3)=(a 1+a 2√3).This implies that for every a 1 and a 2:e 1a 1+3e 2a 2=a 1e 1a 2+e 2a 1=a 2That implies e 1=1and e 2=0. Thus e =1.4. Inverse element. Consider a =a 1+a 2√3∈G and let its inverse be a −1=x 1+x 2√3if it exists. Then we must havea −1a =(x 1+x 2√3)(a 1+a 2√3)=(x 1a 1+3x 2a 2)+(x 1a 2+x 2a 1)√(3)=1=e This impliesx 1a 1+3x 2a 2=1x 1a 2+x 2a 1=0The solution isa −1=a 1−a 2√3a 12−3a 22.Thus G forms a group.b) Is G Abelian?Yes: ab =(a 1+a 2√3)(b 1+b 2√3)=(a 1b 1+3a 2b 2)+(a 1b 2+a 2b 1)√(3)=ba because this expression is symmetric.#20 – Page 665 #9Determine the number of vertices and edges and find the in-degree and out-degree of each vertex for the shown directed multigraph:5 vertices 13 edgesdeg+(a) = 1, deg+(b) = 1, deg+(c) = 5, deg+(d) = 4, deg+(e) = 0deg−(a) = 6, deg−(b) = 5, deg−(c) = 2, deg−(d) = 2, deg−(2) = 0#21 – Page 666 #28Suppose that a newcompany has five employees: Zamora, Agraharam, Smith, Chou, and Macintyre. Each employee will assume one of six responsiblities: planning, publicity, sales, marketing,development, and industry relations. Each employee is capable of doing one or more of these jobs: Zamora could do planning, sales, marketing, or industry relations; Agraharam could do planning or development; Smith could do publicity, sales, or industry relations; Chou could do planning, sales, or industry relations; and Macintyre could do planning, publicity, sales, or industry relations.a) Model the capabilities of these employees using a bipartite graph.b) Find an assignment of responsibilites such that each employee is assigned one responsibility.Note: the assignment is not unique. The only forced choices are (Z, ma) and (A, de). There is a variety of possibilities for the other 3.c) Is the matching of responsibilities you found in part (b) a complete matching? Is it a maximum matching?The matching (from {Z, A, S, C, M} to {ma, de, sa, pl, pu, ir}) is complete because every employee is matched with a job. It is a maximum because |M| = 5 = |{Z, A, S, C, M}|#22 – Page 676 #21 (+ additional questions)Consider the following grapha) Find the adjacency matrix A of the graph A =(1110100220111210)b) Find how many paths of length 3 there are from c to b A 3=A (1110100220111210)(1110100220111210)=(1110100220111210)(4123353054415125)=(12109414361318710121512124)So there are 6 paths from c to b.#23 – Page 676 #38Determine whether the following two graphs are isomorphic. If so, construct an isomorphism.Notice the second graph can be deformed like this (by moving v 2 all the way down and rotating the other vertices by about a quarter of a turn):It has 2 circuits of length 4 whereas the graph on the left has only 1. That immediately implies that these graphs are not isomorphic.#24 – Page 692 #31-32Consider the following graphs#31#31a) List the cut vertices c c, db) List the cut edges none(c,d)c) What is the vertex connectivity κ(G)?11d) What is the edge connectivity λ(G)?21#25 – Page 704 #22Determine whether the directed graph shown has an Euler circuit. Construct an Euler circuit if one exists. If no Euler circuit exists, determine whether the directed graph has an Euler path. Construct an Euler path if one exists.The vertices' total degrees are all even except for vertices b and c. So it has no Euler circuit but there might be an Euler path, although this is not guaranteed because the graph is directed. However every vertex with an even total degree has equal in and out degrees. Beccause the out-degree of c is larger than its in-degree, then the starting point has to be c. In fact, we o find an Euler path:c → e → b → c → b → f → a → f → e → f →d →e → a → b → d → c → b#26 – Page 716 #8Find a shortest path (in mileage) between each of the following pairs of cities in the airline system shown in Figure 1.Note: You must show every steps of the algorithmB N M ACD S L-0------N 191/N-1090/N760/N722/N-2534/N2451/N B --1090/N760/N722/N-2534/N2451/N C --1090/N760/N-1630/C2534/N2451/N A --1090/N--1630/C2534/N2451/N D --1090/N---2534/N2451/N M ------2534/N2451/N LPath = N → L Distance = 2451b) Boston and San FranciscoB N M ACD S L0-------B -191/B--860/B---N --1281/N951N860/B-2725/N2642/N C --1281/N951N-1768/C2715/C2642/N A --1281/N--1768/C2715/C2642/N M -----1768/C2715/C2642/N D ------2715/C2602/D L ------2715/C-SPath = B → C → S Distance = 2715c) Miami and DenverB N M ACD S L--0-----M -1090/M-595/M----A -1090/M--1201/A---N 1281/N---1201/A-3624/N3541/N C 1281/N----2109/C3056/C3541/N B -----2109/C3056/C3541/N DPath = M → A → C → D Distance = 2109B N M ACD S L--0-----M-1090/M-595/M----A-1090/M--1201/A---N1281/N---1201/A-3624/N3541/N C1281/N----2109/C3056/C3541/N B-----2109/C3056/C3541/N D------3056/C2943/D LPath = M → A → C → D → L Distance = 2943#27 – Page 726 #12Suppose that a connected planar graph has eight vertices, each of degree three. Into how many regions is the plane divided by a planar representation of this graph?We have V = 8. Each node has a degree equal to 3. The sum of all the degrees is therefore 24 and we know it is equal to twice the number of edges; thus E = 12. Recall Euler's formula: V – E + F = 2. So we have 8 – 12 + F = 2, which implies that F = 6.#28 – Page 732 #4Construct the dual graph for the map shown. Then find the number of colors needed to color the map so that no two adjacent regions have the same color.#29 – Page 733 #17Schedule the final exams for Math 115, Math 116, Math 185, Math 195, CS 101, CS 102, CS 273, and CS 473, using the fewest number of different time slots, if there are no students taking both Math 115and CS 473, both Math 116 and CS 473, both Math 195 and CS 101, both Math 195 and CS 102, both Math 115 and Math 116, both Math 115 and Math 185, and both Math 185 and Math 195, but there are students in every other pair of courses.The best way to obtain a graph for this is to draw a complete graph and then remove edges according to the description in the above paragraph.{MAT115, MAT116, CS473}{MAT185, MAT195}{CS101}{CS102}{CS273}The scheduling is not unique.#30 – Page 755 #4Consider the following rooted tree:a) Which vertex is the root?ab) Which vertices are internal?b, d, e, g, h, i, oc) Which vertices are leaves?c, f, j, k, l, m, n, p, q, r, sd) Which vertices are children of n?nonee) Which vertex is the parent of g?bf ) Which vertices are siblings of k?jg) Which vertices are ancestors of o?a, d, ih) Which vertices are descendants of d?h, i, n, o, p, q, r, s#31 – Page 756 #20How many leaves does a full 3-ary tree with 100 vertices have?L=(m−1)n+1n =(3−1)×100+13=2013=67MATMATMAT185MAT195CS473CS273CS101CS102#32 – Page 769 #2Build a binary search tree for the words oenology, phrenology, campanology, ornithology, ichthyology , limnology, alchemy , and astrology using alphabetical order.#33 – Page 770 #24Use Huffman coding to encode these symbols with given frequencies: A: 0.10, B: 0.25, C: 0.05, D: 0.15, E: 0.30, F: 0.07, G: 0.08. What is the average number of bits required to encode a symbol?0.050.070.080.100.150.250.30 C F G A D B E0.080.100.120.150.250.30 GADBE0.120.150.180.250.30 DB E0.180.250.270.30 BE0.270.300.43Eoenologyphrenologycampanology ichthyology alchemy astrologylimnologyornithology0.430.571.00Codes:A = 110B = 10C = 0111D = 010E = 00F = 0110G = 111Average nuber of bits = (3 + 2 + 4 + 3 + 2 + 4 + 3) / 7 = 21/7 = 3#34 – Page 783 #10-11Consider the following rooted tree:In which order are the vertices visited using a preorder traversal?a, b, d, e, i, j, m, n, o, c, f, g, h, k, p, l#35 – Page 784 #23What is the value of the following prefix expression?a) − 2 / 8 4 3∗− 2 ∗/ 8 4 3=− 2 2∗ 3=− 4 3=1GACFCFb) ↑ − 3 3 4 2 5∗∗∗ 5=↑ − 3 3∗ 8 5∗ 4 2↑ − 3 3=↑ − 9 8 5=↑ 1 5=1c) + − ↑ 3 2 ↑ 2 3 / 6 − 4 2+ − ↑ 3 2 ↑ 2 3 / 6 − 4 2=+ − ↑ 3 2 ↑ 2 3 / 6 2=+ − ↑ 3 2 ↑ 2 3 3=+ − ↑ 3 2 8 3=+ − 9 8 3=+ 1 3=4∗d) + 3 + 3 ↑ 3 + 3 3 3+ 3 + 3 ↑ 3∗↑ 3 6 3∗+ 3 3 3= + 3 + 3∗+ 3 729 3= + 3=∗+ 3 732 3∗= 735 3=2205#36 – Page 795 #13Use depth-first search to produce a spanning tree for the following simple graph. Choose vertex 'a' as the root of this spanning tree and assume that the vertices are ordered alphabetically.a →b →c →d →e →f →g →h → Ig → j#37 – Page 802 #3Use Prim's algorithm to find a minimum spanning tree (and its total weight) for the following weighted graph:(ef)1(cf)3(eh)3(hi)2(gh)4(bc)4(bd)3(ad)2Total weight = 22#38 – Page 802 #8Use Kruskal’s algorithm to find a minimum spanning tree for the weighted graph in Exercise 4 (#37). (ef)1(ad)2(hi)2(bd)3(cf)3(eh)3(bc)4(gh)4Total weight = 22The spanning tree is identical to that in Exercise 4 (#37).。

《离散数学》课程试题【A】卷阅卷须知：阅卷用红色墨水笔书写，得分用阿拉伯数字写在每小题题号前，用正分表示，不得分则在题号前写0；大题得分登录在对应的分数框内；统一命题的课程应集体阅卷，流水作业；阅卷后要进行复核，发现漏评、漏记或总分统计错误应及时更正；对评定分数或统分记录进行修改时，修改人必须签名。

特别提醒：学生必须遵守课程考核纪律，违规者将受到严肃处理。

PLEASE ANSWER IN CHINESE OR IN ENGLISH!!1. Fill the best answer in the blanks (3 points each，15 points in all)(1) If A, B, and C be sets, then (A–C) – (B–C) ___________ A–B.(2) A relation on a set A that is reflexive, symmetric, and transitive is called an (or a) ___________relation.(3) K n has ___________edges.(4) There are _______ __non-isomorphic rooted trees with four vertices.(5) Assume that P(x, y) means “x+ 2y= xy”, where x and y are integers. Then the truth value of thestatement ∀x∃y P(x, y) is _______ __.2. Choose the corresponding letter of the best answer that best completes the statements oranswers the questions among A, B, C, and D and fill the blanks (3 points each，15 pointsin all).(1) Suppose A = {1, 2, 3}. The following statement ( ) is not true. A ．∅ ⊆(A )B ．{∅} ⊆ (A )C ．{2, 3} A AD ．{{2}} ⊆(A )(2) Suppose that R and S are transitive relations on a set A . Then ( ) is transitive. A ． S R ⋂ B ．S R ⋃ C ． S R - D ．S R(3) There are ( ) strongly connected components of the following graph G .A. 1B. 2C. 3D. 4(4) There are ( ) nonisomorphic undirected trees with 5 vertices.A. 6B. 5.C. 4D. 3(5) Suppose P (x , y ) is a predicate and the universe for the variables x and y is {1,2,3}. Suppose P (1,3), P (2,1), P (2,2), P (2,3), P (3,1), P (3,2) are true, and P (x , y ) is false otherwise. The following statement ( ) is true.A. ∀y ∃x (P (x , y ) → P (y , x ))B. ¬∃x ∃y (P (x , y ) ∧ ¬P (y , x ))C. ∀x ∀y (x ≠ y → (P (x , y ) ∨ P (y , x ))D. ∀y ∃x (x ≤ y ∧ P (x , y ))3. Write “” for true, and “” for false in the blanks at end of each statement (3 pointseach ，15 points in all).(1) There is a set S such that its power set (S) has 12 elements. ( )(2) An irreflexive and transitive relation on a set A is antisymmetric. ( )(3) The largest value of n for which K n is planar is 6. ( )(4) Every full binary tree with 61 vertices has 31 leaves. ( )(5) Logical expressions ))(x)xB(∧∀are equivalent. ( )xA∀x∀and)(x∧((x)AxB4.For any function f: A B, define a new function g: (A) (B) as follows: for every S A, g(S) = {f(x)|x S}. Prove that g is surjective (or onto) if and only f is surjective(or onto). (10 points)5.Find the transitive closure t(R) of R on {a, b, c, d} and draw the graph of t(R) where R = {(a, a), (b, a), (b,c), (c, a), (c, c), (c, d), (d, a), (d, c)}. (10 points)6. Either give an example or prove that there is none: A graph with 7 vertices that has a Hamilton circuit but no Euler circuit. (10 points)7. Let G be an undirected tree with 3 vertices of degree 3, 1 vertex of degree 2, the other vertices of degree 1.(15 points)(1) How many vertices in G are there?(2) Draw two nonisomorphic undirected trees satisfying the above requirements.8. Show that p→ (q→ r) and p→ (q∧ r) are logically equivalent. (10 points)。

2011级离散数学(A)参考答案一、填空题（每小题2分，共30分）1. 设():M x x 为人， ():F x x 不吃饭。

将命题“没有不吃饭的人”符号化为：))()((x F x M x ⌝→∀ 或 ))()(((x F x m x ∧∃⌝ 。

2. 设A={1, 2, 3, 4} ，则 A 的全部2元子集共有 6 个。

3. 设p ：明天是周一，q ：明天是周三，r ：我有课。

则命题“如果明天是周一或周三，我就有课”的符号化形式为 r q p →∨)( 。

4. 已知命题公式A 含有2个命题变项，其成真赋值为00、10、11，则其主析取范式为 320m m m ∨∨ 。

5. 设p ：北京比大连人口多，q ：2+2=4，r ：乌鸦是白色的。

则命题公式)()(r p r q ⌝→→∨的真值为 1 。

6. 集合}3,2,1{=A 上的关系}3,2,3,1,2,1{><><><=R ，则=-1R { <2,1>,<3,1>,<3,2> }。

7. 画出下图的补图 。

8.设A={1,2,3}，B={a,b,c}，A 1={1}，f={<1,a>,<2,a>,<3,b>}，则=-))((11A f f { 1,2 }。

9. 设无向图的度数序列为：1，2，2，3，4。

则该无向图的边数m= 6 。

10. 3阶有向完全图的2条边的非同构的生成子图有 4 个。

11. 设〈≤,A 〉为偏序集，A B ⊆。

若y x B y x 与,,∈∀都是可比的，则称B是A 中的一条链，B 中的元素个数称为链的长度。

在偏序集〈{1,2,…,9}，整除〉中，{1,2,4,8}是长为 4 的链。

12. 下面运算表中的单位元是 b 。

13. 写出模4加法群G=<Z 4,⊕ >的运算表14. 模4加法群中， 2-3= 2 。

………密………封………线………以………内………答………题………无………效……电子科技大学英才学院2022 -2022学年第 1学期期 末 考试 A 卷离散数学 课程考试题 A 卷 〔 120分钟〕 考试形式：闭卷 考试日期 2022 年 月 日课程成绩构成：平时 分， 期中 分， 实验 分， 期末 100 分I.Multiple Choice (15%, 1.5 points each)〔A 〕 1. (p ∧q)→(p ∨q) is logically equivalent toa) T b) p ∨q c) F d) p ∧q〔A 〕 2. If P(A) is the power set of A, and A = ∅, what is |P(P(P(A)))|?a) 4 b) 24 c) 28 d) 216〔C 〕 3. Which of these statements is NOT a proposition?a) Today is Monday. ` b) 1+1=2.c) Am I right? d) Go and play with me.〔C 〕 4. Which of these propositions is not logically equivalent to the other three?a) (p → q) ∧ (r → q) b) (p ∨ r) → qc) (p ∧r) → q d) The contrapositive of ¬q → (¬p ^ ¬r)〔B 〕 5. Suppose | A | = 3 and | B | = 8. The number of 1-1 functions f : A → B isa) 24 b) P (8,3). c) 38 d) 83〔B 〕 6. Let R be a relation on the positive integers where xRy if x is a factor of y . Whichof the following lists of properties best describes the relation R ? a) symmetric, transitiveb) antisymmetric, transitive, reflexive c) antisymmetric, symmetric, reflexive d) symmetric, transitive, reflexive〔C 〕 7. Which of the following are partitions of },,,,,,,{h g f e d c b a U =?a)},,,,,{},,,{},{h g f e d c c b a a . b) },,,,,{},,{},{h g f e d c c b a c) }{},,{},,{},,,{h f e c b g d a . d) },,,,{},,{},,{h g f e d c b b a〔C 〕 8. The function f(x)=x 2log(x 3+78) is big-O of which of the following functions?a) x 2 b) x(logx)3 c) x 2logx d) xlogx〔A 〕 9.If 1010110111101101R ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦M , then R is: a) reflexive b) symmetric c) antisymmetric d) transitive.〔B 〕 10. Which of the followings is a function from Z to R ?………密………封………线………以………内………答………题………无………效……a) )1()(-±=n n f . ` b) 1)(2+=x x f . c) x x f =)( d) 21)(2-=n n fII. True or False (10%, 1 point each) 〔T 〕 1. If 1 < 0, then 5 = 6. 〔F 〕 2. (p ∧ q) ∨ r ≡ p ∧ (q ∨ r)〔F 〕 3. If A , B , and C are sets, then (A -C )-(B -C )=A -B . 〔T 〕 4. Suppose A = {a ,b ,c }, then {{a }} ⊆ P (A ).〔F 〕 5.()h x =is defined as a function with domain R and codomain R.〔T 〕 6. Suppose g : A → B and f : B → C , where f g is 1-1 and f is 1-1. g must be 1-1? 〔T 〕 7. If p and q are primes (> 2), then p + q is composite .〔F 〕 8.If the relation R is defined on the set Z where aRb means that ab > 0, then R is an equivalence relation on Z .〔T 〕 9. (A - B ) ⋃ (A - C ) = A - (B ⋂ C ).〔T 〕 10. The set{∅,{a },{∅},{a ,∅}} is the power set of some set III. Fill in the Blanks (20%, 2 points each)1. Let p and q be the propositions “I am a criminal 〞 and “I rob banks 〞. Express in simpleEnglish the proposition “if p then q 〞: If I am a criminal them I rob banks. 2. P (x ,y ) means “x + 2y = xy 〞, where x and y are integers. The truth value of ∃x ∀yP (x ,y )is False .3. T he negation of the statement “No tests are easy.〞 is some tests are easy.4. If 11{|}i A x x R x i i =∈∧-≤≤ then 1i i A +∞=is ∅.5. Suppose A = {x , y }. Then ()P A is {∅, {x}, {y},{x,y}}.6. Suppose g : A →A and f :A →A where A ={1,2,3,4},g = {(1, 4), (2,1), (3,1), (4,2)} andf ={(1,3),(2,2),(3,4),(4,2)}.Then fg ={(1,2),(2,3),(3,3),(4,2)}.7. The sum of 2 + 4 + 8 + 16 + 32 + ... + 210 is 211 - 2 .8. The expression of gcd(45, 12) as a linear combination of 12 and 45 is 12 ⋅ 4 + 45 ⋅ (1). 9.There are 5! permutations of the seven letters A,B ,C ,D ,E ,F have A immediately to the left of E .10. The two's complement of -13 is 1 0011 . IV. Answer the Questions (32%, 4points each)：1. Determine whether the following argument is valid:………密………封………线………以………内………答………题………无………效……p→rq→rq∨⌝r________∴⌝pAns: Not valid: p true, q true, r true2.Suppose you wish to prove a theor em of the form “if p then q〞.(a) If you give a direct proof, what do you assume and what do you prove?(b) If you give an indirect proof, what do you assume and what do you prove?(c) If you give a proof by contradiction, what do you assume and what do you prove? Ans: (a) Assume p, prove q.(b) Assume ⌝q, prove ⌝p.(c) Assume p∧⌝q, show that this leads to a contradiction.3.Prove that A B A B⋂=⋃by giving a proof using logical equivalence.Ans:()()()() A B x x A Bx x A Bx x A Bx x A x Bx x A x Bx x A x Bx x A x Bx x A B A B ⋂={|∈⋂}={|∉⋂}={|⌝∈⋂}={|⌝∈∧∈}={|⌝∈∨⌝∈}={|∉∨∉}={|∈∨∈}={|∈⋃}=⋃4.Suppose f:R→R where f(x) =⎣x/2⎦.(a) If S={x| 1 ≤x≤ 6}, find f(S).(b) If T={3,4,5}, find f-1(T). Ans: (a) {0,1,2,3}(b) [6,12).e the definition of big-oh to prove that5264473n nn+--is O(n3).………密………封………线………以………内………答………题………无………效……Ans: 5555322226446410573763n n n n n n n n n n +-+≤==--, if n ≥ 2. 6. Solve the linear congruence 5x ≡ 3 (mod 11).Ans: 5 + 11k .7. Use the Principle of Mathematical Induction to prove that 1311392732n n+-++++...+= for alln ≥ 0.Ans: P (0):13112-= , which is true since 1 = 1. P (k ) → P (k + 1):111211313123311333222k k k k k k ++++++--+⋅-++...+=+==.8．Encrypt the message NEED HELP by translating the letters into numbers, applying the encryption function f(p ) = (3p + 7) mod 26, and then translating the numbers back into letters.Ans: Encrypted form: UTTQ CTOA.V. (6%) Without using the truth table, show that the following are tautologiesa) [⌝p ∧(p ∨q)]→q b) [p ∧(p →q)]→qAns:a) ⌝p ∧(p ∨q)≡(⌝p ∧p)∨(⌝p ∧ q)≡flase[⌝p ∧(p ∨q)]→q ≡ false →q ≡⌝false ∨q ≡true ∨q ≡true (3points)b)[p ∧(p →q)]→q ≡(⌝[p ∧(⌝p ∨q)])∨q ≡(⌝p ∨(p ∧⌝q))∨q ≡((⌝p ∨p)∧(⌝p ∨⌝q))∨q ≡⌝p ∨⌝q ∨q ≡true (3points)VI. (6%) Devise an algorithm which will find the minimum of n integers. What is the worst case time………密………封………线………以………内………答………题………无………效……complexity of this algorithm?a) procedure min(a1, a2, …, an: integers)(4points)v := a1 {largest element so far}for i := 2 to n {go thru rest of elems}if ai < v then v := ai {found smaller?}{at this poi nt v’s value is the same as the smallest integer in the list}return vb) the worst case time complexity of this algorithm is O(n). (2points)VII.(5%) Give the definition of a transitive relation, and Prove or disprove that the union of two transitive relations is transitive.Ans: A relation R on a set A is called transitive if only if (a,b)∈R and (b,c)∈R ,then (a,c) ∈R ,for a,b,c ∈A. (2points)The union of two transitive relations may be not transitive. A counter-example:A={1,2,3}, R1= {<1,1>, <2,3>}, R2={<1,2><3,3> }R1∪R2={<1.1>, <2,3><1,2><3,3>}, which is not transitive. (3points)VIII.(6%) Give an argument using rules of inference to show that the conclusion follows from the hypotheses. List all the steps in your argument.Hypotheses: All computer scientists like Star Trek. Sarah does not like Star Trek. Therefore, Sarah is not a computer scientist.Solution:Hypotheses: ∀x(ComputerScientist(x) →Likes(x, StarTrek))¬Likes(Sarah, StarTrek)Conclusion: ¬ComputerScientist(Sarah)Step 1: ∀x(ComputerScientist(x) →Likes(x, StarTrek)) (Hypothesis)Step 2: ComputerScientist(Sarah) →Likes(Sarah, StarTrek) (Univ. Inst. Step 1)Step 3: ¬Likes(Sarah, StarTrek) (Hypothesis)Step 4: ¬ComputerScientist(Sarah) (Modus Toll. St. 2+3)The argument is sound.Grading rubric: -3 points for making wrong assumptions.-2 points for not being able to complete the proof.-1 to -3 points for illegal usage of inference rules.。

Homework33.1: P177Ex4: set the answer to be . For i going from 1 through n-1, computer the value of the (i+1)st element in the list minus the i th element in the list. If this is larger than the answer, reset the answer to be this value.Ex27ternary(V, s, e)if s > ereturn -1elsem1 ←(e-s)/3 + sm2 ←2*(e-s)/3 + sif V = A[ m1 ]return m1else if V = A[ m2 ]return m2else if V < A[ m1 ]return ternary(V, s, m1-1)else if V < A[ m2 ]return ternary(V, m1+1, m2-1)elsereturn ternary(V, m2+1, e)3.2: P191Ex2 (a) Yes (c) Yes (e) NoEx20 The approach in these problems is to pick out the most rapidly growing term in each sum and discard the rest (including the multiplicative constants).a) O(n3log(n)) b) O(6n) c) O(n n n!)Ex28 (a) Choose C1=1 and C2=2, for all x>1, we have C1*3x2 <=3x2+x+1<=C2*3x2.Ex36 This does not follow. Let f(x)=2x and g(x)=x. then f(x) is O(g(x)). Now 2f(x)=4x, and 2g(x)=2x. The ratio 4x/2x=2x grows without bound as x grows—it is not bounded by a constant.3.3: P200Ex8a) Initially y:=3, for i=1 we set y to 7, for i=2 we set y to 15, and we are done.b) There is one multiplication and one addition for each of the n passes through the loop, so there are n multiplication and n additions in all.Ex10a) 1.224*10-6 seconds b) 1.05*10-3 seconds c) 1.13*106 seconds d) 1.27*1021 seconds3.4: P208Ex6 Under the hypotheses, we have c=as and d=bt for some s and t. Multiplying we obtain cd=ab(st), which means ab|cd, as desired.Ex24 Write n=2k+1 for some integer k. Then n 2=4k(k+1)+1. Since either k or k+1 is even, therefore n 2-1 is a multiple of 8, so n 2≡1 (mod 8).3.5: P217Ex10 These are 1,5,7,and 11.Ex32 From a ≡b (mod m) we know that b=a+sm for some integer s. Now if d is a common divisor of a and m, then it divides the right-hand side of this equation, so it dived b. We can rewrite the equation as a=b-sm, and then by similar reasoning, we see that every common divisor of b and m is also a divisor of a. This shows that the set of common divisors of a and m is equal to the set of common divisors of b and m, so certainly gcd(a,m)=gcd(b,m).3.6:P230Ex8 a) 1111 0111 becomes F7Ex28 d) 79=81-3+13.7: P244Ex4 Since 13*937-1=12180=2436*5, we have 13*937≡1(mod 2436).Ex12 We know from exercise 6 that 9 is an inverse of 2 modulo 17. Therefore if we multiply both sides of this equation by 9, we will get x ≡12 (mod 17)Ex18 x=2*20*2+1*15*3+3*12*3≡53 (mod 60).3.8: P255Ex16 The (i,j)th entry of (A t )t is the (j,i)th entry of (A t ), which is (i,j)th entry of A.Homework44.1: P279Ex6. The basis step is clear, since 1*1!=2!-1. Assuming the inductive hypothesis, we then have 1*1!+2*2!+….+k*k!+(k+1)*(k+1)!=(k+1)!-1++(k+1)*(k+1)!=(k+2)!-1.Ex38. The basis step is trivial, as usual: A 1⊆B 1. Assume the inductive hypothesis that if A j ⊆B j for j=1,2,…,k, then 11kkj j j j A B ==⊆U U . We want to show that if A j ⊆B j for j=1,2,…,k+1, then1111k kj j j j A B ++==⊆U U . To show that one set is a subset of another we show that an arbitraryelement of the first set must be an element of the second set. So letx ∈11k j j A +=U =11()kj j k A A =+U U . Either x ∈1kj j A =U or x ∈1k A +. In the first case we know bythe inductive hypothesis that x ∈1kj j B =U ; in the second case, we know from the given fact thatA k+1⊆B k+1 that x ∈1k B +. Therefore in either case x ∈11k j j B +=U .Ex49. In the inductive hypothesis, it assume x and y are positive integer. Therefore we can ’t conclude x-1=y-1 from max(x-1,y-1)=k since x-1 and y-1 can be not positive.4.2: P293Ex12. The basis step is to note that 1=20. Assume the inductive hypothesis, that every positive integer up to k can be written as a sum of distinct powers of 2. We must show that k+1 can be written as a sum of distinct powers of 2. if k+1 is odd, then k is even, so 20is not part of the sum for k. therefore the sum for k+1 is the same as the sum for k with the extra term 20added. If k+1 is even, then (k+1)/2 is a positive integer, so by the inductive hypothesis (k+1)/2 can be written as a sum of distinct powers of 2. Increasing each exponent by 1 doubles the value and give us the desired sum for k+1.4.3: P308Ex6. a) valid b) valid c) invalid d) invalid e) invalid.Ex28.a) basis step: (1,2)∈S, (2,1)∈S. recursive step: if (a,b) ∈S then (a+2,b)∈S, (a,b+2)∈S and (a+1,b+1)∈S.b) basis step: (1,1)∈S. recursive step: if (a,a) ∈S then (a+1,a+1)∈S; if (a,b) ∈S then (a,a+b)∈S.c) basis step: (1,2)∈S, (2,1)∈S. recursive step: if (a,b) ∈S then (a+3,b)∈S, (a,b+3)∈S, (a+1,b+2)∈S and (a+2,b+1)∈S.4.4: P321Ex12.Procedure power(x, n, m:positive intergers)If n=1 then power(x,n,m):=x mod mElse power(x,n,m):=(x*power(x,n-1,m)) mod m4.5: P327Ex2. There are two cases. If x>=0 initially, then nothing is executed, so x>=0 at the end. If x<0 initially, then x is set equal to 0, so x=0 at the end; hence again x>=0 at the end.。

英文离散数学试题及答案一、选择题（每题2分，共20分）1. 在集合论中，空集的符号表示为：A. ∅B. ∅∅C. ØD. ∅(∅)2. 布尔代数中，逻辑与（AND）操作的符号是：A. ∧B. ∨C. ¬D. →3. 如果一个命题P是真命题，那么¬P是：A. 假命题B. 真命题C. 既非真也非假D. 无法确定4. 在图论中，一个图的度是指：A. 顶点的数量B. 边的数量C. 每个顶点连接的边数D. 图中所有顶点的度数之和5. 以下哪个是有限自动机的组成部分：A. 状态B. 初始状态C. 转移函数D. 所有上述选项6. 以下哪个不是关系的性质：A. 反射性B. 对称性C. 传递性D. 唯一性7. 一个命题逻辑公式的真值表通常有多少行：A. 2B. 3C. 与变量的数量相同D. 与命题的数量相同8. 以下哪个是等价关系的属性：A. 传递性B. 非传递性C. 非对称性D. 非自反性9. 一个命题逻辑公式的否定等价于：A. 原公式的真值表中所有真值取反B. 原公式的逻辑或C. 原公式的逻辑与D. 原公式的逻辑异或10. 在组合数学中，排列与组合的区别在于：A. 排列考虑顺序B. 组合不考虑顺序C. 排列不考虑顺序D. 所有上述选项答案：1. A2. A3. A4. C5. D6. D7. C8. A9. A10. A, B二、简答题（每题5分，共30分）1. 简述集合的并集和交集的定义。

2. 解释什么是逻辑蕴涵，并给出一个例子。

3. 描述图的有向性和无向性的区别。

4. 阐述关系数据库中主键和外键的作用。

5. 什么是递归函数，并给出一个简单的例子。

6. 简述命题逻辑和谓词逻辑的区别。

三、计算题（每题10分，共30分）1. 给定集合A = {1, 2, 3}和B = {2, 3, 4}，求A∪B和A∩B。

2. 证明以下逻辑等价性：(P ∧ Q) → R ≡ P → (Q → R)。

P.161.14.f) If I did not buy a lottery ticket this week, then I did not win the million dollar jackpot on Friday.g) I did not buy a lottery ticket this week, and I did not win the million dollar jackpot on Friday.h ) Either I did not buy a lottery ticket this week, or else I did buy one and won the million dollar jackpot on Friday.10.a) r ∧┐q b) p ∧ q∧ r c)r → pd) p ∧┐q ∧ r e) (p ∧q) → r f) r↔ ( q ∨ p)20.a) If I am to remember to send you the address, then you will have to send me ane-mail message.(This has been slightly reworded so that the tenses make more sense.)b) If you were born in the United States, then you are a citizen of this country.c) If you keep your textbook, then it will be a useful reference in your future courses.(The word "then" is understood in English, even if omitted.)d) If their goaltender plays well, then the Red Wings will win the Stanley Cup.e) If you get the job, then you had the best credentials.f) If there is a storm, then the beach erodes.g) If you log on to the server, then you have a valid password.h) If you don’t begin your climb too late, then you will reach the summit.33.c)P.261.28.a) Kwame will not take a job in industry and he will not go to graduate school.b) Yoshiko doesn’t know Java or she doesn’t know calculus.c) James is not young or he is not strong.d) Rita will not move to Oregon and she will not move to Washington.10.a)c)12.a) Assume the hypothesis is true. Then p is false. Since p∨q is true, we conclude that q must be true.Here is a more "algebraic" solution:[┐p∧(p ∨q)]→q <=> ┐[┐p∧(p ∨q)]∨q <=> ┐┐p∨┐(p∨q)∨q <=> p∨┐(p∨q)∨q <=> (p ∨q)∨┐(p∨q) <=> Tc) Assume the hypothesis is true. Then p is true, and since the second part of the hypothesis is ture, we conclude that q is also true, as desired.51.((p ↓ p) ↓ q )↓((p ↓ p) ↓ q )7.The graph is planar.20.The graph is not homeomorphic to K3,3, since by rerouting the edge between a and h we seethat it is planar.22.Replace each vertex of degree two and its incident edges by a single edge. Then the result isK3,3 : the parts are {a,e,i} and {c,g,k}. Therefore this graph is homeomorphic to K3,3.23.The graph is planar.25. The graph is not planar.9.83. 3F E8. 310.417. time slot 1: Math 115, Math 185; time slot 2: Math 116, CS 473;time slot 3: Math 195, CS 101; time slot 4: CS 102time slot 5: CS 273P.461.33. a) true b) false c) false d) false5. a) There is a student who spends more than 5 hours every weekday in class.b) Every student spends more than 5 hours every weekday in class.c) There is a student who does not spend more than 5 hours every weekday in class.d) No student spends more than 5 hours every weekday in class.9. a) x(P(x)∧Q(x)) b) x(P(x)∧﹁Q(x))c) x(P(x)∨Q(x)) d) x﹁(P(x)∨Q(x))16. a) true b) false c) true d) false24. Let C(x) be the propositional function “x is in your class.”a)x P(x) and x(C(x)→P(x)), where P(x) is “x has a cellular phone.”b) x F(x) and x(C(x)∧F(x)), where F(x) is “x has seen a foreign movie.”c)x﹁S(x) and x(C(x)∧﹁S(x)), where S(x) is “x can swim.”d)x E(x) and x(C(x)→E(x)), where E(x) is “x can solve quad ratic equations.”e)x﹁R(x) and x(C(x)∧﹁R(x)), where R(x) is “x wants to be rich.”62.a) x (P(x)→﹁S(x)) b)x(R(x)→S(x))c) x (Q(x)→P(x))d)x(Q(x)→﹁R(x))e) Yes. If x is one of my poultry, then he is a duck (by part(c)), hence not willing to waltz (part (a)). Since officers are always willing to waltz (part (b)), x is not an officer.1.412.d)x┐C(x, Bob)h)x y (I(x) ∧((x≠y) →┐ I(y)))k)x y( I(x) ∧┐C(x, y))n)x y z ((x≠y) ∧┐ (C(x, z) ∧ C(y, z)))14.a) x H(x), where H(x) is “x can speak Hindi”and the universe of the discourse consists of all students in this class.b) x y P(x, y), where P(x, y) is “x plays y.” and the universe of the discourse for x consists of all students in this class, and the universe of the discourse for y consists of all sports.c) x A(x) ∧┐H(x) , where A(x) is “x has visited Alaska.” , H(x) is “x has visited Hawaii” and the universe of the discourse for x consists of all students in this class.d) x y L(x, y), where L(x, y) is “x has learned programming language y” and the universe of the discourse for x consists of all students in this class, and the universe of the discourse for y consists of all programming languages.e) x z y (Q(y,z) →P(x, y)), where P(x, y) is“x has taken course y.”, Q(y, z) is “course y is offered by department z.”, and the universe of the discourse for x consists of all students in this class, the universe of the discourse for y consists of all courses in this school, and the universe of the discourse for z consists of all departments in this school.f)x y z ( (x≠y) ∧P(x, y)∧ ((x≠y≠z) →┐P(x, z))), where P(x, y) is “x and y grew up in the same town.” and the universe of the discourse for x, y, z consists of all students in this class.g) x y z C(x, y) ∧G(y, z), where C(x, y) is “x has chatted with y”, G(y, z) is “y is in chat group z”, the universe of the discourse for x, y consists of all students in this class, and the universe of the discourse for z consists of all chat group in this class.a) There is an additive identity for the real numbers.d) The product of two nonzero numbers is nonzero for the real numbers.38.b) There are no students in this class who have never seen a computer.d) There are no students in this class who have taken been in at least one room of every building on campus.1.5(1)(┐r∧(q→p))→(p→(q∨r)) <=> ┐(┐r∧(┐q∨p))∨(┐p∨(q∨r)) <=>(q∧┐p)∨(┐p∨q∨r)<=> (┐p∨q∨r∨q)∧(┐p∨q∨r∨┐p) <=> (┐p∨q∨r) <=> ∏3 <=> ∑0,1,2,4,5,6,7 (2) P.726. Let r be the proposition "It rains", let f be the proposition "It is foggy", let s be the proposition "The sailing race will be held", let l be the proposition "The lifesaving demonstration will go on", and let t be the proposition "The trophy will be awarded". We are given premises (┐r∨┐f)→(s∧l), s→t, and ┐t. We want to conclude r. We set up the proof in two columns, with reasons. Note that it is valid to replace subexpressions by other expressions logically equivalent to them.Step Reason1. ┐t Hypothesis2. s→t Hypothesis3. ┐s Modus tollens using Steps 1 and 24. (┐r∨┐f)→(s∧l) Hypothesis5. (┐(s∧l))→┐(┐r∨┐f) Contrapositive of step 46. (┐s∨┐l)→(r∧f) De Morgan's law and double negative7. ┐s∨┐l Addition, using Step 38. r∧f Modus ponens using Step 6 and 79. r Simplification using Step 8First, using the conclusion of Exercise 11, we should show that the argument form with premises (p ∧t) → (r ∨s), q→ (u ∧t), u→p, ┐s, q, and conclusion r is valid. Then, we use rules of inference from Table 1.Step Reason1. q Premise2. q→ (u ∧t)P remise3. u ∧t Modus ponens using Steps 1 and 24. u Simplification using Step 35. u→p Premise6. p Modus ponens using Steps 3 and 47. t Simplification using Step 38. p ∧t Conjunction using Steps 6 and 79. (p ∧t) → (r ∨s) Premise10. r ∨s Modus ponens using Steps 8 and 911. ┐s Premise12. r Disjunctive syllogism using Steps 10 and 11 14．b)Let R(x) be “x is one of the five roommates,” D(x) be “x has taken a course in discrete mathematics,” and A(x) be “x can take a course in algorithms.” The premises are x (R(x) → D(x)), x (D(x) → A(x)) and R(Melissa). Using the first premise and Universal Instantiation, R(Melissa) → D(Melissa) follows. Using the third premise and Modus Ponens, D(Melissa) follows. Using the second premise and Universal Instantiation, A(Melissa) follows. So do the other roommates.d) Let C(x) be “x is in the class,”F(x) be “x has been to France,” and L(x) be “x has visited Louvre.” The premises are x(C(x) ∧F(x)) and x (F(x) → L(x)). From the first premise and Existential Instantiation imply that C(y) ∧F(y) for a particularperson y. Using Simplification, F(y) follows. Using the second premise and Universal Instantiation F(y) → L(y) follows. Using Modus Ponens, L(y) follows. Using Existential Generalization, x(C(x) ∧L(x)) follows.24. The errors occur in steps (3), (5) and (7).For steps (3) and (5), we cannot assume, as is being done here, that the c that makes P(x) true is the same as the c that makes Q(x) true at the same time. For step (7), it is not a conjunction and there is no such disjunction rule.29.Step Reason1. x ┐P(x) Premise2. ┐P(c) Existential instantiation from (1)3. x (P(x) ∨Q(x)) Premise4. P(c) ∨Q(c) Universal instantiation from (3)5. Q(c) Disjunctive syllogism from (2) and (4)6. x (┐Q(x) ∨S(x)) Premise7. ┐Q (c) ∨S(c) Universal instantiation from (6)8. S(c) Disjunctive syllogism from (5) and (7)9. x (R(x) →┐S(x)) Premise10. R(c) →┐S(c) Universal instantiation from (9)11. ┐R(c) Modus tollens from (8) and (10)12. x ┐R(x) Existential generalization from (11)P.861.637.Suppose that P1→P4→P2→P5→P3→P1. To prove that one of these propositions implies any of the others, just use hypothetical syllogism repeatedly.P.1031.713.a) This statement asserts the existence of x with a certain property. If we let y=x, then we see that P(x) is true. If y is anything other than x, then P(x) is not true. Thus, x is the unique element that makes P true.b) The first clause here says that there is an element that makes P true. The second clause says that whenever two elements both make P true, they are in fact the same element. Together these say that P is satisfied by exactly one element.c) This statement asserts the existence of an x that makes P true and has the further property that whenever we find an element that makes P true, that element is x. In other words, x is the unique element that makes P true.P.1202.19.T T F T T F16. Since the empty set is a subset of every set, we just need to take a set B that contains Φ as an element. Thus we can let A = Φ and B = {Φ} as the simplest example.20 .The union of the sets in the power set of a set X must be exactly X. In other words, we can recover X from its power set, uniquely. Therefore the answer is yes.22.a) The power set of every set includes at least the empty set, so the power set cannot be empty. Thus Φ is not the power set of any set.b) This is the power set of {a}c) This set has three elements. Since 3 is not a power of 2, this set cannot be the power set of any set.d) This is the power set of {a,b}.28.a) {(a,x,0), (a,x,1), (a,y,0), (a,y,1), (b,x,0), (b,x,1), (b,y,0), (b,y,1), (c,x,0), (c,x,1), (c,y,0), (c,y,1)}c) {(0,a,x), (0,a,y), (0,b,x), (0,b,y), (0,c,x), (0,c,y), (1,a,x), (1,a,y), (1,b,x), (1,b,y), (1,c,x), (1,c,y)}P.1302.214. Since A = (A - B)∪(A∩B), we conclude that A = {1,5,7,8}∪{3,6,9} ={1,3,5,6,7,8,9}. Similarly B = (B - A)∪(A ∩ B) = {2,10}∪{3,6,9} = {2,3,6,9,10}.24. First suppose x is in the left-hand side. Then x must be in A but in neither B nor C. Thus x∈A - C, but x B - C, so x is in the right-hand side. Next suppose that x is in the right-hand side. Thus x must be in A - C and not in B - C. The first of these implies that x∈A and x C. But now it must also be the case that x B, since otherwise we would have x∈B - C. Thus we have shown that x is in A but in neither B nor C, which implies that x is in the left-hand side.40. This is an identity; each side consists of those things that are in an odd number of the sets A,B,and C.P147.2.335a) This really has two parts. First suppose that b is in f(S∪T). Thus b=f(a) for somea∈S∪T. Either a ∈S, in which case b∈f(S), or a∈T, in which case b∈f(T). Thus in either case b∈ f(S) ∪f(T). This shows that f(S∪T) ⊆f(S) ∪f(T), Conversely, suppose b∈f(S) ∪f(T). Then either b∈f(S) or b∈f(T). This means either that b=f(a) for some a∈S or that b=f(a) for some a ∈T. In either case, b=f(a) for some a∈S∪T, so b∈f(S∪T). This shows that f(S) ∪f(T) ⊆f(S∪T), and our proof is complete. b)Suppose b∈f(S∩T). Then b=f(a) for some a∈S∩T. This implies that a∈S anda∈T , so we have b∈f(S) and b∈f(T). Therefore b∈f(S)∩f(T), as desired.52In some sense this question is its own answer—the number of integers between a and b, inclusive, is the number of integers between a and b, inclusive. Presumably we seek an express involving a, b, and the floor and/or ceiling function to answer this question. If we round a up and round b down to integers, then we will be looking at the smallest and largest integers just inside the range of the integers we want to count, respectively. These values are of course ⎡⎤a and ⎣⎦b, respectively. Then the answer isb-+1 (just think of counting all the integers between these two values, ⎣⎦⎡⎤aincluding both ends—if a row of fenceposts one foot apart extends for k feet, then there are k +1 fenceposts). Note that this even works when, for example, a=0.3 and b=0.7 .P1622.434.a) This is countable. The integers in the set are ±1,±2,±4,±5,±7,andso on. We can listthese numbers in the order 1, -1 , 2, -2, 4, -4,…, thereby establishing the desired correspondence. In other words, the correspondence is given by 1↔1，2↔-1，3↔2，4↔-2，5↔4，and so on.b) This is similar to part(a);we can simply list the elements of the set in order ofincreasing absolute value, listing each positive term before its correspondingnegative:5,-5,10,-10,15,-15,20,-20,30,-30,40,-40,45,-45,50,-50,……c) This is countable but a little tricky. We can arrange the numbers in a 2-dimensionaltable as follows:1..1 0.11 0.111 0.1111 0.11111 ……1.1 1 1.1 1.11 1.111 1.1111 ……1.1111 11.1 11.11 11.111 11.1111 ……1111.111 111.1 111.11 111.111 111.1111 ……………………………………d) This set is not countable. We can prove it by the same diagonalization argument aswas used to prove that the set of all reals is uncountable in Example 21.All we need to do is choose d i=1 when d ii=9 and choose d i=9 when d ii=1 or d ii is blank(if the decimal expansion is finite)46.We know from Example 21 that the set of real numbers between 0 and 1 is uncountable. Let us associate to each real number in this range(including 0 but excluding 1) a function from the set of positive integers to the set {0,1,2,3,4,5,6,7,8,9} as follows: If x is a real number whose decimal representation is 0.d1d2d3…(with ambiguity resolved by forbidding the decimal to end with an infinite string of9's),then we associate to x the function whose rule is given by f(n)=d n. clearly this is a one-to-one function from the set of real numbers between 0 and 1 and a subset of the set of all functions from the set of positive integers the set {0,1,2,3,4,5,6,7,8,9}.Two different real numbers must have different decimal representations, so the corresponding functions are different.(A few functions are left out, because of forbidding representations such as 0.239999…)Since the set of real numbers between 0 and 1 is uncountable, the subset of functions we have associated with them must be uncountable. But the set of all such functions has at least this cardinality, so it, too, must be uncountable.P1913.21. The choices of C and k are not unique.a) Yes C = 1, k = 10 b) Yes C = 4, k = 7 c) Nod) Yes C = 5, k = 1 e) Yes C = 1, k = 0 f) Yes C = 1, k = 29. x2+4x+17 ≤ 3x3 for all x＞17, so x2+4x+17 is O(x3), with witnesses C = 3, k=17. However, if x3 were O(x2+4x+17), then x3≤C(x2+4x+17) ≤ 3Cx2for some C, for all sufficiently large x, which implies that x≤ 3C, for all sufficiently large x, which is impossible.P2093.419.a) no b) no c) yes d) no31.a) GR QRW SDVV JRb) QB ABG CNFF TBc) QX UXM AHJJ ZXP2183.513.a) Yes b) No c) Yes d) Yes17a) 2 b) 4 c) 12P2804.122.A little computation convinces us that the answer is that n2 ≤ n! for n= 0, 1, and all n≥ 4. (clearly the inequality doesn’t hold for n=2 or n=3) We will prove by mathematical induction that the inequality holds for all n≥ 4. The base case is clear, since 16 ≤ 24. Now suppose that n2 ≤ n! for a given n≥ 4. We m ust show that (n+1)2≤ (n+1)!. Expanding the left-hand side, applying the inductive hypothesis, and then invoking some valid bounds shows this:n2 + 2n+ 1 ≤ n! + 2n + 1≤ n! + 2n + 1 = n! + 3n≤ n! + n·n≤ n! + n·n!≤ (n+1)n! = (n+1)!P2934.231.Assume that the well-ordering property holds. Suppose that P(1) is true and that the conditional statement [P(1)∧P(2) ∧···∧P(n)] →P(n+1) is true for every positive integer n. Let S be the set of positive integers n for which P(n) is false. We will show S=Ø. Assume that S≠Ø, then by the well-ordering property there is a least integer m in S. We know that m cannot be 1 because P(1) is true. Because n=m is the least integer such that P(n) is false, P(1), P(2),…,P(m-1) are true, and m-1 ≥1. Because [P(1)∧P(2) ∧···∧P(m-1)] →P(m) is true, it follows that P(m) must also be true, which is a contradiction. Hence, S= Ø.P3084.310.The base case is that S m(0)=m. The recursive part is that S m(n+1) is the successor of S m(n)(i.e., S m(n)+1)12.The base case n=1 is clear, since f12=f1f2=1. Assume the inductive hypothesis. Thenf12+f22+…+f n2+f n+12 = f n+12+f n f n+1= f n+1(f n+1+f n)= f n+1f n+2, as desired.31.If x is a set or variable representing set, then x is well-formed formula. if x and y are all well-formed formulas, then x, (x∪y), (x∩y) and (x-y) are all well-formed formulas.50.Let P(n) be “A(1, n) = 2n .”BASIC STEP: P(1) is true, because P(1) = A(1, 1) = 2 = 21.INDCUTIVE STEP: Assume that P(m) is true, that is A(1, m) = 2m and m≥1. Then P(m+1) = A(1, m+1) = A(0, A(1, m))= A(0, 2m)=2·2m=2m+1.So A(1, n) = 2n whenever n≥159.b) Not well defined. F(2) is not defined since F(0) isn’t.Also, F(2) is ambiguous.d) Not well defined. The definition is ambiguous about n=1.P3445.13.a) 104b) 10512.We use the sum rule, adding the number of bit strings of each length up to 6. If we include the empty string, then we get 20 + 21 + 22 + 23 + 24 + 25 + 26= 27–1=12720.a) Every seventh number is divisible by 7. Therefore there are 999 / 7=142such numbers. Note that we use the floor function, because the k th multiple of 7 does not occur until the number 7k has been reached.b) For solving this part and the next four parts, we need to use the principle of inclusion-exclusion. Just as in part(a), there are 999/11=90 numbers in our range divisible by 11, and there are 999/77=12 numbers in our range divisible by both 7 and 11 (the multiples of 77 are the numbers we seek). If we take these 12 numbers are away from the 142 numbers divisible by 7, we see that there are 130 numbers in our range divisible by 7 but not by 11.c) as explained in part(b), the answer is 12.d) By the principle of inclusion-exclusion, the answer, using the data from part (b), is 142+90-12=220.e) If we subtract from the answer to part(d) the number of numbers divisible by neither of them; so the answer is 220-12=208.f) If we subtract the answer to part(d) from the total number of positive integers less than 1000, we will have the number of numbers divisible by exactly one of them; so the answer is 999-220=779.g) If we assume that numbers are written without leading 0s, then we should break the problem down into three cases-one-digit numbers, two-digit numbers. Clearly there are 9 one-digit numbers, and each of them has distinct digits. There are 90 two-digit numbers (10 through 99), and all but 9 of them have distinct digits. An alternativeway to compute this is to note that the first digit must be 1 through 9 (9 choices) and the second digit must be something different from the first digit (9 choices out of the 10 possible digits), so by the product rule, we get 9*9=81 choices in all. This approach also tells us that there are 9*9*8=648 three-digit numbers with distinct digits (again, work from left to right-in the ones place, one 8 digits are left to choose from). 80 the final answer is 9+81+648=738.h) It turns out to be easier to count the odd numbers with distinct digits and subtract from our answer to part(g), so let us proceed that way. There are 5 odd one-digit numbers. For two-digit numbers, first choose the one digit (5 choices), then choose the tens digits (8 choices), since neither the ones digit value not 0 is available); therefore there are 40 such two-digit numbers. (Note that this is not exactly half of 81.) For the three-digit numbers, first choose the ones digit (5 choices), then the hundreds digit (8 choices), then the tens digit (8 choices), giving us 320 in all. So there are 5+40+320=365 odd numbers with distinct digits. Thus the final answer is 738-365=373.35.a) 若n=1, 为2；若n=2, 为2; 若n>=3, 为0b) 对于n>1, 为22 n；若n=1, 为1；c) 2(n-1) (注：n可映射到0，1两种可能)44.First we count the number of bit strings of length 10 that contain five consecutive 0’s. We will base the count on where the string of five or more consecutive 0’s starts. If it starts in the first bit, then the first five bits are all 0’s, but there is free choice for the last five bits; therefore there are 25 = 32 such strings. If it starts in the second bit, then the first bit must be a 1, the next five bits are all 0’s, but there is free choice for the last four bits; therefore there are 24 = 16 such strings. If it starts in the third bit, then the second bit must be a 1 but the first bit and the last three bits are arbitrary; therefore there are 24= 16 such strings. Similarly, there are 16 such strings that have the consecutive 0’s starting in each of positions four, five ,and six. This gives us a total of 32+5×16=112 strings that contain five consecutive 0’s. Symmetrically, there are 112 strings that contain five consecutive 1’s. Clearly there are exactly two strings that contain both (0000011111,1111100000). Therefore by the inclusion-exclusion principle, the answer is 2*(112)-2=222.52.We draw the tree, with its root at the top. We show a branch for each of the possibilities 0 and 1, for each bit in order, except that we do not allow three consecutive 0’s. Since there are 13 leaves, the answer is 13.second bitthird bitfourth bitP3535.26.There are only d possible remainders when an integer is divided by d, namely 0, 1, …, d-1. By the pigeonhole principle, if we have d+1 remainders, then at least two must be the same.10.The midpoint of the segment whose endpoints are (a,b) and (c,d) is ( ( a + c ) / 2, ( b + d ) / 2). We are concerned only with integer values of the original coordinates. Clearly the coordinates of these fractions will be integers as well if and only if a and c have the same parity (both odd or both even) and b and d have the same parity. Thus what matters in this problem is the parities of coordinates. There are four possible pairs of parities: (odd,odd), (odd, even), (even, even) and (even,odd). Since we are given five points, the pigeonhole principle guarantees that at least two of them will have the same pair of parties. The midpoint of the segment joining these two points will therefore have integer coordinates.38.a) T b) Tc) T1 ≤a1< a2 < …< a75≤ 125 , and 26 ≤a1 + 25 < a2 + 25 < …< a75 + 25 ≤ 150.Now either of these 150 numbers are precisely all the number from 1 to 150, or else by the pigeonhole principle we get, as in Exercise 37, a i = a j + 25 for some i and j and we are done. In the former case, however, since each of the number a i + 25 is greater than or equal to 26, the numbers 1, 2, … , 25 must all appear among the a i’s. But since the a i’s are increasing, the only way this can happen is if a1=1, a2 =2 , …, a25=25. Thus there were exactly 25 matches in the first25 hours.d) TWe need a different approach for this part, an approach, incidentally, that works for many numbers besides 30 in this setting. Let a1, a2 , …a75 be as before, and note that 1 ≤a1< a2 < …< a75≤ 125. By the pigeonhole principle two of the numbers among a1, a2 , …a 31 are congruent modulo 30. If they differ by 30, then we have our solution. Otherwise they differ by 60 or more, so a 31 ≥ 61. Similarly, among a 31through a 61 ,either we find a solution, or two numbers must differ by 60 or more; therefore we assume that a 61 ≥ 121. But this means that a 66 ≥ 126, a contradiction.注：38题d 因为30大于25，不能用解决a，b，c的方法解决，所以适用一种新的方法（这种方法对前面3问同样适用的）。