离散数学B复习题

离散数学B复习题---离散数学B复习题一、命题逻辑核心概念：命题、联结词（否定、合取、析取、蕴涵、等价）、真值表、等值式、析取范式与合取范式、主析取范式与主合取范式、命题逻辑的推理理论。1.概念辨析与基本运算：*请指出下列语句中哪些是命题，并说明理由。对于是命题的语句，请判断其真值（如果能确定的话）。*a)请勿吸烟。*b)今天天气真好啊！*c)如果明天下雨，那么我就带伞。*d)x+y=5。*给定命题变元p：“今天是晴天”，q：“我们去郊游”。试用自然语言描述下列复合命题：*a)¬p∨q*b)p→¬q*c)(p∧q)∨(¬p∧¬q)*构造命题公式(p→q)∧r的真值表，并指出该公式的类型（重言式、矛盾式、可满足式）。2.等值演算与范式：*试用等值演算法证明等值式：p→(q∨r)⇔(p→q)∨(p→r)。*求命题公式(p∨q)→r的主析取范式和主合取范式，并通过主范式判断该公式的类型。3.推理理论：*请用自然推理系统P，证明下面的推理是否正确：前提：p∨q，p→¬r，s→t，¬s→r，¬t结论：q*（附加题）某案件有四名嫌疑人。已知：1.如果A作案，则B也作案；2.B和C中至少有一人作案；3.C和D中至少有一人未作案；4.如果D作案，则A也作案。请问：谁一定作案？请写出推理过程。二、谓词逻辑（一阶逻辑）核心概念：个体词、谓词、量词（全称量词、存在量词）、谓词公式、辖域、自由变元与约束变元、谓词公式的解释与赋值、等值式与置换规则、前束范式、谓词逻辑的推理理论。1.基本概念与符号化：*指出下列谓词公式中各量词的辖域，以及各变元的自由出现和约束出现。*∀x(F(x)→∃yG(x,y))∨H(x,z)*将下列自然语言语句符号化：*a)所有的计算机都需要电力。*b)有些学生喜欢离散数学。*c)并非所有的鸟都会飞。*d)存在一个数，它是所有数的倍数。（假设个体域为实数集）2.等值演算与前束范式：*利用谓词逻辑的等值式，将下列公式化成与之等值的前束范式。*∃xF(x)∧¬∀xG(x)*∀xF(x)→∃yG(y)3.推理理论：*尝试用谓词逻辑的自然推理系统，证明下面的推理：前提：∀x(M(x)→P(x))，∃xM(x)结论：∃xP(x)*（思考题）为什么在全称量词消去规则中，当用个体常项取代变元时，要求该个体常项在公式中不出现？三、集合论初步核心概念：集合的基本概念与表示法、集合间的关系（包含、相等）、集合的基本运算（并、交、补、差、对称差）、集合恒等式、幂集、有序对与笛卡儿积。1.集合的基本概念与运算：*设集合A={a,{b},c}，B={{a},b,c}，求A∪B，A∩B，A-B，P(A)（A的幂集）。*判断下列集合恒等式是否成立，若成立请给出证明，若不成立请举出反例。*A∩(B∪C)=(A∩B)∪(A∩C)*A-(B∩C)=(A-B)∩(A-C)2.笛卡儿积：*设A={1,2}，B={a,b}，求A×B和B×A。*证明：若A×B=A×C，且A非空，则B=C。四、二元关系核心概念：二元关系的定义与表示（集合、矩阵、图）、关系的运算（定义域、值域、逆、复合）、关系的性质（自反性、反自反性、对称性、反对称性、传递性）、关系的闭包（自反闭包、对称闭包、传递闭包）、等价关系与划分（等价类、商集）、偏序关系与偏序集（哈斯图、极大元、极小元、最大元、最小元、上界、下界、上确界、下确界）。1.关系的基本概念与表示：*设集合A={1,2,3,4}，R是A上的二元关系，定义为R={<x,y>|x整除y}。*用列举法写出R。*画出R的关系图。*写出R的关系矩阵。2.关系的性质：*判断上题中的关系R具有哪些性质（自反性、反自反性、对称性、反对称性、传递性），并说明理由。*设A={a,b,c}，试构造A上的一个二元关系，使其同时具有自反性和反对称性，但不具有传递性。3.关系的闭包：*设集合A={1,2,3}，A上的二元关系R={<1,2>,<2,3>,<3,1>}。求R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)。4.等价关系与偏序关系：*设集合A={1,2,3,4,5,6}，R是A上的模3同余关系，即<x,y>∈R当且仅当x≡ymod3。*证明R是A上的等价关系。*写出A关于R的所有等价类。*写出A关于R的商集A/R。*设集合A={2,3,4,5,6,7,8}，≤是A上的整除关系。*画出≤的哈斯图。*求集合B={4,5,6}的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界（如果存在）。五、函数核心概念：函数的定义、定义域、值域、像与原像、函数的性质（单射、满射、双射）、函数的复合、反函数、常用函数（恒等函数、特征函数、集合的基数（势）概念初步）。1.函数的基本概念与性质：*判断下列关系是否为从集合A到集合B的函数。若是，判断其是否为单射、满射或双射，并说明理由。*A={1,2,3}，B={4,5,6}，f={<1,4>,<2,5>,<3,6>}。*A={1,2,3}，B={4,5}，f={<1,4>,<2,5>,<3,4>}。*A=B=R（实数集），f(x)=x²。*设A和B是有限集，|A|=m，|B|=n。问：*从A到B可以定义多少个不同的函数？*在什么条件下，存在从A到B的单射？*在什么条件下，存在从A到B的满射？2.函数的复合与反函数：*设f:R→R，f(x)=x+1；g:R→R，g(x)=x²-2。求f∘g和g∘f，并指出它们的定义域和值域。*证明：若函数f:A→B是双射，则其反函数f⁻¹:B→A也是双射。---复习建议与温馨提示：1.回归教材，吃透概念：离散数学的逻辑性强，对概念的理解必须精准。复习时务必仔细回顾教材中的定义、定理和例题。2.动手实践，多做练习：只看不练是学不好离散数学的。通过做题可以检验对知识的掌握程度，熟悉解题方法和技巧。本复习题仅为示例，建议大家结合课程大纲和更多习题进行练习。3.梳理脉络，构建体系：尝试画出知识点之间的联系图，将零散的概念串联起来，形成完整的知识体系。例如，命题逻辑与谓词逻辑的联系与区别，关系与函数的联系等。4.重视证明，理解逻辑：对于定理的证明，要