中国石油大学大学《离散数学》期末复习题和答案

..《离散数学》期末复习题一、填空题（每空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是阿贝尔群G,+的元素.则-(a+b+c)=。10、一个图的哈密尔顿路是。11、不能再分解的命题称为.至少包含一个联结词的命题称为。12、命题是。13、如果p表示王强是一名大学生.则┐p表示。14、与一个个体相关联的谓词叫做。15、量词分两种：和。16、设A、B为集合.如果集合A的元素都是集合B的元素.则称A是B的。17、集合上的三种特殊元是、及。18、设A={a,b}.则ρ(A)的四个元素分别是：...。19、代数系统是指由及其上的或组成的系统。..20、设L,*1,*2是代数系统.其中是*1,*2二元运算符.如果*1,*2都满足、.并且*1和*2满足.则称L,*1,*2是格。21、集合A={a,b,c,d}.B={b}.则A\B=。22、设A={1,2},则∣A∣=。23、在有向图中.结点v的出度deg+(v)表示.入度deg-(v)表示以。24、一个图的欧拉回路是。25、不含回路的连通图是。26、不与任何结点相邻接的结点称为。27、推理理论中的四个推理规则是、、、。二、判断题（每题2分.共20分）1、空集是唯一的。2、对任意的集合A.A包含A。3、恒等关系不是对称的.也不是反对称的。4、集合{1,2,3,3}和{1,2,2,3}是同一集合。5、图G中.与顶点v关联的边数称为点v的度数.记作deg(v)。6、在实数集上.普通加法和普通乘法不是可结合运算。7、对于任何一命题公式.都存在与其等价的析取范式和合取范式。8、设（A,*）是代数系统.a∈A.如果a*a＝a.则称a为（A.*）的等幂元。9、设f：A→B.g：B→C。若f.g都是双射.则gf不是双射。10、无向图的邻接矩阵是对称阵。11、一个集合不可以是另一个集合的元素。12、映射也可以称为函数.是一种特殊的二元关系。13、群中每个元素的逆元都不是惟一的。14、{0,1,2,3,4},MAX,MIN是格。15、树一定是连通图。..16、单位元不是可逆的。17、一个命题可赋予一个值.称为真值。18、复合命题是由连结词、标点符号和原子命题复合构成的命题。19、任何两个重言式的合取或析取不是一个重言式。20、设f：A→B.g：B→C。若f.g都是满射.则g◦f不是满射。21、集合{1,2,3,3}和{1,2,3}是同一集合。22、零元是不可逆的。23、一般的.把与n个个体相关联的谓词叫做一元谓词。24、“我正在说谎。”不是命题。25、用A表示“是个大学生”.c表示“张三”.则A(c)：张三是个大学生。26、设F＝{3,3,6,2}.则F-1＝{6,3,2,6}。27、欧拉图是有欧拉回路的图。28、设f：A→B.g：B→C。若f.g都是单射.则g◦f也是单射。三、计算题（每题10分.共40分）1、设A={c,d},B={0,1,2}.则计算A×B.B×A。2、A={a,b,c}.B={1,2}.计算A×B。3、A={a,b,c}.计算A×A。4、符号化命题“如果2大于3.则2大于4。”。5、符号化命题“并不是所有的兔子都比所有的乌龟跑得快”。6、符号化命题“2是素数且是偶数”。7、设A={a,b,c,d}.R是A的二元关系.定义为：R={a,a,a,b,b,a,c,b,c,a,d,c,d,b,d,a}.写出A上二元关系R的关系矩阵。8、设A={1,2,3,4}.R是A的二元关系.定义为：R={1,1,1,2,2,1,3,2,3,1,4,3,4,2,4,1}.写出A上二元关系R的关系矩阵。9、设有向图G如下所示.求各个结点的出度、入度和度数。..10、设有向图G如下所示.求各个结点的出度、入度和度数。11、设无向图G如下所示.求它的邻接矩阵。12、求命题公式┐(p∧┐q)的真值表。13、设2x+y,5=10,x－3y.求x.y。14、R1、R2是从{1,2,3,4,5}到{2,4,6}的关系.若R1＝{1,2,3,4,5,6}.R2={1,4,2,6}.计算domR1.ranR1.fldR1.domR2.ranR2.fldR2。15、例：设A={1,2,3,4,5}.B={3,4,5},C={1,2,3}.A到B的关系R={x,y|x+y=6}.B到C的关系S={y,z|y－z=2}.求R◦S。16、集合A={a,b,c}.B={1,2,3,4,5}.R是A上的关系.S是A到B的关系。R={a,a,a,c,b,b,c,b,c,c}.S={a,1,a,4,b,2,c,4,c,5}.求R◦S.S–1◦R–117、A＝{1,2,3,4,5,6}.D是整除关系.画出哈斯图并求出最小元、最大元、极小元和极大元。..18、设集合A={a,b,c}.A上的关系R={a,a,a,b,b,c}.求R的自反、对称、传递闭包。19、求下图中顶点v0与v5之间的最短路径。20、分别用三种不同的遍历方式写出对下图中二叉树点的访问次序。四、证明题（每题10分.共20分）1、若R和S都是非空集A上的等价关系.证明RS是A上的等价关系。2、证明苏格拉底论证：凡人要死。苏格拉底是人.苏格拉底要死。3、P→Q.┐QR.┐R.┐SP┐S4、在群G,*中.除单位元e外.不可能有别的幂等元。5、设R和S是二元关系.证明：(RS)-1=R-1S-16、证明：((Q∧S)→R)∧(S→(P∨R))=(S∧(P→Q))→R.7、设I是整数集合.k是正整数.I上的关系R＝{x,y|x,y∈I.且x－y可被k整除}.证明R是等价关系。8、证明((p→q)→r)((┐q∧p)∨r)9、证明(P∨Q)∧(P→R)∧(Q→S)S∨R10、证明P→┐Q.Q∨┐R.R∧┐S┐P11、证(∀x)(P(x)∨Q(x))┐(∀x)P(x)→(x)Q(x)v0v2v1v4v33v5121475326..12、证明定理：设G,◦是群.对于任意a,b∈G.则方程a◦x=b与y◦a=b.在群内有唯一解。《离散数学》复习题参考答案一、填空题（每空1分.共20分）1、集合A上的偏序关系的三个性质是自反性、反对称性和传递性。2、一个集合的幂集是指该集合所有子集的集合。3、集合A={b,c}.B={a,b,c,d,e}.则A⋃B={a,b,c,d,e}。4、集合A={1,2,3,4}.B={1,3,5,7,9}.则A⋂B={1,3}。5、若A是2元集合,则2A有4个元素。6、集合A={1,2,3｝.A上的二元运算定义为：a*b=a和b两者的最大值.则2*3=3。7、设A={a,b,c,d},则∣A∣=4。8、对实数的普通加法和乘法.0是加法的幂等元.1是乘法的幂等元。9、设a,b,c是阿贝尔群G,+的元素.则-(a+b+c)=(-a)+(-b)+(-c)。10、一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路。11、不能再分解的命题称为原子命题.至少包含一个联结词的命题称为复合命题。12、命题是能够表达判断（分辩其真假）的陈述语句。13、如果p表示王强是一名大学生.则┐p表示王强不是一名大学生。14、与一个个体相关联的谓词叫做一元谓词。15、量词分两种：全称量词和存在量词。16、设A、B为集合.如果集合A的元素都是集合B的元素.则称A是B的子集。17、集合上的三种特殊元是单位元、零元及可逆元。18、设A={a,b}.则ρ(A)的四个元素分别是：空集.{a}.{b}.{a,b}。19、代数系统是指由集合及其上的一元或二元运算符组成的系统。20、设L,*1,*2是代数系统.其中是*1,*2二元运算符.如果*1,*2都满足交换律、结合律.并且*1和*2满足吸收律.则称L,*1,*2是格。21、集合A={a,b,c,d}.B={b}.则A\B={a,c,d}。22、设A={1,2},则∣A∣=2。..23、在有向图中.结点v的出度deg+(v)表示以v为起点的边的条数.入度deg-(v)表示以v为终点的边的条数。24、一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路。25、不含回路的连通图是树。26、不与任何结点相邻接的结点称为孤立结点。27、推理理论中的四个推理规则是全称指定规则(US规则)、全称推广规则(UG规则)、存在指定规则(ES规则)、存在推广规则(EG规则)。二、判断题（每题2分.共20分）1、√。2、√。3、×。4、√。5、√。6、×。7、√。8、√。9、×。10、√。11、×。12、√。13、×。14、√。15、√。16、×。17、√。18、√。19、×。20、×。21、√。22、√。23、×。24、√。25、√。26、×。27、√。28、√。1、空集是唯一的。2、对任意的集合A.A包含A。3、恒等关系不是对称的.也不是反对称的。4、集合{1,2,3,3}和{1,2,2,3}是同一集合。5、图G中.与顶点v关联的边数称为点v的度数.记作deg(v)。6、在实数集上.普通加法和普通乘法不是可结合运算。7、对于任何一命题公式.都存在与其等价的析取范式和合取范式。8、设（A,*）是代数系统.a∈A.如果a*a＝a.则称a为（A.*）的等幂元。9、设f：A→B.g：B→C。若f.g都是双射.则gf不是双射。10、无向图的邻接矩阵是对称阵。11、一个集合不可以是另一个集合的元素。12、映射也可以称为函数.是一种特殊的二元关系。13、群中每个元素的逆元都不是惟一的。14、{0,1,2,3,4},MAX,MIN是格。15、树一定是连通图。16、单位元不是可逆的。17、一个命题可赋予一个值.称为真值。..18、复合命题是由连结词、标点符号和原子命题复合构成的命题。19、任何两个重言式的合取或析取不是一个重言式。20、设f：A→B.g：B→C。若f.g都是满射.则g◦f不是满射。21、集合{1,2,3,3}和{1,2,3}是同一集合。22、零元是不可逆的。23、一般的.把与n个个体相关联的谓词叫做一元谓词。24、“我正在说谎。”不是命题。25、用A表示“是个大学生”.c表示“张三”.则A(c)：张三是个大学生。26、设F＝{3,3,6,2}.则F-1＝{6,3,2,6}。27、欧拉图是有欧拉回路的图。28、设f：A→B.g：B→C。若f.g都是单射.则g◦f也是单射。三、计算题（每题10分.共40分）1、设A={c,d},B={0,1,2}.则A×B={c,0,c,1,c,2,d,0,d,1,d,2}.B×A={0,c,0,d,1,c,1,d,2,c,2,d}。2、A={a,b,c}.B={1,2}.A×B={a,b,c}×{1,2}={a,1,b,1,c,1,a,2,b,2,c,2}。3、A={a,b,c}.A×A={a,b,c}×{a,b,c}={a,a,a,b,a,c,b,a,b,b,b,c,c,a,,c,b,c,c}。4、符号化命题“如果2大于3.则2大于4。”。设L(x,y)：x大于y.a：2.b：3.c：4.则命题符号化为L(a,b)→L(a,c)。5、符号化命题“并不是所有的兔子都比所有的乌龟跑得快”。设F(x)：x是兔子。G(x)：x是乌龟。H(x,y)：x比y跑得快。该命题符