东北大学期末考核《离散数学X》期末考试备战高分题集4

东北大学期末考核《离散数学X》期末考试备战高分题集4引言同学们，《离散数学X》的期末考试日益临近，想必大家都在紧张地复习备考。离散数学作为计算机等相关专业的核心基础课程，其概念抽象、逻辑性强，要想在期末考试中取得高分，除了深刻理解基本概念和定理外，足量且有针对性的练习必不可少。本套题集（第四套）聚焦于课程核心知识点，精选并设计了若干典型题目，旨在帮助大家巩固所学，熟悉题型，掌握解题技巧，查漏补缺，力求在期末考试中做到胸有成竹，下笔有神。请大家务必独立思考，认真作答，之后再对照解析进行反思，如此方能事半功倍。一、典型例题解析与拓展（一）集合论基础与二元关系题目1：设集合A={1,2,3,4}，B={2,4,6}，C={x|x∈N且x≤5}。(1)求(A∩B)∪(C-A)；(2)设R是集合A上的关系，定义为R={<a,b>|a,b∈A且a+b是偶数}，试判断R是否为等价关系，并说明理由。若为等价关系，求出其所有等价类。解析与点评：(1)首先，我们需要明确各个集合运算的定义。*A∩B表示集合A与B的交集，即由同时属于A和B的元素组成的集合。A={1,2,3,4}，B={2,4,6}，故A∩B={2,4}。*C-A表示集合C与A的差集，即由属于C但不属于A的元素组成的集合。C={x|x∈N且x≤5}={0,1,2,3,4,5}（注意：自然数N是否包含0，不同教材可能有不同约定，此处根据“x≤5”及通常离散数学中对N的理解，包含0更为合理，解题时需注意题干隐含信息或教材约定）。因此，C-A={0,5}。*最后，(A∩B)∪(C-A)即为{2,4}∪{0,5}={0,2,4,5}。此处容易出错的地方是对集合C的理解，以及差集运算的方向。务必牢记，差集C-A是“在C中去掉A有的元素”。(2)判断一个关系是否为等价关系，需验证其是否同时满足自反性、对称性和传递性。*自反性：对于任意a∈A，a+a=2a，显然是偶数。因此<a,a>∈R，自反性成立。*对称性：若<a,b>∈R，则a+b是偶数。因为加法交换律，b+a=a+b也是偶数，故<b,a>∈R，对称性成立。*传递性：若<a,b>∈R且<b,c>∈R，则a+b为偶数，b+c为偶数。两式相加得(a+b)+(b+c)=a+2b+c为偶数。由于2b是偶数，所以a+c=(a+2b+c)-2b也为偶数（偶数减偶数仍为偶数）。因此<a,c>∈R，传递性成立。综上，R是等价关系。等价类是指在等价关系下彼此等价的元素构成的集合。对于R，a与b等价当且仅当a+b为偶数，即a与b同奇偶（同奇或同偶）。*A中奇数有1,3，故[1]R=[3]R={1,3}。*A中偶数有2,4，故[2]R=[4]R={2,4}。此类题目是关系部分的常考题型，务必熟练掌握等价关系的三个性质的验证方法，并能准确找出等价类。（二）命题逻辑与逻辑代数题目2：(1)将下列自然语言命题符号化：“除非你努力学习，否则你不可能取得好成绩。”（设P：你努力学习；Q：你取得好成绩）。(2)已知命题公式G=(P→Q)∧(¬R∨S)。a)求G的主析取范式（要求：利用真值表法或等值演算法均可，但需写出关键步骤）。b)根据主析取范式，指出公式G的成真赋值和成假赋值，并判断其类型（重言式、矛盾式、可满足式）。解析与点评：(1)“除非A，否则B”是命题符号化中的一个难点，需要准确理解其逻辑含义。通常，“除非A，否则B”可以理解为“如果不A，那么B”，即¬A→B。在此题中，“除非你努力学习（P），否则你不可能取得好成绩（¬Q）”。即“如果不努力学习（¬P），那么不可能取得好成绩（¬Q）”。因此符号化为：¬P→¬Q。也可等价地表示为Q→P（逆否命题），即“如果你取得好成绩，那么你努力学习了”，这在语义上也是通顺的。两种形式是等值的。符号化时，务必仔细揣摩自然语言的语义，找准逻辑连接词的对应关系。(2)a)求主析取范式，这里采用等值演算法。G=(P→Q)∧(¬R∨S)首先，消去蕴含词：P→Q⇔¬P∨Q。所以G⇔(¬P∨Q)∧(¬R∨S)此时公式为合取范式，但我们需要的是主析取范式。可以考虑将其展开为析取范式，再通过补元法化为极小项之和。设所有命题变元为P,Q,R,S（虽然原式中未出现所有变元的组合，但主析取范式要求包含所有相关变元）。先将(¬P∨Q)看作关于P,Q的表达式，(¬R∨S)看作关于R,S的表达式。(¬P∨Q)⇔(¬P∧Q)∨(¬P∧¬Q)∨(P∧Q)（这是(¬P∨Q)的主析取范式，包含P,Q的3个极小项）(¬R∨S)⇔(¬R∧S)∨(¬R∧¬S)∨(R∧S)（这是(¬R∨S)的主析取范式，包含R,S的3个极小项）然后，G⇔[(¬P∧Q)∨(¬P∧¬Q)∨(P∧Q)]∧[(¬R∧S)∨(¬R∧¬S)∨(R∧S)]利用分配律展开，共3×3=9个合取项，每个合取项都是一个包含P,Q,R,S的极小项：(¬P∧Q∧¬R∧S)∨(¬P∧Q∧¬R∧¬S)∨(¬P∧Q∧R∧S)∨(¬P∧¬Q∧¬R∧S)∨(¬P∧¬Q∧¬R∧¬S)∨(¬P∧¬Q∧R∧S)∨(P∧Q∧¬R∧S)∨(P∧Q∧¬R∧¬S)∨(P∧Q∧R∧S)这就是G的主析取范式（可简写为m6∨m4∨m14∨m2∨m0∨m10∨m14∨m12∨m14？此处需注意极小项的编码规则，通常按P,Q,R,S的顺序，1表示原变量，0表示否定。例如，¬P∧¬Q∧¬R∧¬S是m0，¬P∧¬Q∧¬R∧S是m1，以此类推。请同学们自行核对编码，确保准确无误）。或者，也可以通过列出所有2^4=16种赋值，判断哪些赋值使G为真，然后写出对应的极小项。这种方法虽然繁琐，但不易出错，尤其在变元较少时。b)主析取范式中包含的极小项对应的赋值即为成真赋值，其余赋值为成假赋值。由于G的主析取范式包含了部分但不是全部极小项，因此G是可满足式。本题综合考察了命题符号化、等值演算和主范式的求解与应用，是逻辑部分的核心内容，需要重点掌握。（三）图论基础题目3：已知无向简单图G有8个顶点，每个顶点的度数不是5就是6。证明G中至少有5个度数为6的顶点或者至少有6个度数为5的顶点。解析与点评：此类问题通常可考虑使用握手定理和反证法。握手定理：在任何无向图中，所有顶点的度数之和等于边数的两倍，必为偶数。证明：假设G中既没有至少5个度数为6的顶点，也没有至少6个度数为5的顶点。即：*度数为6的顶点个数n6≤4；*度数为5的顶点个数n5≤5。由于图G共有8个顶点，所以n5+n6=8。结合上述假设，n5≤5且n6≤4，而5+4=9≥8，因此可能的组合有：(n5=5,n6=3)或(n5=4,n6=4)（因为n5和n6都必须是非负整数，且之和为8）。我们来计算这两种情况下的总度数之和：1.若n5=5,n6=3：总度数之和=5×5+3×6=25+18=43。2.若n5=4,n6=4：总度数之和=4×5+4×6=20+24=44。根据握手定理，总度数之和必须是偶数。43是奇数，矛盾！44是偶数，似乎可行？但我们的假设是否仅排除了这两种情况？仔细想想，“至少有5个度数为6的顶点”的否定是“至多有4个度数为6的顶点”；“至少有6个度数为5的顶点”的否定是“至多有5个度数为5的顶点”。所以反证法的假设是这两个否定同时成立，即n6≤4且n5≤5。而n5=8-n6，所以当n6≤4时，n5=8-n6≥4。因此可能的n5取值为4,5（因为n5≤5），对应n6=4,3，即上述两种情况。对于情况1：总度数43为奇数，与握手定理矛盾，故不可能。对于情况2：总度数44为偶数，不矛盾。但这是否意味着我们的原命题不成立？注意！我们原命题是“至少有5个度数为6的顶点或者至少有6个度数为5的顶点”。其否定是“（至多4个度数为6的顶点）并且（至多5个度数为5的顶点）”。我们刚才假设的就是这个否定。而情况2(n5=4,n6=4)满足这个否定，且总度数为偶数，似乎是一个反例？问题出在哪里？哦！不对，我们再仔细看原命题：“至少有5个度数为6的顶点或者至少有6个度数为5的顶点”。“或者”是逻辑或，只要其中一个成立即可。我们假设的是两个都不成立。但是，当n5=4,n6=4时，n5=4，确实不是“至少6个”；n6=4，也确实不是“至少5个”。这似乎说明原命题不成立？但这与题目要求我们“证明”相悖，说明我们的分析可能有误。重新审视：我们忽略了一个关键点：n5必须是偶数！因为度数为5的顶点，每个贡献5（奇数）的度数。奇数个奇数相加为奇数，偶数个奇数相加为偶数。n5个5相加的和的奇偶性取决于n5的奇偶性。而总度数之和必须是偶数（握手定理）。在情况2中，n5=4（偶数），4个5相加是20（偶数）；n6=4，4个6相加是24（偶数）。偶数+偶数=偶数，总度数44是偶数，没问题。情况1中，n5=5（奇数），5个5相加是25（奇数）；n6=3，3个6相加是18（偶数）。奇数+偶数=奇数，43为奇数，矛盾，所以情况1不可能。那么，唯一可能的“否定假设下”的情况是情况2(n5=4,n6=4)。但这是否真的可能存在？题目说“无向简单图”。简单图中，每个顶点的度数不能超过n-1（n为顶点数）。此处n=8，顶点最大度数为7，5和6都小于7，所以度数本身没问题。但是，我们是否还需要考虑别的约束？比如，对于度数为6的顶点，每个都要与其他6个顶点相连。如果有4个度数为6的顶点，它们彼此之间以及与度数为5的顶点之间的连接是否会导致度数为5的顶点的度数超过5？设n5=4（记为A类顶点），n6=4（记为B类顶点）。每个B类顶点（共4个）需要连出6条边。这些边可以连接到A类或B类顶点。B类顶点之间最多可以有C(4,2)=6条边。每个B类顶点在B类内部最多连3条边（与其他3个B类顶点）。因此，每个B类顶点至少需要向A类顶点连6-3=3条边。4个B类顶点，每个至少向A类连3条边，那么A类顶点收到的边数至少为4×3=12条。而A类顶点共有4个，每个A类顶点度数为5，总度数为4×5=20条边。这些边包括A类内部之间的边和A类与B类之间的边。设A类内部边数为m，则A类顶点之间的边对A类总度数的贡献为2m（每条边贡献2度）。A类与B类之间的边数为k（即A类收到的边数，也就是B类发出的边数），则k≥12。因此，2m+k=20。由于k≥12，所以2m=20-k≤8，即m≤4。A类内部最多有4条边。A类有4个顶点，A类内部边数m≤C(4,2)=6，4≤6，是可能的。例如，A类4个顶点构成一个圈（4条边，每个A类顶点在内部获得2度），则k=20-2×4=12。此时每个B类顶点向A类发出3条边（12/4=3），B类内部边数为(4×6-12)/2=(24-12)/2=6条边，而4个B类顶点最多可连C(4,2)=6条边，即B类顶点构成一个完全图K4，每个B类顶点在内部获得3度（6条边，每个顶点3条），3+3