离散数学练习(部分)解答

《离散数学练习(部分)解答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《离散数学》练习解答福建农林大学东方学院2009——2010学年第二学期第一篇数理逻辑二、解答题：1、将下列命题符号化：（1）明天不下雨又有空的话，我就会去打球。（2）只要她生病了，我都会去看她（只有她生病了，我才会去看她）。（3）每个旅客或坐头等舱或坐二等舱。（4）有些汽车比任何火车都慢，但并非所有的汽车都比火车慢。解（1）设：明天不下雨；：明天我有空；：明天我去打球。则该命题可符号化为。（2）设：她生病；：我去看她。则该命题可符号化为。（3）设是旅客；坐；是头等舱位；是二等舱位。则该命题可符号化

2、为。（4）设是汽车；是火车；比慢。则该命题可符号化为2、求公式的主合取范式和主析取范式，并求使取值为真的所有指派。解：的主析取范式：练习解答第1页（共9页）所以的主合取范式为使取值为真的所有指派为：注意：若没有要求用等值演算，也可采用真值表求。三、逻辑推理题1、用演绎法证明：P→（Q→R），SP，Q,R├S.（应注明每一步推理所采用的推理规则）。证明：（1）（假设，否定结论引入）（2）（（1）置换，T规则）（3）（前提，P规则）（4）（（2），（3）析取三段论，T规则）（5）（前提，P规则）（6）（

3、（4），（5）假言推理，T规则）（7）（前提，P规则）（8）（（7），（6）假言推理，T规则）（9）（前提，P规则）（10）（（8），（9）合取，T规则）所以2、找出下列推导过程中的错误，并问结论是否有效？如果是，写出正确的推导过程。（1）规则（前提引入）（2）(1)（3）规则（前提引入）（4）(3)（5）(2),(4)假言推理（6）(5)练习解答第2页（共9页）解该推导过程中由（3）推出结论（4）是错误的。这是因为第（2）步中已有变元出现，因此由第（3）步中应用规则时,不能再引入变元。………………

4、3分结论是有效的，其正确推导过程为：（1）规则（2）(1)（3）规则（4）(3)（5）(2),(4)假言推理（6）(5)3、有红、黄、绿、白四队参加足球联赛，如果红队第三，则当黄队不是第二时，绿队第四。或者白队不是第一，或者红队第三。已知绿队不是第四。试证明：如果白队第一，那么黄队第二。（要求：设：白队第一；：黄队第二；：红队第三；：绿队第四。并写出前提和结论的符号化及推理过程。）解前提：结论：证明：（1）附加前提引入（2）前提引入（3）（1），（2）析取三段论（4）前提引入（5）（3），（4）假言

5、推理（6）前提引入（7）（6），（5）拒取第二篇集合论二、解答题1、设集合，为上的整除关系，试求：（1）画出偏序集的Hasse图；（2）写出中的最大元、最小元、极大元、极小元；（3）写出的子集的上界、下界及上、下确界。练习解答第3页（共9页）解：（1）的Hasse图如下：111796312241058（2）中没有最大元；最小元是1；极小元也是1；极大元有7，8，9，10，11，12。（3）没有上界，也就没有上确界；下界是1；下确界也是1。2、（自然映射问题）习题八（P162）第16题。（屈婉玲《离散

6、数学》，下同）设，R为上的等价关系，且求自然映射。解：因为，所以，，3、（计数问题）习题六（P99）第21，23题。（1）某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打蓝球或排球。求不会打球的人数。解：设S为该班学生集合，A、B、C分别表示会打篮球、排球和网球的学生集合，则据题设，有，，，，，，因为会打网球的人都会打蓝球或排球，因此有于是由包含排斥原理知或从而不会打球的人数为（2）使用包含排斥原理求不超过

7、120的素数个数。解：因为112=121，故不超过120的合数至少含有2、3、5或7这些素因数之一。为此，设练习解答第4页（共9页）现在先要求出不能被这4个素数整除的数的个数。由于，且因此，不能被2、3、5及7整除的整数有又因为2、3、5及7不满足上述条件，被“筛掉”，但它们是素数，而数1则相反。故不超过120的素数有个*4、（特征函数问题）习题八（P162）第14题。设S为集合，A，B是S的子集，表示T的特征函数。若，，求。*5、设，，则①，cardA2。②A上可定义个二元关系。其中4个自反关系，

8、4个反自反关系，8个对称关系，12个反对称关系，2个等价关系，3个偏序关系。练习解答第5页（共9页）注意：A上的二元关系是的一个子集，若，则的子集有个。空关系即空集既是反自反的，也是对称的，还是反对称的。应掌握本例中每一类关系具体的有哪些。③S中有个函数，其中2个是双射。*6、（哈斯图问题）（P127例7.19）设集合，为幂集上的包含关系，试求：（1）画出偏序集的Hasse图；（2）写出中的最大元、最小元、极大元、极小元；（3）写出的子集的上界、下界及上、下确界。*7