(0004)离散数学复习思考题

（0004）《离散数学》复习思考题一、填空题1．（（（P→Q）∨￢Q）→RQ）合式公式。2．“我正在说谎”命题。3．公式（R∧（R→Q））→Q重言式。4．（（（￢P∨R）→Q）∧R）∨Q）合式公式。5．公式（x）（P（x）→Q(y)）∧R(x)中的自由未知量为。6.“如果雪是黑的，太阳从西边出”是命题。7．A，B为集合，则A-BB-A。8．A，B为集合，则A∩（B∪A）A。9．设Y={a,b,c},,则P(Y)中有个元素。10．A，B为集合，则A∩BB∪A。11．A，B为集合，则B∪（A-B）B。12．设X={1,2,3},,则X上不同的关系有种。13．A，B为集合，BA,则(B-A)∪BB。14．R，S都是A上的自反，传递，对称关系，则s（R∩S）=。15.R，S都是A上的自反，传递，对称关系，则t（R∩S）=。16．A是一个集合，则P（A）上集合的包含关系是关系。17．A={1，2，3}上的小于关系函数。18．A，B，C为集合，则（A－B）∩CA∩C－B∩C。19．一个二元运算函数。20．设X={a,b,c},Y={s,r},从X到Y上有个不同的函数。21．函数二元关系。22．I是一个整数集，*是加法运算，代数系统I，*中的幺元是。23．A是整数集，*是乘法运算，代数系统A，*中的幺元是。24．独异点半群。25．群中的元素逆元。26．群一定是交换群。27．n个结点的树中有边数为。28．5个结点的无向完全图平面图。29．根树中有一个结点的入度为。30．有n个结点的无向完全图的边数结点数。31．欧拉图汉密尔顿图。32．根树中有个结点的入度为0。33.无回路的连通图是。34．欧拉图连通图。35．图中所有结点的度数之和为。二．判断题1．A，B，C为命题公式，如果A∨CB∨C，则有AB。()2．P→（Q→R）Q→（P→R）。（）3．所有重言式都是等价的。（）4．任一命题公式既可化为析取范式，又可化为合取范式。（）5．命题“有理数都是实数”谓词符号化时不用量词。（）6．空集是每个集合的子集。（）7.φ∈P（A），其中P（A）为集合A的幂集。（）8．空集是P（A）中的一个元素，其中A为任一集合，P（A）为A的幂。（）9．实数集上的整除关系是反对称关系。（）10．序偶做成的集合一定是关系。（）11．笛卡尔积运算满足交换律。（）12．集合的包含关系是传递关系。（）13.集合A上的相容关系具有传递性。()14.等价关系具有传递性。（）15.偏序集的任一非空子集一定有极大元。（）16．函数不一定是关系。（）17．双射函数一定是入射函数。()18．任意一个函数f的逆函数都存在。（）19.恒等函数一定是双射函数。（）20．实数集上的除法运算一定是封闭的。（）21．自然数集上的加法运算一定是封闭的。（）22．有零元的代数系统一定不是群。（）23．R为实数集，*为R上的普通乘法运算，代数系统R,*是群。（）24．群中不一定有零元。（）25．S为集合，代数系统〈P（S），∩〉是群。（）26．A为正数集，·是普通乘法运算，代数系统A，·是群。（）27．代数系统R,＋是群,其中R为实数集。（）28．群中的运算满足消去律。（）29．根树中所有结点的入度为1。（）30．完全图Ｋ５是欧拉图。（）31．有n个结点的无向完全图是汉密尔顿图。（）32．平面图一定是连通图。（）33．两个结点相同，边数相同的图一定同构。（）34．汉密尔顿图一定不是欧拉图。（）35．汉密尔顿图是连通图。（）三．计算题1．将“我留下，仅当你走”命题符号化。2．将“除非天不下雨，否则我乘车上班”命题符号化。3．将“我去镇上，仅当我有时间”命题符号化。4．将“我将去看电影，当我有时间”命题符号化。5．将复合命题“我既不去看电影，也不去看电视，我准备做作业。”分解成原子命题。6．做命题公式(P→Q)→￢R的真值表。7．做命题公式(Q∧G)∨￢R的真值表。8．求出命题公式￢（P→Q）∧R的合取范式。9．求（P→Q）→R的析取范式。10．求￢（P→Q）的合取范式。11．求出命题公式￢（P→Q）→R的合取范式。12．将“不是所有运动员都是教练员”谓词符号化。13．求空集Ф的幂集的幂集。14．求空集Ф的幂集。15．已知集合A={a,b,c,d}上的关系R={a,a,a,b,b,c,d,d}，求R的对称闭包s(R)。16．A={1，2，3，…20}上的小于等于关系是偏序关系，A的子集B={2，5，8，10，14，19}，求B的极大元，极小元，最大元，最小元。17．整数集I上的同余模5的关系R是等价关系，试求出由R所确定的所有等价类。18．设A={1，2，3，4}上的二元关系R={1,2,2,4,3,3,1,3}，求r（R）。19．设A={1，2，3，4}上的二元关系R={1,2,2,4,3,3,1,3}，求S(R)-R．20．设A={1，2，3，4}上的二元关系R={1,2,2,4,3,3,1,3}，求t（R）。21．设A={1，2，3，4}上的二元关系R={1,2,2,4,3,3,1,3}和S={1,1,2,1,3,4,3,1},求SοR。22．设A={1，2，3，4}上的二元关系S={1,1,2,1,3,4,3,1},求S的逆关系。23．设A={1，2，3，4}上的关系R={x,y∣（x-y）/2是整数}，S={x,y∣（x-y）/3是正整数}，求R∪S。24．设A={1，2，3，4}上的关系R={x,y∣（x-y）/2是整数}，S={x,y∣（x-y）/3是正整数}，求R∩S。25．设A={1，2，3，4}上的关系R={x,y∣（x-y）/2是整数}，S={x,y∣（x-y）/3是正整数}，求S-R。26．设A={1，2，3，4}上的关系R={x,y∣（x-y）/2是整数}，S={x,y∣（x-y）/3是正整数}，求～R∪S。27．设A={1，2，}，B={3，4，5}，求AB。28．设A={1，2，}，B={3，4，5}，求～（AB）。29．已知集合A={a,b,c,d}上的关系R={a,a,a,b,b,c,d,d}，求R的传递闭包t(R)。30．集合A={1，2，3，…20}上的大于等于关系是偏序关系，A的子集B={1，3，5，10。16，19}，求B的极大元，极小元，最大元，最小元。31．集合T={1，2，3，4}上的关系R={1,1,1,4,4,1,4,4,2,2,2,3,3,2,3,3}是等价关系，试求出由R所确定的所有等价类。32．判断函数f:R→R,f(r)=2r-15是否是满射，入射，双射，R为实数集。33．判断函数f:I→N,f(i)=∣2i∣+1是否是满射，入射，双射，I为整数集。34．判断函数f:N→N,f(n)=n是否是满射，入射，双射，N为自然数集。35．设A={a,b,c},B={1,0}，求出从A到B的一切可能的函数。36．已知函数f={1,2,2,3,3,1},g={1,2,2,3,3,3}，求fоg。37．给出两个是群的代数系统。38．举出两个不是群的代数系统。39．集合S={a,b,c,d,e}上的二元运算*的运算表如下，求出它的幺元，零元，及逆元。*abcdeabacccbabcdeccccccdedcbaedecdb40．设A={a,b}，A的幂集P（A）上的交运算∩，给出它的运算表。41．设A={a,b}，A的幂集P（A）上的交运算∪，给出它的运算表。42．求出带权为1，3，4，5，6的最优二叉树，并求其权。43．一棵树中，度数为2的结点有a个，度数为3的结点有b个，度数为4的结点有c个，剩下的结点度数都为1，求出度数为1的结点有多少个。44．已知5个结点的完全图G,且各条边上的边权分别为1,2,3,4,5,6,7,8,9,10,求出G的一棵最小生成树,并求其权。45．画出有汉密尔顿回路，没有欧拉回路的图。46．画出有汉密尔顿回路，也有欧拉回路的图。47．画出没有汉密尔顿回路，没有欧拉回路的图。48．画一个有欧拉回路，而没有汉密尔顿回路的图。49．画出一个既是平面图，又是无向完全图的图。四．证明题1．证明：（P∨Q）∧（Q→R）∧（P→S）S∨R。2．证明(x)(￢A(x)→B(x))，(x)￢B(x)(x)A(x)3．已知R是集合X上的对称关系，证明R∪IX是X上的相容关系。4．已知S和R是集合A上的等价关系，证明S∩R也是A上的等价关系。5．已知S是集合A上的自反和传递关系，证明S∩SC是A上的等价关系。6．已知集合X={1,2,3,4,5,6,7,8,9,10}上的关系R={x,y∣x能整除y，且x，y∈X}，证明R是X上的偏序关系。7．设fоg是复合函数，如果是fоg入射，证明g也是入射。8．已知R是实数集，＊是普通乘法运算，判断代数系统R，＊是否是一个群，并证明你的结论。9.设I是整数集，H={x∣x=dn,n∈I,d是一固定的正整数}，+是普通的加法运算，证明代数系统I,+与代数系统H,+是同构的。10.问有1个结点的度数为1，2个结点的度数为2，3个结点的度数为3，4个结点的度数为4的树吗？并证明你的理由。（0004）《离散数学》复习思考题答案一．1．不是；2不是；3是；4是；5x,y；6真；7≠；8=；98；10；11；1229；13=；14R∩S；15R∩S；16偏序关系；17不是；18≠；19．是；208；21是；220；231；24是；25有；26循环群；27n-1；28不是；290；30大于；31不一定是；321；33树；34一定是；35边数的两倍。二．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勾；29叉；30勾；31勾；32叉；33叉；34叉；35勾。三．1．设：P：我留下；Q：你走。符号化为：P→Q。2．设：P：天不下雨；Q：我乘车上班。命题符号化为：￢P→Q3．设：P：我去镇上；Q：我有时间。命题符号化为：P→Q。4．设：P：我去看电影；Q：我有时间。命题符号化为：Q→P。5．原子命题为：我不去看电影；我不去看电视；我准备做作业。6．PQRP→Q￢R（P→Q）→￢RTTTTFFTTFTTTTFTFFTTFFFTTFFFTTTFFTTFFFTFTTTFTTTFF7．解命题公式的真值表如下：QGRQ∧G￢R（Q∧G）∨￢RTTTTFTTTFTTTTFTFFFTFFFTTFFFFTTFFTFFFFTFFTTFTTFFF8．原式￢（￢P∨Q）∧RP∧￢Q∧R。9．原式￢（￢P∨Q）∨R（P∧￢Q）∨R10．原式￢（￢P∨Q）P∧￢Q11．原式（P→Q）∨R￢P∨Q∨R12．设：S（x）：x是运动员；R（x）：x是教练员。￢(x)（S(x)→R（x））13．P（P（Ф））={Ф，{Ф}}14．P（Φ）={Φ}15．s(R)={a,a,a,b,b,c,d,d,b,a,c,b}16．B的极大元：19；极小元：2；最大元：19；最小元：2。17．等价类：[0]={…-10，-5，0，5，10，…}[1]={…-9，-4，1，6，11，…}[2]={…-8，-3，2，7，12，…}[3]={…-7，-2，3，8，13，…}[4]={…-6，-1，4，9，14，…}18．r(R)=R∪IA={1,2,2,4,3,3,1,3,1,1,2,2,4,4}19．s(R)=R∪RC={2,1,4,2,3,1}20．t(R)=R∪R2∪R3∪R4={1,2,2,4,3,3,1,3,1,4}21.SоR={1,2