2017华科离散数学离线作业

2017华科离散数学离线作业篇一

离散数学作业3_4

离散数学作业3

离散数学集合论部分形成性考核书面作业

本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。

一、填空题

1．设集合A{1,2,3},B{1,2}，则P(A)-P(B ，A B．

2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，

R{x,yxA且yB且x,yAB}

则R的有序对集合为 ．

4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}， A到B的二元关系

R＝{x,yy2x,xA,yB}

那么R1＝

－

5．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R具有的性质是．

6．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R中再增加两个元素 ，则新得到的关系就具有对称性．

7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 个．

8．设A={1, 2}上的二元关系为R={<x, y>|xA，yA, x+y =10}，则R的自反闭包为． 9．设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含等元素．

10．设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是 ．

二、判断说明题（判断下列各题，并说明理由．）

1．若集合A = {1，2，3}上的二元关系R={<1, 1>，<2, 2>，<1, 2>}，则 (1) R是自反的关系； (2) R是对称的关系．

2．如果R1和R2是A上的自反关系，判断结论：“R11、R1∪R2、R1∩R2是自反的” 是否成立？并说明理由．

-

3．若偏序集<A，R>的哈斯图如图一所示，

a

c g

 h

f 图一

则集合A的最大元为a，最小元不存在．

b d e

4．设集合A={1, 2, 3, 4}，B={2, 4, 6, 8}，，判断下列关系f是否构成函数f：AB，并说明理由．

(1) f={<1, 4>, <2, 2,>, <4, 6>, <1, 8>}； (2)f={<1, 6>, <3, 4>, <2, 2>}；

(3) f={<1, 8>, <2, 6>, <3, 4>, <4, 2,>}．

三、计算题

1．设E{1,2,3,4,5},A{1,4},B{1,2,5},C{2,4}，求： (1) (AB)~C； (2) (AB)- (BA) (3) P(A)－P(C)； (4) AB．

2．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算

（1）（AB）； （2）（A∩B）； （3）A×B．{2017华科离散数学离线作业}.

3．设A={1，2，3，4，5}，R={<x，y>|xA，yA且x+y4}，S={<x，y>|xA，yA且x+y<0}，试求R，S，RS，SR，R-1，S-1，r(S)，s(R)．

4．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}．

(1) 写出关系R的表示式； (2 )画出关系R的哈斯图；

(3) 求出集合B的最大元、最小元．

四、证明题

1．试证明集合等式：A (BC)=(AB)  (AC)．

2．试证明集合等式A (BC)=(AB)  (AC)．

3．对任意三个集合A, B和C，试证明：若AB = AC，且A，则B = C．

4．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．

2017华科离散数学离线作业篇二

华中科技大学2013——2014年《离散数学》试卷A卷

计算机学院2013—2014学年《离散数学》考试试卷

A卷 闭卷 考试时间： 年 月 日

专业 班级 学号 学生姓名

一. 单项选择题。（每小题2分，总共20分）

(1)

集合A={a，b，{a}，{c}}，那么下列描述错误的是（ ）： A aA ； B {b}A ； C {a}A ； D cA

(2) A={0，1} B={1，2} ，下列哪一项不属于A×B （ ） A （0，1） ； B （0，2）； C （1，0） ； D （1，1）

(3) 下列集合不能构成函数的为 ( ):

A { ( 1, ( 2 , 3 ) ), ( 2 , ( 3 , 4 ) ) , ( 3 , ( 1 , 4 ) ) , ( 4 , ( 1 , 4 ) ) B { ( 1, ( 2 , 3 ) ), ( 2 , ( 3 , 4 ) ) , ( 3 , ( 3 , 2 ) ) } C { ( 1, ( 2 , 3 ) ), ( 2 , ( 3 , 4 ) ) , ( 1 , ( 2 , 4 ) ) } D { ( 1, ( 2 , 3 ) ),

( 2 , ( 2 , 3 ) ) , ( 3 , ( 2 , 3 ) ) }

(4) 设图G（V、E）为一二部图，则其中的回路长度为（ ）

A．奇数长

B．偶数长 C．要视具体回路而定

D．不能确定

(5)

设有函数f：RR、f(x)=x2

-4，则f是（ ）

A．内射、非满射 B．满射、非内射

C．非内射、非满射

D．双射{2017华科离散数学离线作业}.{2017华科离散数学离线作业}.

(6)

n 阶完全图Kn= (n,m)中m=( )

}

