当前位置:文档之家› 652离散数学答案2013

652离散数学答案2013

652离散数学答案2013
652离散数学答案2013

河南科技大学

2013年硕士研究生入学考试试题答案及评分标准

考试科目代码: 652 考试科目名称: 离散数学

一、单项选择题(本大题共15小题,每小题2分,共30分)

在每小题列出的备选项中只有一个是符合题目要求的,错选、多选或未选均无分。 1-5:B A A D C 6-10:D A B B A 11-15:B D B B D

二、填空题(本大题共10小题,每小题2分,共20分)

1. p q ? 1或真

2. 01,10

3. 反对称 、 传递

4. {,{},{},{,}}a b a b ?

5. {2,2,3,3,6,6,3,2,6,2,6,3,}<><><><><><>

6.

7. 3 、 1

8.

9. 1

10. 1001011

0()1100001

1M G ???

???=???

???

三、计算题(本大题共5小题,每小题8分,共40分)

1.利用等值演算化简命题公式A ,并指出A 的类型(注:重言式、矛盾式或可满足式)

A =()()()p q r q r p r ?∧?∧∨∧∨∧

解:A =()()()p q r q r p r ?∧?∧∨∧∨∧

(())(())p q r q p r ??∧?∧∨∨∧ (1分) (())(())p q r q p r ??∧?∧∨∨∧ (1分) (()())p q q p r ??∧?∨∨∧ (1分) (()())p q q p r ??∨∨∨∧ (1分) 1r ?∧ (1分) r ? (1分)

所以,A 是可满足式 (2分)

2.设f 是一元运算,P 是一元谓词,Q 是二元谓词,给出解释I :D I ={2, 3},f (2)=3,f (3)=2,P (2)=1,P (3)=0,

Q (2, 2)=Q (3, 3)=1,Q (2, 3)=Q (3, 2)=0,求在解释I 下?x ?y (Q (f (x ), y ))→P (x ))的真值。 解:(((),)())x y Q f x y P x ??→

