离散数学AB卷
离散数学黄金AB卷
A卷
一、选择题：（30分）
1、取个体域为整数集，给定下列公式
（1）?x?y（x*y=0）
（2）?x?y（x*y=1）
（3）?y?x（x*y=2）
（4）?x?y?z（x–y = z）
（5）x–y = - y + x
（6）?x?y（x*y = y）
（7）?x（x*y= x）
（8）?x?y（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）若X∩S5 = ?，则A | ； | ； | ； |
（2）若X?S4 但X∩S2 = ?，则B | |||
（3）若X?S1 但X?S3，则C | |||
； | |||
（4）若X - S3= ?，则D | ； | ||
（5）若X?S3 但X?S1，则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，则；如果R是数的小于等于关系，则B；如果R=Es，则C 。
（2）设有序对<x+2，4> 与有序对<5，2x+y>相等，则
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；⑩-2
4、设S=<1，2，3，4>，R为S上的关系，其关系矩阵
是?1?1??0??1000000001?0??，1??0?
；则（1）R的关系表达式是A
（2）domR=B | ；ranR=C | ； |
（3）R?R 中有D | 个有序对； | |
（4）R-1 的关系图中有E | 个环。 | |
A：①｛<1，1>，<1，2>，<1，4>，<4，1>，
<4，3>｝；
②｛<1，1>，<1，4>，<2，1>，<4，1>，<3，
4>｝；
B、C：
③｛1，2，3，4｝；④｛1，2，4｝；⑤｛1，4｝；⑥｛1，3，4｝；
D、E：
⑦1；⑧3；⑨6；⑩7
5、在有理数集合Q上定义二元运算*，?x，y∈Q有
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：⑧所有的元素都有逆元；⑨只有唯一的逆元；
-1⑩?x∈Q，x?1时，有逆元x。
6、下图给出一个格L，则
（1）L 是A | 元格； | ，a 的补元是D | ，1 的补元是E | 。 |
（2）L 是B | ； | |||
（3）b 的补元是C | ||||
A：①5；②6；
B：③分配格；④有补格；⑤布尔格；⑥以上都不对；
C、D、E：
⑦不存在；⑧c和d；⑨0；⑩c；
7、6个顶点11条边的所有可能的非同构的连通的简单的非平面图有个，
其中有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）（p∧q）→（s∧?r）
（2）（p∧?q∧r∧?s）∨(s→?q)
（3）（p∧q∧r）?（?p∨?s）
那么，（1）的真值为 ；（2）的真值为 ；（3）的真值为 ；
2、已知命题公式A含有3个命题变项，其成真赋值为000，010，100，110。
为 | 则A 的主析取范式为 | ，主合取范式 |
。 3、设S=｛1，2，3｝，定义S×S 上的等价关系R， | ||
?<a，b>，<c，d>∈S×S有：<a，b>～<c，d>?a
+d = b + c
则由R产生了S×S的一个划分。在该划分中共有 个划分块，
其中最大的块有 个元素，并且含有元素 。最小的划分块有
块，
每块含有 个元素。
4、设V1=<｛1，2，3｝，?，1>，其中x?y表示取x和y之中较大的数，V2=<｛5，6｝，*，6>，其中x*y表示取x和y之中较小的数。
（1）V1含有 个子代数，其中平凡的真子代数有 个；
V2含有个平凡的子代数。
（2）积代数V1×V2 中有 | 个元素，其幺元是 | 。 |
5、在下面所示的各图中，
6、在下面所示的各图中，是二部图的为在二部图中存在完美匹配的是，它的匹配数是 。
三、判断下列句子中哪些是命题（5分）（1）2是素数
（2）血是黑色的
（3）明年10月1日是晴天
（4）这朵花多好看呀！
（5）X+ y > 5
四、求下面命题公式的主析取范式和主合取范式（6分）（（p∨q）→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｝，<P（A），?>构成群，其中?为集合
的对称差。（6 分） （1）求解方程｛1，3｝?X=｛3，4，5｝； （2）令B=｛1，4，5｝，求由B 生成的循环子群<B>； |
十一、一个n（n≥2）阶无向简单图G中，n为奇数，已知G中有r个奇数度顶点，问G的补图G中有几个奇数度顶点？（5分）
十二、画出度数列为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、
主析取范式为 m0∨m2∨m4∨m6；
主合取范式为M1∧M3∧M5∧M7；
3、
5；3；<1，1>，<2，2>，<3，3>；2；1；4、
（1）4；2；2；
（2）6；<1，6>；
5、
（c）、（e）为欧拉图；
（b）、（c）、（d）、（e）、（f）为哈密顿图；
6、
二部图的为（c）、（d）、（e）；完美匹配的是（d）
；3；三、是命题：（1）、（2）、（3）；不是命题（4）、（5）；
四、主析取范式：m2∨m4∨m5∨m6∨m7；
或者：（p∧q∧?r）∨（p∧?q∧?r）∨（?p∧q∧?r）∨（p∧q∧r）∨（p∧?q∧r）主合取范式：M0∧M1∧M3；
或者：（p∨q∨r）∧（p∨q∨?r）∧（p∨?q∨?r）
五、
p：甲盗窃了录音机；q：乙盗窃了录音机；r：作案时间发生在午夜前；
s：乙的证词正确；t：午夜时屋里灯光灭；
则前提为：
p∨q；p→?r；s→?t；?s→r；t；
推理过程：
（1）t 前提
（2）s→?t 前提
（3）?s（1）（2）
（4）?s→r前提
（5）r （3）（4）
（6）p→?r 前提
（7）?p （5）（6）
（8）p∨q 前提
（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相等；
?x?y（p（x，y）→q（x，y））
七、
八、f：Z→N，f（x）=?
?2x,x?0,?2x?1,x?0,?
九、
十、
（1）由于<P（A），?>构成群，群方程ax=b在群中有唯一解
x=a-1b；
方程｛1，3｝?X=｛3，4，5｝，有
X=｛1，3｝-1?｛3，4，5｝=｛1，3｝?｛3，4，5｝=｛1，4，5｝
（2）由于对任何B∈P（A）有B?B=?，因此Bn=B（n为奇数）或者Bn=?
（n为偶数）；所以，由B生成的循环子群为｛｛1，4，5｝，?｝
十一、
对于n个顶点的完全图，n个顶点的度数均为n-1，由于n为奇数，正
好n-1为偶数；由于G中有r个奇数度顶点，所以，补图G中有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）圆的面积等于半径的平方与?的乘积
B
以上10个语句中，是简单命题的为A，是复合命题的为
，
是真命题的为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 上可定义个不同的二元关系，其中
个偏序关系，Is 是。
A、B、C：
①1；②2；③3；④4；⑤8；⑥16
D：
⑦等价关系但不是偏序关系；⑧偏序关系但不是等价关系；
⑨等价关系和偏序关系；⑩既不是等价关系也不是偏序关系；
3、设S=｛1，2，…，9，10｝，?是S上的整除关系，则<S,?>的哈斯图是，其中最大元是B ，最小元是C ，最小上界是D ，最大下界是E 。A：①一棵树；②一条链；③以上都不对；
B、C、D、E：
④?；⑤1；⑥10；⑦6，7，8，9，10；⑧6；⑨0；⑩不存在
4、设Z+=｛x|x∈Z∧x>0｝
，*表示求两个数的最小公倍数的运算，则
（1）4*6=A | ； | ，零元是D | ； |
（2）*在Z+上B | ； | ||
（3）对于*运算的幺元是C | |||
（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｝，n≥2，ai∈R，i=1，2，…，n，
?ai，aj∈S2，有ai?aj=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的最短路径的权为；b到g的最短路径的权为；
A、B、C、D：
①4；②5；③6；④7；⑤8；⑥9；⑦10；
7、（1）非同构的无向的4阶自补图有
（2）非同构的无向的5阶自补图有B 个；
A、B：①0；②1；③2；④3；
二、填空题：（20分）
1、给定命题公式如下：（?p→q）→（p∨?q）
该命题公式的主析取范式中含极小项的个数为 | ，主合取范式中含 | |||
极大项的个数为 | ，成真赋值个数为 | ，成假赋值个数 | ||
为 | 。 | |||
2、对于下面的语句，
（1）只要4＜3，就有3＞2。真值是。
（3）只有4＜3，才有3＞2。真值是。
（6）4≥3仅当3≤2。真值是。
。（7）4＜3当且仅当3＞2。真值是
3、下列命题
（1）???；（2）???；（3）??｛?｝；（4）??｛?｝正确的是 ；错误的是 。
4、设A、B为集合，
（1）A–B = B，成立的充分必要条件是 ；
（2）A–B = B - A，成立的充分必要条件是 ；
（3）A∪B= A∩B，成立的充分必要条件是 ；
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分）
（p∧q）∨r
五、指出下列各合式公式中的指导变项、量词的辖域、个体变项的自
由出现和约束出现。（6分）
（1）?x（F（x）→?yH（x，y））
（2）?xF（x）∧G（x，y）
六、计算以下幂集（6分）
（1）P（?）；（3）P（｛?，｛?｝｝）；
七、设A=｛1，2，3｝，求出A上的所有的等价关系（4分）
八、设S=｛1，2，…，9，10｝，问下面定义的二元运算*是否为S上的二元运算？（
（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的个数，其中x≤p≤y。
九、设<B，∧，∨，′，0，1>是布尔代数，
（1）a，b∈B，公式f为b∧（a∨（a′∧（b∨b′）））,在B中化简f；
（2）在B中等式（a∧b′）∨（a′∧b）=0成立的条件是什么？（5分）
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是偶数；p∧q；
（2）p：李芳学过英语；q：李芳学过日语；可兼或；p∨q；
（3）p：小王是游泳冠军；q：小王是百米赛跑冠军；可兼或；p∨q；（4）p：小王现在在宿舍；q：小王现在在图书馆；不可兼或；?
（p?q）；
（5）p：明天天气好；q：我们去郊游；（p?q）∧（?p??q）；
（6）p：你爱我；q：我就嫁给你；p?q；
主析取范式为：m7∨m6∨m5∨m3∨m1；
主合取范式为：M0∧M2∧M4；
五、（1）在?yH（x，y）中，指导变项y、?量词的辖域H（x，y）、个
体变项的自由出现x和约束出现y；在整个公式中，指导变项x、?量词的辖域（F（x）→?yH（x，y））、约束出现x、y；
（2）在?xF（x）中，指导变项x、?量词的辖域F（x）、约束出现x；在G（x，y）中，自由出现x、y；
六、（1）P（?）=｛?｝；
（2）P（｛?，｛?｝｝）=｛?，｛?｝，｛｛?｝｝，｛?，｛?｝｝｝
七、由集合A的所有5中划分来确定其等价关系。
（1）IA=｛<1，1>，<2，2>，<3，3>｝
（2）EA=｛<1，1>，<2，2>，<3，3>，<1，2>，<2，1>，<1，3>，<3，1>，<2，3>，<3，2>｝ （3）R1={<1，2>，<2，1>}∪IA
（4）R1={<1，3>，<3，1>}∪IA
（5）R1={<2，3>，<3，2>}∪IA
八、
（1）是
（2）不是
（3）不是
（4）是
（5）不是
九、
（1）b∧（a∨（a′∧（b∨b′）））=b∧（a∨（a′∧1））=b∧（a∨a′）=b∧1=b
（2）因为（a∧b′）∨（a′∧b）=0，所以a∧b′=0，a′∧b=0，而对a∧b′求补可以得到a′∨b=1，由a′∧b=0和a′∨b=1可知，b与a′为补元，而a与a′为补元，由布尔代数补元的唯一性，得到a=b。
十、
十一、
设v1、v2、v3、v4、v5分别表示张、王、李、赵、陈，u1、u2、u3分别表示物理组、化学生物组。在3中情况下作出其相应的二部图为G1、G2、G3，
G1中满足t=2的t条件，能选出；
G2不满足t条件，但满足相异性条件，能选出；
G3不能；
十二、
因篇幅问题不能全部显示，请点此查看更多更全内容