下载文档原格式
..一、填空2．A ，B ，C 表示三个会合，文图中暗影部分的会合表达式为 (B⊕C)-AA C4．公式(PR)(SR)P的主合取范式为(PSR) ( PS R)。
5．若解说I 的论域D 仅包括一个元素，则 xP(x) xP(x) 在I 下真值为 1 。
6．设A={1，2，3，4}，A 上关系图以下，则 R^2={(1,1),(1,3),(2,2),(2,4)}。
//备注： 0 1 0 01 0 1 0 0 1 0 1R 1 0 1 0 R 20 0 0 1 0 0 0 00 0 0 00 0 0 07．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图以下，则R={(a,b),(a,c),(a,d),(b,d),(c,d)}U{(a,a),(b,b)(c,c)(d,d)}。
备注：偏序知足自反性，反对称性，传达性8．图 的补图为 。
//补图:给定一个图G,又G 中全部结点和全部能使 G 成为完整图的增添边构成的图,成为补图. 自补图:一个图假如同构于它的补图,则是自补图 9．设A={a ，b ，c ，d}，A 上二元运算以下：* a b c da abcd b b c d a ccdabd d a b c那么代数系统<A ，*>的幺元是 a ，有逆元的元素为a,b,c,d，它们的逆元分别为a,b,c,d 。
//备注：二元运算为 x*y=max{x,y}，x,y A 。
10．以下图所示的偏序集中，是格的为 c。
//（注：什么是格？即随意两个元素有最小上界 和最大 下界的偏序）二、选择题 1、以下是真命题的有（ C 、D ）A ．{a} {{a}}；B ．{{}} { ,{}}；C ．{{}, }； D ．{} {{ }}。
2、以下会合中相等的有（ B 、C ）A ．{4，3} ；B ．{ ，3，4}；C ．{4， ，3，3}；D ．{3，4}。
;....3、设A={1，2，3}，则A 上的二元关系有（ C ）个。
离散数学期末试题及答案HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】326《离散数学》期末考试题(B )一、填空题(每小题3分，共15分)1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ).2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数.3.谓词公式))()(())()((y P y Q y x Q x P x ⌝∧∃∧→∀中量词x ∀的辖域为( ), 量词y ∃的辖域为( ).4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元.5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=⨯||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个.2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射.3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧⌝)(； (5)q q p →→)(.4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).三．1.设}}{},,{{c b a A =，}}{},,{},{{c c b a B =，则)(=⋃B A ，)(=⋂B A ，)()(=A P .2.集合},,{c b a A =，其上可定义( )个封闭的1元运算，( )个封闭的2元运算，( )个封闭的3元运算.3.命题公式1)(↑∧q p 的对偶式为( ).4.所有6的因数组成的集合为( ).5.不同构的5阶根树有( )棵.四、(10分)设B A f →:且C B g →:，若g f 是单射，证明f 是单射，并举例说明g 不一定是单射.五、(15分)设},,,{d c b a A =,A 上的关系)},(),,(),,(),,(),,(),,(),,(),,(),,{(c d b d a d c c b c a c c a b a a a R =,1.画出R 的关系图R G .2.判断R 所具有的性质.3.求出R 的关系矩阵R M .六、(10分)利用真值表求命题公式))(())((p q r r q p A →→↔→→=的主析取范式和主合取范式.七、(10分) 边数30<m 的简单平面图G ，必存在节点v 使得4)deg(≤v . 八、(10分) 有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.《离散数学》期末考试题(B)参考答案一、1. {{a , b }, a , b , ?}， {{a , b }, a , b }，16.2.92, 27.3.)()(x Q x P →, )()(y P y Q ⌝∧.4. 2, 4, 6, 12.5.4≤，奇数.二、1.22,2,m mn mn ., g , g . ,2,4.，不存在，不存在. 5.连通，3，10.三、1. }}{},,{},,{},{{c c b b a a B A =⋃，}}{{c B A =⋂，{)(=A P ?, {{a , b }}, {{c }}, {{a , b }, {c }}}.2.27933,3,3. 3.0)(↓∨q p .4.{-1，-2，-3，-6，1，2，3，6}. .四、证 对于任意A y x ∈,，若)()(y f x f =，则))(())((y f g x f g =，即))(())((y g f x g f =. 由于g f 是单射，因此y x =，于是f 是单射.例如取},,{},3,2,1(},,{γβα===C B b a A ，令)}2,(),1,{(b a f =，)},3(),,2(),,1{(ββα=g ，这时)},(),,{(βαb a g f = 是单射，而g 不是单射.五、解 1. R 的关系图R G 如下：2.(1)由于R b b ∉),(，所以R 不是自反的. (2)由于R a a ∈),(，所以R 不是反自反的.(3)因为R b d ∈),(，而R d b ∉),(，因此R 不是对称的. (4)因R a c c a ∈),(),,(，于是R 不是反对称的.(5)经计算知R c d a d c c b c a c c a b a a a R R ⊆=)},(),,(),,(),,(),,(),,(),,(),,{( ，进而R 是传递的.综上所述，所给R 是传递的.3.R 的关系矩阵⎪⎪⎪⎪⎪⎭⎫⎝⎛=0111011100000111R M .六、解 命题公式))(())((p q r r q p A →→↔→→=的真值表如下:由表可知，))(())((p q r r q p A →→↔→→=的主析取范式为A 的主合取范式为)()(r q p r q p A ⌝∨⌝∨∧∨⌝∨⌝=.七、证 不妨设G 的阶数3≥n ，否则结论是显然的. 根据推论1知，63-≤n m . 若G 的任意节点v 的度数均有5)deg(≥v ，由握手定理知n v m v5)deg(2≥=∑.于是m n 52≤，进而652363-⋅≤-≤m n m . 因此30≥m ，与已知矛盾. 所以必存在节点v 使得4)deg(≤v .八、解 设满足要求的r 位数的个数有a r 种，r = 0，1，2，…，则排列计数生成函数65432121211219619431x x x x x x ++++++=,因而38!412194=⋅=a .。
《离散数学》复习题一、填空题1、若P ，Q 为二命题，Q P ↔真值为1，当且仅当 。
2、对公式),()),(),((y x xR z x zQ y x yP ∀∨∃∧∀中自由变元进行代入的公式为 。
3、))(()(x xG x xF ∃⌝∧∀的前束范式为 。
4、设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的，则 被称为全称量词消去规则，记为US 。
5、与非门的逻辑网络为 。
6、}0|{>∧∈=+x Z x x Z ，*表示求两数的最小公倍数的运算（Z 表示整数集合），对于*运算的幺元是 ，零元是 。
7、代数系统<A,*>中，|A|>1，如果θ和e 分别为<A,*>的幺元和零元， 则θ和e 的关系为 。
8、设<G,*>是一个群，<G,*>是阿贝尔群的充要条件是 。
9、图的完全关联矩阵为 。
10、一个图是平面图的充要条件是 。
二、选择题1、下列各符号串，不是合式公式的有（ ）。
A 、R Q P ⌝∧∧)(；B 、)()((S R Q P ∧→→；C 、R Q P ∧∨∨；D 、S R Q P ∨∧∨⌝))((。
2、下列语句是命题的有（ ）。
A 、2是素数；B 、x+5 > 6；C 、地球外的星球上也有人；D 、这朵花多好看呀！。
3、下列公式是重言式的有（ ）。
A 、)(Q P ↔⌝；B 、Q Q P →∧)(；C 、P P Q ∧→⌝)(；D 、P Q P ↔→)(4、下列问题成立的有（ ）。
若C B C A ∨⇔∨，则B A ⇔； B 、若C B C A ∧⇔∧，则B A ⇔； C 、若B A ⌝⇔⌝，则B A ⇔； D 、若B A ⇔，则B A ⌝⇔⌝。
5、命题逻辑演绎的CP 规则为（ ）。
A 、在推演过程中可随便使用前提；B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；D 、设)(A Φ是含公式A 的命题公式，A B ⇔，则可用B 替换)(A Φ中的A 。
![最新离散数学期末考试试题与答案[1]课件ppt](https://uimg.taocdn.com/9ceca2c04431b90d6d85c7c2.webp)
离散数学期末考试题及答案1.选择题（每题3分，共30分）1. 下列命题中，属于复合命题的是：A. 3是一个奇数，且2是一个偶数B. 如果2是一个素数，那么4也是一个素数C. 不是所有奇数都是素数D. 存在一个整数x，使得x>5且x是一个偶数答案：D2. 已知命题p：草地是绿的，命题q：天空是蓝的。
下列表述可以表示p ∧ ¬q 的是：A. 草地是绿的，天空是蓝的B. 草地不是绿的，天空是蓝的C. 草地是绿的，天空不是蓝的D. 草地不是绿的，天空不是蓝的答案：B3. 设命题p表示“这个数是偶数”，q表示“这个数大于10”。
那么“这个数既是偶数又大于10”可以表示为：A. p ∧ qB. p ∨ qC. ¬p ∧ qD. ¬p ∨ q答案：A4. 下列以下列集合的方式描述，其中哪个是空集∅：A. {x | 0 ≤ x ≤ 1}B. {x | x是一个自然数，x > 10}C. {x | x是一个正偶数，x < 2}D. {x | x是一个负整数，x < -1}答案：C5. 设A = {a, b, c}，B = {c, d, e}，C = {a, c, e}。
则(A ∪ B) ∩ C等于：A. {a, b, c, d, e}B. {a, c, e}C. {c}D. 空集∅答案：B6. 假设U是全集，A、B、C是U的子集。
则(A ∪ B) ∩ C 的补集是：A. A ∩ B ∩ C的补集B. (A ∪ B) ∩ C的补集C. A ∪ (B ∩ C)的补集D. (A ∩ C) ∩ (B ∩ C)的补集答案：D7. 若关系R为集合A到集合B的一种映射，且|A| = 7，|B| = 4，则R包含的有序对数目为：A. 4B. 7C. 11D. 28答案：D8. 设A={1,2,3}，B={4,5,6}，则从A到B的映射总数为：A. 3B. 9C. 6D. 18答案：C9. 设A={a,b,c,d,e}，则集合A的幂集的元素个数是：A. 2B. 5C. 10D. 32答案：D10. 若f：A→B为满射且g：B→C为单射，则(g ∘ f)：A→C为：A. 双射B. 满射C. 单射D. 非单射且非满射答案：A2.简答题（每题10分，共20分）1. 请简要解释什么是关系R的自反性、对称性和传递性。
一．填空题（每小题2分，共10分）1. 谓词公式)()(x xQ x xP ∃→∀的前束范式是___________。
2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =____，=A _____，=B A __ _____3. 设{}{}b a B c b a A ,,,,==，则=-)()(B A ρρ__ __________，=-)()(A B ρρ_____ ______。
二．选择题（每小题2分，共10分）1. 与命题公式)(R Q P →→等价的公式是（ ）（A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=,A 上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 三．计算题（共43分）1. 求命题公式r q p ∨∧的主合取范式与主析取范式。
（6分）2. 设集合{}d c b a A ,,,=上的二元关系R 的关系矩阵为⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000000011010001R M ,求)(),(),(R t R s R r 的关系矩阵，并画出R ，)(),(),(R t R s R r 的关系图。
（10分）5. 试判断),(≤z 是否为格？说明理由。
（5分）（注：什么是格？Z 是整数，格：任两个元素，有最小上界和最大下界的偏序）四．证明题（共37分）1. 用推理规则证明D D A C C B B A ⌝⇒∧⌝⌝⌝∧∨⌝→)(,)(,。
（10分）2. 设R 是实数集，b a b a f R R R f +=→⨯),(,:，ab b a g R R R g =→⨯),(,:。
求证：gf 和都是满射，但不是单射。
（10分）一，1, _∃x∃y¬P(x)∨Q(y)2, {2} {4,5} {1,3,4,5}3, {{c},{a,c},{b,c},{a,b,c}} Φ_二，B D三，解：主合取方式：p∧q∨r⇔(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r⇔(p∧q∧r) ∨(p∧q∧¬r)∨(¬p∧q∧r) ∨(¬p∧¬q∧r) ∨(p∧¬q ∧r)=∑1.3.5.6.7四，1，证明：编号公式依据（1）（¬B∨C）∧¬C前提（2）¬B∨C，¬C（1）（3）¬B（2）（4）A→B （3）（5）¬A（3）（4）（6）¬（¬A∧D）前提（7）A∨¬D（6）（8）¬D（5）（6）2，证明：要证f是满射，即∀y∈R,都存在（x1，x2）∈R×R，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即证得；再证g是满射，即∀y∈R，,都存在（x1，x2）∈R×R，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即证得；最后证f不是单射，f（x1，x2）=f（x2，x1）取x1≠x2，即证得，同理：g（x1，x2）=g（x2，x1），取x1≠x2，即证得。
大学离散数学期末考试题库和答案一、单项选择题（每题2分，共20分）1. 在集合论中，以下哪个符号表示“属于”？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 如果A和B是两个集合，那么A∪B表示什么？A. A和B的交集B. A和B的并集C. A和B的差集D. A和B的补集答案：B3. 以下哪个命题是真命题？A. ∀x∈N, x^2 > xB. ∃x∈N, x^2 = x + 1C. ∀x∈N, x^2 ≥ xD. ∃x∈N, x^2 < x答案：C4. 在图论中，一个无向图的边数为E，顶点数为V，那么这个图的生成树的边数是多少？A. EB. V-1C. VD. E-1答案：B5. 以下哪个算法是用于解决旅行商问题（TSP）的？A. 动态规划B. 贪心算法C. 分支限界法D. 回溯法答案：D6. 在逻辑中，以下哪个符号表示“蕴含”？A. ∧B. ∨C. →D. ↔答案：C7. 以下哪个是二进制数？A. 1010B. 2A3C. 12BD. ZYX答案：A8. 在关系数据库中，以下哪个操作用于删除表中的行？A. SELECTB. INSERTC. UPDATED. DELETE答案：D9. 以下哪个是布尔代数的基本运算？A. 并集B. 交集C. 差集D. 所有以上答案：D10. 在离散数学中，以下哪个概念用于描述两个集合之间的关系？A. 函数B. 映射C. 序列D. 所有以上答案：D二、多项选择题（每题3分，共15分）11. 以下哪些是集合的基本运算？A. 并集B. 交集C. 差集D. 补集答案：ABCD12. 在图论中，以下哪些是图的基本类型？A. 无向图B. 有向图C. 完全图D. 二分图答案：ABCD13. 在逻辑中，以下哪些是命题逻辑的基本连接词？A. 与（∧）B. 或（∨）C. 非（¬）D. 蕴含（→）答案：ABCD14. 在关系数据库中，以下哪些是SQL的基本操作？A. SELECTB. INSERTC. UPDATED. DELETE答案：ABCD15. 在离散数学中，以下哪些是组合数学的基本概念？A. 排列B. 组合C. 二项式系数D. 图论答案：ABC三、填空题（每题3分，共30分）16. 如果集合A={1, 2, 3}，集合B={2, 3, 4}，那么A∩B=______。
离散数学试题(B卷答案1）一、证明题（10分）1)(⌝P∧(⌝Q∧R))∨(Q∧R)∨(P∧R)⇔R证明: 左端⇔(⌝P∧⌝Q∧R)∨((Q∨P)∧R)⇔((⌝P∧⌝Q)∧R))∨((Q∨P)∧R)⇔(⌝(P∨Q)∧R)∨((Q∨P)∧R)⇔(⌝(P∨Q)∨(Q∨P))∧R⇔(⌝(P∨Q)∨(P∨Q))∧R⇔T∧R(置换)⇔R2) ∃x (A(x)→B(x))⇔∀xA(x)→∃xB(x)证明：∃x(A(x)→B(x))⇔∃x(⌝A(x)∨B(x))⇔∃x⌝A(x)∨∃xB(x)⇔⌝∀xA(x)∨∃xB(x)⇔∀xA(x)→∃xB(x)二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。
证明：(P∨(Q∧R))→(P∧Q∧R)⇔⌝(P∨(Q∧R))∨(P∧Q∧R))⇔（⌝P∧(⌝Q∨⌝R)）∨(P∧Q∧R)⇔(⌝P∧⌝Q)∨(⌝P∧⌝R))∨(P∧Q∧R)⇔(⌝P∧⌝Q∧R)∨(⌝P∧⌝Q∧⌝R)∨(⌝P∧Q∧⌝R))∨(⌝P∧⌝Q∧⌝R))∨(P∧Q∧R)⇔m0∨m1∨m2∨m7⇔M3∨M4∨M5∨M6三、推理证明题（10分）1）C∨D， (C∨D)→⌝E，⌝E→(A∧⌝B)， (A∧⌝B)→(R∨S)⇒R∨S 证明：(1) (C∨D)→⌝E P(2) ⌝E→(A∧⌝B) P(3) (C∨D)→(A∧⌝B) T(1)(2)，I(4) (A∧⌝B)→(R∨S) P(5) (C∨D)→(R∨S) T(3)(4)， I(6) C∨D P(7) R∨S T(5)，I2) ∀x(P(x)→Q(y)∧R(x))，∃xP(x)⇒Q(y)∧∃x(P(x)∧R(x))证明(1)∃xP(x) P(2)P(a) T(1)，ES(3)∀x(P(x)→Q(y)∧R(x)) P(4)P(a)→Q(y)∧R(a) T(3)，US(5)Q(y)∧R(a) T(2)(4)，I(6)Q(y) T(5)，I(7)R(a) T(5)，I(8)P(a)∧R(a) T(2)(7)，I(9)∃x(P(x)∧R(x)) T(8)，EG(10)Q(y)∧∃x(P(x)∧R(x)) T(6)(9)，I四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。
离散数学期末复习例题讲解一、考核说明考核对象：本课程考核说明适用于国家开放大学开放教育本科电气信息类计算机科学与技术专业的学生．考核依据：本考核说明是以本课程的教学大纲（2015年3月修改）和指定的参考教材为依据制定的．本课程指定的参考教材是由胡俊、顾静相编写，国家开放大学出版社出版的《离散数学（本科）》第2版．考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式．其中终结性考核采用半开卷、笔试方式，试卷满分100分．半开卷考试允许考生携带指定的一张专用A4纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4纸上带入考场，作为答卷时参考．考试时间：90分钟．试题类型及结构：单项选择题的分数占15％，填空题的分数占15％，公式翻译题的分数占12％，判断说明题的分数占14％，计算题的分数占36％；证明题的分数占8％．二、例题讲解（一）集合论1．单项选择题（1）若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )．A．{a，{ a }}∈A B．{ a }⊆AC．{2}∈A D．∅∈A答：B（2）若集合A={a，b，{1，2 }}，B={1，2}，则（）．A．B⊂ A，且B∈A B．B⊄ A，且B∉AC．B ⊂ A，但B∉A D．B∈ A，但B⊄A答：D（3）设集合A = {1, a }，则P(A) = ( )．A．{{1}, {a}} B．{∅,{1}, {a}}C．{∅,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }}答：C（4）设集合A = {1，2，3，4，5，6 }上的二元关系R ={<a , b>⎢a , b∈A , 且a +b = 8}，则R具有的性质为（）．A．对称的B．自反的C．对称和传递的D．反自反和传递的答：A（5）设集合A={1 , 2 , 3 , 4}上的二元关系R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，S = {<1 , 1>，<2 , 2>，<2 , 3>，<3 , 2>，<4 , 4>}，则S 是R 的（ ）闭包．A ．自反B ．传递C ．对称D ．以上都不对 答：C（6）设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系的哈斯图如图1所示,若A 的子集B = {3 , 4 , 5}， 则元素3为B 的（ ）．A ．最小上界B ．最大下界C ．下界D ．以上答案都不对 图1 答：A2．填空题（1）设集合A 有n 个元素，那么A 的幂集合P (A )的元素个数为 ． 答：2n（2）设集合A ={0,1,2},B ={0,2,4},R 是A 到B 的二元关系，},,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的集合表示式为 ． 答：{<0,0>, <0,2>, <2,0>, <2,2>}（3）设集合A =｛a ,b ,c ,d ｝，A 上的二元关系R ={<a , b >, <b , a >, <b , c >, <c , d >}，则R 的自反闭包是 ．答：r (R )= {<a , b >, <b , a >, <b , c >, <c , d >}∪I A（4）设A ={1, 2, 3, 4, 5, 6, 7, 8}，R 是A 上的整除关系，B ={2, 4, 6}，则集合B 的最大元、最小元、上界、下界依次为 ． 答：无、2、无、2（5）设集合A ={1, 2},B ={a , b }，那么集合A 到B 的不同函数的个数有 ． 答：4因为：f ：{<1, a >, <2, a >}, {<1, b >, <2, b >}{<1, a >, <2, b >}, {<1, b >, <2, a >}3．如果R 1和R 2是A 上的自反关系，判断结论：“R 1-1、R 1∪R 2、R 1⋂R 2是自反的”是否成立？并说明理由． 答：结论成立．因为R 1和R 2是A 上的自反关系，即I A ⊆R 1，I A ⊆R 2． 由逆关系定义和I A ⊆R 1，得I A ⊆ R 1-1；由I A ⊆R 1，I A ⊆R 2，得I A ⊆ R 1∪R 2，I A ⊆ R 1⋂R 2．所以，R 1-1、R 1∪R 2、R 1⋂R 2是自反的．注： R 1-R 2是自反的吗？4．若偏序集<A ，R >的哈斯图如图2所示，则集合 A 的最大元为a ；最小元不存在．答：错a 是集合A 的极大元，最大元不存在． 图2 5．设集合A ＝{a ,b , { a , b }}，B ={{a }, {b }, b }，求a f5（1）B ⋂A ； （2）A －B ； （3）A ⨯B ． 解：（1）B ⋂A ={a , b , { a , b }}⋂{{a }, {b }, b }={b } （2）A －B = {a , b , { a , b }}－{{a }, {b }, b }={a , { a , b }} （3）A ⨯B ＝{a , b , { a , b }}⨯{{a }, {b }, b }＝{<a , {a }>, <a , {b }>, <a , b >，<b , {a }>, <b , {b }>, <b , b >, <{ a , b }, {a }>, <{ a , b }, {b }>, <{ a , b }, b >}6．设A ={0，1，2，3，4}，R ={<x ，y >|x ∈A ，y ∈A 且x +y <0}，S ={<x ，y >|x ∈A ，y ∈A 且x +y ≤3}，试求R ，S ，R ︒S ，R -1，S -1，r (R )，s (R )，t (R )，r (S )，s(S )，t (S )．解：R =∅，S ={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} R ︒S =∅，R -1=∅，S -1= S ；r (R )= I A ，s (R )= ∅，t (R )= ∅；r (S )=S ∪{<2,2>，<3,3>,<4,4>}，s (S )= S ；t (S )= S ∪{<1,3>，<2,2>,<2,3>,<3,1>，<3,2>,<3,3>} 7．试证明集合等式：A ⋃ (B ⋂C )=(A ⋃B ) ⋂ (A ⋃C )．证：若x ∈A ⋃ (B ⋂C )，则x ∈A 或x ∈B ⋂C ， 即 x ∈A 或x ∈B 且 x ∈A 或x ∈C ． 即x ∈A ⋃B 且 x ∈A ⋃C ， 即 x ∈T =(A ⋃B ) ⋂ (A ⋃C )，所以A ⋃ (B ⋂C )⊆ (A ⋃B ) ⋂ (A ⋃C )．反之，若x ∈(A ⋃B ) ⋂ (A ⋃C )，则x ∈A ⋃B 且 x ∈A ⋃C ， 即x ∈A 或x ∈B 且 x ∈A 或x ∈C ，即x ∈A 或x ∈B ⋂C ， 即x ∈A ⋃ (B ⋂C )，所以(A ⋃B ) ⋂ (A ⋃C )⊆ A ⋃ (B ⋂C )． 因此．A ⋃ (B ⋂C )=(A ⋃B ) ⋂ (A ⋃C )． 8．设R 是集合A 上的对称关系和传递关系，试证明：若对∀a ∈A ，∃b ∈A ，使得<a , b >∈R ，则R 是等价关系．证明：已知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 是等价关系．（二）图论1．单项选择题（1）设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100则G 的边数为( )．A ．5B ．6C ．3D ．4 答：D（2）设图G ＝<V , E >，则下列结论成立的是 ( )．A ．deg(V )=2∣E ∣B ．deg(V )=∣E ∣C ．E v Vv 2)deg(=∑∈ D ．E v Vv =∑∈)deg(答：C（3）设有向图（a ）、（b ）、（c ）与（d ）如图3所示，则下列结论成立的是 ( )．图3A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的答：A（4）给定无向图G 如图4所示，下面给出的结点集子集中，不是点割集的为（ ）． A ．{b , d } B ．{d }C ．{a , c }D ．{g , e } 答：A 图4（5）图G 如图5所示，以下说法正确的是( )． A ．{(a , d )}是割边B ．{(a , d )}是边割集C ．{(d , e )}是边割集D ．{(a, d ) ,(a, c )}是边割集答：C 图5 （6）设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )．A ．e －v ＋2B ．v ＋e －2C ．e －v －2D ．e ＋v ＋2 答：A2．填空题（1）已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ．答：15 （1⨯1+2⨯2+3⨯3+4⨯4）/2（2）设无向图G ＝<V ,E >是汉密尔顿图，则V 的任意非空子集V 1，都有 ≤∣V 1∣． 答：W （G - V 1）（3）设无向图G 为欧拉图，则图G 连通且 ． 答：每个结点的度数为偶数（4）设图G =<V ,E >，其中|V |=n ,|E |=m ．则图G 是树当且仅当G 是连通的，且m = ． 答：n -1（5）连通无向图G 有6个顶点9条边，从G 中删去 条边才有可能得到G 的一棵生成树T ． 答：4οο οο (a )οο οο (b ) οοοο (c )οοοο(d )a gb d fc e οο ο οο οο ο a ο οο ο ο b c f d e（6）给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素 ，则该序列集合构成前缀码．答：1 3．给定图G （如图6所示）: （1）试判断它们是否为欧拉图？并说明理由． （2）若是欧拉图，请写出一条欧拉回路．答：（1）图G 是欧拉图，因为图G 是连通图且每个结点的度数是偶数．（2）欧拉回路为： v 1 e 1 v 2 e 2 v 3 e 3 v 4 e 5v 5 e 7 v 2 e 8v 6 e 6 v 4 e 4v 1 注意：回路是不惟一4．试判断“设G 是一个有5个结点、10条边的连通图，则G 为平面图”是否正确，为什么？答：错误．因为它不满足定理4.3.3，即“设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v -6．”5．设图G =<V ，E >，其中V ={a 1, a 2, a 3, a 4, a 5},E ={(a 1, a 2)，(a 2, a 4)，(a 3, a 1)，(a 4, a 5)，(a 5, a 2)}（1）试给出G 的图形表示； （2）求G 的邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形． 解：（1）图G 是无向图，图形如图7所示：图7 （2）图G 的邻接矩阵如下：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=0101010010000011100100110)(G A（3）结点a 1, a 2, a 3, a 4, a 5的度数分别为：2，3，1，2，2． （4）图G 的补图的如图8所示：图86．图G =<V , E >，其中V ={a , b , c , d , e , f }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (d , e ),ο οο ο οa 1a 2 a 3a 4a 5v 1 v 2 v 3v 4 v 5v 6 e 1 e 2e 3 e 4 e 5 e 6e 7 e 8 οο ο ο ο ο图6 ο ο ο ο οa 1a 2 a 3a 4 a 5οο ο ο οa 1 a 2 a 3a 4a 5(d , f ), (e , f ) }，对应边的权值依次为5，2，1，2，6，1，9，3及8．（1）画出G 的图形； （2）写出G 的邻接矩阵；（3）求出G 权最小的生成树及其权值． 解：（1）G 的图形如图9所示：（2）邻接矩阵：⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡011000101111110010010001011001010110 图9（3）粗线表示最小的生成树（见图10）：最小的生成树的权为：1+1+5+2+3=12． 图107．设有一组权为2,3,6,9,13,15,试 （1）画出相应的最优二叉树； （2）计算它们的权值．解：最优二叉树如图11所示：图11 权值： 2⨯4+3⨯4+6⨯3+9⨯2+13⨯2+15⨯2 =8+12+18+18+26+30 =1128．设G 是一个n 阶无向简单图，n 是大于等于2的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于2的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．οο ο ο οc a b e dοf1 5 22 61 9 38 ο ο ο ο οc a b ed οf 15 22 61 938 οοο οο ο ο ο ο32 9 135 6 1115 20 ο ο 48289．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k条边才能使其成为欧拉图．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数． 又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图．故最少要加2k条边到图G 才能使其成为欧拉图．（三）数理逻辑1．单项选择题（1） 下列命题公式是等价公式的为( )．A ．⌝P ∧⌝Q ⇔P ∨QB ．A →(⌝B →A ) ⇔⌝A →(A →B )C ．Q →(P ∨Q ⇔⌝Q ∧(P ∨Q )D ．⌝A ∨(A ∧B ) ⇔B 答：B 因为A →(⌝B →A ) ⇔ A →(B ∨A ) ⇔⌝A ∨(B ∨A ) ⇔ A ∨ (⌝A ∨B ) ⇔ A ∨ (A →B )⇔⌝A →(A →B )（2）下列公式 ( )为重言式．A ．⌝(⌝P ∨(P ∧Q )) ↔QB ．(B →(A ∨B )) ↔(⌝A ∧(A ∨B ))C ．A ∧⌝B ↔A ∨BD ．(P →(⌝Q →P ))↔(⌝P →(P →Q )) 答：D 因为(P →(⌝Q →P ))⇔⌝P ∨(Q ∨P )) ⇔1 (⌝P →(P →Q )) ⇔P ∨(⌝P ∨Q )) ⇔1 （3）命题公式⌝ (P →Q )的主析取范式是( )． A ．Q P ⌝∧ B Q P ∧⌝ C ．Q P ∨⌝ D ．Q P ⌝∨答：A 因为⌝ (P →Q ) ⇔⌝ (⌝P ∨Q ) ⇔P ∧⌝Q（4）设C (x ): x 是国家级运动员，G (x ): x 是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( )A ．))()((x G x C x ⌝∧⌝∀B ．))()((x G xC x ⌝→⌝∀C ．))()((x G x C x ⌝→⌝∃D ．))()((x G x C x ⌝∧⌝∃答：D（5）表达式))(),(())(),((z zQ y x R y z Q y x P x ∀→∃∧∨∀中x ∀的辖域是( )． A ．P (x , y ) B ．P (x , y )∨Q (z ) C ．R (x , y ) D ．P (x , y )∧R (x , y ) 答：B2．填空题（1）命题公式()P Q P →∨的真值是 ． 答：1 因为()P Q P →∨⇔⌝P ∨(Q ∨ P ) ⇔1（2）含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 ． 答：(P ∧Q ∧⌝R )∨( P ∧Q ∧R )因为P ∧Q ⇔ P ∧Q ∧(⌝R ∨R ) ⇔(P ∧Q ∧⌝R )∨( P ∧Q ∧R )（3）设个体域D ＝{1,2},那么谓词公式)()(y yB x xA ∀∨∃消去量词后的等值式为 ． 答：(A (1) ∨A (2))∨(B (1) ∧B (2))（5）谓词命题公式(∀x )(P (x )→Q (x )∨R (x ，y ))中的约束变元为 ． 答：x3．请将语句翻译成命题公式： （1）今天不是天晴．（2）你去听课，他也去听课．（3）如果天下雪，则我明天就不去市里． （4）尽管他参加了考试，但他没有通过考试．解：（1）设P ：今天是天晴； 命题公式为： ⌝ P ．（2）设P ：你去听课，Q ：他去听课：命题公式为：P ∧Q ．（3）设P ：天下雪，Q ：我明天去市里； 命题公式为：P →⌝Q ．（4）设P ：他参加了考试，Q ：他没有通过考试； 命题公式为：P ∧⌝ Q ．4．请将语句翻译成谓词公式： （1）所有人都不去上课． （2）有人不去工作． 解：（1）设P (x )：x 是人，Q (x )：x 去上课．谓词公式为： (∀x )(P (x )→ ┐Q (x ))．（2）设P (x )：x 是人，Q (x )：x 去工作，谓词公式为： (∃x )(P (x) ∧┐Q (x ))． 5．判断下列各题正误，并说明理由．（1）公式((Q ∧⌝R )→P )∧(⌝P →Q ∨R )↔P ∨R 为永真式．（2）求命题公式(P ∧Q )∧(⌝P ∨⌝R )的真值表，并判断它的类型. 解：（1）该公式是永真式．因为 R P R Q P P R Q ∨↔∨→⌝∧→⌝∧)())((R P R Q P P R Q ∨↔∨∨∧∨∨⌝⇔)()( R P Q Q R P ∨↔∧⌝∨∨⇔)( 1⇔（2）6．判断下列各题正误，并说明理由．（1）公式))(),(()(x xP y x yG x xP ∀→∃→∀是逻辑有效式(永真式)．（2）下面的推理是否正确，请给予说明． ① P （a ） P ② （∀x ）P （x ） US ① 解：（1）该公式是永真式．因为 ))(),(()(x xP y x yG x xP ∀→∃→∀⇔))(),(()(x xP y x yG x xP ∀∨⌝∃∨⌝∀1)(),()(⇔∀∨⌝∃∨⌝∀⇔x xP y x yG x xP（2）错误．② 应为（∀x ）P （x ） UG ① 全称指定规则与全称推广规则不能混淆．7．求公式R Q P →∧)(的析取、合取、主合取\主合取范式． 解：R Q P R Q P ∨∧⌝⇔→∧)()(R Q P ∨⌝∨⌝⇔)(R Q P ∨⌝∨⌝⇔ （析取、合取、主合取范式）⇔(┐P ∧(┐Q ∨Q )∧(┐R ∨R ))∨((┐P ∨P )∧┐Q ∧(┐R ∨R )) ∨((┐P ∨P )∧(┐Q ∨Q )∧R )⇔(┐P ∧┐Q ∧┐R )∨(┐P ∧┐Q ∧R )∨(┐P ∧Q ∧┐R )∨(┐P ∧Q ∧R )∨(P ∧┐Q ∧┐R )∨(P ∧┐Q ∧R )∨(P ∧Q ∧R )（主析取范式）8．用列真值表的方法求命题公式R Q P →→)(的主析取范式．解：列真值表取真值为1的项，所求主析取范式为：(┐P ∧┐Q ∧R )∨(┐P ∧Q ∧R )∨(P ∧┐Q ∧┐R )∨(P ∧┐Q ∧R ) ∨(P ∧Q ∧R )9．试求谓词公式),()),(),()((y x B y x yG y x xH x S x ∨∃→∃∧∀中，∀x ，∃x ，∃y 的辖域，试问G (x , y )和B (x , y )中x ，y 是自由变元，还是约束变元？解：∀x 的辖域：)),(),()((y x yG y x xH x S ∃→∃∧ ∃x 的辖域：H (x ,y )∃y 的辖域：G (x ,y ) G (x , y )中的x ，y 是约束变量，B (x , y )中的x , y 是自由变量. 10．证明命题公式(P →(Q ∨⌝R ))∧⌝P ∧Q 与⌝（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 )∨(⌝P ∧Q )∨(⌝P ∧Q ∧⌝R ) ⇔⌝P ∧Q （吸收律） ⇔⌝(P ∨⌝Q ) （摩根律）9．构造推理证明))()(()()(x Q x P x x xQ x xP →∀⇒∀→∃． 分析：前提：)()(x xQ x xP ∀→∃．结论：))()((x Q x P x →∀证：(1) )()(x xQ x xP ∀→∃ P(2) )()(x xQ x xP ∀∨⌝∃ T (1)E(3) )()(x xQ x P x ∀∨⌝∀ T (2) E (量词与否定的关系) (4) ))()((x Q x P x ∨⌝∀(5) ))()((x Q x P x →∀ T (4) E上面这些例题供大家复习参考．。
