您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 《离散数学1-7习题解答
离散数学习题解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∧r00000101001110010111011111110111101000010000001000011100000000112.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)000110111001111001111000(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)→rkq→(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)kq→(p→r)(2)¬(p∧q)⇔m0∨m1∨m2¬(p∨q)⇔m0所以¬(p∧q)k¬(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)k(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)))注)联结词越少,公式越长.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,但AkB.(2)取A=p,B=q,C=0(矛盾式),有A∧C⇔B∧C,但AkB.好的例子是简单,具体,而又说明问题的.(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)(已为{¬,→,↔}中公式
本文标题:《离散数学1-7习题解答
链接地址:https://www.777doc.com/doc-4447202 .html