离散数学习题及答案 下载本文

离散数学习题及答案

【篇一:《离散数学》题库及答案】

>一、选择或填空 (数理逻辑部分)

1、下列哪些公式为永真蕴含式?()

(1)?q=q→p (2)?q=p→q (3)p=p→q (4)?p?(p?q)=?p答:(1),(4)

2、下列公式中哪些是永真式?( )

(1)(┐p?q)→(q→?r) (2)p→(q→q) (3)(p?q)→p(4)p→(p?q) 答:(2),(3),(4)

3、设有下列公式,请问哪几个是永真蕴涵式?() (1)p=p?q (2) p?q=p (3) p?q=p?q

(4)p?(p→q)=q (5) ?(p→q)=p (6) ?p?(p?q)=?p 答:(2),(3),(4),(5),(6)

4、公式?x((a(x)?b(y,x))? ?z c(y,z))?d(x)中,自由变元是(),约束变元是( )。 答:x,y,x,z

5、判断下列语句是不是命题。若是,给出命题的真值。( )

(1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗?(4) 若7+8>18,则三角形有4条边。 (5) 前进! (6) 给我一杯水吧!

答:(1) 是,t (2) 是,f (3) 不是 (4) 是,t (5) 不是 (6) 不是

6、命题“存在一些人是大学生”的否定是(),而命题“所有的人都是要死的”的否定是()。

答:所有人都不是大学生,有些人不会死

7、设p:我生病,q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校

(3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) ?q?p(2) p??q (3) p??q (4)?p?q 8、设个体域为整数集,则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0)

答:(1)对任一整数x存在整数 y满足x+y=0(2)存在整数y对任一整数x满足x+y=0

9、设全体域d是正整数集合,确定下列命题的真值: (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x)( ) 答:(1) f (2) f(3)f(4)t

10、设谓词p(x):x是奇数,q(x):x是偶数,谓词公式 ?x(p(x)?q(x))在哪个个体域中为真?()

