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

1、离散数学 第1章 习题解答习题1. 下列句子中，哪些是命题哪些不是命题如果是命题，指出它的真值。 中国有四大发明。 计算机有空吗 不存在最大素数。 21+35。 老王是山东人或河北人。 2与3都是偶数。 小李在宿舍里。 这朵玫瑰花多美丽呀! 请勿随地吐痰! 圆的面积等于半径的平方乘以。 只有6是偶数，3才能是2的倍数。 雪是黑色的当且仅当太阳从东方升起。如果天下大雨，他就乘班车上班。解：是命题，其中是真命题，是假命题，的真值目前无法确定；不是命题。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是

3、偶数，则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，则雪不是白

4、的。是无理数当且仅当加拿大位于亚洲。 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的半径相等；原命题符

5、号化为：pq；该命题是真命题。p：王小红心情愉快；q：王小红唱歌；原命题符号化为：pq；该命题是真命题。习题1.判断下列公式哪些是合式公式，哪些不是合式公式。 (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) 解： 我有时间并且

6、我将进城。 我没有时间并且我也没有进城。 我进城，当且仅当我有时间并且天不下雪。 如果我有时间，那么我将进城，反之亦然。4. 试把原子命题表示为p、q、r等，将下列命题符号化。 或者你没有给我写信，或者它在途中丢失了。 如果张三和李四都不去，他就去。 我们不能既划船又跑步。 如果你来了，那末他唱不唱歌将看你是否伴奏而定。解： p：你给我写信；q：信在途中丢失；原命题符号化为：(p q)(pq)。p：张三去；q：李四去；r：他去；原命题符号化为：pqr。p：我们划船；q：我们跑步；原命题符号化为：（pq）。p：你来了；q：他唱歌；r：你伴奏；原命题符号化为：p（qr）。5. 用符号形式写出下列命

7、题。假如上午不下雨，我去看电影，否则就在家里读书或看报。我今天进城，除非下雨。仅当你走，我将留下。解：p：上午下雨；q：我去看电影；r：我在家读书；s：我在家看报；原命题符号化为：（pq）（prs）。p：我今天进城；q：天下雨；原命题符号化为：qp。p：你走；q：我留下；原命题符号化为：qp。习题1.设A、B、C是任意命题公式，证明：AA若AB，则BA若AB，BC，则AC证明：由双条件的定义可知AA是一个永真式，由等价式的定义可知AA成立。因为AB，由等价的定义可知AB是一个永真式，再由双条件的定义可知BA也是一个永真式，所以，BA成立。对A、B、C的任一赋值，因为AB，则AB是永真式， 即A

8、与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的真值表如表所示。表pqpqq(pq)q(pq)p0010

9、1011101000111111使得公式q(pq)p成真的赋值是：00，10，11，使得公式q(pq)p成假的赋值是：01。p(qr) 的真值表如表所示。表pqrqrp(qr)0000100111010110111110000101111101111111 使得公式p(qr)成真的赋值是：000，001，010，011，101，110，111，使得公式p(qr)成假的赋值是：100。(pq)(qp) 的真值表如表所示。表pqpqqp(pq)(qp)00001011111011111111所有的赋值均使得公式(pq)(qp)成真，即(pq)(qp)是一个永真式。(pq)(rq)r的真值表如表所示

