离散数学（）2017年7月份试题
单项选择题（题3分题15分）
1．设A{1 3 5 7 9｝B{2 4 6}AB关系R{|xy1｝R ( )．
A．{<1 2> <2 3> <3 4>} B．{<1 2> <3 4> <5 6>}
C．{<1 1> <2 2> <3 6>} D．{<3 2> <5 4> <7 6>}
2．集合A＝{a b c}列表述正确( )．
A．{a b }ÍA B．{a}ÎA
C．{a b}ÎA D．ÆÎA
3．设体域集合{12345}公式(x)(y)(x+y5)解释 ( )．
A．存整数x整数y满足x+y5
B．整数x存整数y满足x+y5
C．存整数x意整数y满足x+y5
D．整数x意整数y满足x+y5
4．设G连通图（ ）时G中存欧拉回路．
A．G存两奇数度数结点 B．G存奇数度数结点
C．G存奇数度数结点 D．G存偶数度数结点
5．n阶完全图Kn边数结点度数分（ ）．
A．n(n1)n B．n(n1)2n1
C．n1n D．n(n1)n1
二填空题（题3分题15分）
6．设集合A{1 2 3}B{2 3}C{3 4}A∪(BC) ．
7．设A{ab}B{12}C{ab}AB函数f{ }BC函数g{<1b> <2a >}g° f等 ．
8．设G图| E |10G结点度数 ．
9．设G具n结点m条边k面连通面图n+k 2 ．
10．设体域D＝{1 2 3}A(x)x2倍2谓词公式（x）A(x)真值 ．
三逻辑公式翻译（题6分题12分）
11．语句果掌握计算机法完成项工作．翻译成命题公式．
12．语句前天雨昨天雨．翻译成命题公式．
四判断说明题（判断题正误说明理．题7分题14分）
13．设A{ abc }R{< aa > < bb > < cc > < ab >< ba >< bc >< cb >}R等价关系．
14．(x)(P(x)∧Q(y)→R(x))中量词辖域(P(x)∧Q(y))．
五．计算题（题12分题36分）
15．设集合A{a b c d }B{a b}试计算
（1）AÈB （2）A B （3）A×B．
16．设GV{v1 v2 v3 v4}E{(v1v2) (v1v3) (v1v4) (v2v3) (v3v4)}试
（1）出G图形表示 （2）写出邻接矩阵
（3）求出结点度数 （4）画出补图图形．
17．试利Kruskal算法求出示赋权图中生成树（求写出求解步骤）求生成树权．
六证明题（题8分）
18．试证明：ØP∨Q Þ P→ Ø (P→ ØQ) ．
离散数学（）2017年7月份试题
参考解答
单项选择题（题3分题15分）
1．D 2．A 3．B 4．C 5．B
二填空题（题3分题15分）
6．{1 2 3}
7．{ }
8．20（：2|E|）
9．m
10．假（F0）
三逻辑公式翻译（题6分题12分）
11．设P：掌握计算机法 Q：完成项工作． （2分）
命题公式： P ® Q． （6分）
12．设P：前天雨 Q：昨天雨． （2分）
命题公式：P∧Q． （6分）
四判断说明题（题7分题14分）
13．错误． （3分）
R等价关系R中包含< ab >< bc >包含< ac >满足传递性． （7分）
14．错误． （3分）
辖域紧接量词子公式(P(x)∧Q(y)→R(x))． （7分）
五．计算题（题12分题36分）
15．（1）AÈB{ a b c d} （4分）
（2）A B{ c d} （8分）
（3）A×B{ < c b > < d b >} （12分）
v1
o
o
o
o
v2
v3
v4
图
16．（1）G图形表示图示：
（3分）
（2）邻接矩阵：
（6分）
（3） deg(v1)3
deg(v2)2
deg(v3)3
deg(v4)2 （9分）
v1
o
o
o
o
v2
v3
v4
图二
（4）补图图二示：
（12分）
17． Kruskal算法求产生生成树步骤：
w(v1v7) 1 选e1v1v7
w(v3v4) 3 选e2v3v4
w(v2v7) 4 选e3v2v7
w(v3v7) 9 选e4v3v7
w(v4v5) 18选e5v4v5
w(v1v6) 22选e6v1v6 （6分）
生成树图三示：
（9分）
图三
生成树权C(T) 1+3+4+9+18+2257． （12分）
六证明题（题8分）
18．证明：
（1）ØP∨Q P （1分）
（2）P P（附加前提） （2分）
（3）Q T（1）（2）I （4分）
（4）P∧Q T（2）（3）I （5分）
（5）Ø (ØP∨ØQ) T（4）E （6分）
（6）Ø (P→ ØQ) T（5）E （7分）
（7）P→Ø (P→ ØQ) CP规 （8分）
说明：证明程中公式引次序般引前提正确1分利两公式出效结12分出结21分．
真值表验证．
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
单项选择题（题3分题15分）
1．设A{1 3 5 7 9｝B{2 4 6}AB关系R{
A．{<1 2> <2 3> <3 4>} B．{<1 2> <3 4> <5 6>}
C．{<1 1> <2 2> <3 6>} D．{<3 2> <5 4> <7 6>}
2．集合A＝{a b c}列表述正确( )．
A．{a b }ÍA B．{a}ÎA
C．{a b}ÎA D．ÆÎA
3．设体域集合{12345}公式(x)(y)(x+y5)解释 ( )．
A．存整数x整数y满足x+y5
B．整数x存整数y满足x+y5
C．存整数x意整数y满足x+y5
D．整数x意整数y满足x+y5
4．设G连通图（ ）时G中存欧拉回路．
A．G存两奇数度数结点 B．G存奇数度数结点
C．G存奇数度数结点 D．G存偶数度数结点
5．n阶完全图Kn边数结点度数分（ ）．
A．n(n1)n B．n(n1)2n1
C．n1n D．n(n1)n1
二填空题（题3分题15分）
6．设集合A{1 2 3}B{2 3}C{3 4}A∪(BC) ．
7．设A{ab}B{12}C{ab}AB函数f{
8．设G
9．设G具n结点m条边k面连通面图n+k 2 ．
10．设体域D＝{1 2 3}A(x)x2倍2谓词公式（x）A(x)真值 ．
三逻辑公式翻译（题6分题12分）
11．语句果掌握计算机法完成项工作．翻译成命题公式．
12．语句前天雨昨天雨．翻译成命题公式．
四判断说明题（判断题正误说明理．题7分题14分）
13．设A{ abc }R{< aa > < bb > < cc > < ab >< ba >< bc >< cb >}R等价关系．
14．(x)(P(x)∧Q(y)→R(x))中量词辖域(P(x)∧Q(y))．
五．计算题（题12分题36分）
15．设集合A{a b c d }B{a b}试计算
（1）AÈB （2）A B （3）A×B．
16．设G
（1）出G图形表示 （2）写出邻接矩阵
（3）求出结点度数 （4）画出补图图形．
17．试利Kruskal算法求出示赋权图中生成树（求写出求解步骤）求生成树权．
六证明题（题8分）
18．试证明：ØP∨Q Þ P→ Ø (P→ ØQ) ．
离散数学（）2017年7月份试题
参考解答
单项选择题（题3分题15分）
1．D 2．A 3．B 4．C 5．B
二填空题（题3分题15分）
6．{1 2 3}
7．{
8．20（：2|E|）
9．m
10．假（F0）
三逻辑公式翻译（题6分题12分）
11．设P：掌握计算机法 Q：完成项工作． （2分）
命题公式： P ® Q． （6分）
12．设P：前天雨 Q：昨天雨． （2分）
命题公式：P∧Q． （6分）
四判断说明题（题7分题14分）
13．错误． （3分）
R等价关系R中包含< ab >< bc >包含< ac >满足传递性． （7分）
14．错误． （3分）
辖域紧接量词子公式(P(x)∧Q(y)→R(x))． （7分）
五．计算题（题12分题36分）
15．（1）AÈB{ a b c d} （4分）
（2）A B{ c d} （8分）
（3）A×B{
v1
o
o
o
o
v2
v3
v4
图
16．（1）G图形表示图示：
（3分）
（2）邻接矩阵：
（6分）
（3） deg(v1)3
deg(v2)2
deg(v3)3
deg(v4)2 （9分）
v1
o
o
o
o
v2
v3
v4
图二
（4）补图图二示：
（12分）
17． Kruskal算法求产生生成树步骤：
w(v1v7) 1 选e1v1v7
w(v3v4) 3 选e2v3v4
w(v2v7) 4 选e3v2v7
w(v3v7) 9 选e4v3v7
w(v4v5) 18选e5v4v5
w(v1v6) 22选e6v1v6 （6分）
生成树图三示：
（9分）
图三
生成树权C(T) 1+3+4+9+18+2257． （12分）
六证明题（题8分）
18．证明：
（1）ØP∨Q P （1分）
（2）P P（附加前提） （2分）
（3）Q T（1）（2）I （4分）
（4）P∧Q T（2）（3）I （5分）
（5）Ø (ØP∨ØQ) T（4）E （6分）
（6）Ø (P→ ØQ) T（5）E （7分）
（7）P→Ø (P→ ØQ) CP规 （8分）
说明：证明程中公式引次序般引前提正确1分利两公式出效结12分出结21分．
真值表验证．
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
