离散数学数理逻辑与集合论试题.pdf

离散数学（离散数学（1）数理逻辑与集合论试题）数理逻辑与集合论试题 一、形式化下列语句： （每小题 3 分，共 12 分） 1. 有的实数不是有理数，但所有的有理数都是实数。 2. 实数的稠密性（任意两个实数 x 和 y 之间必可找到另一个实数 z） 。 3. 集合的集合 A 的任一元素的元素都是 A 的元素（一类特殊集合 A） 。 4. 除 0 而外，每个自然数有且仅有一个相继前元（论域已设定为自然数集） 。 二、判断下列推理式及集合、关系运算的正确性（正确的标；错误的标，每小题 2 分， 共 18 分） ： 1.(PQ)(PR) P (QR) （ ） 2.(PQ)R(PR)(QR) （ ） 3.(x)（P(x)Q(x)）(x)P(x)(x)Q(x) （ ） 4. (x)(P(x)Q(x) (x)P(x)(x)Q(x) （ ） 5.(x) (y) P (x, y) (x)(x)P(x,y) （ ） 6. P(A)P(B) P(AB) A,B 为任意集合 （ ） 7. 一个关系可以：既不满足自反性，也不满足非自反性。 （ ） 8一个关系可以：既不满足对称性，也不满足反对称性。 （ ） 9一个关系可以：既满足对称性，同时也满足反对称性。 （ ） 三、 （每小题 4 分，共 8 分） 1. 给出一个公式在 D1 上是普遍有效的，而在 D2 上不是普遍有效的；再给出一个公式， 在 D1 上是不可满足的，而在 D2 上是可满足的。其中，D1，D2 分别是含一个和两个个 体的论域。 2.写出 IF P THEN Q ELSE R 的命题公式表达。要求分别给出两种范式的最简形式： （1）合取范式； （2）析取范式。 （注：所谓最简形式指公式长度最短） 四、 （每小题 5 分，共 10 分） 1.写出下式的主析取范式和主合取范式： （PR）（P （Q R） ） 2.使用归结法证明：由(x) (F(x)s(x) ) (y)(M(y)W(y), (x)(M(y)W(y) (x)(F(x)S(x). 五、(共 20 分) 1. 设 A=（1）求 P（A）和 A+， （2 分） （2）写出 P（A）上的包含关系 R（3 分） （3）计算 card(R), card(A), card (A)。 （3 分） 2. 设 A=，从 A 到 B 不同的二元关系有多少个？ 又有多少种不同的函数？（4 分） 3.计算（8 分） ： (1). (2). (3). (4). (5). card(N) (6). card(R) (7). card(NN) (8). card(RR) 六、 （共 27 分) 1.（8 分）设 A=，在 AA 上定义关系 R：如果 a+d=b+c, 则R.（1）证明 R 是等价关系.（2）求R 2.（10 分）设 A=，R 是集合 A 上的整除关系： R| x 整除 y 。 （1）证明 R 是偏序关系； （2）画出相应的哈斯图； （3）给出所有最长的链和最长的反链。 3.（9 分）设是集合 X 的划分， 证明也是集合 X 的划分。 七、 （5 分） 对集合 A，B 和 C， 定义 ABC 为 ABC = （AB）C. 证明由 f()=的定义的函数 f: ABCA(BC)是双射函数。 答案： 一、 1. 设 ： 是实数， ： 是有理数 2. 设 ： 是实数， ： 与 相等， ： 在 与 之间 3. 设 表示 是一类特殊集合 4. 设 ： 与 相等， ： 是 的相继前元 二、1. 2. 3. 4. 5. 6. 7. 8. 9. 三、1. 该式在 上是普遍有效的， 而在 上不是普遍有效的。 该式在 上是不可满足的， 而在 上是可满足的。 2. 合取范式 析取范式 四、1. 主析取范式为 0,1,2,4,6,7 主合取范式为2,4 2. 原式可表示为 即证明 为矛盾式 求出 的子句集为 的子句集为 的子句集为 建立归结过程 (1) (2) (3) (4) (5) (6) (1)(2)归结 (7) (3)(6)归结 (8) (4)(7)归结 (9) (5)(8)归结 证毕 五、1. (1) (2) (3) ， ， 2. 不同的二元关系共有 个 不同的函数为 种 3. (1) 3，(2) 9，(3) 10，(4) 0，(5) ，(6) ，(7) ，(8) 六、1. （1） 证：i) , 自反性成立 ii) ， 且 有 ，则 对称性成立 iii) 。且 , ， 有 且 。 二式相加，可得 传递性成立 由以上三条知， 是等价关系 (2) 其中 即 。 2 (1) 证明 是偏序关系 (i) 整除 ，即 ， 自反 (ii) ，且 整除 ，即 显然 只有满足 时才有 即 或 满足反对称性 (iii) 且 时 设 ， ( 为正整数) 则 即 整除 ， 满足传递性 为偏序关系 (2) 画出哈斯图 (3) 最长的链，即长度为 4 的链包括： 2, 4, 12, 24 24 2, 6, 12, 24 12 30 3, 6, 12, 24 最长的反链，(长度为 3)包括： 6 4 2, 3, 5 5 4, 5, 6 3 2 证明：令 ， (1) ，由已知条件 ，显然 即 不在 中， 。 (2) 证 是集合 的划分，则 ， (3) 证： 设 与 不同时成立，由于