离散数学答案(尹宝林版)第一章习题解答.docx

1、第一章命题逻辑习题与解答 判断下列语句是否为命题，并讨论命题的真值。 2x - 3 = 0。 前进！ 如果 8 + 7 20，则三角形有四条边。 请勿吸烟！ 你喜欢鲁迅的作品吗？ 如果太阳从西方升起，你就可以长生不老。 如果太阳从东方升起，你就可以长生不老。解,表达命题，其中,表达真命题，表达假命题。 将下列命题符号化： 逻辑不是枯燥无味的。 我看见的既不是小张也不是老李。 他生于 1963 年或 1964 年。 只有不怕困难，才能战胜困难。 只要上街，我就去书店。 如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐。 如果林芳在家里，那么他不是在做作业就是在看电视。 三角形三条边相等是

2、三个角相等的充分条件。 我进城的必要条件是我有时间。 他唱歌的充分必要条件是心情愉快。 小王总是在图书馆看书，除非他病了或者图书馆不开门。解 p：逻辑是枯燥无味的。“逻辑不是枯燥无味的”符号化为 p。p：我看见的是小张。q：我看见的是老李。 “我看见的既不是小张也不是老李”符号化为p q 。p：他生于 1963 年。q：他生于 1964 年。“他生于 1963 年或 1964 年”符号化为 p q。p：害怕困难。q：战胜困难。 “只有不怕困难，才能战胜困难”符号化为q p。p：我上街。q：我去书店。 “只要上街，我就去书店”符号化为 p q。p：小杨晚上做完了作业。q：小杨晚上没有其它事情。r

3、：小杨晚上看电视。s：小杨晚上听音乐。“ 如果晚上 做完了作 业并且没有其 它事情， 小杨就看电视 或听音乐 ”符号化为p q r s 。p：林芳在家里。q：林芳做作业。r：林芳看电视。 “如果林芳在家里，那么他不是在做作业就是在看电视”符号化为 p q r 。p：三角形三条边相等。q：三角形三个角相等。“三角形三条边相等是三个角相等的充分条件”符号化为 p q 。p：我进城。q：我有时间。 “我进城的必要条件是我有时间”符号化为p q。p：他唱歌。q：他心情愉快。 “他唱歌的充分必要条件是心情愉快” 符号化为 p q 。p：小王在图书馆看书。q：小王病了。r：图书馆开门。“小王总是在图书馆看

4、书，除非他病了或者图书馆不开门”符号化为(q r) p，或者(q r) p。也可符号化为 (q r) p，或者 (q r) p。 列出除 ， ， ， ， 之外的所有二元联结词的真值表。解共有 16 个二元联结词，记除 ， ， ， ， 之外的二元联结词为D1, D2 , D11 。pqpD1qpD2qpD3qpD4qpD5qpD6q00000001010001101001100011001010pqpD7 qpD8qpD9qpD10qpD11q0011111010011110110111101001 求下列公式在真值赋值( p1 / 1, p2 / 1, p3 / 0, p4 / 0)下的值：

5、p1 ( p2 p3 ) ( p1 p2 p3 ) ( p1 p2 ) ( p3 p4 ) ( p1 p2 ) p3 (p1 p2 ) p3 ) p4 )(4)(p2 p1) (p3 p4) ( p1 p3 ) (p2 p4 ) p1 ( p2 p3 p1 ) p2 p4(7)(p1 p3) (p2 p4)解记真值赋值( p1 / 1, p2 / 1, p3 / 0, p4 / 0)为 v。 v( p1 ( p2 p3 ) = 1 (1 0) = 1 。 v( p1 p2 p3 ) ( p1 p2 ) ( p3 p4 ) = (1 1 0) (1 1) (0 0) = 1 v( p1 p2 )

6、 p3 (p1 p2 ) p3 ) p4 )= (1 1) 0 (1 1) 0) 0) = 1。(4)v (p2 p1) ( p3 p4) = (1 1) ( 0 0) = 0 1 = 1。 v( p1 p3 ) (p2 p4 ) = (1 0) (1 0) = 0 。 v( p1 ( p2 p3 p1) p2 p4 ) = 1 (1 0 1) 1 0 = 1 。(7)v (p1 p3) (p2 p4) = (1 0) (1 0) = 0 0 = 0。5. 用真值表判断以下公式是不是永真式、永假式、可满足式。(1)(p r) (q r) (p q r)(2) ( p p) p(3)(p q)

