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

《离散数学》期末复习题填空题（每空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上的等价关系，证明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），（6）4、在群<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 //