最新离散数学试卷及答案 (1)

《离散数学》试题及答案一、选择题（每题5分，共25分）1. 下列关系中，哪个是等价关系？（）A. 小于等于（≤）B. 大于等于（≥）C. 整除（|）D. 模2同余（≡）答案：D2. 下列哪个图是完全图？（）A. 无向图B. 有向图C. 简单图D. n阶完全图答案：D3. 设A和B为集合，若A∪B=A，则下列哪个结论成立？（）A. A⊆BB. B⊆AC. A=BD. A∩B=∅答案：B4. 下列哪个命题是永真命题？（）A. (p→q)∧(q→p)B. (p∧q)→(p∨q)C. (p→q)∧(p→¬q)D. (p∧¬q)→(p→q)答案：B5. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的最小生成树的边数是（）。

A. 4B. 5C. 6D. 7答案：B二、填空题（每题5分，共25分）6. 设A={1,2,3,4,5}，B={3,4,5,6,7}，则A∩B=_________。

答案：{3,4,5}7. 设图G的顶点集V={a,b,c,d}，边集E={e1,e2,e3,e4,e5}，其中e1=(a,b)，e2=(a,c)，e3=(b,d)，e4=(c,d)，e5=(d,a)，则G的邻接矩阵为_________。

答案：[0 1 1 0 0; 1 0 0 1 0; 1 0 0 1 0; 0 1 1 0 1;0 0 0 1 0]8. 设p为真命题，q为假命题，则(p∧q)∨(¬p∧¬q)的值为_________。

答案：真9. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的度数序列为（3,3,3,3,3,3），则G的边数是_________。

答案：1510. 下列命题中，与“若p，则q”互为逆否命题的是_________。

离散数学试题及答案一、选择题1. 在集合论中，下列哪个选项表示两个集合A和B的并集？A. A ∩ BB. A ∪ BC. A - BD. A × B答案：B2. 命题逻辑中，下列哪个符号表示逻辑非？A. ∧B. ∨C. ¬D. →答案：C3. 在有向图中，如果存在一条从顶点u到顶点v的路径，那么称顶点v为顶点u的：A. 祖先B. 后代C. 邻居D. 连接点答案：B二、填空题1. 一个命题函数P(x)表示为“x是偶数”，那么其否定形式为________。

答案：x是奇数2. 在关系R上，如果对于所有的a和b，如果(a, b)∈R且(b, a)∈R，则称R为________。

答案：自反的三、简答题1. 简述什么是等价关系，并给出其三个基本性质。

答案：等价关系是一种特殊的二元关系，它满足自反性、对称性和传递性。

自反性指每个元素都与自身相关；对称性指如果a与b相关，则b也与a相关；传递性指如果a与b相关，b与c相关，则a与c也相关。

2. 解释什么是图的连通分量，并给出如何判断一个图是否是连通图。

答案：连通分量是指图中最大的连通子图，即图中任意两个顶点之间都存在路径。

判断一个图是否是连通图，可以通过深度优先搜索或广度优先搜索算法遍历整个图，如果所有顶点都被访问，则图是连通的。

四、计算题1. 给定命题公式P：((p → q) ∧ (r → ¬p)) → (q ∨ ¬r)，证明P是一个重言式。

答案：通过使用命题逻辑的等价规则和真值表，可以证明P在所有可能的p, q, r的真值组合下都为真，因此P是一个重言式。

2. 给定一个有向图G，顶点集合V(G)={1, 2, 3, 4}，边集合E(G)={(1, 2), (2, 3), (3, 4), (4, 1), (2, 4)}。

找出所有强连通分量。

答案：通过Kosaraju算法或Tarjan算法，可以找到图G的强连通分量，结果为{1, 4}和{2, 3}。

