《离散数学复习题》由会员分享，可在线阅读，更多相关《离散数学复习题（11页珍藏版）》请在金锄头文库上搜索。
1、. . 题型一、填空题1、设集合A有n个元素，那么A的幂集P(A)的元素个数为_。2、谓词公式$xF(x)Q(x,y)中的前束式为_。3、设集合Aa,b,a,b，Ba,b,则B-A=_。4、设集合A0,1，B1,2,则AB=_。5已知图G中有1个1度结点，2个2度结点，3个3度结点，则G的边数是。二、单项选择题1、以下各命题中真值为真的命题有（ ）。A. 2+2=4当且仅当3是奇数 B. 2+2=4当且仅当3不是奇数C. 2+24当且仅当3是奇数 D. 2+2=4仅当3不是奇数2、设个体域D=a,b，与公式等价的公式是( )。A. B. C. D. 3、令F(x):x是人，G(x):x是犯错误
2、，则命题“没有不犯错误的人”可符号化为（ ）。A. B.C. D.4、以下命题公式不是永真式的是( )。A. B . C. D. 5、设X=1,2,3,Y=a,b,c,f=,则以下命题正确的是( )。Af是从X到Y的二元关系，但不是从X到Y的函数Bf是从X到Y的函数，但不是满射的，也不是单射的Cf是从X到Y的满射，但不是单射 Df是从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,4 B. 1,3,2,4
3、C. 1,3,2,4 D. 1,2,3,4图1 G1dcab8、图G1如图1所示，以下说确的是( )。A. a是割点 B. b,c是点割集 C. b,d是点割集 D. c是割点9、设集合S=1,-1，下面定义的哪种运算关于集合S是封闭的( )。A. 普通的减法运算 B. 普通的加法运算 图2 G2243612623C. 普通的乘法运算 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)-
4、C.2、构造下面推理的证明。 前提：A，AB，AC，B(DC) 结论：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的可达矩阵。4、如图4-1和图4-2所示的两个图G4，G5：（1）试判断它们是否为欧拉图？并说明理由；（2）若是欧拉图，请写出一条欧拉回路；dbecfajihg（3）若不
5、是欧拉图，请问至少添加几条边，能够使其成为欧拉图。cedba 图4-1 G4图4-2 G55、设R为实数集合，在R上定义二元运算*，有（1）验证二元运算*是否满足结合律；（2）求二元运算*的单位元；（3）对实数x，求其逆元。离散数学期末考试复习题一、填空题1、谓词公式中的辖域是。2、将以下命题进行命题符号化为_。(1) 平不但聪明又用功。 (2) 平虽然聪明，但不用功。 (3) 平不但聪明，而且用功。 (4) 平不是不聪明，而是不用功。 3、将以下命题进行命题符号化为_。(1) 人不犯我，我不犯人；人若犯我，我必犯人。 (2) 不经一事，不长一智。4、 命题公式的成真赋值为_。5、命题公式的成
6、真赋值为 _。6、将命题“没有一个运动员不是强壮的”谓词符号化为_。7、给定简单命题函数：A(x)：x身体好， B(x)：x学习好， C(x)：x工作好，复合命题函数 A(x)(B(x)C(x)表示的含义是：_。8、将以下命题符号化：_。(1)偶数均能被2整除. (2)存在着偶素数. (3)没有不吃饭的人.(4)素数不全是奇数. 9、公式的前束式为_。10、谓词公式(xF(x，y)$yG(x，y)的前束式为。11、在1和1000之间（包括1和1000在）不能被4和5整除的数有个。12、若集合Aa,b,B0,1,2,则AB为_；BA为_。13、设集合A = 1, 2，则P(A)为_； P(A)A
7、为_。14、设集合A=0, 1, B=1, 2, C=0, 1, 2 ，则A, B和C的笛卡尔积ABC为：_。15、请用谓词表达式（或枚举方式）描述实数集上子集A上的小于等于关系_；正整数集合的子集B上的整除关系_；集合C的幂集上的包含关系_；集合D=1,2,3,4,5,6,7上的模3同余关系_。16设是定义在集合上的二元关系，则的对称闭包_。17、命题“所有的人都是要死的”的否定的含义是_。18、设集合A中有m个元素，集合B中有n个元素，则集合A和集合B的笛卡尔积AB中含有_个元素，定义在集合A和集合B上不同的二元关系有_个，从集合A到集合B不同的函数有_个。19无向连通图是欧拉图的充分必要
8、条件是_。20已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是21设给定图G(如以下图所示)，则图G的点割集是ooooocabedof22设无向图G是哈密尔顿图，则V的任意非空子集V1，都有23设有向图D为欧拉图，则图D中每个结点的入度24设完全图Kn有n个结点(n2)，m条边，当时，Kn中存在欧拉回路25集合A=a , b , c 上总共可定义的二元运算的个数为_。26设，则关于普通加法、减法、乘法中_ _运算是封闭的。27设，在代数系统中，分别表示模n的加法和乘法，则对运算的单位元是_，对的单位元是_。28设G=1 , 2 , 3 , 4 , 5, 6，G关
9、于模7乘法构成代数系统，群G的幺元是_，元素3与_互为逆元。二、单项选择题1、以下句子中有（ ）个是命题。 (1) 我是老师。(2) 禁止吸烟! (3) 蚊子是鸟类动物。(4) 月亮比地球大。A. 1 B . 2 C. 3 D. 42、以下公式中，哪个是永真式（ ）A. B. C. D. 3、 设: 是有理数，：能表示成分数。在一阶逻辑中，命题“没有不能表示成分数的有理数”可符号化为( )。A. B. C. D. 4、 设个体域是整数集，则以下命题的真值为真的是( )。A BC D5、以下命题中为假命题的是( )（其中P（A）为A的幂集）A B. C. D.6、 集合上的关系，则的性质为( )
10、。A、自反的 B、传递的、对称的C、对称的 D、反自反的、传递的7、设分别表示实数、整数和自然数集，设函数，（除以3所得的余数），则上述函数中满射的个数为（ ）。A1 B. 2 C. 3 D. 4 8、设R和S定义在P上，P是所有人的集合。， ，则对于表示( )A.x是y的丈夫 B.x是y的妻子 C. x是y的子 D.x是y的祖母9、设集合A =1 , 2, 3上的函数分别为：f = ，g = ，h = ，则h =（ ） A. fg B. gf C. ff D. gg10设图G的邻接矩阵为则G的边数为( )A5 B6 C3 D411图G如右图所示，以下说确的是 ( ) A(a, d)是割边B(
11、a, d)是边割集C(d, e)是边割集D(a, d) ,(a, c)是边割集12无向图G存在欧拉通路，当且仅当( )AG中所有结点的度数全为偶数 BG中仅有有两个奇数度结点CG连通且所有结点的度数全为偶数DG连通且仅有两个奇数度结点13设S=a,b，则S上总共可定义的二元运算的个数是（ ） A.4B.8C.16D.3214设集合，下面定义的哪种运算关于集合是不封闭的（ ）。 A BC 即的最大公约数D 即的最小公倍数15在自然数集N上，以下哪种运算是可结合的？（ ）A.a*b=a-bB.a*b=maxa,bC.a*b=a+2bD.a*b=|a-b|16设是正整数集上的二元运算，其中（即取与中的最大者），那么在中（ ）A不适合交换律；B不适合结合律；C存在单位元；D每个元都有逆元。三、计
