2024年自学考试离散数学试题汇编.doc

全国4月高等教育自学考试
离散数学试题
课程代码：02324
一、单项选择题（本大题共15小题，每题1分，共15分）
在每题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未选均无分。
1．下列命题公式为重言式的是（ ）
A．p→ (p∨q) B．(p∨┐p)→q C．q∧┐q D．p→┐q
2．下列语句中不是命题的只有（ ）
A．这个语句是假的。B．1+1=1.0 C．飞碟来自地球外的星球。 D．凡石头都可练成金。
3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是
A．┐p∧q B．┐p→q C．┐p→┐q D．p→┐q
4．下列等价式正确的是（ ）
A．┐┐A B．
C．┐┐A D．
5．在公式中变元y是（ ）
A．自由变元B．约束变元C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元
6．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（ ）
A．自反关系 B．反自反关系
C．对称关系 D．传递关系
7．设集合X为人的全体，在X上定义关系R、S为R={<a，b|a，b∈X∧a是b的爸爸}，S={<a，b>|a，b∈X∧a是b的母亲}，那么关系{<a，b>|a，b∈x∧ a是b的祖母}的体现式为（ ）
A．RS B．R-1S
C．SR D．RS-1
8．设A是正整数集，R={(x，y)|x，y∈A∧x+3y=12}，则R∩ ({2，3，4，6}×{2，3，4，6})=（ ）
A． O/
B．{<3，3>}
C．{<3，3>，<6，2>}
D．{<3，3>，<6，2>，<9，1>}
9．下列式子不正确的是（ ）
A．(A-B)-C=(A-C)-B B．(A-B)-C=A-(B∪C)
C．(A-B)-C=(A-C)-(B-C) D．A-(B∪C)=(A-B)∪ C
10．下列命题正确的是（ ）
A．{l，2}{{1，2}，{l，2，3}，1}
B．{1，2}{1，{l，2}，{l，2，3}，2}
C．{1，2}{{1}，{2}，{1，2}}
D．{1，2}∈{1，2，{2}，{l，2，3}}
11．在下列代数系统中，不是环的只有（ ）
A．<Z，+，*)，其中Z为整数集，+，*分别为整数加法和乘法。
B．(Q，+，*)，其中Q为有理数集，+，*分别为有理数加法和乘法。
C．<R，+，*>，其中R为实数集，+为实数加法，a*b=a+2b。
D．<Mn (R)，+，*>，其中Mn(R)为实数集n×n阶矩阵结合，+，*是矩阵加法和乘法。
12．下列整数集对于整除关系都组成偏序集，而能组成格的是（ ）
A．{l，2，3，4，5} B．{1，2，3，6，12}
C．{2，3，7} D．{l，2，3，7}
13．结点数为奇数且所有结点的度数也为奇数的连通图必然是（ ）
A．欧拉图 B．汉密尔顿图
C．非平面图 D．不存在的
14．无向图G是欧拉图当且仅当G是连通的且（ ）
A．G中各顶点的度数均相等
B．G中各顶点的度数之和为偶数
C．G中各顶点的度数均为偶数
D．G中各顶点的度数均为奇数
15．平面图(如下)的三个面的次数分别是（　　　）

A．11，3，4 B．11，3，5
C．12，3，6 D．10，4，3
二、填空题（本大题共10小题，每题2分，共20分）
请在每题的空格中填上正确答案。错填、不填均无分。
16．求一个公式的主析取或主合取范式的措施，有______________法和______________法。
17．给定谓词合式公式A，其中一部分公式形式为()B(x)或(x)B(x)，则量词，背面所跟的x称为______________，而称B为对应量词的______________。
18．设X，U，V，Y都是实数集，f1：X→U，且fl(x)→ex； f2：U→V，且f2(u)＝u (1+u)；f3：V→Y，且f3(v)=cosv。那么f3f2f1的定义域是______________，而复合函数(f3f2f1)(x)= ______________。
19．集合X={a，b，c，d}上二元关系R={<a，b>，<a，c>，<a，d>，<b，c>，<b，d>， <e，d>}，则R的自反闭包r(R)= ______________，对称闭包s(R)= ______________。
20．已知G=<{l，-1，i，-i}，·>(其中i=，是数的乘法)是群，则-l的阶是______________；i的阶是______________。
21．对代数系统<S，*>，其中*是S上的二元运算，若a，b∈S，且对任意的x∈S，都有a*x=x*a=x，b*x=x*b=b，则称a为运算“*”的______________，称b为运算“*”的______________。
22．设<S，*>是群，则<S，*>满足结合律和______________；若｜S｜>l，S中不也许有______________。
23．写出如右有向图的一条初级回路：______________，其长度是______________。
24．一个______________且______________的无向图称为树。
25．在简单无向图G=<V，E>中，假如V中的每个结点都与其他的所有结点邻接，则该图称为______________，假如V有n个结点，那么它还是______________度正则图。