(1) 自然数 (2) 实数(3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2是偶数或-3是负数”的否定是( )。 答:2不是偶数且-3不是负数。 12、永真式的否定是( )

(1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答:(2) 13、公式(?p?q)?(?p? 为( )。

答:?p ,q?p ?q)化简为( ),公式 q?(p?(p?q))可化简

14、谓词公式?x(p(x)? ?yr(y))?q(x)中量词?x的辖域是( )。 答:p(x)? ?yr(y)

15、令r(x):x是实数,q(x):x是有理数。则命题“并非每个实数都是有理

数”的符号化表示为( )。 答:??x(r(x)?q(x)) (集合论部分)

16、设a={a,{a}},下列命题错误的是( )。

(1) {a}?p(a) (2) {a}?p(a) (3) {{a}}?p(a) (4) {{a}}?p(a) 答:(2) 17、在0()?之间写上正确的符号。 (1) = (2) ? (3) ? (4) ? 答:(4)

18、若集合s的基数|s|=5,则s的幂集的基数|p(s)|=( )。 答:32

19、设p={x|(x+1)2?4且x?r},q={x|5?x2+16且x?r},则下列命题哪个正确( )

(1) q?p (2) q?p (3) p?q (4) p=q 答:(3)

20、下列各集合中,哪几个分别相等()。

(1) a1={a,b} (2) a2={b,a} (3) a3={a,b,a} (4) a4={a,b,c}

(5) a5={x|(x-a)(x-b)(x-c)=0} (6) a6={x|x2-(a+b)x+ab=0} 答:a1=a2=a3=a6, a4=a5

答:(4)

22、判断下列命题哪个为真?( )

(1) a-b=b-a = a=b (2) 空集是任何集合的真子集

(3) 空集只是非空集合的子集 (4) 若a的一个元素属于b,则a=b 答:(1)

23、判断下列命题哪几个为正确?() 答:(2),(4)

24、判断下列命题哪几个正确?( )

25、设a∩b=a∩c,a∩b=a∩c,则b( )c。 答:=(等于)

26、判断下列命题哪几个正确?( )

(1) 若a∪b=a∪c,则b=c (2) {a,b}={b,a} (3) p(a∩b)?p(a)∩p(b) (p(s)表示s的幂集) (4) 若a为非空集,则a?a∪a成立。 答:(2)

27、A,B,C是三个集合,则下列哪几个推理正确:

(1) a?b,b?c= a?c (2) a?b,b?c= a∈b (3) a∈b,b∈c= a∈c 答:(1)

(二元关系部分)

28、设A={1,2,3,4,5,6},b={1,2,3},从A到b的关系R={〈x,y〉|x=y2},求(1)r (2) r-1 。 答:(1)r={1,1,4,2} (2) r?1={1,1,2,4}

29、举出集合a上的既是等价关系又是偏序关系的一个例子。( ) 答:a上的恒等关系

30、集合a上的等价关系的三个性质是什么?( ) 答:自反性、对称性和传递性

31、集合a上的偏序关系的三个性质是什么?( ) 答:自反性、反对称性和传递性

32、设s={1,2,3,4},A上的关系R={〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉} 求(1)r?r (2) r-1 。

答:r?r ={〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉} r ={〈2,1〉,〈1,2〉,〈3,2〉,〈4,3〉} -1

33、设A={1,2,3,4,5,6},R是a上的整除关系,求r= {( )}。 答:r={1,1,2,2,3,3,4,4,5,5,6,6,1,2,1,3,1,4, 1,5,1,6,2,4,2,6,3,6}

34、设A={1,2,3,4,5,6},b={1,2,3},从A到b的关系R={〈x,y〉|x=2y},求(1)r (2) r-1 。

答:(1)r={1,1,4,2,6,3} (2) r?1={1,1,2,4,(36}

35、设A={1,2,3,4,5,6},b={1,2,3},从A到b的关系R={〈x,y〉|x=y2},

求r和r-1的关系矩阵。

?1?0?0答:r的关系矩阵=? ?0? ?0

??00001000?0??1?0?0 r?1的关系矩阵=??0????00?0??0000000100000??0 ?0??

36、集合a={1,2,…,10}上的关系r={x,y|x+y=10,x,y?a},则r 的性质为()。

(1) 自反的 (2) 对称的(3) 传递的,对称的 (4) 传递的 答:(2) (代数结构部分)

37、设a={2,4,6},a上的二元运算*定义为:a*b=max{a,b},则在独异点a,*中,单位元是( ),零元是( )。 答:2,6

38、设a={3,6,9},a上的二元运算*定义为:a*b=min{a,b},则在独异点

【篇二:离散数学练习题及答案】

的表示方法有两种:法。请把“奇整数集合”表示出 ,k?z} 来{}。1、列举;描述;{x|x?2k?1

2、无向连通图g含有欧拉回路的充分必要条件是 2*、连通有向图d含

有欧拉回路的充分必要条件是d中每个结点的入度=出度.

3、设r是集合a上的等价关系,则r所具有的关系的三个特性是 自反性、对称性、传递性.

4、有限图g是树的一个等价定义是:.

5、设n(x):x是自然数,z(y);y是整数,则命题“自然数都是整数,而有的整数不是自然

数”符号化为?x(n(x)?z(x))??x(z(x)??n(x))

6、在有向图的邻接矩阵中,第i行元素之和,第j列元素之和分别为 结点v的出度和结点v的入度.

7、设a,b为任意命题公式,c为重言式,若a?c?b?c,那么命题a?b是

重言式的真值是 1.

8、命题公式?(p?q)的主析取范式为

9、 设图g=v,e和g?=v?,e?,若g?是g的真子图,若 ,则g?是g的生成子图. v??v或e??e;v??v,e??e 10、在平面图g??v,e?中,则

11、设a?{a,b},?deg(r)=,其中r(i=1,2,…,r)是g的

面. iiri?1b?{1,2},则从a到b的所有映射是11、?1={(a,1),(b,1)};?2={(a,2),(b,2)};?3={(a,1),(b,2)};?4={(a, 2),(b,1)}

12、表达式?x?yl(x,y)中谓词的定义域是{a,b,c},将其中的量词消除,写成与之等价 的命题公式为

12、(l(a,a)?l(a,b)?l(a,c))?(l(b,a)?l(b,b)?l(b,c))?(l(c,a)?l(c,b)?l(c,c))

12*、设个体域d={a,b},公式?x(g(x)??yh(x,y))消去量词化为

13、含有三个命题变项p,q,r的命题公式p?q的主析取范式是 14、设r,s都是集合a上的等价关系,则对称闭包s(r?s)=15、设g是连通平面图,v,e,r分别表示g的结点数,边数和面数,则v,e和r满足的关系式 是v?r?e??

16、设g是n个结点的简单图,若g,则g一定是哈密顿图. 17、一个有向树t称为根树,若

称为树叶. 若有向图t恰有一个结点的入度为0,其余结点入度为1;入度为0的结点;出度为0的结点.

18、图的通路中边的数目称为结点不重复的通路是通路. 边不重复的 通路是 通路. 通路长度;初级;简单.

19、设a和b为有限集,|a|=m,|b|=n,则有 个从a到b的关系,有 个从a到b的函数,其中当m?n时有 个入射,当m=n时,有 个双射。 19、2m*nm,nm,cn?m!,m!

2a?{n|n?n}(是/不是)可数的。是 20、集合 21、设l??1,2,3,4,12?上的整除关系 ??a1,a2a1,a2?l,a1整除a2 ??