《离散数学》复习题及答案.doc
《《离散数学》复习题及答案.doc》由会员分享，可在线阅读，更多相关《《离散数学》复习题及答案.doc（43页珍藏版）》请在冰点文库上搜索。
《离散数学》试题及答案
一、选择或填空
（数理逻辑部分）
1、下列哪些公式为永真蕴含式？
（ ）
（1）Q=>Q→P
（2）Q=>P→Q（3）P=>P→Q（4）P（PQ）=>P
答：
（1），（4）
2、下列公式中哪些是永真式？
（）
（1）（┐PQ）→（Q→R）
（2）P→（Q→Q）（3）（PQ）→P（4）P→（PQ）
答：
（2），（3），（4）
3、设有下列公式，请问哪几个是永真蕴涵式?
（）
（1）P=>PQ
（2）PQ=>P（3）PQ=>PQ
（4）P（P→Q）=>Q（5）（P→Q）=>P（6）P（PQ）=>P
答：
（2），（3），（4），（5），（6）
4、公式"x（（A（x）®B（y，x））Ù$zC（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）
（2）（3）（4）
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、公式（PQ）（PQ）化简为（），公式Q（P（PQ））可化简为（）。
答：
P，QP
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）4且xR},Q={x|5x+16且xR},则下列命题哪个正确（）
（1）QP
（2）QP （3）PQ （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
21、若A-B=Ф，则下列哪个结论不可能正确？
（）
（1）A=Ф
（2）B=Ф （3）AB（4）BA
答：
（4）
22、判断下列命题哪个为真?
（）
（1）A-B=B-A=>A=B
（2）空集是任何集合的真子集
（3）空集只是非空集合的子集（4）若A的一个元素属于B，则A=B
答：
（1）
23、判断下列命题哪几个为正确？
（ ）
（1）{Ф}∈{Ф,{{Ф}}}
（2）{Ф}{Ф,{{Ф}}}（3）Ф∈{{Ф}}
（4）Ф{Ф}（5）{a,b}∈{a,b,{a},{b}}
答：
（2），（4）
24、判断下列命题哪几个正确？
（ ）
（1）所有空集都不相等
（2）{Ф}Ф（4）若A为非空集，则AA成立。
答：
（2）
25、设A∩B=A∩C，∩B=∩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为非空集，则AA∪A成立。
答：
（2）
27、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：
（1）AB，BC=>AC
（2）AB，BC=>A∈B（3）A∈B，B∈C=>A∈C
答：
（1）
（二元关系部分）
28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求
（1）R
（2）R-1。
答：
（1）R={<1,1>,<4,2>}
（2）R={<1,1>,<2,4>}
29、举出集合A上的既是等价关系又是偏序关系的一个例子。
（ ）
答：
A上的恒等关系
30、集合A上的等价关系的三个性质是什么？
（）
答：
自反性、对称性和传递性
31、集合A上的偏序关系的三个性质是什么？
（）
答：
自反性、反对称性和传递性
32、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝
求
（1）RR
（2）R-1。
答：
RR={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}
R-1=｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝
33、设Ａ＝｛1，2，3，4，5，6｝，Ｒ是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、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=2y｝，求
（1）R
（2）R-1。
答：
（1）R={<1,1>,<4,2>,<6,3>}
（2）R={<1,1>,<2,4>,（36>}
35、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求R和R-1的关系矩阵。
答：
R的关系矩阵=R的关系矩阵=
36、集合A={1,2,…,10}上的关系R={|x+y=10,x,yA}，则R的性质为（）。
（1）自反的
（2）对称的 （3）传递的，对称的（4）传递的
答：
（2）
（代数结构部分）
37、设A={2,4,6}，A上的二元运算*定义为：
a*b=max{a,b}，则在独异点中，单位元是（），零元是（）。
答：
2，6
38、设A={3,6,9}，A上的二元运算*定义为：
a*b=min{a,b}，则在独异点中，单位元是（），零元是（）；
答：
9，3
（半群与群部分）
39、设〈G,*〉是一个群，则
（1）若a,b,x∈G，ax=b，则x=（）；
（2）若a,b,x∈G，ax=ab，则x=（）。
答：
（1）ab
（2）b
40、设a是12阶群的生成元，则a2是（）阶元素，a3是（）阶元素。
答：
6,4
41、代数系统是一个群，则G的等幂元是（ ）。
答：
单位元
42、设a是10阶群的生成元，则a4是（）阶元素，a3是（）阶元素。
答：
5，10
43、群的等幂元是（ ），有（ ）个。
答：
单位元，1
44、素数阶群一定是（）群,它的生成元是（）。
答：
循环群，任一非单位元
45、设〈G,*〉是一个群，a,b,c∈G，则
（1）若ca=b，则c=（）；
（2）若ca=ba，则c=（）。
答：
（1）b
（2）b
46、是的子群的充分必要条件是（）。
答：
是群或"a，bG，abH，a-1H或"a,bG，ab-1H
47、群＜A,*＞的等幂元有（ ）个，是（ ），零元有（ ）个。
答：
1，单位元，0
48、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是（）。
答：
k
49、在自然数集N上，下列哪种运算是可结合的？
（）
（1）a*b=a-b
（2）a*b=max{a,b} （3）a*b=a+2b （4）a*b=|a-b|
答：
（2）
50、任意一个具有2个或以上元的半群，它（）。
（1）不可能是群
（2）不一定是群
（3）一定是群 （4）是交换群
答：
（1）
51、6阶有限群的任何子群一定不是（）。
（1）2阶
（2）3阶（3）4阶 （4）6阶
答：
（3）
（格与布尔代数部分）
52、下列哪个偏序集构成有界格（）
（1）（N,）
（2）（Z,）
（3）（{2,3,4,6,12},|（整除关系）） （4）（P（A）,）
答：
（4）
53、有限布尔代数的元素的个数一定等于（）。
（1）偶数
（2）奇数（3）4的倍数 （4）2的正整数次幂
答：
（4）
（图论部分）
54、设G是一个哈密尔顿图，则G一定是（）。
（1）欧拉图
（2）树 （3）平面图（4） 连通图
答：
（4）
55、下面给出的集合中，哪一个是前缀码？
（ ）
（1）{0，10，110，101111}
（2）{01，001，000，1}
（3）{b，c，aa，ab，aba} （4）{1，11，101，001，0011}
答：
（2）
56、一个图的哈密尔顿路是一条通过图中（）的路。
答：
所有结点一次且恰好一次
57、在有向图中，结点v的出度deg+（v）表示（），入度deg-（v）表示（）。
答：
以v为起点的边的条数，以v为终点的边的条数
58、设G是一棵树，则G的生成树有（）棵。
（1）0
（2）1 （3）2 （4）不能确定
答：
1
59、n阶无向完全图Kn的边数是（），每个结点的度数是（）。
答：
n-1
60、一棵无向树的顶点数n与边数m关系是（ ）。
答：
m=n-1
61、一个图的欧拉回路是一条通过图中（）的回路。
答：
所有边一次且恰好一次
62、有n个结点的树，其结点度数之和是（ ）。
答：
2n-2
63、下面给出的集合中，哪一个不是前缀码（）。
（1）{a，ab，110，a1b11}
（2）{01，001，000，1}
（3）{1，2，00，01，0210}（4）{12，11，101，002，0011}
答：
（1）
64、n个结点的有向完全图边数是（），每个结点的度数是（）。
答：
n（n-1）,2n-2
65、一个无向图有生成树的充分必要条件是（）。
答：
它是连通图
66、设G是一棵树，n,m分别表示顶点数和边数，则
（1）n=m
（2）m=n+1（3）n=m+1（4）不能确定。
答：
（3）
67、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在（）片树叶。
答：
2
68、任何连通无向图G至少有（）棵生成树，当且仅当G是（），G的生成树只有一棵。
答：
1，树
69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:
（1）m-n+2
（2）n-m-2（3）n+m-2（4）m+n+2。
答：
（1）
70、设T是一棵树，则T是一个连通且（）图。
答：
无简单回路
71、设无向图G有16条边且每个顶点的度数都是2，则图G有（）个顶点。
（1）10
（2）4（3）8（4）16
答：
（4）
72、设无向图G有18条边且每个顶点的度数都是3，则图G有（）个顶点。
（1）10
（2）4（3）8（4）12
答：
（4）
73、设图G=，V={a，b，c，d，e}，E={,,,,},则G是有向图还是无向图？
答：
有向图
74、任一有向图中，度数为奇数的结点有（ ）个。
答：
偶数
75、具有6个顶点，12条边的连通简单平面图中，每个面都是由（ ）条边围成？
（1）2
（2）4 （3）3 （4）5
答：
（3）
76、在有n个顶点的连通图中，其边数（）。
（1）最多有n-1条
（2）至少有n-1条
（3）最多有n条 （4）至少有n条
答：
（2）
77、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点为（）。
（1）5
（2）7（3）8 （4）9
答：
（4）
78、若一棵完全二元（叉）树有2n-1个顶点，则它（）片树叶。
（1）n
（2）2n（3）n-1 （4）2
答：
（1）
79、下列哪一种图不一定是树（）。
（1）无简单回路的连通图
（2）有n个顶点n-1条边的连通图
（3）每对顶点间都有通路的图 （4）连通但删去一条边便不连通的图
答：
（3）
80、连通图G是一棵树当且仅当G中（）。
（1）有些边是割边
（2）每条边都是割边
（3）所有边都不是割边 （4）图中存在一条欧拉路径
答：
（2）
（数理逻辑部分）
二、求下列各公式的主析取范式和主合取范式：
1、（P→Q）R
解：
（P→Q）R（PQ）R
（PR）（QR）（析取范式）
（P（QQ）R）（（PP）QR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（主析取范式）
（（P→Q）R）（PQR）（PQR）（PQR）
（PQR）（PQR）（原公式否定的主析取范式）
（P→Q）R（PQR）（PQR）（PQR）
（PQR）（PQR）（主合取范式）
2、（PR）（QR）P
解：
（PR）（QR）P（析取范式）
（P（QQ）R）（（PP）QR）（P（QQ）（RR））
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（主析取范式）
（（PR）（QR）P）
（PQR）（PQR）（原公式否定的主析取范式）
（PR）（QR）P（PQR）（PQR）（主合取范式）
3、（P→Q）（RP）
解：
（P→Q）（RP）
（PQ）（RP）（合取范式）
（PQ（RR））（P（QQ））R）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（主合取范式）
（（P→Q）（RP））
（PQR）（PQR）（PQR）（PQR）
（PQR）（原公式否定的主合取范式）
（P→Q）（RP）
（PQR）（PQR）（PQR）（PQR）（PQR）
（主析取范式）
4、Q→（PR）
解：
Q→（PR）
QPR（主合取范式）
（Q→（PR））
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（原公式否定的主合取范式）
Q→（PR）
（PQR）（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（主析取范式）
5、P→（P（Q→P））
解：
P→（P（Q→P））
P（P（QP））
PP
T（主合取范式）
（PQ）（PQ）（PQ）（PQ）（主析取范式）
6、（P→Q）（RP）
解：
（P→Q）（RP）（PQ）（RP）
（PQ）（RP）（析取范式）
（PQ（RR））（P（QQ）R）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（主析取范式）
（（P→Q）（RP））（PQR）（PQR）（PQR）
（PQR）（PQR）（原公式否定的主析取范式）
（P→Q）（RP）（PQR）（PQR）（PQR）
（PQR）（PQR）（主合取范式）
7、P（P→Q）
解：
P（P→Q）P（PQ）（PP）Q
T（主合取范式）
（PQ）（PQ）（PQ）（PQ）（主析取范式）
8、（R→Q）P
解：
（R→Q）P（RQ）P
（RP）（QP）（析取范式）
（R（QQ）P）（（RR）QP）
（RQP）（RQP）（RQP）（RQP）
（PQR）（PQR）（PQR）（主析取范式）
（（R→Q）P）（PQR）（PQR）（PQR）（PQR）（PQR）（原公式否定的主析取范式）
（R→Q）P（PQR）（PQR）（PQR）
（PQR）（PQR）（主合取范式）
9、P→Q
解：
P→QPQ（主合取范式）
（P（QQ））（（PP）Q）
（PQ）（PQ）（PQ）（PQ）
（PQ）（PQ）（PQ）（主析取范式）
10、 PQ
解：
PQ（主合取范式）
（P（QQ））（（PP）Q）
（PQ）（PQ）（PQ）（PQ）
（PQ）（PQ）（PQ）（主析取范式）
11、PQ
解：
PQ（主析取范式）（P（QQ））（（PP）Q）
（PQ）（PQ）（PQ）（PQ）
（PQ）（PQ）（PQ）（主合取范式）
12、（PR）Q
解：
（PR）Q
（PR）Q
（PR）Q
（PQ）（RQ）（合取范式）
（PQ（RR））（（PP）QR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（主合取范式）
（PR）Q
（PQR）（PQR）（PQR）（PQR）（PQR）（原公式否定的主析取范式）
（PR）Q
（PQR）（PQR）（PQR）（PQR）
（PQR）（主析取范式）
13、（PQ）R
解：
（PQ）R
（PQ）R
（PQ）R（析取范式）
（PQ（RR））（（PP）（QQ）R）
（PQR）（PQR）（PQR）（PQR）（PQR）
（PQR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（主析取范式）
（PQ）R
（PQ）R
（PQ）R（析取范式）
（PR）（QR）（合取范式）
（P（QQ）R）（（PP）QR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（主合取范式）
14、（P（QR））（P（QR））
解：
（P（QR））（P（QR））
（P（QR））（P（QR））
（PQ）（PR）（PQ）（PR）（合取范式）
（PQ（RR））（P（QQ）R）（PQ（RR））
（P（QQ）R）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（主合取范式）
（P（QR））（P（QR））
（PQR）（PQR）（原公式否定的主合取范式）
（P（QR））（P（QR））
（PQR）（PQR）（主析取范式）
15、P（P（Q（QR）））
解：
P（P（Q（QR）））
P（P（Q（QR）））
PQR（主合取范式）
（PQR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）
（原公式否定的主合取范式）
（PQR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（主析取范式）
16、（PQ）（PR）
解、（PQ）（PR）
（PQ）（PR）（合取范式）
（PQ（RR）（P（QQ）R）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）（PQR）（主合取范式）
（PQ）（PR）
（PQ）（PR）
P（QR）（合取范式）
（P（QQ）（RR））（（PP）QR）
（PQR）（PQR）（PQR）（PQR）
（PQR）（PQR）
（PQR）（PQR）（PQR）（PQR）（PQR）
（主析取范式）
三、证明：
1、P→Q，QR，R，SP=>S
证明：
（1）R前提
（2）QR前提
（3）Q
（1），
（2）
（4）P→Q前提
（5）P（3），（4）
（6）SP前提
（7）S（5），（6）
2、A→（B→C），C→（DE），F→（DE）,A=>B→F
证明：
（1）A前提
（2）A→（B→C）前提
（3）B→C
（1），
（2）
（4）B附加前提
（5）C（3），（4）
（6）C→（DE）前提
（7）DE（5），（6）
（8）F→（DE）前提
（9）F（7），（8）
（10）B→FCP
3、PQ，P→R,Q→S=>RS
证明：
（1）R附加前提
（2）P→R前提
（3）P
升级会员 