2017离散数学复习题

1、题型一、填空题1、设集合A有n个元素，那么A的募集P(A)的元素个数为2、谓词公式 xF(x)Q(x,y)中的前束范式为 3、设集合 A = a,b,a,b , B = a,b,则 B-A=。4、设集合 A : 0,1, B=1,2,则AXB=5.已知图G中有1个1度结点，2个2度结点，3个3度结点，则G的边数是 0二、单项选择题 TOC o 1-5 h z 1、下列各命题中真值为真的命题有()。A. 2+2=4当且仅当3是奇数 B. 2+2=4当且仅当3不是奇数C. 2+2当当且仅当3是奇数 D. 2+2=4仅当3不是奇数2、设个体域D=a,b,与公式xA(x)等价的公式是()。A. A(a

2、) A(b) B. A(a) A(b) C. A(a) A(b) D. A(b) A(a)3、令F(x):x是人，G(x):x是犯错误，则命题 没有不犯错误的人”可符号化为()。A. x(F(x) G(x)B. x(F(x) G(x)C. x(F(x) G(x) D. x(F(x) G(x)4、下列命题公式不是永真式的是()。A. (p q) p B . p (q p) C. p (q p) D. (p q) p5、设 X=1,2,3,Y= a,b,c,f=,贝U以下命题正确的是()。f是从X到Y的二元关系，但不是从 X到Y的函数f是从X到Y的函数，但不是满射的，也不是单射的f是从X到Y的满射

3、，但不是单射D . f是从X到Y的双射6、设集合 A=a, b, c, A 上的二元关系 R=, , ,则 R 是()。A.自反的 B.对称白C.传递的D.反对称的7、设集合A=1,2,3,4 , A上的等价关系R= , Ia,则对应于R的划分是( )。A. 1,2,3,4B. 1,3,2,4C. 1,3,2,4D.1,2,3,4A.普通的减法运算B.普通的加法运算S是封闭的()。C.普通的乘法运算D.以上均不是10、集合A=2,3,6,12,24,36上的偏序关系R的哈斯图G2如图2所示，则集合B=2,3,6的最小元为()。A. 2 B. 3 C. 2和3 D.不存在三、推理及证明题1、已知

4、A, B, C是三个集合，证明：A-(B C)=(A-B)-C.2、构造下面推理的证明。前提：A, KB , AtX , B-(D C)结论：D四、综合应用题1、利用等值演算法求命题公式(P Q) 赋值。2、设集合A=a, b, c上的二元关系R= r(R),对称闭包s(R)及传递闭包t(R)。3、设有向图D如图G3所示，回答下列问题：(1)求图D的邻接矩阵；(2)求图D中长度为2的通路数；(3)求图D中长度为2的回路数；(4)求图D的可达矩阵。R的主合取范式并给出其成真赋值和成假a, b , b,a, b, c,求R的自反闭包图3G8、图Gi如图1所示，以下说法正确的是()A. a是割点B.

5、 b,c是点割集C. b,d是点割集D. C 割点9、设集合S=1,-1,下面定义的哪种运算关于集合4、如图4-1和图4-2所示的两个图G4, G5： (1)试判断它们是否为欧拉图？并说明理由；(2)若是欧拉图，请写出一条欧拉回路;(3)若不是欧拉图，请问至少添加几条边，能够使其成为欧拉图图 4-1 G4h 1图 4-2 G55、设R为实数集合，在R上定义二元运算*, x,y R,有 x* y x y xy(1)验证二元运算*是否满足结合律；(2)求二元运算*的单位元；(3)对实数x,求其逆元。离散数学期末考试复习题一、填空题1、谓词公式 x y(P(x, y) Q(y,z) xR(x, y)

6、中 x 的辖域是。2、将以下命题进行命题符号化为 (1)李平不但聪明又用功。(2)李平虽然聪明，但不用功。(3)李平不但聪明，而且用功。(4)李平不是不聪明，而是不用功。3、将以下命题进行命题符号化为 (1)人不犯我，我不犯人；人若犯我，我必犯人。(2)不经一事，不长一智。4、命题公式(p q)的成真赋值为5、命题公式(p q) ( p q)的成真赋值为 o6、将命题没有一个运动员不是强壮的”谓词符号化为 o7、给定简单命题函数：A(x) : x身体好， B(x): x学习好，C(x): x工作好，复合命题函数A(x) 一(B(x)A C(x)表示的含义是： o8、将下列命题符号化：o偶数均能

7、被2整除.(2)存在着偶素数.(3)没有不吃饭的人.(4)素数不全是奇数.9、公式 xP(x) xQ(x)的前束范式为10、谓词公式 (xF(x , y) yG(x, y)的前束范式为。11、在1和1000之间(包括1和1000在内)不能被4和5整除的数有 个12、若集合 A = a,b,B =0,1,2,则 AXB为 BXA 为13、设集合A = 1,2,则P(A)为; P(A)法为 14、设集合 A=0, 1, B=1,2, C=0, 1,2,则 A, B 和C的笛卡尔积 AXBXC为:15、请用谓词表达式(或枚举方式)描述实数集上子集A上的小于等于关系L集合C的募集上的包含关系 ;集合D

8、=1,2,3,4,5,6,7上的模3同余关系16.设R是定义在集合A 1,2,3,4上的二元关系R 1,1 , 1,2 , 2,3 , 1,4 ,则 R 的对称闭包 s(R) 17、命题 所有的人都是要死的”的否定的含义是 。18、设集合A中有m个元素，集合B中有n个元素，则集合A和集合B的笛卡尔积AXB中含有个元素，定义在集合A和集合B上不同的二元关系有个，从集合A到集合B不同的函数有个。.无向连通图是欧拉图的充分必要条件是 o.已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是.设给定图G(如下图所示)，则图G的点割集是.设无向图G=是哈密尔顿图，则V的任意非

9、空子集Vi,都有 一.设有向图D为欧拉图，则图D中每个结点的入度 .设完全图Kn有n个结点(n2) m条边，当 时，Kn中存在欧拉回路.集合A=a , b , c上总共可定义的二元运算的个数为 。.设A 1, 1,则关于普通加法、减法、乘法中 运算是封闭的。.设Zn 0,1,2，,n 1,在代数系统 Zn, 中，分别表示模n的力口法和 乘法，则Zn对 运算的单位元是 , Zn对 的单位元是 。.设G=1 , 2,3,4,5, 6 ,G关于模7乘法构成代数系统，群G的幺元是, 元素3与旦为逆元。二、单项选择题1、下列句子中有()个是命题。我是老师。(2)禁止吸烟！(3)蚊子是鸟类动物。(4)月亮

10、比地球大。A. 1 B . 2 C. 3 D. 42、下列公式中，哪个是永真式()A. q (p q) B. (p q) p C. p (p q) D. (p q) q3、设F(x): x是有理数，G(x)： x能表示成分数。在一阶逻辑中，命题“没有不 能表示成分数的有理数”可符号化为()。A. x(F(x) G(x) B. x(F(x) G(x)C. x(F(x) G(x) D. x(F(x) G(x)4、设个体域是整数集，则下列命题的真值为真的是()。A. y x(x y 1)B . x y(x y 0)c,22、C. x y(x y y )D . y x(x y x )5、下列命题中为假

11、命题的是() (其中P (A)为A的募集)A. P( ) B. P( ) C. P( ) D. P( ) P( )6、集合A 1,2,L ,10上的关系R x,y |x y 10, x,y A,则R的性质为 ()。A、自反的B、传递的、对称的C、对称的D、反自反的、传递的7、设R,Z,N分别表示实数、整数和自然数集，设函数f1：N0,1,2 , f(x) xmod3 , (x除以3所得的余数)，x_f2 ： R R, f (x) 2, f3: ZN, f (x)| x |, f4:N N N , f (x)x,x 1则上述函数中满射的个数为()。A. 1 B. 2 C. 3 D. 48、设R和

12、S定义在P上，P是所有人的集合。R x,y |x, y P x是y的父亲，S x,y |x, y P x是y的母亲，则对于 x, y S 1 R表示()A.x是y的丈夫 B.x是y的妻子 C. x是y的孙子 D.x是y的祖母9、设集合 A =1 , 2, 3上的函数分别为：f = , , , g = , , , h = , , ，贝U h=().A. f?g B. g?f C. f?f D. g?g.设图G的邻接矩阵为A. 5B. 6C. 3D. 4.图G如右图所示，以下说法正确的是().(a, d)是割边(a, d)是边割集(d, e)是边割集(a, d) ,(a, c)是边割集.无向图G存

13、在欧拉通路，当且仅当().G中所有结点的度数全为偶数B . G中仅有有两个奇数度结点G连通且所有结点的度数全为偶数G连通且仅有两个奇数度结点.设S=a,b,则S上总共可定义的二元运算的个数是()A.4B.8C.16D.32.设集合A 1,2,3,.,10,下面定义的哪种运算关于集合 A是不封闭的()A . x* y max x, y B . x* y min x, yC. x* y GCD(x, y) 即x,y的最大公约数D . x* y LCM x, y即x, y的最小公倍数.在自然数集N上，下列哪种运算是可结合的？()A.a* b=a-b B.a*b=maxa,bC.a* b=a+2bD.

14、a* b=|a-b|.设 是正整数集Z+上的二元运算，其中a b max a,b (即取a与b中的最大 者),那么在Z+中()A,不适合交换律；B.不适合结合律；C.存在单位元；D,每个元都有逆元。 三、计算题1、求命题公式(p q)2、求命题公式(p q)3、求命题公式(P Q)4、求命题公式p (q5、给定集合 A=a,b,c,d(p r)的主析取范式，主合取范式及其成真成假赋值。r) p的主析取范式，主合取范式及其成真成假赋值。R主析取范式，主合取范式及其成真成假赋值。r)主析取范式，主合取范式及其成真成假赋值。,给出A上的所有等价关系。6、给定集合A=a,b,c,给出A上的所有等价关系

15、。7、设A=a,b,c,d o下列哪个是A的划分，请说明原因？若是划分，则求其诱导的等价关系?B=a,b,c,d;C=a,b,c,a,d;D=a,b,c8、设 A, R为偏序集，其中A (1,2,3, 4, 6,9, 24,54 , R是A上的整除关系。(1) 画出 A, R的哈斯图；(2)求A中的极大元最大元、最小元、极大元、极小元。9、设集合A 1,2,3,4,6,9,12,18,36, R为A上的整除关系，则R为偏序关系。1)求该关系的哈斯图；2)令B (2,3,6,求B的最大元、最小元、极大元、极小元、上界，上确界，下界和下确界。10、设集合A a,b,c,d, R为A上的二元关系，且

16、R (a,b),(b,c),(c,a),(d,d),1)求R的关系矩阵；2)求R的性质；3)求R的自反闭包，对称闭包以及传递闭包 t(R);11、给定解释I如下：D1=2,3 ; (2) D1中特定元素a=2; 函数f(x)为f(2)=3,f=2;谓词 F(x)为 F(2)=0;F(3)=1;G(x,y) 为 G(i,j)=1,i,j=2,3;L(x,y)为 L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0;在解释I下，求下列各式的真值。x(F(x) G(x,a)x(F(f (x) G(x,f (x);x yL(x,y)12、求出下列公式的前束范式xF(x) xG(x)xF(x)

17、 xG(x)xF(x)xG(x)xF(x) yG(x, y)x(F(x)yG(x, y,z)zH (x, y,z) 13、求1到1000之间不能被5、6、8整除的数的个数。14、设人=a,b,c,d,R=, 试给出 R和 r(R),s(R),t(R)的关系图。15、设图 GV,E ,其中 Va1,a2,a3,a4,a5,Ea1，a2,a2,a4,a3,a1,a4, a5 ,a5, a2(1)试给出G的图形表示；(2)求G的邻接矩阵，关联矩阵；(3)判断图G是强连通图、单侧连通图还是弱连通图？16、设有向图D如右图所示，求图D中长度为3的通路数, 并指出其中的回路数.17、在实数集合R上定义二元

18、运算X*Y XY 2X 2Y 6(1)验证*是否满足交换律和结合律。(2)求*的单位元。(3)对任何实数X,求其逆元。18、设代数系统A,* ,其中A a,b,c,d , *运算定义如下表，请指出*运算是否是可交换的；是否有单位元；如果有单位元，指出哪些元素是可逆的，并给出它们的逆 元。*abcdaabcdbbcdaccdabddabc19、设丫= 为代数系统，其中 A=0,1,2,3,4 , a,b A,a*b (ab) mod 5。(1)列出*的运算表*是否有零元和幺元？若有幺元，请求出所有可逆元素的逆元。20、设Z为整数集合，在Z上定义二元运算*, x,y Z ,有x* y x y 2

19、,(1)二元运算*满足结合律吗？(2)二元运算*是否有零元和幺元？若有幺元，请求出所有可逆元素的逆元。Z与二元运算*是否构成群，为什么。22、学生会下设6个委员会，第一委员会二张，李，王,第二委员会二李，赵，刘,第 三委员会二张，刘，王,第四委员会=赵，刘，孙,第五委员会张，王,第六委员 会=李，刘，王.每个月每个委员会都要开一次会，为了确保每个人都能参加他所在 的委员会会议，这6个会议至少要安排在几个不同时间段？23、某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州、香港去开会，每个地 方只能去一人.已知a只想去上海，b只想去广州，c, d, e都表示想去广州或香港.问

20、该课题组在满足个人要求的条件下，给出一种派遣方案？24、有7个人，A会讲英语，B会讲英语和汉语，C会讲英语、意大利语和俄语，D会讲 日语和汉语，E会讲德语和意大利语,F会讲法语、日语和俄语，G会讲法语和德语.问 能否将他们沿圆桌安排就坐成一圈，使得每个人都能与两旁的人交谈？25、画出下面平面图的对偶图四、推理及证明。1、如果我上街，我一定去新华书店.我没上街，所以我没去新华书店.2、若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。3如果今天是星期一，则要进行英语或离散数学的考试.如果英语老师有会，则不考英 语.今天

21、是星期一，英语老师有会，所以进行离散数学的考试.4、构造下面推理的证明前提：qp, q s , s t, t r结论：p q s r5、判断下列推理是否正确。先将命题符号化，再写出前提和结论，然后进行判断。a)如果今天是1号，则明天是5号，今天是1号，所以明天是5号。b)如果今天是1号，则明天是5号，明天是5号，所以今天是1号。c)如果今天是1号，则明天是5号，今天不是1号，所以明天不是5号。d)如果今天是1号，则明天是5号，明天不是5号，所以今天不是1号。6、构造下面推理的证明前提：P- Q, ?(QV R)结论：？ P7、构造下面推理的证明前提：(PAQ - R, ?RVS, ?S, P结

22、论：？ Q8、构造下面推理的证明前提：A BA C, ?B V D , (E ?P) ?D, B AA ?E结论：B E9、给定集合A,证明P(A)上的包含关系为偏序关系。10、给定有限集合A,证明A上的小于等于关系 为偏序关系。11、设 A, R为偏序集，其中A 1,2,3,4,5,6,7,8,9, R是A上的整除关系，试证明R为偏序关系。12、令I是整数集合，I上关系R定义为：R=|x-y可被m整除,求证R是自 反、对称和传递的。13、已知A、Ek C是三个集合，证明以下集合恒等式。an (eu c)=(a n E) u (A n C)au(B n c)=(a u e) n (a u c)a-(eu c)=(a-e) n(a-C)a-(en c)=(a-e) u(a-C)14、若无向图G中只有两个奇数度结点，则这两个结点一定是连通的.15、设G是一个n阶无向简单图，n是大于等于2的奇数.证明图G与它的补图G中 的奇数度顶点个数相等.16、设连通图G有k个奇数度的结点，证明在图G中至少要添加K条边才能使其成