19. (5分) 已知公理 A: (pq) ((qp) (pq)) B: pp∨q
C: pp D: (pr) ((qr) ((p∨q) r)) E: p∧qp 证明定理: p(p∨p)
证明:
(1) pp∨q
公理B
(2) pp∨p
代入
(3) (pr) ((qr) ((p∨q) r))
公理D
(4) (pp) ((pp) ((p∨p) p)) 代入
∑d(v) ≥1+2(|V|-1)=2|E|+1, 这与结论 ∑ d(v) =2|E| 矛盾! 矛盾说明 T 不止
一片树叶。
12. (8分) (G, ·)是一个群，取定u ∊ G. ∀g1,g2∊G，定义： g1*g2= g1·u-1·g2. 证明: (G,*)是群。
证明: (1) 封闭性 (2) 可以结合性 (3) 幺元 e*=u. 事实上, g*e*=g*u=g·u-1·u=g·e=g e**g=u*g=u·u-1·g=e·g=g (4) 逆元 对于∀g∊G, 在代数运算*下的逆元记为g*-1 于是, g*-1=u·g-1·u
所以，根据连通的定义知：G的补图一定连通 。
9. (4分) 一个有奇数条边、偶数个顶点的欧拉图，但不是哈 密尔顿图。
10 (6分) 画出K4,4，判断K4,4是否平面图. 否!
11. (5分) 证明: 多于一个顶点的树，至少有两片树叶。
证明：设 T=(V,E)是一棵树，若T中最多只有一片树叶， 则有
g*a*g-1H,
g*a*g-1K, 从而有g*a*g-1HK， 故HK是G的正规子群。
14. (4分) 已知(G, *)，(A, △)是两个群，f: G→A是群同态的。
证明: (1) f(eG)=eA (eG G是幺元, eA A是幺元). (2) ∀g∊G, f(g-1)=(f(g))-1.

离散数学考试题及答案一、单项选择题（每题2分，共10分）1. 在集合{1,2,3}和{3,4,5}的笛卡尔积中，元素(3,4)属于（）。

A. {1,2,3}B. {3,4,5}C. {1,2,3,4,5}D. {1,2,3}×{3,4,5}答案：D2. 命题“若x>2，则x>1”的逆否命题是（）。

A. 若x≤2，则x≤1B. 若x≤1，则x≤2C. 若x≤1，则x≤2D. 若x≤2，则x≤1答案：C3. 函数f: A→B的定义域是集合A，值域是集合B的（）。

A. 子集B. 真子集C. 任意子集D. 非空子集答案：D4. 以下哪个图是无向图（）。

A. 有向图B. 无向图C. 完全图D. 树答案：B5. 以下哪个命题是真命题（）。

A. 所有的马都是白色的B. 有些马是白色的C. 没有马是白色的D. 以上都不是答案：B二、填空题（每题2分，共10分）6. 集合{1,2,3}的子集个数为______。

答案：87. 命题“若x>0，则x>1”的逆命题是：若x>1，则______。

答案：x>08. 函数f: A→B中，若A={1,2}，B={3,4}，则f的值域可以是{3}或{4}或{3,4}，但不能是______。

答案：{1,2}9. 在有向图中，若存在从顶点A到顶点B的有向路径，则称A到B是______的。

答案：可达10. 命题逻辑中，合取（AND）的符号是______。

答案：∧三、解答题（每题15分，共30分）11. 证明：若p∧q为真，则p和q都为真。

证明：根据合取（AND）的定义，p∧q为真当且仅当p和q都为真。

因此，若p∧q为真，则p和q都为真。

12. 给定函数f: A→B，其中A={1,2,3}，B={4,5,6}，且f(1)=4，f(2)=5，f(3)=6。

请找出f的值域。

答案：根据函数的定义，f的值域是其所有输出值的集合。

因此，f的值域为{4,5,6}。

权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）
试卷二答案：
填空20%（每小题2分）
1、 ； 2、T 3、 4、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}； 5、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>} 6、a；否；有7、Klein四元群；循环群8、B 9、 ；图中无奇度结点且连通10、渗釤呛俨匀谔鱉调硯錦鋇絨钞。
前提： 、 结论： ……3分
① P
② P
③ US②
④ T①I
⑤ T③④I
⑥ T①I
⑦ T⑤⑥I
⑧ EG⑦……11分
３、１0分
证明：
。
4、8分
证明：设G中两奇数度结点分别为u和v，若u，v不连通，则G至少有两个连通分支G1、G2，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。铙誅卧泻噦圣骋贶頂廡缝勵罴。
选择20%（每小题2分）
题目
1
2
3
4
5
6
7
8
9
10Biblioteka 答案B、DD；DD
B
D
A