7、(p q) p)(4) ( p (q r) ( p q) ( p r)(5) ( p q) ( p r) (q r) r(6)p (p q)(7) ( p q) ( p q) p)解(1)将(p r) (q r) (p q r)记为 A。pqrp rq rp qp q r (q r) (p q r)A000110111001110111010101011011111111100011001101111111110001011111111111(p r) (q r) (p q r) 是永真式。(3) 将(p q) (p q) p) 记为 A。pqp qqp q(p q) pA0011100011

8、010010011111110011(p q) (p q) p) 是非永真的可满足式。(6)pq0 pp q011 (p q)0p (p q)0011100100010110100p (p q) 是永假式。解(1), (2), (4), (5), (7)是永真式，(6)是永假式，(3)是非永真的可满足式。6. 指出满足下列公式的所有真值赋值。(1) ( p q) (p r)(2) p (q r ( p q)(3) p r ( p r) (q r)(4)p (q r)解(1) ( p / 0, q / 0, r / 0) ， ( p / 0, q / 0, r /1) ， ( p / 0, q

9、/1, r / 0) ， ( p / 0, q /1, r /1) ， ( p /1, q / 0, r /1) ， ( p /1, q /1, r / 0) ， ( p /1, q /1, r /1)。(2) ( p / 0, q /1, r / 0) ， ( p /1, q / 0, r / 0) ， ( p /1, q / 0, r /1) ， ( p /1, q /1, r / 0) ， ( p /1, q /1, r /1)。(3) ( p / 0, q / 0, r / 0) ， ( p / 0, q /1, r / 0) 。(4) 任取满足 p (q r) 的真值赋值 v。若 v

10、 (p) = 0，则 v (q r) = 1，v (q) = v (r)。若 v (p) = 1，则 v (q r) = 0，v (q) v (r)。所以，满足 p (q r) 的真值赋值有以下四个：( p / 0, q / 0, r / 0)，( p / 0, q / 1, r / 1)，( p / 1, q / 0, r / 1)，( p / 0, q / 1, r / 0)。7. 若公式 A 既不是永真式，也不是永假式，则A 的每个替换实例一定既不是永真式，也不是永假式。对吗？解不对。若 A 是非永真的可满足式，则它的替换实例中既有永真式，也有永假式，也有非永真的可满足式。设 A 中出现

11、的命题变元是 p1, pn，v1 和 v2 分别是使得 A 为真的真值赋值和使得 A 为假的真值赋值。取公式 B1, Bn, C1, Cn 如下： p p若 v ( p ) = 1 p p若 v( p ) = 1B = 1iC = 2ii任取真值赋值 v，p p若 v ( p ) = 01iip p若 v ( p ) = 02i1v( Ap ,L, pn) = v p/ v(B ),L, p/ v(B )(A) = v ( A) = 1，B ,L,B11nn11n1v( Ap ,L, pnC ,L,C) = v p1/ v(C ),L, p1n/ v(Cn)(A) = v2( A) = 0 ，

12、1n1所以，A 的替换实例 Ap ,L, pnB ,L,B是永真式，A 的替换实例 Ap ,L, pn1C ,L,C是永假式。1n1nA 本身也是 A 的替换实例，它是非永真的可满足式。8. 用真值表证明以下等值式。(1) p (q r) (p q) ( p r)pqrq rp (q r)p qp r(p q) ( p r)0000000000110000010100000110000010000000101110111101110111100110(2)(3)(4)9. 用等值演算证明以下等值式。 (1) p (q r) q ( p r)(2) ( p q) ( p r) p q r(3)

13、(p q) (r q) p r q(4) p (q p) p ( p q)(5) ( p q) (r q) p r q(6) (p q) p q解(1) p (q r) p (q r) q (p r) q ( p r)(2) ( p q) ( p r) (p q) (p r) p (q r) p q r(3)(p q) (r q) ( p q) ( r q) ( p r) (q q) ( p r) q ( p r) q p r q(4) p (q p) p q p 1 p p q p ( p q)(5)( p q) (r q) (p q) (r q) (p r) q ( p r) q p r

14、q(6)(p q) p qp q (p q) (p (q 1) 1 (p q) (1 1) (p q) 0 p q10. 用等值演算证明以下公式是永真式。(1) (q p) (p q) p(2) (p q) (r s) (p r q s)(3) ( p q) ( p r) ( p s) ( p q r s)(4) ( p q r) ( p r) (q r)解(1) (q p) (p q) p (q p) ( p q) p p p 1(2)( p q) (r s) ( p r q s) (p q) (r s) p r q s (p q) p (r s) r q s q p s r q s 1(3

15、)( p q) ( p r) ( p s) ( p q r s) p q p r p s ( p q r s) p q r s p q r s 1(4)( p q r) ( p r) (q r) ( p q) r) p r q r ( p q) r) p q r ( p q p q r) (r p q r) 11 111. 用等值演算证明以下公式是永假式。(1) (q p) (p q) p(2) ( p q) (q r) ( p r)解(1) (q p) (p q) p (q p) ( p q) p p p 0(2)( p q) (q r) ( p r) (p q) (q r) (p r) (

16、p q) (q r) p r (p q) p) (q r) r) p q q r 012. 找出与下列公式等值的尽可能简单的由, 生成的公式。13. 找出与下列公式等值的尽可能简单的由, 生成的公式。(1) p q (r p)(2) ( p q r) p q(3) p q p解 (1) p q (r p) p q (r p) (p q r) (p q p) p q r ( p q r)(2) ( p q r) p q (p q r) p q (p q r) p q)(3) p q p (p q p)14. 设 A 是由生成的公式。证明：A 是永真式当且仅当每个命题变元在 A 中出现偶数次。证明