A, n (n-1) B, n(n+1) C, n(n-1)/2 D, n(n+1)/2

(7)

从一点出发走完所有的边且仅一次,又回到原来的出发点,这样的路为( ) A 欧拉路 B 欧拉回路 C哈密尔顿路 D 哈密尔顿回路

(8)

图G如下图，则G是（ ）

A．欧拉图 非哈密顿图 B．哈密顿图 非欧拉图 C．非欧拉图 非哈密顿图 D．欧拉图且哈密顿图

(9)

下列语句是命题的（ ）

D．火星上有生命

A．好大的雪啊！ B．x+y>6 C．请关门 (10) 与P←→Q等价的命题公式为( );

A (P→Q)∨(Q→P) ； B (P∧Q)∨(┐P∧┐Q) ； C (P∧Q) ∧(┐P∧┐Q) ； D (P∨Q)∧(┐P∨┐Q)

(1)

二. 填空题 (每个空2分，共10分)

y,使用u和v对谓词公式 x(P(x, y)   y Q(x, z))  S(x, z) 中的约束变元x和y

进行改名，得到结果是( ）。 已知集合A有3个元素，则集合A上最多定义（ ）个等价关系。 某复合函数f·g为一双射函数，则f为（ ）射。

已知连通平面图G=(n,m,k) 中，边数m=9 , 点数n=6, 那么该图G具有( )个有限面。

(2) (3) (4)

(5) 已经满二元树根节点为0级节点，最高级节点为5级节点，则该树总共有（ ）个节点。

(1)

三. 计算与解答题(每一个题目8分,共40分)

使用全总个体域对下列命题符号化。（8分）

a) 有些人聪明，但并非所有的人都聪明；

b) 对任意实数，存在更大的实数；但并不存在比任意实数都更大的实数； (2)

判断蕴含式P→(Q→R) =>(P→Q)→(P→R)是否成立，并写出解题过程。(8分)

(3)

已知集合A={0,1,2,3}，定义A上的关系ρ

1

和ρ2，

其中ρ1={(i ,j)|j=i+1或j=i/2 } , ρ2={ (i ,j)|i=j+2}。

 求出复合关系ρ1•ρ 求t(ρ1)。（4分）

2

（4分）

(4)

设有函数f：A→B，定义函数g：B→2A，使得

g(b)={a|a∈A，f(a)=b}，

试证明如果f满射，则g内射；反之，如果g内射，f是否一定满射？ (5)

判断图G1和G2是否是平面图,列出解题过程.(8分)

8分）（

G1

G2

2017华科离散数学离线作业篇三

华中科技大学2013——2014年《离散数学》试卷B卷

计算机学院2013—2014学年《离散数学》考试试卷

B卷 闭卷 考试时间： 2013 年 11 月 26 日

专业 班级 学号 学生姓名

一. 单项选择题。（每小题2分，总共20分）

(1)

设A＝{Φ, {Φ } } ，B ＝ 2A

，则下列选项错误的是（ ） A．Φ∈B

B．{Φ }∈B

C．{ {Φ } } B

D．{{Φ, {Φ } }}∈B

(2)

设有某复合函数，g·f为一双射函数，则f、g分别为（ ） A．内射、满射 B．满射、内射C．内射、内射 D．满射、满射

(3) 下列集合不能构成函数的为 ( ):

A { ( 1, ( 2 , 3 ) ), ( 2 , ( 3 , 4 ) ) , ( 3 , ( 1 , 4 ) ) , ( 4 , ( 1 , 4 ) ) B { ( 1, ( 2 , 3 ) ), ( 2 , ( 3 , 4 ) ) , ( 3 , ( 3 , 2 ) ) } C { ( 1, ( 2 , 3 ) ),

( 2 , ( 3 , 4 ) ) , ( 1 , ( 2 , 4 ) ) } D { ( 1, ( 2 , 3 ) ), ( 2 , ( 2 , 3 ) ) , ( 3 , ( 2 , 3 ) ) }

(4) 设集合A、B为有限集，且#A=m，#B=n，则A到B的二元关系顶多为（A．m·n

B．2m

·n

C．(2m)2n

D．2m+n

(5){2017华科离散数学离线作业}.

设有函数f：RR、f(x)=x2

-4，则f是（ ）

A．内射、非满射 B．满射、非内射

C．非内射、非满射

D．双射

） }

