离散数学期末考试试题(配答案).doc

一填空题（每小题 2 分，共 10 分）1.谓词公式)()(xxQxxP的前束范式是_。2.设全集,5,2,3,2,1,5,4,3,2,1BAE则 AB=_，A_，BA _ _ 3.设baBcbaA,，则)()(BA_ _，)()(AB_ _。二选择题（每小题 2 分，共 10 分）1.与命题公式)(RQP等价的公式是（）（A）RQP)(（B B）RQP)(（C）)(RQP（D）)(RQP 2.设集合cbaA,A 上的二元关系bbaaR,不具备关系()性质（A）(A)传递性 (B)反对称性 (C)对称性 (D)(D)自反性 三计算题（共 43 分）1.求命题公式rqp的主合取范式与主析取范式。（6 分）2.设 集 合dcbaA,上 的 二 元 关 系 R 的 关 系 矩 阵 为1000000011010001RM,求)(),(),(RtRsRr的关系矩阵，并画出 R，)(),(),(RtRsRr的关系图。（10 分）5.试判断),(z是否为格？说明理由。（5 分）（注：什么是格？Z 是整数，格：任两个元素，有最小上界和最大下界的偏序）四证明题（共 37 分）1.用推理规则证明DDACCBBA)(,)(,。（10 分）2.设 R 是实数集，babafRRRf),(,:，abbagRRRg),(,:。求证：gf和 都是满射，但不是单射。（10 分）一，1,_ x x yP(x)yP(x)Q(y)Q(y)2,2,22 4,54,5 1,1,3,4,53,4,5 3,3,c,a,c,b,c,a,b,cc,a,c,b,c,a,b,c _ 二，B D 三，三，解：主合取方式：解：主合取方式：p pq qr r(p(pq qr)r)(p(p q qr)r)(p(pq qr)r)=0.2.40.2.4 主析取范式：主析取范式：p pq qr r(p(pq qr)r)(p(pq qr)r)(p(pq qr)r)(p(pqqr)r)(p(pqqr)=r)=1.3.5.6.71.3.5.6.7 四，四，1 1，证明：证明：编号编号 公式公式 依据依据 （1 1）（BBC C）CC 前提前提 （2 2）BBC C，CC （1 1）（3 3）BB （2 2）（4 4）A AB B （3 3）（5 5）AA （3 3）（）（4 4）（6 6）（AAD D）前提前提 （7 7）A ADD （6 6）（8 8）DD （5 5）（）（6 6）2 2，证明证明：要证要证f f是满是满射射，即即 y yR,R,都存在都存在（x1x1，x2x2）R RR R，使使f f（x1x1，x2x2）=y=y，而而f f（x1x1，x2x2）=x1+x2=x1+x2，可取可取x1=0 x1=0，x2=yx2=y，即证得即证得；再证再证g g是满射是满射，即即 y yR R，,都存在都存在（x1x1，x2x2）R RR R，使使g g（x1x1，x2x2）=y=y，而而g g（x1x1，x2x2）=x1x2=x1x2，可取可取x1=1x1=1，x2x2=y=y，即证得即证得；最后证最后证 f f 不是单射不是单射，f f（x1x1，x2x2）=f=f（x2x2，x1x1）取取 x1x1x2x2，即证得即证得，同理同理：g g（x1x1，x2x2）=g=g（x2x2，x1x1），），取取 x1x1x2x2，即证得。即证得。5 5，解：（解：（Z,Z,）是格，理由如下：）是格，理由如下：对于任意对于任意 a aZ Z，a aa a 成立，满足自反性；成立，满足自反性；对于任意对于任意 a aZ Z，b bZ Z，若，若 a ab b 且且 b ba a，则，则 a=ba=b，满足反对称性；，满足反对称性；对于任意对于任意 a a，b b，c cZ Z，若，若 a ab b，b bc c，则，则 a ac c，满足传递性；，满足传递性；而对于任意而对于任意 a a，b bZ Z，a ab b，b b 为最小上界，为最小上界，a a 为最大下界，故（为最大下界，故（Z Z，）是格。，）是格。