三、计算题(本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分)
26．若集合A={a，{b，c}}的幂集为P(A)，集合B={ O/　　　　，{ O/　 }}的幂集为P(B)，
求P(A)∩P(B)。
27．结构命题公式(p→ (q∧ r))→┐p的真值表。
28．求图G＝<V，E>的可达矩阵，其中V＝｛v1,v2,v3,v4｝
E＝｛(v1,v2), (v2,v3), (v2,v4), (v3,v2), (v3,v4), (v3,v1), (v4,v1)｝
29．求下列公式的主析取范式和主合取范式：（P∧Q）∨（┐P∧R）
30．设A＝｛2，3，4，6，8，12，24｝，R为A上整除关系，试画<A，R>的哈斯图，并求A中的最大元，最小元，极大元，极小元。
四、证明题（本大题共3小题，第31、32小题各6分，第33题8分，共20分）
31．设M是偶数集，＋和·是数的加、乘运算，证明<M，＋，·>是一个环。
32．设R是集合X上的二元关系，证明R是X上传递关系当且仅当RRR。
33．设G是简单平面图，G有n个顶点m条边，且m<30，证明G中存在一项点v，　　　　　　d（v）≤4。
五、应用题（本大题共2小题，第34题6分，第35题9分，共15分）
34．判断下面推理是否正确，并证明你的结论。
假如小王今日家里有事，则他不会来开会。假如小张今日看到小王，则小王今日来开会了。小张今日看到小王。因此小王今日家里没事。
35．有6个村庄Vi，i=l，2，…，6欲修建道路使村村可通。现已经有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。

7月全国自考离散数学试题试卷真题
课程代码：02324
一、单项选择题（本大题共15小题，每题1分，共15分）
在每题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未选均无分。
1．下列语句中不是命题的只有（　　　）
A．鸡毛也能飞上天？ B．或重于泰山，或轻于鸿毛。
C．不经一事，不长一智。 D．牙好，胃口就好。
2．从真值角度看，命题公式的所有类型是（　　　）
A．永真式 B．永假式
C．永真式，永假式 D．永真式，永假式，可满足式
3．设M（x）：x是人；F（x）：x要吃饭。用谓词公式体现下述命题：所有的人都要吃饭，其中错误的体现式是（　　　）
A． B．
C． D．
4．下列公式是前束范式的是（　　　）
A． B．
C． D．
5．设论域为整数集，下列真值为真的公式是（　　　）
A． B．
C． D．
6．下列是谓词演算中的合式公式的是（　　　）
A． B．
C． D．
（ ）
．（　　　）
A．B．
C．D．
．（　　　）

8．下列式子正确的是（　　　）
A．（A－B）-C=A-（B∪C） B．A－（B∪C）=（A－B）∪C
C．~（A－B）=~（B－A） D．~（A∩B）A
9．下列集合对所给的运算是封闭的只有（　　　）
A．非零整数集合Z*上的除法运算
B．全体n×n实可逆矩阵集合Mn（R）上的矩阵加法和乘法运算
C．全体n×n实矩阵集合Mn（R）上的矩阵加法和乘法运算
D．A={1，2，…，10}，x*y=LCM（x，y），即x，y最小公倍数
10．设<A，，*>是环，则下列说法不正确的是（　　　）
A．<A，>是互换群 B．<A， *>是半群
C．*对是可分派的 D．对*是可分派的
11．下列四个格，是分派格的是（　　　）

C．D．
．（　　　）
A．B．

12．下列各图是无向完全图的是（　　　）

13．下列各有向图是强连通图的是（　　　）

