计算机数学基础(1)期末复习要点与模拟练习师范部冯泰一、关于期末考核1.本学期的结业考核由形成性考核和期末考核构成．形成性考核由平时作业成绩构成，占结业考核成绩的20%, 期末考核成绩占结业考核成绩的80%．2.期末考核实行全国统一考核，根据本课程考试说明，由中央电大统一命题，统一考核时间，制定统一评分标准．开办试点的地方电大组织考核．期末考核的考核内容和要求以考核说明为准；采用闭卷笔试，试卷满分100分；时限120分钟．试题类型及分数：单项选择题和填空题，分数约占25％．解答与计算题，分数约占56％；证明题，分数约占19％．3, 考核试卷分数分布：第1编数理逻辑约30分，第2编集合论约30分，第3编图论约25分，第4编代数系统约15．4. 易、中、较难题目在试卷中占的比例是4：4：2．二、各章基本问题与重点第1章命题逻辑基本问题：1. 命题符号化，是否命题判断或求真值．2. 命题公式赋值，及类型判别．3. 命题公式等值判别或证明．方法有真值表法、等值演算法和主范式法.4. 求范式和主范式．5. 蕴含式(推理理论)证明：方法有：真值表法、等值演算法、主析取范式法、构造证明法――直接法、附加前提证明法和反证法．重点：真值表，命题公式的赋值于命题公式类型以及公式之间等值的判别，求主范式和构造推理证明．第2章谓词逻辑基本问题：1. 命题符号化．2. 求辖域、约束变元、自由变元．3. 给定解释求谓词公式的真值(多为个体域有限的情形)．4. 判断谓词公式是否重言式(用代换实例)、永假式或可满足式？5. 求前束范式．6. 谓词公式等值式的证明．重点：求辖域、变元，在有限个体域内求谓词公式的真值，求前束范式．第3章集合及其运算基本问题：1. 求集合表达式(列举法或描述法)．2. 判断集合与元素、集合与集合的关系，用∈，∉，⊂，⊆，⊄？3. 求幂集．4. 包含或相等的化简或证明．5. 求笛卡儿积，或某些等式证明．重点：求幂集合，集合(包括笛卡儿积)的化简或等式证明．第4章二元关系与函数基本问题：1. 求关系的表达式，关系矩阵、关系图，Dom(R),Ran(R).2. 验证或证明关系的性质．3. 求复合关系、逆关系及其矩阵．4. 求关系闭包．5. 关系计算：求⋃，⋂，－，～，⊕6. 验证或证明关系R是等价关系或偏序关系．7. 求等价关系的等价类．8. 作偏序关系的哈斯图，求极大(小)元、最大(小)元．9. 验证是否是函数，是满射、单射、双射？求函数定义域、值域．10. 求复合函数、反函数．判别是否存在反函数？重点：求关系的表达式(矩阵或关系图)，判别关系的性质，求复合关系和逆关系，证明是否等价关系或偏序关系，作哈斯图求极(最)大极(最)小元．第5章图的基本概念基本问题：1. 图G与G＝<V，E>互求．2. 判断简单图、多重图、完全图．3. 求补图．子图或生成子图．4. 求结点度数或用握手定理求结点数，或判断是否度数序列．5. 判断是否同构，主要用必要条件判断不同构．6. 用握手定理或推理进行证明．7. 求图中通路、回路、长度或通路、回路的数目(主要用定理8)8.判断是否连通、强连通、单侧连通或弱连通．9. 求点割集、割点和边割集、割边．10. 求图的关联矩阵、邻接矩阵和可达矩阵．重点：作图，用握手定理求结点或推理证明，求通路、回路及其长度，判别强(单侧、弱)连通，求有向图的邻接矩阵并求结点之间的通路或回路条数．第6章几种特殊的图基本问题：1.判断或作欧拉图，求欧拉通路、回路．2. 判断或作哈密顿图，求哈密顿通路、回路，说明不是哈密顿图．3. 判断是否可平面图，将可平面图改画为平面图．4. 求连通平面图的面、边界和次数．5. 用第6，7，8作某些证明．6. 判断是否树．7. 求树枝的内点和求树叶数．8. 求最小生成树和权．9. 画根树，求层数和树高．10. 求简单的二元完全树的内点和树叶．重点：欧拉(哈密顿)通路、回路的判别，平面图的判别，平面图的面、边的关系，定理6,7，求树的结点或边，最小生成树．第7章群基本问题：1. 验证代数运算f在A上封闭，即<A,f>是代数系统．2. 验证代数运算有结合律，交换律等．3. 验证代数运算f，g有无分配律，吸收律等．4. 求运算的单位元，逆元.．5. 判断是否半群、群、交换群、循环群，求生成元和循环群的子群．.7. 在群中进行计算、化简等．8. 求复合置换、逆置换等．9. 证明群同态、同构，找同态(同构)映射．重点：验证是否二元运算以及结合律、交换律、求单位元和逆元，半群、群，交换群和循环群，置换．第8章其它代数系统基本问题：1. 验证是否为环？2. 给出偏序集，判断是否为格？3. 在格中进行计算、化简或证明等．4. 判断是否为布尔代数(简单的，告知验证H1,H2,H3,H4)．5. 布尔代数式的化简、求值或证明.重点：环的定义，偏序格的判别，布尔式的化简或证明．三、模拟练习题模拟练习题(1)(一) 单项选择题1. 给定无向图如图1所示，下面给出的顶点集的子集中，不是点割集的为（）(A) {b,d} (B) {d}(C) {a,c} (D) {e,g}f b图12. 无向完全图K 3的不同构的生成子图有（ ）个． (A) 6 (B) 5 (C) 4 (D) 33. 在自然数集合N 上，下列运算可结合的是（ ） (A) ),max(y x y x =* (B)y x y x +=*2 (C)22y x y x +=* (D) y x y x -=*4. 设N 为自然数集合，<N ， >在下面4种运算下不构成代数系统的是（ ） (A) x y = x +y －2xy (B) x y = x +y(C) x y = x ∙y (D) x y = |x |+|y |(其中，+、—分别为普通加法和减法)5. 2所示，是格的为( )图2(二) 填空题6. 若命题变元P ，Q ，R 赋值为(1,0,1)，则命题公式G ＝)())((Q P R Q P ∨⌝∨→∧的真值是 ．7. 设N (x )：x 是自然数，Z (y )；y 是整数，则命题“自然数都是整数，而有的整数不是自然数”符号化为 ．8. 设A ,，B 为任意集合，命题A -B =∅⇔A=B 的真值为 ．9. 设A ，B 为有限集，且|A|=m ,|B|=n ,那末A 与B 间存在双射，当且仅当 ． 10. 在有向图的邻接矩阵中，第i 行元素之和,第j 列元素之和分别为 ．(三) 化简解答题11. 做命题公式))(()(P Q P Q P ∨∧→→的真值表，并判断该公式的类型． 12.化简集合表达式：((A ⋃B ⋃C )⋂(A ⋃C ))－((C ⋃(C －B )－A ) 13. （1）将命题公式)(P R Q P →⌝∧∨⌝化为只含⌝和∧的尽可能简单的等值式． (2) 求谓词公式))(())((a f R x Q P x ∨→∀的真值．其中P ：4>3，Q （x ）：x >1，R （x ）：x ≤2，f (0)=0，f (4)=4．a ：4． 个体域D ={0，4}． (四) 计算解答题14. (1) 设R 和S 是集合A ＝{1,2,3}上的二元关系，R ＝{<1,2>,<3,1>} S ={<1,2>,<2,1>,<3,3>}求R ∙S ，写出它的矩阵M R ∙S ．(2) 求布尔表达式c b c b a c b a E ++∙+=)(),,(的对偶式，并求当a ,b ,c 取值0,0,1时，E (a ,b ,c )以及其对偶式的真值．15. 指出谓词公式)(),())(),()((x S y x xH x P z x G x F x ∧∃∧∨→∀中∀x 和∃x 的辖域，并指出该公式的约束变元和自由变元以及约束出现次数和自由出现次数． 16. 已知带权图G ，如图3所示．试求图G 的最小生成树，并计算该生成树的权． 17. 设简单连通无向图G 有12条边，G 中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不超过3．求G 中至少有多少个结点．试作一个满足该条件的简单无向图． 图3(五) 证明题18. 证明如果R 和S 是非空集合A 上的等价关系，则S R ⋂也是A 上的等价关系． 19. 设R *是非0实数集，在R *上定义集合S 为},00{*R b a b a S ∈⎥⎦⎤⎢⎣⎡= 证明 (S ，*)是代数系统，满足结合律，交换律，存在单位元，S 的每个元素有逆元．其中*是矩阵的乘法运算．模拟练习题(2)(一) 单项选择题1. 设命题公式G ：)(R Q P ∧→⌝,则使公式G 取真值为1的P ，Q ，R 赋值分别是 ( )0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A (2. 谓词公式)(y yP ∀取真值为1的充分必要条件是( ) (A) 对任意y ，使P (y )都取真值1(B) 存在一个y 0，使P (y 0)取真值1 (C) 存在某些y ，使P (y )都取真值1 (D) 存在y 0，使P (y 0)取真值03. 设G ⇔∀x ∃yP (x ,y )→Q (z ,w )，下面三个命题为真的是( ) (A) G 是前束范式 (B) G 不是前束范式 (C) G 不是一阶公式 (D) G 是永真式4. 设集合A ＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是( ) (A) 1∈A (B) {{4,5}}⊂A (C) {1,2,3}⊆A (D) ∅∈A5. 已知集合A ＝{a ,b ,c }上的二元关系R 的关系矩阵M R ＝⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001011010，那么R ＝( )，(A) {<a ,b >,<b ,a >,<b ,b >,<a ,c >} (B) {<a ,b >,<b ,a >,<b ,b >,<c ,b >} (C) {<a ,b >,<a ,a >,<b ,b >,<c ,a >} (D) {<a ,b >,<b ,a >,<b ,b >,<c ,a >} (二) 填空题6.令P ：天气晴朗，Q ：我去爬山，R ：我有时间，则命题“如果天气好，而且我又有时间，那么我就去爬山”符号化为7. 设R ，S 都是集合A 上的等价关系，则对称闭包s (R ⋂S )= ，自反闭r (R ⋂S )=，传递闭包t (R ⋂S )= .8. 设f ：A →B 是双射函数，则f －1是函数，并且是从B 到A 的 ．9.设有向图D ＝<V ,E >的邻接矩阵为A (D )=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1100100001000120，那么∣E ∣＝ . 10. 无向连通图G 含有欧拉通路的充分必要条件是 (三) 化简解答题11. (1) 求命题公式(P ∨⌝Q )→(P ∧Q )的成真赋值 （2）设集合A ＝{1,2},求P (∅)×P (A ).12. 设f 是一元运算，P 是一元谓词，Q 是二元谓词，给定解释如下 ,1)3(,0)2(,2)3(,3)2(},3,2{=====P P f f D I 1)3,3()3,2(,0)2,3()2,2(====Q Q Q Q 求在解释I 下)()))),(((x xP y x f Q y x ∃→∃∀的真值．13. 判断下列各式哪些是正确的？哪些是错误的？ （1）A B B A =⋃-)( （2）A A B A =-⋃)(（3）A A A =⊕ （4）∅=-⋂A B A )( (5) ∅=∅⋃∅}{ (6) ∅=∅⋂∅}{(7) }{}}{,{}{∅=∅∅⋂∅ (8) }}{,{}{}}{,{∅∅=∅-∅∅ (9) {∅,{∅}}－∅＝{{∅}} (10) }{}}{{}}{,{∅=∅-∅∅ (四) 计算解答题14. 已知集合A 及其A 上偏序关系R ，和偏序集<A ,R >的 哈斯图如图1．试写出二元关系R 的集合表达式，并求A 的子集B ={1,3，4}的极大元、极小元、最大元、最小元以及 最小上界和最大下界．15. 有向图D =<V ,E >如图2所示：7∙ 6∙∙5 4∙ 3∙ ∙21∙图1vv 图2(1)写出D的邻接矩阵A及其2，3次幂；(2)根据（1）中计算结果回答以下问题：①D中V3到V4长度小于等于3的通路有几条？②D中V3到V3长度小于等于3的回路有几条？③D中长度等于3的通路有几条？其中有几条是回路？16. 设S=Q⨯Q，其中Q是有理数集合．在S上定义二元运算*，,<><∀有a>∈b,,,Sxybya,,ax*,x+ay>=<><b><假设代数系统（S，*）的单位元是<1,0>,试求S中每个元素的逆元．17. 已知(L，∧，∨)是格，且二元运算∧和∨满足分配律，∀a,b,c∈L，化简表达式((a∧b)∨ (a∧c))∧ ((a∧b)∨ (b∧c))(五) 证明题18. 构造推理证明：(P→(⌝Q∨R))∧(S→P)∧Q⇒S→R19.证明给定的图G(如图3所示)不是哈密尔顿图．图3四、模拟练习题解答模拟练习题(1)解答(一) 单项选择题1. B2. C3. A4. A5. D(二) 填空题6. 17. ∀x(N(x)→Z(x))∧∃x(Z(x)∧⌝N(x))8. 09. m=n．10. 结点v i的出度和结点v j的入度(三) 化简解答题11. . 命题公式的真值表原式为可满足式.12. ((A⋃B⋃C)⋂(A⋃C))－((C⋃(C－B)⋂～A)＝(A⋃C)－（C⋂～A）(两次用吸收律)=((A⋃C)⋂(～C⋃A)=(A ⋂～C )⋃(C ⋂～C)⋃A ⋃(A ⋂C ) =(A ⋂～C )⋃∅⋃A =A13. (1))(P R Q P →⌝∧∨⌝)()(P R Q P ∨∧⌝∧⌝⇔ )()(R P Q P ⌝∧⌝⌝∧⌝∧⌝⇔不惟一.(2) ))(())((a f R x Q P x ∨→∀=))4(()))4(())0(((f R Q P Q P ∨→∧→ =00)11()01(⇔∨→∧→(四) 计算解答题14. (1) R ∙S = {<1,2>,<3,1>}∙{<1,2>,<2,1>,<3,3>}=}2,3,1,1{><><⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=∙010000001SR M(2) 110)11(10)100()1,0,0(=++∙=++∙+=Ec b c b a c b a E ++∙+=)(),,(的对偶式为c b c b a ∙∙+∙)(，其真值是010110)100(=∙∙=∙∙+∙15. ∀x 的辖域为：F (x )→G (x ，z )∨P (x )∃x 的辖域为：H(x ，y ) x 既是约束变元，也是自由变元，约束出现4次，自由出现1次．y 是自由变元，自由出现1次．. z 是自由变元，自由出现1次．)()))),(((x xP y x f Q y x ∃→∃∀))3()2())),3((())),2(((P P y f yQ y f yQ ∨→∃∧∃⇔10))3,2()2,2(())3,3()2,3((∨→∨∧∨⇔Q Q Q Q 11)10()10(⇔→∨∧∨⇔16. 做法如下：①选边1； ②选边2； ③选边3； ④选边5；⑤选边7最小生成树为{1,2,3,5,7}．如解答图4 中粗线所示．权数为18． 解答图4 17. 设图G 有x 个结点，有握手定理2⨯1+2⨯2+3⨯4＋3⨯（x -2-2-3）≥12⨯2271821243≥-+=xx ≥9图G 至少有9个结点． 解答图５ 满足条件的图如解答图5所示． (五) 证明题 18. ① S R x x S x x R x x A x ⋂>∈⇒<>∈<>∈<∈∀,,,,,，所以S R ⋂有自反性；②,,A y x ∈∀因为R ，S 是对称的，S y x R y x S R y x >∈<∧>∈⇔<⋂><,,,S x y R x y S R >∈<∧>∈<⇔,,,对称的S R x y ⋂>∈⇔<,所以，R ⋂S 是对称的． ③ A z y x ∈∀,,，因为R ，S 是传递的， S R z y S R y x ⋂>∈<∧⋂>∈<,,S z y R z y S y x R y x >∈<∧>∈<∧>∈<∧>∈⇔<,,,, S z y S y x R z y R y x >∈<∧>∈<∧>∈<∧>∈⇔<,,,,S R z x S z x R z x S R ⋂>∈⇔<>∈<∧>∈<⇒,,,,传递所以，S R ⋂是传递的． 总之，R ⋂S 是等价关系.19. 首先证*在S 上封闭．任取S 中的元素⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡y x b a 00,00，其中a ,b ,x ,y ∈R *．S by ax y x b a ∈⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡*⎥⎦⎤⎢⎣⎡000000，因为ax ,by ∈R *．即*在S 上封闭．且有 ⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡*⎥⎦⎤⎢⎣⎡by ax y x b a 000000＝⎥⎦⎤⎢⎣⎡*⎥⎦⎤⎢⎣⎡b a y x 0000 即运算*满足交换律．任取S 中的元素⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡d c y x b a 00,00,00，其中a ,b ,x ,y ,c ,d ∈R *，有 ⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡byd axc d c by ax d c y x b a 0000*0000*)00*00(⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡byd axc yd xc b a d c y x b a 0000*00)00*00(*00 可见，*满足结合律．设单位元为E =⎥⎦⎤⎢⎣⎡y o x 0,任取S 中的元素⎥⎦⎤⎢⎣⎡b a 00, 有 ⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡yb xa b a y x b a by ax y x b a 0000*00000000*00 得到⎩⎨⎧==b by a ax ，由a ,b 的任意性，得x=1,y=1,有E =⎥⎦⎤⎢⎣⎡1001∈S,即E 是S 上关于运算*的单位元．任取S 中的元素⎥⎦⎤⎢⎣⎡b a 00如果其逆元为X =⎥⎦⎤⎢⎣⎡y x 00，应有 ⎥⎦⎤⎢⎣⎡b a 00*⎥⎦⎤⎢⎣⎡y x 00=⎥⎦⎤⎢⎣⎡b a 00*⎥⎦⎤⎢⎣⎡y x 00=⎥⎦⎤⎢⎣⎡1001 得到⎩⎨⎧==11by ax ,因为a ,b 不为0，得b y a x 1,1==．显然x ,y 不为0，即x ,y ∈R *，⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡y x 1001∈S ，它是⎥⎦⎤⎢⎣⎡b a 00的逆元．S 的每个元素都有逆元，模拟练习题(2)解答(一) 单项选择题1. D2. A3. B4. B5. D(二) 填空题6. P ∧Q →R7. R ⋂S ， R ⋂S , R ⋂S8. 双射9. 7 10. 至多有两个奇数度的结点(三) 化简解答题11. (1) (P ∨⌝Q )→(P ∧Q )⇔(⌝P ∧Q )∨(P ∧Q )⇔(⌝P ∨P ∧Q ⇔Q ，成真赋值：01，11. (2) P (A )={∅,{1},{2}{1,2}}P (∅)⨯P （A ）={<∅,∅>,,<∅,{1}>,.<∅,{2}>,<∅,{1,2}>} 12. )()))),(((x xP y x f Q y x ∃→∃∀))3()2())),3((())),2(((P P y f yQ y f yQ ∨→∃∧∃⇔10))3,2()2,2(())3,3()2,3((∨→∨∧∨⇔Q Q Q Q 11)10()10(⇔→∨∧∨⇔13. (1) 不对．改正：B A B B A ⋃=⋃-)(； (2) 不对．改正：A B A B A -=-⋃)((3) 不对．改正：∅=⊕A A （4）正确． (5) 不对．改正：}{}{∅=∅⋃∅； (6) 正确．(7) 正确． (8) 不对．改正：}}{{}{}}{,{∅=∅-∅∅； (9) 不对．改正：{∅,{∅}}－∅＝{∅，{∅}}；(10) 正确．(四) 计算题14. A ＝{1,2,3,4,5,6,7}, B ={1，3，4}，R ＝{<1,2>,<1,3><1,4>,<1,5>,<1,6>,<1,7>,<5,7>,<3,6>,<4,6>}⋃I AB 的极大元：3,4；极小元：1．最大元：无；最小元：1．最小上界：6；最大下界：1．15. (1) D 的邻接矩阵及它的幂如下⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=1111111110111001)(,101110111001010)(,1001100101000010)(32D A D A D A (2) ①3条 ② 1条 ③13条；4条． 16. 设,,S b a >∈<∀其逆元记作><y x ,，有*,><b a >>=<+>=<<0,1,,b ay ax y x ， >>=<+>=<<><0,1,,*,y bx ax b a y x得到⎪⎩⎪⎨⎧=+=+=001y bx b ay ax解得aby a x -==,1（0≠a ） 对任意S b a >∈<,，只要0≠a ，那末><b a ,的逆元为>-<aba ,1． 17. ((a ∧b ) ∨ (a ∧c )) ∧((a ∧b ) ∨(b ∧c ))＝(a ∧b ) ∨ ( (a ∧c ) ∧ (b ∧c ))(分配律) =(a ∧b ) ∧ ((a ∧b ) ∧c ) (幂等律) =a ∧b (吸收律)(五) 证明题18. 前提：P →(⌝Q ∨R )，S →P ，Q结论：S →R 证明①S 附加前提 ② S →P 前提引入 ③ P ①，②假言推理 ④P →(⌝Q ∨R ) 前提引入⑤ ⌝Q ∨R ④，⑤假言推理 ⑥ Q 前提引入⑦ ⌝⌝Q ⑥E 1双重否定⑧R ⑦，⑤析取三段论19. 在图G 中取两点a ,c 如解答图1所示.选V 1＝{a ,c }⊂V (G ), 有P (G －V 1)＝3>⎪V 1⎪＝2, 由第6章定理的逆否结论，可知该图不是哈密顿图． 解答图1 注意：证明方法和子集V 1的取法都不惟一.附：《计算机数学基础(1)》离散数学试题(2003年1月用试卷)一、单项选择题(每小题2分，共10分) 1.下列命题公式等值的是( )BB A A QP Q Q P Q B A A B A A Q P Q P ),()D (),()C ()(),()B (,)A (∧∨⌝∨∨⌝∨→→→⌝→→∨⌝∧⌝2. 谓词公式)(y yP ∀取真值为1的充分必要条件是( )(A) 对任意y ，使P (y )都取真值1 (B) 存在一个y 0，使P (y 0)取真值1 (C) 存在某些y ，使P (y )都取真值1 (D) 存在y 0，使P (y 0)取真值03. 设集合A ＝{0,b },B ={1,b ,3},则A ⋃B 上的恒等关系是 ( ).(A) {<0,0>,<1,1>,<3,3>} (B){<0,0>,<1,1>,<b ,b >,<3,3>} (C) {<1,1>,<b ,b >,<3,3>} (D) {<0,1>,<1,b ><b ,3>,<3,0>}4. 已知集合A ＝{a ,b ,c }上的二元关系R 的关系矩阵M R ＝⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001011010，那么R ＝( )， (A) {<a ,b >,<b ,a >,<b ,b >,<a ,c >} (B) {<a ,b >,<b ,a >,<b ,b >,<c ,b >}(C) {<a ,b >,<a ,a >,<b ,b >,<c ,a >} (D) {<a ,b >,<b ,a >,<b ,b >,<c ,a >} 5.设V ＝{a ,b ,c ,d },与V 能构成强连通图的边集E ＝( )(A) {<a ,b >,<a ,c >,<d ,a >,<b ,d >,<c ,d >}(B) {<a ,d >,<b ,a >,<b ,c >,<b ,d >,<d ,c >} (C){<a ,c >,<b ,a >,<b ,c >,<d ,a >,<d ,c >} (D) {<a ,d >,<b ,a >,<b ,d >,<c ,d >,<d ,c >} 二、填空题(每小题3分，共15分)6. 设命题公式G ：P →⌝(Q →P )，则使公式G 为假的真值指派是 ．7. 设P ：我们划船，G ：我们跑步，那么命题“我们不能既划船，又跑步”可符号化为8. 设个体域D ＝{1,2},那么谓词公式)()(y yB x xA ∀∨∃消去量词后的等值式为 ．9.设有向图D ＝<V ,E >的邻接矩阵为A (D )=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1100100001000120，那么∣E ∣＝ . 10. 无向连通图G 含有欧拉回路的充分必要条件是 ．三、化简解答题(每小题8分，共32分)11. 回答问题：下列集合中哪些是相等的, 说明理由. A 1＝{a ,b } A 2＝{b ,a } A 3＝{a ,a ,b } A 4＝{a ,b ,c }A 5＝{0))()((=---c x b x a x x } A 6＝{0)(2=++-ab b a x x }(2) 设无向图G ＝<V ,E >, 那么图G 中∣V ∣与∣E ∣满足什么条件，图G 一定是树. 13.判别谓词公式),(),(y x xF y y x yF x ∃∀→∀∃的类型.四．计算题(每小题8分，共24分)14.求命题公式))()((Q P P Q P ∧⌝∧→→的主合取范式.15. 设全集E ＝(a ,b ,c ,d ,e ,f ), A ={a ,d }，B ={a ,b ,e }，C ={b ,d }，求下列集合： (1) C B A ~)(⋃⋂； (2))()(A P A A ⋃⊕.第12题图 12. (1)设图G (如第12题图)， 作图G 的嵌入图，说明图G 是 平面图.16. 已知图D (如第16题图)的邻接矩阵为A (D )=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡010110100101111043214321v v v v v v v v 求从v 2到v 4长度为2和从v 3到v 3长度为2的通路条数，并将它们具体写出.17. 设代数系统(Z ,*)，其中Z 是整数集，二元运算定义为2*,,-+=∈∀b a b a Z b a ， ∀Z a ∈，求a 的逆元.五、证明题(第18题10分，第19题9分)18. 设R 是集合A 上的对称关系和传递关系，试证明：若对∀a ∈A ,∃b ∈A ，使得(a ,b )∈R ,则R 是等价关系. 19. 设格(L ，∧，∨)满足分配律，证明,,,L c b a ∈∀有b ac b b a c a b a ∧=∧∨∧∧∧∨∧))()(())()((《计算机数学基础(1)》离散数学试题解答一、单项选择题(每小题2分，共15分) 1.C 2. A 3.B 4.D 5.A 二、填空题(每小题3分，共15分)6. 1,0；1,17. )(Q P ∧⌝或Q P ⌝∨⌝ 8. A (1)∨A (2)∨(B (1)∧B (2)) 9. 710. 不含有奇数度结点.三、化简解答题(每小题8分，共32分)11.集合中的元素是无序的，且不能重复，故A 1＝A 2＝A 3；因为(x －a )(x －b )(x －c )=0的解为x =a ,b ,c ,而x 2－(a +b )x +ab =0的解为x =a ,b. 故有A 1＝A 2＝A 3＝A 6，A 4＝A 5 12. (1)图G 的嵌入图，如第12题答案图. 故图G 为平面图(2) 图G 连通且∣E ∣＝∣V ∣－1， 那么图G 一定是树.13. 设I 为任意一个解释，D 为I 的个体域. 若在解释I 下，该公式的前件为0，无论 ),(y x xF y ∃∀如何取值，第16题图第12题答案图),(),(y x xF y y x yF x ∃∀→∀∃为1；若在解释I 下，该公式的前件为1，则,0D x ∈∃使得),(y x yF ∀为1，它蕴含着),(,0y x F D y '∈'∀为1),(y x xF '∃⇒为1，由y '的任意性，必有),(y x xF y ∃∀为1，于是),(),(y x xF y y x yF x ∃∀→∀∃为1. 总之，对任意解释I ，),(),(y x xF y y x yF x ∃∀→∀∃为1. 该公式为永真式.四、计算题(每小题8分，共24分)14. ))()((Q P P Q P ∧⌝∧→→)()()()00()())())()((Q P Q P Q Q P P Q P P Q P Q P Q P P Q P ⌝∨⌝∧∨⌝⇔⌝∧∨⌝⇔∧∨⌝⇔∧⌝∧∨∧⌝∧⌝∨⌝⇔∧⌝∧∨⌝∨⌝⇔15. (1) },,,{},,,{}{~)(f e c a f e c a a C B A =⋃=⋃⋂； (2)∅=⋂-⋃=⊕)()()(A A A A A A . }},{},{},{,{)(d a d a A P ∅=.故)()(A P A A ⋃⊕＝}},{},{},{,{d a d a ∅16. A 2(D )=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡2120020********* 从矩阵A 2(D )中a 24=2,a 33=2可知，从v 2到v 4长度为2的通路有2条. 它们是： v 2v 3v 4,和v 2v 1v 4, 从v 3到v 3长度为2的通路有2条. 它们是： v 3v 4v 3,和v 3v 2v 3, 17. 易知，二元运算满足交换律. ∵对∀a ∈Z , a *2=a +2－2＝a ＝2*a ，即2∈Z 是单位元.∀a ∈Z , a 的逆元记作a －1, 有22*11=-+=--a a a a (单位元)∴ a －1=4－a五、证明题(第18题10分，第19题9分)18. 已知R 是对称关系和传递关系，只需证明R 是自反关系. ∀a ∈A ,∃b ∈A ，使得(a ,b )∈R ，因为R 是对称的，故(b ,a )∈R ; 又R 是传递的，(a ,b )∈R ，(b ,a )∈R ⇒(a ,a )∈R ,由元素a 的任意性，知R 是自反的. 所以，R 是等价关系. 19. ))()(())()((c b b a c a b a ∧∨∧∧∧∨∧＝))()(()(c b c a b a ∧∧∧∨∧ (分配律) ＝))(()(c b a b a ∧∧∨∧ (幂等律)＝b a ∧ (吸收律)。
