离散数学第5版答案

《离散数学第5版答案》由会员分享，可在线阅读，更多相关《离散数学第5版答案（106页珍藏版）》请在金锄头文库上搜索。

1、 1 第 1 章 习题解答 第 1 章 习题解答 11 除（3） ， （4） ， （5） ， （11）外全是命题，其中， （1） ， （2） ， （8） ， （9） ， （10） ， （14） ， （15）是简单命题， （6） ， （7） ， （12） ， （13）是复合命题。 分析 首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中， （3）为疑问句， （5）为感叹句， （11）为祈使句，它们都不是陈述句， 所以它们都不是命题。 其次， （4） 这个句子是陈述句， 但它表示的 判断结果是不确定。 又因为 （1） ， （2） ， （8） ， （9） ， （10） ， （14）

2、 ， （15）都是简单的陈述句，因而作为命题，它们 都是简单命题。 （6）和（7）各为由联结词“当且仅当”联结起来的复合命题， （12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来 的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许 多表述法，例如， “虽然，但是” 、 “不仅，而且” 、 “一面， 一面” 、 “和” 、 “与”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如， （14） 、 （15）中的“与”与“和”是联结 的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或 “与”出现的命题时，要根据命题所陈述

3、的含义加以区分。 12 （1）2:p是无理数，p 为真命题。 （2）5:p能被 2 整除，p 为假命题。 （6）qp 。其中，2:p是素数，q：三角形有三条边。由于 p 与 q 都是真 命题，因而qp 为假命题。 （7）qp ，其中，p：雪是黑色的，q：太阳从东方升起。由于 p 为假命 题，q 为真命题，因而qp 为假命题。 （8）2000:p年 10 月 1 日天气晴好，今日（1999 年 2 月 13 日）我们还不 知道 p 的真假，但 p 的真值是确定的（客观存在的） ，只是现在不知道而已。 （9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 课后答案网 h t t p :

4、/ / w w w . k h d a w . c o m h t t p : / / w w w . k h d a w . c n 2 （10）p：小李在宿舍里. p 的真值则具体情况而定，是确定的。 （12）qp，其中，4:p是偶数，4:q是奇数。由于 q 是假命题，所以，q 为假命题，qp为真命题。 （13）qp， 其中，4:p是偶数，4:q是奇数， 由于 q 是假命题， 所以，qp 为假命题。 （14） p：李明与王华是同学，真值由具体情况而定（是确定的） 。 （15） p：蓝色和黄色可以调配成绿色。这是真命题。 分析 命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不 能

5、马上知道，但它们的真值不会变化，是客观存在的。 13 令, 633:, 422:=+=+qp则以下命题分别符号化为 （1）qp （2）qp （3）qp （4）qp （5）qp （6）qp （7）qp （8）qp 以上命题中， （1） ， （3） ， （4） ， （5） ， （8）为真命题，其余均为假命题。 分析 本题要求读者记住qp及qp的真值情况。qp为假当且仅当 p 为真,q 为假,而qp为真当且仅当 p 与 q 真值相同.由于 p 与 q 都是真命题， 在 4 个蕴含式中，只有（2）rp，其中，p 同（1） ，r：明天为 3 号。 在这里，当 p 为真时，r 一定为假，rp为假，当 p

6、为假时，无论 r 为真 还是为假，rp为真。 课后答案网 h t t p : / / w w w . k h d a w . c o m h t t p : / / w w w . k h d a w . c n课后答案网 h t t p : / / w w w . k h d a w . c o m h t t p : / / w w w . k h d a w . c n 3 15 （1）qp，其中，p：2 是偶数，q：2 是素数。此命题为真命题。 （2）qp，其中，p：小王聪明，q：小王用功 （3）qp，其中，p：天气冷，q：老王来了 （4）qp，其中，p：他吃饭，q：他看电视 （5）q

7、p，其中，p：天下大雨，q：他乘公共汽车上班 （6）qp，其中，p，q 的含义同（5） （7）qp，其中，p，q 的含义同（5） （8）qp，其中，p：经一事，q：长一智 分析 1在前 4 个复合命题中，都使用了合取联结词，都符号化为合取式， 这正说明合取联结词在使用时是很灵活的。在符号化时，应该注意，不要将联结 词部分放入简单命题中。例如，在（2）中，不能这样写简单命题：p：小王不但 聪明，q：小王而且用功。在（4）中不能这样写：p：他一边吃饭， q：他一边 看电视。 2 后 4 个复合命题中，都使用了蕴含联结词，符号化为蕴含式，在这里， 关键问题是要分清蕴含式的前件和后件。 qp所表达的基

8、本逻辑关系为，p 是 q 的充公条件，或者说 q 是 p 的必要 条件，这种逻辑关系在叙述上也是很灵活的。例如， “因为 p，所以 q” ， “只要 p， 就 q” “p 仅当 q” “只有 q 才 p” “除非 q，否则p” “没有 q，就没有 p”等都表 达了 q 是 p 的必要条件，因而都符号化为qp或qp的蕴含式。 在（5）中，q 是 p 的必要条件，因而符号化为qp，而在（6） （7）中， p 成了 q 的必要条件，因而符号化为pq。 在（8）中，虽然没有出现联结词，但因两个命题的因果关系可知，应该符 号化为蕴含式。 16 （1） ， （2）的真值为 0， （3） ， （4）的真值为

