离散数学试卷二十三试题与答案_离散数学试卷答案

离散数学试卷二十三试题与答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学试卷答案”。

试卷二十三试题与答案

一、单项选择题：（每小题1分，本大题共10分）

1．命题公式P(QP)是（）。

A、矛盾式；B、可满足式；C、重言式；D、等价式。

2．下列各式中哪个不成立（）。

A、x(P(x)Q(x))xP(x)xQ(x)；

B、x(P(x)Q(x))xP(x)xQ(x)；

C、x(P(x)Q(x))xP(x)xQ(x)；

D、x(P(x)Q)xP(x)Q。

3．谓词公式x(P(x)yR(y))Q(x)中的 x是（）。

A、自由变元；B、约束变元；

C、既是自由变元又是约束变元；D、既不是自由变元又不是约束变元。

4．在0 之间应填入（）符号。

A、=；B、；C、；D、。

5．设 是偏序集，BA，下面结论正确的是（）。

A、B的极大元bB且唯一；B、B的极大元bA且不唯一；

C、B的上界bB且不唯一；D、B的上确界bA且唯一。

6．在自然数集N上，下列（）运算是可结合的。

（对任意a,bN）

A、abab；B、abmax(a,b)；

C、aba5b；D、abab。

7．Q为有理数集N，Q上定义运算*为a*b = a + b – ab ,则的幺元为（A、a；B、b；C、1；D、0。

8．给定下列序列，（）可以构成无向简单图的结点度数序列。

A、（1，1，2，2，3）；B、（1，1，2，2，2）；

C、（0，1，3，3，3）；D、（1，3，4，4，5）。

9．设G是简单有向图，可达矩阵P(G)刻划下列（）关系。

A、点与边；B、边与点；C、点与点；D、边与边。

10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（A、5；B、7；C、9；D、8。

。）。）

二、填空：（每空1分，本大题共15分）

1．在自然数集中，偶数集为N1、奇数集为N2，则N1N2=；

N1N2 =。

2．设X{1,2,3,4},R{1,2,2,4，3,3}，则

r(R)=；s(R)= ；t(R)=。

3．设R为集合A上的等价关系，对aA，集合[a]R=，称

为

元

素

a

形

成的R

等

价

类，[a]R，因

为。

4．任意两个不同小项的合取为，全体小项的析取式为。

5．设Q(x):x为偶数，P(x):x为素数，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1）；

（2）。

6．设T为根树，若，则称T为m元树；

若则称T为完全m叉树。

7．含5个结点，4条边的无向连通图（不同构）有 个，它们是。

三、判断改正题：（每小题2分，本大题共20分）

1．命题公式(A(AB))B是一个矛盾式。（）2．任何循环群必定是阿贝尔群，反之亦真。（）3．根树中最长路径的端点都是叶子。（）4．若集合A上的关系R是对称的，则R



1也是对称的。（）

5．数集合上的不等关系（≠）可确定A的一个划分。（）6．设集合A、B、C为任意集合，若A×B = A×C，则B = C。（）7．函数的复合运算“。”满足结合律。（）8．若G是欧拉图，则其边数e合结点数v的奇偶性不能相反。（）9．图G为（n , m）图，G的生成树TG必有n个结点。（）10．使命题公式P(QR)的真值为F的真值指派的P、Q、R值分别是T、F、F。（）

四、简答题（每小题5分，本大题共25分）

1．设H,和K,都是群G,的子群，问HK,和HK,是否是

G,的子并说明理由。

