离散数学屈婉玲版课后习题汇总

第一章部分课后习题参考答案16设p、q的真值为0;r、s的真值为1,求下列各命题公式的真值。(1)pVqO0VAO()(一)八]VO(-1)A1OaO()(「A「A)-AA]o(aA)-AAoLA)fA「o(A)fAOfO17.判断下面一段论述是否为真：“兀是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除,6才能被4整除。”答：p:兀是无理数13是无理数02是无理数16能被2整除16能被4整除0命题符号化为：pA(qfr)A(tfs)的真值为1,所以这一段的论述为真。19．用真值表判断下列公式的类型：(pfq)f(「qf「p)(pAr)»(「pA「q)(6)((pfq)A(qfr))f(pfr)答：(4)pqpfq「q「p「qf「p(pfq)f(「qf「p)0011111011011110010011110011所以公式类型为永真式(5)公式类型为可满足式(方法如上例)(6)公式类型为永真式(方法如上例)第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值.(1)](pAqfq)(2)(pf(pVq))V(pfr)(3)(pVq)f(pAr)答：(2)(pf(pVq))V(pfr)O(「pV(pVq))V(「pVr)O「pVpVqVrO1所以公式类型为永真式PqrpVqpAr(pVq)f(pAr)000001001001010100011100100100101111110100111111所以公式类型为可满足式用等值演算法证明下面等值式：f）fop八八」V「八Op八」八证明（）。）fo「V八」Vo「V八ofAA「V「AoV」AA」V」AoV「AVA」V」A」Vo1AAA「AAoV）「A求下列公式的主析取范式与主合取范式，并求成真赋值「ff「V「。AAVAfVV解：（）主析取范式「f）「vo「A）」Vo「A「V」Vo「A「V「AV「A「VAVA「omvmvm023oE主合取范式：「ff「vo「AV「V0Av-0p-oon主合取范式为：-vAAo——V）A0A-AA0所以该式为矛盾式主合取范式为n矛盾式的主析取范式为主合取范式为：vAfVVo-vAfVVO-A-V-VVVO-VVVA-V-A/VV0A0所以该式为永真式永真式的主合取范式为主析取范式为£第三章部分课后习题参考答案在自然推理系统中构造下面推理的证明：前提：-「A结论：-前提：—仆3A结论：A证明：（）①「A前提引入②「V-①置换③”「②蕴含等值式④前提引入⑤「③④拒取式前提引入⑤⑥拒取式证明（）:①证明（）:①人②③妗④妗⑤匕⑥（f）A⑦（）⑧⑨1⑩前提引入①化简律前提引入前提引入③④等价三段论—⑤置换⑥化简②⑥假言推理前提引入⑧⑨假言推理⑧⑩合取在自然推理系统中用附加前提法证明下面各推理:在自然推理系统中用附加前提法证明下面各推理:前提：—T,结论：-证明附加前提引入—前提引入①②假言推理④——前提引入—③④假言推理前提引入⑤⑥假言推理在自然推理系统中用归谬法证明下面各推理:前提：——1—1VA—I结论：—证明：①结论的否定引入②—「前提引入③[①②假言推理

④1V前提引入⑤「④化简律⑥入「前提引入⑦⑥化简律⑧入「⑤⑦合取由于最后一步A「是矛盾式所以推理正确第四章部分课后习题参考答案在一阶逻辑中将下面将下面命题符号化并分别讨论个体域限制为条件时命题的真值对于任意均有错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。).存在使得其中个体域为自然数集合个体域为实数集合解：错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。在两个个体域中都解释为VxF(x)，在()中为假命题，在中为真命题。在两个个体域中都解释为3在两个个体域中都解释为3xG(x)，在()中对均为真命题。.在一阶逻辑中将下列命题符号化:(1对没有不能表示成分数的有理数.(2对在北京卖菜的人不全是外地人.解:能表示成分数是有理数命题符号化为「3x(「F(x)aH(x))是北京卖菜的人是外地人命题符号化为「Vx(F(x)TH(x)).在一阶逻辑将下列命题符号化:火车(都1比对轮船快.不存(在3比对所有火车都快的汽车.解:是火车是轮船比快命题符号化为VxVy((F(x)aG(y))fH(x,y))是火车是汽车比快命题符号化为「方(G(y)aVx(F(x)fH(x,y)))给定解释如下个体域为实数集合中特定元素错误！未找到引用源。特定函数错误！未找到引用源。错误！未找到引用源。£。错误！未找到引用源。给特定谓词错误！未找到引用源。错误！未找到引用源。eD说明下列公式在下的含义并指出各公式的真值VxVy(G(x,y)f「F(x,y))(2V)xVy(F(f(x,y),a)fG(x,y))答对于任意两个实数如果那么w真值对于任意两个实数如果那么真值给定解释如下：()个体域为自然数集合()中特定元素错误！未找到引用源。()上函数错误！未找到引用源。错误！未找到引用源。()上谓词错误！未找到引用源。说明下列各式在下的含义，并讨论其真值错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。一答对于任意自然数都有真值对于任意两个自然数使得如果那么真值11给判断下列各式的类型:(1对错误！未找到引用源。错误！未找到引用源。解因为pf(qfp)O「pv(「qvp)o1为永真式；所以错误！未找到引用源。为永真式；取解释个体域为全体实数所以前件为任意实数存在实数使，前件真；后件为存在实数对任意实数都有，后件假，此时为假命题再取解释个体域为自然数所以前件为任意自然数存在自然数使，前件假。此时为假命题。此公式为非永真式的可满足式。13.给定下列各公式一个成真的解释，一个成假的解释。错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。解:（个1体）域:本班同学:会吃饭：会睡觉成真解释:是泰安人：是济南人（）成假解释（2个误体域:泰山学院的学生:出生在山东出生在北京出生在江苏成假解释:会吃饭：会睡觉：会呼吸成真解释第六章部分课后习题参考答案确.定下列命题是否为真：TOC\o"1-5"\h\z()0=0真()0£0假(3)0={0}真()0e{0}真(){}={{}}真(){}e{}}}真(){}={{}}}}真(){}e}}}}}假.设各不相同，判断下述等式中哪个等式为真(1)}}a}}b，c}0}=}}a}}b}c}假(2)}a}}b=}}aa}}b真(3)}}a}，{b}}=}}a}}}b假()}0,}0},}}0}0}}}假．求下列集合的幂集：()}}0()}1}2}}0,

