离散数学课本习题
习题1.1
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)若A?B且B?C，则A?C。
b)若A∈B且B?C，则A?C。
c)若A?B且B?C，则A?C。
d)若A∈B且B∈C，则A∈C。
7、若A、B为集合，则A?B与A∈B能同时成立吗？请证明你的结论。
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)(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. 设0{|R a a R =∈且1}a ≤，{|i R a a R =∈且1
(1)}a i <+，i I +∈。 证明01
n
i i R R ==
10. 设{|n A x x R =∈且}x n >，n N ∈，试求
n n A ∞
= 和0
n
n A
∞
=
11. 设{|x A y y R =∈且0},y x x R ≤≤∈。试求
1
x
x R
x A
∈> 和
1
x
x R x A
∈> 。
12. 设0i
m i m
A A ∞∞===
，0i
m i m
A A ∞∞
=== ，我们称A 和A 分别为集合序列0
1
2
,,,A A A 的上极
限和下极限，证明： a) A 为由一切属于无限多个i A 的元素组成的集合；
b)
A 为由一切属于“几乎所有”的i A 的元素组成的集合。
习题1.3
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 0∈N 。假定对任意自然数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 ，则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×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) (A⊕B)×(C ⊕D)= (A×C)⊕(B×D)
3、如果B∪C?A，则(A×B)－(C×D)= (A－C)×(B－D)。这个命题对吗？如果对，则给予证明；如果不对，则举出反例。
f)4、证明：若x∈C且y∈C，则
5、证明：a∈∪
6、把三元偶
7、为了给出序偶的另一定义，选取两个不同集合A和B(例如取A=?，B={?})，并定义 b>={{ a, A },{b, B}}。证明这个定义的合理性。 第二章 二元关系 习题2.1 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 ，R ⊕S 也是自反的(反自反的，对称的，反对称的，或传递的)。 7、描述R 上的下列二元关系S 的性质： a) S ={ b) S ={ 8、设n , m ∈I +。若集合A 恰有n 个元素，则在A 上能有多少个不同的m 元关系？证明你的结论。 9、设ξ和ζ都是由从集合A 到集合B 的二元关系构成的集类，并且ζ ≠?。证明 a) dom (∪ξ)=∪{dom R |R ∈ξ}； b) ran(∪ξ)=∪{ran R |R ∈ξ}； c) dom (∩ζ)?∩{dom R |R ∈ζ}； d) ran(∩ζ)?∩{ran R |R ∈ζ}； 10、设R 为集合A 上的一个二元关系。如果R 是反自反的和传递的，则R 一定是反对称的。 11、设R 为集合A 上的一个二元关系，若令fld R =dom R ∪ran R 则fld R =∪(∪R )。 12、若R 为集合A 上的一个二元关系，则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 的关系图G R ，求出R 的关系矩阵M R ,并指出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的关系矩阵M R ?R-1 中最多能有多少个元素为1？ 2. 设R 为集合A 上的二元关系，则R ?R -1为A 上包含R 的最小对称关系，R ?R -1为A 上 的包含在R 中的最大对称关系。 3. 设I A 为集合A 上的恒等关系，即I A ={ 的二元关系I A ?R ?R -1必是自反的和对称的。 4. 设R 为任意的二元关系。证明 a) domR -1=ranR; b) ranR -1=domR 。 习题2.4 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∈{R0,R1,…,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的二元关系，且对每个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，则(R1o R2) (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) R o R*= R+= R*o R； 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) R1o R2是A上的相容关系； R是A上的相容关系； f) 2 1 3、如果A为恰含n个元素的有限集，则A上有多少个不同的相容关系？ 习题2.7 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使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,…,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.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=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, y2∈R，则< x1, y1>T< x 2, y2>当且仅当x 1?x2且y1?y2； b) 若x1, x2, y1, y2∈R，则< x1, y1>T< x 2, y2>当且仅当x 1?x 2； c) 若x1, x2, y1, y2∈R，则< 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)。证明在半序结中有 Sup l=∪l；inf l=∩l。 14、设π为集合A的所有划分组成的集合，并在π上定义二元关系R如下：对任意的∏1,∏2∈π，则∏1R∏2当且仅当∏1为∏2的加细。证明R是上的半序。 第三章 习题3.1 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 (,), 0f 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。 习题3.2 1、设f ,g ,h 是从R 到R 的函数，对每个x ∈R 皆有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)= x a 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为内射 习题3.3 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的内射? 习题3.4 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?。 习题7.1 1.画出图G= a)V={ν1, ν2, ν3, ν4, ν5} E={e1,e2,e3,e4,e5,e6,e7} ψ={< e1, {ν2}>},< e2,{ν2, ν4}>,< e3,{ν1, ν2}>,< e4, {ν1, ν3}>,< e5, {ν1, ν3}>,< e6, {ν3, ν4}>, < e7, {ν4, ν5}>} b)V={ν1, ν2, ν3, ν4, ν5} E={ e1,e2,e3,e4,e5,e6,e7,e8,e9,e10} ψ={< 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}>} c)V={ν1, ν2, ν3, ν4, ν5, ν6, ν7, ν8} E={ e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11} ψ={< 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。 习题7.2 1.画出K4的所有不同构的子图，并说明其中哪些是生成子图，并找出互为补图的生成子 图。 2.设G= 3.画出图7.2.5的两个图的交、并和环和。 4.设G是任意6阶简单无向图。证明G或者G必有一个子图是3阶完全无向图。 5.我们称与其补图同构的简单无向图为自补图。证明每个自补图的阶能被4整除或被4 除余数为1。 6.证明没有子图是3阶完全无向图的n阶简单无向图最多有[n2/4]条边。 习题7.3 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的加权距离。 习题 7.4 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是若干个边不相交 的有向回路之并。 习题7.5 1.写出图7.5.2各图的邻接矩阵和关系矩阵，由邻接矩阵求出路径矩阵和距离矩阵，并确 定图的直径。 2.如何由邻接矩阵判断图的连通性？ 3.如何由邻接矩阵判断图是不是非循环图？ 4.如何由邻接矩阵判断有向图是否有有向回路？ 习题7.6 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给出的有序森林对应的定位二元有序树，并求其前缀编码。 离散数学（第五版）清华大学出版社第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令F(x):x是鸟 G(x):x会飞翔. 命题符号化为 ?x(F(x)→G(x)). (2)令F(x):x为人. G(x):x爱吃糖 命题符号化为 ??x(F(x)→G(x)) 或者 ?x(F(x)∧?G(x)) (3)令F(x):x为人. G(x):x爱看小说. 命题符号化为 ?x(F(x)∧G(x)). (4) F(x):x为人. G(x):x爱看电视. 命题符号化为 ??x(F(x)∧?G(x)). 分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的F(x)都是特性谓词。 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 27 ?x(F(x)∧G(x)) 即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。 3°（2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 ?xF(x) 其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。 （2）在(a),(b),(c)中均符号化为 ?xG(x) 其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在(a),(b),(c)中均符号化为 ?xH(x) 其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。 分析1°命题的真值与个体域有关。 2°有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 ?xF(x) 这里，F(x):x呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ?x(F(x)→G(x)) 这里，F(x):x为人，且F(x)为特性谓词。G(x):x呼吸。 28 2．3 因题目中未给出个体域，因而应采用全总个体域。 （1）令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题符号化为?x(F(x)→(G(x)∨H(x)) （2）令F(x):x是人，G(y):y是化，H(x):x喜欢，命题符号化为 ?x(F(x)∧?y(G(y)→H(x,y))) （3）令F(x):x是人，G(x):x犯错误，命题符号化为 ??x(F(x)∧?G(x)), 或另一种等值的形式为 ?x(F(x)→G(x) 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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 )。 《离散数学》模拟试题3 一、填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A得幂集合p（A）=_____ _。 2. 设集合E ={a, b, c, d, e}, A= {a, b, c}, B = {a, d, e}, 则A∪B =___ ___， A∩B =____ __，A－B =___ ___，～A∩～B =____ ____。 3. 设A，B是两个集合，其中A= {1, 2, 3}, B= {1, 2}，则A－B =____ ___， ρ（A）－ρ（B）=_____ _ _。 4. 已知命题公式R Q P G→ ∧ ? =) (，则G的析取范式为。 5. 设P：2＋2＝4，Q：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A、B是两个集合，A＝{1,3,4}，B＝{1,2}，则A－B为（）. A.{1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X＝{x, y}，则ρ（X）＝（）。 A. {{x},{y}} B. {φ,{x},{y}} C. {φ,{x},{y},{x, y}} D. {{x},{y},{x, y}} 4. 设集合A＝{1,2,3}，A上的关系R＝{(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R不具备（）. 三、计算题（共50分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0 离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若 离散数学习题三 11、填充下面推理证明中没有写出的推理规则。 前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。 前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨?? ②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。 （2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明： （1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理： 前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 即根据附加前提证明法，推理正确。 习题参考答案 1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。 阮允准同学提供答案: 解：设度数小于3的结点有x个，则有 3×4＋4×3＋2x≥2×16 解得：x≥4 所以度数小于3的结点至少有4个 所以G至少有11个结点 2、设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。 阮允准同学答案： 证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。 若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。 若度数为5的结点数为6,8个，结论显然成立。 由上可知，G中至少有5个6度点或至少有6个5度点。 3、证明：简单图的最大度小于结点数。 阮同学认为题中应指定是无向简单图. 晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n. 4、设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3 。阮同学给出证明如下： 证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。 6、画出所有5个结点3条边，以及5个结点7条边的简单图。 解：如下图所示：(晓津与阮同学答案一致) 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值： （4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 离散数学（第五版）清华大学出版社第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们 都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来 的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许 多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结 的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→ｑ。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→ｑ为假命题。 （7）p→ｑ，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→ｑ为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 1. 写出命题公式 ﹁（P →（P ∨ Q)）的真值表。 答案： 2.证明 答案: 3. 证明以下蕴涵关系成立： 答案： ４. 写出下列式子的主析取范式: 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)(Q P)P (Q)(Q Q)P (P)Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧? 5． 构造下列推理的论证:p ∨q, ｐ→?r ， s →t, ?s →ｒ， ?t ? ｑ 答案: ①s →ｔ 前提 ②t 前提 ③ｓ ①②拒取式I12 ④s →ｒ 前提 ⑤ｒ ③④假言推理I １１ ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论Ｉ10 6. 用反证法证明:ｐ→(?(r ∧s ）→?q ）, p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨ ７. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F （ x )：ｘ是鱼 Ｗ（ x )：x 生活在水中 ))((W(x)F(x)x →? 8． 请将下列命题符号化: 存在着不是有理数的实数。 答案: 令 Q ( ｘ ):x 是有理数 R （ x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令Ｍ(ｘ)：x 是人 Ｃ（x):x 是聪明的 则上述命题符号化为 １０. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥ｘ。 答案: 令P(x):x 是正实数 Ｓ（ｘ,y): x+y ≥x １１． 请将下列命题符号化： 每个人都要参加一些课外活动。 答案: 令P(x ）:x 是人 Q （ｙ）: y 是课外活动 S(ｘ,ｙ）:ｘ参加y ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→?? 第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为)(x ?，在（a）中为假命题，在 xF (b)中为真命题。 (2)在两个个体域中都解释为)(x ?，在（a）(b)中均为真命 xG 题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ x ?? ? ) ( H ( (x (2)F(x): x是卖菜的人 H(x): x是外地人 命题符号化为: )) F ?? x x→ (x ( H ) ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F y x G ? y ? ∧ x→ ( ( )) ( H ) x ((y , (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x F x y G ∧ ? H ?? y→ ) ( , x ( ( ( (y ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=x y,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x 15.设D的结点数大于1，D= 1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧? 5. 构造下列推理的论证：p ∨q, p →?r, s →t, ?s →r, ?t ? q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →(?(r ∧s)→?q), p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨ 7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x 是人 Q(y): y 是课外活动 S(x,y):x 参加y )))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→?? 离散数学（第五版）清华大学出版社第1章习题解答1．1除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2（1）p:2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命可编辑范本 题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。 离散数学试题 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.设P：天下大雨,Q：他在室内运动,命题“如果天下大雨，他就．在室内运动”可符合化为 （B） A. P∧Q B. P→Q C. Q→P D. P∨Q 2.设G=(V , E)为任意一图（无向或有向的），顶点个数为n，边的条数为m， 则各顶点的度数之和等于（ D ）。 A.n B. m C. 2n D. 2m 3.下列命题为假．命题的是（A） A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 4.谓词公式(?x(P(x)∨?yR(y))→Q(x) 中变元x是（D） A.自由变元 B.约束变元 C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元 5.若个体域为整数域，下列公式中值为真的是（A） A.?x?y(x+y=0) B.?y?x(x+y=0) C.?x?y(x+y=0) D.??x?y(x+y=0) 6.下列命题中不．正确的是（D） A.x∈{x}-{{x}} B.{x}?{x}-{{x}} C.A={x}∪x,则x∈A且x?A D.A-B=??A=B 7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（C） A.P?Q B.P?Q C.Q?P D.Q=P 8.下列表达式中不．成立的是（A） A.A∪(B⊕C)=(A∪B) ⊕ (A∪C) B.A∩(B⊕C)=(A∩B) ⊕ (A∩C) C.(A⊕B)×C=(A×C) ⊕ (B×C) D.(A-B) ×C=(A×C)-(B×C) 9.半群、群及独异点的关系是（A） A.{群}?{独异点}?{半群} B.{独异点}?{半群}?{群} 欢迎共阅 一、填空题 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.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G 的前束范式是_______________________________. 16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________, R 2＝______________________________________________________. 二、选择题 离散数学习题详细答案 ————————————————————————————————作者：————————————————————————————————日期： 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值： 离散数学（第五版）清华大学出版社第6章习题解答 6.1 A:⑨; B:⑨; C:④; D:⑥; E:③ 分析对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对 给定运算的封闭性,具体方法已在 5.3节做过说明. 下面分别讨论对各种不同代数系纺的判别方法. 1°给定集合S和二元运算°,判定 离散数学（第五版）清华大学出版社第7章习题解答 7.1 (1),(2),(3),(5)都能构成无向图的度数列,其中除(5)外又都能构成无向简单图的度数列. 分析1°非负整数列d,d ,L,d 能构成无向图的度数列当且仅当n di为 1 2n∑ i=1偶数,即d1,d2,L,dn中的奇数为偶数个.（1）,(2),(3),(5)中分别有4个,0个,4个,4 个奇数,所以,它们都能构成无向图的度数列,当然,所对应的无向图很可能是非简 单图.而(4)中有 3 个奇数,因而它不能构成无向图度数列.否则就违背了握手定理的推论. 2°(5) 虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若存在无向简单图G,以1,3,3,3 为度数列,不妨设G 中顶点为v1,v2,v3,v4,且d(vi)=1,于是d(v2)=d(v3)=d(v4)=3.而v1只能与v2,v3,v4之一相邻,设v1与v2相邻,这样一来,除v2能达到3度外, v3,v4都达不到3度,这是矛盾的. 在图7.5所示的4个图中,(1) 以1为度数列,(2)以2为度数列,(3)以3为度数列,(4)以4为度数列(非简单图). 7.2 设有几简单图D以2,2,3,3为度数列,对应的顶点分别为v1,v2,v3,v4,由于d(v)=d+(v)+d_(v),所示,d+(v)-d-(v)=2-0=2,d+(v )=d(v )-d-(v ) 11222=2-0=2,d+(v)=d(v)-d-(v)=3-2=1,d+(v)=d(v)-d-(v)=3-3=0 333444 81 由此可知,D 的出度列为2,2,1,0,且满足d+(v)= d-(v).请读者画出 ∑i∑ｉ 一个有向图.以2,2,3,3为度数列,且以0,0,2,3为入度列,以2,2,1,0为出度列. 7.3 D 的入度列不可能为1,1,1,1.否则,必有出度列为2,2,2,2(因为d(v)=d+(v)+d-(v)),)此时,入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知,1,1,1,1也不能为D的出席列. 7.4 不能. N阶无向简单图的最大度Δ≤n-1.而这里的n个正整数彼此不同,因而这n个数不能构成无向简单图的度数列,否则所得图的最大度大于n,这与最大度应该小于等于n-1矛盾.离散数学(第五版)清华大学出版社第2章习题解答
离散数学题库及答案
离散数学第五版 模拟试题 及答案
离散数学题目大汇总
离散数学习题三 含答案
自考离散数学教材课后题第五章答案
最新离散数学习题答案
离散数学试题与答案
离散数学(第五版)清华大学出版社第1章习题解答
离散数学复习题及标准答案
屈婉玲版离散数学课后习题答案
最新离散数学试题库
离散数学复习题及答案
离散数学(第五版)清华大学出版社第
离散数学练习题及答案
《离散数学》试习题及答案
离散数学习题详细答案
离散数学(第五版)清华大学出版社第6章习题解答
离散数学(第五版)清华大学出版社第7章习题解答