L(x,y)为L(2,2)=L(3,2):=0, L(2,3)=L(3,3):=1，在该解释下
0 .
1
7、设谓词的论域D={a，b，c}，试将 中的量词消除,写成与之等值的命题公式为
得
分
三、计算与简答(共20分)
1、 是可能的吗？说明你的理由。（4分）
解答：可能。
如：定B={{a},a} A={a}
3、求命题公式 的主析取范式和主合取范式。(要求：主析取范式和主合取范式并分别用和mi，Mi形式表示，并写出推导过程)（5分）
解
除去重复项得主析取范式为
=m0∨m2∨m4
根据主析取范式和主合取范式的对应关系得主合取范式为
M1∧M3∧M5∧M6∧M7
=
4、在一阶逻辑中将下列命题符号化：(6分)
（1）参加考试的人未必都能取得好成绩。
（a+bi）R（c+di） ac>0,证明R是等价关系。（15分）
证明:（1）对于任意非零实数a，有
a2>0 （a+bi）R（a+bi）
所以R在C*是自反的。
（2）对任意（a+bi）R（c+di） ac>0
因为ca=ac>0 （c+di）R（a+bi）
所以R在C*是对称的。
（3）设（a+bi）R（c+di）且（c+di）R（u+vi），则有：
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〉}
13、设N是自然数集，R是实数集，于是在下列集合中，基数为0的是（C）