17、首先证明：若 A 是由生成的仅出现一个命题变元 p 的公式，则1pA 对 p 在 A 中的出现次数进行归纳。若p在A中出现偶数次若p在A中出现奇数次若 p 在 A 中出现 1 次，即 A 为 p，显然 A p 。若 p 在 A 中出现 2 次，即 A 为 p p ，显然 A 1。设p 在A 中的出现n 次，A 为 B C ，p 在B，C 中的出现次数分别为k 和l，则n = k + l ， k n 且l n 。若 n 为偶数,则 k 和 l 的奇偶性相同，B 和 C 等值于同一公式， A 1。若 n 为奇数,则 k 和 l 的奇偶性不同，B 和 C 中一个等值于 p，另一个是永真式，因此A p

18、 1 p 。设在 A 中的出现的所有命题变元为 p1,L, pn ，它们的出现次数分别为k1,L, kn 。因为A B ( A B) (B A) B A ，并且( A B) C ( A B) C) A B 1 C 1 A B C 11 ( A (B C) A (B C)nniii所 以 满 足 交 换 律 和 结 合 律 ， 存 在 由 生 成 的 公 式 B1,L, B ， 使 得A B1 L B ，并且 B 仅出现命题变元 p ，出现次数为 k ， i = 1,L, n 。若k1,L, kn 全为偶数， 则 A B1 L Bn 1L1 1 。 若 k1,L, kn 中有llk ,L, k1

19、m是奇数，则 A B1L B pL pl1lm，显然 A 不是永真式。n15. 设 A 是由生成的公式。证明：A 是永假式当且仅当每个命题变元在 A 中出现偶数次。证明首先证明：若 A 是由生成的仅出现一个命题变元 p 的公式，则 pA 0对 p 在 A 中的出现次数进行归纳。若 p 在 A 中出现偶数次若 p 在 A 中出现奇数次若 p 在 A 中出现 1 次，即 A 为 p，显然 A p。若 p 在 A 中出现 2 次，即 A 为 p p，显然 A 0。设 p 在 A 中出现 n 次，A 为 B C，p 在 B，C 中的出现次数分别为 k 和 l，则n = k + l，k n 且 l n。

20、若 n 为偶数,则 k 和 l 的奇偶性相同，B 和 C 等值于同一公式， A 0。若 n 为奇数,则 k 和 l 的奇偶性不同，B 和 C 中一个等值于 p，另一个是永假式， 因此 A p 0 p。设在 A 中的出现的所有命题变元为 p1, pn，它们的出现次数分别为 k1, kn。因为满足交换律和结合律，所以存在由生成的公式 B1, Bn，使得 A B1 Bn，Bi 中仅出现命题变元 pi，并且出现次数为 ki ，i = 1, n。若 k1, kn 全为偶数，则lA B1 Bn 0 0 0。若 k1, kn 中有k1,L, klm是奇数，则nA B1 L B p L pl1lm，显然 A

21、不是永假式。16. 北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。甲说：“天津第一，上海第二。”乙说：“天津第二，广州第三。”丙说：“北京第二，广州第四。”比赛结果显示，每人猜对了一半，并且没有并列名次。问：实际名次怎样排列？解用字母表示命题如下：p2：北京第二，q2：上海第二，r1：天津第一， r2：天津第二，s3：广州第三，s4：广州第四。由已知条件列出以下方程：甲猜对了一半：r1 q2 = 1，乙猜对了一半：r2 s3 = 1， 丙猜对了一半：p2 s4 = 1； 每个城市只能得一个名次：r1 r2 = 0，s3 s4 = 0；没有并列名次：p2 q2 = 0，p2 r2

22、 = 0，r2 q2 = 0。解以上8个方程组成的方程组。r2 = r2 1 = r2 (r1 q2) = (r2 r1 ) ( r2 q2) = 0 0 = 0，将 r2 = 0 代入 r2 s3 = 1 得 s3 = 1，将 s3 = 1 代入 s3 s4 = 0 得 s4 = 0，将 s4 = 0 代入 p2 s4 = 1 得 p2 = 1，将 p2 = 1 代入 p2 q2 = 0 得 q2 = 0，将 q2 = 0 代入 r1 q2 = 1 得 r1 = 1。将 p2 = r1 = s3 = 1，q2 = r2 = s4 = 0 代入 8 个方程验证它们满足方程组。因此，天津第一，北

23、京第二，广州第三，上海第四。17.某勘探队取回一块矿样，三人判断如下。甲说：“矿样不含铁，也不含铜。”乙说：“矿样不含铁，含锡。”丙说：“矿样不含锡，含铁。”已经知道，这三人中有一个是专家，一个是老队员，一个是实习队员。化验结果表明：这块矿样只含一种金属，专家的两个判断皆对，老队员的判断一对一错，实习队员的两个判断皆错。问：这三人的身分各是什么？解p :矿样含铁，q :矿样含铜，甲说的两句话为： p ， q 乙说的两句话为： p ， r 丙说的两句话为： r ， pr :矿样含锡。如果用一个公式表达出这三人中有一个是专家，一个是老队员，一个是实习队员，公式会非常复杂。其实我们不必完全写出这样的

24、公式。因为矿样只含一种金属，所以 p q = 0 ，q r = 0 ，r p = 0 。甲是实习队员，即甲说的两句话都是错的，可表示为： p q 。乙是实习队员，即乙说的两句话都是错的，可表示为： p r 。丙是实习队员，即丙说的两句话都是错的，可表示为： r p 。甲、乙、丙三人中至少有一个是实习队员，可表示为：( p q) ( p r) (r p) = 1因为 p q = 0 ，所以( p r) (r p) = 1，即 p r = 1 ， p 和r 中恰好有一个为 1， 因此q = 0 。甲是老队员，即甲说的话一半对一半错，可表示为：p q 。乙是老队员， 即乙说的话一半对一半错，可表示为

25、：p r 。丙是老队员，即丙说的话一半对一半错， 可表示为： r p 。甲、乙、丙三人中有奇数个老队员，可表示为：(p q) (p r) (r p) = 1由教材上的等值式可得到(p q) (p r) (r p) (p p) (r r) (q p) 0 1 (q 1 p) q p又知道q = 0 ，所以 p = 1。因为r p = 0 ，所以r = 0 。因此，甲说的话一半对一半错， 甲是老队员。乙说的话全错，乙是实习队员。丙说的话全对，丙是专家。18. 先用等值演算证明下列等值式，再用对偶定理得出新等值式。(1) (p q) (p q) p(2) ( p q) ( p q) (p q) (p

26、 q)(3) q (p q) p) 1解(1) (p q) (p q) ( p q) ( p q) p (q q) p由对偶定理得(p q) (p q) p 。(2)( p q) ( p q) (p q) ( p (q q) (p q) p (p q) ( p p) ( p q) p q (p q)由对偶定理得( p q) ( p q) (p q) (p q) 。(3)19. 设 A 是由0, 1, , , 生成的公式，A*与 A 互为对偶式。(1) 若 A 是永真式，则 A*是永假式。(2) 若 A 是永假式，则 A*是永真式。证明(1) 设 A 是永真式，则 A 1，由对偶定理得 A* 0

27、，因此 A*是永假式。(2) 设 A 是永假式，则 A 0，由对偶定理得 A* 1，因此 A*是永真式。20. 证明以下联结词集合是极小完全集。(1) 0, (2) , (3) , , (4) , , 证明 (1) p p 0 p 0，因为, 是完全集，所以0, 是完全集。任取由0生成的不出现除命题变元p 之外的命题变元的公式A，令真值赋值v = (p/0)，则v(A) = 0，而v(p) = 1，因此0不能定义。所以0不是完全集。任取由生成的仅出现命题变元p 的公式A，令真值赋值v = (p/1)，则v(A) = 1 ，而 v(p) = 0 ，因此 不能定义。所以不是完全集。所以0, 是极小

28、完全集。(2) p p 1 p (p p)，因为, 是完全集，所以, 是完全集。任取由生成的仅出现命题变元p 的公式A，令真值赋值v = (p/0)，则 v(A) = 0，而v(p) = 1，因此不能定义。所以不是完全集。不是完全集。所以, 是极小完全集。(3) p p 1 p (p p)，因为, 是完全集，所以, , 是完全集。任取由, 生成的仅出现命题变元p 的公式A，令真值赋值v = (p/0)，则 v(A) = 0，而v(p) = 1 ，因此, 不能定义。所以, 不是完全集。任取由, 生成的仅出现命题变元p 的公式A，令真值赋值v = (p/1)，则v(A) = 1，而 v(p) =

29、0，因此, 不能定义。所以, 不是完全集。, 不是完全集。所以, , 是极小完全集。(4) p p 1 p (p p)，因为, 是完全集，所以, , 是完全集。任取由, 生成的仅出现命题变元p 的公式A，令真值赋值v = (p/0)，则 v(A) = 0，而v(p) = 1 ，因此, 不能定义。所以, 不是完全集。任取由, 生成的仅出现命题变元p 的公式A，令真值赋值v = (p/1)，则v(A) = 1，而 v(p) = 0，因此, 不能定义。所以, 不是完全集。, 不是完全集。所以, , 是极小完全集。21. 证明以下联结词集合不是完全集。(1) , , , (2) , , 证明 (1)

30、任取由, , , 生成的仅出现命题变元p 的公式A，令真值赋值v = ( p /1) ，则v( A) = 1，而v(p) = 0 ，因此, , , 不能定义 。所以, , , 不是完全集。(2) 任取由 , , 生成的仅出现命题变元 p 的公式 A，令真值赋值 v = ( p / 0) ，则v( A) = 0 ，而v(p) = 1 ，因此 , , 不能定义 。所以 , , 不是完全集。22. 二元联结词 （称为“与非”）和 （称为“或非”）的真值表如下。pqp qp q0011011010101100证明：(1) 是完全集。(2) 是完全集。(3) 若 D 是二元联结词且D是完全集，则 D 是

31、 或 。证明(1) p p p,p q (p q) (p q) (p q) (p q)， 因为, 是完全集，所以是完全集。(2) p p p ,p q (p q) (p q) (p q) (p q) ，因为, 是完全集，所以是完全集。(3)若 0 D 0 = 0 或 1 D 1 = 1，则 不能由D定义。因此，0 D 0 = 1 且 1 D 1 = 0。若 0 D 1 1 D 0，则 D 的真值表的最后一列有偶数个 1，真值表最后一列有奇数个1 的 不能由D定义。所以，0 D 1 = 1 D 0。若 0 D 1 = 1 D 0 = 1，则 D 是 。若0 D 1 = 1 D 0 = 0，则 D

32、 是 。23. 三元联结词D 的真值表如下。pqrD( p, q, r)00010011010001101000101011011110证明 D 是极小完全集。证明p q Dpqq ，因为 是完全集，所以 D 是极小完全集。24.在下列公式中，哪些是析取范式，哪些是合取范式?p，p q，(p q) r，p r，p p，(p q) q) r解p，p q，p r，p p 是析取范式，p，p q，p r，(p q) r，p p 是合取范式。25. 在下列公式中，哪些是关于 p, q, r 的主析取范式，哪些是关于 p, q, r 的主合取范式？p q r,p q r,(p q r) ( p q r)

