离散数学复习题 (2)

1、for personal use only in study and research; not for commercial use离散数学复习题一. 有两个小题1分别说明联结词、和的名称，再分别说明它们在自然语言中表示什么含义。解：(1) 叫做否定 。 (2) 叫做合取。(3) 叫做析取。 (4) 叫做蕴涵。 (5) 叫做等价。“”表示“不成立”，“不”。“”表示“并且”、“不但而且.”、“既又 .”等。“”表示“或者”， 是可兼取的或。“”表示 如果 ，则 ；只要 ，就 ； 只有 , 才； 仅当 。“”表示“当且仅当”、“充分且必要”。2分别列出p、pq、pq、pq、pq的真值表(填下表

2、)。pqppqpqpqpq解：pqppqpqpqpqfftffttfttfttftffftffttftttt二. 将下面命题写成符号表达式。(3,4题要使用句后给定的谓词。)1.如果小张去，则小王与小李都不去，否则小王与小李不都去。解：设p：小张去。q：小王去。r：小李去。 此命题的表达式为： (p(qr)(p(qr)2.我们不能既划船又跑步。解：令 p:我们划船。q:我们跑步。 此命题的表达式为(pq) 3.有些运动员是大学生。(l(x): x是运动员，s(x): x是大学生。)解：$x(l(x)s(x)4.每个运动员都钦佩一些教练。 ( l(x):x是运动员，a(x,y):x钦佩y，j(x

3、):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). (pq)p (2). p(pq) (3). (p(pq)q (4). (pq)q 解:(2),(3),(4)为永真式。3.然后对上面的永真式任选其中一个给予证明(方法不限)。证明 (4). (pq)q 设前件(pq)为真，则得q为真。所以(pq

4、)q是永真式。 四. 写出命题公式 (qp)q 的主合取范式。（要求有解题过程）解： 方法1：等价变换 (qp)q (qp)q ( 去 ) (qp)q ( 摩根定律 ) q ( 吸收律 ) (pp)q （互补、同一律 ） (pq)(pq) ( 分配律 )方法2：真值表法先列(qp)q的真值表如下：pqpqp(qp)qffttfftttttfftfttfft从真值表看出，该命题公式的主合取范式含有大项m0和m2，即(pq)和(pq)。于是此命题公式的主合取范式为：(qp)q (pq)(pq)五. 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 $xp(x), x(q(

5、x)r(x), x(p(x)r(x) $xq(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 $xq(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

6、七. 令集合a=1,1,b=1，p(a)表示a的幂集。1.判断下面命题的真值。并说明原因，否则不给分。 (1) ba, (2) p(b)p(a) (3) p(a) (4) 1p(b)解：p(a),1,1, 1,1 p(b),1：真值为t；因为a=1,1, b=1, b是a中一个元素，所以ba。：真值为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) ap(b) (2)

7、 ab (3) p(a)p(b)解： a=1,1, b=1， ap(b)1,1 ,1 , ab(ab)(ab) =(1,11) (1,1 1)1,111。 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. 计算ae解：因为aea=1,2-1=2 ae2 1,2(21

8、,2)(21,2)1,221 九. 令集合a=1,b1,2, p(a)表示集合a的幂集。（注意：要求要有计算过程，不能直接写出计算结果！） 1计算a与b的对称差ab。解：ab(ab)(ab) (11,2)(11,2)1,212 2计算 p(b)p(a)解： p(b)p(a)p(1,2)p(1) ,1,2,1,2,12,1,2 十. 给定集合a=1,2,3,定义a上的关系如下： r=, s=, t=, m=(空关系) n=aa(完全关系（全域关系）) 1.写出关系r的矩阵；再画出上述各个关系的有向图。解：关系r的矩阵如下：下面是几个关系的有向图：聿。蚆。芇。螂1蒂3荿2螃m袃s薀。蝿。蒄。蚁1蚈

9、3膈2芄。螂。肁。薇1羄3螄2腿r肇。蚅。薁1薁3蒆2蒅n羁。聿。蒈。薄。肂1膇3羈2芅t2.判断各个关系性质。用“”表示“是”，用“”表示“否”，填下表：自反的反自反的对称的反对称的传递的rstmn解：自反的反自反的对称的反对称的传递的rstmn3.上述五个关系中，哪些是等价关系？哪些是偏序关系？哪些是a上函数？对等价关系，写出此等价关系的各个等价类。 对函数，指出它的类型。解：s和n是等价关系。 r是偏序关系。 a/s=1,2,3 a/n=1,2,3 t是函数。是双射的。4.分别求复合关系 ros 以及r的逆关系rc。解：ros, rc,十一. r是实数集合，给出r上的运算：+、max、m

10、in、|x-y|,分别表示加法、减法、乘法、两个数中取最大的、两个数中取最小的、x-y的绝对值运算。1. 判断各个运算性质。用“”表示“是”，用“”表示“否”，填下表：+maxmin|x-y|有交换性有结合性有幂等性有幺元有零元2.分别指出r对上面哪些运算是半群、独异点和群。3.如果有群，请说明它为什么是群。解:1.+maxmin|x-y|有交换性有结合性有幂等性有幺元有零元2. 构成半群的有：， ， , . 构成独异点的有： ， 。 构成群的有： 。3. 是群的理由： (1) 在实数集合内满足封闭性。即 任何a,br, 有r。 (2) 是可结合的。 (3) 0是运算的幺元。任何ar, 有0+

11、a=a=a+0 . (4) 任何实数a, 都有逆元ar , 使得 (-a)+a=0=a+(-a) .所以是群。十二. 设i是整数集合，在i上定义二元运算*如下： 对于任何a,bi a*b=a+b4 求证是个交换群.解：1.证明封闭性: 任取a,bi 因ab4 i , a*bi. 所以*满足封闭性。2.证明交换性: 任取a,bi, 因为a*b=ab4=ba4=b*a.所以*满足交换性。3.证明结合性, 任取a,b,ci, (a*b)*c=(ab4)c4=ab4c4 =a(bc4)4=a*(b*c). 所以*满足结合性。4.证明-4是幺元, 任取ai, 因为(-4)i, 使得 a* (-4)=a4

12、(-4)=a (-4) *a=(-4)+a+4=a，所以-4是幺元。5.证明有逆元, 任取ai, 因为-8-ai ,使得 a* (-8-a)= a+(-8-a)+4=-4 (-8-a) *a=(-8-a)+a+4=-4 所以-8-a是a的逆元。综上所述 是个交换群。十三 有三个小题。1.名词解释无向图结点的度有向图结点的出度，入度平行边简单图无向完全图kn路，回路迹，闭迹通路，圈无向连通图欧拉图汉密尔顿图树根树m叉树完全m叉树解：无向图结点v的度:g是个无向图, vv(g), 结点v所关联边数,称之为结点v的度. 记作 deg(v).(或d(v).有向图结点的出度和入度: g=是有向图,vv

13、v的出度: 从结点v射出的边数. v的入度: 射入结点v的边数. 平行边:在两个结点之间关联的多条边，这些边是平行边. 简单图:不含有环和平行边的图.无向完全图kn：g是个简单图, 如果每对不同结点之间都有边相连，则称g是个无向完全图。如果g有n个结点, 则记作kn。路: 给定图g=，设v0 ,v1,v2,vnv, e1,e2,ene 其中ei是关联vi-1 ,vi的边, 则称结点和边的交叉序列v0 e1v1 e2v2envn是连接v0到vn的路. 回路:如果一条路的起点和终点是一个结点,则称此路是一个回路. 迹： 如果一条路中,所有边都不同,则称此路为迹.闭迹：如果一条回路中,所有边都不同,

14、则称此回路为闭迹.通路：如果一条路中,所有结点都不同,则称此路为通路.圈： 如果一条回路中,除起点和终点外,其余结点都不同,则称此回路为圈.无向连通图: 如果一个无向图g只有一个连通分支(w(g)=1),则称g是连通图.欧拉图：在无孤立结点的图g中,若存在一条回路,它经过图中每条边一次且仅一次,称此图为欧拉图。汉密尔顿图：图中有通过每个结点恰好一次的回路。(具有汉密尔顿回路)的图.称之为汉密尔顿图。树：一个连通无回路的无向图t，称之为树。根树:如果一棵有向树,恰有一个结点的入度为0,其余所有结点的入度均为1,则称此树为根树. m叉树:在根树中,如果每个结点的出度最大是m, 则称此树是m叉树.完

15、全m叉树:在根树中,如果每个结点的出度都是m或者等于0, 则称此树是完全m叉树.2给定图的集合g=a,b,c,d,e,f,h,k,m,n,r,s,t,v,w,x,y,其中各个图如下所示，请指出这些图中哪些是彼此同构的。2解:同构的有:ar ；bd；cmsw ；efty；h ；kx ； vn。3.请画出五个具有五个结点的无向图，使之分别满足： (1) 此图既是欧拉图也是汉密尔顿图。 (2) 此图是欧拉图但不是汉密尔顿图。 (3) 此图是汉密尔顿图但不是欧拉图 。(4) 此图是完全图k5。(5) 此图是棵树解： (1) (2) (3) (4) (5)十四. 有三个小题 1. 指出下面各个图中哪些是

16、彼此同构的.abcdfghie解： a、h、i 同构； b、d同构； c、g同构； e、f同构。2.完全二叉树中，设边数为e，叶结点数为t，求证 e=2(t-1)。解：由完全m叉树公式 (m1)i=t1 这里m2，得 (21)i=t1, i=t1, t中总的结点数v为: v=it =(t1)t=2t1，于是t的边数e：e=v1= 2t11= 2t2=2(t1)3根据给定一组权值:1,6,2,5,3,4,1,6,2 画出一棵最优完全二叉树。要求有画图的过程。解 权值排序并画图：1,1,2,2,3,4,5,6,62,2,2,3,4,5,6,62,3,4,4,5,6,64,4,5,5,6,65, 5,6,6,86,6,8,108,10,1212,1830321121851030841224665仅供个人用于学习、研究；不得用于商业用途。