14．设Ｇ是具备n个结点的无向简单图，若在Ｇ中存在一条汉密尔顿路，则Ｇ中每一对结点的度数之和与n-1的关系为（　　　）
A．不小于 B．不小于等于
C．等于 D．小于
15．设连通平面图Ｇ，共有n个结点，e条边，r个面，则欧拉证明成立的公式是（　　　）
A．e-n+r=2 B．n+r-e=2
C．n-r+e=2 D．n-e-r=2
二、填空题（本大题共10小题，每题2分，共20分）
请在每题的空格中填上正确答案。错填、不填均无分。
16．所谓____是指不能再分解的命题，而复合命题是由某些____通过联结词复合而成的命题。
17．在命题演算中，两个____的合取、析取、条件、双条件均为____。
18．使公式成立的条件是____中不含y，____中不含x。
19．设A={1，2，3，4}，R是A上的二元关系，R={<x,y>|x/y是素数}，则domR=_____;
ranR=____。
20．设无向图Ｇ有n个结点m条边，每个结点的度数为k或k+1，记Nk为度数等于k的结点数，则Nk=_____。假如无向简单图C的结点的度数均为相同的偶数，且m=7，则n=____。
21．设X={1，3，5，9，15，45}，R是X上的整除关系，则R是X上的偏序，其最大元是___，极小元是____。
22．设<>是有界格，a,bL,若ab=0,则a=b=_____；若ab=1,则a=b=____。
23．设e是群G上的幺元，若aG且a2=e,则a-1=____ ,a-2=__________。
24．代数系统<A,。>，其中A为命题公式集合，。为析取运算，则<A，。>中零元素是____，幺元是____。
25．树是不包括_____的___图。
三、计算题（本大题共6小题，第26、27题各4分，第28、29题各5分，第30、31题各6分，共30分）
26．假如论域是集合{a,b,c}，试消去下面公式中的量词：
27．求公式（的主析取范式。
28．设A={a,b,c},A上二元关系R={<a,a>,<a,c>,<b,a>},用关系矩阵法求最小的自然数m,n,m<n使Rm=Rn。
29．依照下列条件假如能画则请画出一个欧拉图，假如不能画则请阐明理由。
（1）偶数个顶点，偶数条边
（2）奇数个顶点，奇数条边
（3）偶数个顶点，奇数条边
（4）奇数个顶点，偶数条边
30．下列各整数集合对于整除关系“|”都组成偏序集，判断哪些偏序集能组成格？并阐明理由。
1)L={1,2,3,4,5}
2) L={1,2,3,6,12}
3)L={1,2,3,4,6,9,12,18,36}
4)L={1,2,22,23,…,2n}
31．设A={2，3，5，12，19}，等价关系R={<x,y>|x, (mod 3)},写出各元素的等价类，并求A/R。
四、证明题（本大题共3小题，第32、33题各6分，第34题8分，共20分）
32．用等价变换法证明：是永真式。
33．若无向图G是欧拉图，G中是否存在割边？为何？
34．设A是一个集合，X=P（A），R是X上元素之间的包括关系，试证明<X,R>是偏序集。（注：P（A）为A的幂集）
五、应用题（本大题共2小题，第35题6分，第36题9分，共15分）
35．设有n个村庄要修路，（1）若要使所有村庄之间都有通路，问需在两村之间最少修几条路？（2）若要使任意两村庄之间有一条直接的路，则最少修几个路？（3）若修一条连接所有村庄的环路，问有多少种修路方案？
36．设有推理：
(a)没有不守信用的人是可信赖的；
(b)有些能够信赖的人是受过教育的人；
(c)因此有些受过教育的人是守信用的。
试结构推理的证明，要求把推理的前提，结论符号化为谓词形式，并写出推理过程。（个体域：人的集合）
提示：设F（x）表示x是守信用的人；G（x）表示x是可信赖的人；H（x）表示x是受过教育的人。

