2015春课件作业
第一部分集合论
第一章集合的基本概念和运算
1-1 设集合 A ={{2,3,4},5,1},下面命题为真是(选择题) [ C ] A.1 ∈A; B.2 ∈ A; C.3 ∈A; D.{3,2,1} ? A。
1-2 A,B,C 为任意集合,则他们的共同子集是(选择题) [ D ] A.C; B.A; C.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 设集合 B = {4,3} ∩?, C = {4,3} ∩{ ? },D ={ 3,4,? },
E = {x│x ∈R 并且 x2 - 7x + 12 = 0},
F = { 4,?,3,3},
试问:集合 B 与那个集合之间可用等号表示(选择题) [ A ]
A. C;
B. D;
C. E;
D. F.
1-5 用列元法表示下列集合:A = { x│x ∈N 且 3-x 〈 3 }(选择题) [ D ]
A. N;
B. Z;
C. Q;
D. Z+
1-6 为何说集合的确定具有任意性 ? (简答题)
第二章二元关系
2-1 给定 X =(3, 2,1),R 是 X 上的二元关系,其表达式如下:
R = {〈x,y〉x,y ∈X 且 x > y } (综合题)求:(1)domR =?; (2)ranR =?; (3)R 的性质。
R={<2,3>,<1,2>,<1,3>}∪Ix;
(1)DomR={R中所有有序对的x}={3,2,1};
(2)RanR={R中所有有序对的y}={3,2,1};
(3)(3)R的性质:自反,反对称,传递性质.
2-2 设 R 是正整数集合上的关系,由方程 x + 3y = 12 决定,即
R = {〈x,y〉│x,y ∈Z+ 且 x + 3y = 12},
试给出 dom(R 。R)。(选择题) [ B ]
A. 3;
B. {3};
C. 〈3,3〉;
D.{〈3,3〉}。
2-3 判断下列映射 f 是否是 A 到 B 的函数;以及函数的性质。最后指出 f:A→B 中的双射函数。(选择题) [ 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 。
A.(1)和(2);
B.(2)和(3);
C.(3)和(4);
D.(4)和(5)
2-4 设f(x)=x+1,g(x)=x-1 都是从实数集合R到R的函数,则f。g=[ C ] A.x+1;B.x-1;C.x;D.x2。
2-5 关系型数据库与《关系与函数》一章内容有何联系?(简答题)
答:关系数据库,是建立在关系模型基础上的数据库,借助于集合代数和各种函数关系等数
学概念和方法来处理数据库中的数据,现实世界中的各种实体以及实体之间的各种联系均用
关系模型来表示。
第三章结构代数(群论初步) (3-1),(3-2)为选择题
3-1 给出集合及二元运算,判断是否代数系统,何种代数系统?
(1)S1 = {1,1/4,1/3,1/2,2,3,4},二元运算 * 是普通乘法。 [ A ] A.不构成代数系统;B.只是代数系统。;C.半群;D.群。
(2)S2 = {a1,a2,……,an},ai ∈R,i = 1,2,……,n ;
二元运算。定义如下:对于所有 ai,aj ∈S2,都有 ai 。aj = ai 。 [ C ]
A.不构成代数系统;B.只是代数系统。;C.半群;D.群。
(3)S3 = {0,1},二元运算 * 是普通乘法。 [ C ] A.不能构成代数系统;B.半群;C.独异点;D.群。
3-2 在自然数集合上,下列那种运算是可结合的[ A ]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 上二元运算。能否构成代数系统,何种代数系统?为什麽?(综合题)
假设代数系统的幺元是集合中的元素e,则一个方程来自于二元运算定义,
即e。x=e+x-4,
一个方程来自该特殊元素的定义的性质,
即e。x=x.由此而来的两个方程联立结果就有:e+x=x成立.
设y是x的逆,则一个方程为y。
x=y+x-4,另一个方程为y。x=4,
联立结果得到y=8-x;
结论是:代数系统〈Z,。〉构成群。
第二部分图论方法
第四章图以下三题分别为:选择题是非题填空题
4-1 10 个顶点的简单图G中有4个奇度顶点,问 G 的补图中有 r 个偶数度顶点。[ C ] A.r =10 ;B.r = 6;C.r = 4;D.r = 9。
4-2 是非判断:无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点。[ 是 ]
4-3 填空补缺:1条边的图 G 中,所有顶点的度数之和为 2 。
第五章树
5-1 概述无向图与无向树的关系。(简答题)
答:连通而不含回路的无向图称谓无向树。(1)生成树的定义--生成子图概念;(2)生成子图与母图的关系--定点数相同;(3)何种图采用生成树--连通图;(4)连通图中的那种永远不会进入任何一颗生成树中--环;(5)连通图中的那种边必然会进入其生成树中--桥。
5-2 握手定理的应用(指无向树)(计算题)
(1)在一棵树中有 7 片树叶,3个3 度顶点,其余都是4 度顶点,共几个顶点 [ 11 ] (2)一棵树有两个 4 度顶点,3 个 3 度顶点,其余都是树叶,问有几片叶 [ 9 ]
5-3 求最优 2 元树:用 Huffman 算法求带权为 1,2,3,5,7,8 的最优 2 元树 T。
试问:T 的权 W(T)= ( 61 );树高 ( 4 ) 层。(填空题)
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,f,g,h 出现的频率分别为 25%;20%;20%.15%,10%,5%,4%,1%;
试完成下列要求。(综合题)
1、最优二元树 T;
2、二元树的权 W(T)= ;
3、每个字母的码字;
。100
60。
30。。a 。40
15。。c
10。。。20 。b
。。 f 。。
g h d e
编码如下:g(00000),h(00001),f(0001),d(100),e(101),c(001),b(11),a(01)。
第三部分逻辑推理理论
第六章命题逻辑
6-1 判断下列语句是否命题,简单命题或复合命题。(填空题)
(1)2月 17 号新学期开始。(是简单)命题
(2)离散数学很重要。(是简单)命题(3)离散数学难学吗?(不是)命题
(4)C 语言具有高级语言的简洁性和汇编语言的灵活性(是复合)命题(5)x + 5 > 2 。(不是)命题
(6)今天没有下雨,也没有太阳,是阴天。(是复合)命题
6-2 将下列命题符号化. (填空题)(1)2 是偶素数。符号化为: p ∧ q。
(2)小李不是不聪明,而是不好学。符号化为:p ∧﹃q。
(3)明天考试英语或考数学。(兼容或)符号化为:p ∨ q。
6-3 用等值演算法求下列命题公式的主析取范式,并由此指出该公式的类型
(1)﹃(p→q)∧ q (计算题)
(2)((p→q)∧ p)→q (计算题)
(3)(p→q)∧ q (计算题)
(1)0,永假式;(2)Σ(0,1,2,3),永真式;(3)Σ(1,3),可满足式。
6-4 令p:经一堑;q:长一智。命题’’只有经一堑,才能长一智’’符号化为[ B ] A.p→q;B.q→p;C.p∧q;D.﹁q→﹁p
6-5p:天气好;q:我去游玩.命题”如果天气好,则我去游玩”符号化为[ A ]A.p→q;B.q→p;C.p∧q;D.﹁q→p
6-6 将下列推理命题符号化,然后用不同方法判断推理结果是否正确。(综合题)如果今天不下雨,则明天上体育课。今天没有下雨。所以,明天上体育课。
题解与分析:首先将原子命题符号化,然后,按题意将原子命题组织成公式。再用不同方法,例如用等值演算法判断推理的正确与否。公式是重言式,所以,推理正确。方法 1:等值演算法(略)
方法 2: 主范式法(略);
方法 3: 真值表法(略);
方法 4:构造证明法,如下:
(1)将原子命题符号化:
(2)按题意构成前提:
(3)按题意构成结论:
(4)证明:
方法 1:等值演算法((p→﹃q)∧p)→﹃q ﹤=﹥1;
方法 2: 主范式法(略);
方法 3: 真值表法(略);
方法 4:构造证明法,如下:
将公式分成前提及结论。
前提:(p→﹃q),p;
结论:﹃q;
证明:(1)(p→﹃q)前提引入
(2) p 前提引入
(3)(p→﹃q)∧p (1)(2)假言推理
(4)﹃q
所以推理正确。
第七章谓词逻辑
7-1 在谓词逻辑中用 0 元谓词将下列命题符号化(填空题)
(1)这台机器不能用。﹃F(a)。
(2)如果 2 > 3,则 2 > 5。 L(a,b)→ H(a,z)。(1)﹃F(a)。(2)L(a,b)→ H(a,z)。
7-2 填空题:设域为整数集合 Z+,命题?x?y彐z(x-y = z)的真值为 1
7-3 在谓词逻辑中将下列命题符号化(填空题)人固有一死。?x(M(x)→ F(x))。7-4 一阶逻辑与命题逻辑有何联系?举例说明。(简答题)
《附录》习题符号集
? 空集, ∪并, ∩交,⊕对称差,~绝对补,∑累加或主析取范式表达式缩写 ,
-普通减法, ÷普通除法, ㏑自然对数, ㏒对数,﹃非,?量词”所有”,”每个”,∨析取联结词,∧合取联结词,彐量词”存在”,”有的”。
答:把命题逻辑中的符号化的命题,把句子成分展示出来,并按句子成分符号化,就变成一阶逻辑中的公式了。例如:每个人都会死。命题逻辑中的P变成一阶逻
辑中的?x(M(x)→ F(x))。