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） ， （15）都是简单的
2、陈述句，因而作为命题，它们都是简单命题。 （6）和（7）各为由联结词“当且仅当” 联结起来的复合命题，（12）是由联结词“ 或” 联结的复合命题，而（ 13）是由联结词 “且”联结起来的复合命题。这里的“ 且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如， “虽然 ，但是” 、 “不仅，而且”、 “一面，一面”、 “和”、 “与”等。但要注意，有时“和” 或“与”联结的是主语，构成简单命题。例如， （14） 、 （15）中的“与” 与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和” 或“与”出现的命题时，要根据命题所陈述的含义加以区分。12 （1
3、）p: 2 是无理数，p 为真命题。（2）p:5 能被 2 整除，p 为假命题。（6）pq。其中，p:2 是素数，q：三角形有三条边。由于 p 与 q 都是真命题，因而 pq 为假命题。（7）pq，其中，p：雪是黑色的，q：太阳从东方升起。由于 p 为假命题，q 为真命题，因而 pq 为假命题。（8）p:2000 年 10 月 1 日天气晴好，今日（1999 年 2 月 13 日）我们还不知道 p 的真假，但 p 的真值是确定的（客观存在的） ，只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。1（10）p：小李在宿舍里. p 的真值则具体情况而定，是确定的。（
4、12）pq，其中，p:4 是偶数，q:4 是奇数。由于 q 是假命题，所以，q为假命题，pq 为真命题。（13）pq，其中，p:4 是偶数，q:4 是奇数，由于 q 是假命题，所以，pq为假命题。（14） p：李明与王华是同学，真值由具体情况而定（是确定的） 。（15） p：蓝色和黄色可以调配成绿色。这是真命题。分析 命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。13 令 p:2+2=4,q:3+3=6,则以下命题分别符号化为（1）pq（2）pq（3）pq（4）pq（5）pq（6）pq（7）pq（8）pq以上命题中， （1） ， （
5、3） ， （4） ， （5） ， （8）为真命题，其余均为假命题。分析 本题要求读者记住 pq 及 pq 的真值情况。pq 为假当且仅当p 为真,q 为假,而 pq 为真当且仅当 p 与 q 真值相同.由于 p 与 q 都是真命题，在 4 个蕴含式中，只有（2）pr，其中，p 同（1） ，r：明天为 3 号。在这里，当 p 为真时，r 一定为假，pr 为假，当 p 为假时，无论 r 为真还是为假，pr 为真。215 （1）pq，其中，p：2 是偶数，q：2 是素数。此命题为真命题。（2）pq，其中，p：小王聪明，q：小王用功（3）pq，其中，p：天气冷，q：老王来了（4）pq，其中，p：他吃饭
6、，q：他看电视（5）pq，其中，p：天下大雨，q：他乘公共汽车上班（6）pq，其中，p，q 的含义同（5）（7）pq，其中，p，q 的含义同（5）（8）pq，其中，p：经一事，q：长一智分析 1在前 4 个复合命题中，都使用了合取联结词，都符号化为合取式，这正说明合取联结词在使用时是很灵活的。在符号化时，应该注意，不要将联结词部分放入简单命题中。例如，在（2）中，不能这样写简单命题：p：小王不但聪明，q：小王而且用功。在（4）中不能这样写：p：他一边吃饭， q：他一边看电视。2 后 4 个复合命题中，都使用了蕴含联结词，符号化为蕴含式，在这里，关键问题是要分清蕴含式的前件和后件。pq 所表达的
7、基本逻辑关系为，p 是 q 的充公条件，或者说 q 是 p 的必要条件，这种逻辑关系在叙述上也是很灵活的。例如， “因为 p，所以 q”， “只要 p，就 q”“p 仅当 q”“只有 q 才 p”“除非 q，否则p”“ 没有 q，就没有 p”等都表达了 q 是 p 的必要条件，因而都符号化为 pq 或pq 的蕴含式。在（5）中，q 是 p 的必要条件，因而符号化为 pq，而在（6） （7）中，p 成了 q 的必要条件，因而符号化为 qp。在（8）中，虽然没有出现联结词，但因两个命题的因果关系可知，应该符号化为蕴含式。16 （1） ， （2）的真值为 0， （3） ， （4）的真值为 1。分析
8、1 （ 1）中公式含 3 个命题变项，因而它应该有 23=8 个赋值：000，3001，111 题中指派 p, q 为 0, r 为 1，于是就是考查 001 是该公式 p(qr)的成真赋值，还是成假赋值，易知 001 是它的成假赋值。2 在公式（2） ， （3） ， （4）中均含 4 个命题就项，因而共有 24=16 个赋值：0000，0001，1111。现在考查 0011 是它的成假赋值。1.7 （ 1） ， （2） ， （4 ） ， （9）均为重言式， （3） ， （7）为矛盾式， （5） ， （6） ，（8） ， （10）为非重言式的可满足式。一般说来，可用真值表法、等值演算法、主析取
9、范式（主合取范式）法等判断公式的类型。（1）对（1）采用两种方法判断它是重言式。真值表法表 1.2 给出了（1）中公式的真值表，由于真值表的最后一列全为 1，所以，（1）为重言式。pqrp(p qr)p q r0 0 0 0 10 0 1 1 10 1 0 1 10 1 1 1 11 0 0 1 11 0 1 1 11 1 0 1 11 1 1 1 1等值演算法p(p qr)p (pp r) （蕴含等值式）(pp)pr （结合律）1qr （排中律）1 （零律）4由最后一步可知， （1）为重言式。（2）用等值演算法判（2）为重言式。(pp)p(p)p （蕴含等值式）p p （等幂律） pp （蕴
10、含等值式）1 （排中律）（3）用等值演算法判（3）为矛盾式(pq)q(pq) q （蕴含等值式） pq q （德 摩根律） p(q q) （结合律） p0 （矛盾律）0 （零律）由最后一步可知， （3）为矛盾式。（5）用两种方法判（5）为非重言式的可满足式。真值表法p q p pqqp(pq)(qp)0 0 1 0 1 10 1 1 1 1 11 0 0 1 1 11 1 0 1 0 0由表 1.3 可知（5）为非重言式的可满足式。主析取范式法(pq)(qp)(pq)(q p)5(pq)(qp)(pq)q pp q(p1)(1q)(p(qq)(pp)q)(pq)(pq)(pq)(p q)(pq
11、)(pq)(pq)m0m1m2.在（3）的主析取范式中不含全部（4 个）极小项，所以（3）为非重言式的可满足式，请读者在以上演算每一步的后面，填上所用基本的等值式。其余各式的类型，请读者自己验证。分析 1 真值表法判断公式的类别是万能。公式 A 为重言式当且仅当 A 的 o真值表的最后一旬全为 1；A 为矛盾式当且仅当 A 的真值表的最后一列全为0；A 为非重言式的可满足式当且仅当 A 的真值表最后一列至少有一个 1，又至少有一个 0。真值表法不易出错，但当命题变项较多时，真值表的行数较多。2o 用等值演算法判断重言式与矛盾式比较方例，A 为重言式当且仅当 A 与 1等值；A 为矛盾式当且仅当
12、 A 与 0 等值，当 A 为非重言式的可满足式时，经过等值演算可将 A 化简，然后用观察法找到一个成真赋值，再找到一个成假赋值，就可判断 A 为非重言式的可满足式了。例如，对（ 6）用等值演算判断它的类型。(pp)q0q （矛盾律）(pq)(q0) （等价等值式）(0q)(q0) （蕴含等值式）(1q)q （同一律）1q （零律）6q （同一律）到最后一步已将公式化得很简单。由此可知，无论 p 取 0 或 1 值，只要 q 取 0值，原公式取值为 1，即 00 或 10 都为原公式的成真赋值，而 01，11 为成假赋值，于是公式为非重言式的可满足式。用主析取范式判断公式的类型也是万能的。A
13、为重言式当且仅当 A 的主析取范式含 2n（n 为 A 中所含命题变项的个数）个极小项； A 为矛盾式当且仅当 A 的主析取范式中不含任何极小项，记它的主析取范式为 0；A 为非重言式的可满足式当且仅当 A 的主析取范式中含极小项，但不是完全的。当命题变项较多时，用主析取范式法判公式的类型，运算量是很大的。用主合取范式判断公式的类型也是万能的。A 为重言式当且仅当 A 的主合取范式中不含任何极大项，此时记 A 的主合取范式为 1；A 为矛盾式当且仅当 A 的主合取范式含 2n 个极大项（n 为 A 中含的命题变项的个数） ；A 为非重言式的可满足式当且仅当 A 的主析取范式中含含极大项，但不是
14、全部的。1.8 （1）从左边开始演算(pq)(pq) p(qq)（分配律）p1 （排中律）p.（同一律）（2）从右边开始演算p(q r)p (qr) （蕴含等值式）(pq)(pr) （分配律）(pq)(pr).（蕴含等值式）（3）从左边开始演算(pq)7(pq)(qp)(pq)(pq)(pq)(p)(qq)(pq)(p q)(pq)(pq)(pq).请读者填上每步所用的基本等值式。本题也可以从右边开始演算(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(qp)(qq) (1 pq)(q p)1(pq)(qp)(pq).读者填上每步所用的基本的等值式。1.9 （1
15、）(p q)p)(pq)p （蕴含等值式）(pq)p) （德摩根律） pqp （结合律、交换律）(pp)q （矛盾式）0. （零律）8由最后一步可知该公式为矛盾式。（2）(pq)(qp)(pq)(pq)p) （蕴含等值式）由于较高层次等价号两边的公式相同，因而此公式无成假赋值，所以，它为重言式。（3）(pq)(qp)(pq)(q p) （蕴含等值式）(pq)(qp) （蕴含等值式）(pq)qp （德摩根律）q p （吸收律）p q. （交换律）由最后一步容易观察到，11 为该公式成假赋值，因而它不是重言式，又00，01，10 为成真赋值，因而它不是矛盾式，它是非重言式的可满足式。1.10 题中
16、给出的 F，G，H，R 都是 2 元真值函数。给出的 5 个联结词集都是全功能集，可以用观察法或等值演算法寻找与真值函数等值的公式。首先寻找在各联结词集中与 F 等值的公式。（1）设 A=(pq)，易知 A 是,中公式且与 F 等值，即 FA.（2）设 B=pq，易知 B 是,中公式且与 F 等值，即 FB.（3）设 C=(pq)，易知 C 是, 中公式，且 FC.（4）设 D=(p(qq)(p(qq)，易知 D 为中公式，且 FD.（5）设 E=(pp)q，易知 E 为中公式，且 FE.分析 1 只要找到一个联结词集中与 F 等值的公式，经过等值演算就可以找出其他联结词集中与 F 等值的公式
17、。例如，已知 A=(pq)是,公式，且FA。进行以下演算，就可以找到 F 等值的其他联结词集中的公式。对 A 进行等值演算，消去联结词，用，取代，得9A=(pq)(pq)pq 记为 B.则 B 为 ,中公式，且 FB。再对 A 进行等值演算，消去，用，取代，得A=(pq)(pq) 记为 C.则 C 为 ,中公式，且 FC。再对 B 进行演算，消去 ，用取代，在演算中，注意，对于任意的公式 A，有A(AA) AA.B=pq p(qq)(p(qq)(p(qq)(p(qq)(p(qq)记为 D.则 D 为中公式，且 FD.再对 C 进行演算，消去,用取代，在演算中注意，对于任意的公式 AA(AA)
18、AA.C=(pq)pq(pp)q 记为 E.则 E 为 中公式，且 FE.2 开始找一个与某真值函数等值的公式的方法，除观察法外，就是根据10该真值函数的真值表，求它的主析取范式，而后进行等值演算即可。例如，由G 的真值表可知 G 的主析取范式为 m1m3，于是Gm1m3(pq)(pq)(pp)qq.由于公式 q 不带联结词，所以，它应该为任何联结词集中的合式公式。3 在各联结词集中找到的与某真值函数等值的公式并不唯一。例如，取A=qq.(,中公式)B=qq.(,中公式)C=qq.(,中公式)D=(qq)(qq).(中公式 )E=(qq)(qq).(中公式 )则 GABCDE,对于同一个真值函数 G，找到与它等值的形式各异的公式。对于 H 和 R，请读者自己去完成。1.11 （1）对 C 是否为矛盾式进行讨论。当 C 不是矛盾式时，ACB C，则一定有 AB，这是因为，此时，
