本科离散数学

1．设P：a是偶数，Q：b是偶数。R：a+b是偶数，则命题“若a是偶数，b是偶数，则a+b也是偶数”符号化为（D．PQ→R）。2．表达式x（P（x，y）Q（z））y（Q（x，y）→zQ（z））中x的辖域是（P（x，y）Q（z））。3．设则命题为假的是（）。4．设G是有n个结点的无向完全图，则G的边数（1/2n（n-1））。5．设G是连通平面图，有v个结点，e条边，r个面，则r=（e-v+2）。6．若集合A={1，{2}，{1，2}}，则下列表述正确的是({1}A)．7．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为(5)．8．设无向图G的邻接矩阵为则G的边数为(7)．9．设集合A={a}，则A的幂集为({，{a}})．10．下列公式中(AB(AB))为永真式．11．若G是一个汉密尔顿图，则G一定是(连通图)．12．集合A={1,2,3,4}上的关系R={<x，y>|x=y且x,yA}，则R的性质为（传递的）．13．设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集<A，>上的元素5是集合A的（极大元）．14．图G如图一所示，以下说法正确的是({(a,d),(b,d)}是边割集)．图一15．设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（(x)(A(x)∧B(x))）．16．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是(AB，且AB)．17．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是(（d）是强连通的)．18．设图G的邻接矩阵为则G的边数为(5)．19．无向简单图G是棵树，当且仅当(G连通且边数比结点数少1)．20．下列公式((P(QP))(P(PQ)))为重言式．21．若集合A＝{a，{a}，{1，2}}，则下列表述正确的是({a}A)．22．设图G＝<V,E>，vV，则下列结论成立的是()．23．命题公式（P∨Q）→R的析取范式是(（P∧Q）∨R)24．下列等价公式成立的为(P(QP)P(PQ))．25．设A={a,b}，B={1,2}，R1，R2，R3是A到B的二元关系，且R1={<a，2>,<b，2>}，R2={<a，1>,<a，2>,<b，1>}，R3={<a，1>,<b，2>}，则（R2）不是从A到B的函数．26．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为(无、2、无、2)．27．若集合A的元素个数为10，则其幂集的元素个数为（1024）．28．如图一所示，以下说法正确的是(e是割点)．图一29．设完全图K有n个结点(n≥2)，m条边，当（n为奇数）时，K中存在欧拉回路．30．已知图G的邻接矩阵为，则G有（5点，7边）．二、填空题（每小题3分，共15分）1．设A，B为任意命题公式，C为重言式，若ACBC，那么AB是重言式（重言式、矛盾式或可满足式）。2．命题公式（P→Q）P的主合取范式为。3．设集合A={，{a}}，则P（A）=。4．设图G=〈V，E〉，G′=〈V′，E′〉，若V′=V,E′E,则G′是G的生成子图。5．在平面G=〈V，E〉中，则=2|E|，其中（i=1，2，…，r）是G的面。6．命题公式的真值是假（或F，或0）．7．若无向树T有5个结点，则T的边数为4．8．设正则m叉树的树叶数为t，分支数为i，则(m-1)i=t-1．9．设集合A={1，2}上的关系R＝{<1,1>,<1,2>}，则在R中仅需加一个元素<2,1>，就可使新得到的关系为对称的．10．(x)(A(x)→B(x，z)∨C(y))中的自由变元有z，y．11．若集合A={1，3，5，7}，B={2，4，6，8}，则A∩B=空集（或）．12．设集合A={1，2，3}上的函数分别为：f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，则复合函数gf={<1,2>,<2,3>,<3,2>,}．13．设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为2|E|（或“边数的两倍”）．14．无向连通图G的结点数为v，边数为e，则G当v与e满足e=v-1关系时是树．15．设个体域D＝{1,2,3}，P(x)为“x小于2”，则谓词公式(x)P(x)的真值为假（或F，或0）16．命题公式的真值是T（或1）．17．若图G=<V,E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W|S|．18．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素0，则该序列集合构成前缀码．19．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为5．20．(x)(P(x)→Q(x)∨R(x，y))中的自由变元为R(x，y)中的y．21．设集合A={0,1,2,3}，B={2,3,4,5}，R是A到B的二元关系，则R的有序对集合为{<2,2>，<2,3>，<3,2>}，<3,3>．22．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2．23．设G＝<V,E>是有6个结点，8条边的连通图，则从G中删去3条边，可以确定图G的一棵生成树．24．无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数．25．设个体域D＝{1,2}，则谓词公式消去量词后的等值式为A(1)A(2)．26．设集合A＝{a，b}，那么集合A的幂集是{,{a,b},{a},{b}}．27．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有2个．28．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边后使之变成树．29．设连通平面图G的结点数为5，边数为6，则面数为3．30．设个体域D＝{a,b}，则谓词公式(x)A(x)∧（x）B（x）消去量词后的等值式为(A(a)∧A(b))∧(B（a）∨B（b）)．31.设集合A={0，1，2}，B={l，2，3，剖，R是A到B的二元关系，R={<x,y>|x∈A且y∈B且x，y∈A∩B}则R的有序对集合为___{<1,1>,<1,2>,<2,1>,<2,2>}___32.设G是连通平面图，v，e，r分别表示G的结点数，边数和面数，则v，e和r满足的关系式__v-e+r=2_____33.G=<V,E>是有20个结点，25条边的连通图,则从G中删去__6__条边，可以确定图G的一棵生成树.34.无向图G存在欧拉回路，当且仅当G所有结点的度数全为偶数且_连通____35.设个体域D={1,2}，则谓词公式"xA(x)消去量词后的等值式为__A(1)∧A(2)___三、化简解答题11．设集合A={1，2，3，4}，A上的二元关系R，R={〈1，1〉，〈1，4〉，〈2，2〉，〈2，3〉，〈3，2〉，〈3，3〉，〈4，1〉，〈4，4〉}，说明R是A上的等价关系。解从R的表达式知，即R具有自反性；三、逻辑公式翻译1．将语句“今天上课．”翻译成命题公式．设P：今天上课，则命题公式为：P．2．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式． 设P：他去操场锻炼，Q：他有时间，则命题公式为：PQ．3．将语句“他是学生．”翻译成命题公式．设P：他是学生，则命题公式为：P．4．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．设P：明天下雨，Q：我们就去郊游，则命题公式为：PQ．5．将语句“他不去学校．”翻译成命题公式．设P：他去学校，P．6．将语句“他去旅游，仅当他有时间．”翻译成命题公式．设P：他去旅游，Q：他有时间，PQ．7．将语句“所有的人都学习努力．”翻译成命题公式．设P(x)：x是人，Q(x)：x学习努力，（x）(P(x)Q(x))．8．将语句“如果你去了，那么他就不去．”翻译成命题公式．设P：你去，Q：他去，PQ．9．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．设P：小王去旅游，Q：小李去旅游，PQ．10．将语句“所有人都去工作．”翻译成谓词公式．设P(x)：x是人，Q(x)：x去工作，(x)(P(x)Q(x))．11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．设P：所有人今天都去参加活动，Q：明天的会议取消， PQ．12．将语句“今天没有人来．”翻译成命题公式．设P：今天有人来，P．13．将语句“有人去上课．”翻译成谓词公式．设P(x)：x是人，Q(x)：x去上课，(x)(P(x)Q(x))．11.将语句"如果小李学习努力，那么他就会取得好成绩."翻译成命题公式.设P：小李学习努力，Q:小李会取得好成绩，P→Q12.将语句"小张学习努力,小王取得好成绩."翻译成命题公式.设P：小张学习努力，Q:小王取得好成绩，P∧Q四、判断说明题1．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1,3>}，则f是A到B的函数．错误．因为A中元素2没有B中元素与之对应，故f不是A到B的函数．2．设G是一个有4个结点10条边的连通图，则G为平面图． 错误．不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”3．设N、R分别为自然数集与实数集，f：N→R，f(x)=x+6，则f是单射．正确．设x1，x2为自然数且x1x2，则有f(x1)=x1+6x2+6=f(x2)，故f为单射．4．下面的推理是否正确，试予以说明．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）US（1）．错误．（2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆．5．如图二所示的图G存在一条欧拉回路．图二错误．因为图G为中包含度数为奇数的结点．6．设G是一个有6个结点14条边的连通图，则G为平面图．错误．不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”7．如果R1和R2是A上的自反关系，则R1∪R2是自反的．正确．R1和R2是自反的，xA，<x,x>R1，<x,x>R2，则<x,x>R1R2，所以R1∪R2是自反的．8．如图二所示的图G存在一条欧拉回路．vv1v2v3v5v4dbacefghn图二正确．因为图G为连通的，且其中每个顶点的度数为偶数．9．┐P∧（P→┐Q）∨P为永真式．正确．┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，如果P的值为真，则┐P∧（P→┐Q）∨P为真，如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真，也即┐P∧（P→┐Q）∨P为真，所以┐P∧（P→┐Q）∨P是永真式．另种说明：┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，只要其中一项为真，则整个公式为真．可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真，所以┐P∧（P→┐Q）∨P是永真式．或用等价演算┐P∧（P→┐Q）∨PT10．若偏序集<A，R>的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．图一正确．对于集合A的任意元素x，均有<x,a>R（或xRa），所以a是集合A中的最大元．按照最小元的定义，在集合A中不存在最小元．11.如果R1和R2是A上的自反关系，则R1∩R2是自反的。正确，R1和R2，是自反的，"x∈A,<x,x>∈R1,<x,x>∈R2,则<x,x>∈R1∩R2，所以R1∩R2是自反的.12.如图二所示的图中存在一条欧拉回路.图二正确，因为图G为连通的，且其中每个顶点的度数为偶数。五．计算题（每小题12分，本题共36分）1．试求出（P∨Q）→（R∨Q）的析取范式．（P∨Q）→（R∨Q）┐(P∨Q)∨（R∨Q）(┐P∧┐Q)∨（R∨Q）(┐P∧┐Q)∨R∨Q（析取范式）2．设A={{1},1,2}，B={1,{2}}，试计算（1）（A∩B）（2）（A∪B）（3）A（A∩B）．（1）（A∩B）={1}（2）（A∪B）={1,2,{1},{2}}（3）A（A∩B）={{1},1,2}3．图G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)}，对应边的权值依次为1、2、3、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；图一图一abcd112453（1）G的图形表示如图一所示：图二图二abcd112453（3）最小的生成树如图二中的粗线所示：权为：1+1+3=54．画一棵带权为1,2,2,3,4的最优二叉树,计算它们的权．1223347512图三权为13+23+22+32+42=275．求（P∨Q）→R的析取范式与合取范式．（P∨Q）→R（P∨Q）∨R(P∧Q)∨R（析取范式）(P∨R)∧(Q∨R)（合取范式）6．设A={0，1，2，3}，R={<x，y>|xA，yA且x+y<0}，S={<x，y>|xA，yA且x+y2}，试求R，S，RS，S-1，r(R)．R=,S={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}RS=，S-1=S，r(R)=IA={<0,0>,<1,1>,<2,2>,<3,3>}．7．试求出（P∨Q）→R的析取范式，合取范式，主合取范式． （P∨Q）→R┐(P∨Q)∨R(┐P∧┐Q)∨R（析取范式）(┐P∨R)∧(┐Q∨R)（合取范式）((┐P∨R)∨(Q∧┐Q))∧((┐Q∨R)∨(P∧┐P))(┐P∨R∨Q)∧(┐P∨R∨┐Q)∧(┐Q∨R∨P)∧(┐Q∨R∨┐P)(┐P∨Q∨R)∧(┐P∨┐Q∨R)∧(P∨┐Q∨R)8．设A={{a,b},1,2}，B={a,b,{1},1}，试计算（1）（AB）（2）（A∪B）（3）（A∪B）（A∩B）．（1）（AB）={{a,b},2}（2）（A∪B）={{a,b},1,2,a,b,{1}}（3）（A∪B）（A∩B）={{a,b},2,a,b,{1}}9．图G=<V,E>，其中V={a,b,c,d,e}，E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)}，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．（1）G的图形表示为：（2）邻接矩阵：（3）粗线表示最小的生成树，权为7：10．设谓词公式，试（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元．（1）x量词的辖域为，z量词的辖域为,y量词的辖域为．（2）自由变元为与中的y，以及中的z约束变元为x与中的z，以及中的y．11．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算（1）（AB）；（2）（A∩B）；（3）A×B．（1）AB={{1},{2}}（2）A∩B={1,2}（3）A×B={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>，<{2},{1,2}>，<1,1>，<1,2>，<1,{1,2}>，<2,1>，<2,2>,<2,{1,2}>}12．设G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形． （1）G的图形表示为：（2）邻接矩阵：（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2（4）补图如下：13．设集合A={1，2，3，4}，R={<x,y>|x,yA；|xy|=1或xy=0}，试（1）写出R的有序对表示；（2）画出R的关系图；（3）说明R满足自反性，不满足传递性．（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}12343）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。因有<2,3>与<3,4>属于R，但<2,4>不属于R，所以R在A上不是传递的。14．求PQR的析取范式，合取范式、主析取范式，主合取范式．P→（R∨Q）Û┐P∨(R∨Q)Û┐P∨Q∨R（析取、合取、主合取范式）Û(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(P∧┐Q∧┐R)∨(P∧┐Q∧R)∨(P∧Q∧┐R)∨(P∧Q∧R)（主析取范式）15．设图G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试画出G的图形表示；写出其邻接矩阵；(3)求出每个结点的度数；v1v2v1v2v3v4v5（1）关系图（2）邻接矩阵（3）deg(v1)=2deg(v2)=3deg(v3)=4deg(v4)=3v1v2vv1v2v3v4v5（4）补图16．设谓词公式$x(A(x,y)∧"zB(x,y,z))∧"yC(y,z)试

(1)写出量词的辖域;

$x量词的辖域为(A(x,y)∧"zB(x,y,z)),"z量词的辖域为B(x,y,z),"y量词的辖域为C(y,z)(2)指出该公式的自由变元和约束变元. 自由变元为(A(x,y)∧"zB(x,y,z))中的y,以及C(y,z)中的z.约束变元为(A(x,y)∧"zB(x,y,z))中的x与B(x,y,z)中的z,以及C(y,z)中的y。六、证明题1．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．证明：设xA，因为R自反，所以xRx，即<x,x>R；又因为S自反，所以xRx，即<x,x>S．即<x,x>R∩S故R∩S自反．2．试证明集合等式A(BC)=(AB)(AC)．证明：设S=A(BC)，T=(AB)(AC)，若x∈S，则x∈A或x∈BC，即x∈A或x∈B且x∈A或x∈C．也即x∈AB且x∈AC，即x∈T，所以ST．反之，若x∈T，则x∈AB且x∈AC，即x∈A或x∈B且x∈A或x∈C，也即x∈A或x∈BC，即x∈S，所以TS．因此T=S．3．试证明集合等式A(BC)=(AB)(AC)．证明：设S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若x∈S，则x∈A且x∈B∪C，即x∈A且x∈B或x∈A且x∈C，也即x∈A∩B或x∈A∩C，即x∈T，所以ST．反之，若x∈T，则x∈A∩B或x∈A∩C，即x∈A且x∈B或x∈A且x∈C也即x∈A且x∈B∪C，即x∈S，所以TS．因此T=S．4．试证明集合等式A(BC)=(AB)(AC)．证明：设S=A(BC)，T=(AB)(AC)，若x∈S，则x∈A或x∈BC，即x∈A或x∈B且x∈A或x∈C．也即x∈AB且x∈AC，即x∈T，所以ST．反之，若x∈T，则x∈AB且x∈AC，即x∈A或x∈B且x∈A或x∈C，也即x∈A或x∈BC，即x∈S，所以TS．因此T=S．5．试证明（x）（P（x）∧R（x））（x）P（x）∧（x）R（x）．证明：（1）（$x）（P（x）∧R（x））P（2）P（a）∧R（a）ES(1)（3）P（a）T(2)I（4）（$x）P（x）EG(3)（5）R（a）T(2)I（6）（$x）R（x）EG(5)（7）（$x）P（x）∧（$x）R（x）T(5)(6)I6．设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍证明设，，…，为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，，，…，这m＋1个整数中至少存在两个数和，它们被m除所得余数相同，因此和的差是m的整数倍。7．已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C)证明∵xA-（B∪C）xA∧x（B∪C）xA∧（xB∧xC）（xA∧xB）∧（xA∧xC）x（A-B）∧x（A-C）x（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C）8．（15分）设<A，*>是半群，对A中任意元a和b，如a≠b必有a*b≠b*a，证明：(1)对A中每个元a，有a*a＝a。(2)对A中任意元a和b，有a*b*a＝a。(3)对A中任意元a、b和c，有a*b*c＝a*c。证明由题意可知，若a*b＝b*a，则必有a＝b。(1)由(a*a)*a＝a*(a*a)，所以a*a＝a。(2)由a*(a*b*a)＝(a*a)*(b*a)＝a*b*(a*a)＝(a*b*a)*a，所以有a*b*a＝a。(3)由(a*c)*(a*b*c)＝(a*c*a)*(b*c)＝a*(b*c)