离散数学课本习题教学内容Word格式.docx
- 文档编号:4053050
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:29
- 大小:82.33KB
离散数学课本习题教学内容Word格式.docx
《离散数学课本习题教学内容Word格式.docx》由会员分享,可在线阅读,更多相关《离散数学课本习题教学内容Word格式.docx(29页珍藏版)》请在冰点文库上搜索。
证明A=B。
习题1.2
1.设U={1,2,3,4,5},A={1,4},B={1,2,5},C={2,4}。
试求下列集合:
a)A⋂~B;
b)(A⋂B)⋃~C;
c)~(A⋂B);
d)~A⋃~B;
e)(A–B)–C;
f)A–(B–C);
g)(A⊕B)⊕C;
h)(A⊕B)⊕(B⊕C)
2.设A={n|n∈I+且n<
12},B={n|n∈I+且n≤8},C={2n|n∈I+},D={3n|n∈I+}且E={2n-1|n∈I+}试用A,B,C,D和E表达下列集合:
a){2,4,6,8};
b){3,6,9};
c){10};
d){n|n为偶数且n>
10};
e){n|n为正偶数且n≤10,或n为奇数且n≥9}。
3.证明:
a)如果A⊆B且C⊆D,则A⋃C⊆B⋃D且A⋂C⊆B⋂D;
b)A⋂(B-A)=∅;
c)A⋃(B-A)=A⋃B;
d)A–(B⋃C)=(A–B)⋂(A–C);
e)A–(B⋂C)=(A–B)⋃(A–C);
f)A–(A–B)=A⋂B;
g)A-(B-C)=(A-B)⋃(A⋂C)。
4.证明
a)A=B当且仅当A⊕B=∅;
b)A⊕B=B⊕A;
c)(A⊕B)⊕C=A⊕(B⊕C);
d)A⋂(B⊕C)=(A⋂B)⊕(A⋂C);
e)(B⊕C)⋂A=(B⋂A)⊕(C⋂A)。
5.判断一下结论是否成立,如果或成立,就给予证明,如果不成立,就用文氏图加以说明。
a)若A⋂C⊆B⋂C且A⋂~C⊆B⋂~C,则A⊆B;
b)若A⋂B=A⋂C且~A⋂B=~A⋂C,则B=C;
c)若A⋃B=A⋃C,则B=C;
d)若A⋂B=A⋂C,则B=C;
e)A⊕B=A⊕C,则B=C;
f)若A⊆B⋃C,则A⊆B或A⊆C;
g)若B⋂C⊆A,则B⊆A或C⊆A。
6.给出下列各式成立的充分必要条件,并加以证明。
a)(A-B)⋃(A-C)=A;
b)(A-B)⋃(A-C)=∅;
c)(A-B)⋂(A-C)=A;
d)(A-B)⋂(A-C)=A;
e)(A-B)⊕(A-C)=A;
f)(A-B)⊕(A-C)=∅;
g)A⋂B=A⋃B;
h)A-B=B;
i)A-B=B-A;
j)A⊕B=A;
k)℘(A)⋃℘(B)=℘(A⋃B);
7.设A,B为任意两个集合,证明:
a)℘(A)⋃℘(B)⊆℘(A⋃B);
b)℘(A)⋂℘(B)=℘(A⋂B)。
8.试求出⋃℘和⋂℘,其中℘为:
a){{∅}};
b){∅,{∅}};
c){{a},{b},{a,b}}。
9.设
且
,
。
证明
10.设
,试求
和
11.设
试求
12.设
,我们称
分别为集合序列
的上极限和下极限,证明:
a)
为由一切属于无限多个
的元素组成的集合;
b)
为由一切属于“几乎所有”的
的元素组成的集合。
习题1.3
1、用归纳法证明:
;
b)2+22+23+…+2n=2n+1-2;
c)2n=2n;
d)3|n3+2n;
e)1·
2·
3+2·
3·
4+…+n(n+1)(n+2)=
f)任意三个相邻整数的立方和能被9整除;
g)11n+2+122n+1是133的倍数;
h)若n∈I+则
2、设a0,a1,a2,…为由自然数组成的严格单调递增序列。
证明:
若n∈N,则n≤an。
3、斐波那契(Fibonacci)数列定义为
F0=0
F1=1
Fn+1=Fn+Fn-1,n∈I+
若n∈I+,则
4、设n,m∈I+且n>m。
假定有n个直立的大头针,甲、乙两人轮流把这些直立的大头针扳倒。
规定每人每次可扳倒1至
根,且扳倒最后一根直立的大头针者为获胜者。
试证明:
如果甲先扳且(m+n)不能整除n,则甲总能获胜。
5、证明以下的二重归纳原理的正确性:
设i0,j0∈N。
假定对任意自然数i≥i0及j≥j0,皆有一个命题P(i,j)满足:
i)P(i0,j0)真;
ii)对任意自然数k≥i0及l≥j0,若P(k,l)真,则P(k+1,l)和P(k,l+1)皆真。
则对任意自然数i≥i0及j≥j0,P(i,j)皆真。
6、证明:
若n∈N,则n∉n。
7、证明:
若n,m∈N,则n⊂m当且仅当n∈m。
8、证明:
若n,m∈N,则n∈m当且仅当n+∈m+。
9、证明:
若n,m∈N,则n<m当且仅当有x∈N使m=n+x+。
10、证明:
若n∈N,则不可能有m∈N使n<m<n+。
习题1.4
1、设A={0,1},B={1,2}。
试确定下列集合:
a)A×
{1}×
B
b)A2×
c)(B×
A)2
2、证明或用反例推翻下列命题:
a)(A∪B)×
(C∪D)=(A×
C)∪(B×
D)
b)(A∩B)×
(C∩D)=(A×
C)∩(B×
D)
c)(A-B)×
(C-D)=(A×
C)-(B×
d)(A⊕B)×
(C⊕D)=(A×
C)
(B×
3、如果B∪C⊆A,则(A×
B)-(C×
D)=(A-C)×
(B-D)。
这个命题对吗?
如果对,则给予证明;
如果不对,则举出反例。
f)4、证明:
若x∈C且y∈C,则<
x,y>
∈℘(℘(C))。
5、证明:
a∈∪<
a,b>
且b∈∪<
6、把三元偶<
a,b,c>
定义为{{a},{a,b},{a,b,c}}合适吗?
说明理由。
7、为了给出序偶的另一定义,选取两个不同集合A和B(例如取A=∅,B={∅}),并定义<
={{a,A},{b,B}}。
证明这个定义的合理性。
第二章二元关系
习题2.1
1、列出从A到B的关系R中的所有序偶。
a)A={0,1,2},B={0,2,4},R={<
|x,y∈A∩B}
b)A={1,2,3,4,5},B={1,2,3},R={<
|x∈A,y∈B且x=y2}
2、设R1和R2都是从{1,2,3,4}到{2,3,4}的二元关系,并且
R1={<
1,2>
<
2,4>
3,3>
}
R2={<
1,3>
4,2>
求R1∪R2,R1∩R2,domR1,domR2,ranR1,ranR2,dom(R1∪R2)和ran(R1∪R2)。
3、设
都是从集合
到集合
的二元关系。
证明
dom(R1∪R2)=domR1∪domR2
ran(R1∩R2)⊆ranR1∩ranR2
4、用L和D分别表示集合{1,2,3,6}上的普通的小于关系和整除关系,试列出L,D和L∩D中的所有序偶。
5、给出满足下列要求的二元关系的实例:
a)既是自反的,又是反自反的;
b)既不是自反的,又不是反自反的;
c)既是对称的,又是反对称的;
d)既不是对称的,又不是反对称的。
6、试判断下面的论断正确与否。
若正确,请加以证明;
若不正确,请给出反例。
设R和S都是集合A上的二元关系。
若R和S都是自反的(反自反的,对称的,反对称的,或传递的),则R∩S,R∪S,R-S,R⊕S也是自反的(反自反的,对称的,反对称的,或传递的)。
7、描述R上的下列二元关系S的性质:
a)S={<
|x,y∈R且x·
y>0};
b)S={<
|x,y∈R,4整除|x-y|且|x-y|<10};
c)S={<
|x,y∈R,x2=1且y>0};
d)S={<
|x,y∈R,4|x|≤1且|y|≥1}。
8、设n,m∈I+。
若集合A恰有n个元素,则在A上能有多少个不同的m元关系?
证明你的结论。
9、设ξ和ζ都是由从集合A到集合B的二元关系构成的集类,并且ζ
∅。
a)dom(∪ξ)=∪{domR|R∈ξ};
b)ran(∪ξ)=∪{ranR|R∈ξ};
c)dom(∩ζ)⊆∩{domR|R∈ζ};
d)ran(∩ζ)⊆∩{ranR|R∈ζ};
10、设R为集合
上的一个二元关系。
如果R是反自反的和传递的,则R一定是反对称的。
11、设R为集合
上的一个二元关系,若令fldR=domR∪ranR则fldR=∪(∪R)。
12、若R为集合
上的一个二元关系,则
也是∪(∪R)上的二元关系。
习题2.2
1.设集合A={1,2,3,4,5,6}上的二元关系R为
R={<
1,1>
2,2>
3,3>
4,4>
5,5>
6,6>
1,2>
2,1>
1,3>
3,1>
2,3>
3,2>
4,5>
5,4>
}
试画出R的关系图GR,求出R的关系矩阵MR,并指出R所具有的性质。
2.对图2.2.3给出的集合A={1,2,3}上的十二个二元关系的关系图,写出相应的关系矩阵,并指出各个关系所具有的性质。
3.对习题2.1种第4题所给的二元关系L,D和L⋂D,画出它们的关系图,并写出它们的关系矩阵。
4.设A为恰有n个元素的有限集。
a)共有多少个A上的不相同的自反关系?
a)共有多少个A上的不相同的反自反关系?
b)共有多少个A上的不相同的对称关系?
c)共有多少个A上的不相同的反对称关系?
d)共有多少个A上的不相同的既是对称又反对称的关系?
习题2.3
1.设R为非空有限集A上的二元关系。
如果R是反对称的,则R⋂R-1的关系矩阵MR⋂R-1中最多能有多少个元素为1?
2.设R为集合A上的二元关系,则R⋃R-1为A上包含R的最小对称关系,R⋂R-1为A上的包含在R中的最大对称关系。
3.设IA为集合A上的恒等关系,即IA={<
x,x>
|x∈A}。
则对A上的任意二元关系R,A上的二元关系IA⋃R⋃R-1必是自反的和对称的。
4.设R为任意的二元关系。
a)domR-1=ranR;
b)ranR-1=domR。
习题2.4
1、设集合{a,b,c,d}上的二元关系R1和R2为R1={<
a,a>
b,d>
};
a,d>
b,c>
c,b>
}。
试求R2oR1,R1oR2,
及
3、若R为任意集合
上的空关系或全关系,则R2=R。
4、举出使R1o(R2∩R3)⊂(R1oR2)∩(R1oR3),(R2∩R3)oR4⊂(R2oR4)∩(R3oR4)
成立的二元关系R1,R2,R3和R4的实例。
5、设R1和R2都是集合A上的二元关系。
证明或用反例推翻以下的论断:
a)如果R1和R2都是自反的,则R1oR2也是自反的;
b)如果R1和R2都是反自反的,则R1oR2也是反自反的;
c)如果R1和R2都是对称的,则R1oR2也是对称的;
d)如果R1和R2都是传递的,则R1oR2也是传递的;
6、设A={0,1,2,3}上的二元关系R1和R2为R1={<
i,j>
|j=i+1或j=i/2};
i,j>
|i=j+2};
8、设R为集合A上的二元关系,s,t
N,s<
t且Rs=Rt。
a)若k∈N,则Rs+k=Rt+k;
b)若k,i∈N,则Rs+kp+i=Rs+i;
c)若k∈N,则Rk
{R0,R1,…,Rt-1}。
其中p=t-s。
9、设IA为集合A上的恒等关系,R为A上的任意二元关系。
a)R是自反的,当且仅当IA⊆R;
b)R是反自反的,当且仅当R∩IA=∅;
c)R是对称的,当且仅当R=R-1;
d)R是反对称的,当且仅当R⋂R-1=IA;
e)R是传递的,当且仅当RoR⊆IA。
10、如果集合A上的二元关系R既是自反的,又是传递的,则R2=R。
11、设R1为从集合A到集合B的二元关系,R2为从集合B到集合C的二元关系。
试求dom(R1oR2)和ran(R1oR2)。
12、设R为从集合A到集合B的二元关系,且对每个X⊆A,皆令R(X)={y∈B|有x∈X使<x,y>∈R}。
若X1⊆A且X2⊆A,则有
i)R(X1∪X2)=R(X1)∪R(X2);
ii)R(X1∩X2)⊆R(X1)∩R(X2);
iii)R(X1﹨X2)⊇R(X1)﹨R(X2);
13、设R1为从集合A到集合B的二元关系,R2为从集合B到集合C的二元关系。
若X⊆A,则(R1oR2)(X)=R2(R1(X))。
习题2.5
2、设R1和R2都是集合A上的二元关系,试证明:
a)r(R1∪R2)=r(R1)∪r(R2);
b)s(R1∪R2)=s(R1)∪s(R2);
c)t(R1∪R2)⊇t(R1)∪t(R2)。
4、设R1和R2都是集合A上的二元关系,试证明:
a)r(R1∩R2)=r(R1)∩r(R2);
b)s(R1∩R2)⊆s(R1)∩s(R2);
c)t(R1∩R2)⊆t(R1)∩t(R2)。
并分别给出使s(R1)∩s(R2)⊆s(R1∩R2)和t(R1)∩t(R2)⊆t(R1∩R2)不成立的R1和R2的具体实例。
6、给出一个二元关系R使st(R)≠ts(R)。
7、设R为集合A上的二元关系,试证明:
a)RoR*=R+=R*oR;
b)(R+)+=R+;
c)(R*)*=R*;
习题2.6
1、设R1和R2都是集合A上的相容关系。
证明或用反例推翻下列命题:
a)R1∩R2是A上的相容关系;
b)R1∪R2是A上的相容关系;
c)R1-R2是A上的相容关系;
d)R1⊕R2是A上的相容关系;
e)R1oR2是A上的相容关系;
f)
是A上的相容关系;
3、如果A为恰含n个元素的有限集,则A上有多少个不同的相容关系?
习题2.7
1、试判断下列I上的二元关系是不是I上的等价关系,并说明理由。
a){<
|i,j∈I且i·
j>
0};
b){<
j≥0且i与j不同时为0};
c){<
|i,j∈I且i≤0};
d){<
|i,j∈∈I且i·
j≥0};
e){<
|i,j∈I且i|j};
f){<
|i,j∈I且有x∈I使10x≤i≤j≤10(x+1)};
g){<
|i,j∈I且|i-j|≤10};
h){<
|i,j∈I且有x,y∈I使10x≤i≤10(x+1)及10y≤j≤10(y+1)};
i){<
|i,j∈I且有x∈I使10x<
i<
10(x+1)};
2、有人说:
“如果集合A上的二元关系R是对称的和传递的,则R必是自反的”。
并给出了如下的证明:
如果<
∈R,则由R是对称的可知<
y,x>
∈R,从而由R是传递的得到<
x,x>
∈R和<
y,y>
R。
因此R是自反的。
请你想一想,他的看法和证明对吗?
为什么?
3、设集合A上的二元关系R是自反的。
证明R为等价关系的充要条件是:
若<
a,b>
a,c>
R,则<
b,c>
R.
4、如果集合A上的二元关系R满足:
y,z>
∈R,则<
z,x>
∈R。
就称R为循环的。
试证明集合A上的二元关系R为A上的等价关系,当且仅当R是自反的和循环的。
5、设R1和R2都是集合A上的等价关系。
试判断下列A上的二元关系是不是A上的等价关系,为什么?
a)A2-R1;
b)R1-R2;
c)
d)r(R1-R2);
e)R2oR1;
f)R1∪R2;
g)t(R1∪R2);
h)t(R1∩R2);
6、设∏1和∏2都是集合A的划分。
试判断下列集类是不是A的划分,为什么?
a)∏1∪∏2;
b)∏1∩∏2;
c)∏1-∏2;
d)(∏1∩(∏2-∏1))∪∏1;
7、如果R1和R2都是集合A上的等价关系,则R1=R2当且仅当A/R1=A/R2。
8、设∏1和∏2都是集合A的划分,若对每个S1∈∏1,皆有S2∈∏2使S1⊆S2,就称∏1和∏2的加细,记为∏1≤∏2且∏1≠∏2,就称∏1为∏2的真加细,并记为∏1<
∏2。
设R1和R2都是集合A上的等价关系,证明:
a)R1⊆R2当且仅当A/R1≤A/R2。
b)R1⊂R2当且仅当A/R1<A/R2。
9、设A和B都是非空集,{A1,A2,…,An}为A的划分。
试证明{A1∩B,A2∩B,…,An∩B}并不总是集合A∩B的划分。
10、若R为集合A上的等价关系,则称n(A/R)为R的秩。
如果i,j∈I+且集合A上的等价关系R1与R2的秩分别为i和j,则R1∩R2也A上的等价关系且max{i,j}≤n(A/(R1∩R2))≤i·
j。
11、设A为恰含n个元素的非空有限集,则有多少个不同的A上的等价关系?
其中秩为2的又有多少?
12、如果n,m∈I+,则I/≡n为/I≡m的加细当且仅当m|n。
习题2.8
2、画出下列集合上的整除关系的哈斯图。
a){1,2,3,4,6,8,12,24};
b){i|i∈I且1≤i≤14};
c){i|i∈I且5≤i≤20};
3、设R为集合A上的二元关系且S
A,证明或用反例推翻下述断言:
a)若R是A上的半序,则R|s是S上的半序;
b)若R是A上的拟序,则R|s是S上的拟序;
c)若R是A上的全序,则R|s是S上的全序;
d)若R是A上的良序,则R|s是S上的良序;
4、设R是集合A上的二元关系。
a)若R是A上的半序,当且仅当R∩R-1=IA且R=R*;
b)若R是A上的拟序,当且仅当R∩R-1=∅且R=R+;
a)半序关系的逆关系仍然是半序关系;
b)全序关系的逆关系仍然是全序关系;
c)良序关系的逆关系未必是良序关系;
7、举出满足下列条件的半序结构<
A,≤>
的实例。
a)<
为全序结构,且A的某些非空子集无最小元。
b)<
不是全序结构,且A的某些非空子集无最大元。
c)A的某些非空子集有下确界,但无最小元。
d)A的某些非空子集有上界,但无上确定界。
8、设<
为半序结构。
证明A的每个非空有限子集都至少有一个极小元和极大元。
9、设<
为全序结构。
证明A的每个非空有限子集都有一个最大元和最小元。
10、试判断下列定义在二维欧氏空间R×
R上的二元关系T是不是R×
R上的拟序,半序,全序和良序?
R×
R的每个有下界的非空子集(关于拟序或半序T)是否与下确界?
并给出证明。
a)若x1,x2,y1,y2∈R,则<
x1,y1>
T<
x2,y2>
当且仅当x1≤x2且y1≤y2;
b)若x1,x2,y1,y2∈R,则<
当且仅当x1≤x2;
c)若x1,x2,y1,y2∈R,则<
当且仅当x1<x2或者x1=x2且y1≤y2;
d)若x1,x2,y1,y2∈R,则<
x1,y1>
当且仅当x1<x2。
11、设R为集合S上的全序关系。
证明R和R-1同时为S上的良序,当且仅当S为有限集。
12、I+在上定义二元关系R如下:
nRm当且仅当f(n)<
f(m),或f(n)=f(m)且n≤m
其中f(n)表示n的不同素因子的个数。
证明<
I+,R>
为良序结构。
13、设S为集合且l⊆℘(S)。
证明在半序结<
℘(S),⊆>
中有
Supl=∪l;
infl=∩l。
14、设π为集合A的所有划分组成的集合,并在π上定义二元关系R如下:
对任意的∏1,∏2∈π,则∏1R∏2当且仅当∏1为∏2的加细。
证明R是上的半序。
第三章
习题3.1
1、下列关系中哪些是部分函数?
对于不是部分函数的关系,说明不能构成部分函数的原因。
x,y>
|x,y∈N且x+y<
|x,y∈R且y=x2};
|x,y∈R且y2=x}。
2、下列集合能定义部分函数吗?
如果能,试求出它们的定义域和值域。
1,<
>
2,<
3,4>
3,<
1,4>
4,<
2,4>
3、设A为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 课本 习题 教学内容