3，4，9}，B{2，4，7，10,12}，从A到B的关系 2．设A{2，R{a,baA,bB,且a整除b}，试给出R的关系图和关系矩阵，并说明此

关系是否为函数？为什么？

3．设S,是半群，OL是左零元，对任xS,xOL是否是左零元？为什么？

4．某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）

5．通过主合取范式，求出使公式(PQ)R的值为F的真值指派。

五、证明题：（共30分）

1．设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。

2．试证明若G,是群，HG，且任意的aH，对每一个xG，有axxa，则H,是G,的子群。

3．设G是每个面至少由k（k3）条边围成的连通平面图，试证明为结点数，e为边数。

4．符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。答案

e

k(v2)k

2，其中v

一、单项选择题：

1．N

2;

。r(R){1,2,2,4,3,3,1,1,2,2,4,4}，2．

s(R){1,2,2,4,3,3,2,1,4,2}，RRR{1,4,3,3}，RRR{3,3}，RRR{3,3}，所以，t(R){1,2,2,4,3,3,1,4}。

3．[a]R{xxA,aRx}；a[a]R。4．永假式（矛盾式），永真式（重言式）。5．（1）x((Q(x)P(x))y(Q(y)P(y)xy))。（2）xy(Q(x)P(x)Q(y)P(y)xy)。

6．每个结点的出度都小于等于m；除叶子外，每个结点的出度都等于m。7．3。

三、判断改正题：

1．×命题公式(A(AB))B是一个重言式。2．×任何循环群必定是阿贝尔群，但反之不真。3．×根树中最长路径的端点不都是叶子。

4．√5．×≠不能确定A的一个划分。6．√7．√

8．×欧拉图其边数e和结点数v的奇偶性可以相反。9．√10．√

四、简答题

1．解：HK,是 G,的子群，HK,不一定是G,的子群。a,bHK,则的子群，a,bH,a,bK,由

H,和K,都是G,



ab



1H且ab

1

K,ab

1

HK,HK,是G,的子群。

如：G = {1，5，7，11}，：模12乘，则G,为群。且H = {1，5}，K = {1，7}，H,和K,皆为G,的子群，但HK{1,5,7}，HK,不是G,的子群。因为 5711HK，即运算不封闭。

2．解：R{2,2,2,4,2,10,2,12,3,12,4,4,4,12}则R的关系图为： R的关系矩阵为

10

00

1010

0000

1000

1110

M

R

关系R不是A到B的函数，因为

元素2，4的象不唯一（或元素9无象）

3．解：xOL仍是左零元。因为yS，由于OL是左零元，所以，OLyOL，又S,为半群，所以*可结合。

所以，(xOL)yx(OLy)xOL，所以，xOL仍是左零元。

4．解：可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图

GV,E，20人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅

一次得回路。由题已知，u,vV,deg(u)10,deg(v)10，deg(u)deg(v)20，由判定定理，G中存在一条汉密尔顿回路。即所谈情况可能。

5．解：

原式(PQ)R(PQ)R(PR)(QR)

(PQR)(PQR)(PQR)(PQR)M100M110M

010

∴使公式(PQ)R的值为F的真值指派为：

P:1



Q:0R:0；

P:1



Q:1R:0；

P:0



Q:1R:0。

五、证明题：

1．证明：假设R不是反对称的，则 x,yR,性，∴ x,xR 此与R反自反矛盾，∴R反对称。

y,xR,xy 由R的传递

2．证明：（1）设群G,的幺元为e，则xG有 xeex，∴eH即H非空。（2）a,bH，则 xG 有 axxa,bxxb，从而

(ab

1)x(ab

1

11)x(bb

1)

a(bb)xb

1

(ax)b

1

1

x(ab),abH

故 H,是G,的子群。

3．解：设连通平面图G有t个面：r1,r2,,rt则有 ver2，deg(ri)k,2k



tt

又有题意，deg(ri)kt

i1

又

e

deg(r)2e

i

i1，∴2ekt，teve

2k

e2

kk2

(v2)

。从而，∴。

4．解：设P(x)：x喜欢美术，Q(x)：x喜欢体育，R(x)：x喜欢音乐。论域：人。

命题形式化为：前提：x(P(x)Q(x))，x(Q(x)R(x))，xR(x)结论：xP(x)。证明：（1）xR(x)P(2)R(a)ES(1)(3)x(Q(x)R(x))P(4)Q(a)R(a)US(4)(5)Q(a)T(2)(4)I(6)x(P(x)Q(x))P(7)P(a)Q(a)US(6)(8)P(a)T(5)(7)I(9)xP(x)EG(8)∴ 结论有效。

离散数学试卷

离散数学试卷（共9篇）由网友“wenwenwne”投稿提供，下面是小编帮大家整理后的离散数学试卷，希望对大家带来帮助，欢迎大家分享。篇1：离散 离散这几天天气都冷的恐怖.穿得很棉,手和脚......

离散数学试卷

诚信应考,考试作弊将带来严重后果！华南理工大学期末考试 《离散数学》试卷A 注意事项：1.考前请将密封线内填写清楚；2.所有答案请直接答在试卷上；3．考试形式：闭卷；4.本试卷共五大题，......

离散数学试卷2

离散数学试题（2）一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1.一个连通的......

离散数学试卷1

离散数学试题（1）一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。......

离散数学试题与答案

《离散数学》试题及答案一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。1.命题公式(PQ)Q为 ()(A) 矛盾式 (B) 可满足式(C) 重言......