2017离散数学复习题

. . 题型一、填空题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是犯错误，则命题“没有不犯错误的人”可符号化为（ ）。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 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)-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）若不是欧拉图，请问至少添加几条边，能够使其成为欧拉图。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、将命题“没有一个运动员不是强壮的”谓词符号化为_。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为_。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无向连通图是欧拉图的充分必要条件是_。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关于模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、 集合上的关系，则的性质为( )。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(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每个元都有逆元。三、计算题1、 求命题公式的主析取式，主合取式与其成真成假赋值。2、 求命题公式的主析取式，主合取式与其成真成假赋值。3、 求命题公式主析取式，主合取式与其成真成假赋值。4、 求命题公式p (q r)主析取式，主合取式与其成真成假赋值。5、给定集合A=a,b,c,d，给出A上的所有等价关系。6、给定集合A=a,b,c，给出A上的所有等价关系。7、设A=a,b,c,d。以下哪个是A的划分,请说明原因？若是划分，则求其诱导的等价关系？（1）B=a,b,c,d;（2）C=a,b,c,a,d;（3）D=a,b,c8、设为偏序集，其中，是上的整除关系。（1）画出的哈斯图；（2）求中的极大元最大元、最小元、极大元、极小元。9、设集合，R为A上的整除关系，则R为偏序关系。1) 求该关系的哈斯图；2) 令，求B的最大元、最小元、极大元、极小元、上界，上确界，下界和下确界。10、 设集合，R为A上的二元关系，且，1) 求R的关系矩阵；2) 求R的性质；3) 求R的自反闭包，对称闭包以与传递闭包t(R)；11、 给定解释I如下：(1) D1=2,3； (2) D1中特定元素a=2；(3) 函数f(x)为f(2)=3,f(3)=2；(4)谓词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下，求以下各式的真值。1)2)3)12、求出以下公式的前束式1) 2)3)4)5)13、求1到1000之间不能被5、6、8整除的数的个数。14、设Aa,b,c,d,R,试给出R和r(R),s(R),t(R)的关系图。15、设图G=，其中V=a1,a2,a3,a4,a5,E=，（1）试给出G的图形表示；（2）求G的邻接矩阵，关联矩阵；v2v1（3）判断图G是强连通图、单侧连通图还是弱连通图？16、设有向图D如右图所示，求图D中长度为3的通路数，并指出其中的回路数v4v317、在实数集合R上定义二元运算（1） 验证*是否满足交换律和结合律。（2） 求*的单位元。（3） 对任何实数X，求其逆元。18、设代数系统，其中，*运算定义如下表，请指出*运算是否是可交换的；是否有单位元；如果有单位元，指出哪些元素是可逆的，并给出它们的逆元。19、设V=为代数系统，其中A=0,1,2,3,4，。（1） 列出*的运算表（2） *是否有零元和幺元？若有幺元，请求出所有可逆元素的逆元。20、设Z为整数集合，在Z上定义二元运算*，有，（1） 二元运算*满足结合律吗？（2）二元运算*是否有零元和幺元？若有幺元，请求出所有可逆元素的逆元。（3）Z与二元运算*是否构成群，为什么。22、学生会下设6个委员会, 第一委员会=, , 王, 第二委员会=, , , 第三委员会=, , 王, 第四委员会=, , , 第五委员会=, 王, 第六委员会=, , 王. 每个月每个委员会都要开一次会, 为了确保每个人都能参加他所在的委员会会议, 这6个会议至少要安排在几个不同时间段?23、某课题组要从a, b, c, d, e 5人中派3人分别到、去开会，每个地方只能去一人. 已知a只想去，b只想去，c, d, e都表示想去或. 问该课题组在满足个人要求的条件下，给出一种派遣方案？24、有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲法语、日语和俄语, G会讲法语和德语. 问能否将他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人交谈?25、画出下面平面图的对偶图四、推理与证明。 1、如果我上街,我一定去新华书店.我没上街,所以我没去新华书店.2、若小喜欢数学，则小或小也喜欢数学。若小喜欢数学，则他也喜欢物理。小确实喜欢数学，可小不喜欢物理。所以，小喜欢数学。3、如果今天是星期一,则要进行英语或离散数学的考试.如果英语老师有会,则不考英语.今天是星期一,英语老师有会,所以进行离散数学的考试.4、构造下面推理的证明前提：qp，q s，s t, tr结论：pqsr 5、判断以下推理是否正确。先将命题符号化，再写出前提和结论，然后进行判断。a) 如果今天是1号，则明天是5号，今天是1号，所以明天是5号。 b) 如果今天是1号，则明天是5号，明天是5号，所以今天是1号。 c) 如果今天是1号，则明天是5号，今天不是1号，所以明天不是5号。 d) 如果今天是1号，则明天是5号，明天不是5号，所以今天不是1号。 6、构造下面推理的证明 前提：PQ，(QR) 结论：P7、构造下面推理的证明 前提：(PQ)R，RS，S，P 结论：Q8、构造下面推理的证明 前提：ABC, BD , (EP)D, BAE 结论：BE9、给定集合A，证明P(A)上的包含关系为偏序关系。10、给定有限集合A，证明A上的小于等于关系为偏序关系。11、设为偏序集，其中，是上的整除关系，试证明R为偏序关系。12、令I是整数集合，I上关系R定义为：R=|x-y可被m整除，求证R是自反、对称和传递的。13、已知A、B、C是三个集合，证明以下集合恒等式。 A(BC)=(AB)(AC) A(BC)=(AB)(AC) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C)14、若无向图G中只有两个奇数度结点，则这两个结点一定是连通的15、设G是一个n阶无向简单图，n是大于等于2的奇数证明图G与它的补图中的奇数度顶点个数相等16、设连通图G有k个奇数度的结点，证明在图G中至少要添加条边才能使其成为欧拉图17、设G为n阶无向连通简单图, 若G中有割点或桥, 则G不是哈密顿图.18、证明K5 和 K3,3不是平面图.五、判断题1、以下命题公式的类型，若为可满足式，给出成真赋值1) 2) 3) 4) 5) 6) 7)8) 9) 10) 11) 2、如何判断一个二元关系是否具有自反性、反自反性、对称性、反对称性以与传递性（给出一种方法即可）。3、设集合A=1,2,3,A上关系R1，R2,R3，R4，.判断其各有哪些性质(用二进制码依次对是否具有自反、反自反、对称、反对称、传递性质进行标示)：R1=, , ;R2=, , ;R3=, ;R4=, , , , , ;R5=, , ;R6=, , , , ;.4、判断以下f、g、h是否为从A到B的函数，若是，再判断是否是单射、满射或双射；若不是，请说明理由。1) A=1,2,3,4,5，B=6,7,8,9,10，f=, , , , 。2) A=1,2,3,4,5，B=6,7,8,9,10，g=, , , 。3) A=1,2,3,4,5，B=6,7,8,9,10，h=, , , , , 。4) A=B=R(实数集)， f(x)=x2-x。5) A=B=R(实数集)， f(x)=x3。6) A=B=R(实数集)， f(x)=。5给定两个图G1，G2（如以下图所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由（2）若是欧拉图，请写出一条欧拉回路11 / 11