华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x
2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5
第12章习题答案 1.设T 是一个非平凡树，证明T 中最长基本链的起点和终点的次数为1。 证明：假设P 是T 中最长的基本链，P 的起点或终点的次数不为1，即它的次数至少是2，则至少有一个顶点，令其为u ，与P 的起点或终点邻接。若u 在P 上，则构成圈，与T 是树矛盾，若u 不在P 上，则存在比P 更长的基本链，这与P 是T 中最长的基本链矛盾。因此，非平凡树T 中最长基本链的起点和终点的次数必为1。 2.证明恰好有两个顶点的次数为1的树必为一基本链。 证明：假设T 是任意一个恰好有两个顶点的次数为1的树，如果T 不是一基本链，则至少有一个分支顶点的次数大于2。设T 有n 个顶点，则T 有n-2个分支顶点，n-1条边。根据定理9.1，T 的顶点的次数之和等于T 的边数的2倍，可知 2（n-1）>2+2（n-2） 因此得到2n-2>2n-2，矛盾。故T 必为一基本链。即恰好有两个顶点的次数为1的树必为一基本链。 3.一个树有n 2个顶点次敉为2，n 3个顶点次数为3，…，n k 个顶点次数为k ，问这个树有几片树叶？ 解：设这个树为T ，有x 片树叶，则T 有x +n 2+n 3+…+n k -1条边。根据定理9.1，T 的顶点的次数之和等于T 的边数的2倍，有 x +2n 2+3n 3+…+k n k =2（x +n 2+n 3+…+n k -1） 解得 x =n 3+2n 4+3n 5+…+（k-2）n k +2 即这个树有n 3+2n 4+3n 5+…+（k-2）n k +2片树叶。 7.证明在完全二元树中，弧的总数等于2(n t -1)，这里n t 是树叶的数目。 证明：设完全二元树T 有n 个顶点，m 条弧。因为它有n t 片树叶，所以除树叶以外的顶点有n -n t 个。由于在完全二元树中，除树叶以外的顶点的引出次数均为2，每片树叶的引出次数均为0，故所有顶点的引出次数之和为2（n -n t ），它等于弧的总数m 。又因为1-=n m ， 故有2（n -n t ）=1-n ，解得n =2n t -1。因此m=n-1=2(n t -1)。 11. 图12.11给出了一个有序树，试求其对应的位置二元树。 解：把该树顶点标记i u 的下标i 作为序， 利用将有序树转化为位置二元树的算法， 求得其对应的位置二元树如右图所示。 4u 3 u 5 u 7 u 0u 1 u 2 u 6 u 8 u 9 u 10
《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群
19、代数系统是指由及其上的或 组成的系统。 20、设
1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={
第十二章 格和布尔代数 12.1 设c b a ,,是格),( A 中的元素，求证：如果b a ，则)()(c a b c b a ∨∧∧∨ 证明 因为b a ，且)(c a a ∨ ，所以)(c a b a ∨∧ 。 又因为b c b ∧，且c a c c b ∨∧ ，所以)(c a b c b ∨∧∧ 。 即)(c a b ∨∧是a 和c b ∧的上界，从而有： )()(c a b c b a ∨∧∧∨ 。 12.2 设c b a ,,是格),( A 中的元素，求证： （1）)()()(c a b a c b a ∨∧∨∧∨ （2）)( )()(c b a c a b a ∨∧∧∨∧ (1)证明 因为c a a b a a ∨∨ ,，所以)()(c a b a a ∨∧∨ 。 又因为b a b c b ∨∧ ，且c a c c b ∨∧ ，所以)()(c a b a c b ∨∧∨∧ 。 即)()(c a b a ∨∧∨是a 和c b ∧的上界。 所以，)()()(c a b a c b a ∨∧∨∧∨ 。 （2）证明 因为a b a ∧，a c a ∧，则有a c a b a )()(∧∨∧。 又因为b b a ∧，有c b b b a ∨∧ ，同理c b c a ∨∧ 。从而有c b c a b a ∨∧∨∧ )()(。 即)()(c a b a ∧∨∧是a 和c b ∨的下界。 因此，)( )()(c b a c a b a ∨∧∧∨∧ 。 10.3 设),,(∧∨A 是一个代数系统，其中∨和∧是满足吸收律的二元运算，证明：∨和∧也满足等幂律。 证明
因为∨和∧是满足吸收律，所以a b a a =∨∧)(，a b a a =∧∨)(。于是有： )((b a a a a a ∧∨∧=∧ )(c a a ∨∧= （其中b a c ∧=） a = 同理可证，a a a =∨。 故∨和∧也满足等幂律。 10.4 证明：一个格是可分配的，当且仅当对于这个格中的任意元素a ，b 和c ，有 )()(c b a c b a ∧∨∧∨ 证明 （1）必要性 因为a c a ∧和c b c b ∧∧ ，所以)()()(c b a c b c a ∧∨∧∨∧ 。 又因为格为分配格，所以)()()(c b c a c b a ∧∨∧=∧∨。 因此，)()(c b a c b a ∧∨∧∨ 。 （2）充分性 因为对于c b a ,,?，有)()(c b a c b a ∧∨∧∨ ，则 )()()(c c b a c b a ∧∧∨=∧∨ （等幂律） c c b a ∧∧∨=))(( （结合律） c c b a ∧∧∨))(( （假设） c a c b ∧∨∧=))(( （交换律） )()(c a c b ∧∨∧ （假设） 又因为b a a ∨ ，c c ，所以c b a c a ∧∨∧)( ；同理，c b a c b ∧∨∧)( 因此，c b a c b c a ∧∨∧∨∧)()()( 综上所述，)()()(c b c a c b a ∧∨∧=∧∨ 故该格是可分配的。 10.5 证明一个格),( A 是分配的，当且仅当对A 中的任意元素a ，b 和c ，有 )()()()()()(a c c b b a a c c b b a ∨∧∨∧∨=∧∨∧∨∧
一（6%）选择填空题。 (1) 设S = {1，2，3}，R 为S 上的二元关系，其关系图如右图所示，则R 具有（ ）的性质。 A. 自反、对称、传递； B. 反自反、反对称； C. 自反、传递； D. 自反。 (2) 设A = {1, 2, 3, 4}， A 上的等价关系 R = {
(4)没有不犯错的人。 五（10%）在自然推理系统Ｐ中构造下面推理的证明： 如果他是计算机系本科生或者是计算机系研究生，则他一定学过DELPHI语言且学过C++语言。只要他学过DELPHI语言或者Ｃ++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。 六（10%）在自然推理系统中构造下面推理的证明（个体域：人类）： 每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。 七（14%）下图给出了一些偏序集的哈斯图，判断其是否为格，对于不是格的说明理由，对于是格的说明它们是否为分配格、有补格和布尔格（布尔代数）。 八（12%）设S = {1, 2, 3, 4, 6, 8, 12, 24}，“ ”为S上整除关系， (1)画出偏序集> ,S的哈斯图； < (2)设B = { 2, 3, 4, 6, 12}，求B的极小元、最小元、极大元、最大元，下界，上界。 九（8%）画一个无向图，使它是： (1)是欧拉图，不是哈密尔顿图； (2)是哈密尔顿图，不是欧拉图； (3)既不是欧拉图，也不是哈密尔顿图； 并且对欧拉图或哈密尔顿图，指出欧拉回路或哈密尔顿回路，对于即不是欧拉图也不是哈密尔顿图的说明理由。 十（8%）设6个字母在通信中出现的频率如下： 12 13 :c :b% 45 :a% % :e% :f 9 5 : d% % 16 用Huffman算法求传输它们的最佳前缀码。要求画出最优树，指出每个字母对应的编码，n个按上述频率出现的字母需要多少个二进制数字。 并指出传输)2 ( n 10≥
离散数学复习 第一章命题逻辑基本概念 1．掌握命题及相关概念 2．理解各联结词的逻辑关系 3．会将复合命题符号化 4．会求公式的真值表，并用它求公式的成真赋值、成假赋值及判断公式的类型 第二章命题逻辑等值演算 1．记住基本等值式，会应用它们进行公式的等值演算 2．了解简单析取式、简单合取式、析取范式、合取范式的概念 3．理解极大项、极小项的概念 4．掌握求主析取范式和主合取范式的方法(等值演算和真值表法) 5．会用主范式判断公式的类型及进行简单应用 6．了解联结词完备集的概念 第三章命题逻辑的推理理论 1．理解并记住推理形式结构的两种形式： (1) A1∧A2∧…∧A k→B (2) 前提：A1, A2, … , A k 结论：B 2．掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）3．记住自然推理系统P系统中的推理规则 4．掌握自然推理系统P系统中的推理方法 第四章一阶逻辑基本概念 1．会进行命题的符号化 2．理解公式的解释 3．理解永真式、矛盾式、可满足式的概念及相互之间的关系 4．对于给定的解释会判断公式的真值，或判定真值不确定（即仍不是命题） 第五章一阶逻辑等值演算与推理 1．理解并记住重要等值式，并能熟练地应用它们 2．会使用置换规则、换名规则(约束条变项)、代替规则(自由变项) 3．会求给定公式的前束范式 4．正确地使用UI, UG, EG, EI规则，特别要注意它们之间的关系 5．在F系统，对给定的推理，正确地构造出它的证明 第六章集合代数 1. 掌握集合的表示法 2．能够判别元素是否属于给定的集合 3．能够判别两个集合之间是否存在包含、相等、真包含等关系 第七章二元关系 1. 掌握二元关系、空关系、全域关系、恒等关系、关系的定义域、值域、域、逆关系、 左复合、右复合、限制、像的概念； 2．掌握关系的集合表达式、关系矩阵和关系图三种表示法； 3．掌握关系的基本运算和关系的幂的运算性质，掌握关系的五个性质：自反性、反自反性、对称性、反对称性和传递性等五个性质； 4．掌握关系的闭包的概念，会应用关系的性质求出关系的闭包（自反闭包、对称闭包和传递闭包）；
《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.
2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
Discrete Mathematics Lecture Notes Chapter11:Graph Theory Scribe:Denis Tchaouchev December11,2017 1De?nitions ?A graph is a collection of nodes,vertices,and edges. –In a directed graph(digraph)?={a,b}={b,a}= ?A walk is a sequence of alternating vertices and edges. ?A trail is a walk with no repeated vertices. ?A circuit is a closed trail(starts and stops at the same place).?A Eulerian circuit is a circuit containing every edge. ?A Eulerian trail is a trail containing every edge. ?A Eulerian graph is a graph containing a Eulerian circuit. Figure1:Examples of Eulerian Circuits(Wendy Sparks) 1
2Konigsberg Bridge Problem Figure2:The Konigsberg Bridge Problem The Konigsberg Bridge Problem asks if it is possible to?nd a route,be-ginning at any location,that crosses every bridge and returns to its original starting point.Think of the bridges as edges and the land as vertices. Euler’s Theorem:A connected(9a path between every vertex)undirected graph G has a Eulerian circuit if and only if every vertex in G has an even degree. G has a Eulerian trail if and only if G has exactly two vertices of odd degree. 3Travelling Salesman Problem Figure3:Examples of Hamiltonian cirucit/path(Robert Almazan)?A Hamiltonian circuit is a circuit that visits each vertex at least once.?A Hamiltonian trail is a trail that visits each vertex at least once. 2
主要内容 1. 无向图与有向图. 2. 简单图与多重图. 3. 顶点的度数与握手定理. 4. 图的同构. 5. 完全图与正则图. 6. 子图与补图. 7. 通路与回路的定义. 8. n阶图中通路与回路的性质. 9. 无向图的连通性. 10 无向图中顶点之间的短程线及距离. 11 无向图的连通度. 12 有向图的连通性及其分类. 13 扩大路径法及极大路径. 14 二部图及判别定理. 学习要求 1. 熟练掌握握手定理及其推论的内容及其应用. 2. 掌握图同构的概念. 3. 加深对简单图、完全图、正则图、子图、补图等概念的理解. 4. 深刻理解通路与回路的定义及其分类. 5. 能正确地使用不同的表示法表示通路与回路. 6. 理解同构意义下与定义意义下通路与回路的区别与联系. 7.
深刻理解无向图中两个顶点之间的连通关系、短程线、距离、图的连通性等概念. 8. 深刻理解点割集、边割集、点连通度、边连通度等概念. 9. 理解有向图中, 顶点之间的可达、相互可达关系、短程线、距离等概念. 10 深刻理解有向图的连通性及分类, 以及判别定理. 11 理解并会使用扩大路径法. 12 理解无向图与有向图关联矩阵的概念. 13 会求无向图与有向图的关联矩阵. 14 深刻理解有向图的邻接矩阵与可达矩阵的概念. 15 熟练掌握求有向图的邻接矩阵及各次幂的方法, 并利用它们求D中定义意义下的通路与回路数. 典型习题 1. 无向图G有16条边, 3个4度顶点, 4个3度顶点, 其余顶点的度数均小于3, 问G的阶数n至少为几？ 2. 9阶图G中, 每个顶点的度数不是5就是6, 证明G中至少有5个6度顶点或至少有6个5度顶点. 3. 在一次象棋比赛中, n名选手中的任意两名选手之间至多只下一盘, 又每人至少下一盘, 证明：总能找到两名选手, 他们下棋的盘数相同. 4. 下面两组数, 是否是可以简单图化的？若是, 请给出尽量多的非同构的无向简单图以它为度数 列. 5. 的所有非同构的生成子图. 画出K 4 6. 设无向图G中只有两个奇度顶点u与v, 试证明u与v必连通. 7. 设D=