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

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

q：我去书店只要上街，我就去书店”符号化为p qp：小杨晚上做完了作业q：小杨晚上没有其它事情r：小杨晚上看电视s：小杨晚上听音乐 如果晚上做完了作业并 且没有其它事情，小杨 就看电视或听音乐”符 号化为srqpp：林芳在家里q：林芳做作业r：林芳看电视如果林芳在家里，那么他不是在做作业就是在看电视”符号化为rqpp：三角形三条边相等q：三角形三个角相等三角形三条边相等是三个角相等的充分条件”符号化为qpp：我进城q：我有时间我进城的必要条件是我有时间”符号化为p qp：他唱歌q：他心情愉快他唱歌的充分必要条件是心情愉快”符号化为qpp：小王在图书馆看书q：小王病了r：图书馆开门小王总是在图书馆看书，除非他病了或者图书馆不开门”符号化为(qr) p，或者( qr) p也可符号化为(qr) p，或者(qr) p 列出除，之外的所有二元联结词的真值表解共有 16 个二元联结词， 记除，之外的二元联结词为1121,p q qp1qp2qp3qp4qp5qp60 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0 0 1 1 0 0 1 0 1 0 p q qp7qp8qp9qp10qp110 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 求下列公式在真值赋值( p1 / 1, p2 / 1, p3 / 0, p4 / 0)下的值：)(321ppp)()()(4321321ppppppp)()(4321321ppppppp(4)(p2 p1) ( p3 p4)()(4231pppp421321)(pppppp(7)(p1 p3) (p2 p4)解记真值赋值( p1 / 1, p2 / 1, p3 / 0, p4 / 0)为v。

1)01(1)(321pppv1)00()11()011()()()(4321321pppppppv)()(4321321pppppppv1)0)0)11(0)11(4)v (p2 p1) ( p3 p4) = (1 1) ( 0 0) = 0 1 = 10)01()01()()(4231ppppv101)101(1)(421321ppppppv7)v (p1 p3) ( p2 p4) = (1 0) ( 1 0) = 0 0 = 05. 用真值表判断以下公式是不是永真式、永假式、可满足式1) (pr) (qr) (p qr)(2) ppp)(3) (pq) (pq) p)(4) )()()(rpqprqp(5) rrqrpqp)()()(6) p(pq)(7) )()(pqpqp解(1) 将(pr) (qr) (p qr)记为Apqrpr qrp q p qr (qr) (p qr)A 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 (pr) (qr) (p qr) 是永真式。

3) 将(pq) (pq) p) 记为Apqppq(pq) pA 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 1 0 0 1 1 (pq) (pq) p) 是非永真的可满足式6) pq ppq (pq) p(pq)0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 p(pq) 是永假式解(1), (2), (4), (5), (7) 是永真式， (6)是永假式， (3)是非永真的可满足式6. 指出满足下列公式的所有真值赋值1) )()(rpqp(2) )(qprqp(3) )()(rqrprp(4) p (qr)解(1) )0/,0/,0/(rqp，)1/,0/,0/(rqp，)0/,1/,0/(rqp，)1/,1/,0/(rqp，)1/,0/,1/(rqp，)0/,1/,1/(rqp，)1/,1/,1/(rqp2) )0/,1/,0/(rqp，)0/,0/,1/(rqp，)1/,0/,1/(rqp，)0/,1/,1/(rqp，)1/, 1/,1/(rqp3) )0/,0/,0/(rqp，)0/,1/,0/(rqp。

4) 任取满足p (qr) 的真值赋值v若v (p) = 0，则v (qr) = 1，v (q) = v (r)若v (p) = 1，则v (qr) = 0，v (q) v (r)所以，满足p (qr) 的真值赋值有以下四个：( 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 中出现的命题变元是p1, pn，v1和v2分别是使得A为真的真值赋值和使得A为假的真值赋值取公式B1, Bn, C1, Cn如下：0)(1)(11iiipvpppvppB若若0)(1)(22iiipvpppvppC若若任取真值赋值v，1)()(/,),(/)(111,11AvABvpBvpvAvnnppBBnn，0)()(/,),(/)(211,11AvACvpCvpvAvnnppCCnn，所以，A的替换实例nnppBBA,11是永真式，A的替换实例nnppCCA,11是永假式。

A 本身也是A 的替换实例，它是非永真的可满足式8. 用真值表证明以下等值式1)p(q r) (pq)( pr)pqrqrp (q r) p qp r(pq) ( pr)0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 (2) (3) (4) 9. 用等值演算证明以下等值式1) )()(rpqrqp(2) rqprpqp)()(3) (pq) (rq) p rq(4) )()(qpppqp(5) qrpqrqp)()(6) (pq) p q解(1) )()()()(rpqrpqrqprqp(2) rqprqprpqprpqp)()()()()(3) (pq) (rq) ( pq) ( rq) ( p r) () ( p r) q ( p r) qp rq(4) )(1)(qppqpppqppqp(5) qrpqrqpqrqp)()()()()(qrpqrp)(6) (pq) pqp q(pq) (p (q 1) 1 (pq) (1 1) (pq) 0 pq10. 用等值演算证明以下公式是永真式。

1) pqppq)()(2) (pq) (rs) (p rq s)(3) )()()()(srqpsprpqp(4) )()()(rqrprqp解(1) pqppq)()(1)()(pppqppq(2) )()()(sqrpsrqpsqrpsrqp)()(sqrsrpqp)()(1sqrspq(3) )()()()(srqpsprpqp)(srqpsprpqp1srqpsrqp(4) )()()(rqrprqprqrprqp)(rqprqp)(111)()(rqprrqpqp11. 用等值演算证明以下公式是永假式1) pqppq)()(2) )()()(rprp解(1) pqppq)()(0)()(pppqppq(2) )()()(rprp)()()(rprprprp)()()()(rrqpqp0rp12. 找出与下列公式等值的尽可能简单的由,生成的公式13. 找出与下列公式等值的尽可能简单的由,生成的公式1) )(prqp(2) qprqp)(3) pqp解(1) )(prqp)(prqp)()(pqprqprqp)(rqp(2) )()()(qprqpqprqpqprqp(3) )(pqppqp14. 设A是由生成的公式。

证明：A是永真式当且仅当每个命题变元在A中出现偶数次证明首先证明：若A是由生成的仅出现一个命题变元p的公式，则中出现奇数次在若中出现偶数次在若AppApA1对p在A中的出现次数进行归纳若p在A中出现 1 次，即A为p，显然pA若p在A中出现 2 次，即A为pp，显然1A设p在A中的出现n次，A为CB，p在B，C中的出现次数分别为k和l， 则lkn，nk且nl若n为偶数 , 则k和l的奇偶性相同，B和C等值于同一公式，1A若n为奇数 , 则k和l的奇偶性不同，B和C中一个等值于p，另一个是永真式，因此ppA1设在A中的出现的所有命题变元为npp,1，它们的出现次数分别为nkk,1因为ABABBABA)()(，并且11)()(CBACBACBA)()(11CBACBACBA所 以满 足 交 换 律 和 结 合 律 ， 存 在 由生 成 的 公 式nBB,1， 使 得nBBA1，并且iB仅出现命题变元ip，出现次数为ik，ni, 1若nkk,1全 为 偶 数 ， 则1111nBBA 若nkk,1中 有mllkk,1是奇数，则mllnppBBA11，显然A不是永真式15. 设A是由生成的公式 证明：A是永假式当且仅当每个命题变元在A中出现偶数次。

证明首先证明：若A 是由生成的仅出现一个命题变元p的公式，则中出现奇数次在若中出现偶数次在若AppApA0对p在A中的出现次数进行归纳若p在A中出现 1 次，即A为p，显然A p若p在A中出现 2 次，即A为pp，显然A 0设p在A中出现n次，A为BC，p在B，C 中的出现次数分别为k和l，则n = k + l，k n且l n若n为偶数 , 则k和l的奇偶性相同，B和C等值于同一公式，A 0若n为奇数 , 则k和l的奇偶性不同，B和C中一个等值于p，另一个是永假式，因此A p0p设在A中的出现的所有命题变元为p1, pn，它们的出现次数分别为k1, kn因为满足交换律和结合律，所以存在由生成的公式B1, Bn，使得A B1 Bn，Bi中仅出现命题变元pi，并且出现次数为ki ，i = 1, n若k1, k。