参考答案试卷一一、选择填空1.C2.A3.D4.D5.A6.A7.B8.C9.D 10.B二、填空1.主合取范式)()(q p q p ⌝∨∧∨⌝.前束范式))()((x G x F x →∀或))()((y G x F y x →∀∀ 2. n-k,93.=)(A ρ{Φ,{1}，{2}，{1，2}}，B A ⨯={〈1,a 〉,<1,b>,<2,a>,<2,b>}4. [b]R ={1,2,3}, X/R={{1,2,3},{4},{5}}.5． ,,G y x ∈∀ )()()(y f x f y x f *= 。

6.=-)(1R r { <2,1>,< 4,2>,<1,1>,<3,3>,<2,2>}，=S R {<1,4>,<2,2>}。

7.15，12.8. =τσ⎪⎪⎭⎫ ⎝⎛42134321 =(132) =-1στ⎪⎪⎭⎫ ⎝⎛41324321=(123) 9．0, 45 10．2,0三 1.× 2.√ 3. √ 4.× 5.×四.1．一棵树具有3个2度结点，2个3度结点，2个4度结点，其余为叶。

试求其共有多少个结点？多少片叶？解: 设该树其有x 片叶,则顶点数为x+7, 根据树的性质知,该树有x+6边,由握手定理有:3*2+2*3+2*4+x*1=2(x+6), 得x=8故该树共有15个结点,8 片叶 .2.已知X={a,b,c},给出X 上的所有等价关系。

解:X 的划分其有五种:S 1={{a,b,c}}, S 2={{a,b},{c}}, S 3={{a,c},{b}}, S 4={{a},{b,c}},S 5={{a},{b},{c}},因为X 上划分与等价关系一一对应,故x 上共有五个等价关系，它们是：R 1＝{<a,b>,<b,a>,<a,c><c,a>,<b,c>,<c,b>}X I ⋃R 2＝{<a,b>,<b,a>}X I ⋃, R 3＝{<a,c><c,a>}X I ⋃R 4＝{<b,c>,<c,b>}X I ⋃, R 5＝X I3.．画一棵权为2，3，3，4，5，6，7，8 的最优二叉树，并计算出它的树权。

离散数学试题及答案一、单项选择题（每题2分，共20分）1. 在集合论中，空集的表示符号是（）。

A. {0}B. ∅C. {}D. Ø答案：B2. 如果A和B是两个集合，那么A∩B表示（）。

A. A和B的并集B. A和B的交集C. A和B的差集D. A和B的补集答案：B3. 命题逻辑中，p ∧ q的真值表中，当p和q都为假时，p ∧ q的值为（）。

A. 真B. 假C. 不确定D. 无定义答案：B4. 在图论中，如果一个图中的任意两个顶点都由一条边相连，则称这个图为（）。

A. 连通图B. 无向图C. 完全图D. 有向图答案：C5. 布尔代数中，逻辑或运算符表示为（）。

A. ∧B. ∨C. ¬D. →答案：B6. 一个关系R是从集合A到集合B的二元关系，如果对于A中的每个元素x，B中都存在唯一的元素y与之对应，则称R为（）。

A. 单射B. 满射C. 双射D. 单满射答案：C7. 在命题逻辑中，如果p是假命题，那么¬p的值为（）。

A. 真B. 假C. 不确定D. 无定义答案：A8. 一个有向图是无环的，那么它一定是（）。

A. 有向无环图B. 无向无环图C. 有向有环图D. 无向有环图答案：A9. 在集合论中，如果集合A是集合B的子集，那么A⊆B表示（）。

A. A包含于BB. A是B的真子集C. A是B的超集D. A与B相等答案：A10. 命题逻辑中，p → q的真值表中，当p为真，q为假时，p → q 的值为（）。

A. 真B. 假C. 不确定D. 无定义答案：B二、多项选择题（每题3分，共15分）1. 在集合论中，以下哪些符号表示的是集合的并集（）。

A. ∪B. ∩C. ⊆D. ⊂答案：A2. 在图论中，以下哪些说法是正确的（）。

A. 有向图可以是无环的B. 无向图可以是无环的C. 有向图一定是连通的D. 无向图一定是连通的答案：A B3. 在命题逻辑中，以下哪些符号表示的是逻辑与（）。

最新离散数学试题及答案一、选择题（每题2分，共20分）1. 在离散数学中，以下哪个不是命题逻辑的基本联结词？A. 与（∧）B. 或（∨）C. 非（¬）D. 模（%）答案：D2. 以下哪个选项不是命题逻辑的真值表的正确形式？A. P | Q | P ∧ QB. P | Q | P ∨ QC. P | Q | P → QD. P | Q | P ↔ Q答案：B3. 集合A={1, 2, 3}，集合B={2, 3, 4}，求A∪B的结果。

A. {1, 2, 3}B. {2, 3}C. {1, 2, 3, 4}D. {4}答案：C4. 以下哪个是等价关系的属性？A. 自反性B. 对称性C. 传递性D. 所有选项都是答案：D5. 以下哪个是图论中的基本概念？A. 顶点B. 边C. 路径D. 所有选项都是答案：D6. 在有向图中，如果存在一条从顶点u到顶点v的有向路径，那么称v为u的后继。

以下哪个选项不是后继的定义？A. 存在一条从u到v的有向路径B. 存在一条从v到u的有向路径C. 存在一条从u到v的有向简单路径D. 存在一条从v到u的有向简单路径答案：B7. 以下哪个是二元关系R的自反性的定义？A. 对于所有a，(a, a) ∈ RB. 对于所有a，(a, a) ∉ RC. 对于所有a和b，如果(a, b) ∈ R，则(b, a) ∈ RD. 对于所有a和b，如果(a, b) ∈ R，则(a, a) ∈ R答案：A8. 在命题逻辑中，以下哪个是德摩根定律的表达式？A. ¬(P ∧ Q) ↔¬P ∨ ¬QB. ¬(P ∨ Q) ↔¬P ∧ ¬QC. P ∧ Q ↔¬P ∨ ¬QD. P ∨ Q ↔¬P ∧ ¬Q答案：B9. 以下哪个是集合的幂集？A. 包含集合本身的所有子集的集合B. 包含集合本身的所有超集的集合C. 包含集合本身的所有真子集的集合D. 包含集合本身的所有非空子集的集合答案：A10. 在图论中，以下哪个是强连通性的图？A. 任意两个顶点之间都存在有向路径B. 任意两个顶点之间都存在无向路径C. 任意两个顶点之间都存在有向简单路径D. 任意两个顶点之间都存在无向简单路径答案：C二、填空题（每空1分，共10分）11. 命题逻辑中的“与”操作可以用符号________表示。

离散数学考试题及答案一、选择题（每题5分，共20分）1. 下列哪个选项不是离散数学的研究对象？A. 图论B. 组合数学C. 微积分D. 逻辑学答案：C2. 在逻辑学中，下列哪个命题是真命题？A. 如果今天是周一，那么明天是周二。

B. 如果今天是周一，那么明天是周三。

C. 如果今天是周一，那么明天是周四。

D. 如果今天是周一，那么明天是周五。

答案：A3. 在集合论中，下列哪个符号表示集合的并集？A. ∩B. ∪C. ⊆D. ⊂答案：B4. 在图论中，下列哪个术语描述的是图中的顶点集合？A. 边B. 路径C. 子图D. 顶点答案：D二、填空题（每题5分，共20分）1. 如果一个集合A包含5个元素，那么它的子集个数是______。

答案：322. 在逻辑学中，如果命题P和命题Q都是真命题，那么复合命题“P且Q”的真值是______。

答案：真3. 在图论中，如果一个图的顶点数为n，那么它的最大边数是______。

答案：n(n-1)/24. 如果一个二叉树的深度为3，那么它最多包含______个节点。

答案：7三、简答题（每题10分，共30分）1. 请简述什么是图的连通性，并给出一个例子。

答案：图的连通性是指在图中任意两个顶点之间都存在一条路径。

例如，在一个完全图K3中，任意两个顶点之间都可以通过一条边直接连接，因此它是连通的。

2. 解释什么是逻辑蕴含，并给出一个例子。

答案：逻辑蕴含是指如果一个命题P为真，则另一个命题Q也必须为真。

例如，命题P：“如果今天是周一”，命题Q：“明天是周二”。

如果今天是周一，那么根据逻辑蕴含，明天必须是周二。

3. 请描述什么是二叉搜索树，并给出它的一个性质。

答案：二叉搜索树是一种特殊的二叉树，其中每个节点的左子树只包含小于当前节点的数，右子树只包含大于当前节点的数。

它的一个性质是中序遍历可以得到一个有序序列。

四、计算题（每题15分，共30分）1. 给定一个集合A={1, 2, 3, 4, 5}，请计算它的幂集，并列出所有元素。

离散数学考试题目及答案1. 试述命题逻辑中的等价关系和蕴含关系。

答案：命题逻辑中的等价关系是指两个命题在所有可能的真值赋值下都具有相同的真值。

若命题P和Q等价，则记作P⇔Q。

蕴含关系是指如果命题P为真，则命题Q也为真，但Q为真时P不一定为真。

若命题P蕴含Q，则记作P→Q。

2. 证明：若集合A和B的交集非空，则它们的并集包含A和B。

答案：设x属于A∩B，即x同时属于A和B。

根据并集的定义，若元素属于A或B，则它属于A∪B。

因此，x属于A∪B。

由于x是任意属于A∩B的元素，所以A∩B≠∅意味着A∪B至少包含A∩B中的所有元素，即A∪B包含A和B。

3. 给定一个有向图G，如何判断G中是否存在环？答案：判断有向图G中是否存在环，可以采用深度优先搜索（DFS）算法。

在DFS过程中，记录每个顶点的访问状态，如果遇到一个已访问过的顶点，且该顶点不是当前路径的直接前驱，则表示存在环。

4. 描述有限自动机的组成部分及其功能。

答案：有限自动机由以下几部分组成：输入字母表、状态集合、转移函数、初始状态和接受状态集合。

输入字母表定义了自动机可以接收的符号集合；状态集合包含了自动机所有可能的状态；转移函数定义了在给定输入符号和当前状态的情况下，自动机如何转移到下一个状态；初始状态是自动机开始工作时的状态；接受状态集合包含了所有使自动机接受输入字符串的状态。

5. 什么是图的连通分量？如何确定一个无向图的连通分量？答案：图的连通分量是指图中最大的连通子图。

在一个无向图中，如果两个顶点之间存在路径，则称这两个顶点是连通的。

确定无向图的连通分量可以通过深度优先搜索（DFS）或广度优先搜索（BFS）算法。

从任一顶点开始搜索，搜索过程中访问的所有顶点构成一个连通分量。

重复此过程，直到所有顶点都被访问过，即可确定图中所有连通分量。

离散数学考试题目及答案一、单项选择题（每题2分，共20分）1. 集合A={1,2,3}，集合B={3,4,5}，则A∩B的元素个数为：A. 0B. 1C. 2D. 3答案：B2. 函数f: X→Y是一个双射，当且仅当：A. f是单射且满射B. f是单射C. f是满射D. f是双射答案：A3. 命题p: "x是偶数"，命题q: "x是3的倍数"，下列逻辑运算中，表示"x是6的倍数"的是：A. p∧qB. p∨qC. ¬p∧¬qD. ¬p∨¬q答案：A4. 有向图G中，若存在从顶点u到顶点v的有向路径，则称顶点u可达顶点v。

若G中任意两个顶点都相互可达，则称G为：A. 强连通图B. 弱连通图C. 无向图D. 有向无环图答案：A5. 在二进制数系统中，下列哪个数的值最大？A. 1010B. 1100C. 1110D. 1101答案：C6. 布尔代数中，逻辑或运算符表示为：A. ∧B. ∨C. ¬D. →答案：B7. 有限自动机中，状态q0是初始状态，状态q1是接受状态。

若存在从q0到q1的ε-转移，则该自动机：A. 仅在输入为空时接受B. 仅在输入非空时接受C. 无论输入为何都接受D. 无法确定是否接受答案：C8. 命题逻辑中，若命题p和q都为真，则p∧q的真值是：A. 真B. 假C. 可能为真，也可能为假D. 无法确定答案：A9. 集合{1,2,3}的子集个数为：A. 4B. 6C. 7D. 8答案：D10. 若关系R在集合A上是自反的，则对于A中的任意元素a，有：A. (a,a)∈RB. (a,a)∉RC. (a,a)是R的自反对D. (a,a)不是R的自反对答案：A二、填空题（每题3分，共15分）1. 集合A={1,2,3}的幂集包含__个元素。

答案：82. 若函数f: X→Y是满射，则对于Y中的任意元素y，至少存在X中的一个元素x，使得f(x)=__。

大学离散数学试卷一及答案一、单项选择题(本大题共10小题，每小题2分，共20分)1.下列不是命题的是[ C ]。

A.7能被3整除.B.5是素数当且仅当太阳从西边升起.C.x加7小于0.D.华东交通大学位于南昌北区.2. 设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为[ D ]。

A. p→qB. ⌝p→qC. ⌝q→pD. q→p3. 下面4个推理定律中，不正确的为[ D ]。

A.A=>(A∨B) (附加律)B. (A∨B)∧⌝A=>B (析取三段论)C. (A→B)∧A=>B (假言推理)D. (A→B)∧⌝B=>A (拒取式)4. 设解释I如下，个体域D={1,2},F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1，在解释I下，下列公式中真值为1的是[ A ]。

A.∀x ∃yF(x,y)B. ∃x∀yF(x,y)C. ∀x∀yF(x,y)D. ⌝∃x∃yF(x,y)5. 下列四个命题中哪一个为真？[ D ]。

A. ∅∈∅B. ∅∈{a}C. ∅∈{{∅}}D. ∅⊆∅6. 设S={a,b,c,d}，R={<a,a>,<b,b>,<d,d>}，则R的性质是[ B ]。

A.自反、对称、传递的B. 对称、反对称、传递的C.自反、对称、反对称的D. 只有对称性7.设A={a,b,c}，则下列是集合A的划分的是[ D ]。

A.{{b,c},{c}}B.{{a,b},{a,c}}C.{{a,b},c}D.{{a},{b,c}}8. 设集合})关于普通数的乘法，不正确的有[ C ]。

