离散数学

Forpersonaluseonlyinstudyandresearch;notforcommercialuse蚄离散数学复习题蚁一.有两个小题袇1．分别说明联结词、∧、∨、→和的名称，再分别说明它们在自然语言中表示什么含义。膇解：(1)叫做否定。(2)∧叫做合取。(3)∨叫做析取。莁(4)叫做蕴涵。(5)叫做等价。螀“”表示“…不成立”，“不…”。芆“∧”表示“并且”、“不但…而且...”、“既…又...”等。蚃“∨”表示“或者”，是可兼取的或。蒃“”表示如果…，则…；只要…，就…；只有…,才…；仅当…。袈“”表示“当且仅当”、“充分且必要”。蚆2．分别列出P、PQ、PQ、PQ、PQ的真值表(填下表)。莄P薄Q芀P荿PQ膄PQ莁PQ荿PQ袈袄莃螁芈蚅蒄衿蚇莅芁膂肇肆芃莀薆袆莄葿艿薆膂螁虿莇膃罿肈解：袃P芄Q节P蒇PQ薃PQ肂PQ莀PQ羇F芄F膃T薈F莆F肄T膄T袁F螆T螅T羂F罿T葿T薅F肃T莂F袈F芅F袀T蒀F莈F肆T袂T薈F螇T螆T羃T羁T膆二.将下面命题写成符号表达式。(3,4题要使用句后给定的谓词。)蒆1.如果小张去，则小王与小李都不去，否则小王与小李不都去。螁解：设P：小张去。Q：小王去。R：小李去。聿此命题的表达式为：蚆(P→(Q∧R))∧(P→(Q∧R))芇2.我们不能既划船又跑步。螂解：令P:我们划船。Q:我们跑步。蒂此命题的表达式为(P∧Q)荿3.有些运动员是大学生。(L(x):x是运动员，S(x):x是大学生。)螃解：x(L(x)∧S(x))袃4.每个运动员都钦佩一些教练。薀(L(x):x是运动员，A(x,y):x钦佩y，J(x):x是教练。)蝿解：x(L(x)→y(J(y)∧A(x,y)))蒄三.有三个问题蚁1.先说明什么叫永真式(也叫重言式)。蚈解：A(P1,P2,…,Pn)是含有命题变元P1,P2,…,Pn的命题公式，如不论对P1,P2,…,Pn作任何指派，都使得A(P1,P2,…,Pn)为真，则称之为重言式，也称之为永真式。膈2.指出下面的命题公式中哪些是永真式(只写题号即可)。芄(1).(P∨Q)→P(2).P→(P∨Q)螂(3).(P∧(P→Q))→Q(4).(P∧Q)→Q肁解:(2),(3),(4)为永真式。薇3.然后对上面的永真式任选其中一个给予证明(方法不限)。羄证明(4).(P∧Q)→Q螄设前件(P∧Q)为真，则得Q为真。所以(P∧Q)→Q是永真式。腿四.写出命题公式(Q→P)→Q的主合取范式。（要求有解题过程）肇解：蚅方法1：等价变换薁(QP)Q薁(Q∨P)∨Q(去)蒆(Q∧P)∨Q(摩根定律)蒅Q(吸收律)蚂(P∧P)∨Q（互补、同一律）蚀(P∨Q)∧(P∨Q)(分配律)腿方法2：真值表法膅先列(QP)Q的真值表如下：蚄P螈Q蕿P羆QP蒁(QP)Q膀F羈F蚆T薂T艿F蒈F蒇T蚄T蚁T袇T膇T莁F螀F芆T蚃F蒃T袈T蚆F莄F薄T芀从真值表看出，该命题公式的主合取范式含有大项M0和M2，即(P∨Q)和荿(P∨Q)。于是此命题公式的主合取范式为：膄(QP)Q(P∨Q)∧(P∨Q)莁五.用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。荿xP(x),x(Q(x)R(x)),x(P(x)R(x))xQ(x)袈解：⑴xP(x)P袄⑵P(a)ES⑴莃⑶x(P(x)R(x))P螁⑷P(a)R(a)US⑶芈⑸R(a)T⑵⑷I蚅⑹x(Q(x)R(x))P蒄⑺Q(a)R(a)US⑹衿⑻Q(a)T⑸⑺I蚇⑼xQ((x)EG⑻莅六.用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。芁xC(x),x(A(x)B(x)),x(B(x)C(x))xA(x)膂解：⑴x(A(x)B(x))P肇⑵A(a)B(a)ES⑴肆⑶xC(x)P芃⑷C(a)US⑶莀⑸x(B(x)→C(x))P薆⑹B(a)→C(a)US⑸袆⑺B(a)T⑷⑹I莄⑻A(a)T⑵⑺I葿⑼xA(x))EG⑻艿七.令集合A={1,{1}},B={1}，P(A)表示A的幂集。薆1.判断下面命题的真值。并说明原因，否则不给分。膂(1)B∈A,(2)P(B)P(A)螁(3){Φ}P(A)(4){{1}}∈P(B)虿解：P(A)＝{Φ,{1},{{1}},{1,{1}}莇P(B)＝{Φ,{1}}膃⑴：真值为T；因为A={1,{1}},B={1},B是A中一个元素，所以B∈A。罿⑵：真值为T；因为P(B)＝{Φ,{1}}，P(B)中两个元素Φ和{1}都属于P(A),所以P(B)P(A)。肈⑶：真值为T；因为集合{Φ}中只有一个元素Φ，而P(A)中也有元素Φ，所以{Φ}P(A)。袃⑷：真值为F。因为{{1}}不是P(B)中元素，故真值为F。芄2.分别计算:（注意：要求要有计算过程，不能直接写出计算结果！）节(1)A×P(B)蒇(2)A⊕B薃(3)P(A)－P(B)肂解：A={1,{1}},B={1}，莀⑴A×P(B)＝{1,{1}}×{Φ,{1}}羇＝{1,Φ,1,{1},{1},Φ,{1},{1}}芄⑵A⊕B＝(AB)－(AB)膃=({1,{1}}{1})－({1,{1}}{1})＝{1,{1}}－{1}＝{{1}}。薈⑶P(A)－P(B)＝{Φ,{1},{{1}},{1,{1}}－{Φ,{1}}莆＝{{{1}},{1,{1}}}肄八.令全集E={1,2},A={1},P(A)表示集合A的幂集。膄（注意：要求要有计算过程，不能直接写出计算结果！）袁1.指出P(E)和P(A)各有多少个元素。即求|P(E)|和|P(A)|.螆解：因为P(E)＝{Φ,{1},{2},{1,2}}所以P(E)有4个元素。即|P(E)|＝4。螅P(A)＝{Φ,{1}}所以P(A)有2个元素。即|P(A)|＝2。羂2.计算～AE罿解：因为～A＝E－A={1,2}-{1}={2}葿～AE＝{2}{1,2}＝({2}{1,2})－({2}{1,2})＝{1,2}－{2}＝{1}薅九.令集合A={1},B＝{1,2},P(A)表示集合A的幂集。肃（注意：要求要有计算过程，不能直接写出计算结果！）莂1．计算A与B的对称差AB。袈解：AB＝(AB)－(AB)芅＝({1}{1,2})－({1}{1,2})＝{1,2}－{1}＝{2}袀2．计算P(B)－P(A)蒀解：P(B)－P(A)＝P({1,2})－P({1})莈＝{Φ,{1},{2},{1,2}}－{Φ,{1}}＝{{2},{1,2}}肆十.给定集合A={1,2,3},定义A上的关系如下：袂R={1,1,1,2,1,3,2,2,3,3}薈S={1,1,1,2,2,1,2,2,3,3}螇T={1,2,2,3,3,1}螆M=Ф(空关系)羃N=A×A(完全关系（全域关系）)羁1.写出关系R的矩阵；再画出上述各个关系的有向图。膆解：关系R的矩阵如下：蒆下面是几个关系的有向图：螁袀2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：葿莇自反的肅反自反的羁对称的蚈反对称的螆传递的螅R羃羀芆薆螀肈S蚅羂袁芇肅螂T袃蕿螈蒃蚀蚈M膇芃螁肀蚇聿。蚆。芇。螂1蒂3荿2螃M袃S薀。蝿。蒄。蚁1蚈3膈2芄。螂。肁。薇1羄3螄2腿R肇。蚅。薁1薁3蒆2蒅N羁。聿。蒈。薄。肂1膇3羈2芅T001010111MR羄N螃膈肆螄薀薁解：蒅蒄自反的蚂反自反的虿对称的袅反对称的膅传递的螃R螇√××√√S√×√×√T×√×√×M×√√√√N√×√×√3.上述五个关系中，哪些是等价关系？哪些是偏序关系？哪些是A上函数？对等价关系，写出此等价关系的各个等价类。对函数，指出它的类型。解：S和N是等价关系。R是偏序关系。A/S={{1,2},{3}}A/N={{1,2,3}}T是函数。是双射的。4.分别求复合关系RoS以及R的逆关系Rc。解：RoS＝{1,1,1,2,1,3,2,1,2,2,3,3}Rc＝{1,1,2,1,3,1,2,2,3,3}十一.R是实数集合，给出R上的运算：+、－、×、max、min、|x-y|,分别表示加法、减法、乘法、两个数中取最大的、两个数中取最小的、x-y的绝对值运算。1.判断各个运算性质。用“√”表示“是”，用“×”表示“否”，填下表：+－×maxmin|x-y|有交换性有结合性有幂等性有幺元有零元2.分别指出R对上面哪些运算是半群、独异点和群。3.如果有群，请说明它为什么是群。解:1.+－×maxmin|x-y|有交换性√×√√√√有结合性√×√√√×有幂等性×××√√×有幺元√×√×××有零元××√×××2.构成半群的有：R,＋，R,×，R,max,R,min.构成独异点的有：R,＋，R,×。构成群的有：R,＋。3.R,＋是群的理由：(1)＋在实数集合内满足封闭性。即任何a,b∈R,有ａ＋ｂ∈R。(2)＋是可结合的。(3)0是＋运算的幺元。任何a∈R,有0+a=a=a+0.(4)任何实数a,都有逆元－a∈R,使得(-a)+a=0=a+(-a).所以R,＋是群。十二.设I是整数集合，在I上定义二元运算*如下：对于任何a,b∈Ia*b=a+b＋4求证I,*是个交换群.解：1.证明封闭性:任取a,bI因a＋b＋4I,a*bI.所以*满足封闭性。2.证明交换性:任取a,bI,因为a*b=a＋b＋4=b＋a＋4=b*a.所以*满足交换性。3.证明结合性,任取a,b,cI,(a*b)*c=(a＋b＋4)＋c＋4=a＋b＋4＋c＋4=a＋(b＋c＋4)＋4=a*(b*c).所以*满足结合性。4.证明-4是幺元,任取aI,因为(-4)I,使得a*(-4)=a＋4＋(-4)=a(-4)*a=(-4)+a+4=a，所以-4是幺元。5.证明有逆元,任取aI,因为-8-aI,使得a*(-8-a)=a+(-8-a)+4=-4(-8-a)*a=(-8-a)+a+4=-4所以-8-a是a的逆元。综上所述I,*是个交换群。十三．有三个小题。1.名词解释无向图结点的度有向图结点的出度，入度平行边简单图无向完全图Kn路，回路迹，闭迹通路，圈无向连通图欧拉图汉密尔顿图树根树m叉树完全m叉树解：无向图结点v的度:G是个无向图,v∈V(G),结点v所关联边数,称之为结点v的度.记作deg(v).(或d(v)).有向图结点的出度和入度:G=V,E是有向图,v∈Vv的出度:从结点v射出的边数.v的入度:射入结点v的边数.平行边:在两个结点之间关联的多条边，这些边是平行边.简单图:不含有环和平行边的图.无向完全图Kn：G是个简单图,如果每对不同结点之间都有边相连，则称G是个无向完全图。如果G有n个结点,则记作Kn。路:给定图G=V,E，设v0,v1,v2,,…,vn∈V,e1,e2,,…,en∈E其中ei是关联vi-1,vi的边,则称结点和边的交叉序列v0e1v1e2v2…envn是连接v0到vn的路.回路:如果一条路的起点和终点是一个结点,则称此路是一个回路.迹：如果一条路中,所有边都不同,则称此路为迹.闭迹：如果一条回路中,所有边都不同,则称此回路为闭迹.通路：如果一条路中,所有结点都不同,则称此路为通路.圈：如果一条回路中,除起点和终点外,其余结点都不同,则称此回路为圈.无向连通图:如果一个无向图G只有一个连通分支(W(G)=1),则称G是连通图.欧拉图：在无孤立结点的图G中,若存在一条回路,它经过图中每条边一次且仅一次,称此图为欧拉图。汉密尔顿图：图中有通过每个结点恰好一次的回路。(具有汉密尔顿回路)的图.称之为汉密尔顿图。树：一个连通无回路的无向图T，称之为树。根树: