离散数学练（合集）.docx

离散数学练（合集）

第一篇：离散数学练《离散数学》练习福建农林大学东方学院2009——2010学年第一学期第一篇数理逻辑一、填空题及单项选择题：1、设解释I为：客体城D{2,3}，a2b,3f(2)3f(3),2P(2,2)1P(2,3)1P(3,2)0P(3,3)0则P(a,f(a))P(b,f(b))，xyP(x,y)。2、公式G(P(QR))Q的主析取范式为。3、下列命题等值式正确的是【】（A）PQ(PQ)(QP)；PQ(PQ)(PQ)；（B）（C）PQQP；（D）PQPQ.4、设命题公式G(QP)(PQ)，则G是【】（A）可满足的；（B）永真的；（C）永假的；（D）析取范式5、前提xP(x)与x(P(x)Q(x))的有效结论是【】（A）xQ(x)；（B）xQ(x)；（C）xP(x)；（D）x(P(x)Q(x))。.二、解答题：1、将下列命题符号化：（1）明天不下雨又有空的话，我就会去打球。（2）只要她生病了，我都会去看她（只有她生病了，我才会去看她）。（3）每个旅客或坐头等舱或坐二等舱。（4）有些汽车比任何火车都慢，但并非所有的汽车都比火车慢。2、求公式G(P(QR))Q的主合取范式和主析取范式，并求使G取值为真的所有指派。练习（）三、逻辑推理题1、用演绎法证明：P→（Q→R），SP，Q,R├S.（应注明每一步推理所采用的推理规则）。2、找出下列推导过程中的错误，并问结论是否有效？如果是，写出正确的推导过程。（1）x(P(x)Q(x))（2）P(y)Q(y)（3）xP(x)（4）P(y)（5）Q(y)（6）xQ(x)规则P（前提引入）(1)规则P（前提引入）(3)(2),(4)假言推理(5)3、有红、黄、绿、白四队参加足球联赛，如果红队第三，则当黄队不是第二时，绿队第四。或者白队不是第一，或者红队第三。已知绿队不是第四。试证明：如果白队第一，那么黄队第二。（要求：设P：白队第一；Q：黄队第二；R：红队第三；S：绿队第四。并写出前提和结论的符号化及推理过程。）第二篇集合论一、填空题及单项选择题：1、设R是集合A{a,b,c}上的二元关系，且R{(a,b),(a,c)}，则s(R)ts(R)。2、设R是A{a,b,c,d}上的二元关系，且R{(a,b),(a,d),(c,c),(d,a)}，则R的关系矩阵AR3、偏序关系应具有的性质为4．设N、Z、Q、R和C分别为自然数、整数、有理数、实数和复数集合，（0，1）为实数区间，则下列式子正确的是【】（A）NR；（B）QC；（C）NQ；（D）(0,1)Z.5．设N、R分别为自然数和实数集合，则下列基数关系式正确的是【】（A）cardR；（B）0；（C）card2；（D）card2N0练习（）N6．按照阶从低到高的次序排列，则下列排列次序正确的是【】（An,n2,2n；（B）lgnn,n2(2n)；（C）lognn,n2；（D）logn(lgnn,2n二、解答题1、设集合A{1,2,,12}，R为A上的整除关系，试求：（1）画出偏序集(A,R)的Hasse图；（2）写出A中的最大元、最小元、极大元、极小元；（3）写出A的子集B{1,3,6,9}的上界、下界及上、下确界。2、（自然映射问题）习题八（P162）第16题。（屈婉玲《离散数学》，下同）设A{a,b,c}，R为A上的等价关系，且R{a,b,b,a}IA求自然映射g:AA/R。3、（计数问题）习题六（P99）第21，23题。（1）某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打蓝球或排球。求不会打球的人数。（2）使用包含排斥原理求不超过120的素数个数。三、证明题也是A上的等价关系。1、设R是非空集合A上的等价关系，试证R的逆关系R也是A上的偏序关系。2、设R是非空集合A上的偏序关系，试证R的逆关系R3、设（0，1）和[0，1]为实数区间，证明：(0,1)[0,1]*第三篇代数系统一、填空题及单项选择题：1234561、设,,S6，且(1)，546213，则=，的阶=。123456521436，,10,11}，运算是按位加，则群(G,)的子群有2、设G{00,01凡子群有个，2阶子群有个。3、整数集Z对于普通减法来说作成一个代数系统(Z,)，则(Z,)【】（A）是半群但没有单位元；（B）含有单位元；（C）有右单位元，但没有左单位元；（D）有左单位元，但没有右单位