《离散》09-10试题

安徽大学计算机学院2010 —20 11 学年第 1 学期《离散数学---数理逻辑部分》测试试卷院/系 计算机 年级 09 专业 计算机科技 姓名 倪晨 学号 E10914029一、填空题（每小题1分，共16分）1、 判断下列公式的类型① (P Q)( P Q R)∨⌝→⌝∧∧是 偶然 式；② (Q P)(P Q)→∧⌝∧是 永假 式； ③ ()P (P Q P →∧→是 永真 式；2、 命题联结词有 否定 、合取 、 析取 、 蕴含 、 等值 。

3、 含有n 个命题变元的主析取范式的个数是 2的2n 个 。

4、 辖域：紧接在量词之后最小的子公式 。

5、 命题公式P 与()()P Q P Q ∧∨∧⌝是 等值 （等值、不等值）。

6、 ()()()(),,,x y P x y Q x y xP x y ∀∀∧∧∃的自由变元是 y 。

7、 已知公式A 含有两个命题变元，且A 的主析取范式为12m m ∨，则它的主合取范式为 ()()P Q P Q ⌝∨⌝∧∨。

8、 假言推理的规则为 如果P 且P →Q 是真 则Q 。

9、 “中国有四大发明” 是（是，不是）命题。

10、 谓词公式()()()(),,,,x Px y tQ t z R x y t ∀∧∃→中量词∃的辖域为 Q(t,z) 。

二、选择题（每小题2分，共20分） 1、 下列语句中哪个是真命题（ C ） （A ）我正在说谎（B ）如果1+2=3，那么雪是黑的 （C ）如果1+2=5，那么雪是黑 （D ）严禁吸烟2、 下面哪个命题公式是重言式（B ） （A ）()()P Q Q P →∧→ （B ）()P Q P ∧→（C ）()()P Q P Q ⌝∨∧⌝⌝∧⌝ （D ）()P Q ⌝∨3、 下列推理不正确的是（A ） （A ）()P Q P Q →∧→ （B ）()P Q P P →∧→ （C ）()P Q P Q ∨∧⌝→ （D ）()P Q Q P →∧→4、 设论述域为整数集，下列公式中哪个的值为真（ B ） （A ）()0x y x y ∀∃+= （B ）()0x y x y ∃∀+= （C ）()0x y x y ∀∀+=（D ）()0x y x y ⌝∃∃+=5、 设个体域为A={a,b},公式()()xP x xS x ∀∧∃在A 上消去量词后应为（ B ） （A ）()()P x S x ∧（B ）()()()()()P a P b S a S b ∧∧∨ （C ）()()P a P b ∧（D ）()()()()P a P b S a S b ∧∧∨6、 设P ：我去镇上，Q ：我有时间。

安阳师范学院计算机与信息工程学院09计科、09网络、09软件工程（Java 方向）、09软件工程（.net 方向）专业《离散数学》考试2009—2010学年下学期期末考试试卷A一、填空题 ( 本大题共10空，每空2 分，共 20 分, 请将答案写在下面。

)1.设P ：2+2=4；Q ：3是奇数；将命题“2+2=4，当且仅当3是奇数”符号化 Q<->P ，其真值为 真 。

2. 设论域是{a,b,c}，则∀xP(x)等价于命题公式 P(a)/\P(b)/\P(c) ，x ∃P(x)等价于命题公式 P(a)\/P(b)\/P(c) 。

3.设全集合为U={1,2,3,4,5}，A={1,5},B={1,2,3,4},C={2,5},求__A B C = {1,3,4} ，()()A B ρρ = {{},{1}} 。

4. 非空集合上的空关系所不具有的特性是 自反性 。

5. 集合S={1，2，3，4，5}，S 的划分为{{1，2},{3},{4，5}}，确定由S 的划分所诱导出的等价关系为：R= 。

6.设f 是从X 到Y 的函数,如果f (X )=Y , 那么f 是 满射 ，如果x ≠x ′蕴含着f (x )≠f (x ′) (即f (x )=f (x ), 那么x =x ′), 那么f 是 单射的 .1. ， 。

2. ， 。

3. ， 。

4. 。

5. 。

6. ， 。

二、选择题 (本大题共 10 小题，每小题 2 分，共 20 分，请将答案写在下面的答1.对命题变元P 、Q 、R 而言，下列是极大项的是___C______。

A.P ⌝B.Q P ∨C.R Q P ∨⌝∨D.R Q P ∧∧⌝2.下列不是逻辑恒等式是（C ）A.∀xA ⇔AB.A →∀xB(x)⇔ ∀x(A →B(x))C.∃x(A(x)∧B(x))⇔∃xA(x)∧∃xB(x)D.∀x(A(x)∧B(x))⇔ ∀xA(x)∧∀xB(x)3．谓词公式∃xP(x,y)∧∀x(Q(x,z)→∃x ∀yR(x,y,z))中量词∀x 的辖域是（ ）A.∀xQ(x,z)→∃x ∀yR(x,y,z))B.Q(x,z)→∀yR(x,y,z)C.Q(x,z)→∃x ∀yR(x,y,z)D.Q(x,z)4．设A={Φ},B=(())A ρρ,以下正确的式子是_________。

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).。

