离散数学 第1章 习题解答.doc

第1章 习题解答习题1.11. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 中国有四大发明。 计算机有空吗? 不存在最大素数。 21+35。 老王是山东人或河北人。 2与3都是偶数。 小李在宿舍里。 这朵玫瑰花多美丽呀! 请勿随地吐痰! 圆的面积等于半径的平方乘以p。 只有6是偶数，3才能是2的倍数。 雪是黑色的当且仅当太阳从东方升起。如果天下大雨，他就乘班车上班。解：是命题，其中是真命题，是假命题，的真值目前无法确定；不是命题。2. 将下列复合命题分成若干原子命题。 李辛与李末是兄弟。 因为天气冷，所以我穿了羽绒服。 天正在下雨或湿度很高。 刘英与李进上山。 王强与刘威都学过法语。 如果你不看电影，那么我也不看电影。我既不看电视也不外出，我在睡觉。 除非天下大雨，否则他不乘班车上班。解：本命题为原子命题；p：天气冷；q：我穿羽绒服；p：天在下雨；q：湿度很高；p：刘英上山；q：李进上山；p：王强学过法语；q：刘威学过法语；p：你看电影；q：我看电影；p：我看电视；q：我外出；r：我睡觉；p：天下大雨；q：他乘班车上班。3. 将下列命题符号化。 他一面吃饭，一面听音乐。 3是素数或2是素数。 若地球上没有树木，则人类不能生存。 8是偶数的充分必要条件是8能被3整除。 停机的原因在于语法错误或程序错误。 四边形ABCD是平行四边形当且仅当它的对边平行。 如果a和b是偶数，则a+b是偶数。解：p：他吃饭；q：他听音乐；原命题符号化为：pqp：3是素数；q：2是素数；原命题符号化为：pqp：地球上有树木；q：人类能生存；原命题符号化为：pqp：8是偶数；q：8能被3整除；原命题符号化为：pqp：停机；q：语法错误；r：程序错误；原命题符号化为：qrpp：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：pq。p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：pqr4. 将下列命题符号化，并指出各复合命题的真值。如果3+3=6，则雪是白的。 如果3+36，则雪是白的。 如果3+3=6，则雪不是白的。 如果3+36，则雪不是白的。是无理数当且仅当加拿大位于亚洲。 2+3=5的充要条件是是无理数。(假定是10进制) 若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。 当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。解：设p：336。q：雪是白的。原命题符号化为：pq；该命题是真命题。原命题符号化为：pq；该命题是真命题。原命题符号化为：pq；该命题是假命题。原命题符号化为：pq；该命题是真命题。p：是无理数；q：加拿大位于亚洲；原命题符号化为：pq；该命题是假命题。p：2+35；q：是无理数；原命题符号化为：pq；该命题是真命题。p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：pq；该命题是真命题。p：王小红心情愉快；q：王小红唱歌；原命题符号化为：pq；该命题是真命题。习题1.21.判断下列公式哪些是合式公式，哪些不是合式公式。 (pqr) (p(qr) (pq)(rs) (pqrs) (p(qr)(qp)qr)。解：是合式公式；不是合式公式。2.设p：天下雪。q：我将进城。r：我有时间。将下列命题符号化。 天没有下雪，我也没有进城。 如果我有时间，我将进城。 如果天不下雪而我又有时间的话，我将进城。解： pq rq prq 3.设p、q、r所表示的命题与上题相同，试把下列公式译成自然语言。 rq (rq) q (r p) (qr)(rq) 解： 我有时间并且我将进城。 我没有时间并且我也没有进城。 我进城，当且仅当我有时间并且天不下雪。 如果我有时间，那么我将进城，反之亦然。4. 试把原子命题表示为p、q、r等，将下列命题符号化。 或者你没有给我写信，或者它在途中丢失了。 如果张三和李四都不去，他就去。 我们不能既划船又跑步。 如果你来了，那末他唱不唱歌将看你是否伴奏而定。解： p：你给我写信；q：信在途中丢失；原命题符号化为：(p q)(pq)。p：张三去；q：李四去；r：他去；原命题符号化为：pqr。p：我们划船；q：我们跑步；原命题符号化为：（pq）。p：你来了；q：他唱歌；r：你伴奏；原命题符号化为：p（qr）。5. 用符号形式写出下列命题。假如上午不下雨，我去看电影，否则就在家里读书或看报。我今天进城，除非下雨。仅当你走，我将留下。解：p：上午下雨；q：我去看电影；r：我在家读书；s：我在家看报；原命题符号化为：（pq）（prs）。p：我今天进城；q：天下雨；原命题符号化为：qp。p：你走；q：我留下；原命题符号化为：qp。习题1.31.设A、B、C是任意命题公式，证明：AA若AB，则BA若AB，BC，则AC证明：由双条件的定义可知AA是一个永真式，由等价式的定义可知AA成立。因为AB，由等价的定义可知AB是一个永真式，再由双条件的定义可知BA也是一个永真式，所以，BA成立。对A、B、C的任一赋值，因为AB，则AB是永真式， 即A与B具有相同的真值，又因为BC，则BC是永真式， 即B与C也具有相同的真值，所以A与C也具有相同的真值；即AC成立。2.设A、B、C是任意命题公式，若ACBC, AB一定成立吗？若ACBC, AB一定成立吗？若AB，AB一定成立吗？解：不一定有AB。若A为真，B为假，C为真，则ACBC成立，但AB不成立。不一定有AB。若A为真，B为假，C为假，则ACBC成立，但AB不成立。一定有AB。3.构造下列命题公式的真值表，并求成真赋值和成假赋值。 q(pq)p p(qr) (pq)(qp) (pq)(rq)r (p(pq)r)(qr)解：q(pq)p的真值表如表1.24所示。表1.24pqpqq(pq)q(pq)p00101011101000111111使得公式q(pq)p成真的赋值是：00，10，11，使得公式q(pq)p成假的赋值是：01。p(qr) 的真值表如表1.25所示。表1.25pqrqrp(qr)0000100111010110111110000101111101111111 使得公式p(qr)成真的赋值是：000，001，010，011，101，110，111，使得公式p(qr)成假的赋值是：100。(pq)(qp) 的真值表如表1.26所示。表1.26pqpqqp(pq)(qp)00001011111011111111所有的赋值均使得公式(pq)(qp)成真，即(pq)(qp)是一个永真式。(pq)(rq)r的真值表如表1.27所示。表1.27pqrqpqrq(pq)(rq)(pq)(rq)r0001000100110001010000010110011110011010101110111100000111100111使得公式(pq)(rq)r成真的赋值是：000，001，010，011，101，110，111，使得公式(pq)(rq)r成假的赋值是：100。(p(pq)r)(qr) 的真值表如表1.28所示。表1.28pqrpqp(pq)(p(pq)rqr(p(pq)r)(qr)0000010100100101010001110110010110011000101111011100101111101101使得公式(p(pq)r)(qr)成真的赋值是：000，001，010，011，101，110，111，使得公式(p(pq)r)(qr)成假的赋值是：100。 4.用真值表证明下列等价式：(pq)pq证明：证明(pq)pq的真值表如表1.29所示。表1.29pqpq(pq)qpq001010011000100111111000由上表可见：(pq)和pq的真值表完全相同，所以(pq)pq。pqqp 证明：证明pqqp的真值表如表1.30所示。表1.30pqpqpqqp001111011101100010111001由上表可见：pq和qp的真值表完全相同，所以pqqp。(pq)pq证明：证明(pq)和pq的真值表如表1.31所示。表1.31pqpq(pq)qpq001010010101100111111000由上表可见：(pq)和pq的真值表完全相同，所以(pq)pq。p(qr)(pq)r证明：证明p(qr)和(pq)r的真值表如表1.32所示。表1.32pqrqrp(qr)pq(pq)r00011010011101010010101111011001101101110111000101111111由上表可见：p(qr)和(pq)r的真值表完全相同，所以p(qr)(pq)r。p(qp) p(pq)证明：证明p(qp)和p(pq)的真值表如表1.33所示。表1.33pqqpp(qp)pqpqp(pq)00111111010110111011011111110001由上表可见：p(qp)和p(pq)的真值表完全相同，且都是永真式，所以p(qp)p(pq)。(pq)(pq)(pq)证明：证明(pq)和(pq)(pq)的真值表如表1.34所示。表1.34pqpq(pq)pqpq(pq)(pq)(pq)00100010010110111001101111101100由上表可见：(pq)和(pq)(pq)的真值表完全相同，所以(pq)(pq)(pq)(pq)(pq)(pq) 证明：证明(pq)和(pq)(pq)的真值表如表1.35所示。表1.35pqpq(pq)pqpq(pq)(pq)0010000010101110011011110000由上表可见：(pq)和(pq)(pq)的真值表完全相同，所以(pq)(pq)(pq)。p(qr)(pq)r证明：证明p(qr)和(pq)r的真值表如表1.36所示。表1.36pqrqrp(qr)qpq(pq)r0000110100111101010110010111100110000110101111111101100111111001由上表可见：p(qr)和(pq)r的真值表完全相同，所以p(qr)(pq)r。5. 用等价演算证明习题4中的等价式。(pq)(pq)(条件等价式)pq(德摩根律)qpqp(条件等价式)qp(双重否定律)pq(交换律) pq(条件等价式)(pq)(pq)(qp)(双条件等价式)(pq)(qp)(条件等价式)(pq)(qp)(德摩根律)(pq)q)(pq)p)(分配律)(pq)(qp)(分配律)(pq)(qp)(交换律)(pq)(qp)(条件等价式)pq(双条件等价式)p(qr)p(qr)(条件等价式)(pq)r(结合律)(pq)r(德摩根律)(pq)r(条件等价式)p(qp)p(qp)(条件等价式)Tp(pq)p(pq)(条件等价式)T所以p(qp) p(pq)(pq)(pq)(pq)(例1.17)(pq)(pq)(德摩根律)(pq)(pq)(德摩根律)所以(pq)(pq)(pq)(pq)(pq)(qp)(双条件等价式)(pq)(qp)(条件等价式)(pq)(pq)(德摩根律)p(qr)p(qr)(条件等价式)(pq)r(结合律)(pq)r(德摩根律)(pq)r(条件等价式)6.试用真值表证明下列命题定律。结合律：(pq)rp(qr)，(pq)rp(qr)证明：证明结合律的真值表如表1.37和表1.38所示。表1.37pqrpq(pq)rqrp(qr)00000000010111010111101111111001101101111111011111111111表1.38pqrpq(pq)rqrp(qr)00000000010000010000001100101000000101000011010001111111由真值表可知结合律成立。分配律：p(qr)(pq)(pr)，p(qr)(pq)(pr)证明：证明合取对析取的分配律的真值表如表1.39所示，析取对合取的的分配律的真值表如表1.40所示。表1.39pqrqrp(qr)pqpr(pq)(pr)0000000000110000010100000111000010000000101110111101110111111111表1.40pqrqrp(qr)pqpr(pq)(pr)0000000000100010010001000111111110001111101011111100111111111111由真值表可知分配律成立。假言易位式：pqqp证明：证明假言易位式的真值表如表1.41所示。表1.41pqpqqpqp001111011011100100111001由真值表可知假言易位律成立。双条件否定等价式：pqpq证明：证明双条件否定的真值表如表1.42所示。表1.42pqpqpqpq001111010100100010111001由真值表可知双条件否定等价式成立。习题 1.4 1.用真值表或等价演算判断下列命题公式的类型。(pq)q(pq)q（条件等价式）(pq)q（德摩根律）q（可满足式）（吸收律）(pq)q(pq)q（条件等价式）(pq)q（德摩根律）F（永假式）（结合律、矛盾律）(pq)pq(pq)pq（条件等价式）(pp)(qp)q（分配律）(qp)q（同一律、矛盾律）(qp)q（条件等价式）(qp)q（德摩根律）T(永真式)（零律、排中律）(pq)q(pq)q（条件等价式）q（可满足式）（吸收律）(pq)(qp)(pq)(pq)（假言易位式）T(永真式)(pq)(qr)(pr)(pq)(qr)(pr)（条件等价式）(pq)(qr)(pr)（德摩根律）(pq)(pqr)(prr)（分配律）(pq)(pqr)（同一律、排中律、零律）(pqrp)(pqrq)（分配律）T(永真式)p(pq) p(pq)（条件等价式）T(永真式)p(pqr)p(pqr)（条件等价式）T(永真式)2.用真值表证明下列命题公式是重言式。(p(pq)q(p(pq)q的真值表如表1.43所示。由表1.43可以看出(p(pq)q是重言式。表1.43pqpqp(pq)(p(pq)q00101011011000111111(q(pq)p(q(pq)p的真值表如表1.44所示。由表1.44可以看出(q(pq)p是重言式。表1.44pqpqqq(pq)p(q(pq)p0011111011001110010011110001(p(pq)q(p(pq)q的真值表如表1.45所示。由表1.45可以看出(p(pq)q是重言式。表1.45pqpq pp(pq)(p(pq)q000101011111101001111001(pq)(qr)(pr)(pq)(qr)(pr)的真值表如表1.46所示。由表1.46可以看出(pq)(qr)(pr)是重言式。表1.46pqrpqqr(pq)(qr)pr(pq)(qr)(pr)0001111100111111010100110111111110001001101010111101000111111111(pq)(pr)(qr)r(pq)(pr)(qr)r的真值表如表1.47所示。由表1.47可以看出(pq)(pr)(qr)r是重言式。表1.47pqrpqprqr(pq)(pr)(qr)(pq)(pr)(qr)r0000110100101101010110010111111110010101101111111101000111111111(pq)(rs)(pr)(qs)(pq)(rs)(pr)(qs)的真值表如表1.48所示。由表1.48可以看出(pq)(rs)(pr)(qs)是重言式。表1.48pqrspqrs(pq)(rs)prqs(pr)(qs)原公式00001110011000111100110010100001100111110011010011100110101111011101101000011011111101111000010001110010100011101000010011011010100111001110011110111101111110100100111111111111(pq)(qr)(pr)(pq)(qr)(pr)的真值表如表1.49所示。由表1.49可以看出(pq)(qr)(pr)是重言式。表1.49pqrpqqr(pq)(qr)pr(pq)(qr)(pr)00011111001100010100001101101001100010011010001111010001111111113. 用等价演算证明题2中的命题公式是重言式。(p(pq)q(p(pq)q(p(pq)q(pp)(pq)q(pq)qT(q(pq)p(q(pq)p(q(pq)p(q(pq)p(pq)(pq)(pq)(pq)T(p(pq)q(pq)q(pq)qpqqT(pq)(qr)(pr)(pq)(qr)(pr)(pq)(qr)(pr)(pq)(pqr)(prr)(pq)(pqr)(pqrp)(pqrq)T(pq)(pr)(qr)r(pq)(pr)(qr)r(pq)(pq)r)r(pq)r)r(pq)r)r(pq)rrT(pq)(rs)(pr)(qs)(pq)(rs)(pr)(qs)(pq)(rs)(pr)(qs)(pq)(rs)(prq)(prs)(pq)(rs)(prq)(pq)(rs)(prs)(rs)(prqp)(prqq)(rs)(prsp)(prsq)(rs)T)(rs)(pqrs)(rs)(pqrs)(pqrsr)(pqrss)T(pq)(qr)(pr)(pq)(qp)(qr)(rq)(pr)(pq)(qp)(qr)(rq)(pr)(pr)(pq)(pr)(rq)(qr)(qp)(pr)(p(qr)(qr)(rq)(qp)(pr)(qr)(qr)(p(qr)(rq)(qp)(pr)(T(p(qr)(rq)(qp)(pr)p(qr)(rq)(qp)(pr)p(qr)(qp)(pr)(rq)p(qr)(p(qr)(qr)p(qr)p(qr)T4.证明下列等价式：(pr)(qr)(pr)(qr)(pq)r(pq)r(pq)r(pq)(pq)(pq)(pq)p(qq)pFpp(pq)p(pq)(pp)(pq)F(pq)pq习题 1.5 1.求下列命题公式的析取范式。(pq)r(pq)rpqr(pq)r(pq)r(pq)rpqrp(pq) p(pq)(pp)(pq) pq(pq)(qr)(pq)(qr) q(pr)(pq)(rt)(pq)(rt)(pqr)(pqt)2. 求下列命题公式的合取范式。(pq)(pq)pqq(pqr)(qp)(qq)(qr)(qp)(qr)(pq)(pq)(pq)p)(pq)q)(pp)(qp)(pq)(qq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)r(pq)r(pq)rpqr3.求下列命题公式的主析取范式，并求命题公式的成真赋值。(pq)(pr)作(pq)(pr)的真值表，如表1.50所示。表1.50pqrpqpr(pq)(pr)000000001000010000011000100000101011110101111111由真值表可知，原式(pqr)(pqr)(pqr)(主析取范式)5,6,7使得命题公式(pq)(pr)成真的赋值是：101，110，111。(pq)(pr)(pq)(pr)(pq)(pr)(pqp)(pqr)pqr(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)1,2,3,4,5,6,7使得命题公式(pq)(pr)成真的赋值是：001，010、011，100，101，110，111。(pq)(pq)作(pq)(pq)的真值表，如表1.51所示。表1.51pqpqpqpq(pq)(pq)0011100011011110011111100001由真值表可知:原式(pq)(pq)(pq) (主析取范式)1,2,3使得命题公式(pq)(pq)成真的赋值是：01，10，11。(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pqp)(pqq)pq(pq)(pq)(pq)(主析取范式)0,2,3使得命题公式(pq)(pq)成真的赋值是：00,10,11。(p(qr)(p(qr)(p(qr)(p(qr)(pq)(pr)(pq)(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)使得命题公式(p(qr)(p(qr)成真的赋值是：000,111。4. 求下列命题公式的主合取范式，并求命题公式的成假赋值。(pq)r(pq)r(pqr)(pqr)(pr)(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)0,2,4,5,6使得命题公式(pq)r成假的赋值是：000,010,100,101,110。(pq)(pq)作(pq)(pq)的真值表，如表1.52所示。表1.52pqpq(pq)qpq(pq)(pq)0010110011001010011111110001由真值表可知:原式(pq)(pq)0,1使得命题公式(pq)(pq)成假的赋值是：00,01。(pq)(pr)(pq)(pr)(pq)(pr)(pqp)(pqr)pqr0使得命题公式(pq)(pr)成假的赋值是：000。(pq)p(pq)ppqpF0,1,2,3使得命题公式(pq)p成假的赋值是：00,01,10,11。(p(qr)rpqrrpqr4使得命题公式(p(qr)r成假的赋值是：100。5. 求下列命题公式的主析取范式，再用主析取范式求出主合取范式。(pq)(qr)(pq)(qr)(pq)q)(pq)r)(pq)(pr)(qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)0,1,3,72,4,5,6(pqr)(pqr)(pqr)(pqr)(主合取范式)(pq)r(pq)r(pqr)(pqr)(pr)(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)1,3,5,6,70,2,4(pqr)(pqr)(pqr)(主合取范式)6. 求下列命题公式的主合取范式，再用主合取范式求出主析取范式。(pq)r(pq)(qp)r(pq)(qp)r(pqr)(pqr)(qpr)(qpr)(pr)(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主合取范式)0,2,3,4,5,61,7(pqr)(pqr)(主析取范式)(pq)q(pq)qpqqT(无主合取范式)0,1,2,3(pq)(pq)(pq)(pq)7.用主析取范式判断下列命题公式是否等价。p(qr)和q(pr)p(qr)p(qr)pqr(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)0,1,2,3,4,5,7q(pr)q(pr)pqr(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)0,1,2,3,4,5,7因为p(qr)与q(pr)的主析取范式相同，所以p(qr)q(pr)。(pq)(pr)和p(qp)(pq)(pr)(pq)(pr)p(qr)(pq)(pq)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)0,1,2,3,7p(qp)p(qp)(pq)(pp)pq(pq)(pq)(pq)(pq)(pq)(pq)(pq) (主析取范式)0,1,3因为(pq)(pr)与p(qp)的主析取范式不相同，所以(pq)(pr)与p(qp)不等价。8. 用主合取范式判断下列命题公式是否等价。(pq)r和p(qr)(pq)r(pq)r(pq)r(pr)(qr)(pqr)(pqr)(pqr)0,2,6p(qr)p(qr)pqr6因为(pq)r与p(qr)的主合取范式不相同，所以(pq)r与p(qr)不等价。(pq)(pq)和(pq)(pq)(pq)(pq)1,20,3(pq)(pq)(pq)(pq)(p