北京科技大学远程教育学院
《离散数学》综合练习?一?参考答案
数理逻辑
一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。 1、今天天气真好！ 解：不是命题。
2、王华和张民是同学。
解：是命题。真值视实际情况而定。p：王华和张民是同学。 3、我一边吃饭，一边看电视。
解：是命题。真值视实际情况而定。p：我吃饭。q：我看电视。p?q 4、没有不呼吸的人。
解：是命题。真值为1。M?x?：x是人。F?x?：x呼吸。?x?M?x??F?x?? 二、求命题公式的真值表和成真赋值、成假赋值。 [(p?q)?r]?(p?r)
p?q (p?q)?r p?r [(p?q)?r]?(p?r) 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 成真赋值：000，001，010，011，101，111；成假赋值100，110 三、用真值表、等值演算两种方法判别公式类型。 1、[(p?q)?q]?r 解： p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 解： p q r p?q 1 1 1 1 0 0 1 1 (p?q)?q 0 0 1 1 0 0 1 1 [(p?q)?q]?r 1 1 0 1 1 1 0 1 [(p?q)?q]?r??[(?p?q)?q]?r??(?p?q)??q?r
?(p??q)??q?r?[(p??q)?(?q??q)]?r?[(p??q)??q]?r可满足式
2、q??((?p?q)?p) 解：A?q??((?p?q)?p)
p q 0 0 0 1 1 0 1 1 ?p?q 1 1 0 1 (?p?q)?p 0 0 0 1 ?((?p?q)?p) 1 1 1 0 A 1 1 1 1 q??((?p?q)?p)?q??(?p?q)??p??(?p?q)?(?p?q)?1
永真式
四、求命题公式的主析取范式和成真赋值、成假赋值。 p?(q?r) 解： p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 p?(q?r) 1 1 1 1 1 1 0 1 p?(q?r)??(0， 1，2，3，4，5，7）成真赋值：000，001，010，011，100，101，111；成假赋值110
五、解释I如下：D是实数集，特定元素a=0；特定函数f?x，y?=x?y；
特定谓词F?x，y?：x ?x?y[?F(f(x，y)，x)]??x?y[?F(x?y，x)]??x?y[?((x?y)?x)] ??x?y[(x?y)?x)]真值为假 2、?x?y?z{F(x，y)?F[f(x，z)，f(y，z)] 解： ?x?y?z{F(x，y)?F[f(x，z)，f(y，z)]}??x?y?z[(x?y)?(x?z)?(y?z)] 真值为真 六、 1、求前束范式??xF(x)??yG(x，y) 解： ??xF(x)??yG(x，y)??xF(x)??yG(x，y)??xF(x)??yG(t，y) ??x?y[F(x)?G(t，y)] 2、证明：?x(A(x)?B)??xA(x)?B 证明： ?x(A(x)?B)??x(?A(x)?B)??x?A(x)?B???xA(x)?B ??xA(x)?B七、写出下面推理的证明，要求写出前提、结论，并注明 推理规则。 （1）如果乙不参加篮球赛，那么甲就不参加篮球赛。若乙参加篮球赛，那么甲和丙就参加篮球赛。因此，如果甲参加篮球赛，则丙就参加篮球赛。 解： p：甲参加篮球赛。q：乙参加篮球赛。r：丙参加篮球赛。 前提： ?q? ?p ，q ? ?p?r? ， 结论：p ? r 证明：① ?q? ?p 前提引入 ② p?q ①置换 ③ q ? ?p?r? 前提引入 ④ ?q ? ?p?r? ③置换 ⑤ ??q ? p ? ???q ? r? ④置换 ⑥ ?q ? r ⑤化简 ⑦ q ? r ⑥置换 ⑧ p ? r ②⑦假言三段论 推理正确 （2）学会的成员都是专家。有些成员是青年人。所以，有些成员是青年专家。?个体域是人的集合? F?x?：x 是学会成员。G?x?：x 是专家。H?x?：x 是青年人。 前提：?x? F?x?? G?x??，?x? F?x?? H?x?? 结论：?x? F?x?? H?x?? G?x?? 证明：① ?x? F?x?? H?x?? 前提引入 ② F?c?? H?c? ①EI ③ ?x? F?x?? G?x?? 前提引入 ④ F?c?? G?c? ③UI ⑤ F?c? ②化简 ⑥ G?c? ⑤④假言推理 ⑦ F?c?? H?c?? G?c? ②⑥ 合取 ⑧ ?x? F?x?? H?x?? G?x?? ⑦EG 推理正确 《离散数学》综合练习?二?参考答案 集合、关系、函数 一、判断题 1、对任意集合A，都有A?A和A? A，不能同时成立。 （ F ） 2、R1、R2是A上的具有自反性的二元关系，R1－R2也具有自反性。 （ F ） 3、A上恒等关系IA具有自反性、对称性、反对称性、传递性。 （ T ） 4、f：A?B，g：B?C，若fog是A?C的满射，则f、g都是满射。 （ F ） 5、A =｛1，2，3，4｝，f是从A到A的满射，则也是从A到A的单射。 （ T ） 二、填空题 1、?A－B?∪AB = A 。 2、A有2个元素，B有3个元素，从A到B的二元关系有 26 个。 － 3、R是A上的二元关系，RoR1一定具有的性质是 对称性 。 4、f?x?= lnx 是从 R+ 到 R 的函数。 5、f、g都是从A到A的双射，(fog)1 = g1of1 。 － － － 三、集合 1、A={{a，{b}}，c，{c}，{a，b}}、B={{a，b}，c，{b}} 求A∪B、A∩B、A－B、A?B 解： A?B?{{a,{b}},c,{c},{a,b},{a,b},c,{b}}A?B?{c,{a,b}}A?B?{{a,{b}},{c}} A?B?(A?B)?(B?A)?{{a,{b}},{c}}?{b}?{{a,{b}},{c},{b}} 2、A={{a，{b}}，c，?} 求A的幂集。 解：P?A?={?，｛?｝，{{a，{b}}}，｛c｝，｛{a，{b}}，c｝，｛{a，{b}}，?｝，｛c，?｝}，A} 3、证明：A－?B∪C? = ?A－B?∩?A－C? 解：A?(B?C)?A(B?C)?ABC?ABAC?(A?B)?(A?C) 四、二元关系（共30分） 1、A＝{a，b，c，b}，R＝{ 2、指出二元关系满足哪种性质，不满足哪种性质，说明理由。 解：满足反对称性；不满足自反性，反自反性，对称性，传递性 3、A =｛1，2，3，4，5，6｝，S =｛｛1，2｝，｛3｝，｛4，5，6｝｝ 画出由S产生的等价关系的关系图。 解： 4、画出偏序集的哈斯图，并指出最大元、最小元、极大元、极小元。 ｛1，2，3，…，12｝整除关系 解： 最大元：无；最小元、极小元：1；极大元：7，8，9，10，11，12 五、函数 1、确定以下各题中f是否是从A?B的函数，若是指出是否是单射、满射、双射， 如果不是说明理由。 （1）A=｛1，2，3，4，5｝、B=｛5，6，7，8，9｝ f=｛?1，8?，?3，9?，?4，10?，?2，6?，?5，9?｝ 解：f 是函数，由?3，9?，?5，9? f 不是单射，也不是满射。 （2）A=｛1，2，3，4，5｝、B=｛5，6，7，8，9｝ f=｛?1，7?，?2，6?，?4，8?，?1，9?，?5，10?｝ 解：由?1，7?，?1，9?，f 不是函数。 （3）A、B都是实数集，f?x? = x3。 解：f 是函数， f 是单射，也是满射，f 是双射。 （4）A、B都是正整数集，f(x)??x?1?1 ?x?1x?1解：f 是函数， f 是单射，不是满射。 2、A??a，b，c，d?，g、h都是A?A的函数。 g：a?b，b?a，c?d，d?c h：a?b，b?c，c?b，d?c g、h中哪个有反函数？若有则求出反函数。求出复合函数g?g(x)、h?g(x)。
离散数学综合练习及答案