第九章 图9.1设},,,,{y x w v u V =，画出图),(E V G =，其中：（1）)},(),,(),,(),,(),,{(y x y v w v x u v u E =（2）)},(),,(),,(),,(),,{(y x y w x w w v v u E =再求各个顶点的度数。

解（1）见图9.1(a )。

其中顶点u 的度数是2，顶点v 的度数是3，顶点x 的度数是2，顶点y 的度数是2，顶点w 的度数是1。

图9.1 习题1图（2）见图9.1(b )。

其中顶点u 的度数是1，顶点v 的度数是2，顶点x 的度数是2，顶点y的度数是2，顶点w 的度数是3。

9.2 设G 是具有4个顶点的完全图。

（1）画出图G 。

（2）画出G 的所有互不同构的生成子图？解（1）如图9.2(1)所示。

图9.2(1) 习题2图（2） 如图9.6(2)所示﹒ ﹒ ﹒ ﹒ ﹒ ﹒图9.2(2) 习题2图9.3 一个无向简单图，如果同构于它的补图，则称这个图为自互补图。

（1）试画出五个顶点的自互补图。

（2）证明一个自互补图一定只有k 4或14+k 个顶点（k 为整数）。

解（1）(a) (b)图9.3 习题3图 （2）因为n 个顶点的无向完全图有)1(21-n n 条边，所以自互补图有)1(41-n n 条边，因此，k n 4=或14+k 。

9.4 画出两个不同构的简单无向图。

每一个图都仅有6个顶点，且每个顶点都均是3度，并指出这两个图为什么不同构。

解图9.4 习题9.4图9.5 证明任意两个同构的无向图，一定有一个同样的顶点度序列。

顶点度序列是一组按大小排列的正整数。

每一个数对应某一个顶点的度数。

证明两个同构的无向图，度数相同的顶点数目一定相同，这样才能够建立起顶点之间的一一对应关系，进而建立起边的对应关系。

所以，任意二个同构的无向图，一定有一个同样的顶点度序列。

9.6图9.6中所给的图(a )与图(b )是否同构？为什么？(a )(b ) 图9.6 习题6图 解左图9.2（a ）中次数为4的点，与3个度数为1，一个度数为2的顶点相邻接，右图9.2（b ）中度数为4的点，却与3个度数为1，一个度数为3的顶点相邻接。

离散数学试题与答案试卷一一、填空 20% （每小题2分）1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =⋃B A 。

2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为。

3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。

4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为。

5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ∀→∃ 在I 下真值为 。

6．设A={1，2，3，4}，A 上关系图为则 R 2 = 。

7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则 R= 。

8．图的补图为 。

9．设A={a ，b ，c ，d} ，A 上二元运算如下：那么代数系统<A ，*>的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。

10．下图所示的偏序集中，是格的为 。

二、选择 20% （每小题 2分）1、下列是真命题的有（ ）A ． }}{{}{a a ⊆；B ．}}{,{}}{{ΦΦ∈Φ；C ． }},{{ΦΦ∈Φ；D ． }}{{}{Φ∈Φ。

2、下列集合中相等的有（ ）A ．{4，3}Φ⋃；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。

3、设A={1，2，3}，则A 上的二元关系有（ ）个。

A ． 23 ；B ． 32 ；C ． 332⨯；D ． 223⨯。

4、设R ，S 是集合A 上的关系，则下列说法正确的是（ ）A ．若R ，S 是自反的， 则S R 是自反的；B ．若R ，S 是反自反的， 则S R 是反自反的；C ．若R ，S 是对称的， 则S R 是对称的；D ．若R ，S 是传递的， 则S R 是传递的。

5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下|}||(|)(,|,{t s A p t s t s R =∧∈><=则P （A ）/ R=（ ）A ．A ；B ．P(A) ；C ．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D ．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}6、设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“⊆”的哈斯图为（ ）7、下列函数是双射的为（ ）A ．f : I →E , f (x) = 2x ；B ．f : N →N ⨯N, f (n) = <n , n+1> ；C ．f : R →I , f (x) = [x] ；D ．f :I →N, f (x) = | x | 。

中南大学考试试卷2009 -- 2010 学年 一 学期期末考试试题 时间100分钟离散数学课程48学时3学分 考试形式：闭卷一、判断（本大题共10小题，每小题1分，共10分）（ ）1．ρ(A) ⊆ ρ(B) <=> A 是B 的子集（ ）2．Q ∧R ∨P ∧R ∨T ∧¬P ∧R 的对偶式为Q ∨R ∧P ∨R ∧F ∨¬P ∨R （ ）3．设Ａ和Ｂ是两个命题公式，若Ａ=＞B 且B 是重言式，则A 是重言式。

（ ）4．R 和S 都是集合A 上的关系，若R 和S 是自反的，则R ︒S 是自反的。

（ ）5．设A 、B 和C 是集合，若A ∩B=A ∩C ，且Φ≠A，则B=C 。

（ ）6．若R 和S 都是集合A 上的二元关系，则dom(R)∪dom(S)=dom(R ∪S)。

（ ）7．<A ; R>是全序集，则A 的任何非空子集必有唯一极小元。

（ ）8．有限集上的全序关系必是良序关系。

（ ）9．连通的4度正则图一定没有桥。

（ ）10.设无向图G 具有割点，则G 中一定不存在哈密尔顿通路。

二、单项选择（本大题共6小题，每小题2分，共12分）（ ）1．若公式A(P ,Q,R)的主合取范式为∏（0，1，4，5），则下列公式哪个是A(P,Q,R)的主析取范式① ∑（0，1，4，5） ② ∏（0，1，4，5） ③ ∑（2，3，6，7） ④ ∏（2，3，6，7）（ ）2．设∏1和∏2都是非空集合A 的划分，则下列集合哪个必定是A 的划分① ∏1∪∏2 ② ∏1∩∏2 ③ ∏1—∏2 ④（∏1∩（∏2—∏1））∪∏2（ ）3．设A-B=Φ，则下列命题中正确的是① B=Φ ② B ≠Φ ③ A ⊆B④ B ⊆ A（ ）4．设R 是集合A 上的偏序关系，R -1 是R 的逆关系，则R ∪R -1是①偏序关系 ②等价关系③非自反关系④非传递关系（ ）5．若f 、g 是A 上的双射，则①g f 是双射②)g f ( -1 =f -1 g -1③fg g f = ④ 以上答案都不对（ ）6．任何无向图中结点间的可达关系是 ① 偏序关系 ② 等价关系③ 全序关系④ 拟序关系三、 填空（本大题共9小题，每空2分，共24分）1． 若简单连通平面图G 有4个结点，3个面，则G 有______条边。

离散期末考试题及答案离散数学期末考试题及答案一、选择题（每题2分，共20分）1. 在集合论中，以下哪个符号表示属于关系？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 有限集合A和B的并集，其元素个数最多是A和B元素个数之和，这个性质称为：A. 德摩根定律B. 幂集C. 并集原理D. 子集原理答案：C3. 命题逻辑中，以下哪个命题是真命题？A. (p ∧ ¬p) ∨ qB. (p ∨ ¬p) ∧ qC. (p ∨ q) ∧ ¬pD. (p ∧ q) ∨ ¬p答案：B4. 在图论中，一个无向图的边数至少是顶点数的多少倍才能保证图中至少存在一个环？A. 1B. 2C. 3D. 4答案：B5. 以下哪个算法用于生成一个集合的所有子集？A. 欧拉回路B. 哈密顿回路C. 深度优先搜索D. 子集生成算法答案：D6. 在关系数据库中，以下哪个操作用于删除表中的行？A. SELECTB. INSERTC. UPDATED. DELETE答案：D7. 以下哪个是有限自动机的状态？A. 初始状态B. 终止状态C. 转移状态D. 所有选项答案：D8. 以下哪个是图论中的一个基本定理？A. 欧拉定理B. 哈密顿定理C. 狄拉克定理D. 所有选项答案：D9. 在命题逻辑中，以下哪个是德摩根定律的逆命题？A. ¬(p ∨ q) ≡ ¬p ∧ ¬qB. ¬(p ∧ q) ≡ ¬p ∨ ¬qC. ¬(p ∨ q) ≡ ¬p ∨ ¬qD. ¬(p ∧ q) ≡ ¬p ∧ ¬q答案：B10. 在集合论中，以下哪个操作表示集合的差集？A. ∩B. ∪C. -D. ×答案：C二、填空题（每空3分，共30分）11. 集合{1, 2, 3}的幂集包含________个元素。

离散考试试题及答案一、选择题（每题5分，共20分）1. 在离散数学中，下列哪个概念不是布尔代数的基本运算？A. 与B. 或C. 非D. 模答案：D2. 集合论中，下列哪个符号表示“属于”关系？A. ∈B. ∉C. ⊆D. ⊂答案：A3. 命题逻辑中，下列哪个符号表示“蕴含”关系？A. ∧B. ∨C. →D. ↔答案：C4. 关系R在集合A上是自反的，意味着什么？A. 对于所有a∈A，(a, a)∈RB. 对于所有a∈A，(a, a)∉RC. 对于所有a∈A，(a, b)∈RD. 对于所有a∈A，(a, b)∉R答案：A二、填空题（每题5分，共20分）1. 一个集合的基数是集合中元素的________。

答案：数量2. 在有向图中，如果存在一条从顶点u到顶点v的路径，则称顶点v 是顶点u的________。

答案：可达的3. 一个图是连通的，当且仅当图中任意两个顶点都是________。

答案：连通的4. 在命题逻辑中，一个命题的否定是________。

答案：它的对立命题三、简答题（每题10分，共30分）1. 请解释什么是图的哈密顿回路。

答案：哈密顿回路是一个图中的闭合回路，它恰好访问图中的每个顶点一次。

2. 描述一下什么是二元关系，并给出一个例子。

答案：二元关系是定义在两个集合上的一个关系，它关联了第一个集合中的元素和第二个集合中的元素。

例如，小于关系是数字集合上的一个二元关系。

3. 什么是图的生成树？答案：图的生成树是图的一个子图，它包含图中的所有顶点，并且是一棵树，即它是连通的且没有环。

四、计算题（每题15分，共30分）1. 给定一个集合A={1,2,3,4,5}，计算它的幂集。

答案：幂集P(A)={∅, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5},{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}, A}。

离散考试题与答案一、选择题1. 下列哪个不是离散数学的基本概念？A. 集合B. 二进制C. 图论D. 函数答案：C2. 设A = {1, 2, 3, 4}，B = {3, 4, 5, 6}，则A ∩ B = ?A. {1, 2}B. {3, 4}C. {5, 6}D. {3, 4, 5, 6}答案：B3. 在一个完全图中，有多少条边？A. nB. n(n-1)/2C. n(n+1)/2D. 2n答案：B4. 若f(x) = x^2 + 3x，则f(-2)的值为？A. -4B. -2C. 0D. 2答案：C5. 若A = {a, b, c}，B = {b, c, d}，则A - B = ?A. {a, b, c}B. {b, c, d}C. {a, d}D. {}答案：A二、填空题1. 设f(x) = x^2 + 5，求f(-3)的值。

答案：162. 设A = {1, 2, 3}，B = {3, 4, 5}，则A ∪ B = ？答案：{1, 2, 3, 4, 5}3. 在一个有向图中，若存在一条从顶点A到顶点B的路径，并且从B到A也存在一条路径，则该图称为_____图。

答案：强连通图4. 二进制数11111111转换为十进制的结果为______。

答案：2555. 若给定集合A = {1, 2, 3, 4}，则集合A的所有子集的个数为______。

答案：16三、简答题1. 解释集合的并、交和差的运算。

答案：集合的并运算指的是将两个集合中的所有元素合并成一个新的集合，新集合中的元素包括原来两个集合中的所有元素，但不重复。

集合的交运算指的是求出两个集合中共有的元素，构成一个新的集合。

集合的差运算指的是在一个集合中去除另一个集合中的元素，得到一个新的集合。

2. 什么是图论？答案：图论是研究图及其在各个领域中的应用问题的一门学科。

图由若干个顶点及连接这些顶点的边构成，图论主要研究图的性质、结构和算法问题。

3. 什么是函数？答案：函数是一种将每个输入值唯一对应到输出值的关系。

1期末考试参考答案（A 卷） 2009-2010学年第二学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 一、判断题（本大题共10小题，每小题1分，共10分） 说明：正确答“√”，错误答“×”。

二、选择题（本大题共18小题，每小题2分，共36分）三、填空题（本大题共10空，每小题1.5分，共15分）1、 14 ；2、E v Vv i i 2)deg(=∑∈ ；3、)(x y y x >∃∀；4、Φ；5、S ；6、 3 ；7、 1 ；8、1；9、)()(R Q P R Q P ⌝∨∨∧∨∨； 10、001000M M ∧；2四、计算题（本大题共2小题，第1小题4分，第2小题5分，共9分）1. 解：原式)()()())((R P R Q P R P R Q P ∧∨⌝∨⌝∧⌝⇔∧∨∧∨⌝⇔))()((R P R Q P ∧⌝∧∧⌝∧⌝⌝⌝⇔。

2. 解：(1)⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0100100001000121A (2)D 为单连通图。

五、应用题（本大题共2小题，每小题6分，共12分）1. 3．解此问题的最优设计方案即要求该图的最小生成树，由破圈法或避圈法得最小生成树为：其权数为1+1+3+4 = 9 。

2. 解：(1)写出R 的关系矩阵M R(2) 关系R 的自反闭包r(R)的关系图⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=1000000100010001010000010R M3(3) 关系R 的对称闭包r(R)的关系图 (4) 关系R 的传递闭包r(R)的关系图4六、证明题（本大题共3小题，每小题6分，共18分）1.证明：（1）设群>*<,G 的幺元为e ，则G x ∈∀ 有 x e e x *=*，∴H e ∈即H 非空。

（2）H b a ∈∀,，则 G x ∈∀ 有 b x x b a x x a *=**=*,，从而Hb a b a x b x a b x b b a b b x b a x b a ∈*∴**=**=****=****=**--------11111111,)()()()()()(故 >*<,H 是>*<,G 的子群。