离散数学习题解
⑧
?x(H(x) ??(?F(x) ??G(x)))
⑦UG
26
(3)
设: F(x):x 能表示成分数, G(x):x 为无理数, 前提: 结论: 证明: ① ② ③ ④ ⑤ ⑥ ⑦ ?x(H(x) ?F(x)) H(y) ?F(y)
?x(G(x) ??F(x)) G(y) ??F(y) F(y) ??G(y) H(y) ??G(y) ?x(H(x) ??G(x))
前提引入 ①UI 前提引入 ③UI ④置换
②⑤假言三段论 ⑥UG
?x(G(x) ??F(x)), ?x(H(x) ?F(x)) ?x(H(x) ??G(x))
H(x)为有理数
5.24.在自然推理系统 F 中, 构造下面推理的证明:
每个喜欢步行的人都不喜欢骑自行车. 每个人或者喜欢骑自行车或者喜欢乘汽车. 有的人不喜欢乘汽车, 所以有的人不喜欢步行. (个体域为人类集合)
令 F(x): x 喜欢步行, G( x): x 喜欢骑自行车, H(x): x 喜欢乘汽车. 前提: ?x(F(x) ???G(x)), ?x(G(x) ??H(y)), ?x?H(x). 结论: ?x?F(x). ① ?x(G(x) ??H(y)) ② G(c) ??H(c) ③ ?x?H(x) ④ ?H(c) ⑤ G(c)
⑥ ?x(F(x) ???G(x)) ⑦ F(c) ???G(c) ⑧ ?F(c) ⑨ ?x?F(x)
前提引入 ①UI 前提引入 ③UI
②④析取三段 前提引入 ⑥UI ⑤⑦拒取 ⑧EG
5.25.略
离散数学习题解 27
习题六
6.1. 选择适当的谓词表示下列集合:
(1)小于 5 的非负整数 (2)奇整数集合
(3)10 的整倍数的集合
(1){x|x∈??0≤x<5} (2){x|x=2k+1?k∈?} (3){x|x=10k?k∈? }
6.2. 用列元素法表示下列集合: (1)S1＝
{x|x 是十进制的数字} (2)S2＝{x|x＝2?x＝5} (3)S3＝{x|x＝x∈??3 (4)S4＝{x|x∈\\?x2－1＝0?x>3} (5)S5＝{?x, y>|x, y∈??0≤x≤2??1≤y≤0} (1) S1={0,1,2,3,4,5,6,7,8,9} (2) S2={2,5} (3) S3={4,5,6,7,8,9,10,11} (4) S4=?? (5) S5={?0, ?1?,?1, ?1?,?2, ?1?,?0,0?,?1,0?,?2,0?} 6.3. 略 6.4. 设 F 表示一年级大学生的集合, S 表示二年级大学生的集合, M 表示数学专业学生的集合, R 表示计算机 专业学生的集合, T 表示听离散数学课学生的集合, G 表示星期一晚上参加音乐会的学生的集合, H 表示 星期一晚上很迟才睡觉的学生的集合. 问下列各句子所对应的集合表达式分别是什么? 请从备选的答 案中挑出来. (1)所有计算机专业二年级的学生在学离散数学课. (2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉. (3)听离散数学课的学生都没参加星期一晚上的音乐会. (4)这个音乐会只有大学一, 二年级的学生参加. (5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会. 备选答案: ①T?G∪H ②G∪H?T ③S∩R?T ④H＝G∪T ⑤T∩G＝??⑥F∪S?G ⑦G?F∪S ⑧S??(R∪M) ?G ⑥G?S??(R∩M) 答案: (1) ③S∩R?T (2) ④H=G∪T (3) ⑤T∩G=??(4) ⑦G?F∪S (5) ⑧S??(R∪M) ?G 6.5. 确定下列命题是否为真: (1) ????(2) ?∈??(3) ??{?} (4) ?∈{?} (5){a, b}?{a, b, c, {a, b, c}} 离散数学习题解 (6){a, b}∈{a, b, c, {a, b }} (7){a, b}?{a, b, {{a, b}}} (8){a, b}∈{a, b, {{a, b}}} 28 (1) 真(2)假(3) 真(4) 真(5) 真(6) 真(7) 真(8) 假 6.6. 略 6.7. 略 6.8. 略 6.9. 略 6.10.略 6.11.略 6.12.略 6.13.略 6.14.略 6.15.略 6.16.略 6.17.略 6.18.略 6.19.略 6.20.略 6.21.略 6.22.略 6.23.略 6.24.略 6.25.略 6.26.略 6.27.略 6.28.略 6.29.略 6.30.略 6.31.略 6.32.略 6.33.略 6.34.略 6.35.略 6.36.略 6.37.略 6.38.略 6.39.略 6.40.略 6.41.略 6.42.略 6.43.略 6.44.略 6.45.略 离散数学习题解 29 习题七 7.1. 已知 A={?,{?}},求 A×P(A). A×P(A)={ ???,??,??,{?}?,??,{{?}}?,??,{?,{?}}?,?{?},??,?{?},{?}?,?{?},{{?}}?, ?{?},{?,{?}}?} 7.2. 对于任意集合 A,B,C, 若 A×B?A×C,是否一定有 B?C 成立? 为什么? 不一 定, 因为有反例: A=?,B={1},C={2},B?C,A×B=?=A×C. 7.3. 设 A, B, C, D 是任意集合, (1) 求证(A∩B)×(C∩D)=(A×C)∩(B×D). (2) 下列等式中哪个成立? 那些不成立?对于成立的给出证明, 对于不成立的举一反例. (A∪B)×(C∪D)=(A×C)∪(B×D) (A?B)×(C?D)=(A×C) ??(B×D) (1) ??x,y?? ?x,y?∈(A∩B)×(C∩D) ?x∈A∩B?y∈C∩D??(x∈A?x∈B) ??(y∈C?y∈D) ??(x∈A?y∈C) ?? (x∈B?y∈D) ??x,y?∈(A×B) ??x,y?∈(C×D) ??x,y?∈A×B∩C×D (A∩B)×(C∩D)=(A×C)∩(B×D) (2)都不成立, 反例: A={1,2},B={2,3},C={1,2},D={2,3} (A∪B)×(C∪D)={1,2,3}×{1,2,3}?(A×C)∪(B×D) (A?B)×(C?D)={1}×{1}?(A×C) ??(B×D) 7.4. 略 7.5. 设 A, B 为任意集合, 证明 若 A×A=B×B, 则 A=B. ?x, x∈A??x,x?∈A×A??x,x?∈B×B?x∈B A=B 7.6. 列出从集合 A={1, 2}到 B={1}的所有的二元关系. R1=??,R2={?1,1?},R2={?2,1?},R3={?1,1?,?2,1?}. 7.7. 列出集合 A={2, 3, 4}上的恒等关系 IA, 全域关系 EA, 小于或等于关系 LA, 整除关系 DA. IA={?2,2?,?3,3?,?4,4?} EA=A×A={?2,2?,?2,3?,?2,4?,?3,2?,?3,3?,?3,4?,?4,2?,?4,3?,?4,4?} LA={?2,2?,?2,3?,?2,4?,?3,3?,?3,4?,?4,4?} DA={?2,2?,?2,4?,?3,3?,?4,4?} 7.8. 列出集合 A={?, {?}, {?, {?}}, {?, {?}, {?, {?}}}}上的包含关系. R?={??,??,??,{?}?,??,{?,{?}}?,??,{?,{?},{?,{?}}}?,?{?},{?}?,?{?},{?,{?}}?,?{?},{?,{?},??,{ ?}?}?,?{?,{?}}, {?,{?}}?,?{?,{?}},{?,{?},{?,{?}}}?, ?{?,{?},{?,{?}}},{?,{?},{?,{?}}}?} 7.9. 设 A={1, 2, 4, 6}, 列出下列关系 R: (1) R={?x, y?|x, y∈A?x+y?2} (2) R={?x, y?|x, y∈A?|x?y|=1} 离散数学习题解 (3) R={?x, y?|x, y∈A?x/y∈A} (4) R={?x, y?|x, y∈A?y 为素数} (1)R={?1,2?,?1,4?,?1,6?,?2,1?,?2,2?,?2,4?,?2,6?,?4,1?,?4,2?,?4,4?,?4,6?,?6,1?,?6,2?,?6,4?,?6,6?}=EA?{?1,1?} (2)R={?1,2?,?2,1?} (3)R={?1,1?,?2,2?,?4,4?,?6,6?,?2,1?,?4,2?,?4,1?} (4)R={?1,2?,?2,2?,?4,2?,?6,2?} 30 7.10.略 7.11.Ri 是 X 上的二元关系, 对于 x∈X 定义集合 Ri(x)={y|xRiy}. 显然 Ri(x) ?X. 如果 X={?4, ?3, ?2, ?1, 0, 1, 2, 3, 4}, 且令 R1={?x, y?|x, y∈X?x 求 R1(0), R1(1), R2(0), R2(?1), R3(3). R1(0)={1,2,3,4} R1(1)={2,3,4} R2(0)={ ?1,0} R2(?1)={ ?2, ?1} R3(3)= ?? 7.12.设 A={0, 1, 2, 3}, R 是 A 上的关系, 且 R={?0, 0?, ?0, 3?, ?2, 0?, ?2, 1?, ?2, 3?, ?3, 2?} 给出 R 的关系矩阵和关系图. 7.13.设 A = {?1, 2?, ?2, 4?, ?3, 3?} B = {?1, 3?, ?2, 4?, ?4, 2?} 求 A∪B, A∩B, domA, dom(A∪B), ranA, ranB, ran(A∩B), fld(A?B). A∪B={?1,2?, ?1,3?, ?2,4?, ?3,3?, ?4,2?} A∩B={?2,4?} domA={1,2,3} dom(A∪B)={1,2,3,4} ranA={2,3,4} ranB={3,4,2} ran(A∩B)={4} fld(A?B)={1,2,3} 7.14.设 ?1 R={?0,1?,?0,2?,?0,3?,?1,2?,?1,3?,?2,3?} 求 R○R,R,R?{0,1},R[{1,2}]. R○R={?0,2?, ?0,3?, ?1,3?} R?1={?1,0?,?2,0?,?3,0?,?2,1?,?3,1?,?3,2?} R?{0,1}={?0,1?, ?0,2?, ?0,3?, ?1,2?, ?1,3?} R[{1,2}]={2,3} 7.15.设 ?1 2A={??,{?,{?}}?,?{?},??} 求 A,A,A3,A?{?},A[?],A??,A?{{?}},A[{{?}}]. A?1={?{?,{?}},??,??,{?}?}, A2={?{?},{?,{?}}?}, A3=?, A?{?}={??,{?,{?}}?}, A[?]={?,{?}},