全国4月高等教育自学考试
离散数学试题
课程代码：02324
一、单项选择题（本大题共15小题，每题1分，共15分）
在每题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未选均无分。
1．下列命题公式中不是重言式的是（　　　）
A．p→(q→r) B．p→(q→p)
C．p→(p→p) D．(p→(q→r))(q→(p→r))
2．下列语句中为命题的是（　　　）
A．这朵花是谁的？ B．这朵花真漂亮啊！
C．这朵花是你的吗？ D．这朵花是他的。
3．设个体域是整数集，则下列命题的真值为真的是（　　　）
A．yx(x·y=1) B．xy (x·y≠0)
C．xy (x·y=y2) D．yx(x·y=x2)
4．有关谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是（　　　）
A．（x）的辖域是（y）（P（x,y）∧Q(y,z)）
B．z是该谓词公式的约束变元
C．（x）的辖域是P（x,y） D．x是该谓词公式的约束变元
5．设论域D={a,b}，与公式xA（x）等价的命题公式是（　　　）
A．A（a）∧A（b） B．A（a）→A（b）
C．A（a）∨A（b） D．A（b）→A（a）
6．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是（　　　）
A． B．
C． D．
7．设A={Ø}，B=P（P（A）），如下不正确的式子是（　　　）
A．{{Ø }，{{Ø }}，{Ø ，{Ø }}}包括于B B．{{{Ø }}}包括于B
C．{{Ø ，{Ø }}}包括于B D．{{Ø }，{{Ø ，{Ø }}}}包括于B
8．设Z是整数集，E={…，-4，-2，0，2，4，…}，f：Z→E，f（x）=2x，则f（　　　）
A．仅是满射 B．仅是入射
C．是双射 D．无逆函数
9．设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，〈3，1〉，〈4，2〉}，则S-1R-1的运算成果是（　　　）
A．{〈4，1〉，〈2，3〉，〈4，2〉} B．{〈2，4〉，〈2，3〉，〈4，2〉}
C．{〈4，1〉，〈2，3〉，〈2，4〉} D．{〈2，2〉，〈3，1〉，〈4，4〉}
10．设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（　　　）
A．矛盾式 B．重言式
C．可满足式 D．公式p∧q
11．在实数集合R上，下列定义的运算中不可结合的是（　　　）
A．a*b=a+b+2ab B．a*b=a+b
C．a*b=a+b+ab D．a*b=a-b
12．下列集合有关所给定的运算成为群的是（　　　）
A．已给实数a的正整数次幂的全体，且a{0，1，-1}，有关数的乘法
B．所有非负整数的集合，有关数的加法
C．所有正有理数的集合，有关数的乘法
D．实数集，有关数的除法
13．设无向图中有6条边，有一个3度顶点和一个5度顶点，其他顶点度为2，则该图的顶点数是（　　　）
A．3 B．4
C．5 D．6
14．下列各图中既是欧拉图，又是汉密尔顿图的是（　　　）

A． B． C． D．
15．设无向图G的边数为m，结点数为n，则G是树等价于（　　　）
A．G连通且m=n+1 B．G连通且n=m+1
C．G连通且m=2n D．每对结点之间最少有一条通路
二、填空题（本大题共10小题，每题2分，共20分）
请在每题的空格中填上正确答案。错填、不填均无分。
16．不能再分解的命题称为____________，最少包括一个联结词的命题称为____________。
17．在命题演算中，五个联结词的含义是由其____________表唯一确定的，而不是由其类似的____________语言的含义确定。
18．使公式（x）（y）（A（x）→B（y））（（x）A（x）→（y）B（y））成立的条件是____________不含有y，____________不含有x。
19．设A为任意集合，请填入适当的运算符，使式子A____________A=Ø；A____________~A=Ø成立。
20．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)}，则domR=____________，ranR=____________。
21．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，Sn}，其中SiA，Si≠Ø，i=1，2，…，n，且____________；深入若____________，则S是集合A的划分。
22．对实数的一般加法和乘法，____________是加法的幂等元，____________是乘法的幂等元。
23．在代数系统〈A，*〉中，A={a}，*是A上二元运算，则该代数系统的单位元是____________，零元是____________。
24．设〈A，≤〉是偏序集，若A中____________都有最小上界和____________则称A有关偏序≤组成格。
25．若一条路中，所有边均不相同，则此路称作____________；若一条路中所有的结点均不相同，则称此路为____________。
三、计算题（本大题共6小题，第26、27小题各4分，第28、29小题各5分，第30、31小题各6分，共30分）
36．试画出结点数为3的（1）强连通图；（2）单向连通图；（3）弱连通图；（4）非连通图。
27．设A={0，1，2，3}，R={〈x,y〉|x,y∈A∧(y=x+1∨y=)}，S={〈x,y〉|x,y∈A∧（x=y+2）}。试求RSR
28．在全体正整数集合Z+中要求∩，∪为：对任意的a,b∈Z+，
a∪b=[a,b]，即求a,b的最小公倍数；
a∩b=(a,b)，即求a,b的最大条约数；
则运算∩，∪满足结合律，互换律和吸取律，于是〈Z+，∩，∪〉是一个格。判断下列集合是否是<Z+，∩，∪>的子格？
1）A={1，2，3，9，12，72}
2）A={1，2，3，12，18}
3）A={5，52，53，…，5n}
4）T=2Z+={2k|k∈Z+}
29．求命题公式（p→q）→（q∨p）的主析取范式。
30．结出命题公式（p∨(p∧q)）∧((p∨q)∧q)的二叉树表示。
31．设A={a,b,c,d}, R={〈a,c〉，〈c,b〉，〈b,a〉，〈a,d〉}，求R，r(R),s(R),t(R)的关系图。
四、证明题（本大题共3小题，第32、33小题各6分，第34小题8分，共20分）
32．设A是非空集合，P（A）是A的幂集，是集合的包括关系，则〈P（A），〉是格，证明：〈P（A），〉是有补格。
33．设〈{a,b},*〉是半群，其中a*a=b，证明：（1）a*b=b*a；（2）b*b=b。
34．若一棵树恰有2个结点的度数为1，则它必是一条欧拉路。
五、应用题（本大题共2小题，第35小题6分，第36小题9分，共15分）
35．设I是整数集，<，>，＝，≤，≥，≠是Ｉ上的二元关系，分别表示小于，不小于、等于、小于等于，不小于等于，不等于，那么这些关系会满足什么性质？试填写下表

