离散数学课本知识题.docx
《离散数学课本知识题.docx》由会员分享，可在线阅读，更多相关《离散数学课本知识题.docx（29页珍藏版）》请在冰点文库上搜索。
离散数学课本知识题
习题1.1
1、用列举法给出下列集合：
a）小于5的非负整数的集合；
b）10到20之间的素数的集合；
c）不超过65的12之正整数倍数的集合。
2、用命题法给出下列集合：
a）不超过100的自然数的集合；
b）Ev和Od；
c）10的整倍数的集合。
3、用归纳定义法给出下列集合：
a）允许有前0的十进制无符号整数的集合；
b）不允许有前0的十进制无符号整数的集合；
c）允许有前0和后0的有有限小数部分的十进制无符号实数的集合；
d）不允许有前0的十进制无符号偶数的集合；
e）Ev和Od；
f）集合{0，1，4，9，16，25，…}。
4、确定下列集合中哪些是相等的：
A={x|x为偶数且x2为奇数}
B={x|有y∈I使x=2y}
C={1，2，3}
D={0，2，-2，5，-3，4，-4}
E={2x|x∈I}
F={3，3，2，1，2}
G={x|有x∈I且x3-6x2-7x-6=0}
5、确定下列关系中哪些是正确的，并简单说明理由。
a）
b）
c）{}
d）{}
e）{a,b}{a,b,c,{a,b,c}}
f）{a,b}{a,b,c,{a,b,c}}
g）{a,b}{a,b,{a,b}}
h）{a,b}{a,b,{a,b}}
6、设A、B和C为集合。
证明或用反例推翻以下的各个命题：
a）若AB且BC，则AC。
b）若AB且BC，则AC。
c）若AB且BC，则AC。
d）若AB且BC，则AC。
7、若A、B为集合，则AB与AB能同时成立吗？
请证明你的结论。
8、列举出下列集合中每个集合的所有子集：
a）{1，2，3}
b）{1，{2，3}}
c）{{1，{2，3}}}
d）{}
e）{,{}}
f）{{1，2}，{2，1，1}，{2，1，1，2}}
g）{{，2}，{2}}
9、给出下列集合的幂集：
a）{a，{b}}
b）{1，}
c）{x,y,z}
d）{，a,{a}}
e）（{}）
10、设（A）=（B）。
证明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）（AB）~C；
c）~（AB）；
d）~A~B；
e）（A–B）–C；
f）A–（B–C）；
g）（AB）C；
h）（AB）（BC）
2.设A={n|nI+且n<12},B={n|nI+且n8},C={2n|nI+},D={3n|nI+}且E={2n-1|nI+}试用A，B，C，D和E表达下列集合：
a）{2，4，6，8}；
b）{3，6，9}；
c）{10}；
d）{n|n为偶数且n>10}；
e）{n|n为正偶数且n10，或n为奇数且n9}。
3.证明：
a）如果AB且CD，则ACBD且ACBD；
b）A（B-A）=;
c）A（B-A）=AB;
d）A–（BC）=（A–B）（A–C）；
e）A–（BC）=（A–B）（A–C）；
f）A–（A–B）=AB；
g）A-（B-C）=（A-B）（AC）。
4.证明
a）A=B当且仅当AB=；
b）AB=BA；
c）（AB）C=A（BC）；
d）A（BC）=（AB）（AC）；
e）（BC）A=（BA）（CA）。
5.判断一下结论是否成立，如果或成立，就给予证明，如果不成立，就用文氏图加以说明。
a）若ACBC且ACBC，则AB；
b）若AB=AC且AB=AC，则B=C；
c）若AB=AC，则B=C;
d）若AB=AC，则B=C;
e）AB=AC，则B=C;
f）若ABC，则AB或AC；
g）若BCA，则BA或CA。
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）AB=AB;
h）A-B=B;
i）A-B=B-A;
j）AB=A；
k）（A）（B）=（AB）;
7.设A，B为任意两个集合，证明：
a）（A）（B）（AB）;
b）（A）（B）=（AB）。
8.试求出和，其中为：
a）{{}}；
b）{，{}}；
c）{{a},{b},{a,b}}。
9.设
且
，
且
，
。
证明
10.设
且
，
，试求
和
11.设
且
。
试求
和
。
12.设
，
，我们称
和
分别为集合序列
的上极限和下极限，证明：
a）
为由一切属于无限多个
的元素组成的集合；
b）
为由一切属于“几乎所有”的
的元素组成的集合。
习题1.3
1、用归纳法证明：
a）
；
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）若nI+则
。
2、设a0，a1，a2，…为由自然数组成的严格单调递增序列。
证明：
若nN，则n≤an。
3、斐波那契（Fibonacci）数列定义为
F0=0
F1=1
Fn+1=Fn+Fn-1，nI+
证明：
若nI+，则
。
4、设n,mI+且n＞m。
假定有n个直立的大头针，甲、乙两人轮流把这些直立的大头针扳倒。
规定每人每次可扳倒1至
根，且扳倒最后一根直立的大头针者为获胜者。
试证明：
如果甲先扳且（m+n）不能整除n，则甲总能获胜。
5、证明以下的二重归纳原理的正确性：
设i0,j0N。
假定对任意自然数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、证明：
若nN，则nn。
7、证明：
若n,mN，则nm当且仅当nm。
8、证明：
若n,mN，则nm当且仅当n+m+。
9、证明：
若n,mN，则n＜m当且仅当有xN使m=n+x+。
10、证明：
若nN，则不可能有mN使n＜m＜n+。
习题1.4
1、设A={0,1}，B={1,2}。
试确定下列集合：
a）A×{1}×B
b）A2×B
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）
d）（AB）×（CD）=（A×C）
（B×D）
3、如果B∪CA，则（A×B）－（C×D）=（A－C）×（B－D）。
这个命题对吗？
如果对，则给予证明；如果不对，则举出反例。
f）4、证明：
若xC且yC，则（（C））。
5、证明：
a∪且b∪。
6、把三元偶定义为{{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,yA∩B}
b）A={1,2,3,4,5}，B={1,2,3}，R={|xA,yB且x=y2}
2、设R1和R2都是从{1,2,3,4}到{2,3,4}的二元关系，并且
R1={<1,2>,<2,4>,<3,3>}
R2={<1,3>,<2,4>,<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，RS也是自反的（反自反的，对称的，反对称的，或传递的）。
7、描述R上的下列二元关系S的性质：
a）S={|x,yR且x·y＞0}；
b）S={|x,yR，4整除|x－y|且|x－y|＜10}；
c）S={|x,yR，x2=1且y＞0}；
d）S={|x,yR，4|x|≤1且|y|≥1}。
8、设n,mI+。
若集合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和LD，画出它们的关系图，并写出它们的关系矩阵。
4.设A为恰有n个元素的有限集。
a）共有多少个A上的不相同的自反关系？
a）共有多少个A上的不相同的反自反关系？
b）共有多少个A上的不相同的对称关系？
c）共有多少个A上的不相同的反对称关系？
d）共有多少个A上的不相同的既是对称又反对称的关系？
习题2.3
1.设R为非空有限集A上的二元关系。
如果R是反对称的，则RR-1的关系矩阵MRR-1中最多能有多少个元素为1？
2.设R为集合A上的二元关系，则RR-1为A上包含R的最小对称关系，RR-1为A上的包含在R中的最大对称关系。
3.设IA为集合A上的恒等关系，即IA={|xA}。
则对A上的任意二元关系R，A上的二元关系IARR-1必是自反的和对称的。
4.设R为任意的二元关系。
证明
a）domR-1=ranR;
b）ranR-1=domR。
习题2.4
1、设集合{a,b,c,d}上的二元关系R1和R2为R1={,,}；R2={,,,}。
试求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={|j=i+1或j=i/2}；R2={|i=j+2}；试求
，
，
，
及
。
8、设R为集合A上的二元关系，s，t
N，s证明
a）若kN，则Rs+k=Rt+k；
b）若k,iN，则Rs+kp+i=Rs+i；
c）若kN，则Rk
{R0,R1,…,Rt-1}。
其中p=t-s。
9、设IA为集合A上的恒等关系，R为A上的任意二元关系。
证明
a）R是自反的，当且仅当IAR；
b）R是反自反的，当且仅当R∩IA=；
c）R是对称的，当且仅当R=R-1；
d）R是反对称的，当且仅当RR-1=IA；
e）R是传递的，当且仅当RoRIA。
10、如果集合A上的二元关系R既是自反的，又是传递的，则R2=R。
11、设R1为从集合A到集合B的二元关系，R2为从集合B到集合C的二元关系。
试求dom（R1oR2）和ran（R1oR2）。
12、设R为从集合A到集合B的二元关系，且对每个XA，皆令R（X）={yB|有xX使＜x，y＞R}。
若X1A且X2A，则有
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的二元关系。
若XA，则（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）R1R2是A上的相容关系；
e）R1oR2是A上的相容关系；
f）
是A上的相容关系；
3、如果A为恰含n个元素的有限集，则A上有多少个不同的相容关系？
习题2.7
1、试判断下列I上的二元关系是不是I上的等价关系，并说明理由。
a）{|i,jI且i·j>0}；
b）{|i,jI且i·j≥0且i与j不同时为0}；
c）{|i,jI且i≤0}；
d）{|i,jI且i·j≥0}；
e）{|i,jI且i|j}；
f）{|i,jI且有xI使10x≤i≤j≤10（x+1）}；
g）{|i,jI且|i－j|≤10}；
h）{|i,jI且有x,yI使10x≤i≤10（x+1）及10y≤j≤10（y+1）}；
i）{|i,jI且有xI使10x2、有人说：
“如果集合A上的二元关系R是对称的和传递的，则R必是自反的”。
并给出了如下的证明：
如果R，则由R是对称的可知R，从而由R是传递的得到R和
R。
因此R是自反的。
请你想一想，他的看法和证明对吗？
为什么？
3、设集合A上的二元关系R是自反的。
证明R为等价关系的充要条件是：
若,
R,则
R.
4、如果集合A上的二元关系R满足：
若,R，则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使S1S2，就称∏1和∏2的加细，记为∏1≤∏2且∏1≠∏2，就称∏1为∏2的真加细，并记为∏1<∏2。
设R1和R2都是集合A上的等价关系，证明：
a）R1R2当且仅当A/R1≤A/R2。
b）R1R2当且仅当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,jI+且集合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|iI且1≤i≤14}；
c）{i|iI且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+；
5、证明：
a）半序关系的逆关系仍然是半序关系；
b）全序关系的逆关系仍然是全序关系；
c）良序关系的逆关系未必是良序关系；
7、举出满足下列条件的半序结构的实例。
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,y2R，则T当且仅当x1≤x2且y1≤y2；
b）若x1,x2,y1,y2R，则T当且仅当x1≤x2；
c）若x1,x2,y1,y2R，则T当且仅当x1＜x2或者x1=x2且y1≤y2；
d）若x1,x2,y1,y2∈R，则T当且仅当x1＜x2。
11、设R为集合S上的全序关系。
证明R和R-1同时为S上的良序，当且仅当S为有限集。
12、I+在上定义二元关系R如下：
nRm当且仅当f（n）其中f（n）表示n的不同素因子的个数。
证明为良序结构。
13、设S为集合且l（S）。
证明在半序结<（S）,>中有
Supl=∪l；infl=∩l。
14、设为集合A的所有划分组成的集合，并在上定义二元关系R如下：
对任意的∏1,∏2，则∏1R∏2当且仅当∏1为∏2的加细。
证明R是上的半序。
第三章
习题3.1
1、下列关系中哪些是部分函数？
对于不是部分函数的关系，说明不能构成部分函数的原因。
a）{|x,y∈N且x+y<10}；
b）{|x,y∈R且y=x2}；
c）{|x,y∈R且y2=x}。
2、下列集合能定义部分函数吗？
如果能，试求出它们的定义域和值域。
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>>}；
3、设A为集合。
若对任意s1,s2（A）皆令f（s1,s2）=s1∩s2，则f是从（A）×（
升级会员 