(6) n 阶完全图Kn= (n,m)中m=( )

A, n (n-1) B, n(n+1) C, n(n-1)/2 D, n(n+1)/2

(7) 从一点出发走完所有的边且仅一次,又回到原来的出发点,这样的路为( ) A 欧拉路 B 欧拉回路 C哈密尔顿路 D 哈密尔顿回路

(8) 图G如下图，则G是（ ）

A．欧拉图 非哈密顿图 B．哈密顿图 非欧拉图 C．非欧拉图 非哈密顿图

D．欧拉图且哈密顿图

(9)

)（ ） 谓词公式xF(x)F(y是

A．永真公式

B．矛盾式

C．可满足公式 D．不能确定公式类型

(10) 设P、Q是命题变元，则 P →（P∨Q）的类型（ ）

A．不是命题公式 C．是永假公式

B．是永真公式 D．是可满足公式

(1) (2)

二. 填空题 (每个空2分，共10分)

已知集合A有10个元素，则集合A上最多定义（ ）个等价关系。 若f: A→B是内射,那么#A（ ）#B。

(3) (4)

已知平面连通图G（6，11），则其所围成的面为（ ）个.。

已经满二元树根节点为0级节点，最高级节点为3级节点，则该树总共有（ ）个节点。

(5) 请用P→Q 代换命题公式 (P∨(P∧Q))→Q 中的Q得

（ ） (1)

三. 计算与解答题(每一个题目8分,共40分)

已知G（V、E、f）为一带权图如下，试求其最小生成树，并写出最小生成树的权值。（8分）

(2)

(3)

判断┐(P↔Q) ↔ (┐P↔Q)是永真,永假还是可满足式，写出解题过程。(8分)

已知集合A={0,1,2,3}，定义A上的关系ρ

1

和ρ2，

其中ρ1={(i ,j)|j=i+1或i=j+1 } , ρ2={ (i ,j)|i=j+2}。

 求出复合关系ρ1•ρ 列出复合关系ρ2•ρ

2 1

（4分）

的关系矩阵。（4分）

(4) 现有函数f：A→B和g：B→C都是可逆的，求函数复合运算gf的逆函数表

达式，并列出解题过程。（8分）

(5)

使用全总个体域将下列命题符号化（8分）

a) 如果一个人长期吸烟或酗酒，那么他身体绝不会健康； b) 对任何整数x，y，如果xy=0，则x=0或y=0；

2017华科离散数学离线作业篇四

离散数学课件作业_7

离散数学课件作业

第一部分 集合论

第一章 集合的基本概念和运算

1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是 [ ]

A．2 ∈A； B．1 ∈ A； C．5 ∈A； D．{2}  A。

1-2 A,B 为任意集合，则他们的共同子集是 [ ]

A．A； B．B； C．A∪B； D． Ø 。

1-3 设 S = {N，Z，Q，R}，判断下列命题是否成立 ？

（1） N  Q，Q ∈S，则 N  S ［ ］

（2）-1 ∈Z，Z ∈S， 则 -1 ∈S ［ ］

1-4 设集合 A ={3，4}，B = {4，3} ∩ Ø ， C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，

E = {x│x ∈R 并且 x2 - 7x + 12 = 0}，F = { 4，Ø ，3，3}，

试问哪两个集合之间可用等号表示 ？

1-5 用列元法表示下列集合

（1）A = { x│x ∈N 且 x2 ≤ 9 }

（2）A = { x│x ∈N 且 3－x 〈 3 }

第二章 二元关系

2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：

R = {〈x，y〉x，y ∈X 且 x ＜ y }

求：(1)domR =?; (2)ranR =?; (3)R 的性质。

2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即

R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}，试求：

（1）R 的列元表达式； （2）给出 dom（R 。R）。

2-3 判断下列映射 f 是否是 A 到 B 的函数；并对其中的 f：A→B 指出他的性质，即是否单射、

满射和双射，并说明为什么。

（1）A = {1，2，3}，B = {4，5}， f = {〈1，4〉〈2，4〉〈3，5〉}。

