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

/《离散数学》期末复习题填空题〔每空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元集合,则2A6、集合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上的等价关系.证明RS是A上的等价关系。2、证明苏格拉底论证：凡人要死。苏格拉底是人.苏格拉底要死。3、P→Q.┐QR.┐R.┐SPÞ┐S4、在群<G,*>中.除单位元e外.不可能有别的幂等元。5、设R和S是二元关系.证明：<RS>-1=R-1S-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>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有46、集合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跑得快。该命题符号化为：¬∀x∀y<F<x>∧G<y>→H<x,y>>。6、符号化命题"2是素数且是偶数"。设F<x>：x是素数。G<x>：x是偶数。a：2.则命题符号化为F<a>∧G<a>。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的关系矩阵。解：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的关系矩阵。解：R的关系矩阵为：9、设有向图G如下所示.求各个结点的出度、入度和度数。deg<v1>＝3.deg+<v1>＝1.deg-<v1>＝2；deg<v2>＝deg+<v4>＝deg-<v2>＝0；deg<v3>＝3.deg+<v3>＝2.deg-<v3>＝1；deg<v4>＝2.deg+<v4>＝1.deg-<v4>＝1；10、设有向图G如下所示.求各个结点的出度、入度和度数。答：deg<v1>＝3.deg+<v1>＝2.deg-<v1>＝1；deg<v2>＝3.deg+<v2>＝2.deg-<v2>＝1；deg<v3>＝5.deg+<v3>＝2.deg-<v3>＝3；deg<v4>＝deg+<v4>＝deg-<v4>＝0；deg<v5>＝1.deg+<v5>＝0.deg-<v5>＝1；11、设无向图G如下所示.求它的邻接矩阵。12、求命题公式┐<p∧┐q>的真值表。pq┐qp∧┐q┐<p∧┐q>0010101001101101100113、设<2x+y,5>=<10,x－3y>.求x.y。解：由定理列出如下方程组：求解得x=5.y=0。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。解：domR1={1,3,5}.ranR1={2,4,6}.fldR1=domR1∪ranR1={1,2,3,4,5,6}；domR2={1,2}.ranR2={4,6}.fldR2=domR2∪ranR2={1,2,4,6}。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。解：R={<1,5>,<2,4>,<3,3>},S={<3,1>,<4,2>,<5,3>}.从而R◦S={<1,3>,<2,2>,<3,1>}或者因<1,5>∈R.<5,3>∈S.所以<1,3>∈R◦S；因<2,4>∈R.<4,2>∈S.所以<2,2>∈R◦S；因<3,3>∈R.<3,1>∈S.所以<3,1>∈R◦S；从而R◦S={<1,3>,<2,2>,<3,1>}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–1R◦S={<a,1>,<a,4>,<a,5>,<b,2>,<c,2>,<c,4>,<c,5>}<R◦S>-1={<1,a>,<4,a>,<5,a>,<2,b>,<2,c>,<4,c>,<5,c>}R–1={<a,a>,<c,a>,<b,b>,<b,c>,<c,c>}.S–1={<1,a>,<4,a>,<2,b>,<4,c>,<5,c>}S–1◦R–1={<1,a>,<2,b>,<2,c>,<4,a>,<4,c>,<5,a>,<5,c>}。17、A＝{1,2,3,4,5,6}.D是整除关系.画出哈斯图并求出最小元、最大元、极小元和极大元。解：1是A的最小元.没有最大元.1是极小元.4、5、6都是A的极大元。18、设集合A={a,b,c}.A上的关系R={<a,a>,<a,b>,<b,c>}.求R的自反、对称、传递闭包。r<R>={<a,a>,<a,b>,<b,c>,<b,b>,<c,c>}s<R>={<a,a>,<a,b>,<b,a>,<b,c>,<c,b>}t<R>={<a,a>,<a,b>,<b,c>,<a,c>}19、求下图中顶点v0与v5之间的最短路径。解：如下图所示v0与v5之间的最短路径为：v0,v1,v2,v4,v3,v5最短路径值为1+2+1+3+2=920、分别用三种不同的遍历方式写出对下图中二叉树点的访问次序。先根遍历：ABDEHCFIJGK中根遍历：DBHEAIFJCGK后根遍历：DHEBIJFKGCA四、证明题〔每题10分.共20分1、若R和S都是非空集A上的等价关系.证明RS是A上的等价关系。证明：a∈A.因为R和S都是A上的等价关系.所以xRx且xSx。故xRSx。从而RS是自反的。a,b∈A.aRSb.即aRb且aSb。因为R和S都是A上的等价关系.所以bRa且bSa。故bRSa。从而RS是对称的。a,b,c∈A.aRSb且bRSc.即aRb.aSb.bRc且bSc。因为R和S都是A上的等价关系.所以aRc且aSc。故aRSc。从而RS是传递的。故RS是A上的等价关系。2、证明苏格拉底论证：凡人要死。苏格拉底是人.苏格拉底要死。设：H<x>：x是人。M<x>：x是要死的。s：苏格拉底。本题要证明：<"x><H<x>→M<x>>∧H<s>ÞM<s>证明：⑴<"x><H<x>→M<x>> P⑵H<s>→M<s> US⑴⑶H<s> P⑷M<s> ⑵、⑶3、P→Q.┐QR.┐R.┐SPÞ┐S证明：<1>┐R前提<2>┐QR前提<3>┐Q〔1.〔2<4>P→Q前提<5>┐P〔3.〔4<6>┐SP前提<7>┐S〔5.〔64、在群<G,*>中.除单位元e外.不可能有别的幂等元。因为e∗e=e.所以e是幂等元。设aÎG且a∗a=a.则有a=e∗a=<a–1∗a>∗a=a–1∗<a∗a>=a–1∗a=e.即a=e。5、设R和S是二元关系.证明：<RS>-1=R-1S-1证明：.所以.6、证明：<<Q∧S>→R>∧<S→<P∨R>>=<S∧<P→Q>>→R.证明：左边：<<Q∧S>→R>∧<S→<P∨R>>=<┐<Q∧S>∨R>∧<┐S∨<P∨R>>=<┐Q∨┐S∨R>∧<┐S∨P∨R>=<┐Q∨┐S∨R>∧<┐S∨P∨R>右边：<S∧<P→Q>>→R=┐<S∧<┐P∨Q>>∨R=<┐S∨<P∧┐Q>>∨R=<┐Q∨┐S∨R>∧<┐S∨P∨R>所以<<Q∧S>→R>∧<S→<P∨R>>=<S∧<P→Q>>→R.7、设I是整数集合.k是正整数.I上的关系R＝{<x,y>|x,y∈I.且x－y可被k整除}.证明R是等价关系。证明：<1>对任意的x∈A.有x－x=0可被k整除。所以<x,x>∈R.即R具有自反性。<2>对任意的x.y∈A.<x,y>∈R.即x－y可被k整除.设x－y=km.则y－x=－km.显然y－x可被k整除。所以<y,x>∈R.即R具有对称性。<3>设x.y.z∈A.若<x,y>∈R.<y,z>∈R.即x－y可被k整除.y－z可被k整除.设x－y=km.y－z=kn.则x－z=k<m+n>.即x－z可被k整除。所以<x,z>∈R.即R具有传递性。综上所述.R具有自反性、对称性和传递性.故R是等价关系。8、证明：⑴<<p→q>→r>Û<<┐q∧p>∨r>⑵p→<q→r>⇔┐r→<q→┐p>证明：<<p→q>→r>Û<<┐p∨q>→r> //蕴涵等值式Û<┐<┐p∨q>>∨r //蕴涵