自反
反自反
对称
反对称
传递
<

>

=

≤

≥

≠

≤∩≥

≤∪≥

36．设R=，Z是整数集，则：
（1）R对矩阵的加法和乘法组成一个环；
（2）R中存在元素x是右零因子但不是左零因子。

全国7月高等教育自学考试
离散数学试题
课程代码：02324
一、单项选择题（本大题共15小题，每题1分，共15分）
在每题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未选均无分。
1．令P：今日下雪了，Q：路滑，则命题“虽然今日下雪了，不过路不滑”可符号化为（　　　）
A．P→Q B．P∨Q
C．P∧Q D．P∧Q
2．下列命题公式为重言式的是（　　　）
A．Q→（P∧Q） B．P→（P∧Q）
C．（P∧Q）→P D．（P∨Q）→Q
3．下列4个推理定律中，不正确的是（　　　）
A．A（A∧B） B．（A∨B）∧AB
C．（A→B）∧AB D．（A→B）∧BA
4．谓词公式x(P(x)∨yR(y))→Q(x)中量词的辖域是（　　　）
A． B．P（x）
C．(P(x)∨yR(y)) D．P(x), Q(x)
5．设个体域A={a,b}，公式xP(x)∧xS(x)在A中消去量词后应为（　　　）
A．P(x)∧S(x) B．P(a)∧P(b)∧(S(a)∨S(b))
C．P(a)∧S(b) D．P(a)∧P(b)∧S(a)∨S(b)
6．下列选项中错误的是（　　　）
A．ØØ B．Ø∈Ø
C．Ø{Ø} D．Ø∈{Ø}
7．设A={a,b,c,d}，A上的等价关系R={<a, b>, <b, a>, <c, d>, <d, c>}∪IA，则对应于R的A的划分是（　　　）
A．{{a},{b, c},{d}} B．{{a, b},{c}, {d}}
C．{{a},{b},{c},{d}} D．{{a, b}, {c,d}}
8．设R为实数集，函数f：R→R，f(x)=2x，则f是（　　　）
A．满射函数 B．入射函数
C．双射函数 D．非入射非满射
9．设R为实数集，R+={x|x∈R∧x>0}，*是数的乘法运算，<R+，*>是一个群，则下列集合有关数的乘法运算组成该群的子群的是（　　　）
A．{R+中的有理数} B．{R+中的无理数}
C．{R+中的自然数} D．{1，2，3}
10．下列运算中有关整数集不能组成半群的是（　　　）
A．ab=max{a, b} B．ab=b
C．ab=2ab D．ab=|a-b|
11．设Z是整数集，+，分别是一般加法和乘法，则（Z，+，）是（　　　）
A．域 B．整环和域
C．整环 D．含零因子环
12．设A={a, b, c}，R是A上的二元关系，R={<a, a>, <a, b>, <a, c>, <c, a>}，那么R是（　　　）
A．反自反的 B．反对称的
C．可传递的 D．不可传递的
13．设D=<V, E>为有向图，V={a, b, c, d, e, f}, E={<a, b>, <b, c>, <a, d>, <d, e>, <f, e>}是
（　　　）
A．强连通图 B．单向连通图
C．弱连通图 D．不连通图
14．在有n个结点的连通图中，其边数（　　　）
A．最多有n-1条 B．最少有n-1条
C．最多有n条 D．最少有n条
15．连通图G是一棵树，当且仅当G中（　　　）
A．有些边不是割边 B．每条边都是割边
C．无割边集 D．每条边都不是割边
二、填空题（本大题共10小题，每题2分，共20分）
请在每题的空格中填上正确答案。错填、不填均无分。
16．任意两个不一样的小项的合取为________________式，全体小项的析取式必为________________式。
17．公式x(P(x)→Q(x,y)∨zR(y, z))→S(x)中的自由变元为________________，约束变元为________________。
18．设集合M={x|1≤x≤12,x被2整除，x∈Z},N={x|1≤x≤12,x被3整除，x∈Z}，则 M∩N=________________，M∪N=________________。
19．设X={1，2，3}，f：X→X，g：X→X，f={<1, 2>,<2,3>,<3,1>},
g={<1,2>,<2,3>,<3,3>}，则fg=________________，gf=________________。
20．设A={a,b,c}，R是A上的二元关系，且给定R={<a,b>,<b,c>,<c,a>}，则R的自反闭包r(R)= ________________，对称闭包s(R)= ________________。
21．设Q为有理数集，笛卡尔集S=Q×Q，*是S上的二元运算，<a, b>,<x, y>∈S, <a, b>*<x, y>=<ax, y+b>, 则*运算的幺元是________________。<a, b>∈S, 若a≠0，则<a, b>的逆元是________________。
22．设*是集合S上的二元运算，若运算*满足________________且存在________________，则称<S，*>为独异点。
23．令A={a, b, c}，<A, *>是循环群，a是单位元，则b2=________________，c的阶是________________。
24．如下无向图割点是________________，割边是________________。

