离散数学期末试题答案
第一篇：离散数学期末试题答案
离散数学期末考试试题及答案
离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。下面是小编整理的离散数学期末考试试题及答案，欢迎阅读参考!
一、【单项选择题】
(本大题共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} }
第三篇：离散数学 期末考试试卷答案
离散数学试题(B卷答案1)
一、证明题(10分)
1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R 证明: 左端(P∧Q∧R)∨((Q∨P)∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((P∨Q)∧R)∨((Q∨P)∧R) ((P∨Q)∨(Q∨P))∧R ((P∨Q)∨(P∨Q))∧R T∧R(置换)R 2) x (A(x)B(x)) xA(x)xB(x) 证明 ：x(A(x)B(x))x(A(x)∨B(x)) xA(x)∨xB(x) xA(x)∨xB(x) xA(x)xB(x)
二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取范式和主合取范式(10分)。
证明：(P∨(Q∧R))(P∧Q∧R)(P∨(Q∧R))∨(P∧Q∧R)) (P∧(Q∨R))∨(P∧Q∧R) (P∧Q)∨(P∧R))∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R))∨(P∧Q∧R))∨(P∧Q∧R) m0∨m1∨m2∨m7 M3∨M4∨M5∨M6
三、推理证明题(10分)
1) C∨D， (C∨D) E， E(A∧B)， (A∧B)(R∨S)R∨S 证明：(1) (C∨D)E (2) E(A∧B)
P P
P (3) (C∨D)(A∧B) T(1)(2)，I (4) (A∧B)(R∨S) (5) (C∨D)(R∨S) (6) C∨D
T(3)(4)， I P (7) R∨S T(5)，I 2) x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x)) 证明(1)xP(x) P
(2)P(a) T(1)，ES (3)x(P(x)Q(y)∧R(x)) P (4)P(a)Q(y)∧R(a) T(3)，US (5)Q(y)∧R(a) T(2)(4)，I (6)Q(y) T(5)，I (7)R(a) T(5)，I (8)P(a)∧R(a) T(2)(7)，I (9)x(P(x)∧R(x)) T(8)，EG (10)Q(y)∧x(P(x)∧R(x)) T(6)(9)，I
四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数(10分)。
解：A，B，C分别表示会打排球、网球和篮球的学生集合。则|A|=12，|B|=6，|C|=14，|A∩C|=6，|B∩C|=5，|A∩B∩C|=2。
先求|A∩B|。
∵6=|(A∪C)∩B|=|(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2，∴|(A∩B)|=3。
于是|A∪B∪C|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。
五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) (10分)。
证明：∵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)
六、已知R、S是N上的关系，其定义如下：R={| x，yN∧y=x}，S={| x，yN∧y=x+1}。求R、R*S、S*R、R{1，2}、S[{1，2}](10分)。
解：R={| x，yN∧y=x} R*S={| x，yN∧y=x+1} S*R={| x，yN∧y=(x+1)}，R{1，2}={<1，1>，<2，4>}，S[{1，2}]={1，4}。
七、设R={，，}，求r(R)、s(R)和t(R) (15分)。
解：r(R)={，，，，，}
22-
12-1
2s(R)={，，，，，} R= R={，，} R={，，} R={，，} t(R)={，，，，，，，，，}
八、证明整数集I上的模m同余关系R={|xy(mod m)}是等价关系。其中，xy(mod m)的含义是x-y可以被m整除(15分)。
证明：1)x∈I，因为(x-x)/m=0，所以xx(mod m)，即xRx。
2)x，y∈I，若xRy，则xy(mod m)，即(x-y)/m=k∈I，所以(y - x)/m=-k∈I，所以yx(mod m)，即yRx。
3)x，y，z∈I，若xRy，yRz，则(x-y)/m=u∈I，(y-z)/m=v∈I，于是(x-z)/m=(x-y+y-z)/m=u+v ∈I，因此xRz。
九、若f:A→B和g:B→C是双射，则(gf)=fg(10分)。
-
1-1-14325证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数(gf)：C→A。同理可推fg：C→A是双射。
因为∈fg存在z(∈g∈f)存在z(∈f∈g)∈gf∈(gf)，所以(gf)=fg。
-
1-1
-1-1-1-1
-1
-1-1-1
-1离散数学试题(B卷答案2)
一、证明题(10分)
1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P∧R)T 证明: 左端((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧(P∨R))(摩根律) ((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(分配律) ((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R)) (等幂律) T (代入) 2) xy(P(x)Q(y)) (xP(x)yQ(y)) 证明：xy(P(x)Q(y))xy(P(x)∨Q(y)) x(P(x)∨yQ(y)) xP(x)∨yQ(y) xP(x)∨yQ(y) (xP(x)yQ(y))
二、求命题公式(PQ)(P∨Q) 的主析取范式和主合取范式(10分)
解：(PQ)(P∨Q)(PQ)∨(P∨Q) (P∨Q)∨(P∨Q) (P∧Q)∨(P∨Q) (P∨P∨Q)∧(Q∨P∨Q) (P∨Q) M1 m0∨m2∨m3
三、推理证明题(10分)
1)(P(QS))∧(R∨P)∧QRS 证明：(1)R (2)R∨P (3)P (4)P(QS) (5)QS (6)Q (7)S (8)RS 2) x(A(x)yB(y))，x(B(x)yC(y))xA(x)yC(y)。
证明：(1)x(A(x)yB(y)) P (2)A(a)yB(y) T(1)，ES (3)x(B(x)yC(y)) P (4)x(B(x)C(c)) T(3)，ES (5)B(b)C(c) T(4)，US (6)A(a)B(b) T(2)，US (7)A(a)C(c) T(5)(6)，I (8)xA(x)C(c) T(7)，UG (9)xA(x)yC(y) T(8)，EG
四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好(15分)。
解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生
的集合，则命题可符号化为：PxA(x)，xA(x)QQP。
(1)PxA(x) P (2)PxA(x) T(1)，E (3)xA(x)P T(2)，E (4)xA(x)Q P (5)(xA(x)Q)∧(QxA(x)) T(4)，E (6)QxA(x) T(5)，I (7)QP T(6)(3)，I
五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) (10分)
证明：∵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)
六、A={ x1,x2,x3 }，B={ y1,y2}，R={,,}，求其关系矩阵及关系图(10分)。
七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图(15分)。
解：r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>, <3,3>,<4,4>,<5,5>} s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R=R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}
八、设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠。关系R满足：<，>∈R∈R1且∈R2，证明R是A×B上的等价关系(10分)。
证明 对任意的∈A×B，由R1是A上的等价关系可得∈R1，由R2是B上的等价关系可得∈R2。再由R的定义，有<，>∈R，所以R是自反的。
对任意的、∈A×B，若R，则∈R1且∈R2。由R1对称得∈R1，由R2对称得∈R2。再由R的定义，有<，> 432
5∈R，即R，所以R是对称的。
对任意的、、∈A×B，若R且R，则∈R1且∈R2，∈R1且∈R2。由∈R
1、∈R1及R1的传递性得∈R1，由∈R
2、∈R2及R2的传递性得∈R1。再由R的定义，有<，>∈R，即R，所以R是传递的。
综上可得，R是A×B上的等价关系。
九、设f：AB，g：BC，h：CA，证明：如果hgf=IA，fhg=IB，gfh=IC，则f、g、h均为双射，并求出f、g和h(10分)。
解 因IA恒等函数，由hgf=IA可得f是单射，h是满射;因IB恒等函数，由fhg=IB可得g是单射，f是满射;因IC恒等函数，由gfh=IC可得h是单射，g是满射。从而f、g、h均为双射。
由hgf=IA，得f=hg;由fhg=IB，得g=fh;由gfh=IC，得h=gf。 -
1-1
-1-1-1
-1离散数学试题(B卷答案3)
一、(10分)判断下列公式的类型(永真式、永假式、可满足式)?(写过程) 1)P(P∨Q∨R) 2)((QP)∨P)∧(P∨R) 3)((P∨Q)R)((P∧Q)∨R) 解：1)重言式;2)矛盾式;3)可满足式
二、(10分)求命题公式(P∨(Q∧R))(P∨Q∨R)的主析取范式，并求成真赋值。
解：(P∨(Q∧R))(P∨Q∨R)(P∨(Q∧R))∨P∨Q∨R P∧(Q∨R)∨P∨Q∨R (P∧Q)∨(P∧R)∨(P∨Q)∨R ((P∨Q)∨(P∨Q))∨(P∧R)∨R 1∨((P∧R)∨R)1 m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 该式为重言式，全部赋值都是成真赋值。
三、(10分)证明 ((P∧Q∧A)C)∧(A(P∨Q∨C))(A∧(PQ))C 证明：((P∧Q∧A)C)∧(A(P∨Q∨C))((P∧Q∧A)∨C)∧(A∨(P∨Q∨C)) ((P∨Q∨A)∨C)∧((A∨P∨Q)∨C)
((P∨Q∨A)∧(A∨P∨Q))∨C ((P∨Q∨A)∧(A∨P∨Q))C ((P∨Q∨A)∨(A∨P∨Q))C ((P∧Q∧A)∨(A∧P∧Q))C (A∧((P∧Q)∨(P∧Q)))C (A∧((P∨Q)∧(P∨Q)))C (A∧((QP)∧(PQ)))C (A∧(PQ))C
四、(10分)个体域为{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+2=4)) (0∨0)∧(0∨1)0∧10
五、(10分)对于任意集合A，B，试证明：P(A)∩P(B)=P(A∩B) 解：xP(A)∩P(B)，xP(A)且xP(B)，有xA且xB，从而xA∩B，xP(A∩B)，由于上述过程可逆，故P(A)∩P(B)=P(A∩B)
六、(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分)设函数f：R×RR×R，R为实数集，f定义为：f()=。1)证明f是双射。
解：1)，∈R×R，若f()=f()，即=，则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2从而f是单射。
2)∈R×R，由f()=，通过计算可得x=(p+q)/2;y=(p-q)/2;从而的原象存在，f是满射。
八、(10分)是个群，u∈G，定义G中的运算“”为ab=a*u*b，对任意a，b∈G，求证：也是个群。
证明：1)a，b∈G，ab=a*u*b∈G，运算是封闭的。
2)a，b，c∈G，(ab)c=(a*u*b)*u*c=a*u*(b*u*c)=a(bc)，运算是可结合的。
3)a∈G，设E为的单位元，则aE=a*u*E=a，得E=u，存在单位元u。 4)a∈G，ax=a*u*x=E，x=u*a*u，则xa=u*a*u*u*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。
解：1)D的邻接距阵A和可达距阵P如下：
A= 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1
1 1 1 0 1 -
1-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
P= 1 1 1 1
十、(10分)求叶的权分别为
2、
4、
6、
8、
10、
12、14的最优二叉树及其权。
解：最优二叉树为
权=(2+4)×4+6×3+12×2+(8+10)×3+14×2=148
离散数学试题(B卷答案4)
一、证明题(10分)
1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P∧R)T
证明: 左端((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧(P∨R))(摩根律) ((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(分配律) ((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R)) (等幂律) T (代入) 2)x(P(x)Q(x))∧xP(x)x(P(x)∧Q(x)) 证明：x(P(x)Q(x))∧xP(x)x((P(x)Q(x)∧P(x))x((P(x)∨Q(x)∧P(x))x(P(x)∧Q(x))xP(x)∧xQ(x)x(P(x)∧Q(x))
二、求命题公式(PQ)(P∨Q) 的主析取范式和主合取范式(10分)
解：(PQ)(P∨Q)(PQ)∨(P∨Q)(P∨Q)∨(P∨Q)(P∧Q)∨(P∨Q) (P∨P∨Q)∧(Q∨P∨Q)(P∨Q)M1m0∨m2∨m3
三、推理证明题(10分)
1)(P(QS))∧(R∨P)∧QRS 证明：(1)R 附加前提 (2)R∨P P (3)P T(1)(2),I (4)P(QS) P (5)QS T(3)(4),I (6)Q P (7)S T(5)(6),I (8)RS CP 2) x(P(x)∨Q(x))，xP(x)x Q(x) 证明：(1)xP(x) P (2)P(c) T(1),US (3)x(P(x)∨Q(x)) P (4)P(c)∨Q(c) T(3),US (5)Q(c) T(2)(4),I (6)x Q(x) T(5),EG
四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形(可能是退化的)面积不超过1/8(10分)。
证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形(可能是退化的)面积不超过小正方形的一半，即1/8。
五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) (10分)
证明：∵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)
六、={A1，A2，„，An}是集合A的一个划分，定义R={|a、b∈Ai，I=1，2，„，n}，则R是A上的等价关系(15分)。
证明：a∈A必有i使得a∈Ai，由定义知aRa，故R自反。 a,b∈A，若aRb ，则a,b∈Ai，即b,a∈Ai，所以bRa，故R对称。
a,b,c∈A，若aRb 且bRc，则a,b∈Ai及b,c∈Aj。因为i≠j时Ai∩Aj=，故i=j，即a,b,c∈Ai，所以aRc，故R传递。
总之R是A上的等价关系。
七、若f:A→B是双射，则f:B→A是双射(15分)。
证明:对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使∈f，∈f。所以,f是满射。
对任意的x∈A，若存在y1,y2∈B，使得∈f且∈f,则有∈f且∈f。因为f是函数，则y1=y2。所以，f是单射。
因此f是双射。
八、设是群，和是的子群，证明：若A∪B=G，则A=G或B=G(10分)。
证明 假设A≠G且B≠G，则存在aA，aB，且存在bB，bA(否则对任意的aA，aB，从而AB，即A∪B=B，得B=G，矛盾。)
对于元素a*bG，若a*bA，因A是子群，aA，从而a * (a*b)=b A，所以矛盾，故a*bA。同理可证a*bB，综合有a*bA∪B=G。 综上所述，假设不成立，得证A=G或B=G。
九、若无向图G是不连通的，证明G的补图G是连通的(10分)。
证明 设无向图G是不连通的，其k个连通分支为G
1、G
2、„、Gk。任取结点u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]
-
1-1-1
-1
-1
-1-1-1-1是图G的边;若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi(1≤i≤k)中，在不同于Gi的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，，
因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。
离散数学试题(B卷答案5)
一、(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={，，，，，，，
4232-1d>，}
六、(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 a=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|，与简单无向平面图的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。 九.G=,A={a,b,c},*的运算表为：(写过程，7分) -
1-1
-1-1-1-1-1
-1-1 (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 离散数学试题(B卷答案6)
一、(20分)用公式法判断下列公式的类型： (1)(P∨Q)(PQ) (2)(PQ)(P∧(Q∨R)) 解：(1)因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q)
(P∧Q)∨(P∧Q)∨(P∧Q) m1∨m2∨m3 M0
所以，公式(P∨Q)(PQ)为可满足式。
(2)因为(PQ)(P∧(Q∨R))(( P∨Q))∨(P∧Q∧R))
(P∨Q)∨(P∧Q∧R))
(P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R) (P∨Q)∧(P∨Q∨R)
(P∨Q∨(R∧R))∧(P∨Q∨R) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M0∧M1
m2∨m3∨m4∨m5∨m6∨m7
所以，公式(PQ)(P∧(Q∨R))为可满足式。
二、(15分)在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋
又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。
解：论域：所有人的集合。Q(x)：x是勤奋的;H(x)：x是身体健康的;S(x)：x是科学家;C(x)：x是事业获得成功的人;F(x)：x是事业半途而废的人;则推理化形式为：
x(S(x)H(x))Q(x))，x(Q(x)∧H(x)C(x))，x(S(x)∧x(C(x)∨F(x)) 下面给出证明：
(1)x(S(x)∧H(x))
P (2)S(a)∧H(a)
T(1)，ES (3)x(S(x)Q(x))
P (4)S(a)Q(a)
T(1)，US (5)S(a)
T(2)，I (6)Q(a)
T(4)(5)，I (7)H(a)
T(2)，I (8)Q(a)∧H(a)
T(6)(7)，I (9)x(Q(x)∧H(x)C(x))
P (10)Q(a)∧H(a)C(a)
T(9)，Us (11)C(a)
T(8)(10)，I (12)xC(x)
T(11)，EG (13)x(C(x)∨F(x))
T(12)，I
三、(10分)设A={，1，{1}}，B={0，{0}}，求P(A)、P(B)-{0}、P(B)B。 解
P(A)={，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)-{0}={，{0}，{{0}}，{0，{0}}-{0}={，{0}，{{0}}，{0，{0}} P(B)B={，{0}，{{0}}，{0，{0}}{0，{0}}={，0，{{0}}，{0，{0}}
四、(15分)设R和S是集合A上的任意关系，判断下列命题是否成立? (1)若R和S是自反的，则R*S也是自反的。 (2)若R和S是反自反的，则R*S也是反自反的。 (3)若R和S是对称的，则R*S也是对称的。
(4)若R和S是传递的，则R*S也是传递的。 (5)若R和S是自反的，则R∩S是自反的。 (6)若R和S是传递的，则R∪S是传递的。
解
(1)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R*S，故R*S也是自反的。
(2)不成立。例如，令A={1，2}，R={<1，2>}，S={<2，1>}，则R和S是反自反的，但R*S={<1，1>}不是反自反的。
(3)不成立。例如，令A={1，2，3}，R={<1，2>，<2，1>，<3，3>}，S={<2，3>，<3，2>}，则R和S是对称的，但R*S={<1，3>，<3，2>}不是对称的。
(4)不成立。例如，令A={1，2，3}，R={<1，2>，<2，3>，<1，3>}，S={<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S={<1，3>，<1，1>，<2，1>}不是传递的。
(5)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R∩S，所以R∩S是自反的。
五、(15分)令X={x1，x2，„，xm}，Y={y1，y2，„，yn}。问 (1)有多少个不同的由X到Y的函数?
(2)当n、m满足什么条件时，存在单射，且有多少个不同的单射? (3)当n、m满足什么条件时，存在双射，且有多少个不同的双射?
解
(1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共nm个。
(2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到
mY的不同的单射，故不同的单射有Cnm!=n(n-1)(n―m―1)个。
(3)显然当|m|=|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，故不同的双射有m!个。
六、(5分)集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个?
解
X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2mn，所以X到Y的二元关系总共有2mn个。
七、(10分)若是群，则对于任意的a、b∈G，必有惟一的x∈G使得a*x=
b。
证明 设e是群的幺元。令x=a1*b，则a*x=a*(a1*b)=(a*a1)*b=e*b=b。
-
-
-所以，x=a1*b是a*x=b的解。 -若x∈G也是a*x=b的解，则x=e*x=(a1*a)*x=a1*(a*x)=a1*b=x。所以，x
-
-
-=a1*b是a*x=b的惟一解。 -
八、(10分)给定连通简单平面图G=，且|V|=6，|E|=12。证明：对任意f∈F，d(f)=3。
证明
由偶拉公式得|V|-|E|+|F|=2，所以|F|=2-|V|+|E|=8，于是d(f)=2|E|=
fF24。若存在f∈F，使得d(f)>3，则3|F|<2|E|=24，于是|F|<8，与|F|=8矛盾。故对任意f∈F，d(f)=3。
离散数学试题(B卷答案7)
一、(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)偏序集是否有最大元? (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，i11>，<5，4>，<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。
(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)由于
002A001110220130
1 A0211102011120322044A
031201012313 2322所以v1到v4长度为
1、
2、3和4的路的个数分别为
1、
1、
2、3。 (3)由于
00ATA000002131212TAA
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。
(4)00B4AA2A3A40000所以求可达矩阵为P0000(5)因为PPT0010100110+10101000111111。
11111111101111∧1111111100001110=01110111000111，所以{v1}，{v2，v3，v4}
111111因
1110
2010
+
1110
0110
2120312204+
2120320101231323220
000
为
741
747
，
747
434构成G的强分图。
离散数学试题(B卷答案8)
一、(10分)证明(P∨Q)∧(PR)∧(QS)S∨R
证明
因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。 (1)R
附加前提 (2)PR
P (3)P
T(1)(2)，I (4)P∨Q
P (5)Q
T(3)(4)，I (6)QS
P (7)S
T(5)(6)，I (8)RS
CP (9)S∨R
T(8)，E
二、(15分)根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。
设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。
(1)x(P(x)Q(x))
P (2)x(P(x)∨Q(x))
T(1)，E (3)x(P(x)∧Q(x))
T(2)，E (4)P(a)∧Q(a)
T(3)，ES (5)P(a)
T(4)，I (6)Q(a)
T(4)，I (7)x(P(x)(A(x)∨B(x))
P (8)P(a)(A(a)∨B(a))
T(7)，US (9)A(a)∨B(a)
T(8)(5)，I (10)x(A(x)Q(x))
P
(11)A(a)Q(a)
T(10)，US (12)A(a)
T(11)(6)，I
(13)B(a)
T(12)(9)，I (14)P(a)∧B(a)
T(5)(13)，I (15)x(P(x)∧B(x))
T(14)，EG
三、(10分)某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。
解
设A、B、C分别表示会打排球、网球和篮球的学生集合。则：
|A|=12，|B|=6，|C|=14，|A∩C|=6，|B∩C|=5，|A∩B∩C|=2，|(A∪C)∩B|=6。 因为|(A∪C)∩B|=(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2=6，所以|(A∩B)|=3。于是|A∪B∪C|=12+6+14-6-5-3+2=20，|ABC|=25-20=5。故，不会打这三种球的共5人。
四、(10分)设A
1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称
i13为由A
1、A2和A3产生的小项。试证由A
1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。
证明
小项共8个，设有r个非空小项s
1、s
2、…、sr(r≤8)。
对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，即有a∈si，于是Usi。又显然有siU，所以U=si。
i1i1i1i1i13rrrr任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq=。
综上可知，{s1，s2，…，sr}是U的一个划分。
五、(15分)设R是A上的二元关系，则：R是传递的R*RR。
证明
(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。
反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。
六、(15分)若G为连通平面图，则n-m+r=2，其中，n、m、r分别为G的结点数、边数和面数。
证明
对G的边数m作归纳法。
当m=0时，由于G是连通图，所以G为平凡图，此时n=1，r=1，结论自然成立。 假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。
设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：
若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1+n2=n=n，m1+m2=m=m-1，r1+r2=r+1=r+1。由归纳假设有n1-m1+r1=2，n2-m2+r2=2，从而(n1+n2)-(m1+m2)+(r1+r2)=4，n-(m-1)+(r+1)=4，即n-m+r=2。
若e不为割边，则n=n，m=m-1，r=r-1，由归纳假设有n-m+r=2，从而n-(m-1)+r-1=2，即n-m+r=2。
由数学归纳法知，结论成立。
七、(10分)设函数g：A→B，f：B→C，则： (1)fg是A到C的函数;
(2)对任意的x∈A，有fg(x)=f(g(x))。
证明
(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fg。所以Dfg=A。
对任意的x∈A，若存在y
1、y2∈C，使得、∈fg=g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1=t2。又因f：B→C是函数，则y1=y2。所以A中的每个元素对应C中惟一的元素。
综上可知，fg是A到C的函数。
(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f=fg。又因fg是A到C的函数，则可写为fg(x)=f(g(x))。
八、(15分)设是的子群，定义R={|a、b∈G且a1*b∈H}，
-则R是G中的一个等价关系，且[a]R=aH。
证明
对于任意a∈G，必有a1∈G使得a1*a=e∈H，所以∈R。
-
-
若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1=b1*a∈H。所以
-
-
-a>∈R。
若∈R，∈R，则a1*b∈H，b1*c∈H。因为H是G的子群，所以(a
-
-
-1*b)*(b1*c)=a1*c∈H，故∈R。 --综上可得，R是G中的一个等价关系。
对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b=h，b=a*h，
-
-于是b∈aH，[a]RaH。对任意的b∈aH，存在h∈H使得b=a*h，a1*b=h∈H，
-b>∈R，故aH[a]R。所以，[a]R=aH。
离散数学试题(B卷答案9)
一、(10分)证明(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))C。 证明：(P∧Q∧AC)∧(AP∨Q∨C)(P∨Q∨A∨C)∧(A∨P∨Q∨C)
(P∨Q∨A∨C)∧(A∨P∨Q∨C) ((P∨Q∨A)∧(A∨P∨Q))∨C ((P∧Q∧A)∨(A∧P∧Q))∨C ( A∧((P∧Q)∨(P∧Q)))∨C ( A∧(PQ))∨C (A∧(PQ))C。
二、(10分)举例说明下面推理不正确：xy(P(x)Q(y))，yz(R(y)Q(z))xz(P(x)R(z))。
解：设论域为{1，2}，令P(1)=P(2)=T;Q(1)=Q(2)=T;R(1)=R(2)=F。则： xy(P(x)Q(y))x((P(x)Q(1))∨(P(x)Q(2)))
((P(1)Q(1))∨(P(1)Q(2)))∧((P(2)Q(1))∨(P(2)Q(2))) ((TT)∨(TT))∧((TT)∨(TT)) T yz(R(y)Q(z))y((R(y)Q(1))∨(R(y)Q(2)))
((R(1)Q(1))∨(R(1)Q(2)))∧((R(2)Q(1))∨(R(2)Q(2)))
((FT)∨(FT))∧((FT)∨(FT))
T
但
xz(P(x)R(z))x((P(x)R(1))∧(P(x)R(2))) ((P(1)R(1))∧(P(1)R(2)))∨((P(2)R(1))∧(P(2)R(2))) ((TF)∧(TF))∨((TF)∧(TF)) F 所以，xy(P(x)Q(y))，yz(R(y)Q(z))xz(P(x)R(z))不正确。
三、(15分)在谓词逻辑中构造下面推理的证明：所有牛都有角，有些动物是牛，所以，有些动物有角。
解：令P(x)：x是牛;Q(x)：x有角;R(x)：x是动物;则推理化形式为：
x(P(x)Q(x))，x(P(x)∧R(x))x(Q(x)∧R(x)) 下面给出证明：
(1)x(P(x)∧R(x))
P (2)P(a)∧R(a)
T(1)，ES (3)x(P(x)Q(x))
P (4)P(a)Q(a)
T(3)，US (5)P(a)
T(2)，I (6)Q(a)
T(4)(5)，I (7)R(a)
T(2)，I (8)Q(a)∧R(a)
T(6)(7)，I (9)x(Q(x)∧R(x))
T(8)，EG
四、(10分)证明(A∩B)×(C∩D)=(A×C)∩(B×D)。
证明：因为∈(A∩B)×(C∩D)x∈(A∩B)∧y∈(C∩D)x∈A∧x∈B∧y∈C∧y∈D(x∈A∧y∈C)∧(x∈B∧y∈D)∈A×C∧∈B×D∈(A×C)∩(B×D)，所以(A∩B)×(C∩D)=(A×C)∩(B×D)。
五、(15分)设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，i11>，<5，4>，<5，5>}。
六、(10分)若函数f：A→B是双射，则对任意x∈A，有f1(f(x))=x。
-证明
对任意的x∈A，因为f：A→B是函数，则∈f，于是
-由f-1是B到A的函数，于是可写为f1(f(x))=x。
-
七、(10分)若G为有限群，则|G|=|H|·[G:H]。
证明
设[G:H]=k，a
1、a
2、…、ak分别为H的k个左陪集的代表元，由定理8.38得
G[ai]RaiH
i1i1kk又因为对H中任意不同的元素x、y∈H及a∈G，必有a*x≠a*y，所以|a1H|=…=|akH|=|H|。因此
|G||aiH|i1k|aH|k|H|=|H|·[G:H]。
ii1k
八、(20分)(1)画出3阶2条边的所有非同构有向简单图。
解：由握手定理可知，所画的有向简单图各结点度数之和为4，且最大出度和最大入度均小于或等于2。度数列与入度列、出度列为：
1、
2、1：入度列为0、
1、1或0、
2、0或
1、0、1;出度列为
1、
1、0或
1、0、1或0、
2、0
2、
2、0：入度列为
1、
1、0;出度列为
1、
1、0 四个所求有向简单图如图所示。
(2)设G是n(n≥4)阶极大平面图，则G的最小度≥3。
证明
设v是极大平面图G的任一结点，则v在平面图G-{v}的某个面f内。由于G-{v}是一个平面简单图且其结点数大于等于3，所以d(f)≥3。由G的极大平面性，v与f上的结点之间都有边，因此d(v)≥3。由v的任意性可得，G的最小度≥3。
离散数学试题(B卷答案10)
一、(10分)使用将命题公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。
证明：因为(PQ)(P∧Q)(P∨Q)∨(P∧Q)
(P∧Q)∨(P∧Q) (QP)∧(P∨Q)(Q∨P)∧(P∨Q) (P∧Q)∨(Q∧Q)∨(P∧P) ∨(P∧Q) (P∧Q)∨P
(P∧Q)∨(P∧(Q∨Q)) (P∧Q)∨(P∧Q)∨(P∧Q) (P∧Q)∨(P∧Q) 所以，(PQ)(P∧Q)(QP)∧(P∨Q)。
二、(10分)证明下述推理： 如果A努力工作，那么B或C感到愉快;如果B愉快，那么A不努力工作;如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。
解 设A：A努力工作;B、C、D分别表示B、C、D愉快;则推理化形式为： AB∨C，BA，DCAD
(1)A 附加前提 (2)AB∨C P (3)B∨C T(1)(2)，I (4)BA P (5)AB
T(4)，E (6)B T(1)(5)，I (7)C T(3)(6)，I
(8)DC P (9)D T(7)(8)，I (10)AD CP
三、(10分)证明xy(P(x)Q(y))(xP(x)yQ(y))。 xy(P(x)Q(y))xy(P(x)∨Q(y)) x(P(x)∨yQ(y)) xP(x)∨yQ(y) xP(x)∨yQ(y) (xP(x)yQ(y))
四、(10分)设A={，1，{1}}，B={0，{0}}，求P(A)、P(B)-{0}、P(B)B。 解 P(A)={，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)-{0}={，{0}，{{0}}，{0，{0}}-{0}={，{0}，{{0}}，{0，{0}} P(B)B={，{0}，{{0}}，{0，{0}}{0，{0}}={，0，{{0}}，{0，{0}}
五、(15分)设X={1，2，3，4}，R是X上的二元关系，R={<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>} (1)画出R的关系图。 (2)写出R的关系矩阵。
(3)说明R是否是自反、反自反、对称、传递的。 解 (1)R的关系图如图所示： (2) R的关系矩阵为：
10M(R)111011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的;由于对角线上存在非0元，R不是反自反的;由于矩阵不对称，R不是对称的;
经过计算可得
10M(R2)111011101100M(R)，所以R是传递的。 00
六、(15分)设函数f：R×RR×R，f定义为：f()=。 (1)证明f是单射。 (2)证明f是满射。 (3)求逆函数f。
(4)求复合函数ff和ff。
证明 (1)对任意的x，y，x1，y1∈R，若f()=f()，则=，x+y=x1+y1，x-y=x1-y1，从而x=x1，y=y1，故f是单射。
(2)对任意的∈R×R，令x=-1-
1uwuwuwuw
，y=，则f()=<+，2222uwuw->=，所以f是满射。 22(3)f()=<-1-1uwuw，>。 22-1(4)ff()=f(f())=f
-1
()=<
xyxy，
2xy(xy)>= 2ff()=f(f())=f()==<2x，2y>。
七、(15分)给定群，若对G中任意元a和b，有a*b=(a*b)，a*b=(a*b)，a*b=(a*b)，试证是Abel群。
证明 对G中任意元a和b。
因为a*b=(a*b)，所以a*a*b*b=a*(a*b)*b，即得a*b=(b*a)。同33
333
3
2
2255
53
3
3
4
44
13
111理，由a*b=(a*b)可得，a*b=(b*a)。由a*b=(a*b)可得，a*b=(b*a)。
于是(a*b)*(b*a)=(b*a)=a*b，即b*a=a*b。同理可得，(a*b)*(b*a)=(b*a)=a*b，即b*a=a*b。
3333334
4
4
4
4
2
2
344433555444
由于(a*b)*b=a*b=b*a=b*(b*a)=b*(a*b)=(b*a)*b，故a*b=b*a。
八、(15分)(1)证明在n个结点的连通图G中，至少有n-1条边。
证明 不妨设G是无向连通图(若G为有向图，可略去边的方向讨论对应的无向图)。 设G中结点为v
1、v
2、„、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2(否则可重新编号)，连接v1和v2，得边e1，还是由连通性，在v
3、v
4、„、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v
1、v
2、„、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n-1条边。
(2)试给出|V|=n，|E|=(n-1)(n-2)的简单无向图G=是不连通的例子。
解 下图满足条件但不连通。
12344333
第四篇：离散数学试题+答案
专注于收集各类历年试卷和答案
一、单项选择题(本大题共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中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。
第五篇：离散数学试题与答案
《离散数学》试题及答案
一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。
1. 命题公式(PQ)Q为 ()
(A) 矛盾式 (B) 可满足式(C) 重言式 (D) 合取范式
2.设P表示“天下大雨”， Q表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为()。
(A). PQ; (B).PQ;(C).PQ; (D).PQ.
3.设集合A={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是()
(A) 1A(B) {1,2, 3}A
(C) {{4,5}}A(D) A
4. 设A={1,2},B={a,b,c},C={c,d}, 则A×(BC)= ()
(A) {<1,c>,<2,c>}(B) {,<2,c>}(C) {,}(D) {<1,c>,}
5. 设G如右图：那么G不是().(A)哈密顿图;(B)完全图;
(C)欧拉图;(D) 平面图.二、填空题：本大题共5小题，每小题4分，共20
6. 设集合A={,{a}}，则A的幂集P(A7. 设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R={x,yy2x,xA,yB},
那么R1=-
8. 在“同学，老乡，亲戚，朋友”四个关系中_______是等价关系.9. 写出一个不含“”的逻辑联结词的完备集.
10.设X={a,b,c}，R是X上的二元关系，其关系矩阵为
101，那么R的关系图为 MR=100100
三、证明题(共30分)
11. (10分)已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)
12. (10分)构造证明：(P(QS))∧(R∨P)∧QRS
(0,1)13.(10分)证明与[0,1)，[0,1)与[0,1]等势。
四、解答题(共35分)
14.(7分)构造三阶幻方(以1为首项的9个连续自然数正好布满一个33方阵，且方阵中的每一行, 每一列及主、副对角线上的各数之和都相等.)
15.(8分) 求命题公式(PQ)(PQ)的真值表.16.(10分)设R1是A1={1,2}到A2=(a,b,c)的二元关系，R2是A2到A3={,}的二元关系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}
毕节学院《离散数学 》课程试卷第 1 页 共 4 页
求R1R2的集合表达式.
17.(10分)某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法?如何派?
三个条件：(1)若A去，则C和D中要去1个人;(2)B和C不能都去;
(3)若C去，则D留下。
一、单项选择题(每小题3分，共15分)
1.B2.C3. C4.A5.B
二、填空题(每小题4分，共20分)
6. {,{},{{a}},{,{a}}}
7.{<6,3>,<8,4> }8. 老乡
9.{,}或{,} 或 {}或 {}
10. 见第10题答案图.
11.证明：∵x A∩(B∪C) x A∧x(B∪C) ··························································· 2分
x A∧(xB∨xC) ······························································································· 3分
( x A∧xB)∨(x A∧xC) ··········································································· 5分
x(A∩B)∨x A∩C ······························································································ 7分
x(A∩B)∪(A∩C) ····························································································· 9分
∴A∩(B∪C)=(A∩B)∪(A∩C) ·················································································· 10分
12.证明：(1)R附加前提
(2)R∨PP ········································································································ 2分
(3)PT(1)(2)，I ······················································································ 3分
(4)P(QS)P ······································································································· 4分
(5)QST(3)(4)，I ······················································································ 5分
(6)QP ······································································································· 6分
(7)ST(5)(6)，I ······················································································ 8分
(8)RSCP ··································································································· 10分
13. 证明：a) 设A{,,,
c第10题答案图 11
231,}，作f:(0,1)[0,1)如下： ································· 2分 n
1f()0211,xAn2 ························································································ 5分 f()nn1f(x)x,x(0,1)A
b) 设A,,,11
231,}，作f:[0,1)[0,1]如下： ····················································· 7分 n
毕节学院《离散数学 》课程试卷第 2 页 共 4 页
f(0)0111························································································ 10分 ,n1,A ·f()n1nn
f(x)x,x[0,1)A
14.
8
9 5 1 2 7 6
填对每个格得1分。
15.
表中最后一列的数中，每对1个数得2分.
11016.MR1,(2分)001
MR201(4分) 0100
010101(6分) 0000110 MR1R2001
R1R2{1,}(10分)
17. 解设A：A去工作;B：B去工作;C：C去工作;D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。 ······························································································ 2分 因此(ACD)∧(B∧C)∧(CD)
(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)
(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))
(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)
∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)
∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)
F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F
(A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)
(A∧C)∨(B∧C∧ D)∨(C∧D)
T ··································································································································· 8分
毕节学院《离散数学 》课程试卷第 3 页 共 4 页
故有三种派法：B∧D，A∧C，A∧D。 ······································································· 10分
毕节学院《离散数学 》课程试卷第 4 页 共 4 页