2017离散数学复习题
- 格式：doc
- 大小：623.50 KB
- 文档页数：11
题型
一、填空题
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},则A×B=_____________________________________。
5．已知图G中有1个1度结点，2个2度结点，3个3度结点，则G的边数是 。
二、单项选择题
1、下列各命题中真值为真的命题有（ ）。
A. 2+2=4当且仅当3是奇数 B. 2+2=4当且仅当3不是奇数
C. 2+2≠4当且仅当3是奇数 D. 2+2=4仅当3不是奇数
2、设个体域D={a,b}，与公式)(xxA等价的公式是( )。
A. )()(bAaA B. )()(bAaA C. )()(bAaA D. )()(aAbA
3、令F(x):x是人，G(x):x是犯错误，则命题“没有不犯错误的人”可符号化为（ ）。
A.))()((xGxFx B.))()((xGxFx
C.))()((xGxFx D.))()((xGxFx
4、下列命题公式不是永真式的是( )。
A. pqp)( B . )(pqp C. )(pqp D. pqp)(
5、设X={1,2,3},Y={a,b,c},f={<1,b>,<2,a>,<3,a>},则以下命题正确的是( )。
A．f是从X到Y的二元关系，但不是从X到Y的函数
B．f是从X到Y的函数，但不是满射的，也不是单射的
C．f是从X到Y的满射，但不是单射 D．f是从X到Y的双射
6、设集合A={a, b, c}，A上的二元关系R={, , }，则R是( )。
A.自反的 B.对称的 C. 传递的 D.反对称的
7、设集合A={1,2,3,4}，A上的等价关系R={ <3,2>, <2,3>}IA，则对应于R的划分是（ ）。
A. {{1},{2,3},{4}} B. {{1,3},{2,4}} C. {{1,3},{2},{4}} D.
{{1},{2},{3},{4}} 8、图G1如图1所示，以下说法正确的是( )。
A. a是割点 B. {b,c}是点割集
C. {b,d}是点割集 D. c是割点
9、设集合S={1,-1}，下面定义的哪种运算关于集合S是封闭的( )。
A. 普通的减法运算 B. 普通的加法运算
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、已知A，B，C是三个集合，证明：A-(BC)=(A-B)-C.
2、构造下面推理的证明。
前提：A，A→B，A→C，B→(D→C)
结论：D
四、综合应用题
1、利用等值演算法求命题公式（PQ）R的主合取范式并给出其成真赋值和成假赋值。
2、设集合Ａ={a，b，c}上的二元关系R={a，b，b，a，b，c}，求R的自反闭包r(R)，对称闭包s(R)及传递闭包t(R)。
3、设有向图D如图G3所示,回答下列问题：
（1）求图D的邻接矩阵；
（2）求图D中长度为2的通路数；
（3）求图D中长度为2的回路数；
（4）求图D的可达矩阵。
图2 G2 24 36
12
6
2 3 图1 G1 d c a b 4、如图4-1和图4-2所示的两个图G4，G5：
（1）试判断它们是否为欧拉图？并说明理由；
（2）若是欧拉图，请写出一条欧拉回路；
（3）若不是欧拉图，请问至少添加几条边，能够使其成为欧拉图。
图4-1 G4 图4-2 G5
5、设R为实数集合，在R上定义二元运算*，Ryx,，有
xyyxyx*
（1）验证二元运算*是否满足结合律；
（2）求二元运算*的单位元；
（3）对实数x，求其逆元。
d b e c
f a
j i
h g c e
d b a 离散数学期末考试复习题
一、填空题
1、谓词公式((,)(,))(,)xyPxyQyzxRxy中x的辖域是 。
2、将以下命题进行命题符号化为______________________。
(1) 李平不但聪明又用功。
(2) 李平虽然聪明，但不用功。
(3) 李平不但聪明，而且用功。
(4) 李平不是不聪明，而是不用功。
3、将以下命题进行命题符号化为______________________。
(1) 人不犯我，我不犯人；人若犯我，我必犯人。
(2) 不经一事，不长一智。
4、 命题公式pq ( )的成真赋值为_______________________。
5、命题公式()()pqpq的成真赋值为 ___________________。
6、将命题“没有一个运动员不是强壮的”谓词符号化为___________________。
7、给定简单命题函数：
A(x)：x身体好， B(x)：x学习好， C(x)：x工作好，
复合命题函数 A(x)→(B(x)∧C(x))表示的含义是：________________。
8、将下列命题符号化：________________。
(1)偶数均能被2整除. (2)存在着偶素数. (3)没有不吃饭的人.(4)素数不全是奇数.
9、公式()()xPxxQx的前束范式为_____________________________。
10、谓词公式(xF(x，y)yG(x，y))的前束范式为 。
11、在1和1000之间（包括1和1000在内）不能被4和5整除的数有 个。
12、若集合A＝{a,b},B＝{0,1,2},则A×B为______________________；B×A为______________________。
13、设集合A = {1, 2}，则P(A)为________________； P(A)×A为_______________________。
14、设集合A={0, 1}, B={1, 2}, C={0, 1, 2} ，则A, B和C的笛卡尔积A×B×C为：________________________。
15、请用谓词表达式（或枚举方式）描述实数集上子集A上的小于等于关系__________________；正整数集合的子集B上的整除关系____________________；集合C的幂集上的包含关系_________________；集合D={1,2,3,4,5,6,7}上的模3同余关系__________________________。
16．设R是定义在集合{1,2,3,4}A上的二元关系{1,1,1,2,2,3,1,4}R，则R的对称闭包()sR_______________。
17、命题“所有的人都是要死的”的否定的含义是___________。
18、设集合A中有m个元素，集合B中有n个元素，则集合A和集合B的笛卡尔积A×B中含有___________个元素，定义在集合A和集合B上不同的二元关系有___________个，从集合A到集合B不同的函数有___________个。
19．无向连通图是欧拉图的充分必要条件是____________________。
20．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 ．
21．设给定图G(如下图所示)，则图G的点割集是 ．
22．设无向图G＝是哈密尔顿图，则V的任意非空子集V1，都有 ．．
23．设有向图D为欧拉图，则图D中每个结点的入度 ．
24．设完全图Kn有n个结点(n≥2)，m条边，当 时，Kn中存在欧拉回路．
25．集合A={a , b , c }上总共可定义的二元运算的个数为______。
26．设{1,1}A，则关于普通加法、减法、乘法中___ ____运算是封闭的。
27．设{0,1,2,...,1}nnZ，在代数系统,,nZ中，,分别表示模n的加法和乘法，则nZ对运算的单位元是______， nZ对的单位元是_______。
28．设G={1 , 2 , 3 , 4 , 5, 6}，G关于模7乘法构成代数系统，群G的幺元是_________，元素3与______互为逆元。
二、单项选择题
1、下列句子中有（ ）个是命题。
(1) 我是老师。(2) 禁止吸烟! (3) 蚊子是鸟类动物。(4) 月亮比地球大。A. 1 B . 2 C. 3 D. 4
2、下列公式中，哪个是永真式（ ）
A. ()qpq B. ()pqp C. ()ppq D. ()pqq
3、 设()Fx: x是有理数，()Gx：x能表示成分数。在一阶逻辑中，命题“没有不能表示成分数的有理数”可符号化为( )。
A. (()())xFxGx B. (()())xFxGx
C. (()())xFxGx D. (()())xFxGx
4、 设个体域是整数集，则下列命题的真值为真的是( )。
A．(1)yxxy B．(0)xyxy
C．2()xyxyy D．2()yxxyx
5、下列命题中为假命题的是( )（其中P（A）为A的幂集）
A．{}()P B. ({})P C. (){}P D.()({})PP
6、 集合{1,2,,10}AL上的关系{,|10,,}RxyxyxyA，则R的性质为( )。
A、自反的 B、传递的、对称的
C、对称的 D、反自反的、传递的
7、设,,RZN分别表示实数、整数和自然数集，
设函数1:{0,1,2}fN，()mod3fxx，（x除以3所得的余数），
2:,()2xfRRfx，3:,()||fZNfxx，4:fNNN，(),1fxxx