25．无向图G具备生成树，当且仅当________________。G的所有生成树中________________的生成树称为最小生成树。
三、计算题（本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题8分，共30分）
26．集合A={a, b, c, d, e}上的二元关系R为
R={<a,a>, <a,b>, <a,c>, <a,d>, <a,e>, <b,b>, <b,c>, <b,e>, <c,c>, <c,d>, <c,e>, <d,d>, <d,e>, <e,e>}
（1）写出R的关系矩阵；
（2）判断R是不是偏序关系，为何？
27．利用真值表判断公式（（P∨Q）∧（Q→R））→（P∧R）是否为重言式。

28．给定图G如下所示，（1）写出G的可达矩阵；（2）G中长度为4的路有几条？

29．求下列公式的主析取范式和主合取范式：（P→Q）∧（Q→R）
30．设A为54的因子组成的集合，RA×A，x,y∈A, xRyx整除y。画出偏序集<A,R>的哈斯图，并求A中的最大元，最小元，极大元，极小元。
五、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分）
31．设R是A上的一个自反关系，证明：R是一个等价关系，当且仅当若<a,b>∈R，<a,c>∈R，则<b,c>∈R。
32．设<G，*>是一个群，x∈G，定义：ab=a*x*b，a,b∈G。证明：<G, >也是一个群。
33．设图G是具备6个结点，12条边的无向简单图，证明图G是汉密尔顿图。
五、应用题（本大题共2小题，第34小题8分，第35小题7分，共15分）
34．结构下面推理的证明。
假如今日是星期六，我们就要到颐和园或圆明园去玩。假如颐和园游人太多，我们就不去颐和园玩。今日是星期六，颐和园游人太多，因此我们去圆明园玩。
35．n个城市用k条公路的网络连结。一条公路定义为两个城市间的一条不穿过任何中间城市的道路。任意两个城市之间至多修一条公路。证明假如k>(n-1)(n-2)，则人们总能通过连结的公路，在任何两个城市间旅行。

