离散试卷有答案(4).docx

仅供个人参考 仅供个人参考 不得用于商业用途 不得用于商业用途 仅供个人参考 仅供个人参考 不得用于商业用途 不得用于商业用途 For pers onal use only in study and research; not for commercial use 蒈离散数学(A卷及答案) 、 二、 螆(10分)求(P』Q)—；(PA -(QV -R))的主析取范式 膆解：(P^Q)—(QV—R))u—(—( PV Q)) V (PA—Q A R)) fc (PV Q)V (PA —Q A R)) 袂二(PV Q V P)A (P V Q V - Q)A (P V QV R) 腿二(PV Q)A (PV Q V R) 薄=(PV Q V (RA 一R))A (P V QV R) 娜二(PV Q V R)A (P V Q V - R) A (PV QV R) 袂二 Mo A M1 薈二 m2 v m3 v m4 v m, v m6 v m7 、 三、 芆(10分)在某次研讨会的休息时间， 3名与会者根据王教授的口音分别作出下述判断: 薃甲说：王教授不是苏州人，是上海人。 羁乙说：王教授不是上海人，是苏州人。 罿丙说：王教授既不是上海人，也不是杭州人。 螄王教授听后说：你们 3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教 授是哪里人？ 莂解 设设P :王教授是苏州人； Q:王教授是上海人； R:王教授是杭州人。则根据题意应有： 肁甲：-PA Q 肆乙：~Q A P 蒆丙：~Q A 一R 肁王教授只可能是其中一个城市的人或者 3个城市都不是。所以，丙至少说对了一半。因此，可得甲或 乙必有一人全错了。又因为，若甲全错了，则有 一QA P,因此，乙全对。同理，乙全错则甲全对。所以丙 必是一对一错。故王教授的话符号化为： 賺((-PA Q) A (( QA —R) V ( 一Q A R))) V (( 一QA P) A (一QA R)) 蔵=(—PA QA Q A - R) V ( 一PA Q A — QA R) V ( 一Q A P A -QA R) 羅二(—PA QA 一R) V (P A -QA R) 腰二一PA QA — R 応二T 袈因此，王教授是上海人。 三、 四、蚆(10分)证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。 袃证明 设R是非空集合 A上的二元关系，则由定理 4.19知，tsr(R)是包含R的且具有自反性、对称性和 传递性的关系。 莁若R是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知 r(R) R。由定理 4.15 和由定理 4.16 得 sr(R)5s(R) = R,进而有 tsr(R)」(R‘)= R‘。 艿综上可知，tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。 肃四、(15 分)集合 A= {a, b, c, d, e}上的二元关系 R为 R= {a, a, a, b, a, c, a, d, a, e, b, b, b, c, b, e, c, c, c, d, c, e, d, d, d, e, e, e}, 蚁(1)写出R的关系矩阵。 蒁(2)判断R是不是偏序关系，为什么？ 莅解(1) R的关系矩阵为： 螅⑵ 由关系矩阵可知，对角线上所有元素全为 1，故R是自反的；rij + rji 1,故R是反对称的；可计 算对应的关系矩阵为： 蒀由以上矩阵可知 R是传递的。 五、 六、蒁(10分)设 A、B、C和D为任意集合，证明(A — B) X C= (AX C) — (B X C)。 螆证明：因为 芃 X , y € (A — B) X C 二 X € (A — B) A y € C 篆u ( x € AA X B) A y € C 奠u ( x € AA y € C A x B) V ( x € AA y € CA y 9) 腿=(x € AA y € C) A ( x B V y C) 羅=(x € AA y € C) A -( x € B A y € C) 节二 x , y€ (ax C) a x , y(Bx C) 蚀：=x , y € (AX C) — ( BX C) 仅供个人参考 仅供个人参考 不得用于商业用途 不得用于商业用途 不得用于商业用途 不得用于商业用途 仅供个人参考 蚈所以，(A— B) X C = (A X C— B X C)。 六、 七、蒃(10 分)设 f: A B, g: B C, h: C A，证明：如果 h g f= IA, f h g= IB, g f h= lC,贝 U f、g、 —1 — 1 — 1 h均为双射，并求出f、g和h。 肁解 因Ia恒等函数，由h g f = I