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

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)(B ?A(x)) ? B ?(?x) A(x)； C．(?x)(B ?A(x)) ? B ?(?x) A(x)； D．(?x)(A(x)úB) ?(?x)A(x)úB； 下列命题中正确的是（ ）。 A．?∪{?}=?； B．{?,{?}}-{{?}}={?}； C．{?,{?}}-{?}={?，{?}}； D．{?,{?}}-?={{?}}； 设A,B,C为任意三个集合，下列各命题中正确的是（ ）。 A．若A?B且B?C，则A?C； B．若A?B且B?C，则A?C； C．若A?B且B?C，则A?C； D．若A?B且B?C，则A?C。 设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，1 B．2，2 C．3，1 D 三、计算题（共40分，每小题10分） 求命题公式(P?(Q?R))? ((P?Q)? (P?R))的真值表。 通过求主析取范式判断下列命题公式是否等值。 （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)ù(A2?B)ù…ù(An?B)ù(A1úA2ú…úAn) 设R是集合A上的二元关系，IA是A上的恒等变换，证明 （1）R是反自反的?IA∩R = ?； （2）R是反对称的?R∩R-1 í IA