全国4月自考离散数学试题
课程代码：02324
一、单项选择题(本大题共15小题，每题1分，共15分)
在每题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未选均无分。
1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（　　　）
A.ùP∧Q B.ùP→Q
C.ùP→ùQ D.P→ùQ
2.下列命题联结词集合中，是最小联结词组的是（　　　）
A.{ù， } B.{ù，∨，∧}
C.{ù，∧} D.{∧，→}
3.下列命题为假命题的是（　　　）
A.假如2是偶数，那么一个公式的析取范式惟一
B.假如2是偶数，那么一个公式的析取范式不惟一
C.假如2是奇数，那么一个公式的析取范式惟一
D.假如2是奇数，那么一个公式的析取范式不惟一
4.谓词公式x(P(x)∨$yR(y))→Q(x))中变元x是（　　　）
A.自由变元 B.约束变元
C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元
5.若个体域为整数减，下列公式中值为真的是（　　　）
A.x$y(x+y=0) B.$yx(x+y=0)
C.xy(x+y=0) D.ù$x$y(x+y=0)
6.下列命题中不正确的是（　　　）
A.x∈{x}-{{x}} B.{x}Í{x}-{{x}}
C.A={x}∪x,则x∈A且xÍA D.A-B=ÆÛA=B
7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（　　　）
A.PÉQ B.PÊQ
C.QÉP D.Q=P
8.下列体现式中不成立的是（　　　）
A.A∪(BÅC)=(A∪B) Å (A∪C) B.A∩(BÅC)=(A∩B) Å (A∩C)
C.(AÅB)×C=(A×C) Å (B×C) D.(A-B) ×C=(A×C)-(B×C)
9.半群、群及独异点的关系是（　　　）
A.{群}Ì{独异点}Ì{半群} B.{独异点}Ì{半群}Ì{群}
C.{独异点}Ì{群}Ì{半群} D.{半群}Ì{群}Ì{独异点}
10.下列集合对所给的二元运算封闭的是（　　　）
A.正整数集上的减法运算
B.在正实数的集R+上要求*为a*b=ab-a-b a,b∈R+
C.正整数集Z+上的二元运算*为x*y=min(x,y) x,y∈Z+
D.全体n×n实可逆矩阵集合Rn×n上的矩阵加法
11.设集合A={1，2，3}，下列关系R中不是等价关系的是（　　　）
A.R={<1,1>,<2,2>,<3,3>}
B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}
C.R={<1,1>,<2,2>,<3,3>,<1,2>}
D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}
12.下列函数中为双射的是（　　　）
A.f：Z→Z,f(j)=j(mod) B.f：N→N,f(j)=
C.f：Z→N,f(j)=|2j|+1 D.f：R→R,f(r)=2r-15
13.设集合A={a,b, c}上的关系如下，具备传递性的是（　　　）
A.R={<a,c>,<c,a>,<a,b>,<b,a>} B.R={<a,c>,<c,a>}
C.R={<a,b>,<c,c>,<b,a>,<b,c>} D.R={<a,a>}
14.含有5个结点，3条边的不一样构的简单图有（　　　）
A.2个 B.3个
C.4个 D.5个
15.设D的结点数不小于1，D=<V,E>是强连通图，当且仅当（　　　）
A.D中最少有一条通路 B.D中最少有一条回路
C.D中有通过每个结点最少一次的通路 D.D中有通过每个结点最少一次的回路
二、填空题(本大题共10小题，每题2分，共20分)
请在每题的空格中填上正确答案。错填、不填均无分。
16.设A={1,2,3}，B={3,4,5}，则AÅA=___________，AÅB=___________。
17.设A={1,2,3,4,5}，RÍA×A，R={<1,2>，<3,4>,<2,2>}，则R的自反闭包r(R)=__________。
对称闭包t(R)=__________。
18.设P、Q为两个命题，德摩根律可表示为_____________，吸取律可表示为____________。
19.对于公式x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,当论域为{1,2}时，其真值为_____________ ,当论域为{0,1,2}时，其真值为_____________。
20.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数,
。
21.3个结点可组成_________个不一样构的简单无向图，可组成________个不一样构的简单有向图。
22.无向图G=<V,E>如左所示，则G的最大度
Δ(G)=_____________，G的最小度δ(G)=_____________。
23.设图G<V,E>,V={v1,v2,v3,v4},若G的邻接矩阵，则deg-(v1)=_ ________,
deg+(v4)=____________。
24.格L是分派格，当且仅当L既不含有与_______同构的子格，也不含有与______同格的子格。
25.给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={<1,2>,<3,4>,<2,2>},
S={<4,2>,<2,5>,<3,1>,<1,3>}，则，。
三、计算题（本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分）
26.设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，画出R的关系图，并求出A中各元素的等价类。
27.结构命题公式ù（P∨Q） （ùP∧Q）的真值表。
28.求下列