离散数学AB卷.doc

离散数学黄金AB卷A卷一、选择题：（30分）1、取个体域为整数集，给定下列公式（1）xy（x*y=0）（2）xy（x*y=1）（3）yx（x*y=2）（4）xy z（x y = z）（5）x y = - y + x（6）xy（x *y = y）（7）x（x*y = x）（8）xy（x + y = 2y）在上面的公式中，真命题的为A ，假命题的为B 。A：（1）、（3）、（4）、（6）；（3）、（4）、（5）； （1）、（3）、（4）、（5）；（3）、（4）、（6）、（7）B：（2）、（3）、（6）；（2）、（6）、（8）； （1）、（2）、（6）、（7）；（2）、（6）、（8）、（7）2、设S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5。确定在以下条件下X可能与S1,S5中哪个集合相等。（1）若XS5 = ，则A ；（2）若XS4但XS2 = ，则B ；（3）若XS1但XS3，则C ；（4）若X - S3= ，则D ；（5）若XS3但XS1，则E ；A、B、C、D、E：X=S2或者S3；X= S4或者S5；X=S1，S2或者S4；X与其中任何集合都不等；X=S2；X=S5；X=S3或者S5；X=S2或者S4；3、（1）设S=1，2，R为S上的二元关系，且xRy。如果R=Is，则A ；如果R是数的小于等于关系，则B ；如果R=Es，则C 。（2）设有序对 与有序对相等，则x=D ，y=E 。A、B、C：x与y可任意选择1或2；x=1，y=1；x=1，y=1或2；x=y=2；x=2，y=2；x=y=1或x=y=2；x=1，y=2；x=2，y=1；D、E：3；9； -24、设S=，R为S上的关系，其关系矩阵是，则（1）R的关系表达式是A ；（2）domR=B ；ranR=C ；（3）RR中有D 个有序对；（4）R-1的关系图中有E 个环。A：，；，；B、C：1，2，3，4；1，2，4；1，4；1，3，4；D、E：1；3；6；75、在有理数集合Q上定义二元运算*，x，yQ有 x * y = x + y - xy则（1）2*（-5）=A ，7*1/2 = B 。（2）*在Q上是C ；（3）关于*的幺元是D ；（4）Q中满足E ；A、B：4；7；-13；C：可结合的；不可结合的；D：1；0；E：所有的元素都有逆元；只有唯一的逆元；xQ，x1时，有逆元x-1。6、下图给出一个格L，则（1）L是A 元格；（2）L是B ；（3）b的补元是C ，a的补元是D ，1的补元是E 。A：5；6；B：分配格；有补格；布尔格；以上都不对；C、D、E：不存在；c和d；0；c；7、6个顶点11条边的所有可能的非同构的连通的简单的非平面图有A 个，其中有B 个含子图K33，有C 个含与K5同胚的子图。A、B、C：1；2；3；4；5；6；7；8；二、填空题：（20分）1、设p=1，q=0，r=1，s=0，有下列命题公式（1）（pq）（sr）（2）（pqrs）(sq)（3）（pqr）（ps）那么，（1）的真值为 ；（2）的真值为 ；（3）的真值为 ；2、已知命题公式A含有3个命题变项，其成真赋值为000，010，100，110。则A的主析取范式为 ，主合取范式为 。3、设S=1，2，3，定义SS上的等价关系R，SS有：a + d = b + c则由R产生了SS的一个划分。在该划分中共有 个划分块，其中最大的块有 个元素，并且含有元素 。最小的划分块有 块，每块含有 个元素。4、设V1=，其中xy表示取x和y之中较大的数，V2=，其中x*y表示取x和y之中较小的数。（1）V1含有 个子代数，其中平凡的真子代数有 个；V2含有 个平凡的子代数。（2）积代数V1V2中有 个元素，其幺元是 。5、在下面所示的各图中， 为欧拉图， 为哈密顿图。6、在下面所示的各图中，是二部图的为 ，在二部图中存在完美匹配的是 ，它的匹配数是 。三、判断下列句子中哪些是命题（5分）（1）2是素数（2）血是黑色的（3）明年10月1日是晴天（4）这朵花多好看呀！（5）X + y 5四、求下面命题公式的主析取范式和主合取范式（6分）（pq）r）p 五、一公安人员审查一件盗窃案，已知的事实如下：（1）甲或乙盗窃了录音机（2）若甲盗窃了录音机，则作案时间不能发生在午夜前（3）若乙的证词正确，则午夜时屋里灯光未灭（4）若乙的证词不正确，则作案时间发生在午夜前（5）午夜时屋里灯光灭了推理证明，谁盗窃了录音机。（6分）六、将下列语句用谓词表达式符号化（4分）（1）如果2大于3，则2大于4（2）没有不吃饭的人（3）有些人喜欢所有的花（4）凡是对顶角都相等七、设A=1，2，3，11，12，R为A上整除关系，画出哈斯图。（6分）八、对于给定集合A和B，构造从A到B的双射函数。（4分） A=Z，B=N，其中Z，N分别表示整数集和自然数集；九、设R的关系图如所示，试给出r（R）、s（R）、t（R）的关系图。（4分）十、设A=1，2，3，4，5，构成群，其中为集合的对称差。（6分）（1）求解方程1，3X=3，4，5；（2）令B=1，4，5，求由B生成的循环子群；十一、一个n（n2）阶无向简单图G中，n为奇数，已知G中有r 个奇数度顶点，问G的补图中有几个奇数度顶点？（5分）12、 画出度数列为1，1，1，1，2，2，4的所有非同构的7阶无向树。（4分）A卷答案一、选择题：（30分）1、A：；B：；2、A：；B：；C：；D：；E：；3、A：；B：；C：；D：；E：；4、A：；B：；C：；D：；E：；5、A：；B：；C：；D：；E：；6、A：；B：；C：；D：；E：；7、A：；B：；C：；二、填空题：（20分）1、（1）1；（2）1；（3）0；2、主析取范式为 m0m2m4m6；主合取范式为 M1M3M5M7；3、5；3；，；2；1；4、（1）4；2；2；（2）6；5、（c）、（e）为欧拉图；（b）、（c）、（d）、（e）、（f）为哈密顿图；6、二部图的为（c）、（d）、（e）；完美匹配的是（d）；3；三、是命题：（1）、（2）、（3）；不是命题（4）、（5）；四、主析取范式：m2m4m5m6m7；或者：（pqr）（pqr）（pqr）（pqr）（pqr）主合取范式：M0M1M3；或者：（pqr）（pqr）（pqr）五、p：甲盗窃了录音机；q：乙盗窃了录音机；r：作案时间发生在午夜前；s：乙的证词正确；t：午夜时屋里灯光灭；则前提为：pq；pr；st；sr；t；推理过程：（1）t 前提（2）st 前提（3）s （1）（2）（4）sr 前提（5）r （3）（4）（6）pr 前提（7）p （5）（6）（8）pq 前提（9）q （7）（8）结论为：乙盗窃了录音机六、 （1）p（x，y）：表示x大于y；a=2；b=3；c=4；p（a，b）p（a，c）（2）m（x）：x是人； e（x）：x吃饭；x（m（x）e（x）或者（x（m（x）e（x）（3）m（x）：x是人；h（x）：x是花；p（x，y）：x喜欢y；x（m（x）y（h（y）p（x，y）（4）p（x，y）：x与y是对顶角，q（x，y）：x与y相等；xy（p（x，y）q（x，y）七、8、 f：ZN，f（x）=9、十、（1）由于构成群，群方程ax=b在群中有唯一解x=a-1b；方程1，3X=3，4，5，有X=1，3-13，4，5=1，33，4，5=1，4，5（2）由于对任何BP（A）有BB=，因此Bn=B（n为奇数）或者Bn=（n为偶数）；所以，由B生成的循环子群为1，4，5，十一、对于n个顶点的完全图，n个顶点的度数均为n-1，由于n为奇数，正好n-1为偶数；由于G中有r 个奇数度顶点，所以，补图中有r个奇数度顶点。十二、B卷一、选择题：（30分）1、给定语句如下：（1）15是素数（2）10能被2整除，3是偶数（3）你下午有会吗？（4）2x+3 0（5）2是素数或是合数（6）这个男孩真勇敢呀！（7）如果2+2=6，则5是奇数（8）只有4是偶数，3才能被2整除（9）明年5月1日是晴天（10）圆的面积等于半径的平方与的乘积以上10个语句中，是简单命题的为A ，是复合命题的为B ，是真命题的为C ，是假命题的为D ，真值待定（真值客观存在，只是现在不知道）的命题为E 。A：（1）、（4）、（8）（4）、（6）、（9）、（10）（1）、（9）、（10）B：（3）、（10）（2）、（5）、（7）、（8）（7）、（8）C：（2）、（5）、（9）、（10）（7）、（8）、（10）（2）、（9）、（10）（5）、（7）、（8）、（10）D：（1）、（2）、（8）（1）、（2）（1）、（5）E：（4）、（9）（9）（7）、（8）2、设S=1，2，则S上可定义A 个不同的二元关系，其中B 个等价关系，C 个偏序关系，Is是D 。A、B、C：1；2；3；4；8；16D：等价关系但不是偏序关系；偏序关系但不是等价关系；等价关系和偏序关系；既不是等价关系也不是偏序关系；3、设S=1，2，9，10，是S上的整除关系，则的哈斯图是A ，其中最大元是B ，最小元是C ，最小上界是D ，最大下界是E 。A：一棵树；一条链；以上都不对；B、C、D、E：；1；10；6，7，8，9，10；6；0；不存在4、设Z+=x|xZx0，*表示求两个数的最小公倍数的运算，则（1）4*6=A ；（2）*在Z+上B ；（3）对于*运算的幺元是C ，零元是D ；（4）在Z+中E ；A：24；12；B：只满足交换率；只满足结合律；满足交换率、结合律和幂等律；C、D：0；1；不存在；E：不存在逆元；只有唯一的逆元5、对以下定义的集合和运算判断它们是不是代数系统。如果是，是哪一种？（1）S1=1，1/2，2，1/3，3，1/4，4，*为普通乘法，则S1是A ；（2）S2=a1，a2，an，n2，aiR，i=1，2，n， ai，ajS2，有aiaj=ai，则S2是B ；（3）S3=0，1，*为普通乘法，则S3是C ；（4）S4=1，2，3，6，为整除关系，则S4是D ；（5）S5=0，1，+、*分别为模2加法和乘法，则S5是E 。A、B、C、D、E：半群，但不是独异点；是独异点，但不是群；群；环，但不是域；域；格，但不是布尔代数；布尔代数；代数系统，但不是以上7种；不是代数系统；6、给定有向带权图如图所示，图中b到a的最短路径的权为A ；b到d的最短路径的权为B ；b 到e的最短路径的权为C ；b到g的最短路径的权为D ；A、B、C、D：4；5；6；7；8；9；10；7、（1）非同构的无向的4阶自补图有A 个；（2）非同构的无向的5阶自补图有B 个；A、B：0；1；2；3；二、填空题：（20分）1、给定命题公式如下：（pq）（pq）该命题公式的主析取范式中含极小项的个数为 ，主合取范式中含极大项的个数为 ，成真赋值个数为 ，成假赋值个数为 。2、对于下面的语句，（1）只要43，就有32。真值是 。（3）只有43，才有32。真值是 。（6）43仅当32。真值是 。（7）43当且仅当32。真值是 。3、下列命题（1）；（2）；（3）；（4）正确的是 ；错误的是 。4、设A、B为集合，（1）A B = B，成立的充分必要条件是 ；（2）A B = B - A，成立的充分必要条件是 ；（3）AB = AB，成立的充分必要条件是 ；5、设S=a，b，则S上可以定义 个二元运算，其中有4个运算f1，f2，f3，f4，其运算表如下：则只有 满足交换律， 满足幂等律， 有幺元， 有零元。6、下列各组数中，哪些 能构成无向图的度数列？哪些 能构成无向简单图的度数列？（1）1，1，1，2，3；（2）2，2，2，2，2；（3）3，3，3，3；（4）1，2，3，4，5；（5）1，3，3，3；三、将下列命题符号化（6分）（1）2是素数和偶数（2）李芳学过英语或日语（3）小王是游泳冠军或者百米赛跑冠军（4）小王现在在宿舍或者在图书馆（5）如果明天天气好，我们去郊游。否则，不去郊游（6）你爱我，我就嫁给你四、利用真值表求主析取范式和主合取范式（4分）（pq）r五、指出下列各合式公式中的指导变项、量词的辖域、个体变项的自由出现和约束出现。（6分）（1）x（F（x）yH（x，y）（2）x F（x）G（x，y）六、计算以下幂集（6分）（1）P（）；（3）P（，）；七、设A=1，2，3，求出A上的所有的等价关系（4分）八、设S=1，2，9，10，问下面定义的二元运算*是否为S上的二元运算？（5分）（1）x*y = gcd（x，y），x与y的最大公约数；（2）x*y = lcm（x，y），x与y的最小公倍数；（3）x*y =大于等于xy的最小整数；（4）x*y =max（x，y）；（5）x*y =质数P的个数，其中xpy。九、设是布尔代数，（1）a，bB，公式f为b（a（a（bb）,在B中化简f；（2）在B中等式（ab）（ab）=0 成立的条件是什么？（5分）十、画出3个顶点2条边的所有可能非同构的有向简单图；（4分）十一、某中学有3个课外小组：物理组、化学组、生物组。今有张、王、李、赵、陈5名同学。若已知：（1）张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员；（2）张为物理组成员，王、李、赵为化学组成员，王、李、赵、陈为生物组成员；（3）张为物理组和化学组成员，王、李、赵、陈为生物组成员；问在以上3中情况下能否各选出3名不兼职的组长？（5分）十二、求带权为2、3、5、7、8、8的最优二元树；（5分）B卷答案一、选择题：（30分）1、 A：；B：；C：；D：；E：；2、 A：；B：；C：；D：；3、 A：；B：；C：；D：；E：；4、 A：；B：；C：；D：；E：；5、 A：；B：；C：；D：；E：；6、 A：；B：；C：；D：；7、 A：；B：；二、填空题：（20分）1、极小项的个数3；极大项的个数1；3；1；2、（1）1；（2）0；（3）0；（4）0；3、正确的是（1）、（3）、（4）；错误的是（2）；4、（1）A = B =；（2）A = B；（3）A = B；5、16；f1、f2、f3；f4；f2；f1；6、（1）、（2）、（3）、（5）；（1）、（2）、（3）；三、将下列命题符号化（6分）（1）p：2是素数；q：2是偶数；pq；（2）p：李芳学过英语；q：