资源描述：
《离散数学数理逻辑与集合论试题.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学（1）—数理逻辑与集合论试题一、形式化下列语句：（每小题3分，共12分）1.有的实数不是有理数，但所有的有理数都是实数。2.实数的稠密性（任意两个实数x和y之间必可找到另一个实数z）。3.集合的集合A的任一元素的元素都是A的元素（一类特殊集合A）。4.除0而外，每个自然数有且仅有一个相继前元（论域已设定为自然数集）。二、判断下列推理式及集合、关系运算的正确性（正确的标√；错误的标×，每小题2分，共18分）：1.(P→Q)(P→R)P→(QR)（）2.(PQ)→R(P→R)(Q→R)（）3.(x)（P(x)→Q(x)）
2、(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上是可满足的。其中
3、，D1，D2分别是含一个和两个个体的论域。2.写出IFPTHENQELSER的命题公式表达。要求分别给出两种范式的最简形式：（1）合取范式；（2）析取范式。（注：所谓最简形式指公式长度最短）四、（每小题5分，共10分）1.写出下式的主析取范式和主合取范式：（┌P→R）→（┌P（┌QR））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
4、）计算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=，在A×A上定义关系R：如果a+d=b+c,则R.（1）证明R是等价关系.（2）求[<3，6>]R2.（10分）设A=，R是集合A上的整除关系：R＝{
5、x整除y}。（1）证明R是偏序关系；
6、（2）画出相应的哈斯图；（3）给出所有最长的链和最长的反链。3.（9分）设是集合X的划分，证明也是集合X的划分。七、（5分）对集合A，B和C，定义A×B×C为A×B×C=（A×B）×C.证明由f()=>的定义的函数f:A×B×C→A×(B×C)是双射函数。答案：一、1.设：是实数，：是有理数2.设：是实数，：与相等，：在与之间3.设表示是一类特殊集合4.设：与相等，：是的相继前元二、1.√2.×3.×4.√5.√6.×7.√8.√9.√三、1.该式在上是普遍有效的，而在上不是普遍有效的。该式在上
7、是不可满足的，而在上是可满足的。2.合取范式析取范式四、1.主析取范式为∨0,1,2,4,6,7主合取范式为∧2,42.原式可表示为即证明为矛盾式求出的子句集为的子句集为的子句集为建立归结过程(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)。
8、且,，有且。二式相加，可得传递性成立由以上三条知，是等价关系(2)其中即。2．(1)证明是偏序关系(i)整除，即，自反(ii)，且整除，即显然只有满足时才有即或满足反对称性(iii)且时设，(为正整数)则即整除，满足传递性为偏序关系(2)画出哈斯图(3)最长的链，即长度为4的链包括：{2,4,12,24}24{2,6,12,24}1230{3,6,12,24}最长的反链，(长度为3)包括：64{2,3,5}5{4,5,6}32证明：令，(1)，由已知条件，显然即不在中，。(2)证是集合的划分，则，(3)证：设与不同时成立，由
9、于为的划分则与中必有一式成立且则(4)其中，分别是的划分，由以上四条知也是的划分七．证：若有即并且()故是单射函数又有，，，即存在此时使即，故是满射函数是双射函数