（）{0}0{0}（）{0,{0}}0,,.化简下列集合表达式：（）（u）n）（u）（）（（uu）（u））u解（u）n）（u）（u）n）n〜」）（u）n〜（u）n0n0（）（（uu）（u））u（（uu）n〜（u））u（n〜（u））u（（u）n〜（u））u（n〜（u））u0u（n〜（u））u.某班有个学生，其中人会打篮球，人会打排球，人会打篮球和排球，人会打篮球（）un（）（）nunnn00（）un0、设是任意集合，证明证明b〜n〜ri〜ri〜n〜。。n〜n〜n〜n〜n〜un〜n〜un〜nn〜n〜u°n〜uu由（）得证。第七章部分课后习题参考答案.列出集合A={2,3,4}上的恒等关系IA，全域关系Ea，小于或等于关系La，整除关系Da.解：，13.设A={<1,2>,<2,4>,<3,3>}B={<1,3>,<2,4>,<4,2>}求AuB,ACB,domA,domB,dom(AuB),ranA,ranB,ran(ACB),fld(A-B).解：uCVC214.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求R。R,R-1,R个{0,1,},R[{1,2}]解：。R-1,个16.设A={a,b,c,d},RR为A上的关系，其中1,2R{a,a,a,b,b,d}1=R={a,d,b,c,b,d,c,b2求RR,RR,R2,R3。TOC\o"1-5"\h\z122112.设，，，，在X上定义二元关系，V£X,〈O证明是X上的等价关系确定由引起的对X的划分()证明：：O・•・是自反的任意的£X如果，那么••

••••・•・是对称的任意的£X若贝U・•・是传递的・•・是X上的等价关系n设人={1,2,3,4},R为AxA上的二元关系，V〈a,b〉，〈c,d〉£AxA,〈a,b〉R〈c,d〉O(1)证明为等价关系.

求R导出的划分证明：Va,b〉EAxA*••・•・是自反的TOC\o"1-5"\h\z任意的£X设，贝c••

••••・•・是对称的任意的£X若则••

••••・•・是传递的・•・是X上的等价关系n对于下列集合与整除关系画出哈斯图下图是两个偏序集，的哈斯图分别写出集合和偏序关系.的集合表达式

下图是两个偏序集，的哈斯图分别写出集合和偏序关系.的集合表达式,<A,e,<AA分别画出下列各偏序集,的哈斯图并找出的极大元极小元最大元和最小元(1)项目极大元:极小元:最大元:最小元:able(1)项目极大元:极小元:最大元:最小元:c(2)第八章部分课后习题参考答案1.设f:NfN,且工若x为奇数f(x)=I-若x为偶数

[2,f-1({3,5,7}).求f(0),f({0}),f(1),f({1}),f({0,2,4,6,…}),f({4,6,8}),

解：f(0)=0,f({0})={0},ff-1({3,5,7}).f({0,2,4,6,…})=N,f({4,6,8})={2,3,4},f-1({3,5,7})={6,10,14}.4.判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的?(1)f:NT(1)f:NTN,f(x)=x2+2不是满射，不是单射(2)f:NTN,f(x)=(x)mod3,x除以3的余数不是满射，不是单射不是满射，不是单射是满射,不是单射[1,若x为奇数不是满射，不是单射是满射,不是单射⑶f：NTN^10,若x为偶数[0,若x为奇数f：NT{0，1}，f(x)=]l,若x为偶数f:N-{0}TR,f(x)=lgx不是满射,是单射f:RTR,f(x)=x2-2x-15不是满射,不是单射X={a,b,c,d},Y={1,2,3},f={<a,1>,<b,2>,<c,3>,}判断以下命题的真假:(1)f是从X到Y的二元关系，但不是从X到Y的函数；对TOC\o"1-5"\h\z(2)f是从X到Y的函数，但不是满射，也不是单射的；错(3)f是从X到Y的满射，但不是单射；错(4)f是从X到Y的双射.错第十四章部分课后习题参考答案5、设无向图有条边，度与度顶点各个，其余顶点的度数均小于，问至少有多少个顶点？在最少顶点的情况下，写出度数列、A(G)、b(G)。解：由握手定理图的度数之和为：2x10=203度与4度顶点各2个,这4个顶点的度数之和为14度。其余顶点的度数共有6度。其余顶点的度数均小于，欲使的顶点最少，其余顶点的度数应都取所以，至少有个顶点出度数列为A(G)=4,8(G)=27设有向图的度数列为，，，，出度列为，，，，求的入度列，并求A(D),8(D)，A+(D),8+(D)A-(D),8-(D)解：的度数列为，3,3出度列为，，，，的入度列为A(D)=3,8(D)=2A+(D)=2,8+(D)=1A-(D)=2,8-(D)=18、设无向图中有6条边,3度与5度顶点各，个,其余顶点都是，度点,问该图有多少个顶点？解：由握手定理图的度数之和为：2x6=12

x=2，该图有个顶点设度点X个，贝u3X1+5X1+2Xx=2，该图有个顶点14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。解：(1(2)＋是+奇4数+，4不+可5解：(1(2)＋是+偶4数+，4可=图1化6；,18、设有3个4阶4条边的无向简单图G/G2、G3,证明它们至少有两个是同构的。证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个：所以，G1、G2、G3至少有两个是同构的。20、已知n阶无向简单图G有m条边，试求G的补图G的边数m'。解：21、无向图G如下图(1)求G的全部点割集与边割集，指出其中的割点和桥;(2)求G的点连通度k(G)与边连通度入(G)。解：点割集:{a,b},(d)边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}k(G)=入(G)=123、求G的点连通度k(G)、边连通度入(G)与最小度数5(G)。23、解：k(G)=2、入(G)=3、5(G)=428、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？13n=2m解：<得n=6,m=9.[2n—3=m31、试确定G的阶数。31、试确定G的阶数。设图G和它的部图G的边数分别为m和m，一n一n(n+1)解：m+m=2—1+1+8(m+m)得n=245、45、有向图D如图⑴求V2⑴求V2到V5长度为1⑵求V5到V5长度为12，3，4的通路数；2，3，4的回路数；⑶求D中长度为4的通路数；(4)求D中长度小于或等于4的回路数;(5)写出D的可达矩阵。解：有向图D的邻接矩阵为:f0101、00000101010f0101、000001010100000110100f0000、21010000002101000]2020,A3202000202020200020200]004f0f00004]40400A4=0000440400、04040,5，，，，-A+A2+A3+A4=24122522121525225254)⑴v2到肘5长度为1,2,3,4的通路数为0,2,0,0；⑵v5到v5长度为1,2,3,4的回路数为0,0,4,0；⑶D中长度为4的通路数为32；(4)D中长度小于或等于4的回路数10；f11111]

11111(4)出D的可达矩阵尸=1111111111j1111)第十六章部分课后习题参考答案1、画出所有5阶和7阶非同构的无向树.2、一棵无向树2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点?解：设3度分支点了个，则5x1+3x2+31=2x(5+3+了-1)，解得了=3T有11个顶点3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。解：设4度分支点了个,则8x1+2x3+4x=2x(8+2+x—1),解得x=2度数列1111111133444、棵无向树T有n,(i=2,3,…，错误！未找到引用源。个度分支点，其余顶点都是树叶，问T应该有几片树叶解：设树叶x片，则nxi+xx1=2x(n+x-1)，解得x=(i—2)n+2,,,评论：2,3,4题都是用了两个结论,一是握手定理，二是m=n—15、n(nN阶无向树T的最大度错误！未找到引用源。至少为几？最多为几？解：2,n-16、若n(nN阶无向树T的最大度错误！未找到引用源。，问T中最长的路径长度为几？解：n-17、证明：n(nN阶无向树不是欧拉图证明：无向树没有回路,因而不是欧拉图。8、证明：n(nN阶无向树不是哈密顿图证明：无向树没有回路,因而不是哈密顿图。9、证明：任何无向树T都是二部图.证明：无向树没有回路,因而不存在技术长度的圈,是二部图。10、什么样的无向树T既是欧拉图，又是哈密顿图解：一阶无向树14、设e为无向连通图G中的一条边，e在G的任何生成树中，问e应有什么性质？解：e是桥15、设e为无向连通图G中的一条边，e不在G的任何生成树中，问e应有什么性质？解：e是环23、已知n阶m条的无向图G是k(kN2)棵树组成的森林，证明：m=n-k.；证明：数学归纳法。k=1时,m=n-1,结论成立