《离散数学》 习题解答.pdf 63页

'离散数学习题解3习题一1.1．略1.2．略1.3．略1.4．略1.5．略1.6．略1.7．略1.8．略1.9．略1.10．略1.11．略1.12．将下列命题符号化,并给出各命题的真值:(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4的充要条件是3+3≠6.(3)2+2≠4与3+3＝6互为充要条件.(4)若2+2≠4,则3+3≠6,反之亦然.(1)p↔q,其中,p:2+2＝4,q:3+3＝6,真值为1.(2)p↔¬q,其中,p:2+2＝4,q:3+3＝6,真值为0.(3)¬p↔q,其中,p:2+2＝4,q:3+3＝6,真值为0.(4)¬p↔¬q,其中,p:2+2＝4,q:3+3＝6,真值为1.1.13．将下列命题符号化,并给出各命题的真值:(1)若今天是星期一,则明天是星期二.(2)只有今天是星期一,明天才是星期二.(3)今天是星期一当且仅当明天是星期二.(4)若今天是星期一,则明天是星期三.令p:今天是星期一;q:明天是星期二;r:明天是星期三.(1)p→q⇔1.(2)q→p⇔1.(3)p↔q⇔1.(4)p→r当p⇔0时为真;p⇔1时为假.1.14．将下列命题符号化.(1)刘晓月跑得快,跳得高.(2)老王是山东人或河北人.(3)因为天气冷,所以我穿了羽绒服.(4)王欢与李乐组成一个小组.(5)李辛与李末是兄弟.(6)王强与刘威都学过法语.(7)他一面吃饭,一面听音乐.(8)如果天下大雨,他就乘班车上班.(9)只有天下大雨,他才乘班车上班.(10)除非天下大雨,他才乘班车上班.(11)下雪路滑,他迟到了.(12)2与4都是素数,这是不对的.(13)“2或4是素数,这是不对的”是不对的. 离散数学习题解4(1)p∧q,其中,p:刘晓月跑得快,q:刘晓月跳得高.(2)p∨q,其中,p:老王是山东人,q:老王是河北人.(3)p→q,其中,p:天气冷,q:我穿了羽绒服.(4)p,其中,p:王欢与李乐组成一个小组,是简单命题.(5)p,其中,p:李辛与李末是兄弟.(6)p∧q,其中,p:王强学过法语,q:刘威学过法语.(7)p∧q,其中,p:他吃饭,q:他听音乐.(8)p→q,其中,p:天下大雨,q:他乘班车上班.(9)p→q,其中,p:他乘班车上班,q:天下大雨.(10)p→q,其中,p:他乘班车上班,q:天下大雨.(11)p→q,其中,p:下雪路滑,q:他迟到了.(12)¬(p∧q)或¬p∨¬q,其中,p:2是素数,q:4是素数.(13)¬¬(p∨q)或p∨q,其中,p:2是素数,q:4是素数.1.15．设p:2+3=5.q:大熊猫产在中国.r:复旦大学在广州.求下列复合命题的真值:(1)(p↔q)→r(2)(r→(p∧q))↔¬p(3)¬r→(¬p∨¬q∨r)(4)(p∧q∧¬r)↔((¬p∨¬q)→r)(1)真值为0.(2)真值为0.(3)真值为0.(4)真值为1.注意:p,q是真命题,r是假命题.1.16．略1.17．略1.18．略1.19．用真值表判断下列公式的类型:(1)p→(p∨q∨r)(2)(p→¬q)→¬q(3)¬(q→r)∧r(4)(p→q)→(¬q→¬p)(5)(p∧r)↔(¬p∧¬q)(6)((p→q)∧(q→r))→(p→r)(7)(p→q)↔(r↔s) 离散数学习题解5(1),(4),(6)为重言式.(3)为矛盾式.(2),(5),(7)为可满足式.1.20．略1.21．略1.22．略1.23．略1.24．略1.25．略1.26．略1.27．略1.28．略1.29．略1.30．略1.31．将下列命题符号化,并给出各命题的真值:(1)若3+＝4,则地球是静止不动的.(2)若3+2＝4,则地球是运动不止的.(3)若地球上没有树木,则人类不能生存.(4)若地球上没有水,则3是无理数.(1)p→q,其中,p:2+2＝4,q:地球静止不动,真值为0.(2)p→q,其中,p:2+2＝4,q:地球运动不止,真值为1.(3)¬p→¬q,其中,p:地球上有树木,q:人类能生存,真值为1.(4)¬p→q,其中,p:地球上有水,q:3是无理数,真值为1. 离散数学习题解6习题二2.1.设公式A=p→q,B=p¬∧q,用真值表验证公式A和B适合德摩根律:¬(A∨B)⇔¬A¬∧B.pqA=p→qB=p¬∧q¬(A∨B)¬A¬∧B001000011000100100111000因为¬(A∨B)和¬A¬∧B的真值表相同,所以它们等值.2.2.略2.3.用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值.(1)¬(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)(1)¬(p∧q→q)⇔¬(¬(p∧q)∨q)⇔¬(¬p∨¬q∨q)⇔p∧q∧¬q⇔p∧0⇔0⇔0.矛盾式.(2)重言式.(3)(p∨q)→(p∧r)⇔¬(p∨q)∨(p∧r)⇔¬p¬∧q∨p∧r易见,是可满足式,但不是重言式.成真赋值为:000,001,101,111pqr¬p∧¬q∨p∧r00011110001111100101000001110000100001001010011111000000111000112.4.用等值演算法证明下面等值式:(1)p⇔(p∧q)∨(p∧¬q)(3)¬(p↔q)⇔(p∨q)∧¬(p∧q)(4)(p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)(1)(p∧q)∨(p∧¬q)⇔p∧(q¬∨q)⇔p∧1⇔p.(3)¬(p↔q) 离散数学习题解7⇔¬((p→q)∧(q→p))⇔¬((¬p∨q)∧(¬q∨p))⇔(p∧¬q)∨(q∧¬p)⇔(p∨q)∧(p∨¬p)∧(¬q∨q)∧(¬p∨¬q)⇔(p∨q)∧¬(p∧q)(4)(p∧¬q)∨(¬p∧q)⇔(p∨¬p)∧(p∨q)∧(¬q∨¬p)∧(¬q∨q)⇔(p∨q)∧¬(p∧q)2.5.求下列公式的主析取范式,并求成真赋值:(1)(¬p→q)→(¬q∨p)(2)¬(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)(1)(¬p→q)→(¬q∨p)⇔¬(p∨q)∨(¬q∨p)⇔¬p∧¬q∨¬q∨p⇔¬p∧¬q∨¬q∨p(吸收律)⇔(p¬∨p)¬∧q∨p∧(q¬∨q)⇔p¬∧q¬∨p¬∧q∨p∧q∨p¬∧q⇔m10∨m00∨m11∨m10⇔m0∨m2∨m3⇔∑(0,2,3).成真赋值为00,10,11.(2)主析取范式为0,无成真赋值,为矛盾式.(3)m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7,为重言式.2.6.求下列公式的主合取范式,并求成假赋值:(1)¬(q→¬p)∧¬p(2)(p∧q)∨(¬p∨r)(3)(p→(p∨q))∨r(1)¬(q¬→p)∧¬p⇔¬(¬q¬∨p)∧¬p⇔q∧p∧¬p⇔q∧0⇔0⇔M0∧M1∧M2∧M3这是矛盾式.成假赋值为00,01,10,11.(2)M4,成假赋值为100.(3)主合取范式为1,为重言式. 离散数学习题解82.7.求下列公式的主析取范式,再用主析取范式求合取范式:(1)(p∧q)∨r(2)(p→q)∧(q→r)(1)m1∨m3∨m5∨m6∨m7⇔M0∧M2∧M4(2)m0∨m1∨m3∨m7⇔M2∧M4∧M5∧M62.8.略2.9.用真值表求下面公式的主析取范式.(2)(p→q)→(p¬↔q)pq(p→q)→(p¬↔q)001001011110100111111000(2)从真值表可见成真赋值为01,10.于是(p→q)→(p¬↔q)⇔m1∨m2.2.10.略2.11.略2.12.略2.13.略2.14.略2.15.用主析取范式判断下列公式是否等值:(1)(p→q)→r与q→(p→r)(2)(p→q)→r⇔¬(¬p∨q)∨r⇔¬(¬p∨q)∨r⇔p¬∧q∨r⇔p¬∧q∧(r¬∨r)∨(p¬∨p)∧(q¬∨q)∧r⇔p¬∧q∧r∨p¬∧q∧¬r∨p∧q∧r∨p∧¬q∧r∨¬p∧q∧r∨¬p∧¬q∧r=m101∨m100∨m111∨m101∨m011∨m001⇔m1∨m3∨m4∨m5∨m7=∑(1,3,4,5,7).而q→(p→r)⇔¬q∨(¬p∨r)⇔¬q∨¬p∨r⇔(¬p∨p)¬∧q∧(¬r∨r)∨¬p∧(¬q∨q)∧(¬r∨r)∨(¬p∨p)∧(¬q∨q)∧r⇔(¬p¬∧q∧¬r)∨(¬p¬∧q∧r)∨(p¬∧q∧¬r)∨(p¬∧q∧r)∨(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧¬r)∨(¬p∧q∧r) 离散数学习题解9∨(¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧¬q∧r)∨(p∧q∧r)=m0∨m1∨m4∨m5∨m0∨m1∨m2∨m3∨m1∨m3∨m5∨m7⇔m0∨m1∨m2∨m3∨m4∨m5∨m7⇔∑(0,1,2,3,4,5,7).两个公式的主吸取范式不同,所以(p→q)→râq→(p→r).2.16.用主析取范式判断下列公式是否等值:(1)(p→q)→r与q→(p→r)(2)¬(p∧q)与¬(p∨q)(1)(p→q)→r)⇔m1∨m3∨m4∨m5∨m7q→(p→r)⇔m0∨m1∨m2∨m3∨m4∨m5∨m7所以(p→q)→r)âq→(p→r)(2)¬(p∧q)⇔m0∨m1∨m2¬(p∨q)⇔m0所以¬(p∧q)â¬(p∨q)2.17.用主合取范式判断下列公式是否等值:(1)p→(q→r)与¬(p∧q)∨r(2)p→(q→r)与(p→q)→r(1)p→(q→r)⇔M6¬(p∧q)∨r⇔M6所以p→(q→r)⇔¬(p∧q)∨r(2)p→(q→r)⇔M6(p→q)→r⇔M0∧M1∧M2∧M6所以p→(q→r)â(p→q)→r2.18.略2.19.略2.20.将下列公式化成与之等值且仅含{¬,→}中联结词的公式.(3)(p∧q)↔r.注意到A↔B⇔(A→B)∧(B→A)和A∧B⇔¬(¬A¬∨B)⇔¬(A¬→B)以及A∨B⇔¬A→B.(p∧q)↔r 离散数学习题解10⇔(p∧q→r)∧(r→p∧q)⇔(¬(p¬→q)→r)∧(r→¬(p¬→q))⇔¬((¬(p¬→q)→r)→¬(r→¬(p¬→q)))注F联结词越少,公式越长.2.21.证明:(1)(p↑q)⇔(q↑p),(p↓q)⇔(q↓p).(p↑q)⇔¬(p∧q)⇔¬(q∧p)⇔(q↑p).(p↓q)⇔¬(p∨q)⇔¬(q∨p)⇔(q↓p).2.22.略2.23.略2.24.略2.25.设A,B,C为任意的命题公式.(1)若A∨C⇔B∨C,举例说明A⇔B不一定成立.(2)已知A∧C⇔B∧C,举例说明A⇔B不一定成立.(3)已知¬A⇔¬B,问:A⇔B一定成立吗?(1)取A=p,B=q,C=1(重言式),有A∨C⇔B∨C,但AâB.(2)取A=p,B=q,C=0(矛盾式),有A∧C⇔B∧C,但AâB.好的例子是简单,具体,而又说明问题的.(3)一定.2.26.略2.27.某电路中有一个灯泡和三个开关A,B,C.已知在且仅在下述四种情况下灯亮:(1)C的扳键向上,A,B的扳键向下.(2)A的扳键向上,B,C的扳键向下.(3)B,C的扳键向上,A的扳键向下.(4)A,B的扳键向上,C的扳键向下.设F为1表示灯亮,p,q,r分别表示A,B,C的扳键向上.(a)求F的主析取范式.(b)在联结词完备集{¬,∧}上构造F.(c)在联结词完备集{¬,→,↔}上构造F.(a)由条件(1)-(4)可知,F的主析取范式为F⇔(¬p∧¬q∧r)∨(p∧¬q∧¬r)∨(¬p∧q∧r)∨(p∧q∧¬r)⇔m1∨m4∨m3∨m6⇔m1∨m3∨m4∨m6 离散数学习题解11(b)先化简公式F⇔(¬p∧¬q∧r)∨(p∧¬q∧¬r)∨(¬p∧q∧r)∨(p∧q∧¬r)⇔¬q∧((¬p∧r)∨(p∧¬r))∨q∧((¬p∧r)∨(p∧¬r))⇔(¬q∨q)∧((¬p∧r)∨(p∧¬r))⇔(¬p∧r)∨(p∧¬r)⇔¬(¬(¬p∧r)∧¬(p∧¬r))(已为{¬,∧}中公式)(c)F⇔(¬p∧r)∨(p∧¬r)⇔¬¬(¬p∧r)∨(p∧¬r)⇔¬(¬p∧r)→(p∧¬r)⇔(p∨¬r)→¬(¬p∨r)⇔(r→p)→¬(p→r)(已为{¬,→,↔}中公式)2.28.一个排队线路,输入为A,B,C,其输出分别为FA,FB,FC.本线路中,在同一时间内只能有一个信号通过,若同时有两个和两个以上信号申请输出时,则按A,B,C的顺序输出.写出FA,FB,FC在联结词完备集{¬,∨}中的表达式.根据题目中的要求,先写出FA,FB,FC的真值表(自己写)由真值表可先求出他们的主析取范式,然后化成{¬,∧}中的公式FA⇔m4∨m5∨m6∨m7⇔p(已为{¬,∧}中公式)FB⇔m2∨m3⇔¬p∧q(已为{¬,∧}中公式)FC⇔m1⇔¬p∧¬q∧r(已为{¬,∧}中公式)2.29.略2.30.略 离散数学习题解12习题三3.1.略3.2.略3.3.略3.4.略3.5.略3.6.判断下面推理是否正确.先将简单命题符号化,再写出前提,结论,推理的形式结构(以蕴涵式的形式给出)和判断过程(至少给出两种判断方法):(1)若今天是星期一,则明天是星期三；今天是星期一.所以明天是星期三.(2)若今天是星期一,则明天是星期二；明天是星期二.所以今天是星期一.(3)若今天是星期一,则明天是星期三；明天不是星期三.所以今天不是星期一.(4)若今天是星期一,则明天是星期二；今天不是星期一.所以明天不是星期二.(5)若今天是星期一,则明天是星期二或星期三.(6)今天是星期一当且仅当明天是星期三；今天不是星期一.所以明天不是星期三.设p:今天是星期一,q:明天是星期二,r:明天是星期三.(1)推理的形式结构为(p→r)∧p→r此形式结构为重言式,即(p→r)∧p⇒r所以推理正确.(2)推理的形式结构为(p→q)∧q→p此形式结构不是重言式,故推理不正确.(3)推理形式结构为(p→r)∧¬r→¬p此形式结构为重言式,即(p→r)∧¬r⇒¬p故推理正确.(4)推理形式结构为(p→q)∧¬p→¬q此形式结构不是重言式,故推理不正确.(5)推理形式结构为p→(q∨r)它不是重言式,故推理不正确.(6)推理形式结构为(p⇒r)∧¬p→¬r 离散数学习题解13此形式结构为重言式,即(p⇒r)∧¬p⇒¬r故推理正确.推理是否正确,可用多种方法证明.证明的方法有真值表法,等式演算法.证明推理正确还可用构造证明法.下面用构造证明法证明(6)推理正确.前提:p⇒r,¬p结论:¬r证明:①p⇒r前提引入②(p→r)∧(r→p)①置换③r→p②化简律④¬p前提引入⑤¬r③④拒取式所以,推理正确.3.7.略3.8.略3.9.用三种方法(真值表法,等值演算法,主析取范式法)证明下面推理是正确的:若a是奇数,则a不能被2整除.若a是偶数,则a能被2整除.因此,如果a是偶数,则a不是奇数.令p:a是奇数;q:a能被2整除;r:a是偶数.前提:p→¬q,r→q.结论:r→¬p.形式结构:(p→¬q)∧(r→q)→(r→¬p).……3.10.略3.11.略3.12.略3.13.略3.14.在自然推理系统P中构造下面推理的证明:(1)前提:p→(q→r),p,q结论:r∨s(2)前提:p→q,¬(q∧r),r结论:¬p(3)前提:p→q结论:p→(p∧q)(4)前提:q→p,q⇒s,s⇒t,t∧r结论:p∧q(5)前提:p→r,q→s,p∧q 离散数学习题解14结论:r∧s(6)前提:¬p∨r,¬q∨s,p∧q结论:t→(r∨s)(1)证明:①p→(q→r)前提引入②p前提引入③q→r①②假言推理④q前提引入⑤r③④假言推理⑥r∨s⑤附加律(2)证明:①¬(q∧r)前提引入②¬q∨¬r①置换③r前提引入④¬q②③析取三段论⑤p→q前提引入⑥¬p④⑤拒取式(3)证明:①p→q前提引入②¬p∨q①置换③(¬p∨q)∧(¬p∨p)②置换④¬p∨(p∧q)③置换⑤p→(p∧q)④置换也可以用附加前提证明法,更简单些.(4)证明:①s⇒t前提引入②(s→t)∧(t→s)①置换③t→s②化简④t∧r前提引入⑤t④化简⑥s③⑤假言推理⑦q⇒s前提引入⑧(s→q)∧(q→s)⑦置换⑨s→q⑧化简⑩q⑥⑥假言推理 离散数学习题解15○11q→p前提引入○12p⑩○11假言推理○13p∧q⑩○12合取(5)证明:①p→r前提引入②q→s前提引入③p∧q前提引入④p③化简⑤q③化简⑥r①④假言推理⑦s②⑤假言推理⑧r∧s⑥⑦合取(6)证明:①t附加前提引入②¬p∨r前提引入③p∧q前提引入④p③化简⑤r②④析取三段论⑥r∨s⑤附加说明:证明中,附加提前t,前提¬q∨s没用上.这仍是正确的推理.3.15.在自然推理系统P中用附加前提法证明下面各推理:(1)前提:p→(q→r),s→p,q结论:s→r(2)前提:(p∨q)→(r∧s),(s∨t)→u结论:p→u(1)证明:①s附加前提引入②s→p前提引入③p①②假言推理④p→(q→r)前提引入⑤q→r③④假言推理⑥q前提引入⑦r⑤⑥假言推理 离散数学习题解16(2)证明:①P附加前提引入②p∨q①附加③(p∨q)→(r∧s)前提引入④r∧s②③假言推理⑤S④化简⑥s∨t⑤附加⑦(s∨t)→u前提引入⑧u⑥⑦假言推理3.16.在自然推理系统P中用归谬法证明下面推理:(1)前提:p→¬q,¬r∨q,r∧¬s结论:¬p(2)前提:p∨q,p→r,q→s结论:r∨s(1)证明:①P结论否定引入②p→¬q前提引入③¬q①②假言推理④¬r∨q前提引入⑤¬r③④析取三段论⑥r∧¬s前提引入⑦r⑥化简⑧¬r∧r⑤⑦合取⑧为矛盾式,由归谬法可知,推理正确.(2)证明:①¬(r∨s)结论否定引入②p∨q前提引入③p→r前提引入④q→s前提引入⑤r∨s②③④构造性二难⑥¬(r∨s)∧(r∨s)①⑤合取 离散数学习题解17⑥为矛盾式,所以推理正确.3.17.P5317.在自然推理系统P中构造下面推理的证明:只要A曾到过受害者房间并且11点以前没用离开,A就犯了谋杀罪.A曾到过受害者房间.如果A在11点以前离开,看门人会看到他.看门人没有看到他.所以A犯了谋杀罪.令p:A曾到过受害者房间;q:A在11点以前离开了;r:A就犯了谋杀罪;s:看门人看到A.前提:p¬∧q→r,p,q→s,¬s.结论:r.前提:p¬∧q→r,p,q→s,¬s;结论:r.证明:①¬s前提引入②q→s前提引入③¬q①②拒取④p前提引入⑤p¬∧q③④合取⑥p¬∧q→r前提引入⑦r⑤⑥假言推理3.18.在自然推理系统P中构造下面推理的证明.(1)如果今天是星期六,我们就要到颐和园或圆明园去玩.如果颐和园游人太多,我们就不去颐和园玩.今天是星期六.颐和园游人太多.所以我们去圆明园玩.(2)如果小王是理科学生,他的数学成绩一定很好.如果小王不是文科生,他必是理科生.小王的数学成绩不好.所以小王是文科学生.(3)明天是晴天,或是雨天；若明天是晴天,我就去看电影；若我看电影,我就不看书.所以,如果我看书,则明天是雨天.(1)令p:今天是星期六;q:我们要到颐和园玩;r:我们要到圆明园玩;s:颐和园游人太多.前提:p→(q∨r),s→¬q,p,s.结论:r.①p前提引入pp→q∨rss→¬q②p→q∨r前提引入③q∨r①②假言推理q∨r¬q④s前提引入r⑤s→¬q前提引入⑥¬q④⑤假言推理(1)的证明树⑦r③⑥析取三段论 离散数学习题解18(2)令p:小王是理科生,q:小王是文科生,r:小王的数学成绩很好.前提:p→r,¬q→p,¬r结论:q证明:①p→r前提引入¬qp→q②¬r前提引入③¬p①②拒取式¬p¬r→p④¬q→p前提引入⑤q③④拒取式(2)的证明树r(3)令p:明天是晴天,q:明天是雨天,r:我看电影,s:我看书.前提:p∨q,p→r,r→¬s结论:s→q证明:①s附加前提引入②r→¬s前提引入③¬r①②拒取式④p→r前提引入⑤¬p③④拒取式⑥p∨q前提引入⑦q⑤⑥析取三段论 离散数学习题解19习题四4.1.将下面命题用0元谓词符号化:(1)小王学过英语和法语.(2)除非李建是东北人,否则他一定怕冷.(1)令F(x):x学过英语;F(x):x学过法语;a:小王.符号化为F(a)∧F(b).或进一步细分,令L(x,y):x学过y;a:小王;b1:英语;b2:法语.则符号化为L(a,b1)∧L(a,b2).(2)令F(x):x是东北人;G(x):x怕冷;a:李建.符号化为¬F(a)→G(a)或¬G(a)→F(a).或进一步细分,令H(x,y):x是y地方人;G(x):x怕冷;a:小王;b:东北.则符号化为¬H(a,b)→G(a)或¬G(a)→H(a,b).4.2.在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为(a),(b)时命题的真值:(1)凡有理数都能被2整除.(2)有的有理数能被2整除.其中(a)个体域为有理数集合,(b)个体域为实数集合.(1)(a)中,∀xF(x),其中,F(x):x能被2整除,真值为0.(b)中,∀x(G(x)∧F(x)),其中,G(x):x为有理数,F(x)同(a)中,真值为0.(2)(a)中,∃xF(x),其中,F(x):x能被2整除,真值为1.(b)中,∃x(G(x)∧F(x)),其中,F(x)同(a)中,G(x):x为有理数,真值为1.4.3.在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为(a),(b)时命题的真值:2(1)对于任意的x,均有x−2=(x+2)(x−2).(2)存在x,使得x+5=9.其中(a)个体域为自然数集合,(b)个体域为实数集合.2(1)(a)中,∀x(x−2=(x+2)(x−2)),真值为1.2(b)中,∀x(F(x)→(x−2=(x+2)(x−2)))),其中,F(x):x为实数,真值为1.(2)(a)中,∃x(x+5=9),真值为1.(b)中,∃x(F(x)∧(x+5=9)),其中,F(x):x为实数,真值为1.4.4.在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人. 离散数学习题解20(3)乌鸦都是黑色的.(4)有的人天天锻炼身体.没指定个体域,因而使用全总个体域.(1)¬∃x(F(x)∧¬G(x))或∀x(F(x)→G(x)),其中,F(x):x为有理数,G(x):x能表示成分数.(2)¬∀x(F(x)→G(x))或∃x(F(x)∧¬G(x)),其中,F(x):x在北京卖菜,G(x):x是外地人.(3)∀x(F(x)→G(x)),其中,F(x):x是乌鸦,G(x):x是黑色的.(4)∃x(F(x)∧G(x)),其中,F(x):x是人,G(x):x天天锻炼身体.4.5.在一阶逻辑中将下列命题符号化:(1)火车都比轮船快.(2)有的火车比有的汽车快.(3)不存在比所有火车都快的汽车.(4)“凡是汽车就比火车慢”是不对的.因为没指明个体域,因而使用全总个体域(1)∀x∀y(F(x)∧G(y)→H(x,y)),其中,F(x):x是火车,G(y):y是轮船,H(x,y):x比y快.(2)∃x∃y(F(x)∧G(y)∧H(x,y)),其中,F(x):x是火车,G(y):y是汽车,H(x,y):x比y快.(3)¬∃x(F(x)∧∀y(G(y)→H(x,y)))或∀x(F(x)→∃y(G(y)∧¬H(x,y))),其中,F(x):x是汽车,G(y):y是火车,H(x,y):x比y快.(4)¬∀x∀y(F(x)∧G(y)→H(x,y))或∃x∃y(F(x)∧G(y)∧¬H(x,y)),其中,F(x):x是汽车,G(y):y是火车,H(x,y):x比y慢.4.6.略4.7.将下列各公式翻译成自然语言,个体域为整数集],并判断各命题的真假.(1)∀x∀y∃z(x−y=z);(2)∀x∃y(x⋅y=1).(1)可选的翻译:①“任意两个整数的差是整数.”②“对于任意两个整数,都存在第三个整数,它等于这两个整数相减.”③“对于任意整数x和y,都存在整数z,使得x−y=z.”选③,直接翻译,无需数理逻辑以外的知识.以下翻译意思相同,都是错的:å“有个整数,它是任意两个整数的差.”ç“存在一个整数,对于任意两个整数,第一个整数都等于这两个整数相减.”é“存在整数z,使得对于任意整数x和y,都有x−y=z.”这3个句子都可以符号化为∃z∀x∀y(x−y=z).X量词顺序不可随意调换.(2)可选的翻译: 离散数学习题解21①“每个整数都有一个倒数.”②“对于每个整数,都能找到另一个整数,它们相乘结果是零.”③“对于任意整数x,都存在整数y,使得x⋅y=z.”选③,是直接翻译,无需数理逻辑以外的知识.4.8.指出下列公式中的指导变元,量词的辖域,各个体变项的自由出现和约束出现:(3)∀x∃y(F(x,y)∧G(y,z))∨∃xH(x,y,z)∀x∃y(F(x,y)∧G(y,z))∨∃xH(x,y,z)前件∀x∃y(F(x,y)∧G(y,z))中,∀的指导变元是x,∀的辖域是∃y(F(x,y)∧G(y,z));∃的指导变元是y,∃的辖域是(F(x,y)∧G(y,z)).后件∃xH(x,y,z)中,∃的指导变元是x,∃的辖域是H(x,y,z).整个公式中,x约束出现两次,y约束出现两次,自由出现一次;z自由出现两次.4.9.给定解释I如下:(a)个体域DI为实数集合y.(b)DI中特定元素⎯a=0.(c)特定函数⎯f(x,y)=x−y,x,y∈DI.(d)特定谓词⎯F(x,y):x=y,⎯G(x,y):x3}(5)S5＝{〈x,y>|x,y∈]∧0≤x≤2∧−1≤y≤0}(1)S1={0,1,2,3,4,5,6,7,8,9}(2)S2={2,5}(3)S3={4,5,6,7,8,9,10,11}(4)S4=∅(5)S5={〈0,−1〉,〈1,−1〉,〈2,−1〉,〈0,0〉,〈1,0〉,〈2,0〉}6.3.略6.4.设F表示一年级大学生的集合,S表示二年级大学生的集合,M表示数学专业学生的集合,R表示计算机专业学生的集合,T表示听离散数学课学生的集合,G表示星期一晚上参加音乐会的学生的集合,H表示星期一晚上很迟才睡觉的学生的集合.问下列各句子所对应的集合表达式分别是什么?请从备选的答案中挑出来.(1)所有计算机专业二年级的学生在学离散数学课.(2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉.(3)听离散数学课的学生都没参加星期一晚上的音乐会.(4)这个音乐会只有大学一,二年级的学生参加.(5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会.备选答案:①T⊆G∪H②G∪H⊆T③S∩R⊆T④H＝G∪T⑤T∩G＝∅⑥F∪S⊆G⑦G⊆F∪S⑧S−(R∪M)⊆G⑥G⊆S−(R∩M)答案:(1)③S∩R⊆T(2)④H=G∪T(3)⑤T∩G=∅(4)⑦G⊆F∪S(5)⑧S−(R∪M)⊆G6.5.确定下列命题是否为真:(1)∅⊆∅(2)∅∈∅(3)∅⊆{∅}(4)∅∈{∅}(5){a,b}⊆{a,b,c,{a,b,c}} 离散数学习题解31习题七7.1.已知A={∅,{∅}},求A×P(A).A×P(A)={〈∅,∅〉,〈∅,{∅}〉,〈∅,{{∅}}〉,〈∅,{∅,{∅}}〉,〈{∅},∅〉,〈{∅},{∅}〉,〈{∅},{{∅}}〉,〈{∅},{∅,{∅}}〉}7.2.对于任意集合A,B,C,若A×B⊆A×C,是否一定有B⊆C成立?为什么?不一定,因为有反例:A=∅,B={1},C={2},B⊆C,A×B=∅=A×C.7.3.设A,B,C,D是任意集合,(1)求证(A∩B)×(C∩D)=(A×C)∩(B×D).(2)下列等式中哪个成立?那些不成立?对于成立的给出证明,对于不成立的举一反例.(A∪B)×(C∪D)=(A×C)(∪B×D)(A−B)×(C−D)=(A×C)−(B×D)(1)∀〈x,y〉〈x,y〉∈(A∩B)×(C∩D)⇔x∈A∩B∧y∈C∩D⇔(x∈A∧x∈B)∧(y∈C∧y∈D)⇔(x∈A∧y∈C)∧(x∈B∧y∈D)⇔〈x,y〉∈(A×B)∧〈x,y〉∈(C×D)⇔〈x,y〉∈A×B∩C×D(A∩B)×(C∩D)=(A×C)∩(B×D)(2)都不成立,反例:A={1,2},B={2,3},C={1,2},D={2,3}(A∪B)×(C∪D)={1,2,3}×{1,2,3}⊃(A×C)(∪B×D)(A−B)×(C−D)={1}×{1}⊂(A×C)−(B×D)7.4.略7.5.设A,B为任意集合,证明若A×A=B×B,则A=B.∀x,x∈A⇔〈x,x〉∈A×A⇔〈x,x〉∈B×B⇔x∈BA=B7.6.列出从集合A={1,2}到B={1}的所有的二元关系.R1=∅,R2={〈1,1〉},R2={〈2,1〉},R3={〈1,1〉,〈2,1〉}.7.7.列出集合A={2,3,4}上的恒等关系IA,全域关系EA,小于或等于关系LA,整除关系DA.IA={〈2,2〉,〈3,3〉,〈4,4〉}EA=A×A={〈2,2〉,〈2,3〉,〈2,4〉,〈3,2〉,〈3,3〉,〈3,4〉,〈4,2〉,〈4,3〉,〈4,4〉}LA={〈2,2〉,〈2,3〉,〈2,4〉,〈3,3〉,〈3,4〉,〈4,4〉}DA={〈2,2〉,〈2,4〉,〈3,3〉,〈4,4〉}7.8.列出集合A={∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}}上的包含关系.R⊆={〈∅,∅〉,〈∅,{∅}〉,〈∅,{∅,{∅}}〉,〈∅,{∅,{∅},{∅,{∅}}}〉,〈{∅},{∅}〉,〈{∅},{∅,{∅}}〉,〈{∅},{∅,{∅},〈∅,{∅}〉}〉,〈{∅,{∅}},{∅,{∅}}〉,〈{∅,{∅}},{∅,{∅},{∅,{∅}}}〉,〈{∅,{∅},{∅,{∅}}},{∅,{∅},{∅,{∅}}}〉}7.9.设A={1,2,4,6},列出下列关系R:(1)R={〈x,y〉|x,y∈A∧x+y≠2}(2)R={〈x,y〉|x,y∈A∧|x−y|=1} 离散数学习题解32(3)R={〈x,y〉|x,y∈A∧x/y∈A}(4)R={〈x,y〉|x,y∈A∧y为素数}(1)R={〈1,2〉,〈1,4〉,〈1,6〉,〈2,1〉,〈2,2〉,〈2,4〉,〈2,6〉,〈4,1〉,〈4,2〉,〈4,4〉,〈4,6〉,〈6,1〉,〈6,2〉,〈6,4〉,〈6,6〉}=EA−{〈1,1〉}(2)R={〈1,2〉,〈2,1〉}(3)R={〈1,1〉,〈2,2〉,〈4,4〉,〈6,6〉,〈2,1〉,〈4,2〉,〈4,1〉}(4)R={〈1,2〉,〈2,2〉,〈4,2〉,〈6,2〉}7.10.略7.11.Ri是X上的二元关系,对于x∈X定义集合Ri(x)={y|xRiy}.显然Ri(x)⊆X.如果X={−4,−3,−2,−1,0,1,2,3,4},且令R1={〈x,y〉|x,y∈X∧xd(u,v),而这与u和v之间距离的最大性假设矛盾.所以v,类似地u,不是割点.uwv14.35.35.设G是n阶无向简单图,n≥3且为奇数,证明G与⎯G中奇度顶点的个数相等.∀v∈V(G)=V(⎯G)=V(Kn)d⎯G(v)+dG(v)=dKn(v)=n−1为偶数(n为奇数)于是,若d⎯G(v)为奇数,必有dG(v)也为奇数.故⎯G与G中奇度顶点个数相等.14.36.36.无向完全图Kn中有几种非同构的偶圈,其长度分别为几?其中n≥4.14.37.37.n阶有向完全图中有几种非同构的圈圈,其长度分别为几?其中n≥2.14.38.38.n阶竞赛图种至多有几种非同构的圈?其中n≥3.14.39.39.若无向图G种恰有两个奇度顶点,证明这两个奇度顶点必然连通.14.40.40.(1)设u,v为无向完全图Kn种的任意两个不同的顶点,问d〈u,v〉为几?14.41.41.设G设无向简单图,δ(G)≥2,证明G种存在长度大于或等于δ(G)+1的圈.14.42.42.设D=〈V,E〉为一个有向图,且为简单图,δ(G)≥2,δ−(G)≥0,δ+(G)≥0,证明D中存在长度大于或等于max{δ−(G),δ+(G)}+1的圈.14.43.43.有向图D如图14.22所示.(1)D中有多少种非同构的圈?有多少种非同构的简单回路?(2)求a到d的短程线和距离d〈a,d〉.(3)求d到a的短程线和距离d〈d,a〉.(4)判断D是哪类连通图.(5)对D的基图讨论(1),(2),(3)三个问题.14.44.44.有向图D如图14.23所示.(1)D中v1到v4长度为1,2,3,4的通路各为几条?(2)D中v1到v1长度为1,2,3,4的回路各为几条?(3)D中长度为4的通路(不含回路)有多少条?长度为4的回路为多少条?(4)D中长度小于或等于4的通路为多少条?其中有多少条为回路?(5)写出D的可达矩阵.利用D的邻接矩阵的前4次幂解此题. 离散数学习题解63⎡⎤⎡⎤12001220⎢⎥⎢⎥00101010AA==⎢⎥⎢⎥,2⎢⎥⎢⎥10011210⎢⎥⎢⎥⎣⎦⎣⎦00101001⎡⎤⎡⎤32225642⎢⎥⎢⎥12102221AA34==⎢⎥⎢⎥,⎢⎥⎢⎥12214432⎢⎥⎢⎥⎣⎦⎣⎦12102221(1)v1到v4长度为1,2,3,4的通路数分别为0条,0条,2条,2条;(2)v1到v1长度为1,2,3,4的回路数分别为1条,1条,3条,5条;(3)D中长度为4的通路(不含回路)共33条,长度为4的回路共11条;(4)D中长度小于或等于4的通路共88条,其中22条是回路;(5)因为D是强联通图,所以可达矩阵为4阶全1阵.14.45.45.有向图D如图14.24所示.求:(1)v2到v5长度为1,2,3,4的通路数.(2)v5到v5长度为1,2,3,4的回路数.(3)D中长度为4的通路数.(4)D中长度小于或等于4的回路数.(5)写出D的可达矩阵.14.46.46.设D=〈V,E〉为4阶有向图,V={v1,v2,v3,v4},已知D的邻接矩阵为⎡⎤0210⎢⎥0010A=⎢⎥⎢⎥0001⎢⎥⎣⎦0011试求D中各顶点的入度与出度.14.47.47.无向图G=〈V,E〉,V={v1,v2,v3,v4},E={e1,e2,e3,e4,e5},其关联矩阵为⎡21110⎤⎢⎥01100MG()=⎢⎥.⎢00011⎥⎢⎥⎣00001⎦试在同构意义下画出G的图形.14.48.48.已知在完全二部图Kr,s中,2≤r≤s.(1)Kr,s中含有多少种非同构的圈?(2)Kr,s中至多有多少个顶点彼此不相邻?(3)Kr,s中至多有多少条边彼此不相邻?(4)Kr,s的点连通度κ为几?边连通度λ为几?解(1)当r=1时,没有长度大于等于1的圈.当2≤r≤s时,有长度为4,6,…,2r的圈,它们都是偶圈,因而非同构的圈共有r−1种.(2)至多有max{r,s}个顶点彼此不相邻.(3)至多有min{r,s}条边彼此不相邻.(4)κ=λ=min{r,s}. 离散数学习题解65习题十五P303全部1~22题15.1.判断图15.11中哪些是欧拉图?对不是欧拉图的至少要加多少条边才能成为欧拉图?(a)(b)(c)(d)图15.11(a),(c)都是欧拉图,它们都连通且无奇度顶点.(b)不是欧拉图,因为它不连通.(d)不是欧拉图,因为它不连通,也因为它有奇度顶点.要使(b),(d)成为欧拉图,至少要加两条边,使它们连通且无奇度顶点.15.2.判断下列命题是否为真?(1)完全图Kn(n≥3)都是欧拉图.(2)n(n≥2)阶有向完全图都是欧拉图.(3)完全二部图Kr,s(r,s均为非0正偶数)都是欧拉图.(1)错误,完全图Kn(n≥3)每个顶点度数都是n−1,要使它成为成为偶数,要求n为奇数.所以完全图Kn只在n为奇数时才是欧拉图.(2)正确.有向完全图是强连通的,且每个顶点的入度等于出度,由定理15.3知命题为真.(3)正确.Kr,s每个顶点的度数不是r就是s,因此都是偶度顶点,且Kr,s是连通的,因此是欧拉图.15.3.3.画一个无向欧拉图,使它具有:(1)偶数个顶点,偶数条边.(2)奇数个顶点,奇数条边.(3)偶数个顶点,奇数条边.(4)奇数个顶点,偶数条边.见答图.(1)(2)(3)(4)第3题答图 离散数学习题解6615.4.画一个有向欧拉图,使它具有:(1)偶数个顶点,偶数条边.(2)奇数个顶点,奇数条边.(3)偶数个顶点,奇数条边.(4)奇数个顶点,偶数条边.见答图.(1)(2)(3)(4)第4题答图15.5.5.在k(k≥2)个长度大于或等于3的圈(全为无向的或全为有向的)之间至少加多少条新边(有向的加有向边)才能使所得图为欧拉图?至少加2k条边.设k个圈为C1,C2,…,Ck,在Ci上取顶点,记为vi,i=1,2,…,k.在vi和vi+1之间加平行边(vi,vi+1),(vi,vi+1),i=1,2,…,k−1.记所得的图为G,则G连通,且所有顶点的度数都为偶数,因而G为欧拉图.至少加k条边.把k个相互分离的连通图连成一个连通图至少要加k−1条边.设k个圈为C1,C2,…,Ck,在Ci上取顶点,记为vi,i=1,2,…,k.在vi和vi+1之间加边(vi,vi+1),i=1,2,…,k−1.这样加了k−1条边后把k个相互分离的圈连成一个连通图,且vi的度数都变成4(偶数),i=2,…,k−1,而v1和vk的度数变成3(奇数),再在vk和v1之间加边(vk,v1),使它们的度数变成4,一共加了k条边.记所得的图为G,则G连通,且所有顶点的度数都为偶数,因而G为欧拉图.不难知道,添加少于k条边不能达到目的.15.6.6.证明:若有向图D是欧拉图,则D是强连通的.因为D为欧拉图,因而存在欧拉回路,设C为其中的一条欧拉回路.任取vi,vj∈V(D),则vi,vj均在C上.于是vi可达vj,并且vj可达vi,所以D是强连通的.15.7.7.设G是恰含2k(k≥1)个奇度顶点的无向连通图.证明G中存在k条边不重的简单通路Γ1,Γ2,…,Γk,使k得E(G)=∪E()Γi.i=1对k进行归纳.k=1时,由定理15.2知G由欧拉通路,设Γ1是其中一条.按定义,欧拉通路是简单通路且含图中所有的边.所以Γ1是简单通路且E(Γ1)=E(G),即结论成立.假设G有2k(k≥1)个奇度顶点时命题为真.当G有2(k+1)个奇度顶点时,设u,v是G的两个奇度顶点,令G"=G∪(u,v),则G"有2k(k≥1)个奇度顶点(u,v在G"中是偶度顶点),由归纳假设,G"中存在k条边不重的 离散数学习题解67k简单通路Γ1,Γ2,…,Γk,使得E(G")=∪E()Γi.易知,必有某个Γs(s=1,2,…,k)含新加边(u,v),于是Γs−(u,v)得i=1到G中两条满足要求的的简单通路.将G中(k+1)条边不重的简单通路重新排序:Γ1,Γ2,…,Γk,Γk+1,则E(G)k+1=∪E()Γi.i=115.8.8.完全图Kn(n≥1)都是哈密顿图吗?完全图Kn(n≥1)中,除了K2不是哈密顿图外,其余的都是哈密顿图.注意,平凡图K1是哈密顿图.15.9.9.设G是无向连通图,证明:若G中有桥或割点,则G不是哈密顿图.(例15.4)(1)证明有割点的无向连通图G不是哈密顿图.设v为G中的一个割点,则{v}为G中一个割集,则p(G−{v})≥2>|{v}|=1由定理15.6可知,G不是哈密顿图.(2)再证有桥的图不是哈密顿图.连通有桥图的最小阶数n=2,即K2,而K2不是哈密顿图.对于阶数n≥3的有桥图,任一桥的两个端点中,至少有一个是割点.由(1)知,这样的图也不是哈密顿图.证二若G是哈密顿图,则G中有哈密顿回路,设为C.∀v∈V(C)=V(G),C−v是连通的,因此G−v是连通的.因此G没有割点.∀e∈E(C),若e∉E(C),则G−e有连通的生成子图C,因此是连通的.若e∈E(C),则G−e仍有连通的生成子图C−e,因而是连通的.所以G没有桥.15.10.10证明定理15.8.定理15.8设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+d(v)≥n,则G为哈密顿图⇔G∪(u,v)为哈密顿图((u,v)是加的新边).(⇒):显然.(⇐):设C是G"=G∪(u,v)中的一条哈密顿回路.(1)若新边(u,v)不在C上,则C是G中的哈密顿回路.(2)若新边(u,v)在C上,则Γ=C−(u,v)是G中的哈密顿通路.①若u,v在G中相邻,则Γ∪(u,v)是G中的哈密顿回路.((u,v)不是新边(u,v)).②若u,v在G中不相邻,则k=d(u)≥2(否则d(u)+d(v)≤1+(n−2)