((((2),)(2))((((3),)y Q f y P y Q f y P ??→∧?→ (2分) ((

(3,2)1)

((3,3)1))

(((2,2)

0)Q Q Q Q ?→∨→∧→∨→ (2分)

((01)(11))

((10)(0?→∨→∧→∨→ (2分)

(11)(0

1)?∨∧∨? (2分)

3.设,A R ??为偏序集,其中A ={1,2,3,4,5,6},R 是A 上的整除关系。 (1) 写出偏序关系R 的表达式,并画出,A R ??的哈斯图; (2) 求该偏序集的最大元、最小元、极大元和极小元;

解:(1) {1,2,1,3,1,4,1,5,1,6,2,4,2,5,2,6,3,6}A R I =<><><><><><><><><>? (2分)

哈斯图如下:(2分)

(2) 无最大元 (1分)

最小元是1 (1分) 极大元是4,5,6 (1分) 极小元是1 (1分)

4.设S =Q ?Q ,其中Q 是有理数集合,在S 上定义二元运算*:S y x b a >∈<>*=。求代数系统(S ,*)的单位元和S 中可逆元素的逆元。

解:(1)设单位元e =<1e ,2e >,S b a >∈<*>>=<>=<<*>

=及<1e a ,1e b +2e >= 得到:12112ae a ae b b e a a e b e b

=??

+=??

=??+=? (2分)

121,0,1,0e e e S ∴===<>∈ (1分)

(2) S b a >∈,有

,,1,0a b x y <>*<>=<>,,,1,0x y a b <>*<>=<> (1分)

即,ax ay b <+>=,1,0xa xb y <+>=<>1

010

ax ay b xa xb y =??

+=??

=??+=? (2分)

求得:x=

a 1,y=)0(≠-a a

b

∴对任意∈S ,只要a ≠0,那么的逆元为

b

-> (1分)

5. 已知图(,)G V E =,{,,,,}V a b c d e =的邻接矩阵为010********

1010101010

1010A ?????

???=??

??????

(1) 画出G 中所表示的图形;

(2) G 中长度为3的通路有几条?其中回路有几条? 解:(1) G 的图形如下:(2分

)

a

b

c d

(2) 经计算知:2

2

020*******

02020303020202A ??

????

??=??

?????? (2分)

3

06060606060

6060606060

6060A ??????

??=??

??????

(2分)

因此,G 中长度为3的通路有72条,其中回路是0条。 (2分)

四、证明题 (本大题共3小题,每小题10分,共30分)

1.在一阶(谓词)逻辑中符号化下列语句,并构造推理证明。

学术委员会的每个成员都是博士并且是教授。有些成员是年轻人。因而有的成员是青年教授。 证明:先将简单命题符号化:(2分)

设F(x):x 是学术委员会成员,G(x):x 是教授,H(x):x 是博士,R(x):x 是青年人 前提:(()()())x F x G x H x ?→∧,(()())x F x R x ?∧ 结论:(()()())x F x R x G x ?∧∧ 推理证明如下:

(1) (()())x F x R x ?∧ 前提引入

(2) ()()F c R c ∧ (1)EI (1分)

(3) (()()())x F x G x H x ?→∧ 前提引入

(4) ()()()F c G c H c →∧ (3)UI (1分)

(5) ()F c (2)化简 (1分) (6) ()()G c H c ∧ (4)(5)假言推理 (1分) (7) ()G c (6)化简 (1分) (8) ()R c (2)化简 (1分) (9) ()()()F c G c R c ∧∧ (5)(7)(8)合取 (1分) (10) (()()())x F x G x R x ?∧∧ (9)EG (1分)

2.如果集合A 上的关系R 和S 是自反的、对称的、传递的,证明:R S 是A 上的等价关系。 证明:(1) a A ?∈,由R 、S 自反知:,,,a a R a a S <>∈<>∈,则,a a R S <>∈?

R S ∴?自反; (3分)

(2) ,a b A ?∈,若,a b R S <>∈?,则,,,a b R a b S <>∈<>∈,由R 、S 对称知:则,b a R S <>∈?

R S ∴?对称; (3分)

(3) ,,a b c A ?∈,若,a b R S <>∈?,,b c R S <>∈?,由R 、S 的传递性知:则,a c R S <>∈?

R S ∴?传递; (4分)

综上可得R S ?是A 上的等价关系。

3. 设S =R -{-1}(R 为实数集),a*b=a+b+ab 。证明:,s ?*?是群。

证明:(1) ,a b S ?∈,a b a b ab S *=++∈,所以*运算封闭; (2分)

(2) ,,a b c S ?∈,()()()a b c a b ab c a b c ab ac bc abc a b c **=++*=++++++=**, 所以,*满足结合律; (2分)

(3) 设S 关于*有幺元e ,有**0a e e a a e ae a e ==++=?=;(3分) (4) 设a S ?∈有逆元1a -,有1111101a

a a a a e a a aa a a

------*=*=?++=?=

+, 即任意元有逆元; (3分)

综上得出,,s ?*?是群。

五、应用题(本大题共2小题,每小题15分,共30分)

1.一航空公司采用三台计算机复核飞行计划以确保其安全性,每台计算机能给出飞行计划正确或错误的回答,由所给的答案,再根据“少数服从多数”的原则做出判断。试将结果用命题公式表示,并加以简化,画出相应的逻辑电路图。(门电路示意图如图5.1所示

)

p q

p q

p q

p q

非门

p p

?

图5.1

解:设p 、q 、r 分别表示三台计算机的答案,S 表示判断的结果 (1) 根据题意,建立其真值表 ------------------(4分)

(2) 根据真值关系写出S S =(┐p ∧q ∧r)∨(p ∧┐q ∧r)∨(p ∧q ∧┐r)∨(p ∧q ∧r) (3) 利用等值演算化简S 得 ------------------(3分) S ?(q ∧r)∨(p ∧r)∨(p ∧q)

(4) S 的逻辑电路图 ------------------(5分)

S

2.假设有6个网络节点i v (i =l ,2,…,6),欲铺设光纤线路使各网络节点可连通,如图5.2所示,图中的边代表铺设线路,边上的数字表示铺设该线路所需费用。由于费用的限制,要求总的铺设费用最低并确保任意二个网络节点之间是可连通的,请写出求解过程,画出符合要求的最低费用的网络线路铺设图并计算其费用。

图5.2

解:

(1) 显然该问题是求带权无向图的最小生成树(用Kruskal 算法-避圈法),去掉顶点V3处的环。 把剩下的边按其权值由小到大排序。

用Kruskal 算法-避圈法,求解过程如下:

(a)v11v1

v2

(c)

2

v6

v1

v2(b)

2

v6

v4

1

13v1

v2

(d)

2

v6v4

13v55

v1

v2

(e)

2

v6v4

13v55

v3

则,图(e)就是所要求的网络线路铺设图。 (10分) (2) 网络线路铺设费用为: (5分) 1+2+3+5+7=18

离散数学期末试题

离散数学考试试题(A 卷及答案) 一、(10分)求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解:(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 ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、(10分)在某次研讨会的休息时间,3名与会者根据王教授的口音分别作出下述判断: 甲说:王教授不是苏州人,是上海人。 乙说:王教授不是上海人,是苏州人。 丙说:王教授既不是上海人,也不是杭州人。 王教授听后说:你们3人中有一个全说对了,有一人全说错了,还有一个人对错各一半。试判断王教授是哪里人? 解 设设P :王教授是苏州人;Q :王教授是上海人;R :王教授是杭州人。则根据题意应有: 甲:?P ∧Q 乙:?Q ∧P 丙:?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以,丙至少说对了一半。因此,可得甲或乙必有一人全错了。又因为,若甲全错了,则有?Q ∧P ,因此,乙全对。同理,乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为: ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此,王教授是上海人。 三、(10分)证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系,则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系,则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )='R ,进而有tsr (R )?t ('R )='R 。

离散数学及其应用 重要名词中英对应以及重要概念解释与举例

离散数学及其应用重要名词中英对应以及重要概念解释与举例 1 The Foundations: Logic and Proofs(逻辑与证明) 1.1 Propositional Logic(命题逻辑) Propositions(命题)——declarative sentence that is either true or false, but not both.判断性语句,正确性唯一。 Truth Table(真值表) Conjunction(合取,“与”,and),Disjunction(析取,or,“相容或”),Exclusive(异或),Negation(非,not),Biconditional(双条件,双向,if and only if) Translating English Sentences 1.2 Propositional Equivalences(命题等价) Tautology(永真式、重言式),Contradiction(永假式、矛盾式),Contingency(偶然式) Logical Equivalences(逻辑等价)——Compound propositions that have the same truth values in all possible cases are called logical equivalent.(真值表相同的式子,p<->q是重言式) Logical Equivalences——Page24 Disjunctive normal form(DNF,析取范式) Conjunctive normal form(CNF,合取范式) 见Page27~29 1.3 Predicates and Quantifiers(谓词和量词) Predicates——谓词,说明关系、特征的修饰词 Quantifiers——量词 ? Universal Quantifier(全称量词) "

离散数学期末试卷A卷及答案

《离散数学》试卷(A 卷) 一、 选择题(共5 小题,每题 3 分,共15 分) 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3,则4+5=9; B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3,则4+5≠9; D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时,下列公式( C )不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质( B )。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是( D )。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题(共 5 小题,每题 3 分,共15 分) 1、设|A|=4,|P(B)|=32,|P(A ?B)|=128,则|A ?B|=??2???.

2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?,其中)(x P :x=1, )(x Q :x=2,当论域为{0,1,2}时,其真值为???1???。 4、设A ={1,2,3,4},则A 上共有???15????个等价关系。 5、设A ={a ,b ,c },B={1,2},则|B A |= 8 。 三、判断题(对的填T ,错的填F ,共 10 小题,每题 1 分,共计10 分) 1、“这个语句是真的”是真命题。 ( F ) 2、“张刚和小强是同桌。”是复合命题。 ( F ) 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 ( T ) 4、)(T S R T R S R ??????。 ( F ) 5、恒等关系具有自反性,对称性,反对称性,传递性。 ( T ) 6、若f 、g 分别是单射,则g f ?是单射。 ( T ) 7、若g f ?是满射,则g 是满射。 ( F ) 8、若A B ?,则)()(A P B P ?。 ( T ) 9、若R 具有自反性,则1-R 也具有自反性。 ( T ) 10、B A ∈并且B A ?不可以同时成立。 (F ) 四、计算题(共 3 小题,每题 10 分,共30 分) 1、调查260个大学生,获得如下数据:64人选修数学课程,94人选修计算机课程,58人选修商贸课程,28人同时选修数学课程和商贸课程,26人同时选修数学课程和计算机课程,22人同时选修计算机课程和商贸课程,14人同时选修三门课程。问 (1)三门课程都不选的学生有多少? (2)只选修计算机课程的学生有多少?

安徽大学期末试卷离散数学上卷及参考答案.doc

安徽大学20 09 — 20 10 学年第 1 学期 《离散数学(上)》考试试卷(A 卷) (时间120分钟) 院/系 专业 姓名 学号 题 号 一 二 三 四 五 总分 得 分 一、单选题(每小题2分,共20分) 1. 设A={a,b,c},A 上二元关系R={〈a,a 〉,〈b,b 〉,〈a,c 〉},则关系R 的对称闭包S(R)是( ) A.R ∪I A B.R C.R ∪{〈c,a 〉} D.R ∩I A 2. 设X={a,b,c},I x 是X 上恒等关系,要使I x ∪{〈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 〉} 3. 下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 4. 设解释R 如下:论域D 为实数集,a=0, f(x,y)=x-y, A(x,y):x

离散数学期末试题及答案完整版

离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

326《离散数学》期末考试题(B ) 一、填空题(每小题3分,共15分) 1.设,,},,{{b a b a A =?},则-A ? = ( ),-A {?} = ( ), )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素,则A 上的二元关系有( )个,其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ,对于其上的整除关系“|”,元素( )不存在补元. 5.当n ( )时,n 阶完全无向图n K 是平面图,当当n 为( )时,n K 是欧拉图. 二.1. 若n B m A ==||,||,则=?||B A ( ),A 到B 的2元关系共有( )个,A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)},则( )是单射,( )是满射,( )是双射. 3. 下列5个命题公式中,是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(; (2))(q p p ∨→; (3))(q p p ∧→; (4)q q p p →∨∧?)(; (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合,“|”是其上的整除关系,则3的补元( ),4的补元( ),6的补元( ).

(完整版)离散数学及其应用(课后习题)

习题1.1 2. 指出下列命题是原子命题还是复合命题。 (3)大雁北回,春天来了。 (4)不是东风压倒西风,就是西风压倒东风。 (5)张三和李四在吵架。 解:(3)和(4)是复合命题,(5)是原子命题。 习题1.2 1. 指出下列命题的真值: (1)若224+>,则太阳从西方升起。 解:该命题真值为T (因为命题的前件为假)。 (3)胎生动物当且仅当是哺乳动物。 解:该命题真值为F (如鸭嘴兽虽是哺乳动物,但不是胎生动物)。 2. 令P :天气好。Q :我去公园。请将下列命题符号化。 (2)只要天气好,我就去公园。 (3)只有天气好,我才去公园。 (6)天气好,我去公园。 解:(2)P Q →。 (3)Q P →。 (6)P Q ?。 习题1.3 2. 将下列命题符号化(句中括号内提示的是相应的原子命题的符号表示): (1)我去新华书店(P ),仅当我有时间(Q )。 (3)只要努力学习(P ),成绩就会好的(Q )。 (6)我今天进城(P ),除非下雨(Q )。 (10)人不犯我(P ),我不犯人(Q );人若犯我,我必犯人。 解:(1)P Q →。 (3)P Q →。 (6)Q P ?→。 (10)()()P Q P Q ?→?∧→。 习题1.4 1. 写出下列公式的真值表: (2)()P Q R ∨→。

解:该公式的真值表如下表: 2. 证明下列等价公式: (2)()()()P Q P Q P Q ∨∧?∧???。 证明: ()(()()) ()()) ()() ()() P Q P Q P Q P Q P Q P Q P Q P Q P Q ????∧∨?∧???∧∧??∧???∧∧∨?∨∧?∧ (4)()()()P Q P R P Q R →∧→?→∧。 证明: ()()()() () () P Q P R P Q P R P Q R P Q R →∧→??∨∧?∨??∨∧?→∧ 3. 甲、乙、丙、丁4人参加考试后,有人问他们谁的成绩最好,甲说,不是我。乙说:是丁。丙说:是乙。丁说:不是我。已知4个人的回答只有一个人符合实际,问成绩最好的是谁? 解:设A :甲成绩最好。B :乙成绩最好。C :丙成绩最好。D :丁成绩最好。 四个人所说的命题分别用P Q R S 、、、表示,则 P A ??;Q A B C D ??∧?∧?∧;R A B C D ??∧∧?∧?;S D ??。 则只有一人符合实际的命题K 符号化为 ()()()() K P Q R S P Q R S P Q R S P Q R S ?∧?∧?∧?∨?∧∧?∧?∨?∧?∧∧?∨?∧?∧?∧

离散数学期末试卷及答案

一.判断题(共10小题,每题1分,共10分) 在各题末尾的括号内画 表示正确,画 表示错误: 1.设p、q为任意命题公式,则(p∧q)∨p ? p ( ) 2.?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3.初级回路一定是简单回路。( ) 4.自然映射是双射。( ) 5.对于给定的集合及其上的二元运算,可逆元素的逆元是唯一的。( ) 6.群的运算是可交换的。( ) 7.自然数集关于数的加法和乘法构成环。( ) 8.若无向连通图G中有桥,则G的点连通度和边连通度皆为1。( ) 9.设A={a,b,c},则A上的关系R={,}是传递的。( ) 10.设A、B、C为任意集合,则A?(B?C)=(A?B)?C。( ) 二、填空题(共10题,每题3分,共30分) 11.设p:天气热。q:他去游泳。则命题“只有天气热,他才去游泳”可符号 化为。 12.设M(x):x是人。S(x):x到过月球。则命题“有人到过月球”可符号 化为。 13.p?q的主合取范式是。 14.完全二部图K r,s(r < s)的边连通度等于。 15.设A={a,b},,则A上共有个不同的偏序关系。 16.模6加群中,4是阶元。 17.设A={1,2,3,4,5}上的关系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>},则R的传递闭包t(R) = 。. 18.已知有向图D的度数列为(2,3,2,3),出度列为(1,2,1,1),则有向图D的入度

列为。 19.n阶无向简单连通图G的生成树有条边。 20.7阶圈的点色数是。 三、运算题(共5小题,每小题8分,共40分) 21.求?xF(x)→?yG(x,y)的前束范式。 22.已知无向图G有11条边,2度和3度顶点各两个,其余为4度顶点,求G 的顶点数。 23.设A={a,b,c,d,e,f},R=I A?{,},则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。 24.求图示带权图中的最小生成树,并计算最小生成树的权。 25.设R*为正实数集,代数系统< R*,+>、< R*,·>、< R*,/>中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群?是群者,求其单位元及每个元素的逆元。 四、证明题(共3小题,共20分) 26 (8分)在自然推理系统P中构造下述推理的证明: 前题:p→(q∨r),?s→?q,p∧?s 结论:r 27 (6分)设是群,H={a| a∈G∧?g∈G,a*g=g*a},则是G的子群 28.(6分)设G是n(≥3)阶m条边、r个面的极大平面图,则r=2n-4。

大学《离散数学》期末考试试卷及答案-(1)

安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷(A卷) (时间120分钟) 开课院(系、部)姓名学号. 一、选择题(每小题2分,共20分)1.下列语句中,哪个是真命题()A、 4 2= + x; B、我们要努力学习; C、如果ab为奇数,那么a是奇数,或b是偶数; D、如果时间流逝不止,你就可以长生不老。 2.下列命题公式中,永真式的是() A、P Q P→ →) (; B、P P Q∧ → ?) (; C、Q P P? ? ∧) (; D、) (Q P P∨ →。3.在谓词逻辑中,令) (x F表示x是火车;) (y G表示y是汽车;) , (y x L表示x比y快。 命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的()

I.)),()()((y x L y G x F y x →∧??? II.)),()()((y x L y G x F y x ?∧∧?? III. )),()()((y x L y G x F y x ?→∧?? A 、仅I ; B 、仅III ; C 、I 和II ; D 、都不对。 4.下列结论正确的是:( ) A 、若C A B A =,则 C B =; B 、若B A B A ?,则B A =; C 、若C A B A =,则C B =; D 、若B A ?且D C ?,则D B C A ?。 5.设φ=1A ,}{2φ=A ,})({3φρ=A ,)(4φρ=A ,以下命题为假的是( ) A 、42A A ∈; B 、31A A ?; C 、24A A ?; D 、34A A ∈。 6.设R 是集合},,,{d c b a A =上的二元关系, },,,,,,,,,,,{><><><><><><=b d d b a c c a a d d a R 。下列哪些命题为真( ) I.R R ?是对称的 II. R R ?是自反的 III. R R ?不是传递的 A 、仅I ; B 、仅II ; C 、I 和II ; D 、全真。

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

离散数学试题(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 ?P (2) E(A∧B) ??P (3) (C∨D)(A∧B) T(1)(2),I (4) (A∧B)(R∨S)??P (5) (C∨D)(R∨S) ? T(3)(4),I (6) C∨D 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) xA∧(xB∧x C) (x A∧x B)∧(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=x2} R*S={| x,y N∧y=x2+1} S*R={<x,y>| x,yN∧y=(x+1)2},R{1,2}={<1,1>,<2,4>},S[{1,2}]={1,4}。 七、设R={<a,b>,,<c,a>},求r(R)、s(R)和t(R) (15分)。 解:r(R)={,,,<b,b>,

离散数学期末试卷(A)

离散数学期末试卷(A) XXXX大学XX学院2007 ~2008学年第一学期《离散数学》期末试卷年级专业题号得分适用年级专业:2006级软件工程专业试卷说明:闭卷考试,考试时间120分钟一、单项选择题1.下列语句中只有不是命题。C A.今年元旦会下雪。B.1+1=10。C.嫦娥一号太棒了!D.嫦娥奔月的神话已成为现实。2.p?q 的主合取范式是。 B A.(p?q)?(p??q)B.(p??q)?(?p?q) C.(p?q)?(?p??q)D.(p?q)?(?p?q) 3.与p? q等值的命题公式是。D A.?p?q B.p??q C.p??q D.?p?q 4.在一阶逻辑中使用的量词只有个。B A.1B.2 C.3D.4 5.??xA(x)?。C A.??xA(x) B.?x?A(x) C.?x?A(x)

D.?xA(x) 6.若|A|=4,则|P(A)|=。 C A.4B.8C.16 D.64 7.设A、B、C为任意集合,集合的对称差运算不具有的性质是。 D A.A?B = B?A B.(A?B)?C = B?(A?C) 班级学号一二三姓名____________ 四总分C.A?A = ?D.A?A = A 8.二元关系是。B A.两个集合的笛卡儿积B.序偶的集合C.映射的集合D.以上都不是9.下面关于函数的叙述中正确的是。D A.函数一定是满射B.函数一定是单射C.函数不是满射就单射D.函数是特殊的关系10.半群中的二元运算一定满足=。B A.交换律B.结合律C.分配律D.幂等律11.环中有个二元运算。 B A.一B.二C.三D.四12.群与独异点的区别是。 C A.满足交换律B.满足结

《离散数学》期末考试试题

《离散数学》期末考试试题 一、 填空题(每空2分,合计20分) 1. 设个体域为{2,3,6}D =-, ():3F x x ≤,():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生,:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =,{2,4,6}B =,则A B -=________,A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =,在集合A 上定义两种关系: {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>, 则_______________S R =ο,_______________R S =ο。 6. 设e 是群G 上的幺元,若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7. 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系,则偏序集,A <>p 的最大元是________,极小元是_ _。 9. 一棵有6个叶结点的完全二叉树,有_____个内点;而若一棵树有2个结点度数为2,一 个结点度数为3,3个结点度数为4,其余是叶结点,则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =,若G 的邻接矩阵????????????=0001001111011010A ,则1()deg v -=________, 4()deg v +=____________。 二、选择题(每题2分,合计20分) 1.下列各式中哪个不成立( )。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ; B 、)()())()((x xQ x xP x Q x P x ?∨??∨?; C 、)()())()((x xQ x xP x Q x P x ?∧??∧?; D 、Q x xP Q x P x ∧??∧?)())((。

离散数学及应用课后习题答案

离散数学及应用课后习题答案 【篇一:离散数学及其应用图论部分课后习题答案】 p165:习题九 1、给定下面4个图(前两个为无向图,后两个为有向图)的集合 表示,画出它们的图形表 示。 (1)g1??v1,e1?,v1?{v1,v2,v3,v4,v5}, e1?{(v1,v2),(v2,v3),(v3,v4),(v3,v3),(v4,v5)} (2)g2??v2,e2?, v2?v1,e1?{(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)} (3) d1??v3,e3?,v3?v1,e3?{?v1,v2?,?v2,v3?,?v3,v2?,?v4,v5?,?v5,v 1?} (4) d2??v4,e4?,v4?v1,e3?{?v1,v2?,?v2,v5?,?v5,v2?,?v3,v4?,?v4,v 3?} 解答:(1) (2) 10、是否存在具有下列顶点度数的5阶图?若有,则画出一个这样 的图。 (1)5,5,3,2,2;(2)3,3,3,3,2;(3)1,2,3,4,5;(4)4,4,4,4,4 解答:(1)(3)不存在,因为有奇数个 奇度顶点 。 14、设g是n(n?2)阶无向简单图,g是它的补图,已 知?(g)?k1,?(g)?k2,求?(g), ?(g)。 解答:?(g)?n?1?k2;?(g)?n?1?k1。 15、图9.19中各对图是否同构?若同构,则给出它们顶点之间的双 射函数。 解答: (c)不是同构,从点度既可以看出,一个点度序列为4,3,3,3,3而另外一个为4,4,3,3,1 (d)同构,同构函数为 ?1?2??f(x)??3 ?4???5 解答: (1)三条边一共提供6度;所以点度序列可能是

离散数学期末试卷

1 / 6 北京工业大学经管学院期末试卷 《离散数学》(A ) 学号 姓名: 成绩 一、单项选择题(每题2分,共18分) 1.令P :今天下雪了,Q :路滑,则命题“虽然今天下雪了,但是路不. 滑”可符号化为( D ) A .P→Q B .P ∨Q C .P ∧Q D .P ∧Q p→q ,蕴涵式,表示假设、条件、“如果,就”。 “→”与此题无关 2. 关于命题变元P 和Q 的极大项M 1表示( C )。 书P1520,此题换作p 、q 更容易理解 A.┐P ∧Q B.┐P ∨Q p ∨┐q 01 1 M 1 ∨┐Q ∧┐Q 3.设R (x ):x 是实数;S ():x 小于y 。用谓词表达下述命题:不存在最小的实数。其中错误的表达式是:( D ) 4.在论域{}中与公式(x ?)A (x )等价的不含存在量词的公式是( B ) A.)b (A )a (A ∧ B. )b (A )a (A ∨ C. )b (A )a (A → D. )a (A )b (A → 5.下列命题公式为重言式的是( C ) A .Q→(P ∧Q ) B .P→(P ∧Q ) C .(P ∧Q )→P D .( P ∨Q )→Q 牢记→真假条件,作为选择题可直接代入0、1,使选项出现1→0,排除。熟练的可直接看出C 不存在1→0的情况 6. 设{1,2,3},{},下列二元关系R 为A 到B 的函数的是( A ) A. {<1>,<2>,<3>} B. {<1>,<2>} C. {<1>,<1>,<2>,<3>} D. {<1>,<2>,<3>,<1>}

2 / 6 7.偏序关系具有性质( D ) 背 A.自反、对称、传递 B.自反、反对称 C.反自反、对称、传递 D.自反、反对称、传递 8.设R 为实数集合,映射:,R R σ→2 ()21,x x x σ=-+-则σ 是( D ). (A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射. 书P96.设函数f :A→B (1)若,则f 是满射的【即值域为B 的全集,在本题中为R ,该二次函数有最高点,不满足】 (2)若对于任何的x 12∈A , x 1≠x 2,都有f(x 1)≠f(x 2),则称f 是单射的【即真正一一对应,甚至不存在一个y 对应多个x 。显然,本题为二次函数,不满足】 (3)若f 既是满射的,又是单射的,则称f 是双射的【本题中两个都不满足,既不是单射也不是满射】 二、填空题(每空2分,共22分) 1.设Q 为有理数集,笛卡尔集×Q ,*是S 上的二元运算,?,∈S, *=<, >, 则*运算的幺元是<1,0>。?∈S, 若a≠0, 则的逆元是<1>。书P123定义 2.在个体域D 中,公式)x (xG ?的真值为假当且仅当某个G(x)的真值为假,公式)x (xG ?的真值为假,当且仅当所有G(x)的真值都为假。 3.给定个体域为整数域,若F (x ):表示x 是偶数,G (x ):表示x 是奇数;那么,)x (G )x ()x (F )x (?∧?是一个 永真式 ;而))x (G )x (F )(x (∧?是一个 永假式 。 4.设{}{}===)R (r ,c ,b ,b ,a R A ,c ,b ,a A 则上的二元关系  {<>,<>,<>,<>,<>,<>} ; s(R)= {<>,<>,<>,<>} 。 书P89、P85. 自反闭包:r(R) = R U R 0 ={<>,<>} U {<>,<>,<>,<>} ={<>,<>,<>,<>,<>,<>} 对称闭包:s(R) = R U R -1 = {<>,<>} U {<>,<>} = {<>,<>,<>,<>} 传递闭包:t(R) = 2 3U…… 5. 设{1,2,3}{},则从X 到Y 的不同的函数共有8个.

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

离散数学试题(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 P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2),I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4), I (6) C∨D 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

离散数学期末考试试题(有几套带答案)

离散数学试题(A卷及答案) 一、证明题(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) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D

(7) R∨S 2) ?x(P(x)→Q(y)∧R(x)),?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数,证明:在任取m+1个整数中,至少有两个整数,它们的差是m的整数倍 证明设 1 a,2a,…,1+m a为任取的m+1个整数,用m去除它们所得余数 只能是0,1,…,m-1,由抽屉原理可知, 1 a,2a,…,1+m a这m+1个整 数中至少存在两个数 s a和t a,它们被m除所得余数相同,因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) (15分)证明∵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=x2},S={| x,y∈N∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}](10分) 解:R-1={| x,y∈N∧y=x2},R*S={| x,y∈N∧y=x2+1},S*R={| x,y∈N∧y=(x+1)2}, 七、若f:A→B和g:B→C是双射,则(gf)-1=f-1g-1(10分)。 证明:因为f、g是双射,所以gf:A→C是双射,所以gf有逆函数

