资源描述：
《离散数学练习题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、典型习题及解析1-1．下面的是否是命题：（1）不在同一直线上的三点确定一个平面。（2）郑州是河南省的省会。（3）今年的冬天将是一个暖冬。（4）这碗汤味太淡了。（5）1011+1000=10011。1-2设P：明天天气晴朗Q：我们就去郊游则P®Q的含义为1-3根据真值表求公式P®(P∧(Q®R))的主析取范式。1-4试证明(﹁P®Q)∧(P®R)∧(﹁Q∨S)ÞS∨R。1-5如果迈克有电冰箱，则或者他卖了洗衣机，或者他向别人借了钱。迈克没有向别人借钱，所以如果迈克没有卖掉洗衣机，则他没有电冰箱。1-6如果今天我没课，则我去机房上机或去图书馆查资料
2、；若机房没有空机器，则我没法去上机；今天我没课，机房也没有空机器，所以我去图书馆查资料。1-7北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。甲说：“天津第一，上海第二。”乙说：“天津第二，广州第三。”丙说：“北京第二，广州第四。”比赛结果显示，每人猜对了一半，并且没有并列名次。问：实际名次怎样排列？2-1说明下列各式中量词的辖域与变元约束的情况：（1）("x)A(y)（2）("x)(A(x)®B(x))（3）("x)(A(x)®($y)B(x,y))（4）("x)(y)(A(x,y)∧B(y,z))∧($x)A(x,y)（5）(
3、"x)(A(x)∧($x)B(x,z)®($y)C(x,y))∨B(x,y)（6）("x)(A(x)«B(x))∧($x)C(x)∧D(x)2-2将公式("x)P(x)®($x)Q(x)化成前缀范式。2.3将公式("x)("y)(($z)(P(x,z)∧P(y,z))®($v)Q(x,y,v))化成前缀范式。3-1设集合X={a,b,c,d}，其上的关系R={,,,}，求t(R)。3-2设集合A的幂集上的包含关系，试对（1）A={a}（2）A={a,b}（3）A={a,b,c}分别画出偏序集(Ã(A),Í
4、)的哈斯图及其最小元、最大元、极小元和极大元。3.3X={a,b,c}；Y={a,b,d}，S={
5、x,y∈X∩Y}，求S的元素。3.4设A={a,b,c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性，并画出R的关系图。3.5设n,m∈Z+（正整数集合），若集合A中恰有n个元素，那么求在A上能有多少个不同的m元关系？3.6若关系R和S都是对称的和传递的，试证明R∩S也是对称的和传递的。3.7设A为3元素集，问：（1）A上自反且对称的关系有多少个？（2）A上反对称的关系有多少个？（3）A上既不是
6、对称，也不是反对称的关系有多少个？3.8R是二元关系，且R=R•R•R•R，选择下面的哪一个一定是传递的。（1）R（2）R•R（3）R•R•R（4）R•R•R•R3.9求关系的合成。设A={1,2,3,4}，A上二元关系R1,R2分别定义为R1={<2,2>,<2,3>,<3,1>}，R2={<2,1>,<3,1>,<3,4>,<4,3>}，请计算R1•R2，R2•R1，R12，R22。3.10证明题。在这类证明题中，通常为证明两个关系之间的等于，包含及被包含关系。由于关系是一种特殊的集合，在证明此类问题时，通常任选一个关系的元素，然后得出它也
7、属于另一个关系。设R,S,T均为A上的二元关系，那么证明(S∪T)•R=(S•R)∪(T•R)3.11“找出三个元素的集合A和A上关系R，使R,R2,R3,R4两两不等”是可能的吗？如可能请具体做出，并说明这一现象与t(R)=不矛盾。3.12将n个元素的集合划分成两个分块，共有多少种不同的分块？3.13设A={1,2,3,4,5}，那么（1）A上共有多少个二元关系？（2）上述关系中，有多少个是等价关系？请读者根据此题归纳出一般的结论。3.14已知N及其关系R如下，试说明R是等价关系，并指出等价类是什么。N是自然数集，R={
8、ni/
9、nj能表示成2n形式，n为任意整数}。解 "ni∈X，有ni/nj=1=20，故∈R，所以R是自反的。"ni,nj∈X，若∈R，即ni/nj=2k（k是整数），所以nj/ni=2−k，所以∈R，所以R是对称的。"ni,nj,np∈X，若∈R∧∈R，则ni/nj=2k1∧ni/nj=2k2（k1,k2是整数），则ni/np=2k1+k2，则∈R，故R是传递的。总之，R是X上的等价关系，等价类是：[1]R={1,2,4,8,16,…,2n,…}[3]R={3,3´2
10、1,3´22,…,3´2n,…}[5]R={5,5´21,5´22,…,5´2n,…}…■3.15图（a）为一有序集的哈斯图。（1）下列命题