9、 1。 分析 1 （1）中公式含 3 个命题变项，因而它应该有823=个赋值：000， 课后答案网 h t t p : / / w w w . k h d a w . c o m h t t p : / / w w w . k h d a w . c n 4 001，111 题中指派 p, q 为 0, r 为 1，于是就是考查 001 是该公式)(rqp 的成真赋值，还是成假赋值，易知 001 是它的成假赋值。 2 在公式（2） ， （3） ， （4）中均含 4 个命题就项，因而共有1624=个赋值： 0000，0001，1111。现在考查 0011 是它的成假赋值。 1.7 （1） ， （

10、2） ， （4） ， （9）均为重言式， （3） ， （7）为矛盾式， （5） ， （6） ， （8） ， （10）为非重言式的可满足式。 一般说来，可用真值表法、等值演算法、主析取范式（主合取范式）法等判 断公式的类型。 （1）对（1）采用两种方法判断它是重言式。 真值表法 表 1.2 给出了（1）中公式的真值表，由于真值表的最后一列全为 1，所以， （1）为重言式。 p q r rqp )(rqpp 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 等值演算法 )(rqpp )(r

11、ppp （蕴含等值式） rppp)( （结合律） rq 1 （排中律） 1 （零律） 5 由最后一步可知， （1）为重言式。 （2）用等值演算法判（2）为重言式。 ppp)( pp)( （蕴含等值式） pp （等幂律） pp （蕴含等值式） 1 （排中律） （3）用等值演算法判（3）为矛盾式 qqp)( qqp)( （蕴含等值式） qqp （德摩根律） )(qqp （结合律） 0p （矛盾律） 0 （零律） 由最后一步可知， （3）为矛盾式。 （5）用两种方法判（5）为非重言式的可满足式。 真值表法 p q p qp pq )()(pqqp 0 0 1 0 1 1 0 1 1 1 1 1 1

12、0 0 1 1 1 1 1 0 1 0 0 由表 1.3 可知（5）为非重言式的可满足式。 主析取范式法 )()(pqqp )()(pqqp 6 )()(pqqp pqqp)( qp )1 () 1(qp )()(qppqqp )()()()(qpqpqpqp )()()(qpqpqp 210 mmm. 在（3）的主析取范式中不含全部（4 个）极小项，所以（3）为非重言式的 可满足式，请读者在以上演算每一步的后面，填上所用基本的等值式。 其余各式的类型，请读者自己验证。 分析 o 1 真值表法判断公式的类别是万能。公式 A 为重言式当且仅当 A 的 真值表的最后一旬全为 1；A 为矛盾式当且仅

13、当 A 的真值表的最后一列全为 0；A 为非重言式的可满足式当且仅当 A 的真值表最后一列至少有一个 1，又至少有一 个 0。真值表法不易出错，但当命题变项较多时，真值表的行数较多。 o 2 用等值演算法判断重言式与矛盾式比较方例， A 为重言式当且仅当 A 与 1 等值；A 为矛盾式当且仅当 A 与 0 等值，当 A 为非重言式的可满足式时，经过 等值演算可将 A 化简，然后用观察法找到一个成真赋值，再找到一个成假赋值， 就可判断 A 为非重言式的可满足式了。例如，对（6）用等值演算判断它的类型。 qpp)( q 0 （矛盾律） )0()(qqp （等价等值式） )0()0(qq （蕴含等值

14、式） qq)1 ( （同一律） q1 （零律） 7 q （同一律） 到最后一步已将公式化得很简单。由此可知，无论 p 取 0 或 1 值，只要q取 0 值，原公式取值为 1，即 00 或 10 都为原公式的成真赋值，而 01，11 为成假赋 值，于是公式为非重言式的可满足式。 用主析取范式判断公式的类型也是万能的。A 为重言式当且仅当 A 的主析取 范式含 n 2 （n为 A 中所含命题变项的个数）个极小项；A 为矛盾式当且仅当 A 的 主析取范式中不含任何极小项，记它的主析取范式为 0；A 为非重言式的可满足 式当且仅当 A 的主析取范式中含极小项，但不是完全的。 当命题变项较多时，用主析取

15、范式法判公式的类型，运算量是很大的。 用主合取范式判断公式的类型也是万能的。A 为重言式当且仅当 A 的主合取 范式中不含任何极大项，此时记 A 的主合取范式为 1；A 为矛盾式当且仅当 A 的 主合取范式含 n 2 个极大项（n为 A 中含的命题变项的个数） ；A 为非重言式的可 满足式当且仅当 A 的主析取范式中含含极大项，但不是全部的。 1.8 （1）从左边开始演算 )()(qpqp )(qqp （分配律） 1 p （排中律） . p （同一律） （2）从右边开始演算 )(rqp )(rqp （蕴含等值式） )()(rpqp （分配律） ).()(rpqp （蕴含等值式） （3）从左边开始演算 )(qp 8 )()(pqqp )()(qpqp )()()()(qpqqpqp )()(qpqp ).()(qpqp 请读者填上每步所用的基本等值式。 本题也可以从右边开始演算 )()(qpqp )()(qpqp