33、,p ( q r),(p p q) ( p q r)解p q r 是关于 p, q, r 的主析取范式，p q r 是关于 p, q, r 的主合取范式。26.是否有这样的公式，它既是主合取范式，又是主析取范式？如果有，举出一例。解有。p 既是关于 p 的主析取范式，又是关于 p 的主合取范式。27. 求下列公式的主范式，进而判断其是否永真式、永假式、可满足式。(1) p q r(2) ( p q) r(3) p q ( p q)(4) p ( p q (q r)(5) ( p q r) (p q r)(6) p q (p q)解(1) p q r (p q) r p q rp q r 的主合

34、取范式是 p q r ，包含一个极大项，因此它是非永真的可满足式。(2) ( p q) r (p q) r (p q) r ( p r) (q r) ( p (q q) r) ( p p) q r) ( p q r) ( p q r) (p q r)( p q) r 的主合取范式是( p q r) ( p q r) (p q r) ，包含了三个极大项，因此它是非永真的可满足式。(3) p q ( p q) (p q) (p q) ( p q) (p q) ( p q) ( p q) p q p qp q ( p q) 的主合取范式为 p q ，包含了一个极大项，因此它是非永真的可满足式。(4) p ( p q (q r) p (p q (q r) 1p ( p q (q r) 的主合取范式为1 ，不包含任何极大项，因此它是永真式。(5) ( p q r) (p q r) (p (q r) (p (q r) (p p) (p q r) (q r p) (q r q r) (p q r) ( p q r)( p q r) (p