离散数学练习题2答案

–1–1-1．都是命题：1-2设P：明天天气晴朗Q：我们就去郊游则PQ：如果明天天气晴朗，我们就去郊游1-3根据真值表求公式P(P∧(QR))的主析取范式。解表1.15例1.42真值表PQRP(P∧(QR))TTTTTTFFTFTTTFFTFTTTFTFTFFTTFFFT则P(P∧(QR))(﹁P∧Q∧R)∨(﹁P∧Q∧﹁R)∨(﹁P∧﹁Q∧R)∨(﹁P∧Q∧﹁R)∨(P∧﹁Q∧R)∨(P∧﹁Q∧﹁R)∨(P∧Q∧R)■由于任意一组命题变元P1,P2,…,Pn的真值指派和它的极小项之间是一一对应的，故可以对极小项进行编码。首先需要规定变元在极小项中的排列次序，假设为P1,P2,…,Pn，用m表示极小项，若Pi出现在极小项中，则编码的第i个位置上的值为1，否则为0。比如变元P,Q,R（规定次序为P,Q,R）的极小项P∧﹁Q∧﹁R的编码为100，将此极小项记为m100。若将编码看作是一个二进制数，又可将例中的极小项记为m4。用此方法，可以简写所求得的错误!文档中没有指定样式的文字。–2–给定公式的主析取范式。P(P∧(QR))m0∨m1∨m2∨m3∨m4∨m5∨m7（规定P,Q,R的次序为P,Q,R）公式P(P∧(QR))的主析取范式。解P(P∧(QR))﹁P∨(P∧(﹁Q∨R))(﹁P∨P)∧(﹁P∨﹁Q∨R)(﹁P∨﹁Q∨R)(﹁P∨﹁Q∨R)1-4试证明(﹁PQ)∧(PR)∧(﹁Q∨S)S∨R。证明（1）﹁PQP（2）﹁Q∨SP（3）QST,(2),E16（4）﹁PST,(1),(3),I13（5）﹁SPT,(4),E18（6）PRP（7）﹁SRT,(5),(6),I13（8）﹁﹁S∨RT,(7),E16（9）S∨RT,(8),E1图1.1例1.51证明过程的树表示错误!文档中没有指定样式的文字。–3–1-5如果迈克有电冰箱，则或者他卖了洗衣机，或者他向别人借了钱。迈克没有向别人借钱，所以如果迈克没有卖掉洗衣机，则他没有电冰箱。解设P：迈克有电冰箱Q：迈克卖了洗衣机R：迈克向别人借了钱。则上述语句可翻译为命题关系式PQ∨R,﹁R﹁Q﹁P（1）PQ∨RP（2）﹁P∨Q∨RT,(1),E16（3）﹁(﹁P∨Q)RT,(2),E16（4）﹁﹁P∧﹁QRT,(3),E9（5）P∧﹁QRT,(4),E1（6）﹁R﹁(P∧﹁Q)T,(5),E18（7）﹁R﹁P∨QT,(6),E8（8）﹁RP（9）﹁P∨QT,(7),(8),I11（10）PQT,(9),E16（11）﹁Q﹁PT,(10),E181-6如果今天我没课，则我去机房上机或去图书馆查资料；若机房没有空机器，则我没法去上机；今天我没课，机房也没有空机器，所以我去图书馆查资料。错误!文档中没有指定样式的文字。–4–解设P：今天我没课Q：我去机房上机R：我去图书馆查资料S：机房没有空机器则上述语句可翻译为命题关系式PQ∨R,S﹁Q,P,SR（1）﹁RP（2）PQ∨RP（3）﹁P∨Q∨RT,(2),E16（4）R∨﹁P∨QT,(3),E3（5）﹁R﹁P∨QT,(4),E16（6）﹁P∨QT,(1),(5),I11（7）PQT,(6),E16（8）S﹁QP（9）﹁﹁Q﹁ST,(8),E18（10）Q﹁ST,(9),E1（11）P﹁ST,(7),(11),I13（12）PP（13）﹁ST,(11),(12),I11错误!文档中没有指定样式的文字。–5–（14）SP（15）F(13),(14)1-7北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。甲说：“天津第一，上海第二。”乙说：“天津第二，广州第三。”丙说：“北京第二，广州第四。”比赛结果显示，每人猜对了一半，并且没有并列名次。问：实际名次怎样排列？解设P2：北京第二Q2：上海第二R1：天津第一R2：天津第二S3：广州第三S4：广州第四由已知条件：甲猜对了一半，(﹁R1∧Q2)∨(R1∧﹁Q2)在真值指派f下为T；乙猜对了一半，(﹁R2∧S3)∨(R2∧﹁S3)在真值指派f下为T；丙猜对了一半，(﹁P2∧S4)∨(P2∧﹁S4)在真值指派f下为T。由事实知，每个城市只能得一个名次即R1∧R2,S3∧S4为永假式。再由题意，没有并列名次可得：P2∧Q2,P2∧R2,R2∧Q2在真值指派f下为F。错误!文档中没有指定样式的文字。–6–以上8个方程组成的方程组可解得f为P2=T,Q2=F,R1=T,R2=F,S3=T,S4=F因此，实际名次为：天津第一、北京第二、广州第三、上海第四。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）(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)解（1）(x)的辖域是A(y)，其中x为约束出现，y为自由出现。（2）(x)的辖域是A(x)B(x),x为约束出现。（3）(x)的辖域是A(x)(y)B(x,y),(y)的辖域是B(x,y)，其中x,y都为约束出现。（4）(x)的辖域是(y)(A(x,y)∧B(y,z))，(y)的辖域是A(x,y)∧B(y,z)，(x)的辖域是A(x,y)，其中在(x)(y)(A(x,y)∧B(y,z))中，x，y都为约束出现，z为自由出现，在(x)A(x,y)中，x为约束出现，y为自由出现。（5）(x)的辖域是(A(x)∧(x)B(x,z)(y)C(x,y))，其中x的3次出现都为约束出现，但第2次出现是受量词(x)的约束，而第1次、第3次出现是受量词(x)的约束，z为自由出现，(x)的辖域是B(x,z)。(y)的辖域是C(x,y)，其中y为约束出现，B(x,y)中的x,y都为自由出现。错误!文档中没有指定样式的文字。–7–（6）(x)的辖域是A(x)B(x)，x为约束出现，(x)的辖域是C(x),x也为约束出现，D(x)中x的出现为自由出现。2-2将公式(x)P(x)(x)Q(x)化成前缀范式。解(x)P(x)(x)Q(x)﹁(x)P(x)∨(x)Q(x)(x)﹁P(x)∨(x)Q(x)(x)(﹁P(x)∨Q(x))■2.3将公式(x)(y)((z)(P(x,z)∧P(y,z))(v)Q(x,y,v))化成前缀范式。解(x)(y)((z)(P(x,z)∧P(y,z))(v)Q(z,y,v))(x)(y)(﹁(z)(P(x,z)∧P(y,z))∨(v)Q(x,y,v))(x)(y)((z)(﹁P(x,z)∨﹁P(y,z))∨(v)Q(x,y,v))(x)(y)(z)(v)((﹁P(x,z)∨﹁P(y,z))∨Q(x,y,v)3-1设集合X={a,b,c,d}，其上的关系R={a,b,b,a,b,c,c,d}，求t(R)。解R={a,b,b,a,b,c,c,d}R2={a,a,a,c,b,b,b,d}R3={a,b,a,d,b,a,b,c}R4={a,a,a,c,b,b,b,d}t(R)=R∪R2∪R3∪R4={a,b,b,a,b,c,c,d,a,a,a,c,b,b,b,d,a,d}3-2设集合A的幂集上的包含关系，试对（1）A={a}（2）A={a,b}（3）A={a,b,c}分别画出偏序集((A),)的哈斯图及其最小元、最大元、极小元和极大元。解它们的哈斯图分别对应于图4.8（a），（b），（c）。错误!文档中没有指定样式的文字。–8–图4.8哈斯图（1）最小元、极小元都为Φ，最大元、极大元都为{a}；（2）最小元、极小元都为Φ，最大元、极大元都为{a,b}；（3）最小元、极小元都为Φ，最大元、极大元都为{a,b,c}。读者很容易看出，对一个偏序集而言，最大（小）元不一定存在，若最大（小）元存在，则必是唯一的。而且一定是极大（小）元。出现在偏序关系哈斯图中最高（低）部分的所有元素，都是极大（小）元。不同的极大（小）元是不可比的。在非空有限偏序集合中，极大（小）元必存在，不一定唯一。3.3X={a,b,c}；Y={a,b,d}，S={x,y|x,y∈X∩Y}，求S的元素。解首先求出X∩Y={a,b}，那么从题意分析可知，关系S就是集合X∩Y上的全域关系，故S={a,a,a,b,b,a,b,b}。3.4设A={a,b,c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性，并画出R的关系图。分析：如果R不满足自反性和反自反性，则其关系图GR上应该有的结点有自圈，有的结点没有自圈；如果R不满足对称性和反对称性，则其关系图GR上应该同时存在一对结点之间只有单向边，而同时又应该有另外一对结点之间有一对反向的单向边；如果R不满足传递性，只要GR同时存在从第一个结点到第二个结点的一条边以及从第二个结点到第三个结点的一条边，但是却不存在从第一个结点到第三个结点的边即可。例如：A上的二元关系R={a,a,a,b,b,c,c,b}，其关系图如图4.9所示。3.5设n,m∈Z+（正整数集合），若集合A中恰有n个元素，那么求在A上能有多少个不同的图4.9关系图错误!文档中没有指定样式的文字。–9–m元关系？解因为A上共有nm个不同的m元序偶。因此，A上全关系中应当包含nm个元素，而该全关系的任一个子集都是A上的m元关系。故A上m元关系数目应当为mn2个。3.6若关系R和S都是对称的和传递的，试证明R∩S也是对称的和传递的。证明不失一般性，我们假设R和S都是定义在集合X上的二元关系。对任意的x,y∈R∩S，那么x,y∈R且x,y∈S。因为R是对称的，故y,x∈R，又因为S也是对称的，故y,x∈S。因此y,x∈R∩S，从而R∩S也是对称的。对任意的x,y∈R∩S,y,z∈R∩S，有x,y∈R且y,z∈R,x,y∈S且y,z∈S，因为R和S都是传递的，故x,z∈R且x,z∈S，那么x,z∈R∩S，因此R∩S也是传递的。3.7设A为3元素集，问：（1）A上自反且对称的关系有多少个？（2）A上反对称的关系有多少个？（3）A上既不是对称，也不是反对称的关系有多少个？解解这类题目的关键在于分析具有自反、反自反、对称、反对称性质的关系矩阵的特点，为了将这种题目的解法更加一般化，这里将A中元素的数目记为n。（1）设R为A上自反的并且对称的关系，其关系矩阵MR的主对角线元素全部为1并且是一个对称矩阵。所以，我们只要关心它的下三角矩阵即可。因为它的下三角矩阵有(n2−n)/2个元素，而每个元素有两种取值（0或者1），因此，这样的关系共有2()/22nn个。（2）设R为A上反对称的关系，于是MR的对角元素可以任意取值，并且，考虑其下三错误!文档中没有指定样式的文字。–10–角的任何一个位置(i,j)与其对称位置(j,i)处元素的取值，只有3种情况：均取0、(i,j)处元素取值为0而(j,i)处元素取值为1、(i,j)处元素取值为1而(j,i)处元素取值为0。因此，A上反对称的二元关系的数目为2()/223nnn个。（3）在回答此问之前，先考虑A上对称的二元关系有多少个呢？这个问题与（1）相比，少了一个自反的限制，于是，对角线上的元素可以任意从0和1之间取值了。于是，总的数目为2()/22nn。再考虑到A上所有的二元关系共有22n个。并且在问题（2）中得知，A上反对称的二元关系的数目为2()/223nnn个。而既对称又反对称的二元关系有2n个