《离散数学第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