离散数学期末考试题

《离散数学》复习题 一、单项选择题(每小题2分,共20分) 1、下列命题中是命题的是( ) A 、 7>+y x B 、雪是黑色的 C 、严禁吸烟 D 、我正在说谎 2下列命题联结词集合中,哪个不是极小全功能集( )。 A 、{,}刭 B 、{,}刳 C 、{}- D 、{,}佼 3、下列公式中哪个不是简单析取式( )。 A 、p B 、p q ∨ C 、()p q ?∨ D 、p q ?∨? 4、设个体域{,}A c d =,公式()()x P x x S x ?∧?在A 中消去量词后应为( ) A ()()P x S x ∧ B (()())(()( P c P d S c S d ∧∧∨ C ()()P c S d ∧ D ()() () (P c P d S c S d ∧ ∧∨ 5、下列是命题公式p ∧(q ∨┓r)的成真指派的是( ) A.110,111,100 B.110,101,011 C.所有指派 D.无 6、下列命题中( )是正确的。 A. 若图G 有n 个顶点,则G 的各顶点的度和为2n; B. 无向树中任意两点之间均相互可达; C. 若有向图G 是弱连通的,则它必定也是单向连通; D. 若无向带权图G 是连通的,则其最小生成树存在且唯一。

7、正整数集合Z +的以下四个划分中,划分块最多的是( ) A .1π={{x }︱x ∈Z + } B .2π= {Z + } C. 3π={12,S S },1S 为素数集,21S Z S + =- D .3π={12,S S ,3S },i S 为Z +中元素除以3的余数 8、给定下列各图: ⑴G 1=,其中V 1=(a ,b ,c ,d ,e), E 1={(a 、b ),(b 、c ),(c 、d ),(a 、e )} ⑵G 2=,其中V 2=V 1, E 2={(a 、b ),(b 、e ),(e 、b ),(d 、e )} ⑶G 3=,其中V 3=V 1, E 3={(a 、b ),(b 、e ),(e 、d ),(c 、c ), (e 、d )} ⑷D 4=,其中V 4=V 1, E 4={} 在以上4个图中A ( )为简单图,B ( )为多重图。 供选答案:A : a: ⑴⑶ b :⑶⑷ c :⑴⑷ B : a :⑵⑶ b :⑴⑵ c :⑴⑷ 9、设X={1, 2, 3, 4},Y={a, b, c, d},则下列关系中为函数的是( )。 A 、{<1, a><1, b><2, c>} B 、{<1, a><2, d><3, c><4, b>} C 、 {<1, a><2, a><3, b>} D 、{<1, a><1, b><2, b><4, b>} 10、设,G V E =<>为无向图,u,v ?V ,u ≠v ,若u,v 连通,则( )。 A 、(,)0d u v > B 、(,)0d u v = C 、(,)0d u v < D 、(,)0d u v 3 二、填空题(每空3分,共30分) 1、设P :我有钱,Q :我去看电影。命题“虽然我有钱,但我不去看电影”符号化为 。

浙江师范大学离散数学期末试卷A

浙江师范大学《离散数学》考试卷 (2010—2011学年第 1 学期) 考试形式闭卷使用学生软件工程、网络工程09 考试时间120分钟出卷时间2010 年12 月26 日 说明:考生应将全部答案都写在答题纸上,否则作无效处理。 一.选择题(每题2分,共20分): 1. 设P:我平时认真学习,Q:我通过离散数学考试,则如下哪种说法能符号化为 P→Q:() A.除非我平时认真学习,否则我不能通过离散数学考试。 B. 若我平时认真学习,则我通过离散数学考试。 C. 因为我平时不认真学习,所以我没有通过离散数学考试。 D. 我通过离散数学考试仅当我平时认真学习。 2.命题公式P→(P∨Q∨R) 为()。 A.重言式B.可满足式C.矛盾式D.等值式 3.设集合A={c, {c}},下列命题错误的是()。 A. {c}∈P(A) B. {c}?P(A) C. {{c}}∈P(A) D. {{c}}?P(A) 4. 设f: N N, f(x)=(x) mod 5, 即x除以5的余数,则函数f (). A. 仅单射 B. 仅满射 C. 双射 D. 既不单设也不满射 5.下列命题中正确的结论是:() A.集合上A的关系如果不是自反的,就一定是反自反的; B.集合上A的关系如果不是对称的,就一定是反对称的; C.在任意关系R上,若∈R,则必有∈R; D.非空集合A上的恒等关系既是等价关系又是偏序关系 6. 设集合A={a, b, c},A上的关系R={, },则下列结论错误的是:() A.R-1 = {, }; B. r(R) = R; C.s(R) = {, , , }; D. t(R) = R

相关主题
文本预览
相关文档 最新文档