离散数学复习思考题201606

《离散数学》复习思考题一、选择题对于公式),()),(),((zxzRzxQyxPx，下列说法正确的是（）。A．y是自由出现的；B．x是约束出现的；C．x的辖域是),()),(),((zxzRzxQyxP；D．x的辖域是),(yxP．A设}},8,7,6{},5,4{},3,2,1{{A，下列正确的是（）。A．A1；B．A}3,2,1{；C．A；D．A}3,2,1{．D设A-B=，则有（）。A．B=；B．B≠；C．AB；D．AB．C设N是自然数集合，函数1,)(nnnfNNNf，：是（）。A．满射，不是单射；B．单射，不是满射；C．双射；D．非单射非满射．B设R为实数集，函数f：R→R，f(x)=xe，则f是（）。A．满射函数；B．单射函数；C．双射函数；D．非单射非满射．B设Z是整数集合，N是自然数集合，则函数xxfNZf)(，：是（）。A．满射，不是单射；B．单射，不是满射；C．双射；D．非单射非满射．A设函数f：N→N（N为自然数集），f(n)=n+1，下面四个命题为真的是（）。A.f是满射；B.f是单射；C.f是双射的；D.f非单射非满射．B谓词公式x(P(x)∨yR(y))→Q(x)中的变元x是（）。A．自由出现的；B．约束出现的；C．既不是自由出现也不是约束出现；D．既是自由出现也是约束出现．D下列不是谓词公式的是（）。A．x∧y∨P（x，y）；B．x(P(x)→x(Q(x)∧A(x，y)))；C．xP（x）→R（y）；D．xP（x）∧Q（y，z）．A下列句子为命题的是（）。A．全体起立!B．x=0；C．你会抽烟吗？D．张三生于1886年的春天．D下列命题正确的是（）。A．{}=；B．{}=；C．{a}{a，b，c}；D．{a，b，c}．A下列命题正确的是（）。A．{l，2}{{1，2}，{l，2，3}，1}；B．{1，2}{1，{l，2}，{l，2，3}，2}；C．{1，2}{{1}，{2}，{1，2}}；D．{1，2}∈{1，2，{2}，{l，2，3}}．B下列图形是（）。A．完全图；B．哈密顿图；C．欧拉图；D．平面图．B下列图中不是平面图的为（）。A.．B．C．D．C下列为公式的是（）。A．srq；B．)((srp；C．)()(pqqp；D．qprs．C下列语句中，（）是命题。A．下午有会吗？B．这朵花多好看呀！C．2是偶数；D．请把门关上!C下列语句中是假命题的是（）。A．5是素数；B．太阳从东方升起；C．1235；D．正在下雨呢！C下列语句中是命题的是（）。A．天气真暖和呀！B．请别激动！C．还记得我吗？D．地球是运动的．D下面既是哈密顿图又是欧拉图的是（）。B一个连通图G具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点（）。A．G没有奇数度的结点；B．G有1个奇数度的结点；C．G有2个奇数度的结点；D．G没有或有2个奇数度的结点．A在自然数集合上，下列运算满足结合律的是（）。A．2ababB．min{,}ababC．ababD．ababB二、填空题令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为_______。p∧┐q设p：明天上午8点下雨，q：明天上午8点下雪，r：我去学校，则命题“如果明天上午8点不下雨并且也不下雪，我就去学校”可符号化为。rqp)(设)(xF：x是偶数，)(xG：x是素数，则命题“存在着偶素数”可符号化为_______。))()((xGxFxn个顶点的无向完全图记为nK，当n满足条件__________时,nK不是平面图。4n设p：我们勤奋，q：我们好学，r：我们取得好成绩，则命题“我们只要勤奋好学，就能取得好成绩”符号化为。rqp)(设A（x）：x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为_______。))()((xBxAx或))()((xBxAx设G是连通的平面图，已知G中有6个顶点，8条边，则G有_______个面。4设P：他聪明，Q：他用功，则命题“他虽聪明,但不用功”可符号化为_______。P∧Q设集合}3,2,1{A，}5,4,3{B，则BA。}2,1{设集合},,{cbaA，},,{dcbB，则BA。},{da设集合}2,1{A，则A的幂集)(AP。}}2,1{},2{},1{,{设集合}}2{,1{A，则A的幂集)(AP。答案：}}}2{,1{}},2{{},1{,{设xxM:)(是人，xxP:)(要吃饭，则命题“人都是要吃饭的”可符号化为_______。答案：))()((xPxMx设xxM:)(是跳高运动员，a：小张，则命题“小张不是跳高运动员”可符号化为_______。)(aM无向图G=V,E如右所示，则图G的最大度数Δ(G)=_______。4无向图G中有16条边，且每个结点的度数都是2，则G的结点数是_______个。16无向完全图5K中有________条边。10已知关系},,,,,{1dbbaaaR,},,,,,,,{2bcdbcbdaR,则12RR=_______。答案：},,,{daca已知关系},,,,,{dbbaaaR,则2R=。},,,,,{dabaaa已知关系},,,,,{1cbcabaR，},,,{2aabaR，则21RR=。答案：},,,{baca已知关系},,,,,,,{bcdbcbdaR,则3R=。答案：},,,,,{dbcbbc三、计算题构造命题公式（PQ）Q的真值表，并判断其类型。解：真值表PQPQ（PQ）（PQ）Q00100011001001011100因此公式（PQ）Q为矛盾式．对某单位的100名员工进行调查，结果发现他们喜欢看球赛、电影和戏剧．其中58人喜欢看球赛，52人喜欢看电影，38人喜欢看戏剧，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，求只喜欢看电影的有多少人。解：设喜欢看球赛、电影和戏剧的人的集合分别为A,B,C，那么A=58，B=52，C=38，AC=18，BC=16,CBA=12，只喜欢看电影的有22人．构造命题公式（PQ）∧R的真值表，并判断其类型。解：真值表为：PQRPQR（PQ）∧R000001010011100101111100101010101000ABC261422612416110111111010公式（PQ）∧R为可满足式．构造命题公式rqp的真值表，并判断其类型。解：真值表为rqpqprqp0000010100111001011101110000001110101011公式rqp为可满足式．集合}3,2,1{A上的关系}3,3,2,3,1,3,2,2,1,2,2,1,1,1{R，试写出关系矩阵M，并讨论R的性质。解：关系矩阵111011011M，R是自反的和传递的．集合}3,2,1{A上的关系}3,3,3,2,3,1,2,1{R，试写出关系矩阵M，并讨论R的性质。解：关系矩阵100100110M，R具有反对称性和传递性．集合}3,2,1{A上的关系}3,3,1,3,2,2,1,2,1,1{R，试写出关系矩阵M，并讨论R的性质。解：关系矩阵101011001M，R是自反的，反对称的和传递的．集合}4,3,2,1{A上的关系}4,4,3,4,4,3,3,3,1,3,2,2,3,1,1,1{R，试写出关系矩阵M，并讨论R的性质。解：关系矩阵1100110100100101M，R具有自反性和对称性．今有工人甲、乙、丙去完成三项任务a、b、c．已知甲能胜任a、b、c三项任务；乙能胜任a、b二项任务；丙能胜任b、c二项任务．试给出一种方案，使每个工人各去完成一项他们能胜任的任务。解：工人与任务的胜任关系的二部图为：甲乙丙abc一种方案是：甲完成a，乙完成b，丙完成c．（注：本题答案不唯一，还可以给出其它的方案．）某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，试求两次考试都得优的学生人数。解：设两次考试都得优的学生人数为x人，由下列文氏图可知17+(26-x)+x+(21-x)=50，解得：x=14，两次考试都得优的学生人数为14人．某大学计算机专业的80名学生在期末考试中，Pascal语言课有58人达到优秀，数据结构课有30人达到优秀，离散数学课有25人达到优秀．并且，Pascal语言和数据结构两门课都达到优秀的有20人，Pascal语言和离散数学两门课都达到优秀的有19人，数据结构和1726-xx21-x离散数学两门课都达到优秀的有17人，还有10人一门优秀都没得到．求三门课都达到优秀的人数。解：设期末考试中Pascal语言课、数据结构课、离散数学课达到优秀的学生集合分别为A,B,C，那么A=58，B=30，C=25，AB=20，AC=19，BC=17由题意，至少有一门课达到优秀的学生人数为CBA=80-)(~CBA=70．于是，三门课都达到优秀的学生数为：CBA=CBA-(A+B+C-AB-AC-BC)=70-58-30-25+20+19+17=13．求图中A到其余各顶点的最短路径的权（要求列表）。B5D12A433F35C1E解：用用标号法解题过程如下BCDEF01311*36423*64364*946*858*13648求图中A点到其余各顶点的最短路径的权（要求列表）。B7C12A253D46E1F解：用用标号法解题过程如下：BCDEF01411*836283*437104*47*959*17934求下面所示带权图中顶点A到其余各顶点的最短路径的权（要求列表）。112256248ABCDEF解：用用标号法解题过程如下：BCDEF0812131*7223732*33*73453*55*31532求下面所示带权图中顶点A到其余各顶点的最短路径的权（要求列表）。解：用用标号法解题过程如下BCDEF042132*101123*81138*1014410*13513*142589263ABCDEF3281013设}4,3,2,1{A，定义A上的二元运算*如下：对Ayx,，5mod)(xyyx（表示xy除以5的余数），试求*的运算表。解：运算表如下：123442413331422432114321设}10,5,2,1{A，定义A上的二元运算*如下：对Ayx,，yxyx与的最大公约数，试给出*的运算表。解：运算表如下：105211055115212121111110521设}10,5,2,1{A，定义A上的二元运算*如下：对Ayx,，yxyx与的最小公倍数，试给出*的运算表。解：运算表如下：10101010101051055101022210521110521设}1,0{A，试给出A上运算的运算表。解：运算表如下10111010设个体域为{1，2}，1)1(P，0)2(P，2a，求公式)()(xxPaP的真值。解：))2()1(()2()()(PPPxxPaP110)01(0．设个体域为{1，2}，0)1(P，1)2(P，1a，求公式)()(aPxxP的真值．解：)()(aPxxP1000)10()1())2()1((