（2）A = {1，2，3} = B， f = {〈1，1〉〈2，2〉〈3，3〉}。

（3）A = B = R， f = x 。

（4）A = B = N， f = x2 。

（5）A = B = N， f = x + 1 。

2-4 设 A ={1，2，3，4}，A 上的二元关系

R ={〈x，y〉︱（x-y）能被3整除}，则自然映射 g：A→A/R使 g(1) = [ ]

A．｛1,2｝； B．｛1,3｝； C．｛1,4｝； D．｛1｝。

2-5 设 A ={1，2，3}，则商集A/IA = [ ]

A．｛3｝； B．｛2｝； C．｛1｝； D．｛｛1｝，｛2｝，｛3｝｝ 。

2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝ [ ]

A．x+1； B．x-1； C．x； D．x2。

第三章 结构代数(群论初步)

3-1 给出集合及二元运算，阐述是否代数系统，何种代数系统 ？

（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 * 是普通乘法。

（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；

二元运算 。定义如下：对于所有 ai，aj ∈S2，都有 ai 。aj = ai 。

（3）S3 = {0，1}，二元运算 * 是普通乘法。

3-2 在自然数集合上，下列那种运算是可结合的 ［ ］

A．x*y = max(x,y) ； B．x*y = 2x+y ；

C．x*y = x2+y2 ； D．x*y =︱x-y︱..

3-3 设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y ∈Z 都有

x 。y = x + y ，

试问〈Z，。〉能否构成群，为什麽 ？

第二部分 图论方法

第四章 图

4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个偶数度顶点 ？

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点. [ ]{2017华科离散数学离线作业}.

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为 [ ]

第五章 树

5-1 握手定理的应用（指无向树）

（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有( )个？

（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有( )片？

5-2 一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶(即一度顶点)，问树叶多少

片？设有x片,则 x=

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1）

T 的权 W（T）？ （2）树高几层 ？

5-4 以下给出的符号串集合中，那些是前缀码？将结果填入[ ]内.

B1 = {0，10，110，1111} [ ]

B2 = {1，01，001，000} [ ]

B3 = {a，b，c，aa，ac，aba，abb，abc} [ ]

B4 = {1，11，101，001，0011} [ ]

5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 [ ]

5-6(是非判断题)二元正则树有奇数个顶点。 [ ]

5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%.

求传输他们的最佳前缀码。

1、最优二元树 T； 2.每个字母的码字；

第三部分 逻辑推理理论

第六章 命题逻辑

6-1 判断下列语句是否命题，简单命题或复合命题。

（1）2月 17 号新学期开始。 [ ]

（2）离散数学很重要。 [ ]

（3）离散数学难学吗 ？ [ ]

（4）C 语言具有高级语言的简洁性和汇编语言的灵活性。 [ ]

（5）x + 5 大于 2 。 [ ]

（6）今天没有下雨，也没有太阳，是阴天。 [ ]

6-2 将下列命题符号化.

（1）2 是偶素数。

（2）小李不是不聪明，而是不好学。

（3）明天考试英语或考数学。（兼容或）

（4）你明天不去上海，就去北京。（排斥或）

6-3 分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型.

（1）﹃（p→q）∧ q； （2）（（p→q）∧ p）→q； （3）（p→q）∧ q。

以下两题(6-4;6-5)为选择题,将正确者填入[ ]内.

6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为 [ ]

A． p→q； B． q→p； C． p∧q； D． ﹁q→﹁p

6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为 ［ ］

A． p→q； B． q→p； C． p∧q； D． ﹁q→p

6-6 证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。

如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。

第七章 谓词逻辑

7-1 在谓词逻辑中用 0 元谓词将下列命题符号化

（1）这台机器不能用。

（2）如果 2 ＞ 3，则 2 ＞ 5。

7-2 填空补缺题：设域为整数集合Ｚ，命题xy彐z（x-y=z）的真值为 （ ）

7-3 在谓词逻辑中将下列命题符号化

（1）有的马比所有的牛跑得慢。

（2）人固有一死。

《附录》习题符号集

Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 , － 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非，量词 ”所有”，”每个”，∨结词，∧ 合取联结词，彐 量词”存在”，”有的”。

年2月20号。 析取联 2010