10、。表pqrqpqrq(pq)(rq)(pq)(rq)r0001000100110001010000010110011110011010101110111100000111100111使得公式(pq)(rq)r成真的赋值是：000，001，010，011，101，110，111，使得公式(pq)(rq)r成假的赋值是：100。(p(pq)r)(qr) 的真值表如表所示。表pqrpqp(pq)(p(pq)rqr(p(pq)r)(qr)0000010100100101010001110110010110011000101111011100101111101101使得公式(p(pq)r)(qr)成真的

11、赋值是：000，001，010，011，101，110，111，使得公式(p(pq)r)(qr)成假的赋值是：100。 4.用真值表证明下列等价式：(pq)pq证明：证明(pq)pq的真值表如表所示。表pqpq(pq)qpq001010011000100111111000由上表可见：(pq)和pq的真值表完全相同，所以(pq)pq。pqqp 证明：证明pqqp的真值表如表所示。表pqpqpqqp001111011101100010111001由上表可见：pq和qp的真值表完全相同，所以pqqp。(pq)pq证明：证明(pq)和pq的真值表如表所示。表pqpq(pq)qpq00101001010

12、1100111111000由上表可见：(pq)和pq的真值表完全相同，所以(pq)pq。p(qr)(pq)r证明：证明p(qr)和(pq)r的真值表如表所示。表pqrqrp(qr)pq(pq)r00011010011101010010101111011001101101110111000101111111由上表可见：p(qr)和(pq)r的真值表完全相同，所以p(qr)(pq)r。p(qp)p(pq)证明：证明p(qp)和p(pq)的真值表如表所示。表pqqpp(qp)pqpqp(pq)00111111010110111011011111110001由上表可见：p(qp)和p(pq)的真值表完

13、全相同，且都是永真式，所以p(qp)p(pq)。(pq)(pq)(pq)证明：证明(pq)和(pq)(pq)的真值表如表所示。表pqpq(pq)pqpq(pq)(pq)(pq)00100010010110111001101111101100由上表可见：(pq)和(pq)(pq)的真值表完全相同，所以(pq)(pq)(pq)(pq)(pq)(pq) 证明：证明(pq)和(pq)(pq)的真值表如表所示。表pqpq(pq)pqpq(pq)(pq)0010000010101110011011110000由上表可见：(pq)和(pq)(pq)的真值表完全相同，所以(pq)(pq)(pq)。p(qr)(

14、pq)r证明：证明p(qr)和(pq)r的真值表如表所示。表pqrqrp(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)

15、 (分配律)(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) (例(pq)(pq) (德摩根律)(pq)(pq) (德摩根律)所以(pq)(pq)(pq)(pq)(pq)(qp) (双条件等价式)(pq)(qp) (条件等价式)(pq)(pq) (德摩根律)p(qr)p(qr) (条件等价式)(pq)r

16、(结合律)(pq)r (德摩根律)(pq)r (条件等价式)6.试用真值表证明下列命题定律。结合律：(pq)rp(qr)，(pq)rp(qr)证明：证明结合律的真值表如表和表所示。表pqrpq(pq)rqrp(qr)00000000010111010111101111111001101101111111011111111111表pqrpq(pq)rqrp(qr)00000000010000010000001100101000000101000011010001111111由真值表可知结合律成立。分配律：p(qr)(pq)(pr)，p(qr)(pq)(pr)证明：证明合取对析取的分配律的真值表如

17、表所示，析取对合取的的分配律的真值表如表所示。表pqrqrp(qr)pqpr(pq)(pr)0000000000110000010100000111000010000000101110111101110111111111表pqrqrp(qr)pqpr(pq)(pr)0000000000100010010001000111111110001111101011111100111111111111由真值表可知分配律成立。假言易位式：pqqp证明：证明假言易位式的真值表如表所示。表pqpqqpqp001111011011100100111001由真值表可知假言易位律成立。双条件否定等价式：pqpq证明

18、：证明双条件否定的真值表如表所示。表pqpqpqpq001111010100100010111001由真值表可知双条件否定等价式成立。习题 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（可满足式） （

19、吸收律）(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的真值表如表所示。由表可以看出(p(pq)q是重言式。表pqpqp(pq)(p(pq)q00101011011000111111(

20、q(pq)p(q(pq)p的真值表如表所示。由表可以看出(q(pq)p是重言式。表pqpqqq(pq)p(q(pq)p0011111011001110010011110001(p(pq)q(p(pq)q的真值表如表所示。由表可以看出(p(pq)q是重言式。表pqpq pp(pq)(p(pq)q000101011111101001111001(pq)(qr)(pr)(pq)(qr)(pr)的真值表如表所示。由表可以看出(pq)(qr)(pr)是重言式。表pqrpqqr(pq)(qr)pr(pq)(qr)(pr)0001111100111111010100110111111110001001101010111101000111111111(pq)(pr)(qr)r(pq)(pr)(qr)r的真值表如表所示。由表可以看出