ab+=aQ∈2,{)2(QbA. 结合律成立B. 有幺元C. 任意元素有逆元D. 交换律成立9.设A是非空集合，P(A)是A的幂集，∩是集合交运算，则代数系统〈P(A),∩〉的幺元是[ C ]。

A. P(A)B. φC. AD. E10.下列四组数据中，不能成为任何4阶无向简单图的度数序列的为[ C ]。

大学《离散数学》期末考试试卷及答案(1)一、选择题1. 离散数学的主要研究对象是（）。

A. 连续的数学结构B. 有限的数学结构C. 数学的综合应用D. 数学的哲学思考2. 命题逻辑是离散数学的一个重要组成部分，它主要研究（）。

A. 命题之间的真假关系B. 变量之间的关系C. 函数之间的关系D. 集合之间的关系3. 集合的基本运算包括（）。

A. 并、交、差、补B. 加、减、乘、除C. 包含、相等、不等、自反D. 大于、小于、等于、不等于二、填空题1. 若集合A={m|2m-1>3}，则A中的元素为______。

2. 有一个集合A={1，2，3}，则集合A的幂集为______。

3. 若命题p为真，命题q为假，则复合命题“p∧q”的真值为______。

三、解答题1. 请写出离散数学中常用的数学符号及其含义。

2. 请解释命题逻辑中的充分必要条件及其符号表示，并给出一个例子。

3. 请定义集合的笛卡尔积，并给出两个集合进行笛卡尔积运算的例子。

四、问答题1. 离散数学在计算机科学中有着重要的应用，请列举三个与计算机科学相关的离散数学应用领域并简要介绍。

2. 请简要解释归纳法在离散数学中的作用，并给出一个使用归纳法证明的例子。

3. 什么是有向图？请给出一个有向图的例子，并解释该图中的关系。

参考答案：一、选择题1. B2. A3. A二、填空题1. A={m|2m-1>3}2. {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}3. 假三、解答题1. 常用数学符号及含义：- ∪：并，表示集合的合并操作。

- ∩：交，表示集合的交集操作。

- ∖：差，表示减去一个集合中的元素。

- ⊆：包含，表示一个集合包含于另一个集合。

- =：相等，表示两个集合具有相同的元素。

2. 充分必要条件是指一个命题的成立与另一个命题的成立互为必要条件，若A是B的充分必要条件，那么当A成立时B一定成立，且当A不成立时B也一定不成立。

江苏技术师范学院20 —20 学年第 学期《离散数学》试卷（1）参考答案与评分标准一、单项选择题（本大题共5道小题，每小题2分，共10分）1．设A={1,2,3},B={1,2,3,4,5},C={2,3}, 则(A ⋃B)- C =（ C ）。

A.{1,2}B.{2,3}C.{1,4,5}D.{1,2,3}2．在自然数集N 上定义二元运算*如下，满足交换律的是（ C ）。

A. a*b=a-bB. a*b=a+2bC. a*b=min{a,b}D. a*b=a3．设集合A={a,b,c},A 上的关系R={<a,a>,<b,b>}具备下列性质（ D ）。

A.等价性B.自反性C.反自反性D.反对称性4．当且仅当为下面条件中的哪一个时，无向简单图G 是哈密顿图？（ D ）。

A. G 的每对结点的度数不大于顶点的个数B. G 的每对结点的度数大于顶点的个数C. G 的每对结点的度数小于顶点的个数D. G 的每对结点的度数不小于顶点的个数5．设B(x)：x 是金子；F(x)：x 会发光；则金子都会发光可符号化为：（ B ）。

A. )()(x F x xB →∀B. ))()((x F x B x →∀C. )()(x F x xB ∧∀D. ))()((x F x B x ∧∀二、填空（本大题共10空，每空2分，共20分）1.设p ：我们勤奋，q ：我们好学，r ：我们取得好成绩。

命题“只要勤奋好学，我们就能取得好成绩”符号化为 p ∧q →r 。

2.若连通的简单图中所有结点的度数为 偶数 ，则该图一定是欧拉图。

3.群<Z 6,+6>的所有子群是：_<Z 6,+6>，<{0,2,4},+6>，<{0,3},+6>，<{0},+6>_。

4.n 个结点的无向完全图的边数m 为 n(n-1)/2 。

5.集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,y ∈A}，则R 的性质为 对称性 。

离散数学期末考试题及答案一、单项选择题（每题2分，共20分）1. 集合A={1,2,3}，B={2,3,4}，则A∩B=（）。

A. {1,2,3}B. {2,3}C. {2,4}D. {1,4}答案：B2. 命题“若x>0，则x>1”的逆否命题是（）。

A. 若x≤0，则x≤1B. 若x≤1，则x≤0C. 若x>1，则x>0D. 若x≤1，则x≤0答案：B3. 函数f: A→B的定义域是集合A，值域是集合B，则（）。

A. A⊆BB. A⊂BC. A⊇BD. A⊃B答案：A4. 集合{1,2,3}与集合{3,2,1}是否相等？（）。

A. 是B. 否C. 无法确定D. 以上都不对答案：A5. 命题p:“x>0”，则￢p为（）。

A. x≤0B. x<0C. x=0D. x<0或x=0答案：A6. 命题“若x>0，则x>1”的逆命题是（）。

A. 若x>0，则x>1B. 若x≤1，则x≤0C. 若x>1，则x>0D. 若x≤0，则x≤1答案：C7. 函数f: A→B的定义域是集合A，值域是集合B，则（）。

A. A⊆BB. A⊂BC. A⊇BD. A⊃B答案：A8. 集合{1,2,3}与集合{3,2,1}是否相等？（）。

A. 是B. 否C. 无法确定D. 以上都不对答案：A9. 命题p:“x>0”，则￢p为（）。

A. x≤0B. x<0C. x=0D. x<0或x=0答案：A10. 命题“若x>0，则x>1”的逆命题是（）。

A. 若x>0，则x>1B. 若x≤1，则x≤0C. 若x>1，则x>0D. 若x≤0，则x≤1答案：C二、填空题（每题2分，共20分）1. 集合A={1,2,3}，B={2,3,4}，则A∪B=______。

答案：{1,2,3,4}2. 命题“若x>0，则x>1”的逆否命题是：若x≤1，则x≤0。

一、填空题:(每空1分，本大题共15分）1．给定命题公式A 、B ，若 ，则称A 和B 是逻辑相等的。

2．命题公式)(Q P →⌝的主析取范式为 ，主合取范式的编码表示为 。

3．设E 为全集， ,称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ，～Φ= 。

4．设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，}},{},{{3c b a S =,}},,{{4c b a S =}}{},{},{{5c b a S =，}},{},{{6c a a S =则A 的覆盖有 ，A 的划分有 。

5．设S 是非空有限集，代数系统＜（S ），，＞中，（S)对的幺元为 ，零元为 。

（S ）对的幺元为 ，零元为 .6．若>=<E V G ,为汉密尔顿图，则对于结点集V 的每个非空子集S ，均有W(G-S) S 成立，其中W （G —S)是 。

二、单项选择题：（每小题1分，本大题共10分)1．下面命题公式（ )不是重言式。

A 、)(Q P Q ∨→；B 、P Q P →∧)(；C 、)()(Q P Q P ∨⌝∧⌝∧⌝;D 、)()(Q P Q P ∨⌝↔→。

2．命题“没有不犯错误的人”符号化为( ）。

设x x M ：)(是人，x x P ：)(犯错误。

A 、))()((x P x M x ∧∀; B 、)))()(((x P x M x ⌝→∃⌝；C 、)))()(((x P x M x ∧∃⌝；D 、)))()(((x P x M x ⌝∧∃⌝。

3．设}{Φ=A ，B =((A ））,下列各式中哪个是错误的（ ）。

A 、B ⊆Φ; B 、B ⊆Φ}{，C 、B ∈Φ}}{{；D 、⊆ΦΦ}}{,{(A ）。

4．对自然数集合N ，哪种运算不是可结合的，运算定义为任N b a ∈,（ ）.A 、),min(b a b a =*;B 、b a b a 2+=*;C 、3++=*b a b a ；D 、)3(mod ,b a b a =*。