离散数学(左孝凌)课后习题解答(详细).doc

第 1 章习题解答 1 离散数学 习题 1.1 1. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 中国有四大发明。 计算机有空吗? 不存在最大素数。 21+35。 老王是山东人或河北人。 2 与 3 都是偶数。 小李在宿舍里。 这朵玫瑰花多美丽呀! 请勿随地吐痰! 圆的面积等于半径的平方乘以 。 只有 6 是偶数，3 才能是 2 的倍数。 雪是黑色的当且仅当太阳从东方升起。 如果天下大雨，他就乘班车上班。 解：是命题，其中是真命题，是假命题， 的真值目前无法确定；不是命题。 2. 将下列复合命题分成若干原子命题。 李辛与李末是兄弟。 因为天气冷，所以我穿了羽绒服。 天正在下雨或湿度很高。 刘英与李进上山。 王强与刘威都学过法语。 如果你不看电影，那么我也不看电影。 我既不看电视也不外出，我在睡觉。 除非天下大雨，否则他不乘班车上班。 解：本命题为原子命题； p：天气冷；q：我穿羽绒服； p：天在下雨；q：湿度很高； p：刘英上山；q：李进上山； p：王强学过法语；q：刘威学过法语； p：你看电影；q：我看电影； p：我看电视；q：我外出；r：我睡觉； p：天下大雨；q：他乘班车上班。 第 1 章习题解答 2 3. 将下列命题符号化。 他一面吃饭，一面听音乐。 3 是素数或 2 是素数。 若地球上没有树木，则人类不能生存。 8 是偶数的充分必要条件是 8 能被 3整除。 停机的原因在于语法错误或程序错误。 四边形 ABCD 是平行四边形当且仅当它的对边平行。 如果 a 和 b 是偶数，则 a+b 是偶数。 解： p：他吃饭；q：他听音乐；原命题符号化为：pq p：3 是素数；q：2 是素数；原命题符号化为：pq p：地球上有树木；q：人类能生存；原命题符号化为：pq p：8 是偶数；q：8 能被 3 整除；原命题符号化为：pq p：停机；q：语法错误；r：程序错误；原命题符号化为：qrp p：四边形 ABCD 是平行四边形；q：四边形 ABCD 的对边平行；原命题符号化 为：pq。 p：a 是偶数；q：b 是偶数；r：a+b 是偶数；原命题符号化为：pqr 4. 将下列命题符号化，并指出各复合命题的真值。 如果 3+3=6，则雪是白的。 如果 3+36，则雪是白的。 如果 3+3=6，则雪不是白的。 如果 3+36，则雪不是白的。 是无理数当且仅当加拿大位于亚洲。3 2+3=5 的充要条件是是无理数。(假定是 10 进制)3 若两圆 O1，O2的面积相等，则它们的半径相等，反之亦然。 当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设 p：336。q：雪是白的。 原命题符号化为：pq；该命题是真命题。 原命题符号化为：pq；该命题是真命题。 原命题符号化为：pq；该命题是假命题。 原命题符号化为：pq；该命题是真命题。 p：是无理数；q：加拿大位于亚洲；原命题符号化为：pq；该命题是假命3 题。 p：2+35；q：是无理数；原命题符号化为：pq；该命题是真命题。3 p：两圆 O1,O2的面积相等；q：两圆 O1,O2的半径相等；原命题符号化为： pq；该命题是真命题。 p：王小红心情愉快；q：王小红唱歌；原命题符号化为：pq；该命题是真命 题。 第 1 章习题解答 3 习题 1.2 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) 解： 我有时间并且我将进城。 我没有时间并且我也没有进城。 我进城，当且仅当我有时间并且天不下雪。 如果我有时间，那么我将进城，反之亦然。 4. 试把原子命题表示为 p、q、r 等，将下列命题符号化。 或者你没有给我写信，或者它在途中丢失了。 如果张三和李四都不去，他就去。 我们不能既划船又跑步。 第 1 章习题解答 4 如果你来了，那末他唱不唱歌将看你是否伴奏而定。 解： 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 章习题解答 5 习题 1.3 1.设 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.24 pq pqq(pq)q(pq)p 第 1 章习题解答 6 00101 01110 10001 11111 使得公式 q(pq)p 成真的赋值是：00，10，11，使得公式 q(pq)p 成假的 赋值是：01。 p(qr) 的真值表如表 1.25 所示。 表 1.25 pqr qrp(qr) 00001 00111 01011 01111 10000 10111 11011 11111 使得公式 p(qr)成真的赋值是：000，001，010，011，101，110，111，使得公式 p(qr)成假的赋值是：100。 (pq)(qp) 的真值表如表 1.26 所示。 表 1.26 pq pqqp(pq)(qp) 00001 01111 10111 11111 所有的赋值均使得公式(pq)(qp)成真，即(pq)(qp)是一个永真式。 (pq)(rq)r 的真值表如表 1.27 所示。 表 1.27 pqrq pqrq(pq)(rq)(pq)(rq)r 00010001 00110001 第 1 章习题解答 7 01000001 01100111 10011010 10111011 11000001 11100111 使得公式(pq)(rq)r 成真的赋值是： 000，001，010，011，101，110，111，使得公式(pq)(rq)r 成假的赋值是： 100。 (p(pq)r)(qr) 的真值表如表 1.28 所示。 使得公式(p(pq)r)(qr)成真的赋值是： 000，001，010，011，101，110，111，使得公式(p(pq)r)(qr)成假的赋 值是：100。 4.用真值表证明下列等价式： (pq)pq 证明：证明(pq)pq 的真值表如表 1.29 所示。 表 1.29 pq pq(pq) qpq 001010 011000 100111 111000 由上表可见：(pq)和 pq 的真值表完全相同，所以(pq)pq。 pqqp 表 1.28 pqr pq p(pq)(p(pq)rqr(p(pq)r)(qr) 00000101 00100101 01000111 01100101 10011000 10111101 11001011 11101101 第 1 章习题解答 8 证明：证明 pqqp 的真值表如表 1.30 所示。 表 1.30 pq pqpqqp 001111 011101 100010 111001 由上表可见：pq 和qp 的真值表完全相同，所以 pqqp。 (pq)pq 证明：证明(pq)和 pq 的真值表如表 1.31 所示。 表 1.31 pqpq(pq) qpq 001010 010101 100111 111000 由上表可见：(pq)和 pq 的真值表完全相同，所以(pq)pq。 p(qr)(pq)r 证明：证明 p(qr)和(pq)r 的真值表如表 1.32 所示。 表 1.32 pqr qrp(qr)pq(pq)r 0001101 0011101 0100101 0111101 1001101 1011101 1100010 1111111 由上表可见：p(qr)和(pq)r 的真值表完全相同，所以 p(qr)(pq)r。 p(qp)p(pq) 证明：证明 p(qp)和p(pq)的真值表如表 1.33 所示。 表 1.33 第 1 章习题解答 9 pq qpp(qp)pq pq p(pq) 00111111 01011011 10110111 11110001 由上表可见：p(qp)和p(pq)的真值表完全相同，且都是永真式，所以 p(qp)p(pq)。 (pq)(pq)(pq) 证明：证明(pq)和(pq)(pq)的真值表如表 1.34 所示。 表 1.34 pqpq(pq)pq pq (pq) (pq)(pq) 00100010 01011011 10011011 11101100 由上表可见：(pq)和(pq)(pq)的真值表完全相同，所以(pq)(pq) (pq) (pq)(pq)(pq) 证明：证明(pq)和(pq)(pq)的真值表如表 1.35 所示。 表 1.35 pqpq(pq) pq pq (pq)(pq) 0010000 0101011 1001101 1110000 由上表可见：(pq)和(pq)(pq)的真值表完全相同，所以(pq)(pq) (pq)。 p(qr)(pq)r 证明：证明 p(qr)和(pq)r 的真值表如表 1.36 所示。 表 1.36 pqr qrp(qr)qpq (pq)r 00001101 第 1 章习题解答 10 00111101 01011001 01111001 10000110 10111111 11011001 11111001 由上表可见：p(qr)和(pq)r 的真值表完全相同，所以 p(qr)(pq) r。 5. 用等价演算证明习题 4 中的等价式。 (pq) (pq)(条件等价式) pq(德摩根律) qp qp(条件等价式) 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)(条件等价式) T p(pq) p(pq)(条件等价式) T 第 1 章习题解答 11 所以 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.37 pqr pq(pq)rqrp(qr) 0000000 0010111 0101111 0111111 1001101 1011111 1101111 1111111 表 1.38 pqr pq(pq)rqrp(qr) 0000000 0010000 0100000 0110010 1000000 1010000 第 1 章习题解答 12 1101000 1111111 由真值表可知结合律成立。 分配律：p(qr)(pq)(pr)， p(qr)(pq)(pr) 证明：证明合取对析取的分配律的真值表如表 1.39 所示，析取对合取的的分配律的 真值表如表 1.40 所示。 表 1.39 pqr qrp(qr)pqpr(pq)(pr) 00000000 00110000 01010000 01110000 10000000 10111011 11011101 11111111 表 1.40 pqr qrp(qr)pqpr(pq)(pr) 00000000 00100010 01000100 01111111 10001111 10101111 11001111 11111111 由真值表可知分配律成立。 假言易位式：pqqp 证明：证明假言易位式的真值表如表 1.41 所示。 表 1.41 第 1 章习题解答 13 pq pqqpqp 001111 011011 100100 111001 由真值表可知假言易位律成立。 双条件否定等价式：pqpq 证明：证明双条件否定的真值表如表 1.42 所示。 表 1.42 pqpqpqpq 001111 010100 100010 111001 由真值表可知双条件否定等价式成立。 第 1 章习题解答 14 习题 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)（同一律、排中律、零律） 第 1 章习题解答 15 (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.43 pq pqp(pq) (p(pq)q 00101 01101 10001 11111 (q(pq)p (q(pq)p 的真值表如表 1.44 所示。由表 1.44 可以看出(q(pq)p 是重言式。 表 1.44 pq pq q q(pq ) p (q(pq) p 0011111 0110011 1001001 1110001 (p(pq)q (p(pq)q 的真值表如表 1.45 所示。由表 1.45 可以看出(p(pq)q 是重 言式。 表 1.45 pq pq p p(pq ) (p(pq)q 第 1 章习题解答 16 000101 011111 101001 111001 (pq)(qr)(pr) (pq)(qr)(pr)的真值表如表 1.46 所示。由表 1.46 可以看出(pq)(qr) (pr)是重言式。 表 1.46 pqr pqqr(pq)(qr)pr(pq)(qr)(pr) 00011111 00111111 01010011 01111111 10001001 10101011 11010001 11111111 (pq)(pr)(qr)r (pq)(pr)(qr)r 的真值表如表 1.47 所示。由表 1.47 可以看出(pq) (pr)(qr)r 是重言式。 表 1.47 pqr pqprqr(pq)(pr)(qr) (pq)(pr)(qr)r 00001101 00101101 01011001 01111111 10010101 10111111 11010001 第 1 章习题解答 17 11111111 (pq)(rs)(pr)(qs) (pq)(rs)(pr)(qs)的真值表如表 1.48 所示。由表 1.48 可以看出(pq) (rs)(pr)(qs)是重言式。 表 1.48 pqrs pqrs(pq)(rs)prqs(pr)(qs) 原公式 00001110011 00011110011 00101000011 00111110011 01001110011 01011110111 01101000011 01111110111 10000100011 10010100011 10100001001 10110101001 11001110011 11011110111 11101001001 11111111111 (pq)(qr)(pr) (pq)(qr)(pr)的真值表如表 1.49 所示。由表 1.49 可以看出(pq)(qr) (pr)是重言式。 第 1 章习题解答 18 表 1.49 pqrpqqr (pq)(qr) pr (pq)(qr)(pr) 00011111 00110001 01000011 01101001 10001001 10100011 11010001 11111111 3. 用等价演算证明题 2 中的命题公式是重言式。 (p(pq)q (p(pq)q (p(pq)q (pp)(pq)q (pq)q T (q(pq)p (q(pq)p (q(pq)p (q(pq)p (pq)(pq) (pq)(pq) T (p(pq)q (pq)q (pq)q pqq T (pq)(qr)(pr) (pq)(qr)(pr) (pq)(qr)(pr) (pq)(pqr)(prr) (pq)(pqr) (pqrp)(pqrq) T (pq)(pr)(qr)r 第 1 章习题解答 19 (pq)(pr)(qr)r (pq)(pq)r)r (pq)r)r (pq)r)r (pq)rr T (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) T 4.证明下列等价式： (pr)(qr) (pr)(qr) (pq)r (pq)r (pq)r (pq)(pq) (pq)(pq) p(qq) pF 第 1 章习题解答 20 p p(pq) p(pq) (pp)(pq) F(pq) pq 习题 1.5 1.求下列命题公式的析取范式。 (pq)r (pq)r pqr (pq)r (pq)r (pq)r pqr p(pq) p(pq) (pp)(pq) pq (pq)(qr) (pq)(qr) q(pr) (pq)(rt) (pq)(rt) (pqr)(pqt) 2. 求下列命题公式的合取范式。 (pq) (pq) pq q(pqr) (qp)(qq)(qr) 第 1 章习题解答 21 (qp)(qr) (pq)(pq) (pq)p)(pq)q) (pp)(qp)(pq)(qq) (pq)(pq) (pq) (pq)(pq) (pq)(pq) (pq)r (pq)r (pq)r pqr 3.求下列命题公式的主析取范式，并求命题公式的成真赋值。 (pq)(pr) 作(pq)(pr)的真值表，如表 1.50 所示。 表 1.50 pqr pqpr(pq)(pr) 000000 001000 010000 011000 100000 101011 110101 111111 由真值表可知，原式(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。 第 1 章习题解答 22 (pq)(pq) 作(pq)(pq)的真值表，如表 1.51 所示。 表 1.51 pqp q pq pq (pq)(pq) 0011100 0110111 1001111 1100001 由真值表可知: 原式(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)(pq r) (pqr)(pqr)(主析取范式) 使得命题公式(p(qr)(p(qr)成真的赋值是：000,111。 4. 求下列命题公式的主合取范式，并求命题公式的成假赋值。 (pq)r (pq)r (pqr)(pqr)(pr)(pr) (pqr)(pqr)(pqr)(pqr)(pqr)(pq r) (pqr)(pqr)(pqr)(pqr)(pqr) 0,2,4,5,6 第 1 章习题解答 23 使得命题公式(pq)r 成假的赋值是：000,010,100,101,110。 (pq)(pq) 作(pq)(pq)的真值表，如表 1.52 所示。 表 1.52 pq pq (pq)qpq(pq)(pq) 0010110 0110010 1001111 1110001 由真值表可知: 原式(pq)(pq)0,1 使得命题公式(pq)(pq)成假的赋值是：00,01。 (pq)(pr) (pq)(pr) (pq)(pr) (pqp)(pqr) pqr 0 使得命题公式(pq)(pr)成假的赋值是：000。 (pq)p (pq)p pqp F 0,1,2,3 使得命题公式(pq)p 成假的赋值是：00,01,10,11。 (p(qr)r pqrr pqr 4 使得命题公式(p(qr)r 成假的赋值是：100。 5. 求下列命题公式的主析取范式，再用主析取范式求出主合取范式。 (pq)(qr) (pq)(qr) (pq)q)(pq)r) (pq)(pr)(qr) (pqr)(pqr)(pqr)(pqr)(pqr)(p qr) 第 1 章习题解答 24 (pqr)(pqr)(pqr)(pqr)(主析取范式) 0,1,3,7 2,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,7 0,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)q pqq T(无主合取范式) 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,7 q(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) 第 1 章习题解答 25 (pq)(pr)(pq)(pr)p(qr) (pq)(pq)(pqr)(pqr) (pqr)(pqr)(pqr)(pqr)(pqr)(p qr) (pqr)(pqr)(pqr)(pqr)(pqr)(主析取 范式) 0,1,2,3,7 p(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,6 p(qr)p(qr)pqr 6 因为(pq)r 与 p(qr)的主合取范式不相同，所以(pq)r 与 p(qr)不等价。 (pq)(pq)和(pq)(pq) (pq)(pq)1,20,3(pq)(pq) (pq)(pq)(pq)(pq)0,3 因为(pq)(pq)和(pq)(pq)的主合取范式相同，所以(pq) (pq) (pq)(pq)。 第 1 章习题解答 26 习题 1.6 1.将下列命题公式用只含，的等价式表示。 (pq)r(pq)(qp)r(pq)(pq)r (p(q(qr)(p(qqr)(q(qr) p(qr)(q(qr) p(qr)q pqr p(pq)p(pq) (p(pq)(p(pq) (pq)p pq (pq)r(pq)(pq)r (pq)(pq)r)(pq)(pq)r) (pqr)(pqr)(pq)(pq)r) (pqr)(pqr)(pq)(pq)r) (pq)(rt)(pq)(qp)(rt) (pq)(qp)(rt)(pq)(qp)(r t) (pq)(qp)(rt)(pq)(qp)(rt) 第 1 章习题解答 27 2. 将下列命题公式用只含，的等价式表示。 (pq)p(pq)p) pq(pq)(qp)(pq)(qp) (pq)r(pq)r(pq)r) pq(pq)(pq)(qp) (pq)(pq) (pq)r(pq)(qp)r(pq)(qp)r) 3. 将下列命题公式用只含，的等价式表示。 pq(rp) pq(rp) (pqrp) (pq)(pr) (pq)(pr)(pr) (pq)(pr)(pr) (pq)(pq) (pq)(pq) pq (pq) (pq)(pq) (pq)(pq) (pq)(pq)(pq) (pq)(pq)(pq) (p(qr)(pr) (pqr)(pr) T 4.下列结论是否成立？若成立，请证明。若不成立，举反例说明。 pqqp 成立。pq(pq)(qp)qp pqqp 成立。pq(pq)(qp)qp p(qr)(pq)r 不成立。p(qr)p(qr)(p(qr)p(qr) (pqr)(pqr)(pqr)4,5,6 而(pq)r(pq)r(pq)r)(pq)r (pqr)(pqr)(pqr)1,3,5 显然上式不成立 p(qr)(pq)r 不成立。p(qr)p(qr)(p(qr)p(qr) (pqr)(pqr)(pqr)1,2,3 而(pq)r(pq)r(pq)r)(pq)r 第 1 章习题解答 28 (pqr)(pqr)(pqr)2,4,6 显然上式不成立。 5.证明下列等价式。 (pq)pq 证明：(pq)(pq)(pq)pq pq (pq) pq 所以：(pq)pq (pq)pq 证明：(pq)(pq)pq pq (pq)pq 所以：(pq)pq 6.将下列命题公式仅用“”表示。 ppp pq(pq)(pq)(pq) pq(pq) pq (pp)(qq) 7.将下列命题公式仅用“”表示。 p(pp)pp pq(pq)pq(pp)(qq) pq(pq)(pq)(pq)(pq) 习题 1.7 1. 写出下列命题公式的对偶式。 (pq)r 的对偶式是：(pq)r (pq)(rp)对偶式是(pq)(rp) pq(pq) (pq)(qp) (pq)(qp) (pq)(qp) 所以 pq 的对偶式是(pq)(qp) 而(pq)(qp) (pq)(qp) pq pq (pq) (pq) 所以 pq 的对偶式是(pq) (pq)r (pq)r 第 1 章习题解答 29 pqr 所以(pq)r 的对偶式是pqr (pq)r 的对偶式是(pq)r (pq)r(pq)r 所以(pq)r 的对偶式是(pq)r p(qr)(pq) p(qr)(pq) (pq)(pqr) 所以 p(qr)(pq)的对偶式是(pq)(pqr) (pq)r (pq)r (pq)(qp)r (pq)(qp)r (pq)(pq)r 所以(pq)r 的对偶式是(pq)(pq)r 2. 设 pq 为公式，则 qp 称为该公式的逆换式，pq 称为反换式，qp 称 为逆反式。证明： 公式与它的逆反式等价，即 pqqp 证明：pqpq 而qpqppq 所以 pqqp 公式的逆换式与公式的反换式等价，即 qppq 证明：qpqp 而pqpqpqqp 所以 qppq 3.用真值表或等价演算证明下列蕴含式。 pqpq 证明：(pq)(pq) (pq)(pq) pqpq T 所以，pqpq pqp(pq) 证明：作(pq)(p(pq)的真值表，如表 1.53 所示。 表 1.53 pq pqpqp(pq)(pq)(p(pq) 001011 011011 100001 第 1 章习题解答 30 111111 由以上真值表可知：(pq)(p(pq)是一个永真式，所以 pqp(pq) ppq 证明：p(pq) ppq ppq T 所以，ppq p(qr)(pq)(pr) 证明：(p(qr)(pq)(pr) (pqr)(pq)(pr) (pqr)(pq)pr (pqr)r)(pq)p) (pr)(qr)(rr)(pp)(pq) (pr)(qr)pq (prp)(qrp)q qrpq 1 所以，p(qr)(pq)(pr) p(pq)q 证明：作(p(pq)q 的真值表，如表 1.54 所示。