第一篇：离散数学试卷及答案
离散数学期末考试试题及答案
离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。下面是小编整理的离散数学期末考试试题及答案，欢迎阅读参考!
一、【单项选择题】
(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。
1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。
[A] 3 [B] 8 [C]9 [D]27
2、设A1,2,3,5,8,B1,2,5,7,则AB( )。
[A] 3,8 [B]3 [C]8 [D]3,8
3、若X是Y的子集，则一定有( )。
[A]X不属于Y [B]X∈Y
[C]X真包含于 Y [D]X∩Y=X
4、下列关系中是等价关系的是( )。
[A]不等关系 [B]空关系
[C]全关系 [D]偏序关系
5、对于一个从集合A到集合B的映射，下列表述中错误的是( )。
[A]对A的每个元素都要有象 [B] 对A的每个元素都只有一个象
[C]对B的每个元素都有原象 [D] 对B的元素可以有不止一个原象
6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为( )。
[A]p→q [B]q→p [C]┐q→┐p [D]┐p→q
7、设A={a,b,c},则A到A的双射共有( )。
[A]3个 [B]6个 [C]8个 [D]9个
8、一个连通G具有以下何种条件时，能一笔画出：即从某结点出发，经过中每边仅一次回到该结点( )。
[A] G没有奇数度结点 [B] G有1个奇数度结点
[C] G有2个奇数度结点 [D] G没有或有2个奇数度结点
9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是( )。
[A] G中有幺元 [B] G中么元是唯一的
[C] G中任一元素有逆元 [D] G中除了幺元外无其他幂等元
10、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为( )
[A] p→┐q [B] p∨┐q
[C] p∧q [D] p∧┐q
11、设G=的结点集为V={v1,v2,v3},边集为E={,}.则G的割(点)集是( )。
[A]{v1} [B]{v2} [C]{v3} [D]{v2,v3}
12、下面4个推理定律中，不正确的为( )。
[A]A=>(A∨B) (附加律) [B](A∨B)∧┐A=>B (析取三段论)
[C](A→B)∧A=>B (假言推理) [D](A→B)∧┐B=>A (拒取式)
13、在右边中过v1,v2的初级回路有多少条( )
[A] 1 [B] 2 [C] 3 [D]
414、若R,,是环，且R中乘法适合消去律，则R是( )。
[A]无零因子环
[C]整环 [B]除环 [D]域
15、无向G中有16条边，且每个结点的度数均为2，则结点数是( )。
[A]8 [B]16 [C]4 [D]
32二、【判断题】
(本大题共8小题，每小题3分，共24分)正确的填T，错误的填F，填在答题卷相应题号处。
16、是空集。 ( )
17、设S,T为任意集合，如果S—T=，则S=T。 ( )
18、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。 ( )
19、关系的复合运算满足交换律。 ( )
20、集合A上任一运算对A是封闭的。 ( )
21、0,1,2,3,4,max,min是格。 ( )
22、强连通有向一定是单向连通的。 ( )
23、设都是命题公式，则(PQ)QP。 ( )
三、【解答题】
(本大题共3小题，
24、25每小题10分，26小题11分，共31分)请将答案填写在答题卷相应题号处。
24、设集合A={a, b, c}，B={b, d, e}，求
(1)BA; (2)AB; (3)A-B; (4)BA.25、设非空集合A，验证(P(A),,,~,,A)是布尔代数
26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。
离散数学试题答案
一、【单项选择题】(本大题共15小题，每小题3分，共45分)
BDDCCCBABDADCBB
二、【判断题】(本大题共8小题，每小题3分，共24分)
FFTFTTTF
三、【解答题】(本大题共3小题，
24、25每小题10分，26小题11分，共31分)
24、设集合A={a, b, c}，B={b, d, e}，求 (1)BA; (2)AB; (3)A-B; (4)BA. 标准答案：(1)BA={a, b, c}{b, d, e}={ b }
(2)AB={a, b, c}{b, d, e}={a, b, c, d, e }
(3)A-B={a, b, c}-{b, d, e}={a, c}
(4)BA= AB-BA={a, b, c, d, e }-{ b }={a, c, d, e }
复习范围或考核目标：考察集合的基本运算，包括交集，并集,见课件第一章第
二节,集合的运算。
25、设非空集合A，验证(P(A),,,~,,A)是布尔代数
标准答案：证明 因为集合A非空，故P(A)至少有两个元素，显然，是P(A)上的二元运算. 由定理10 ，任给B,C,DP(A), H1 BD=DC CD=DC
H2 B(CD)=(BC)(BD) B(CD)=(BC)(BD)
H3 P(A)存在和A，BP(A), 有B=B， BA=B
H4，BP(A), BA，存在A~B，有
BA~B)= A B(A～B)=
所以(P(A),,,~,,A)是布尔代数.复习范围或考核目标：考察布尔代数的基本概念，集合的运算，见课件代数系统中布尔代数小节。
26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。
标准答案：令p：他是计算机系本科生
q：他是计算机系研究生 r：他学过DELPHI语言
s:他学过C++语言
t:他会编程序
前提：(p∨q)→(r∧s),(r∨s)→t
结论：p→t
证①p P(附加前提)
②p∨q T①I
③(p∨q)→(r∧s) P(前提引入)
④r∧s T②③I
⑤r T④I
⑥r∨s T⑤I
⑦(r∨s)→t P(前提引入)
⑧t T⑤⑥I
第二篇：离散数学期末复习试题及答案(一)
离散数学习题参考答案
第一章 集合
1.分别用穷举法，描述法写出下列集合 (1) 偶数集合
(2)36的正因子集合 (3)自然数中3的倍数 (4)大于1的正奇数
(1) E={，-6，-4，-2，0，2，4，6，}
={2 i | i I }
(2) D= { 1, 2, 3, 4, 6, } = {x>o | x|36 }
(3) N3= { 3, 6, 9, ```} = { 3n | nN }
(4) Ad= {3, 5, 7, 9, ```} = { 2n+1 | nN }
2.确定下列结论正确与否 (1)φφ
× (2)φ{φ｝√ (3)φφ√ (4)φ{φ｝√ (5)φ{a｝× (6)φ{a｝√
(7){a，b｝{a，b，c，{a，b，c｝｝×(8){a，b｝{a，b，c，{a，b，c｝｝√(9){a，b｝{a，b，{{a，b｝｝｝× (10){a，b｝{a，b，{{a，b｝｝｝√
3.写出下列集合的幂集 (1){{a｝｝
{φ, {{ a }}}
( 2 ) φ
{φ} (3){φ，{φ｝｝
{φ, {φ}, {{φ}}, {φ,{φ}} } (4){φ，a，{a，b｝｝
{φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }},
{a, {a b }}, {φ,a,{ a, b }} } (5)P(P(φ))
{φ, {φ}, {{φ}}, {φ,{φ}} }
4.对任意集合A，B，C，确定下列结论的正确与否 (1)若AB，且BC，则AC√ (2)若AB，且BC，则AC× (3)若AB，且BC，则AC× (4)若AB，且BC，则AC ×
5.对任意集合A，B，C，证明
(1)A(BC)(AB)(AC) 左差A(BC)差A(BC)D.MA(BC)
分配(AB)(AC)右(2)A(BC)(AB)(AC)1)左差A(BC)(1)的结论(AB)(AC) 差(AB)(AC)右
2)左差A(BC)D.MA(BC)分配(AB)(AC)差(AB)(AC)右(3)A(BC)(AB)(AC)左差A(BC)D.MA(BC) 幂等(AA)(BC)
结合,交换(AB)(AC)右(4)(AB)BAB 左差(AB)B对称差((AB)B)((AB)B)
分配,结合((AB)(BB))(A(B)B))
2 互补((AB)U)(A)
零一
(AB)(AB)右(5)(AB)CA(BC) 左差(AB)C结合A(BC)
D.MA(BC)差A(BC)(6)(AB)C(AC)B左差(AB)C结合A(BC)交换A(CB)结合(AC)B
差(AC)B右(7)(AB)C(AC)(BC)右(5)A(C(BC))差A(C(BC)) 分配A((CB)(CC))互补A((CB)U)
零一A(CB)交换A(BC)(5)(AB)C左
6.问在什么条件下，集合A，B，C满足下列等式
(1)A(BC)(AB)C左(AB)(AC)右若要右左,须CA(BC),
CA时等式成立
(2)ABA左右是显然的,AABAB,AB,
AB时等式成立
(3)ABBABB,BB,B,代入原式得A,
AB时等式成立
(4)ABBAABBA,只能AB,AB, BA,BA,AB时等式成立
(5)ABAB,若B,bB,
当bA,bABA矛盾;当bA,bABA矛盾
(6)ABAB右左是显然的,ABAB,AAB,ABBAB,BAABAB时等式成立
(7)(AB)(AC)A左(AB)(AC)A(BC)A(BC)A(BC)A
ABC时等式成立
(8)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)
A(BC),AB,AC时等式成立
(9)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)
A(BC)时等式成立
(10)(AB)(AC)((AB)(AC))((AB)(AC))(AB)(AC)(AB)(AC)
由(6)知,(AB)(AC),ABAC,ABAC时等式成立
(11)A(BA)BA(BA)(AB)(AA)(AB)U(AB)B
AB时等式成立
7.设A={a，b，{a，b｝，｝，求下列各式(1)φ∩{φ｝=φ (2){φ｝∩{φ｝={φ} (3){φ，{φ｝｝-φ={φ,{φ}} (4){φ，{φ｝｝-{φ｝= {{φ}} (5){φ，{φ｝｝-{{φ｝｝={φ} (6)A-{a，b｝={{a,b}, φ} (7)A-φ = A (8)A-{φ｝={a,b,{a,b}} (9)φ-A=φ (10){φ｝-A=φ
8.在下列条件下，一定有B=C吗? (1) ABAC
否，例：A={1，2，3}，B={4}，C={3,4}, ABAC{1,2,3,4},而BC。
(2)ABAC
否，例：A={1，2，3}，B={2，3}，C={2，3，4} ABAC{2,3},而BC。
(3)ABAC
对,若BC,不妨,aB,aC,若aA,aAB,aAB,aAB,aAC,aAC,aAC; 若aA,aAB,aAB,aAB,aAC,aAC,aAC矛盾(4)ABAC且ABAC
bB,若bA,bABAC,bC,若bA,bABAC,bC,
BC,同理,CB,BC
9. (1) (AB)(BC)AB
证:a左,a(BC),aB,aB;a(AB),而aB,aA,aAB
(2)若A(BC)且B(AC),则B。
若B,aB(AC)(AC),aA(BC),aC,aB即aB,矛盾
10.化简
((ABC)(AB))((A(BC))A)(AB)A(AB)A
(AA)(BA)(BA)BA11. 设A={2，3，4}，B={1，2}，C={4，5，6}，求 (1)AB{1, 3, 4} (2)ABC{1,3,5,6} (3)(AB)(BC){2,3,5,6}
12. 设A={1，2，3，4}，B={1，2，5}，求
(1) P(A)P(B){φ,{1},{2},{1,2}}
(2) P(A)P(B)
{φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}, {1,2,3,},{1,2,4,},{1,3,4,},{2,3,4},{1,2,3,4,},{5},{1,5}, {2,5},{1,2} }
(3)P(A)P(B)
{ {3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},
{2,3,4},{1,2,3,4} }
(4)P(A)P(B)
{{3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}, {2,3,4},{1,2,3,4},{5},{1,5},{2,5},{1,2,5} }
第三篇：离散数学考试试题（A卷及答案）
一、(10分)判断下列公式的类型(永真式、永假式、可满足式)? 1)((PQ)∧Q)((Q∨R)∧Q) 2)((QP)∨P)∧(P∨R) 3)((P∨Q)R)((P∧Q)∨R) 解：1)永真式;2)永假式;3)可满足式。
二、(8分)个体域为{1，2}，求xy(x+y=4)的真值。
解：xy(x+y=4)x((x+1=4)∨(x+2=4))
((1+1=4)∨(1+2=4))∧((2+1=4)∨(2+1=4)) (0∨0)∧(0∨1) 1∧10
三、(8分)已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少?A到B的函数数是多少?
解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。
四、(10分)已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。
解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}
五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。
解 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|=20，|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|=55，|A|+|B|+|C|=70/0.5=140。
由容斥原理，得
|A∪B∪C|=|A|+|B|+|C|―|A∩B|―|A∩C|―|B∩C|+|A∩B∩C| 所以
|A∩B∩C|=75-|A∪B∪C|=75-(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|)+|A∩B∩C|=75-140+55+20=10 没有乘坐过其中任何一种的儿童共10人。
六、(12分)已知R和S是非空集合A上的等价关系，试证：1)R∩S是A上的等价关系;2)对a∈A，[a]R∩S=[a]R∩[a]S。
解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。
x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。
1 x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。
总之R∩S是等价关系。
2)因为x∈[a]R∩S∈R∩S∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。
七(10分)设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()=。证明h是双射。
证明：1)先证h是满射。
∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()==，所以h是满射。
2)再证h是单射。
、∈A×C，若h()=h()，则=，所以f(a1)=f(a2)，g(c1)=g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1=a2，c1=c2，所以=，所以h是单射。 综合1)和2)，h是双射。
八、(12分)是个群，u∈G，定义G中的运算“”为ab=a*u-1*b，对任意a,b∈G，求证：也是个群。
证明：1)a,b∈G，ab=a*u-1*b∈G，运算是封闭的。
2)a,b,c∈G，(ab)c=(a*u-1*b)*u-1*c=a*u-1*(b*u-1*c)=a(bc)，运算是可结合的。 3)a∈G，设E为的单位元，则aE=a*u-1*E=a，得E=u，存在单位元。
4)a∈G，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。 所以也是个群。
九、(10分)已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。
解：D的邻接距阵A和可达距阵P如下：
A= 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0
1 0 1 0 0
0 0 1 0 0
P=
1 1 1 0 1
1 1 1 0 1
1 1 1 0 1
1 1 1 0 1
1 1 1 0 1
十、(10分)求叶的权分别为
2、
4、
6、
8、
10、
12、14的最优二叉树及其权。
解：最优二叉树为
权=148
离散数学考试试题(B卷及答案)
一、(10分)求命题公式(P∧Q)(PR)的主合取范式。
解：(P∧Q)(PR)((P∧Q)(PR))∧((PR)(P∧Q))((P∧Q)∨(P∧R))∧((P∨R)∨(P∨Q)) (P∧Q)∨(P∧R) (P∨R)∧(Q∨P)∧(Q∨R)
(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M1∧M3∧M4∧M5
二、(8分)叙述并证明苏格拉底三段论
解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化：F(x)：x是一个人。G(x)：x要死的。A：苏格拉底。 命题符号化为x(F(x)G(x))，F(a)G(a) 证明：
(1)x(F(x)G(x)) P (2)F(a)G(a) T(1),US (3)F(a) P (4)G(a) T(2)(3),I
三、(8分)已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) 证明：∵x A∩(B∪C) x A∧x(B∪C)
x A∧(xB∨xC)
( x A∧xB)∨(x A∧xC) x(A∩B)∨x A∩C x(A∩B)∪(A∩C)
∴A∩(B∪C)=(A∩B)∪(A∩C)
四、(10分)已知R和S是非空集合A上的等价关系，试证：1)R∩S是A上的等价关系;2)对a∈A，[a]R∩S=[a]R∩[a]S。
解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。
x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。
x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。
总之R∩S是等价关系。
2)因为x∈[a]R∩S∈R∩S
∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。
五、(10分) 设A={a，b，c，d}，R是A上的二元关系，且R={，，，}，求r(R)、s(R)和t(R)。
解 r(R)=R∪IA={，，，，，，，} s(R)=R∪R={，，，，，} R={，，，} R={，，，} R={，，，}=R
t(R)=R={，，，，，，，，} i1i
4232-
1六、(15分) 设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()=。证明h是双射。
证明：1)先证h是满射。
∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()==，所以h是满射。
2)再证h是单射。
、∈A×C，若h()=h()，则= ，所以f(a1)=f(a2)，g(c1)=g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1=a2，c1=c2，所以=，所以h是单射。
综合1)和2)，h是双射。
七、(12分)设是群，H是G的非空子集，证明是的子群的充要条件是若a，bH，则有a*bH。
证明： a,b∈H有b∈H，所以a*b∈H。 a∈H，则e=a*a∈H
4 -1-
1-1-1a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*(b)∈H ∵HG且H≠,∴*在H上满足结合律 ∴是的子群。
八、(10分)设G=是简单的无向平面图，证明G至少有一个结点的度数小于等于5。
解：设G的每个结点的度数都大于等于6，则2|E|=d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图-
1-1
-1-1-1的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。 九.G=,A={a,b,c},*的运算表为：(写过程，7分)
(1)G是否为阿贝尔群?
(2)找出G的单位元;(3)找出G的幂等元(4)求b的逆元和c的逆元 解：(1)(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c) (a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b) (b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c) 所以G是阿贝尔群
(2)因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a (3)因为a*a=a 所以G的幂等元是a (4)因为b*c=c*b=a，所以b的逆元是c且c的逆元是b
十、(10分)求叶的权分别为
2、
4、
6、
8、
10、
12、14的最优二叉树及其权。
解：最优二叉树为
权=148 5
第四篇：离散数学考试试题(A、B卷及答案)test7
离散数学考试试题(A卷及答案)
一、(10分)证明(A∨B)(P∨Q)，P，(BA)∨PA。
证明：(1)(A∨B)(P∨Q)
P (2)(P∨Q)(A∨B)
T(1)，E (3)P
P (4)A∨B
T(2)(3)，I (5)(BA)∨P
P (6)BA
T(3)(5)，I (7)A∨B
T(6)，E (8)(A∨B)∧(A∨B)
T(4)(7)，I (9)A∧(B∨B)
T(8)，E (10)A
T(9)，E
二、(10分)甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的：
(1)甲和乙只有一人参加; (2)丙参加，丁必参加; (3)乙或丁至多参加一人; (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。
解
符号化命题，设A：甲参加了比赛;B：乙参加了比赛;C：丙参加了比赛;D：丁参加了比赛。 依题意有，
(1)甲和乙只有一人参加，符号化为AB(A∧B)∨(A∧B); (2)丙参加，丁必参加，符号化为CD; (3)乙或丁至多参加一人，符号化为(B∧D); (4)丁不参加，甲也不会参加，符号化为DA。 所以原命题为：(AB)∧(CD)∧((B∧D))∧(DA) ((A∧B)∨(A∧B))∧(C∨D)∧(B∨D)∧(D∨A) ((A∧B∧C)∨(A∧B∧C)∨(A∧B∧D)∨(A∧B∧D))∧((B∧D)∨(B∧A)∨(D∧A)) (A∧B∧C∧D)∨(A∧B∧D)∨(A∧B∧C∧D)T
但依据题意条件，有且仅有两人参加竞赛，故A∧B∧C∧D为F。所以只有：(A∧B∧C∧D)∨(A∧B∧D)T，即甲、丁参加了围棋比赛。
三、(10分)指出下列推理中，在哪些步骤上有错误?为什么?给出正确的推理形式。 (1)x(P(x)Q(x))
P
1 (2)P(y)Q(y)
T(1)，US (3)xP(x)
P (4)P(y)
T(3)，ES (5)Q(y)
T(2)(4)，I (6)xQ(x)
T(5)，EG 解
(4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。
正确的推理过程为：
(1)xP(x)
P (2)P(c)
T(1)，ES
(3)x(P(x)Q(x))
P (4)P(c)Q(c)
T(3)，US (5)Q(c)
T(2)(4)，I (6)xQ(x)
T(5)，EG
四、(10分)设A={a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。
解
设R={，，，}，则 因为R，R不自反; 因为∈R，R不反自反;
因为∈R，R，R不对称; 因为∈R，∈R，R不反对称;
因为∈R，∈R，但R，R不传递。
五、(15分)设函数g：A→B，f：B→C，
(1)若fg是满射，则f是满射。 (2)若fg是单射，则g是单射。
证明
因为g：A→B，f：B→C，由定理5.5知，fg为A到C的函数。
(1)对任意的z∈C，因fg是满射，则存在x∈A使fg(x)=z，即f(g(x))=z。由g：A→B可知g(x)∈B，于是有y=g(x)∈B，使得f(y)=z。因此，f是满射。
(2)对任意的x
1、x2∈A，若x1≠x2，则由fg是单射得fg(x1)≠fg(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。
六、(15分)设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得TR且R，证明T是一个等价关系。
证明
因R自反，任意a∈A，有∈R，由T的定义，有∈T，故T自反。
若∈T，即∈R且∈R，也就是∈R且∈R，从而∈T，故T对称。
2 若∈T，∈T，即∈R且∈R，∈R且∈R，因R传递，由∈R和∈R可得∈R，由∈R和∈R可得∈R，由∈R和∈R可得∈T，故T传递。
所以，T是A上的等价关系。
七、(15分)若是群，H是G的非空子集，则是的子群对任意的a、b∈H有a*b1∈H。 -证明
必要性：对任意的a、b∈H，由是的子群，必有b1∈H，从而a*b1∈H。
-
-充分性：由H非空，必存在a∈H。于是e=a*a1∈H。
-任取a∈H，由e、a∈H得a1=e*a1∈H。
-
-对于任意的a、b∈H，有a*b=a*(b1)1∈H，即a*b∈H。
-
-又因为H是G非空子集，所以*在H上满足结合律。 综上可知，是的子群。
八、(15分)(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗?
证明
(1)设无向图G中只有两个奇数度结点u和v。从u开始构造一条回路，即从u出发经关联结点u的边e1到达结点u1，若d(u1)为偶数，则必可由u1再经关联u1的边e2到达结点u2，如此继续下去，每条边只取一次，直到另一个奇数度结点为止，由于图G中只有两个奇数度结点，故该结点或是u或是v。如果是v，那么从u到v的一条路就构造好了。如果仍是u，该回路上每个结点都关联偶数条边，而d(u)是奇数，所以至少还有一条边关联结点u的边不在该回路上。继续从u出发，沿着该边到达另一个结点u1，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v，这就是一条从u到v的路。
(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向图中，只有两个奇数度结点u和v，u和v之间都不可达。
uwv
3 离散数学考试试题(B卷及答案)
一、(15分)设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表示灯亮。
(1)写出F在全功能联结词组{}中的命题公式。 (2)写出F的主析取范式与主合取范式。
解
(1)设A：开关A关闭;B：开关B关闭;C：开关C关闭;F=(A∧C)∨(B∧C)。 在全功能联结词组{}中：
A(A∧A)AA A∧C( A∧C)( AC)(AC)(AC)
A∨B(A∧B)(( AA)∧(BB))( AA)(BB) 所以
F((AC)(AC))∨((BC)(BC)) (((AC)(AC))((AC)(AC)))(((BC)(BC))((BC)(BC))) (2)F(A∧C)∨(B∧C)
(A∧(B∨B)∧C)∨((A∨A)∧B∧C) (A∧B∧C)∨(A∧B∧C)∨(A∧B∧C)∨(A∧B∧C) m3∨m5∨m7
主析取范式 M0∧M1∧M2∧M4∧M6
主合取范式
二、(10分)判断下列公式是否是永真式? (1)(xA(x)xB(x))x(A(x)B(x))。 (2)(xA(x)xB(x))x(A(x)B(x)))。 解
(1)(xA(x)xB(x))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) (xA(x)∨xA(x)∨xB(x))∧(xB(x)∨xA(x)∨xB(x)) x(A(x)∨A(x))∨xB(x) T
所以，(xA(x)xB(x))x(A(x)B(x))为永真式。
(2)设论域为{1，2}，令A(1)=T;A(2)=F;B(1)=F;B(2)=T。
则xA(x)为假，xB(x)也为假，从而xA(x)xB(x)为真;而由于A(1)B(1)为假，所以x(A(x)B(x))也为假，因此公式(xA(x)xB(x))x(A(x)B(x))为假。该公式不是永真式。
三、(15分)设X为集合，A=P(X)-{}-{X}且A≠，若|X|=n，问 (1)偏序集是否有最大元?
4 (2)偏序集是否有最小元?
(3)偏序集中极大元和极小元的一般形式是什么?并说明理由。 解
偏序集不存在最大元和最小元，因为n>2。
考察P(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X|=n，则第n-1层是X的n-1元子集，第n层是X。偏序集与偏序集相比，恰好缺少第0层和第n层。因此的极小元就是X的所有单元集，即{x}，x∈X;而极大元恰好是比X少一个元素，即X-{x}，x∈X。
四、(10分)设A={1，2，3，4，5}，R是A上的二元关系，且R={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。
解
r(R)=R∪IA={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)=R∪R1={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} -R2={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}=R2
t(R)=Ri={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，i1<5，5>}。
五、(10分)设函数g：A→B，f：B→C，
(1)若fg是满射，则f是满射。 (2)若fg是单射，则g是单射。
证明
因为g：A→B，f：B→C，由定理5.5知，fg为A到C的函数。
(1)对任意的z∈C，因fg是满射，则存在x∈A使fg(x)=z，即f(g(x))=z。由g：A→B可知g(x)∈B，于是有y=g(x)∈B，使得f(y)=z。因此，f是满射。
(2)对任意的x
1、x2∈A，若x1≠x2，则由fg是单射得fg(x1)≠fg(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。
六、(10分)有幺元且满足消去律的有限半群一定是群。
证明
设是一个有幺元且满足消去律的有限半群，要证是群，只需证明G的任一元素a可逆。
考虑a，a2，…，ak，…。因为G只有有限个元素，所以存在k>l，使得ak=al。令m=k-l，有al*e=al*am，其中e是幺元。由消去率得am=e。
于是，当m=1时，a=e，而e是可逆的;当m>1时，a*am-1=am-1*a=e。从而a是可逆的，其逆元是am-1。总之，a是可逆的。
七、(20分)有向图G如图所示，试求： (1)求G的邻接矩阵A。
5 (2)求出A
2、A3和A4，v1到v4长度为
1、
2、3和4的路有多少?
(3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。 (4)求出可达矩阵P。 (5)求出强分图。
解
(1)求G的邻接矩阵为：
00A00101011
101100(2)由于
00A200111022010
1 A302111020111203220
4 A4120301012313 2322所以v1到v4长度为
1、
2、3和4的路的个数分别为
1、
1、
2、3。 (3)由于
00TAA000002131212TAA
21011102132110 2121再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。
00(4)因为B4AA2A3A40000以求可达矩阵为P00111111。
11111110100110+
101010001110
2010
+
1110
01102120312204+
2120320101231323220
000741
747
，所
747
43400(5)因为PPT0011101111∧1111111100001110=01110111000111，所以{v1}，{v2，v3，v4}构成G的强分图。
111111 6
第五篇：离散数学试题+答案
专注于收集各类历年试卷和答案
一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条(
) A.汉密尔顿回路
B.欧拉回路 C.汉密尔顿通路
D.初级回路
2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是(
) A.10
B.12
C.16
D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是(
) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是(
) A.<{1},·>
B.〈{-1},·〉
C.〈{i},·〉
D.〈{-i},·〉
5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有(
) A.〈Z，+，/〉
B.〈Z，/〉 C.〈Z，-，/〉
D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是(
) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算
B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，〉，Z是整数集，定义为xxy=xy,x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算
7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性
8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉〈,a,c〉}，则关系R的对称闭包S(R)是(
) A.R∪IA
B.R
C.R∪{〈c,a〉}
D.R∩IA 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取(
) A.{〈c,a〉，〈a,c〉｝
B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉}
D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是(
) A. ∈
B.
C.{}
D.{}∈
11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x
) A.( x)( y)( z)(A(x,y))→A(f(x,z),f(y,z)) B.( x)A(f(a,x),a) C.(x)(y)(A(f(x,y),x))
专注于收集各类历年试卷和答案
D.(x)(y)(A(x,y)→A(f(x,a),a)) 12.设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于(
) A.(x)A(x)→B
B.(x)A(x)→B C.A(x)→B
D.(x)A(x)→(x)B 13.谓词公式(x)(P(x,y))→(z)Q(x,z)∧(y)R(x,y)中变元x(
) A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元
14.若P：他聪明;Q：他用功;则“他虽聪明，但不用功”，可符号化为(
) A.P∨Q
B.P∧┐Q
C.P→┐Q
D.P∨┐Q 15.以下命题公式中，为永假式的是(
) A.p→(p∨q∨r)
B.(p→┐p)→┐p C.┐(q→q)∧p
D.┐(q∨┐p)→(p∧┐p)
二、填空题(每空1分，共20分) 16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。 17.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中m24=______,m34=______。 18.设〈s,*〉是群，则那么s中除______外，不可能有别的幂等元;若〈s,*〉有零元，则|s|=______。 19.设A为集合，P(A)为A的幂集，则〈P(A)，是格，若x,y∈P(A),则x,y最大下界是______，〉最小上界是______。
20.设函数f:X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是______函数，如果ranf=Y，则称f是______函数。
21.设R为非空集合A上的等价关系，其等价类记为〔x〕R。x,y∈A，若〈x,y〉∈R，则 〔x〕R与〔y〕R的关系是______，而若〈x,y〉R，则〔x〕R∩〔y〕R=______。
22.使公式(x)( y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x。 23.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x)______,其中量词(x)的辖域是______。 24.若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是相容的，若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是不相容的。
25.判断一个语句是否为命题，首先要看它是否为 ，然后再看它是否具有唯一的
。
三、计算题 (共30分) 26.(4分)设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。
27.(5)设A={a,b},P(A)是A的幂集，是对称差运算，可以验证是群。设n是正整数，求({a}-1{b}{a})n{a}-n{b}n{a}n 28.(6分)设A={1,2,3,4,5},A上偏序关系
R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA;
专注于收集各类历年试卷和答案
(1)作出偏序关系R的哈斯图
(2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。 29.(6分)求┐(P→Q)(P→┐Q)的主合取范式并给出所有使命题为真的赋值。
30.(5分)设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。
31.(4分)求公式┐((x)F(x,y)→(y)G(x,y))∨(x)H(x)的前束范式。
四、证明题 (共20分) 32.(6分)设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k≥2),证明T中至少有2k-2片树叶。
33.(8分)设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。
证明：〈F, 〉是群。
34.(6分)在个体域D={a1,a2,„，an}中证明等价式：
(x)(A(x)→B(x))(x)A(x)→(x)B(x)
五、应用题(共15分) 35.(9分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。
36.(6分)一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?
参考答案
一、单项选择题(本大题共15小题，每小题1分，共15分)
1.B
2.D
3.A
4.A
5.D
6.D
7.D
8.C
9.D
10.B
11.A
12.A
13.C
14.B
15.C
二、填空题 16.0
1 17.1
0 18.单位元
1 19.x∩y
x∪y 20.入射
满射
21.[x]R=[y]R
22.A(x)
B(y) 23.(M(x)→D(x))
M(x)→D(x)
专注于收集各类历年试卷和答案
24.可满足式
永假式(或矛盾式) 25.陈述句
真值
三、计算题
1100101026. M=
1011001122
2 M=21110111
121011M2ij18,
ij6 M2i1
4 i1j144
G中长度为2的路总数为18，长度为2的回路总数为6。
27.当n是偶数时，x∈P(A),xn=
当n是奇数时，x∈P(A),xn=x
于是：当n是偶数，({a｝-1{b｝{a｝)n{a｝-n{b｝n{a｝n
=({a｝-1)n{b｝n{a｝n=
当n是奇数时，
({a｝-1{b｝{a｝)n{a｝-n{b｝n{a｝n
={a｝-1{b｝{a｝({a｝-1)n{b｝n{a｝n
={a｝-1{b｝{a｝{a｝-1{b｝{a｝= 28.(1)偏序关系R的哈斯图为
(2)B的最大元：无，最小元：无;
极大元：2，5，极小元：1，3
下界：4， 下确界4;
上界：无，上确界：无
29.原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))
((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))
(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))
(┐(P∧┐Q)∨(P∧┐Q))
(P∧Q)∨(P∧┐Q)
P∧(Q∨┐Q)
P∨(Q∧┐Q)
(P∨Q)∧(P∨┐Q)
命题为真的赋值是P=1,Q=0和P=1,Q=1
专注于收集各类历年试卷和答案
30.令e1=(v1,v3),
e2=(v4,v6)
e3=(v2,v5),
e4=(v3,v6)
e5=(v2,v3),
e6=(v1,v2)
e7=(v1,v4),
e8=(v4,v3)
e9=(v3,v5),
e10=(v5,v6)
令ai为ei上的权，则
a1
取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，
T的总权和=1+2+3+4+5=15 31.原式┐(x1F(x1,y)→y1G(x,y1))∨x2H(x2)
(换名)
┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2)
x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2)
x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2)
四、证明题
32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的
xy
d(vi)=2(x+y-1)。
i
1 又树叶的度为1，任一分支点的度大于等于2
且度最大的顶点必是分支点，于是
xy
d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i1
从而2(x+y-1)≥x+2y+2k-4
x≥2k-2 33.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空
(1)f,g∈F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。
(2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。
(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元
(4)f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-1f=IA,因此f-1是f的逆元
由此上知〈F，〉是群
34.证明(x)(A(x)→B(x)) x(┐A(x)∨B(x))
专注于收集各类历年试卷和答案
(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨„∨(┐A(an)∨B(an)))
(┐A(a1)∨A(a2)∨„∨┐A(an)∨(B(a1)∨B(a2)∨„∨(B(an))
┐(A(a1)∧A(a2)∧„∧A(an))∨(┐B(a1)∨B(a2)∨„∨(B(an))
┐(x)A(x)∨(x)B(x) (x)A(x)→(x)B(x)
五、应用题
35.令p：他是计算机系本科生
q：他是计算机系研究生
r：他学过DELPHI语言
s:他学过C++语言
t:他会编程序
前提：(p∨q)→(r∧s),(r∨s)→t
结论：p→t
证①p
P(附加前提)
②p∨q
T①I
③(p∨q)→(r∧s)
P(前提引入)
④r∧s
T②③I
⑤r
T④I
⑥r∨s
T⑤I
⑦(r∨s)→t
P(前提引入)
⑧t
T⑤⑥I 36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。
根据：构造无向简单图G=,其中V={v1,v2,„，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。
Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在汉密尔顿回路。
设C=Vi1Vi2„Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。
【离散数学试卷及答案】相关文章：
离散数学试卷及答案二01-16
离散数学试题答案07-09
离散数学期末试题答案01-16
离散数学最全课后答案01-16
屈婉玲版离散数学课后习题答案05-02
离散数学期末试卷05-01
离散数学一单元04-21
广工离散数学04-22
离散数学期末考试07-09
离散数学集合周记07-09