范文网 论文资料 离散数学期末试题答案(大全)

离散数学期末试题答案(大全)

离散数学期末试题答案第一篇:离散数学期末试题答案离散数学期末考试试题及答案离散数学是研究离散量的结构及其相互关系的数学学科,是现代数学的一个重要分支。下面是小编整理的离散数学期末考试试题及答案,欢迎阅读参考!一、【单项选择题】(本大题共15。

离散数学期末试题答案

第一篇:离散数学期末试题答案

离散数学期末考试试题及答案

离散数学是研究离散量的结构及其相互关系的数学学科,是现代数学的一个重要分支。下面是小编整理的离散数学期末考试试题及答案,欢迎阅读参考!

一、【单项选择题】

(本大题共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 | nN }

(4) Ad= {3, 5, 7, 9, ```} = { 2n+1 | nN }

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)若AB,且BC,则AC√ (2)若AB,且BC,则AC× (3)若AB,且BC,则AC× (4)若AB,且BC,则AC ×

5.对任意集合A,B,C,证明

(1)A(BC)(AB)(AC) 左差A(BC)差A(BC)D.MA(BC)

分配(AB)(AC)右(2)A(BC)(AB)(AC)1)左差A(BC)(1)的结论(AB)(AC) 差(AB)(AC)右

2)左差A(BC)D.MA(BC)分配(AB)(AC)差(AB)(AC)右(3)A(BC)(AB)(AC)左差A(BC)D.MA(BC) 幂等(AA)(BC)

结合,交换(AB)(AC)右(4)(AB)BAB 左差(AB)B对称差((AB)B)((AB)B)

分配,结合((AB)(BB))(A(B)B))

2 互补((AB)U)(A)

零一

(AB)(AB)右(5)(AB)CA(BC) 左差(AB)C结合A(BC)

D.MA(BC)差A(BC)(6)(AB)C(AC)B左差(AB)C结合A(BC)交换A(CB)结合(AC)B

差(AC)B右(7)(AB)C(AC)(BC)右(5)A(C(BC))差A(C(BC)) 分配A((CB)(CC))互补A((CB)U)

零一A(CB)交换A(BC)(5)(AB)C左

6.问在什么条件下,集合A,B,C满足下列等式

(1)A(BC)(AB)C左(AB)(AC)右若要右左,须CA(BC),

CA时等式成立

(2)ABA左右是显然的,AABAB,AB,

AB时等式成立

(3)ABBABB,BB,B,代入原式得A,

AB时等式成立

(4)ABBAABBA,只能AB,AB, BA,BA,AB时等式成立

(5)ABAB,若B,bB,

当bA,bABA矛盾;当bA,bABA矛盾

(6)ABAB右左是显然的,ABAB,AAB,ABBAB,BAABAB时等式成立

(7)(AB)(AC)A左(AB)(AC)A(BC)A(BC)A(BC)A

ABC时等式成立

(8)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)

A(BC),AB,AC时等式成立

(9)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)

A(BC)时等式成立

(10)(AB)(AC)((AB)(AC))((AB)(AC))(AB)(AC)(AB)(AC)

由(6)知,(AB)(AC),ABAC,ABAC时等式成立

(11)A(BA)BA(BA)(AB)(AA)(AB)U(AB)B

AB时等式成立

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) ABAC

否,例:A={1,2,3},B={4},C={3,4}, ABAC{1,2,3,4},而BC。

(2)ABAC

否,例:A={1,2,3},B={2,3},C={2,3,4} ABAC{2,3},而BC。

(3)ABAC

对,若BC,不妨,aB,aC,若aA,aAB,aAB,aAB,aAC,aAC,aAC; 若aA,aAB,aAB,aAB,aAC,aAC,aAC矛盾(4)ABAC且ABAC

bB,若bA,bABAC,bC,若bA,bABAC,bC,

BC,同理,CB,BC

9. (1) (AB)(BC)AB

证:a左,a(BC),aB,aB;a(AB),而aB,aA,aAB

(2)若A(BC)且B(AC),则B。

若B,aB(AC)(AC),aA(BC),aC,aB即aB,矛盾

10.化简

((ABC)(AB))((A(BC))A)(AB)A(AB)A

(AA)(BA)(BA)BA11. 设A={2,3,4},B={1,2},C={4,5,6},求 (1)AB{1, 3, 4}  (2)ABC{1,3,5,6} (3)(AB)(BC){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)) xA(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∧(xB∧xC)

(x A∧xB)∧(x A∧xC)  x(A-B)∧x(A-C)  x(A-B)∩(A-C)

∴A-(B∪C)=(A-B)∩(A-C)

六、已知R、S是N上的关系,其定义如下:R={| x,yN∧y=x},S={| x,yN∧y=x+1}。求R、R*S、S*R、R{1,2}、S[{1,2}](10分)。

解:R={| x,yN∧y=x} R*S={| x,yN∧y=x+1} S*R={| x,yN∧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={|xy(mod m)}是等价关系。其中,xy(mod m)的含义是x-y可以被m整除(15分)。

证明:1)x∈I,因为(x-x)/m=0,所以xx(mod m),即xRx。

2)x,y∈I,若xRy,则xy(mod m),即(x-y)/m=k∈I,所以(y - x)/m=-k∈I,所以yx(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) xy(P(x)Q(y)) (xP(x)yQ(y)) 证明:xy(P(x)Q(y))xy(P(x)∨Q(y)) x(P(x)∨yQ(y)) xP(x)∨yQ(y) xP(x)∨yQ(y) (xP(x)yQ(y))

二、求命题公式(PQ)(P∨Q) 的主析取范式和主合取范式(10分)

解:(PQ)(P∨Q)(PQ)∨(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(QS))∧(R∨P)∧QRS 证明:(1)R (2)R∨P (3)P (4)P(QS) (5)QS (6)Q (7)S (8)RS 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提前进入考场,个体域:考生

的集合,则命题可符号化为:PxA(x),xA(x)QQP。

(1)PxA(x) P (2)PxA(x) T(1),E (3)xA(x)P T(2),E (4)xA(x)Q P (5)(xA(x)Q)∧(QxA(x)) T(4),E (6)QxA(x) T(5),I (7)QP 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∧(xB∨xC)( x A∧xB)∨(x A∧xC) 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:AB,g:BC,h:CA,证明:如果hgf=IA,fhg=IB,gfh=IC,则f、g、h均为双射,并求出f、g和h(10分)。

解 因IA恒等函数,由hgf=IA可得f是单射,h是满射;因IB恒等函数,由fhg=IB可得g是单射,f是满射;因IC恒等函数,由gfh=IC可得h是单射,g是满射。从而f、g、h均为双射。

由hgf=IA,得f=hg;由fhg=IB,得g=fh;由gfh=IC,得h=gf。 -

1-1

-1-1-1

-1离散数学试题(B卷答案3)

一、(10分)判断下列公式的类型(永真式、永假式、可满足式)?(写过程) 1)P(P∨Q∨R) 2)((QP)∨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∧(PQ))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∧((QP)∧(PQ)))C (A∧(PQ))C

四、(10分)个体域为{1,2},求xy(x+y=4)的真值。

解:xy(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∧10

五、(10分)对于任意集合A,B,试证明:P(A)∩P(B)=P(A∩B) 解:xP(A)∩P(B),xP(A)且xP(B),有xA且xB,从而xA∩B,xP(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×RR×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中的运算“”为ab=a*u*b,对任意a,b∈G,求证:也是个群。

证明:1)a,b∈G,ab=a*u*b∈G,运算是封闭的。

2)a,b,c∈G,(ab)c=(a*u*b)*u*c=a*u*(b*u*c)=a(bc),运算是可结合的。

3)a∈G,设E为的单位元,则aE=a*u*E=a,得E=u,存在单位元u。 4)a∈G,ax=a*u*x=E,x=u*a*u,则xa=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))

二、求命题公式(PQ)(P∨Q) 的主析取范式和主合取范式(10分)

解:(PQ)(P∨Q)(PQ)∨(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(QS))∧(R∨P)∧QRS 证明:(1)R 附加前提 (2)R∨P P (3)P T(1)(2),I (4)P(QS) P (5)QS T(3)(4),I (6)Q P (7)S T(5)(6),I (8)RS CP 2) x(P(x)∨Q(x)),xP(x)x Q(x) 证明:(1)xP(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∧(xB∨xC)( x A∧xB)∨(x A∧xC) 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,则存在aA,aB,且存在bB,bA(否则对任意的aA,aB,从而AB,即A∪B=B,得B=G,矛盾。)

对于元素a*bG,若a*bA,因A是子群,aA,从而a * (a*b)=b A,所以矛盾,故a*bA。同理可证a*bB,综合有a*bA∪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)(PR)的主合取范式。

解:(P∧Q)(PR)((P∧Q)(PR))∧((PR)(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∧(xB∨xC)

( x A∧xB)∨(x A∧xC)  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×CB×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,bH,则有a*bH。

证明: 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 ∵HG且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)(PQ) (2)(PQ)(P∧(Q∨R)) 解:(1)因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q)

(P∧Q)∨(P∧Q)∨(P∧Q) m1∨m2∨m3 M0

所以,公式(P∨Q)(PQ)为可满足式。

(2)因为(PQ)(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

所以,公式(PQ)(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|=

fF24。若存在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)AA A∧C( A∧C)( AC)(AC)(AC)

A∨B(A∧B)(( AA)∧(BB))( AA)(BB) 所以

F((AC)(AC))∨((BC)(BC)) (((AC)(AC))((AC)(AC)))(((BC)(BC))((BC)(BC))) (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))∨xA(x)∨xB(x) (xA(x)∨xA(x)∨xB(x))∧(xB(x)∨xA(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,i11>,<5,4>,<5,5>}。

五、(10分)设函数g:A→B,f:B→C,

(1)若fg是满射,则f是满射。 (2)若fg是单射,则g是单射。

证明

因为g:A→B,f:B→C,由定理5.5知,fg为A到C的函数。

(1)对任意的z∈C,因fg是满射,则存在x∈A使fg(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,则由fg是单射得fg(x1)≠fg(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的邻接矩阵为:

00A00101011

101100(2)由于

002A001110220130

1 A0211102011120322044A

031201012313 2322所以v1到v4长度为

1、

2、3和4的路的个数分别为

1、

1、

2、3。 (3)由于

00ATA000002131212TAA

21011102132110 2121再由定理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)00B4AA2A3A40000所以求可达矩阵为P0000(5)因为PPT0010100110+10101000111111。

11111111101111∧1111111100001110=01110111000111,所以{v1},{v2,v3,v4}

111111因

1110



2010

+

1110

0110

2120312204+

2120320101231323220

000

741

747

747

434构成G的强分图。

离散数学试题(B卷答案8)

一、(10分)证明(P∨Q)∧(PR)∧(QS)S∨R

证明

因为S∨RRS,所以,即要证(P∨Q)∧(PR)∧(QS)RS。 (1)R

附加前提 (2)PR

P (3)P

T(1)(2),I (4)P∨Q

P (5)Q

T(3)(4),I (6)QS

P (7)S

T(5)(6),I (8)RS

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,|ABC|=25-20=5。故,不会打这三种球的共5人。

四、(10分)设A

1、A2和A3是全集U的子集,则形如Ai(Ai为Ai或Ai)的集合称

i13为由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,于是Usi。又显然有siU,所以U=si。

i1i1i1i1i13rrrr任取两个非空小项sp和sq,若sp≠sq,则必存在某个Ai和Ai分别出现在sp和sq中,于是sp∩sq=。

综上可知,{s1,s2,…,sr}是U的一个划分。

五、(15分)设R是A上的二元关系,则:R是传递的R*RR。

证明

(5)若R是传递的,则∈R*Rz(xRz∧zSy)xRc∧cSy,由R是传递的得xRy,即有∈R,所以R*RR。

反之,若R*RR,则对任意的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)fg是A到C的函数;

(2)对任意的x∈A,有fg(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,即∈fg。所以Dfg=A。

对任意的x∈A,若存在y

1、y2∈C,使得、∈fg=g*f,则存在t1使得∈g且∈f,存在t2使得∈g且∈f。因为g:A→B是函数,则t1=t2。又因f:B→C是函数,则y1=y2。所以A中的每个元素对应C中惟一的元素。

综上可知,fg是A到C的函数。

(2)对任意的x∈A,由g:A→B是函数,有∈g且g(x)∈B,又由f:B→C是函数,得∈f,于是∈g*f=fg。又因fg是A到C的函数,则可写为fg(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]RaH。对任意的b∈aH,存在h∈H使得b=a*h,a1*b=h∈H,

-b>∈R,故aH[a]R。所以,[a]R=aH。

离散数学试题(B卷答案9)

一、(10分)证明(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))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 ( A∧((P∧Q)∨(P∧Q)))∨C ( A∧(PQ))∨C (A∧(PQ))C。

二、(10分)举例说明下面推理不正确:xy(P(x)Q(y)),yz(R(y)Q(z))xz(P(x)R(z))。

解:设论域为{1,2},令P(1)=P(2)=T;Q(1)=Q(2)=T;R(1)=R(2)=F。则: xy(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))) ((TT)∨(TT))∧((TT)∨(TT)) T yz(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)))

((FT)∨(FT))∧((FT)∨(FT))

T

xz(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))) ((TF)∧(TF))∨((TF)∧(TF)) F 所以,xy(P(x)Q(y)),yz(R(y)Q(z))xz(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,i11>,<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]RaiH

i1i1kk又因为对H中任意不同的元素x、y∈H及a∈G,必有a*x≠a*y,所以|a1H|=…=|akH|=|H|。因此

|G||aiH|i1k|aH|k|H|=|H|·[G:H]。

ii1k

八、(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分)使用将命题公式化为主范式的方法,证明(PQ)(P∧Q)(QP)∧(P∨Q)。

证明:因为(PQ)(P∧Q)(P∨Q)∨(P∧Q)

(P∧Q)∨(P∧Q) (QP)∧(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) 所以,(PQ)(P∧Q)(QP)∧(P∨Q)。

二、(10分)证明下述推理: 如果A努力工作,那么B或C感到愉快;如果B愉快,那么A不努力工作;如果D愉快那么C不愉快。所以,如果A努力工作,则D不愉快。

解 设A:A努力工作;B、C、D分别表示B、C、D愉快;则推理化形式为: AB∨C,BA,DCAD

(1)A 附加前提 (2)AB∨C P (3)B∨C T(1)(2),I (4)BA P (5)AB

T(4),E (6)B T(1)(5),I (7)C T(3)(6),I

(8)DC P (9)D T(7)(8),I (10)AD CP

三、(10分)证明xy(P(x)Q(y))(xP(x)yQ(y))。 xy(P(x)Q(y))xy(P(x)∨Q(y)) x(P(x)∨yQ(y)) xP(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的关系矩阵为:

10M(R)111011101100 00(3)对于R的关系矩阵,由于对角线上不全为1,R不是自反的;由于对角线上存在非0元,R不是反自反的;由于矩阵不对称,R不是对称的;

经过计算可得

10M(R2)111011101100M(R),所以R是传递的。 00

六、(15分)设函数f:R×RR×R,f定义为:f()=。 (1)证明f是单射。 (2)证明f是满射。 (3)求逆函数f。

(4)求复合函数ff和ff。

证明 (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-

1uwuwuwuw

,y=,则f()=<+,2222uwuw->=,所以f是满射。 22(3)f()=<-1-1uwuw,>。 22-1(4)ff()=f(f())=f

-1

()=<

xyxy,

2xy(xy)>= 2ff()=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

111理,由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、„、vn1中的某个结点相邻,得新边en1,由此可见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是整数集,定义为xxy=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.陈述句

真值

三、计算题

1100101026. M=

1011001122

2 M=21110111

121011M2ij18,

ij6 M2i1

4 i1j144

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)

(换名)

┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2)

x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2)

x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

四、证明题

32.设T中有x片树叶,y个分支点。于是T中有x+y个顶点,有x+y-1 条边,由握手定理知T中所有顶点的度数之的

xy

d(vi)=2(x+y-1)。

i

1 又树叶的度为1,任一分支点的度大于等于2

且度最大的顶点必是分支点,于是

xy

d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i1

从而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的双射函数,故fg也是A到A的双射函数,从而集合F关于运算是封闭的。

(2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。

(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F,〉中的幺元

(4)f∈F,因为f是双射函数,故其逆函数是存在的,也是A到A的双射函数,且有ff-1=f-1f=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. 命题公式(PQ)Q为 ()

(A) 矛盾式 (B) 可满足式(C) 重言式 (D) 合取范式

2.设P表示“天下大雨”, Q表示“他在室内运动”,则命题“除非天下大雨,否则他不在室内运动”符号化为()。

(A). PQ; (B).PQ;(C).PQ; (D).PQ.

3.设集合A={{1,2,3}, {4,5}, {6,7,8}},则下式为真的是()

(A) 1A(B) {1,2, 3}A

(C) {{4,5}}A(D) A

4. 设A={1,2},B={a,b,c},C={c,d}, 则A×(BC)= ()

(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,yy2x,xA,yB},

那么R1=-

8. 在“同学,老乡,亲戚,朋友”四个关系中_______是等价关系.9. 写出一个不含“”的逻辑联结词的完备集.

10.设X={a,b,c},R是X上的二元关系,其关系矩阵为

101,那么R的关系图为 MR=100100

三、证明题(共30分)

11. (10分)已知A、B、C是三个集合,证明A∩(B∪C)=(A∩B)∪(A∩C)

12. (10分)构造证明:(P(QS))∧(R∨P)∧QRS

(0,1)13.(10分)证明与[0,1),[0,1)与[0,1]等势。

四、解答题(共35分)

14.(7分)构造三阶幻方(以1为首项的9个连续自然数正好布满一个33方阵,且方阵中的每一行, 每一列及主、副对角线上的各数之和都相等.)

15.(8分) 求命题公式(PQ)(PQ)的真值表.16.(10分)设R1是A1={1,2}到A2=(a,b,c)的二元关系,R2是A2到A3={,}的二元关系,R1= {<1,a>,<1,b>,<2,c>}, R2={,}

毕节学院《离散数学 》课程试卷第 1 页 共 4 页

求R1R2的集合表达式.

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∧(xB∨xC) ······························································································· 3分

( x A∧xB)∨(x A∧xC) ··········································································· 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(QS)P ······································································································· 4分

(5)QST(3)(4),I ······················································································ 5分

(6)QP ······································································································· 6分

(7)ST(5)(6),I ······················································································ 8分

(8)RSCP ··································································································· 10分

13. 证明:a) 设A{,,,

c第10题答案图 11

231,},作f:(0,1)[0,1)如下: ································· 2分 n

1f()0211,xAn2 ························································································ 5分 f()nn1f(x)x,x(0,1)A

b) 设A,,,11

231,},作f:[0,1)[0,1]如下: ····················································· 7分 n

毕节学院《离散数学 》课程试卷第 2 页 共 4 页

f(0)0111························································································ 10分 ,n1,A ·f()n1nn

f(x)x,x[0,1)A

14.

8

9 5 1 2 7 6

填对每个格得1分。

15.

表中最后一列的数中,每对1个数得2分.

11016.MR1,(2分)001

MR201(4分) 0100

010101(6分) 0000110 MR1R2001

R1R2{1,}(10分)

17. 解设A:A去工作;B:B去工作;C:C去工作;D:D去工作。则根据题意应有:ACD,(B∧C),CD必须同时成立。 ······························································································ 2分 因此(ACD)∧(B∧C)∧(CD)

(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 页

上一篇
下一篇
返回顶部