习题
1、用列举法给出下列集合：
a)小于5的非负整数的集合；
b)10到20之间的素数的集合；
c)不超过65的12之正整数倍数的集合。
2、用命题法给出下列集合：
a)不超过100的自然数的集合；
b)E v和O d；
c)10的整倍数的集合。
3、用归纳定义法给出下列集合：
a)允许有前0的十进制无符号整数的集合；
b)不允许有前0的十进制无符号整数的集合；
c)允许有前0和后0的有有限小数部分的十进制无符号实数的集合；
d)不允许有前0的十进制无符号偶数的集合；
e)E v和O d；
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.设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)如果AB且CD，则ACBD且ACBD；
b)A(B-A)=;
c)A(B-A)=AB;
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)(AC)。
4.证明
a)A=B当且仅当AB=；
b)AB= BA；
c)(AB)C= A(B C)；
d)A(B C)=(AB)(AC)；
e)(B C) 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. 设0{|R a a R =∈且1}a ≤，{|i R a a R =∈且1
(1)}a i <+，i I +∈。 证明01
n
i i R R ==I
10. 设{|n A x x R =∈且}x n >，n N ∈，试求
n
n A
∞
=U 和
n n A ∞
=I
11. 设{|x A y y R =∈且0},y x x R ≤≤∈。试求
1
x
x R
x A ∈>U 和1
x x R x A ∈>I
。
12. 设0i
m i m
A A ∞∞===
I U ，0i m i m
A A ∞∞
===UI
，我们称A 和A 分别为集合序列012,,,A A A L 的上极
限和下极限，证明： a) A 为由一切属于无限多个i A 的元素组成的集合； b)
A 为由一切属于“几乎所有”的i A 的元素组成的集合。
习题 1、 用归纳法证明：
a)
1
)1(1321211+=+?++?+?n n n n Λ； b) 2+22+23+…+2n =2n +1-2； c) 2n =2n ； d) 3|n 3+2n ;
e) 1·2·3+2·3·4+…+n (n +1)(n +2) =
()()()4
321+++n n n n
f) 任意三个相邻整数的立方和能被9整除； g) 11n +2+122n +1是133的倍数； h) 若n I +则
n n
≥+
++
12
11
1Λ。
2、设a 0，a 1，a 2，…为由自然数组成的严格单调递增序列。证明：若n N ，则n ≤a n 。
3、斐波那契(Fibonacci)数列定义为 F 0=0 F 1=1 F n +1=F n +F n -1，n I +
证明：若n I +，则1
2
251251--?
??
?
??+≤≤?
??
?
??+n n n F 。
4、设n , m I +且n ＞m 。假定有n 个直立的大头针，甲、乙两人轮流把这些直立的大头针扳倒。
规定每人每次可扳倒1至m 根，且扳倒最后一根直立的大头针者为获胜者。试证明：如果甲先扳且(m +n )不能整除n ，则甲总能获胜。 5、证明以下的二重归纳原理的正确性： 设i 0, j 0N 。假定对任意自然数i ≥i 0及j ≥j 0，皆有一个命题P (i , j )满足： i) P (i 0, j 0)真； ii)对任意自然数k ≥i 0及l ≥j 0，若P (k , l )真，则P (k +1, l )和P (k , l +1)皆真。则对任意自然数i ≥i 0及j ≥j 0，P (i , j )皆真。 6、证明：若n N ，则nn 。
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、 设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)×(C D)= (A×C) (B×D)
3、如果B∪CA，则(A×B) －(C×D)= (A－C) ×(B－D)。这个命题对吗如果对，则给予证明；如果不对，则举出反例。
f)4、证明：若xC且yC，则
5、证明：a∪
6、把三元偶
7、为了给出序偶的另一定义，选取两个不同集合A和B(例如取A=，B={?})，并定义
A },{b, B}}。证明这个定义的合理性。
第二章 二元关系
习题
1、 列出从A 到B 的关系R 中的所有序偶。
a) A ={0, 1, 2}，B ={0, 2, 4}，R ={
b) A ={1, 2, 3, 4, 5}，B ={1, 2, 3}，R ={
求R 1∪R 2, R 1∩R 2, domR 1, domR 2, ranR 1, ranR 2, dom(R 1∪R 2)和ran(R 1∪R 2)。 3、设1R 和2R 都是从集合A 到集合B 的二元关系。证明
dom(R 1∪R 2)= domR 1∪domR 2 ran(R 1∩R 2) ranR 1∩ranR 2
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 ={
b) S ={
10、设R 为集合A 上的一个二元关系。如果R 是反自反的和传递的，则R 一定是反对称的。 11、设R 为集合A 上的一个二元关系，若令fld R =dom R ∪ran R 则fld R =∪(∪R )。 12、若R 为集合A 上的一个二元关系，则R 也是∪(∪R )上的二元关系。
习题
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 的关系图G R ，求出R 的关系矩阵M R ,并指出R 所具有的性质。
2. 对图2.2.3给出的集合A={1,2,3}上的十二个二元关系的关系图，写出相应的关系矩阵，
并指出各个关系所具有的性质。
3. 对习题种第4题所给的二元关系L,D 和LD ，画出它们的关系图，并写出它们的关系矩
阵。
4. 设A 为恰有n 个元素的有限集。
a) 共有多少个A 上的不相同的自反关系 a) 共有多少个A 上的不相同的反自反关系 b) 共有多少个A 上的不相同的对称关系 c) 共有多少个A 上的不相同的反对称关系
d) 共有多少个A 上的不相同的既是对称又反对称的关系
习题
1. 设R 为非空有限集A 上的二元关系。如果R 是反对称的，则RR -1的关系矩阵M RR-1中最
多能有多少个元素为1
2. 设R 为集合A 上的二元关系，则RR -1为A 上包含R 的最小对称关系，RR -1为A 上的包
含在R 中的最大对称关系。
3. 设I A 为集合A 上的恒等关系，即I A ={
二元关系I A RR -1必是自反的和对称的。 4. 设R 为任意的二元关系。证明
a) domR -1=ranR; b) ranR -1=domR 。
习题
1、 设集合{a, b, c, d}上的二元关系R 1和R 2为R 1={,,}；R 2={,,,
2R 。
3、若R 为任意集合A 上的空关系或全关系，则R 2=R 。
4、举出使R 1o(R 2∩R 3) (R 1o R 2)∩(R 1o R 3), (R 2∩R 3)o R 4 (R 2o R 4)∩(R 3o R 4) 成立的二元关系R 1，R 2，R 3和R 4的实例。
5、设R 1和R 2都是集合A 上的二元关系。证明或用反例推翻以下的论断： a) 如果R 1和R 2都是自反的，则R 1o R 2也是自反的； b) 如果R 1和R 2都是反自反的，则R 1o R 2也是反自反的； c) 如果R 1和R 2都是对称的，则R 1o R 2也是对称的； d) 如果R 1和R 2都是传递的，则R 1o R 2也是传递的；
6、设A ={0，1，2，3}上的二元关系R 1和R 2为R 1={| j =i +1或j =i /2}；R 2={< i , j >|i =j +2}；试求1R M ，2R M ，21R R M ?，121R R R M ??及31
R M 。
8、设R 为集合A 上的二元关系，s ，t ∈N ，s c) 若k N ，则R k ∈{R 0,R 1,…,R t -1}。其中p =t -s 。 9、设I A为集合A上的恒等关系，R为A上的任意二元关系。证明 a) R是自反的，当且仅当I A R； b) R是反自反的，当且仅当R∩I A=； c) R是对称的，当且仅当R =R-1； d) R是反对称的，当且仅当R R-1= I A； e) R是传递的，当且仅当R o R I A。 10、如果集合A上的二元关系R既是自反的，又是传递的，则R2=R。 11、设R1为从集合A到集合B的二元关系，R2为从集合B到集合C的二元关系。试求dom(R1o R2)和ran(R1o R2)。 12、设R为从集合A到集合B的二元关系，且对每个XA，皆令R (X)={ yB|有xX使＜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的二元关系。若XA，则(R1o R2) (X)= R2(R1 (X))。 习题 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) R o R*= R+= R*o R； b) (R+)+= R+； c) (R*)*= R*； 习题 1、设R1和R2都是集合A上的相容关系。证明或用反例推翻下列命题： a) R1∩R2是A上的相容关系； b) R1∪R2是A上的相容关系； c) R1－R2是A上的相容关系； d) R1R2是A上的相容关系； e) R1o R2是A上的相容关系； R是A上的相容关系； f) 2 1 3、如果A为恰含n个元素的有限集，则A上有多少个不同的相容关系 习题 1、试判断下列I上的二元关系是不是I上的等价关系，并说明理由。 a) {< i, j >| i, j I且i·j >0}； b){< i, j >| i, j I且i·j≥0且i与j不同时为0}； c){< i, j >| i, j I且i≤0 }； d){< i, j >| i, j I且i·j≥0 }； e){< i, j >| i, j I且i| j }； f){< i, j >| i, j I且有x I使10x≤i≤j≤10(x +1)}； g){< i, j >| i, j I且| i－j |≤10 }； h){< i, j >| i, j I且有x, y I使10x≤i≤10(x+1)及10 y≤j≤10(y +1)}； i){< i, j >| i, j I且有x I使10x< i <10(x +1)}； 2、有人说：“如果集合A上的二元关系R是对称的和传递的，则R必是自反的”。并给出了如下的证明：如果 3、设集合A上的二元关系R是自反的。证明R为等价关系的充要条件是：若 4、如果集合A上的二元关系R满足：若 5、设R1和R2都是集合A上的等价关系。试判断下列A上的二元关系是不是A上的等价关系，为什么 a)A2－R1； b)R1－R2； R； c)2 1 d)r(R1－R2)； e)R2o R1； 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,…,A n}为A的划分。试证明{ A1∩B,A2∩B,…,A n∩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、画出下列集合上的整除关系的哈斯图。 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=I A且R=R*； b) 若R是A上的拟序，当且仅当R∩R-1=且R=R+； 5、证明： a) 半序关系的逆关系仍然是半序关系； b) 全序关系的逆关系仍然是全序关系； c) 良序关系的逆关系未必是良序关系； 7、举出满足下列条件的半序结构 a) b) c) A的某些非空子集有下确界，但无最小元。 d) A的某些非空子集有上界，但无上确定界。 8、设 9、设 10、试判断下列定义在二维欧氏空间R×R上的二元关系T是不是R×R上的拟序，半序，全序和良序R×R的每个有下界的非空子集(关于拟序或半序T)是否与下确界并给出证明。 a) 若x1, x2, y1, y2R，则< x1, y1>T< x 2, y2>当且仅当x 1≤x2且y1≤y2； b) 若x1, x2, y1, y2R，则< x1, y1>T< x 2, y2>当且仅当x 1≤x 2； c) 若x1, x2, y1, y2R，则< x1, y1>T< x 2, y2>当且仅当x1＜x2或者x1=x2且y1≤y2； d) 若x1, x2, y1, y2∈R，则< x 1, y1>T< x 2, y2>当且仅当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), >中有 Sup l=∪l；inf l=∩l。 14、设为集合A的所有划分组成的集合，并在上定义二元关系R如下：对任意的∏1,∏2， 则∏1R∏2当且仅当∏1为∏2的加细。证明R是上的半序。 第三章 习题 1、下列关系中哪些是部分函数对于不是部分函数的关系，说明不能构成部分函数的原因。 a) {< x , y >| x , y ∈N 且 x + y <10}； b) {< x , y >| x , y ∈R 且 y = x 2}； c) {< x , y >| x , y ∈R 且 y 2= 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 为集合。若对任意s 1,s 2(A )皆令f (s 1,s 2)= s 1∩s 2，则f 是从(A )×(A )到(A )上的二元函数。 5、设f 为从X 到Y 的部分函数，试证明： a) 若A ，B (X )，则f [A －B ] f [A ]－f [B ]，并举例说明不能用“=”代替其中的“”； b) 若C ，D (Y )，则f -1[C －D ]= f -1[C ]－f -1[D ]。 6、设A ={－1,0,1}，则定义函数f :A 2→I 如下： 0, 0 (,), 0 f x y x y y >?<>=? -?≤?若y 若x 写出f 的全部序偶。 a) 求出ran f 。 b) 写出f { 0,1}2中的全部序偶。 c) 有多少个和f 具有相同的定义域和值域的函数g :A 2→I 7、设A 和B 为有限集，n (A )=m 且n (B )=n 。 a) 有多少个从A 到B 的1-1函数 b) 有多少个从A 到B 上的函数 8、“91”函数f :N →N 定义如下： ()()10, 100()11, 100 x x f x f f x x ->??=?+≤??若若 试证明 a) f (99)=91； b) f (x )=91，其中0≤x ≤100。 习题 1、设f ,g ,h 是从R 到R 的函数，对每个xR 皆有f (x )= x +3,g (x )=2x +1,h (x )= x /2。试求g o f , f o g, f o f , g o g , f o h , h o g , h o f , g o h 和f o h o g 。 2、设f ,g ,h 都是从R 到R 的部分函数，对于x ≠0,f(x )=1/ x 。对于x ∈R, g(x )= x 2。对x ≥0,h(x )=x 。试求f o f , h o g , g o h 及它们的定义域和值域。 3、对于下面的函数f ，确定 i) f 是否为内射、满射和双射； ii) f的值域； iii) f-1[s]。 a)f:R→R f(x)=2 x s={1} b)f:N→N×N f(n)= s={<2,2>} c)f:N→N f(n)=2n+1 s={2,3} d)f:I→N f(x)=|x| s={1,0} e) f:[0,1]→[0,1] f(x)=2/x+1/4 s=[0,1/2] f) f:[0,∞]→R f(x)=1/(1+ x) s={0,1,2} g) f:{a,b}*→{a,b}* f(x)= xa s={,b,ba} h) f:(0,1)→(0,∞) f(x)=1/x s=(0,1) 4、设n∈I+，f:A→A。证明：如果f是内射(满射，双射)，则f n也是内射(满射，双射)。 5、设f是从A到A的满射且f o f= f，证明f= I A。 6、设f是从X到Y的部分函数，g是从Y到Z的部分函数，ran f dom g。证明dom(g o f)=dom f。 7、设A={1,2,3}。有多少个从A到A的满射f使f(1)=3 8、设A={1,2,…,n}。有多少满足以下条件的从A到A的函数f: a) f o f= f b) f o f= I A c) f o f o f= I A 9、设f:X→Y且g:Y→Z a) 若g o f为满射，g为内射，则f为满射 b) 若g o f为内射，f为满射，则g为内射 习题 2、设f是从X到Y的双射，证明(f-1)-1= f。 3、设f,g,h都是从N到N的函数，其中f(x)=3x,g(x)=3x+1,h(x)=3x+2。 a) 找出它们的一个共同的左逆。 b) 找出f和g的一个共同左逆，使其不是h的左逆。 4、设f:A→B和g:B→C。如果g o f是左可逆的，能否保证f和g也一定都是左可逆的 5、设f:A→B且n(A)≥2。证明f是可逆的当且仅当f有唯一的左(右)逆。 6、设A和B是有限集且1≤n(A)≤n(B)。问共有多少个从A到B的内射 习题 2、用特征函数求下列各式成立的充分必要条件。 a) (A－B)∪(A－C)=A； b) (A⊕B)= ； c) (A⊕B)= A； d) A∩B=A∪B。 1、构造从集合A到集合B的双射。 a) A=R,B=(0,∞)； b) A=(0,1),B=[0,1)； c) A=[0,1),B=(1/4,1/2]； d) A=[0,1],B=(0,1)。 2、设n>0且x1,x 2,…,x n是n个任意整数，证明存在k和i使1≤i≤k≤n且x i+x i+1+…+x k能被n整除。 3、从小于201的正整数中任意选取101个，证明其中必有一个数能整除另一个数。 4、证明在n+1个小于等于2n的不同正整数中必有两数互素，其中n≥1。 5、设n∈I+，证明在能被n整除的正整数中必存在只由数字7和0组成的数。 6、任给52个整数，证明其中必有两数之和能被100整除或两数之差能被100整除。 7、某工人在夜校学习，他打算用37天准备考试，并决定复习60小时，每天至少用1小时，证明他必定在接连的一些天内恰好共复习了13小时。 8、求下列集合的基数，并加以证明。 a) ∑*，其中∑={a}; b) 有理数集合Q； c) {x|x∈Q且0≤x≤1}。 9、证明全体从N到N的严格单调递增函数组成的集合和基数大于。 10、证明N的全体有限子集组成的集合是可列的0。 3、设,,,为基数，0＜≤且≤，证明+≤+，·≤·且≤。 4、设A为集合，(A)= ，证明(A)=2。 5、设B={ f| f:R→R且f是连续的}，证明(A)=。 6、证明=2。 习题 1.画出图G= a)V={?1, ?2, ?3, ?4, ?5} b)E={e1,e2,e3,e4,e5,e6,e7} c)={< e1, {?2}>},< e2,{?2, ?4}>,< e3,{?1, ?2}>,< e4, {?1, ?3}>,< e5, {?1, ?3}>,< e6, {?3, ?4}>, < e7, {?4, ?5}>} d)V={?1, ?2, ?3, ?4, ?5} e)E={ e1,e2,e3,e4,e5,e6,e7,e8,e9,e10} f)={< e1, {?1, ?3}>},< e2,{?1, ?4}>,< e3,{?4, ?1}>,< e4, {?1, ?2}>,< e5, {?2, ?2}>,< e6,{ ?3, ?4}>, < e7, { ?5, ?4}>,< e8,{?5, ?3}>,< e9,{?5, ?3}>,< e10,{?5, ?3}>} g)V={?1, ?2, ?3, ?4, ?5, ?6, ?7, ?8} h)E={ e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11} i)={< e1, {?2, ?1}>},< e2,{?1, ?2}>,< e3,{?1, ?3}>,< e4, {?2, ?4}>,< e5, {?3, ?4}>,< e6,{?4, ?5}>, < e7, {?5, ?3}>,< e8,{?3, ?5}>,< e9,{?6, ?7}>,< e10,{?7, ?8}>,< e11,{?8, ?6}>} 2.写出图7.1.8抽象数学定义。 3.证明在n阶简单有向图中，完全有向图的边数最多，其边数为n(n-1)。 4.证明3度正则图必有偶数个结点。 5.在一次集会中，相互认识的人会彼此握手。试证明与奇数个人握手的人数是偶数。 6.证明图 7.1.9的两个图同构。 7.证明：在任意六个人中，若没有三个人彼此都认识，则必有三个人彼此都不认识。 8.证明图7.1.10的两个图不同构。 9.图7.1.11两个图是否同构说明理由。 10.证明任何阶大于1的简单无向图必有两个结点的度相等。 11.设n阶无向图G有m条边，其中n k个结点的度为k，其余结点的度为k+1，证明 n k=(k+1)n-2m。 习题 1.画出K4的所有不同构的子图，并说明其中哪些是生成子图，并找出互为补图的生成子 图。 2.设G= 3.画出图7.2.5的两个图的交、并和环和。 4.设G是任意6阶简单无向图。证明G或者G必有一个子图是3阶完全无向图。 5.我们称与其补图同构的简单无向图为自补图。证明每个自补图的阶能被4整除或被4 除余数为1。 6.证明没有子图是3阶完全无向图的n阶简单无向图最多有[n2/4]条边。 习题 1.考虑图7.3.6. a)从A至F的路径有多少条找出所有长度小于6的从A至F的路径。 b) 找出从A 至F 的所有简单路径。 c) 找出从A 至F 所有基本路径。 d) 求出从A 至F 的距离。 e) 求出该图的直径。 f) 找出该图的所有回路。 2. 证明图中的基本路径必为简单路径。 3. 考虑图7.3.7 a) 对于每个节点，求R()。 b) 找出所有强分支，单向分支，弱分支。 4. 设1, 2, 3是任意无向图（有向图）G 的三个任意节点，以下三公式是否成立如果成立给出证明，如果不成立举出反例。 a) d (1, 2) 0,并且等号成立当且仅当1 = 2。 b) d (1, 2) = d (2, 1)。 c) d (1, 2) + d (2, 3) d (1, 3)。 5. 证明有向图的每个节点和每条边恰处于一个弱分支中。 6. 有向图的每个节点（每条边）是否恰处于一个强分支中是否恰处于一个单向分支中 7. 证明无向图是连通的当且仅当G 的直径是自然数。 8. 证明同阶的回路必同构。 9. 设图G= 10. 设G 是弱连通有向图。如果对于G 的任意节点皆有()1G d v + =，则G 恰有一条有向回路。试证明之。 11. 证明有k 个弱分支的n 阶简单有向图至多有(n-k)(n-k+1)条边。 12. 证明非连通简单无向图的补图必定连通。 13. 设G 为n 阶简单无向图，对于G 的任意节点，()(1)/2G d v n ≥-，证明G 是连通的。 14. 证明：对于小于或等于n 的任意正整数k ，n 阶连通无向图有k 阶连通子图。 15. 图7.3.8给出了一个加权图，旁边的数字是该边的加权长度，求出从1到11的加权距离。 习题 1. 确定图7.4.6的六个图哪个是欧拉图，欧拉有向图，哈密顿图，哈密顿有向图，找出其 中的一条欧拉闭路，所有的哈密顿回路和哈密顿有向回路（如果存在的话）。 2. 如果G 1和G 2是可运算的欧拉有向图，则G 1?G 2仍是欧拉有向图。这句话对吗如果对， 给出证明，如果不对，举出反例。 3. 设n 是大于2的奇数，证明n 阶完全无向图有(n-1)/2个边不相交的哈密顿回路。 4. 设n 3，对于n 阶简单无向图G 的任意两个不同节点和′，只要它们不邻接就有d G () + d G (′) n 。试证明G 是哈密顿图。 5. 基础图是完全无向图的有向图有哈密顿路径，试证明之。 6. 设G 是非平凡的连通无向图，证明G 是欧拉图当且仅当G 是若干个边不相交的回路之 并。 7.设G是非平凡的弱连通有向图，证明G是欧拉有向图，当且仅当G是若干个边不相交 的有向回路之并。 习题 1.写出图7.5.2各图的邻接矩阵和关系矩阵，由邻接矩阵求出路径矩阵和距离矩阵，并确 定图的直径。 2.如何由邻接矩阵判断图的连通性 3.如何由邻接矩阵判断图是不是非循环图 4.如何由邻接矩阵判断有向图是否有有向回路 习题 1.画出所有不同构的一、二、三、四、五、六阶树。 2.如何由无向图G的邻接矩阵确定G是不是树。 3.设和′是树T的两个不同结点，从至′的基本路径是T中最长的基本路径。证明d T()=d T (′)=1。 4.找出图7.6.12的连通无向图的一个生成树，并求出它的圈秩和余圈秩。 5.证明或以反例反驳以下命题：任意连通无向图的任何一条边都是它的某个生成树的枝， 并且也是另一个生成树的弦。 6.求图 7.6.13的最小生成树。 7.设计一个“破圈法”求最小生成树的算法。 8.证明任何二叉树有奇数个结点。 9.证明n阶二叉树有 1 2 n+ 个叶，其高度h满足log2(n+1)-1 h 1 2 n- 。 10.由有向图G的邻接矩阵如何确定G是不是有向树。 11.找出叶的权分别为2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41的最优叶加权二叉树，并求 其叶加权路径长度。 12.找出图7.6.14给出的有序森林对应的定位二元有序树，并求其前缀编码。 第1章命题逻辑 逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。所谓的数学方法也就是 用一套有严格定义的符号，即建立一套形式语言来研究。因此数理逻辑也称为符号逻辑。 数理逻辑的基础部分是命题逻辑和谓词逻辑。本章主要讲述命题逻辑，谓词逻辑将在第 2章进行讨论。 1.1命题及其表示 1.1.1命题的基本概念 数理逻辑研究的中心问题是推理( Inference),而推理就必然包含前提和结论，前提和 结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要素。在数理逻辑中，将能够判断真假的陈述句称为命题。因此命题就成为推理的基本单位。在命题逻辑中，对命 题的组成部分不再进一步细分。 定义1.1.1能够判断真假的陈述句称为命题(Proposition )。命题的判断结果称为命题的 真值，常用T(True)(或1)表示真，F(False)(或0)表示假。真值为真的命题称为真命题，真值为假的命题称为假命题。 从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。 例1.1.1判断下列句子是否为命题 (1)北京是中国的首都。 (2)请勿吸烟！ (3)雪是黑的。 (4)明天开会吗？ (5)x+y=5。 (6)我正在说谎。 (7)9+5 < 12。 (8)1+101=110。 (9)今天天气多好啊！ (10)别的星球上有生物。 解在上述的十个句子中，(2)、( 9)为祈使句，(4)为疑问句，(5 )、( 6)虽然是陈述句，但(5)没有确定的真值，其真假随x、y取值的不同而有改变，(6)是悖论(Paradox) (即由真能推出假，由假也能推出真) ，因而(2)、(4)、(5)、(6)、(9)均不是命题。(1 )、(3)、(7)、(8)、(10)都是命题，其中(10)虽然现在无法判断真假，但随着科技的进步是可以判定真假的。 需要进一步指出的是，命题的真假只要求它有就可以，而不要求立即给出。如例1.1.1的 (8) 1+101=110，它的真假意义通常和上下文有关，当作为二进制的加法时，它是真命题，否则为假命题。还有的命题的真假不能马上给出，如例 1.1.1的(10)，但它确实有真假意 义。 1.1.2命题分类 根据命题的结构形式，命题分为原子命题和复合命题。 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作， 2006-2007学年第2学期 2005级《离散数学2》期末考试试题(A卷) 考试时间：2007年6月班级_______________________ 学号_____________________ 姓名_____________________ 请将答案写在答题纸上，写明题号，不必抄题，字迹工整、清晰； 请在答题纸和试题纸上都写上你的班级，学号和姓名，交卷时请将试题纸、答题纸和草纸一并交上来。 一.综合体(30分，每题3分) 1. 求( 1 3 5 ) (2 5 4 ) (3 4 ) 2. 只有两个生成元的循环群一定是有限循环群吗？并说明理由。 3. 有限循环群中是否一定存在周期与群的元数相等的元素？ 4. 下面哪个是域GF( 16)的真子域 (A)GF (6) ;(B)GF ⑷;(C)GF(8);(D)GF(16) 5. 有限布尔代数的元素个数必定是如下哪个形式？ (A)2n;(B)n 2 ;(C)2 n;(D)4n. 6. 下列代数系统(S, *)中，哪个是群？ (A) S={0,1,3,5},* 是模7的乘法；(B) S是有理数集合，*运算是普通乘法； (C) S是整数集合，*是普通乘法；(D) S={1,3,4,9},* 是模11的乘法。 7. 设A={0,1,2,3,4},运算为模5加法，请给出A的所有子群。 8. n元恒等置换是奇置换还是偶置换？对换呢？ 9?请给出一个有余，但不是分配格的例子。 10.设R是模12的整数环，R={0,1,2,…,11},下面哪一个是极大理想： (A) 6R; (B)2R; (C)4R; (D)8R 二.计算题(25分，每题5分) 1. 计算分圆多项式①24(X). 2. 设(Z,+)为整数加法群，(C*,??)为非零复数的乘法群，令 f: n -i n ,是Z到C*中的同态映射，请求出f的同态核。 3. 在R上求出x+2除2X5+4X3+3X2+1所得的商式和余式。 4. 设G是3次对称群，H是由I和(13)作成的子群，求H得所有右陪集。 5. 设A={0,1,2,3,4,5}, 运算为模6加法，请给出A中所有元素的周期。 三.(10分)证明或者反驳：f(x)=3x 5+5X2+1 四.(10分)设(G, *)是群，(A, *)和(B，*)是它的两个子群，C={a*b|a € A, b€ B}.证明：若*满足交换律，则(C, *)也是(G，*)的子群。 五.(10分)设Z是整数集合，X={(a,b)|a,b € Z},定义X上的二元运算①和。 如下：对任意(ab) ,(a 2,b2)€ X,有： (a1b"e (a2,b2)= (a+a?,b1+b2), (a1bJ O (a2,b2)= (ax a2,b 1X b)，其中，+，x分别是整数加法与乘法。 证明：(X，?，O)是环，如果此环有零因子请给出它们 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式 本科高等数学离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】 一、填空题 1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________; (A)-(B)＝__________________________. 2.设有限集合A,|A|=n,则|(A×A)|=__________________________. 3.设集合A={a,b},B={1,2},则从A到B的所有映射是 _______________________________________,其中双射的是 __________________________. 4.已知命题公式G＝(PQ)∧R，则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ _________________________;AB＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G＝(P(QR))，则使公式G为真的解释有 __________________________， _____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则 第1章集合 1.1 集合的基本概念 1. 集合、元（元素）、有限集、无限集、空集 2. 表示集合的方法：列举法、描述法 3. 定义1.1.1（子集）：给定集合A和B，如果集合A的任何一个元都是集合B中的元，则称集合A包含于B或B包含A，记为或，并称A为B的一个子集。 如果集合A和B满足，但B中有元不属于A，则称集合A真包含于B，记为，并且称A为B的一个真子集。 4. 定义1.1.2（幂集）：给定集合A，以A的所有子集为元构成的一个集合，这个集合称为A 的幂集，记为或 1.2 集合的运算 定义1.2.1（并集）：设A和B是两个集合，则包含A和B的所有元，但不包含其他元的集合，称为A和B的并集，记为. 定义1.2.2（交集）：A和B是两个集合，包含A和B的所有公共元，但不包含其他元的集合，称为A和B的交集，记为. 定义1.2.3（不相交）：A和B是两个集合，如果它们满足，则称集合A和B是不相交的。 定义1.2.4（差集）：A和B是两个集合，属于A而不属于B的所有元构成集合，称为A和B 的差集，记为. 定义1.2.5（补集）：若A是空间E的集合，则E中所有不属于A的元构成的集合称为A的补集，记为. 定义1.2.6（对称差）：A和B是两个集合，则定义A和B的对称差为 1.3 包含排斥原理 定理1.3.1设为有限集，其元素个数分别为，则 定理 1.3.2设为有限集，其元素个数分别为，则 定理1.3.3设为有限集，则 重要例题P11 例1.3.1 第2章二元关系 2.1 关系 定义2.1.1（序偶）： 若和是两个元，将它们按前后顺序排列，记为，则成为一个序偶。 ※对于序偶和，当且仅当并且时，才称和相等，记为 第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每 一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故 G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝__{3}__________________; ρ(A) - ρ(B)＝___________________{3},{1,3},{2,3},{123}______ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = _____2^(n^2)_____________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是__自反，对称，传递 ____________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2= {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 16. 设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公 常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={ 1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设 作业参考答案——10-特殊图 1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是 哈密顿图。 2.根据给定条件建立一个无向图G= 数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。 5.此平面图具有五个面，如下图所示。 a b c d e f g r1r2 r3 r4 r5 ?r1，边界为abca，D(r1)=3; ?r2，边界为acga，D(r2)=3; ?r3，边界为cegc，D(r3)=3; ?r4，边界为cdec，D(r4)=3; ?r5，边界为abcdefega，D(r5)=8;无限面 6.设该连通简单平面图的面数为r，由欧拉公式可得，6?12+r=2，所以 r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。因是简单图，故每个面至少由3条边围成。只要有一个面是由多于3条边所围成的，那就有所有面的次数之和 8∑ i=1 D(r i)>3×8=24。但是，已知所有面的次数之和等于边数的两倍，即2×12=24。因此每个面只能由3条边围成。 2 离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸，将答题过程手工书写，并拍照上传． 一、填空题 1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15 ． 2．设给定图G(如右由图所示)，则图G的点割集是 { f }，{ e,c} ． 3．设G是一个图，结点集合为V，边集合为E，则 G的结点度数之和等于边数的两倍． 4．无向图G存在欧拉回路，当且仅当G连通且不含奇数度结 点． 5．设G= 8．结点数v与边数e满足e=v - 1 关系的无向连通图就是树． 9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树． 10．设正则5叉树的树叶数为17，则分支数为i = 4 ． 二、判断说明题（判断下列各题，并说明理由．） 1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路． 答：错误。应叙述为：“如果图G是无向连通图，且其结点度数均为偶数，则图G存在一条欧拉回路。” 2．如下图所示的图G存在一条欧拉回路． 答：错误。因为图中存在奇数度结点，所以不存在欧拉回路。 3．如下图所示的图G不是欧拉图而是汉密尔顿图． 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={(完整word版)离散数学电子教材1
离散数学作业答案
吉林大学离散数学精品试卷
(完整版)离散数学作业答案一
大学本科高等数学《离散数学》试题及答案
离散数学试题及答案精选版
离散数学课本定义和定理
吉林大学离散数学课后习题答案
太原理工大学离散数学试题
离散数学题库
慕课 离散数学 电子科技大学 课后习题十 答案
2018国家开放大学离散数学本形考任务答案
离散数学题库及答案
离散数学作业答案
大学离散数学期末重点知识点总结(考试专用)
相关主题
文本预览