05-06(1)《离散数学》期末考试试题(A)

PAGE北京交通大学2005-2006学年第一学期《离散数学》期末考试试卷（A）一、填空题（共16分，每空2分）我们称为命题。在命运题逻辑中，任何命题公式的主合取范式都存在，并且是。设集合，A的幂集。在推理理论中，前提在推导过程中的任何时候都可以引入使用，这一推理规则叫做。设R是集合A上的二元关系，如果关系R同时具有对称性和性，则称R是相容关系。设R是集合A上的二元关系，如果R是自反的，则它的关系矩阵的主对角线元素。设R是集合A上的二元关系，R-1是R的逆关系，则R的关系矩阵与R-1的关系矩阵具有的关系是。设R是集合A上的二元关系，如果关系R同时具有自反性、和传递性，则称R是A上的一个偏序关系。二、选择一个正确答案的代号，填入括号中。（共16分，每小题2分）下列语句中不能成为命题的是（）。A．小王是我的同学，也是我的好朋友；B．地球外的星球上也有人；C．11+1=100；D．我正在说慌。下列各式中，哪一个是析取范式（）。A．ØPÙQ；B．ØPÙPÙ(QÚR)；C．PÙ(Ø(ØQÚR))；D．ØPÙ(QÚØR)。个体域为整数集合，下列公式中（）不是命题。A．(x)(y)(x*y=y)； B．(x)(y)(x*y=1)；C．(x)(x*y=x)； D．(x)(y)(x*y=2)下列谓词公式中（）不正确。A．(x)(A(x)B)(x)A(x)B；B．(x)(BA(x))B(x)A(x)；C．(x)(BA(x))B(x)A(x)；D．(x)(A(x)ÚB)(x)A(x)ÚB；下列命题中正确的是（）。A．∪{}=； B．{,{}}-{{}}={}；C．{,{}}-{}={，{}}； D．{,{}}-={{}}；设A,B,C为任意三个集合，下列各命题中正确的是（）。A．若AB且BC，则AC； B．若AB且BC，则AC；C．若AB且BC，则AC； D．若AB且BC，则AC。设R1，R2是集合A={a，b，c，d}上的两个关系，其中R1={（a，a），（b，b），（b，c），（d，d）}，R2={（a，a），（b，b），（b，c），（c，b），（d，d）}，则R2是R1的（）闭包。A．自反B．对称C．传递D．以上都不是设偏序关系R是集合A={1，2，3，4，5，6}中数的“整除”关系，则A的极大元、极小元的个数分别是（）。A．2，1B．2，2C．3，1D三、计算题（共40分，每小题10分）求命题公式(P(QR))((PQ)(PR))的真值表。通过求主析取范式判断下列命题公式是否等值。（1）（PÙQ）Ú（ØPÙQÙR）；（2）（PÚ（QÙR））Ù（QÚ（ØPÙR））；将公式x((yP(x，y))(zQ(z)R(x)))化成等价的前束范式：设已知集合A={1,2,3,4,5,6}上的等价关系R={(1,1),(1,5),(2,2),(2,3),(2,6),(3,2),(3,3),(3,6),(4,4),(5,1),(5,5),(6,2),(6,3)(6,6)}求A的由R诱导出的划分和A关于R的商集。四、证明题（共28分）用等价变换方法证明：P®(Q®B)(P®Q)®(P®R)用归纳法证明(A1®B)Ù(A