离散数学简答题

.简答题1用真值表法判断下列公式的类型.（1）（PQ）（PQ）（2）（PQ）R（3）（P（PQ）R（4）（PQ）Q解：（1）（PQ）（PQ）的真值表为：P Q R（PQ）PQ（PQ）（PQ）0 0 01110 0 11110 1 01000 1 11001 0 01001 0 11001 1 00011 1 1001由真值表得，此公式（1）为可满足式。（2）（PQ）R的真值表为：P Q RQPQ（PQ）R0 0 01010 0 11010 1 00010 1 10011 0 01101 0 11111 1 00011 1 1001由真值表得，此公式（2）为可满足式。（3）（P（PQ）R的真值表为：P Q RPQP（PQ）（P（PQ）R0 0 00110 0 10110 1 01110 1 11111 0 01111 0 11111 1 01111 1 1111由真值表得，此公式（3）为永真式。（4）（PQ）Q的真值表为：P QPQ（PQ）（PQ）Q0 01000 11001 00101 1100由真值表得，此公式（4）为永假式。2用真值表的方法求（PQ）（QR）的主析取范式和主合取范式。解：（PQ）（QR）的真值表P Q RPQQR（PQ）（QR）0 0 00110 0 10010 1 01000 1 11111 0 01111 0 11001 1 01001 1 1111由表得主析取范式为：（PQ）（QR） 主合取范式为：（PQ）（QR）3用等值演算法求（PQ）R）P的主析取范式和主合取范式。解：（PQ）R）P（PQ）R）P（PQ）R）P（PR）（QR）P（析取范式）P（QR）（析取范式）（P（QQ）（RR）（QR）（ PP）（PQR）（PQR）（PQ R）（PQ R） （PQR）（PQR）（六个极小项，其中重复了一个）（PQR）（PQR）（PQ R）（PQ R）（PQR） （主析取范式）由主合取范式与主析取范式的关系得：（PQ）R）P （主合取范式）4求下列公式的主析取和合取范式。（1）(P Q)(P R)（2）(P Q)(PR)（3） PQR解：（1）(P Q)(P R)(PQ)(PR) (合取范式) (PQ)(RR )(PR)(QQ )(PQR)(PQR )(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) (主合取范式) 由主合取范式与主析取范式的关系得：(P Q)(P R)(主析取范式)（2）(P Q)(PR)（PQ）(PR ) (PPQ )(PQR) (合取范式)(1Q )(PRQ )PQR (主合取范式) 由主合取范式与主析取范式的关系得：(PQ)(PR) （3）PQR (PR)(QR)(P(QQ)R)(PP)QR )(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) (合取范式)由主合取范式与主析取范式的关系得：PQR (主析取范式)5.给定解释I如下：(1)=2,3；(2)中的特定元素a=2；(3)上的函数f(x)为f(2)=3,f(3)=2;(4)上的谓词F(x)为F(2)=0,F(3)=1;.G(x,y)为G(2,2)= G(2,3)= G(3,2)=1, G(3,3)=0;L(x,y)为L(2,2)=L(3,3)=1,L(2,3)= L(3,2)= 0;在这个解释下，求下列各式的值：(1)x(F(x)G(x,a);(2) $x(F(f(x)G(x,f(x) ；(3) x$yL(x,y);(4)$yxL(x,y);(5)xy( L(x,y) L(f(x),f(y) 解：(1) x(F(x)G(x,a)(F(2)G(2,2)(F(3)G(3,2)(01)(11) 0(2)$x(F(f(x)G(x,f(x) (F(f(2)G(2,f(2) (F(f(3)G(3,f(3) (F(3)G(2,3) (F(3)G(3,3)(11) (01)1(3)x$yL(x,y)$yL(2,y)$yL(3,y)(L(2,2)L(2,3)(L(3,2)L(3,3)11 1(4)$yxL(x,y) $y(L(2,y)L(3,y)(L(2,2)L(3,2) (L(2,3)L(3,3)0 00(5)xy( L(x,y) L(f(x),f(y)y(L(2,y)L(f(2),f(y)y(L(3,y)L(f(3),f(y)(L(2,2)L(f(2),f(2)(L(2,3)L(f(2),f(3)(L(3,2)L(f(3),f(2)(L(3,3)L(f(3),f(3) (1L(3,3)(0L(3,2)(0L(2,3)(1L(2,2)(11)(00)(00)(11)06.给定解释I如下：(a)个体域为实数集合R；(b)中的特定元素a=0；(c)上的特定函数f(x,y)=x-y;(d)上的特定谓词F(x,y):x=y,G(x,y):xy说明下列公式在I下的含义，并指出其真值。(1)xy(G(x,y) F(x,y)(2) xy(F(f(x,y),a) G(x,y)(3) xy(G(x,y) F(f(x,y),a) ) (4) xy(G(f(x,y),a) F(x,y) ) 解：(1) xy(G(x,y) F(x,y) 含义：任意两个实数x,y，若xy，则就不会有x=y.真值为1。(2) xy(F(f(x,y),a) G(x,y) 含义：任意两个实数x,y，若x-y=0，则xy。真值不确定。(3) xy(G(x,y) F(f(x,y),a) ) 含义：任意两个实数x,y，若xy，则就不会有x-y=0。真值为1。(4) xy(G(f(x,y),a) F(x,y) ) 含义：任意两个实数x,y，若x-y0，则x=y。真值不确定.7.设个体域为D=a,b,c,将下列各公式的量词去掉。(1) x(F(x)G(x)(2) x(F(x)$yG(y)(3) $xyF(x,y)(4) x(F(x,y) $yG(y)解: (1)x(F(x)G(x)(F(a)G(a)(F(b)G(b)(F(c)G(c) (2)xF(x)$yG(y) (F(a)F(b)F(c)(G(a) G(b) G(c)(3)$xyF(x,y) $x( F(x,a)F(x,b)F(x,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c) (4) x(F(x,y) $yG(y)$xF(x,y) $yG(y)F(a,y)F(b,y)F(c,y)G(a)G(b)G(c)8.求公式下列公式的前束范式。(1)xF(x,y) $yG(x,y)(2) $xF(x)xG(x)(3) xF(x) yG(x,y) (4) x(F(x,y) $y G(x,y,z) )(5) (xF(x,y) $yG(y) xH(x,y,z)(6) $xF(x,y) (F(x) $yH(x,y)解：(1) xF(x,y) $yG(x,y) xF(x, t) $yG(s,y) $x(F(x, t) $yG(s,y) $x$y(F(x, t) G(s,y)(2) $xF(x)xG(x) $xF(x)yG(y) (换名规则) $xy(F(x)G(y) (量词辖域扩张等值式)(3)xF(x) yG(x,y) xF(x) yG(z,y) (换名规则) $xy(F(x) G(z,y) (量词辖域扩张等值式)(4)x(F(x,y) $y G(x,y,z) x(F(x,a) $y G(x,y,z) (代替规则) x$y(F(x,a) G(x,y,z)(量词辖域扩张等值式)(5)(xF(x,y) $yG(y) xH(x,y,z) (xF(x,a) $y G(y)b H(b,a,z) (换名规则)$x$y(F(x,a) G(y)b H(b,a,z) (量词辖域扩张等值式) xyb (F(x,a) G(y)H(b,a,z) (量词辖域扩张等值式)(6) $xF(x,y) (F(x) $yH(x,y)$xF(x,y) (F(a) $yH(a,y)$xF(x,y)(F(a) y H(a,y)$xF(x,y)y(F(a) H(a,y)xy(F(x,y)(F(a) H(a,y)9化简下式各式（1）(ABC)-(BC)A（2）(AB)-(C-(AB)（3）（ABC）（AB）-（A（B-C）A）解：（1）(ABC)-(BC)A=（A（BC）(BC)）A=（A(BC)）（BC）(BC)）A=（A(BC)）A=A 吸收律（2）(AB)-(C-(AB)=(AB)-（C(AB)）=(AB)-（C（AB）=(AB)（CAB）=(AB)（CAB）=AB 吸收律（3）（ABC）（AB）-（A（B-C）A）=（AB）-A （利用两次吸收律） =（AB）A =（AA）（BA） =（BA）=B- A10设A=a, b, a, b， B=a, b，试求BA，AB解：BA BBAa, ba, ba, b, a, ba, ba, bABABABa, b, a, ba, ba, b, a, ba, ba, b, a, ba, ba, b11对60个学生参加课外活动的情况进行调查。结果发现，25人参加物理小组，26人参加化学小组，26人参加生物小组。9人既参加物理小组又参加生物小组，11人既参加物理小组又参加化学小组，8人既参加化学小组又参加生物小组。8人什么小组也没参加，回答下列各问题：（1）有多少人参加了3个小组？（2）只参加一个小组的有多少人？A=x|x参加物理小组,|A|=25 B=x|x参加化学小组,|B|=26 C=x|x参加生物小组,|C|=26 E=x|x 设同时参加3个小组的人数为x，即|ABC|=x 则由已知条件得： |AB|-|ABC|=11-x |AC|-|ABC|=9-x |BC|-|ABC|=8-x |A-(BC)=|A|-(11-x)-(9-x)-x =25-11+x-9+x-x =5+x 同理 |B-(AC)|=26-11+x-8+x-x =7+x |C-(AB)|=26-9+x-8+x-x =9+x 所以 60=5+x+7+x+9+x+11-x+9-x+8-x+x+8得 x=3 只参加1个组的人数为+： 5+x+7+x+9+x=5+3+7+3+9+3=3012在20名青年有10名是公司职员,12名是学生,其中5名既是职员又是学生,问有几名既不是职员,又不是学生。解:设职员和学生的集合分别是A和B。由已知条件A=10, B =12, AB=5AB=A+B-AB=10+12-5=17则(AB)=E-AB=20-17=3所以有3名既不是职员又不是学生。 解：（法二）设全集、职员和学生的集合分别是E、A和B由已知条件E20, A=10,B=12, AB=5,设有x名既不是职员,又不是学生,它们的关系如下图所示，所以5+（10-5）+（12-5）+x=20,解议程得x=3所以有3名既不是职员又不是学生。13求1到500之间能被2,3,7任一数整除的整数个数。解:设1到500间分别能被2,3,7整除的整数集合为A,B,CA=500/2=250(注x表示不大于x的最大整数)B=500/3=166；C=500/7=75；AB=500/(2*3)=83；AC=500/(2*7)=35；BC=500/(3*7)=23；ABC=500/(2*3*7)=11ABC=A+B+C-AB-BC-BC+ABC=250+166+71-83-35=23+11=357 所以，1到500之间能被2,3,7任一数整除的整数个数是357。14.设A=1，2，3，4，R，S都是A上的二元关系，其中：R=，S=，(1)给出R的关系矩阵和关系图，(2)求dom(RS)，ran(RS), fld(R-S)，RoS ，R2 ，R-1 ，RS1,2, R2 解：（1）R的关系矩阵为：R的关系图如下：（2）dom(RS)=4ran(RS)=1,2,3,4fld(R-S)=1,2,3RS=,R2 =,R-1 =,，,R S1,2=,R2=1,3 15.设A=1,2,3,4,5,6,7,8,9,10，R是A上的二元关系， R=|x,yA x+y=10 说明R具有哪些性质。解： R=, , , , , , , 易知 R既不是自反也不是反自反的 R是对称的 R不是反对称的 R不是传递的。16.设A=a,b,c，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性(要求画出R的关系图)。解：满足条件R的关系图为如下所示:17.将集合上的下述二元关系：R=1，1，1，21，33，3T=1，1，1，22，12，2，3，3S=1，1，1，22，22，3AA分别画出R、S、T、AA的关系图，并按自反性、对称性、反对称性和传递性分类（10分）解:具有自反性的二元关系有：T 、AA具有反自反性的二元关系有：具有对称性的二元关系有：T、AA具有反对称性的二元关系有：R、S、具有传递性的二元关系有：R、S、AA18设集合A=1，2，3，4，5，试求A上的模2同余关系R的关系式。解:“模2同余关系R”即指“如果x，y除以2的余数相同，则R”。于是，R=，19设A=a,b,c,A上的二元关系R的关系图如下图所示,（1）写出二元关系R的关系式和关系矩阵M；（2）求r(R),s(R),t(R)。解:（1）R=,，R的关系矩阵（2）=,=r(R)=RIA,s(R)=,t(R)=R, 20.设，A上的二元关系，求r(R)，s(R)，t(R)。解：IA=，R- =，R2 =RR =，R3=R2 R =，r(R)=RIA=，s(R)=RR-=，t(R)=RR2R3=，21.设集合A=a，b，c，d，R1，R2都是A上的二元关系，R1=，R2=，试求R1和R2的自反闭包，对称闭包和传递闭包。解：r（R1）= R1IA=， s= R1 R1-1 =， R12 =，R13 =，t= R1 R12 R13 =，空关系R2的自反闭包，对称闭包和传递闭包均为。22.设A=a,b,c,d,A上的二元关系R=,求R的自反闭包r(R)，对称闭包s(R)和传递闭包t(R)。解: ,r(R)R, s(R)R, r(R), , , , , , , ,s(R), , , , , , , t(R),23.设集合A=a，b，c，A上的二元关系R=， ， ,试给出R，r(R)，s(R), t(R)的关系图。解：24.设A=a,b,c,写出集合A上的所有不同的划分和等价关系解：集合A上共有5种不同的划分: ， ， , ， 。每种划分对应的等价关系为:,.25.设A=a, b, c, d, e, f, A上的等价关系R=IA, ,求（1）a的等价类aR(2)求c的等价类cR(3)求商集A/R解：（1）a的等价类=a,b(2)c的等价类=c(3)商集A/R=a,b,c,d,e,f26分别画出下列各偏序集的哈斯图，并求A的极大元、极小元，最大元、最小元。(1)，A上的二元关系R为：(2)A=1，2，3，4，6，9，24，54，R是A上的整除关系。解：(1)R的哈斯图为：A的极大元、最大元都是eA的极小元、最小元都是a(2)R的哈斯图为：A的极大元是24、54A没有最大元A的极小元、最小元都是127.下图给出了一个偏序关系R的哈斯图。(1)写出二元关系R的关系式。(2)求子集b，c，d上的最大元、最小元、极大元、极小元、上界、上确界、下界、下确界。解：(1)R的关系式为：R,(2)子集b，c，d上的最大元:无子集b，c，d上的最小元、极小元：d子集b，c，d上的上界、上确界：a子集b，c，d上的下界:e,f,d, 下确界：d28设A=a,b,c,d,e，A上的偏序关系R，IA ，求：(1)画出偏序集的哈斯图；(2)求子集B=c,d,e的极大元，极小元，最大元，最小元，上确界，下确界。解：R的哈斯图为：B的极大元：c,dB的极小元：eB中无最大元B中的最小元：eB在偏序集中无上确界B在偏序集中的下确界：e29设A=,A上的包含关系R是P上的偏序关系，即P,R是偏序集,求该偏序集的哈斯图、最大元、最小元:解：P=,a,b,c,a,b,a,c,b,c,a,b,c，偏序关系R的哈斯图如下所示：R的最大元、最小元分别是a,b,c，。30.设A= a,b,c,d,e,给定p如下： =a,b,c,d,e, =a,b,c,d,e, =a,b,c,c,d,e, =a,d,e, =,a,b,c,d,e, =a,b,c,d,e, 问：哪些是A的划分？解: , 是A的划分.31实数集R上的三个函数,f(x)=3-x,g(x)=2x+1 ,h(x)=x/3,求gof, fog, (hog)f, 解:(gof)(x)=g(f(x)=g(3-x)=2(3-x)+1=7-2x;(fog)(x)=f(g(x)=f(2x+1)=2-2x;(hog)f)(x)=h(gof)(x)=h(g(f(x)=h(7-2x)=(7-2x)/3;=(7-x)/2 .32.画出下图G的补图。（3分）解：G的补图如下所示：33.已知无向图G有11条边，2度与3度顶点各2个，其余都是4度顶点，求G中共有几个顶点。（写出过程）解:我们知道一个有限图中，各结点的度数总和是边数的2倍,于是，设共有x个结点，得22+32+4（x22）211解得，x7所以图G中共有7个顶点34.下面的无向图G1和G2同构吗？为什么？答：无向图G1和G2不同构。因为图G2中有一个度为5的结点，而在G1中找不到。35.下面的有向图G1和G2同构吗？说明理由 （4分） 解：有向图G1和G2不同构。因为图G1中有一个度为5的结点，其中出度为3，入度为1，而在G2中虽然也有一个度为5 的结点，但它的出度为2，入度也是2。所以有向图G1和G2不同构。36.有向图G如图所示。用矩阵法求： （8分）（1）G中长度为2的通路有几条？（2）G中长度为3的回路有几条？（3）G的可达矩阵P。正确写出邻接矩阵给1分，求出（1）G中长度为2的通路有几条？（2）G中长度为3的回路有几条？各给2分，求出（3）G的可达矩阵P。给3分。解：图G的邻接矩阵为：依次计算得： 从而得，由矩阵得，长度为2的通路有7条，又由矩阵得，长度为3的回路有0条，而由矩阵B得，G的可达矩阵P为：37.有向图G如下所示。求：（1）图G的邻接矩阵A（G）；（2）从到长度为2和4的通路各有几条？（3）经过的长度不大于4的回路共有几条？（4）图G的可达矩阵P（G）解：（1）图G的邻接矩阵为：（2）依次计算得： 由矩阵的第一行第四列得，从到长度为2的通路有1条，又由矩阵的第一行第四列得，从到长度为4的通路有3条。（3）由矩阵的第四行第四列得，经过的长度不大于4的回路共有3条（4），而由矩阵B得，G的可达矩阵P为：38.设有向图G=(V，E)如下图所示，(1) 试用邻接矩阵方法求长度为3的路的总数和回路总数；(2)求图G的可达矩阵解：（1）图G的邻接矩阵为：依次计算得： 由矩阵得，长度为3的路的总数为38；回路总数为11。（2）矩阵或得，可达矩阵P为：39用标号法求下面有限加权图从到的最短路径，并计算权值。(列表)（6分）解：计算结果列于下表中：(表格中的数字全对才给分)结点步骤1021/V127532/V175473/V1V256/V1V2V4968/V1V2V4V3所以，结点到的最短路径为，权值是8 。40用标号法求下面有限加权图从a到g的最短路径，并计算权值。(列表)（6分）解：计算结果列于下表中：结点步骤abcdefg1021/a7/a34/ab5/ab4/ab45/ab4/ab6/abc55/ab6/abc1166/abc7/abd7/abd所以，从a到g的最短路径是abdg，权值为7。41用标号法求下面有限加权图从a到i的最短路径，并计算权值。(列表)解：计算结果列于下表中：结点步骤abcdefghi1022/a2/a732/a6/ab4/ab43/ac6/abc4/ab56/acd4/acd1165/acdf7/acdf11/acdf12/acdf77/acdf11/acdf11/acdfe810/acdfg11/acdfe911/acdfe所以，从a到i的最短路径是acdfei，权值为11。42有向图PERT图如下所示：（1）求图中各顶点的最早完成时间；（2）求图中各顶点的最晚完成时间；（3）求图中的关键路径。解：（1）（2）图中各顶点的最早完成时间和各顶点的最晚完成时间的计算结果标记在下图的各个顶点处，其中左边数字是该顶点的最早完成时间，右边数字是该顶点的最晚完成时间。（3）由于最早完成时间和最晚完成时间相等的顶点在关键路径，不难看出，关键路径是adfh.43有向图PERT图如下所示：（1）求图中各顶点的最早完成时间；（2）求图中各顶点的最晚完成时间；（3）求图中的关键路径。解：（1）（2）图中各顶点的最早完成时间和各顶点的最晚完成时间的计算结果标记在下图的各个顶点处，其中左边数字是该顶点的最早完成时间，右边数字是该顶点的最晚完成时间。（3）由于最早完成时间和最晚完成时间相等的顶点在关键路径，且关键路径上的每一条边都是关键活动，不难看出，关键路径是和.44.现需涉及一个有6个元件的电路，把6个元件分成两组，每组3个元件，设计要求每组中的任一个元件必须与另一组中的所有元件用导线连接。问能否设计电路使导线不交叉？如果能，画出设计方案，如果不能，说明理由，并画出一个导线交叉最少的设计方案。解：依题意，问题可转化为判断下图是否为可平面图。由于该图是K3，3，它是不可平面图。导线交叉最少的设计方案是下图所示（仅一个交叉）：45已知关于人员a，b，c，d，e，f和g的下述事实：a说英语；b说英语和西班牙语；c说英语，意大利语和俄语；d说日语和西班牙语；e说德语和意大利语；f说法语，日语和俄语；g说法语和德语。试问：上述7人中是否任意两人都能交谈（如有必要，可由其余5人中所组成的译员链帮忙）？解：（1）设7个人为7个结点，将两个能懂同一语言的人之间连一条边（即他们能直接交谈）。这样就得到一简单图G，问题就转化为G是否连通。得G为连通图，如下所示。因此，上述7人中任意两个能交谈。46有张、王、李、赵四位教师，要分配他们教数学、物理、计算机导论、数据结构等四门课程。张熟悉物理和数据结构，王熟悉数学和计算机导论，李熟悉物理、数学和数据结构，赵只熟悉数据结构。(1) 画出关于教师熟悉课程的二部图。(2) 如何分配，才能使每位教师都教一门自己熟悉的课程？（1）设四位教师张、王、李、赵分别为四个结点张、王、李、赵，四门课程数学、物理、计算机导论、数据结构分别为另外的四个结点数、物、计、结，教师与其熟悉的课程间就连一条线，即得相应的二部图，如下所示：（2）分配方法如下所示：47.求下图G的一棵最小生成树，并求它的权W（T） （5分）解：图G的一棵最小生成树如下所示，它的权W（T）=1148.设无向图G如下所示：求最小生成树T。解：按照Kruskal给出的在权图中求最优支撑树的算法，可生成下面的最优支撑树：（权和为15）49.用克鲁斯卡尔算法求带权图的最小生成树，并求权W(T)解：按照Kruskal给出的在权图中求最优支撑树的算法，可生成下面的最优支撑树：（权和为24）50.利用算法求出下面各加权图的最小生成树及其