2023年12月3日发(作者：腾远高考数学试卷答案)
试卷一试题与答案
一、填空 20% （每小题2分）
1．设
A{x|(xN)且(x5)},B{x|xE且x7}（N：自然数集，E+ 正偶数） 则
AB 。
2．A，B，C表示三个集合，文图中阴影部分的集合表达式为
。
3．设P，Q 的真值为0，R，S的真值为1，则
A B
C
(P(Q(RP)))(RS)的真值= 。
4．公式(PR)(SR)P的主合取范式为
。
5．若解释I的论域D仅包含一个元素，则
xP(x)xP(x) 在I下真值为
。
6．设A={1，2，3，4}，A上关系图为
则 R2 = 。
7．设A={a，b，c，d}，其上偏序关系R的哈斯图为
则 R= 。
8．图
的补图为 。 9．设A={a，b，c，d} ，A上二元运算如下：
*
a
b
c
d
a b c d
a b c d
b c d a
c d a b
d a b c
那么代数系统
10．下图所示的偏序集中，是格的为 。
二、选择 20% （每小题 2分）
1、下列是真命题的有（ ）
A．
{a}{{a}}； B．{{}}{,{}}；
C．
{{},}； D．
{}{{}}。
2、下列集合中相等的有（ ）
A．{4，3}；B．{，3，4}；C．{4，，3，3}；D． {3，4}。
3、设A={1，2，3}，则A上的二元关系有（ ）个。
A． 23
；
B． 32
；
C．
2
4、设R，S是集合A上的关系，则下列说法正确的是（ ）
A．若R，S 是自反的， 则RS是自反的；
B．若R，S 是反自反的， 则RS是反自反的；
C．若R，S 是对称的， 则RS是对称的；
33； D．
322。 D．若R，S 是传递的， 则RS是传递的
5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下
R{s,t|s,tp(A)(|s||t|}则P（A）/ R=（ ）
A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；
D．{{}，{2}，{2，3}，{{2，3，4}}，{A}}
6、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（ ）
7、下列函数是双射的为（ ）
A．f : IE , f (x) = 2x ； B．f : NNN, f (n) =
C．f : RI , f (x) = [x] ； D．f :IN, f (x) = | x | 。
（注：I—整数集，E—偶数集， N—自然数集，R—实数集）
8、图 中 从v1到v3长度为3 的通路有（ ）条。
A． 0； B． 1；
9、下图中既不是Eular图，也不是Hamilton图的图是（ ）
C． 2； D． 3。
10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。 A．1； B．2； C．3； D．4 。
三、证明 26%
１、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当
< a, b> 和在R中有<.b , c>在R中。（8分）
２、f和g都是群
*>的同态映射，证明
３、G=
ek(v2)k2， 由此证明彼得森图（Peterson）图是非平面图。（11分）
四、逻辑推演 16%
用CP规则证明下题（每小题 8分）
1、ABCD,DEFAF
2、x(P(x)Q(x))xP(x)xQ(x)
五、计算 18%
1、设集合A={a，b，c，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。 （9分）
2、如下图所示的赋权图表示某七个城市v1,v2,,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （９分）
试卷二试题与答案
一、 填空 20% （每小题2分）
1、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为
；“虽然你努力了，但还是失败了”的翻译为
。
2、论域D={1，2}，指定谓词P
P (1,1)
T
P (1,2)
T
P (2,1)
F
P (2,2)
F
则公式xyP(y,x)真值为 。
3、设S={a1
，a2
，„，a8}，Bi是S的子集，则由B31所表达的子集是
。
}，则R=
4、设A={2，3，4，5，6}上的二元关系R{x,y|xyx是质数
（列举法）。
R的关系矩阵MR=
。
5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R= ；A上既是对称的又是反对称的关系R= 。 6、设代数系统
*
a
b
c
a b c
a b c
b b c
c c b
则幺元是 ；是否有幂等 性 ；是否有对称性 。
7、4阶群必是 群或 群。
8、下面偏序格是分配格的是 。
9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是
。
10、公式(P(PQ))((PQ)R的根树表示为
。
二、选择 20% （每小题2分）
1、在下述公式中是重言式为（ ）
A．(PQ)(PQ)；B．(PQ)((PQ)(QP))；
C．(PQ)Q； D．P(PQ)。
2、命题公式
(PQ)(QP) 中极小项的个数为（ ），成真赋值的个数为（ ）。
A．0； B．1； C．2； D．3 。 S3、设S{,{1},{1,2}}，则
2 有（ ）个元素。
A． 3； B．6； C．7； D．8 。
4、设S{ 1, 2, 3 }，定义SS上的等价关系
R{a,b,c,d | a,bSS,c,dSS,adbc}
则由R产 生的SS上一个划分共有（ ）个分块。
A．4； B．5； C．6； D．9 。
5、设S{ 1, 2, 3 }，S上关系R的关系图为
则R具有（ ）性质。
A．自反性、对称性、传递性； B．反自反性、反对称性；
C．反自反性、反对称性、传递性； D．自反性 。
6、设
, 为普通加法和乘法，则（ ）S,,是域。
A．S{x|xab3,C．S{x|x2n1,
7、下面偏序集（ ）能构成格。
a,bQ} B．S{x|x2n,a,bZ}
nZ} D．S{x|xZx0}= N 。
8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。
A．1； B．2； C．3； D．4 。 9、在如下各图中（ ）欧拉图。
10、设R是实数集合，“”为普通乘法，则代数系统
A．群； B．独异点； C．半群 。
三、证明 46%
1、 设R是A上一个二元关系，
S{a,b|(a,bA)(对于某一个cA,有a,cR且c,bR)}试证明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）
2、 用逻辑推理证明：
所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）
Af:ABg:B23、 若是从A到B的函数，定义一个函数对任意bB有Ag(b){x|(xA)(f(x)b)}，证明：若f是A到B的满射，则g是从B到
2
的单射。（10分）
4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）
5、 设G是具有n个结点的无向简单图，其边数Hamilton图（8分）
四、 计算 14%
m1(n1)(n2)22，则G是1、设
2、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）
试卷三试题与答案
一、 填空 20% （每空 2分）
1、 设 f，g是自然数集N上的函数xN,f(x)x1,g(x)2x，
则fg(x) 。
2、 设A={a，b，c}，A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,
则s（R）= 。
}，则用列举3、 A={1，2，3，4，5，6}，A上二元关系T{x,y|xy是素数法
T= ；
T的关系图为
；
T具有 性质。
4、 集合A{{,2},{2}}的幂为2A= 。
5、 P，Q真值为0 ；R，S真值为1。则wff(P(RS))((PQ)(RS))的真值为 。
6、
wff((PQ)R)R的主合取范式为 。
7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词wffx(P(x)y(O(y)N(y,x)))的自然语言是
。
8、 谓词wffxy(z(P(x,z)P(y,z))uQ(x,y,u))的前束范式为
二、 选择 20% （每小题 2分）
1、 下述命题公式中，是重言式的为（ ）。
A、(pq)(pq)； B、(pq)((pq))(qp))；
C、(pq)q； D、(pp)q。
2、
wff(pq)r的主析取范式中含极小项的个数为（ ）。
A 、2； B、 3； C、5； D、0； E、 8 。
3、 给定推理
①x(F(x)G(x))
②F(y)G(y)
③xF(x)
④F(y)
⑤G(y)
⑥xG(x)
P
US①
P
ES③
T②④I
UG⑤
x(F(x)G(x))xG(x) 推理过程中错在（ ）。
A、①->②; B、②->③; C、③->④; D、④->⑤; E、⑤->⑥
4、 设S1={1，2，„，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，
S5={3，5}，在条件XS1且XS3下X与（ ）集合相等。
A、 X=S2或S5
； C、X=S4或S5；
B、 X=S1，S2或S4； D、X与S1，„，S5中任何集合都不等。
5、 设R和S是P上的关系，P是所有人的集合，R{x,y|x,yPx是y的父亲}，S{x,y|x,yPx是y的母亲}则S1R表示关系 （ ）。
}；
A、{x,y|x,yPx是y的丈夫}；
B、{x,y|x,yPx是y的孙子或孙女C、
；
}。
D、{x,y|x,yPx是y的祖父或祖母
6、 下面函数（ ）是单射而非满射。
A、f:RR,B、f:ZR,C、f:RZ,D、f:RR,f(x)x22x1；
f(x)lnx；
f(x)[x],[x]表示不大于x的最大整数；
f(x)2x1。
其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。
7、 设S={1，2，3}，R为S上的关系，其关系图为
则R具有（ ）的性质。
A、 自反、对称、传递； B、什么性质也没有；
C、反自反、反对称、传递； D、自反、对称、反对称、传递。
8、 设S{,{1},{1,2}}，则有（ ）S。
A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。
9、 设A={1 ,2 ,3 }，则A上有（ ）个二元关系。
A、2 ； B、3 ； C、2； D、2
10、全体小项合取式为（ ）。
A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。
三、 用CP规则证明 16% （每小题 8分）
1、ABCD,DEF
322332AF
2、x(P(x)Q(x))xP(x)xQ(x)
四、（14%）
集合X={<1,2>, <3,4>, <5,6>,„ }，R={<
x2+y1} 。
1、 证明R是X上的等价关系。 （10分）
2、 求出X关于R的商集。（4分）
五、（10%）
设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >}
要求 1、写出R的关系矩阵和关系图。（4分）
2、用矩阵运算求出R的传递闭包。（6分） 六、（20%）
1、（10分）设f和g是函数，证明fg也是函数。
2、（10分）设函数g:ST入射函数。
离散数学四
本题得分
一、选择题（选择真确答案，并将其代号写在题干后面的括号里，本题共
6小题,每小题3分，共18分)
f:TS，证明
f:TS有一左逆函数当且仅当f是1 命题“小李和小王学习努力”的否定是：（ ）
(A)小李或小王学习不努力； (B) 小李和小王学习都不努力；
(C)小李学习努力和小王学习不努力；(D) 小李和小王至少有一人学习努力。
2 设个体域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)。
3 A={1，2，3}，A上的如下二元关系中， ( )是函数。
(A)R1={<1，2>，<2，1>，,<2，2>}； (B)R2={<1，2>，<1，1>，<3，2>}；
(C)R3={<1，1>，<2，2>}； (D)R4={<1，2>，,<2，3>，<3，3>}。
4下列代数系统(S,)，哪个是群？ （ ）
(A)
S{0,1,3,5},是模7加法；
(B)SQ（有理数集合），是一般乘法；
(C)
SZ(整数集合)，是一般减法；
(D)
S{1,3,4,5,9},是模11乘法。
5下面集合（ ）关于整除关系构成格。
(A){2，3，6，12，24，36} ； (B){1，2，3，4，6，8，12} ；
(C){1，2，3，5，6，15，30} ； (D){3，6，9，12}。
6
V{a,b,c,d,e,f}，E{a,b,b,c,c,aa,d,d,e,
。
f,e}，则有向图GV,E是（ ）(A)强连通的 ； (B)单侧连通的 ； (C)弱连通的 ； (D)不连通的。
本题得分
1 设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。二、填空题（请将正确答案填入空格内，每小题3分，共18分）
命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为
_____________________。
2 设A={1，2}，P(A)表示A的幂集，,则P(A) A =_____________________。
3．设A{a,b,c}考虑下列子集：
S1{{a,b},{b,c}}，S2{{a},{a,b},{a,c}}，S3{{a},{b,c}}，S4{{a,b,c}}，S5{{a},{b},{c}}，S6{{a},{a,c}}
则A的覆盖有 ，A的划分有 。
4 设(A,)是分配格，若对任意的a,b,cA，如果有(abac,abac成立，则有 。
5 若连通平面图GV,E共有r个面，其中|V|v,|E|e，则它满足的Euler公式为 。
6 5个结点可以构成 棵非同构得无向树。
本题得分
三、判断题（请在你认为正确的题后括号内打“√”，错误的打“×”，本题共6小题，每小题1分，共6分）
1设P，Q是两个命题，当且仅当P，Q的真值均为T时，PQ的值为T。（ ）
2{}{,{}}且{}{,{}}。（ ） 3 集合A{a,b,c}上的关系R{a,b,a,c}是传递的。（ ）
4任何循环群必定是阿贝尔群，反之亦真。（ ）
5设G为无向图，若G中恰好n个结点，n-1条边，则G必为一棵树。（ ）
6平面图一定是连通图。( )
本题得分
四、计算题（本题共4小题,每小题6分，共24 分）
1求下式的主析取范式和主合取范式：
（PQ)(PQ)。
2设集合A= {1,2,3,4}上的二元关系R1与R2定义如下：
R1={<1,1>,<1,3>,<2,2>,<2,4>,<3,3>,<4,4>}，
R2={<1,1>,<1,2>,<2,1>,<2,3>,<3,4>,<4,1>}，
（1）写出R1的关系矩阵，并判断R1具有哪些性质？
（2）求出R1R2。
3 设S = R {-1}（R为实数集），ababab。
（1）说明(S,)是否构成群；
（2）在S中解方程2x37。
4 一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。
问T中有几个结点?
本题得分
五、应用题（本题共1小题,每小题10分，共10分）
下图给出的赋权图表示六个城市a,b,c,d,e,f及架起城市间直接通讯线路的预测造价。给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。
。
本题得分
1．
六、证明题（本题共3小题,每小题8分，共24分）
设A{1,2,,9}，在AA上定义关系R:a,bc当,dR且仅当adbc，证明R是AA上的等价关系，并求出[2,5]R.
2． 设G是群，H是G的子群，xG，证明：xHx1{xhx1|hH}是G的子群。
3．将下列命题形式化，并证明结论的有效性：所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。
《离散数学》试题五
一、判断题（每题1分，共10分）
1.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是惟一的。
（ ）
2. 011是公式(pq)r的成真赋值 ( )
3.(xF(x)yG(y))(xF(x))(yG(y)) ( )
4.
x(F(x)G(x))xF(x)xG(x) （ ）
5.三种重要的二元关系是等价关系、偏序关系和函数关系，它们的共同特点是都具有自反性 。 ( )
6. 设F,R都是二元关系,则(F·R)-1=F-1·R-1。 ( )
7.设n是任意一个正整数,则一定存在阶是n的群. ( )
8. 布尔代数是有界格,也是分配格. ( )
9.无向完全图Kn（n>2）一定是哈密顿图 ( )
10.阶数至少是2 树的每一条边都是桥,因而它的边连通度是1. （ ） 二、空题（每小题２分，共２０分）
1. 谓词公式x(P(x,y)∧
tQ(t,z)→R(x,y,t))中量词的辖域是
___________________。
2.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_______ ___。
3.(pq)pq从公式分类角度来看，它为__________式。
4.设R={<1,1>,<1,2>,<2,3>}，则R的对称闭包是 。
5.设A,B是集合，A3,B4,AB2,那么，AB
6. 7．整数加群 8.设A,是偏序集,如果_________ ____, 则称A,是(偏序)格。 9.一棵二叉树先序遍历得ABDECF，中序遍历得DBEACF,则后序遍历的结果是________________。 10. r=5,当s= 时，完全二部图Kr,s才可能存在完美匹配。 。 三、计算题（1-4题每题8分；5-6题每题10分，共52分） 1.R1={<1,2>,<2,1>,<2,3>,<3,2>},R2={<2,2>,<2,3>,<3,1>} 求：(1) R1-1 (2) R1·R2 (3)R22 (4)t(R1)(传递闭包) 2．设G=a010100101,b,c,d，G上的运算是矩1011010阵乘法。已知G构成群。 （1）指出个元素的阶； （2）找出G的全部子群； （3）在同构的意义下G是4阶循环群还是Klein四元群？ 3.(1)在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中应该有几片树叶？ (2)画出两棵非同构的满足上述条件的无向树 。 4.设 （1）画出的哈斯图； （2）求A的极大元和极小元； （3）求B={4,6}的上确界和下确界。 5.求公式(pq)r的主和取范式(化成M1M2M3的形式)。 ６．画一棵带权为2，2，2，3，3，4，5，8的最优二叉树T，并计算它的权W（T）。 四、证明题（每小题6分，共18分） 1.前提： p(qr),q(rs) 结论: (pq)s 2.定理（子群判别法1)设H是群 (1)a，b∈H， ab∈H； (2)a∈H，a∈H。 －1（3）利用上述定理证明：设H是群 3.用数学归纳法证明n阶无向树T有n-1边。 《离散数学》试题六 一、判断题（每题1分，共10分） 1.任何命题公式都存在惟一的析取范式。 （ ） 2. 封闭的公式在任何解释下都变成命题。 ( ) 3. (pq)(rs)的层数是3 （ ）4.x(BA(x))x(BA(x)). ( ) 5. 设A,B,C是三集合，已知AB＝AC，则一定有B＝C. ( ) 6.矩阵的等价、相似、合同都是等价关系。 ( ) 7.已知a是群集的二阶元，则={a,a2}. ( ) 8.有界格中某元的的补元不止一个，则它不是分配格。 ( ) 9.有向图是强连通的，则它一定是单向连通的，也弱连通的。 ( ) 10.二部图K3,3是欧拉图也是哈密顿图。 ( ) 二、填空题（每小题2分，共20分） 1.((pq)q)p从公式的类型看，它属于 式。 2.x(A(x)B(x)) ___________________。 3.设F(x):x是人，H(x):x呼吸，在一阶逻辑中，命题“凡人 都呼吸”的符号化形式为_______ _________。 4.6阶循环群有 个子群。 5. A={a,b},则A的幂集P(A)到自身的双射有__ _个。 6. A={1,2,3}，S是A上所有置换构成的集合，则单位元是 ，S,构成群，的逆元是 ，该元是 阶元。 1233217.一个3阶有向图的度序列是2，2，4，入度序列是2，0，2，出度序列是 。 8.一无向图存在生成树的充分必要条件是 。 9.最优二叉树有n片树叶，则它有 分支点。 10. 下图的点连通度等于 ，边连通度等于_________。 三、计算题（每小题10分，共50分） 1.设A={a,b,c},B={b,c,d},C={d,e,f},R1={<1,2>,<2,2>, <2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>} 求 (1) AB (2) A⊕B (3) R1-1 (4) R1·R2 (5) R1在A上的限制。 2.其中，A={1，2，3，4}，R={<1,2>,<2,2>,<2,3>,<3,4>},R是A上的二元关系。 （1）画出的R的关系图； （2）求R的自反、对称、传递闭包； 3.S=Q×Q,其中Q为有理数集合，定义S上的二元运算*， (1)求<3,4>*<1,2>. (2)已知<-1,3>* (3)*是可交换的吗？是可结合的吗？ 4.在一个无向图中有6条边，3度顶点和5度顶点各1个，其余顶点都是2度点，该图有几个顶点？ 5.在下图中，用克鲁斯卡尔算法构造最小生成树，写出边添加到生成树的边序列，并画出生成树。 5a5f1b27h6648e6d3c 四、证明题（共20分） 1.前提：x(F(x)H(x)),x(G(x)H(x)) 结论:x(G(x)F(x)) 2.已知Mn(Z),(即整数集上2阶方阵构成的集合关于矩阵的加法)构成a0群,H=aZ 0a(1) Mn(Z),的单位元是什么? (2)证明: H是Mn(Z),的子群. 3.叙述并证明关于连通平面图的欧拉公式。 12的逆元是什么? 34《离散数学》试题七 一、选择题（每小题 2 分，共 20 分） 1、使命题公式p→(p∧q)为假的赋值是 ( ) A.10 B.01 C. 00 D.11 2、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ） A. p∧┐q B．p∨┐q C.p∧q D．p→┐q 3、设B不含有x，下列一阶逻辑等值式不正确的是 ( ) ．．．A.x(A(x)B)xA(x)B B.x(A(x)B)xA(x)B C. x(A(x)B(x))xA(x)xB(x) D. x(A(x)B(x))xA(x)xB(x) 4、 设X，Y，Z是集合，下列结论不正确的是（ ） ．．．A．若XY,则XY=X B．(X-Y)-Z=X-(Y∩Z) C．XX D．XYX(~Y) 5、设R是集合A上的二元关系，IA是上的恒等关系，IAR下面四个命题为真的是 ( ) A.R是自反的 B.R是传递的 C.R是对称的 D.R是反对称的 6、设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是 ( ) A. f是单射 B. f是满射 C. f是双射的 D.f非单射非满射 7、集合A={1，2，3，4}，则对 A 的元素进行分类正确的是（ ） A. {,{1,2},{3,4}} B. {{1,2,3},{3,4}} C. {{1},{3,4}} D. {{1,2,3,4}} 8、无向完全图Kn有 ( )条边 A. n B. n2 C. n(n-1) D. n(n-1)/2 9、 设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ） A．2 B．3 C．4 D．5 10、一颗二叉树后序遍历的结果是bdeca，中序遍历的结果是badce，则 根结点的右子树有（ ）结点。 A．1 B．2 C．3 D．4 二、填空题（每题2分，共10分） 1、量词否定等值式xA(x) ___________________。 2、设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的对称闭包是 。 3、A={1，2}，P(A),是群，是集合的对称差运算。该群的单位元是 ，{1}的逆元是 。 4、图G是平面图的充分必要条件是没有收缩到___或 的子图。 5、无向图G= 三、计算题（每题8分，共 48分） 1、求公式(pq)r的主和取范式(化成M1M2M3的形式)。 2、R1={<1,2>,<1,3>,<2,3>,<3,3>}, R2={<2,2>,<2,3>,<3,4>}, (1) 求 R1-1 (2) 求R2R1 (3)R1是函数吗？ 3、(1)叙述等价关系的定义； (2)设A={1，2，3，4},R={<1,1>,<2,2>,<3,3>,<4,4>,<2,3>,<3,2>}是A上的等价关系吗？如果是,给出R确定的对A的分类；如果不是,请说明理由。 4、已知M2(R),,(即实数集上2阶方阵构成的集合关于矩阵的加法和乘法)构成的环。 (1)M2(R),,的零位元是什么?单位元是什么? (2)说明 M2(R),,不是无零因子环； (3)举例说明不满足消去律。 5、求A到其余顶点的最短路径。 B8A1C 42262D5F1E 6、求下PERT图中各顶点的最早完成时间TE(vi)和最迟完成时间TL(vi)，并求出关键路径。 c9a3b124d28g4j3f 1h6221e 得分 阅卷人 四、证明题（ 22分） 1、前提： x(F(x)G(x)H(x)),x(F(x)R(x)) 结论: x(F(x)R(x)G(x)) 2、设 k证明H是G的子群。 3、 用数学归纳法证明，含有n片树叶的最优二叉树有n-1个分支点. 《离散数学》试卷 八 得分 阅卷人 一、选择题（每小题 2分，共 20 分。请将答案填在下面的表格内） 1、从集合分类的角度看,命题公式可分为( ) A.永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 2、设B不含有x，x(A(x)B)等值于 ( ) A.xA(x)B B.x(A(x)B) C.xA(x)B D.x(A(x)B) 3、设S,T,M是集合，下列结论正确的是（ ） A．如果S∪T=S∪M，则T=M B．如果S-T=Φ，则S=T C．SSS D．STS(~T) 4、设R是集合A上的偏序关系，则R不一定是( ) A.自反的 B. 对称的 C. 反对称的 D. 传递的 5 设R为实数集，定义R上4个二元运算，不满足结合律的是（ ）。 A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy D. f4(x,y)=max{x,y} 6、设 A.交换律 B. 结合律 C. 吸收律 D. 消去律 7、设A={1,2},则群P(A),的单位元和零元是( ) A. 与A B. A 与 C. {1}与 D. {1}与A 8、下列编码是前缀码的是( ). A.{1,11,101} B.{1,001,0011} C. {1,01,001,000} D.{0,00,000} 9、下图中既是欧拉图又是哈密顿图的是（ ） A． K9 B．K10 C．K2,3 D．K3,3 10、下图所示的二叉树中序遍历的结果是（ ） abdce A．abcde B．edcba C．bdeca D．badce 题号 答案 得分 1 2 3 4 5 6 7 8 9 10 阅卷人 二、填空题（每题3分，共24分） 1、含3个命题变项的命题公式的主合取范式为M0M3M4M6M7, 则它的主析取范式为 。(表示成mm的形势) 2、〈Z4，〉模4加群， 则3是 阶元，33= ，3的逆元是 。 xZ，3、设V= 2(x)=-x,3(x)=x+5, 4(x)=2x，其中有 个自同构. 4、设2123456是集合A={1，2，3，4,5,6}上的一个置换，则把它表示成31546不相交的轮换的积是 。 4、已知n阶无向简单图G有m条边，则G的补图有 条边。 5、一个有向图是强连通的充分必要条件是 。 7、已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m， 则m= . 8、在下图中从A点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是 （ ）。 A5B1726E8C34D 得分 阅卷人 三、计算题（每题9分，共 36分） 1、已知命题公式(pq)(qp)， (1) 构造真值表。 (2) 求主析取范式(要求通过等值演算推出)。 2、R1={<1,2>,<1,3>,<2,3>}, R2={<2,2>,<2,3>,<3,4>},求： (1)R1R2 （２）R11 (３) 求R2R1 ３、设 （1）画R出的哈斯图； （2）求A的极大元和极小元； （3）求B={4,6}的上确界和下确界。 ４、画一棵带权为1，1，1，3，3，5，8的最优二叉树T，并计算它的权W（T）。 得分 阅卷人 四、证明题（共 20分） 1、（7分）前提： p(qs),q,pr 结论: rs 2、（7分）A={(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1)}, R={<(a,b),(c,d)>| (a,b),(c,d)A且a+b=c+d }. (1)证明：R是A上的等价关系． (2)给出R确定的对A的划分(分类). 3、（6分）设G,是群, S{x|xG且对于yG,xyyx}, 证明S是G的子群. 《离散数学》试题九 一、选择题（每小题2分，共20分） 1．一个命题公式或一阶逻辑公式的（ ）是不惟一的。 A．主析取范式 B．主合取范式 C．前束范式 D．对偶式 2．下列四个公式正确的是 ①x(A(x)B(x))xA(x)xB(x) ②x(A(x)B(x))xA(x)xB(x) ③x(A(x)B(x))xA(x)xB(x) ④xA(x)xB(x)x(A(x)B(x)) A.①③ B.①④ C.③④ D.②④ 3．设集合A={a，b，c，d，e}，偏序关系R的哈斯图下图所示，则元素的关系不正确的是（ ）。 ecabdg fA．cd B．ae C．ac D．de 4．已知A,B是集合│A│=15，│B│=10，│A∪B│=20，则│A∩B│=（ ） A．10 B．5 C．20 D．13 5．X={a，b，c，d，e}，Y={1，2，3，4}，f从X到Y的映射，其中f(a)=2, f(b)=4,f(c)=1,f(d)=3,f(e)=4,则f是（ ） A.双射 B. 满射 C. 单射 D. 不是单射也不是满射 6．设A,B,C是三个非空集合,则( )是正确的. A.ABACBC B.ABACBC C.ABACBC D. ABACBC 7．在下图所示的哈斯图中的偏序集不是格的是（ ） 8．下图中,（ ）是欧拉图。 A B C D 9.关于无向树的描述,不正确的是( ). A. 无向树是连通图、没有回路,每个边都是桥； B. 无向树是连通图、边数比顶点数少１,任意两个顶点的路径是惟一的； C. 无向树是连通图、没有回路,每个顶点都是割点； D. 无向树是连通图、没有回路，每条边都是割边。 10.关于含有n片树叶的最优二叉树描述,不正确的是( ). A. 含有n片树叶的最优二叉树每个分支点都有两个孩子； B. 含有n片树叶的最优二叉树分支点的个数是n-1； C. W(T)等于个分支点的权重（构造最优二叉树时产生）之和； D. 在权重一定的前提下，含有n片树叶的最优二叉树是惟一的。 二、计算题（每小题10分，共40分） 1.(1)求((pq)r)p的主析取范式； (2)根据主析取范式直接写出主合取范式； (3)根据主析取范式直接写出真值表。 2.设集合A={a，b，c，d}，A上的关系R={ （1）画出R的关系图； （2）求出R的传递闭包tr(R) ； (3) tr(R)中再添加一些元素后得D(R)，若使D(R)是等价关系，则tr(R)中再添哪些元素后得D(R)? 3.(1)下图的最下生成树； (2)求该图的点连通度和边连通度； (3)求A到B的最短路径的长度。 A B 4.(10分)对于下有向图, (1) 写出度序列和出度序列； (2) 写出邻接矩阵A，第一行元素之和的含义是什么？ (3) 求A4,据此说明从A到A的长度为4的回路用多少？ ADB 三、证明题（每小题10分，共40分） 1.利用推理规则证明。 前提：xP(x)xQ(x) 结论：x(P(x)Q(x)) 2. 设A是正整数集合，在AA上定义二元关系R如下： C x,y,u,vR当且仅当xvyu,证明：R为等价关系。 3. 设R为实数集，+为普通加法，为普通乘法， x*y=x+y+xy 证明: 4.设f1，f2都是一从代数系统 离散数学十 本题得分 一、 题共6小题,每小题3分，共18分) 选择题（选择正确答案，并将其代号写在题干后面的括号里，本1 下列语句中 哪个是真命题？ （） (A) 我正在说谎。 (B) 请讲普通话。 (C) 如果1＋2＝5，那么雪是黑的。 (D) 如果1+2=3,那么雪是黑的。 2 集合A{1,2,,10}上的关系R{(x,y)|xy10,xA,yA},则R的性质为：（ ） (A) 自反的 (B)对称的 (C) 传递的、对称的 (D) 反自反的、传递的 3下面集合( )关于减法运算是封闭的。 (A) N (B) {x|x是质数}； (C) {2x1|xI}； (D) {2x|xI}。 4设G1{0,1,2},，G2{0,1},*，其中表示模3加法，*表示模2加法，则积代数G1G2的单位元是（ ）。 (A)<0,0>； (B) <0,1>； (C) <1,0>； (D) <1,1> 5 下列偏序集中能构成格的是 （ ）。 6 图G和G的结点和边分别存在一一对应关系是G和G同构的 ( ) 。 (A) 必要条件 (B) 充分条件 (C) 充要条件 (D) 既不充分也不必要条件 本题得分 二、填空题（请将正确答案填入空格内，每小题3分，共18分） 1 命题公式p→q的真值为假，当且仅当_________________。 2 设 G(x):x是金子,F(x):x是闪光的,则命题“金子是闪光的,但闪光的不一定是金子”符号化为: 。 3 设整数集合I上的二元关系R{(a,b)|ab},则R的对称闭包为： 。 ))(bx1x2)是布尔代数{0,a,b,1}, 4 f(x1,x2)((ax1)(x1x2,,,0,1上的布尔表达式，则 f(a,b) 。 5 设树T有m个顶点，n条边，则T中顶点与边的关系为: 。 6 不同构的5阶无向树有_______棵。 本题得分 三、判断题（请在你认为正确的题后括号内打“√”，错误的打“×”，本 题共6小题，每小题1分，共6分） 1 （PQ）（PQ）是永真式。（ ） 2 {}{,{}}且{}{,{}}。（ ） 3 一种关系，不是自反的，就是反自反的。（ ） 4代数系统中一个元素的左逆元并一定等于该元素的右逆元。（ ） 5 设G为无向图，若G无回路，则G必为一棵树。 （ ） 6 5阶完全图是平面图。（ ） 本题得分 四、计算题（本题共4小题,每小题6分，共24 分） 1 给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：(QR)(PR)的真值。 2 集合A{1,2,3,4}上的关系R{(1,1),(1,3),(2,2),(3,1),(3,3),(3,4), (4,3),(4,4)}，写出关系矩阵MR，并讨论R的性质。 3 设 4 给定一组权值为：2，3，5，7，8，9，请构造一棵最优二叉树，并求W（T）。 本题得分 五、应用题（本题共1小题,每小题10分，共10分） 下列前提下结论是否有效？ 今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看书。故我在看书时，说明今天下雨。 本题得分 六、证明题（本题共3小题,每小题8分，共24分） 1 设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得 2 设A,,,是一个布尔代数，如果在A上定义二元运算“☆”为：a☆b(ab)(ab)，则 3 设T是非平凡无向树，T中结点数大于等于2，T中度数最大的结点有2个，它们的度数为k(k2)，证明：T中至少有2k2个叶结点。
更多推荐
命题,公式,关系,集合,小题,下列,证明,二叉树
发布评论