离散数学复习题全

1、离散数学复习资料一、填空.命题“对于任意给定的正实数，都存在比它大的实数”令F(x)： X为实数，L(x，y)：x y则命题的逻辑谓词公式为 。.设p：王大力是100米冠军，q：王大力是500米冠军，在命题逻辑中，命题“王大力不 但是100米冠军，而且是 500米冠军”的符号化形式为 。命题“存在一个人不但是 100米冠军，而且是 500米冠军”的符号化形式为 。.选择合适的论域和谓词表达集合A= 直角坐标系中，单位元(不包括单位圆周)的点集”则A= o.设P (x)： x是素数，E(x)： x是偶数，O(x)： x是奇数N (x,y)： x可以整数y。则谓词x(P(x) y(O(y) N(y

2、, x)的自然语言是对于任意一个素数都存在一个奇数使该素数都能被整除。.设个体域是a, b,谓词公式(x) P(x) ( x)P(x)写成不含量词的形式是 。.谓词 x y( z(P(x,z) P(y,z) uQ(x, y,u)的前束范式为 。.命题公式A P ( P (Q ( Q R)的主合取范式为,其编码表示为。. 设E为全集，称为A的绝对补，记作A,且(A) =，E =,.=。.设 A=2,5,6,B 2,3,4,C1 ,3,4,则 A-B=, AB= ,AxC =。.设 A a,b,c考虑下列子集 Si a,b,b,c , S2 a, a,b,a,c,. S3a,b,c, S4 a,b

3、,c, S5 a,b,c , S6 a,a,c.则A的覆盖有 , A的划分有 。.设 M x1 x 12,x被2整除，x Z , N x1 x 12,x被3整除，x Z,则M N , M N o.设人=, , B=,恻 A B=, A B=。. A=1, 2, 3, 4, 5, 6, A上二元关系T x, y | x y是素数，则用列举法 T= ;T的关系图为, T具有 性质。17.偏序集 A, R的哈斯图为17.偏序集 A, R的哈斯图为d.设A x|x 2n , n N,定义A上的二元运算为普通乘法、除法和加法，则代数系统A,*中运算*关于 运算具有封闭性。. A, B, C表示三个集合，

4、文图中阴影部分的集合表达式为 。20.0 10 1设图 G = V, 20.0 10 1设图 G = , V Vi,V2,V3,V4的邻接矩阵1,则V1的入度0110 0 0deg (Vi)=, V4的出度deg (V4) =,从V2到V4的长度为2的路径有 条。.结点数n ( n 3)的简单连通平面图的边数为m,则m与n的关系为 m=3n-6。.设f, g是自然数集N上的函数x N, f (x) x 1 , g(x) 2x,则f g(x) Z3上定义+3如下:.设I是整数集合，Z3上定义+3如下:3 j (i j)mod 3,则+3的运算表为 ； 是否构成群 24.集合 24.集合 S=”

5、,3, 丫，8 上的二元运算*为*a3丫8a8a3丫3a3丫8丫3丫Y丫8a8Y8那么，代数系统S, *中的幺元是 , “的逆元是 25.设 a,b,c, * 为代数系统，*运算如下:*abcaabcbbaccccc则它的幺元为设 A=a, b, c, A 上设 A=a, b, c, A 上.兀关系 R= , ，则 s (R)=27 .28.设集合X=1,2,3,27 .28.设集合X=1,2,3,下列关系中不是等价的。设 A=, , B=,则 A B =29.30.设G是n阶完全图，则G的边数m=31.设A=a, b,c,d,其上偏序关系 R的哈斯图如右图所示：则29.30.设G是n阶完全图

6、，则G的边数m=31.设A=a, b,c,d,其上偏序关系 R的哈斯图如右图所示：则R=。32.n阶完全图Kn的边数为33.结点数n ( n 3)的简单连通平面图的边数为m,则m与n的关系为34.O的补图为,oA= ,B= ,C= ,D= ,设 X 1,2,3,4, R 1,2，2,4，3,3 ，则(R尸；s (R)= ;t(R) =.有向图 I中从vi到V2长度为2的通路有 条。.设G为9阶无向图，每个结点度数不是5就是6,则G中至少有 个5度结点。. n阶完全图结点 v的度数d(v) =n-1。二、证明.不构造真值表证明蕴涵式.(Q (PP) (R(R(P P)R Q.证明ABC D ,

7、DEFA F.证明(PA Q)V(PAQ) P.证明(P QR)(P Q)R.证明 x(P(x) Q(x) xP(x) xQ(x).证明 x(P(x)Q(x) xP(x)xQ(x).用推理规则证明下式：.前提：(x)P(x) x(P(x) Q(x)R(x) ,( x)P(x),( x)Q(x).结论：(x)( y)(P(x) R(y).设论域 D=a , b , c,求证：xA(x) xB(x) x(A(x) B(x)。.设g f是复合函数，如果 g f满射，则g也是满射。.假定f : AB,g : B C,且gf是一个满射，g是个入射，则f是满射。.用反证法证明(P Q)(P R)(Q S)

8、 S Ro.设 I , + 一个群，设 Ie= x|x=2n , nCI ,证明 Ie, + 是 I , + 的一个子群。三、按要求解答.将谓词公式( x)P(x) ( y)Q(y)( y)R(y)化为前束析取范式与前束合取范式。.用推理规则论证：如果今天是星期六，我们就要到颐和园或圆明园玩，如果颐和园游人太 多，我们就不去颐和园玩。今天是星期六，颐和园游人太多，所以，我们去圆明园玩。.符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。.用推理规则论证：或者逻辑难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑 并不难学。因此，如果许多学生喜欢逻辑，那么

9、数学并不难学。.设有下列情况，用推理规则论证结论是否有效(a)或者天晴，或者下雨。(b)如果天晴,我去看电影。(c)如果我去看电影，我就不看书。结论：如果我在看书则天在下雨。.符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子” 并推证其结论。.给定3个命题：P:北京比天津人口多； Q: 2大于1; R: 15是素数。求复合命题：(Q R) (P R)的真值。.将x( ( yP(x, y)( zQ(z) R(x)化为与其等价的前束范式。.把公式 x P x x Q x转化为前束范式.求(Q P) ( P Q)的主合取范式。.求(ABC) (A(BC)的主析取范式与主

10、合取范式。.求(PVQ)R的主析取范式与主合取范式。.设命题Ai, A2的真值为1, A3, A4真值为0,求命题. (Ai (A2(A3A)(A2A4)的真值。. 一 1. 一一 .求集合Anx 0 x (n 1,2,3,)的并与父。n.设*=1,2,3,4,5, X上的关系 R= , , , , ,求 R 的传递闭 包 t (R)。.设集合X a, b, c, d上的关系R a,b , b,a , b,c , c,c 。求R的传递闭包t(R)。.在实数平面上，画出关系 R x,y xy20 xy20,并判定关系的特 殊性质。.设 X= a, b, c, d , R是 X上的二元关系,R=,

11、 , , , 设$=1 , 2,3,4, 6,8 , 12,24“ ”为S上整除关系，问：（1）偏序集 S , 的哈斯图如何（2）偏序集（1）画出R的关系图。（2）写出R的关系矩阵。（3）说明R的性质. A=a,b,c,d, R=,为A上的关系，利用矩阵乘法求R的传递闭包，并画出t （R）的关系图。. S, 的极小元、最小元、极大元、最大元是什么.集合 A 2,3,6,12,24,36上的偏序关系为整除关系。设B 6,12,C 2,3,6,试画出哈斯图，并求 A, B, C的最大元素、极大元素、下界、上确界。.对于实数集合R,在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”

12、或 “N”。MaxMin+可结合性可交换性存在幺兀存在零兀.设 B4=e , a , b , ab ,运算 *如下表,*eababeeababaaeabbbbabeaababbae则是一个群（称作 Klein四元群）。.设 S = R - -1 （R 为实数集），a b a b ab。(1)说明S，是否构成群；(2)在S中解方程2 x 3 7 o.设X =1,2,3,4, R是X上的二元关系，. R= 1,1 , 3,1 , 1 ,3 , 3 ,3 , 3,2 , 4,3 , 4,1 , 4 2 , 1 ,2 (1)画出R的关系图。写出 R的关系矩阵。说明 R是否是自反、反自反、对称、传递的。

13、.设I是负整数集合，定义二个双射函数f、g ,f :I I f x x 1,1 ,2,2 ,g: I N g x x 1 1,0 , 2,1 , ,求g o f ,并说明其是否是双射函数。.设M= 0o,60o,120o,240o,300o,180o表示平面上几何图形顺时针旋转的六种位置，定义一个二元运算对M中任一元素a,b有2*=图形旋转(a+b)的角度，并规定当旋转到360o时即为0o。是否是群。*0o60o120o180o240o300o0o0o60o120o180o240o300o60o60o120o180o240o300o0o120o120o180o240o300o0o60o180o

14、180o240o300o0o60o120o240o240o300o0o60o120o180o300o300o0o60o120o180o240o.求图中的一棵最小生成树。v731.已知某有向图的邻接矩阵如下:路径的条数。32.33.V2V3V40 试求：V3到V1的长度为4的有向F31.已知某有向图的邻接矩阵如下:路径的条数。32.33.V2V3V40 试求：V3到V1的长度为4的有向F图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。30G201CB4。123D的可达矩阵，并判断图的连通性。34.有向图G如图所示，试求：（1）求G的邻接矩阵Ao （2）求出A2、A3和A4 （3） v1到V4长度为1、2、3和4的路径有多少（4）求出可达矩阵 P。35.35.画一个有一条