离散数学答案（尹宝林版）第一章习题解答

第一章 命题逻辑

习题与解答

⒈ 判断下列语句是否为命题，并讨论命题的真值。 ⑴ 2x ? 3 = 0。 ⑵ 前进！

⑶ 如果8 + 7 > 20，则三角形有四条边。 ⑷ 请勿吸烟！

⑸ 你喜欢鲁迅的作品吗？

⑹ 如果太阳从西方升起，你就可以长生不老。 ⑺ 如果太阳从东方升起，你就可以长生不老。

解 ⑶,⑹,⑺表达命题，其中⑶,⑹表达真命题，⑺表达假命题。 ⒉ 将下列命题符号化： ⑴ 逻辑不是枯燥无味的。

⑵ 我看见的既不是小张也不是老李。 ⑶ 他生于1963年或1964年。 ⑷ 只有不怕困难，才能战胜困难。 ⑸ 只要上街，我就去书店。

⑹ 如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐。 ⑺ 如果林芳在家里，那么他不是在做作业就是在看电视。 ⑻ 三角形三条边相等是三个角相等的充分条件。 ⑼ 我进城的必要条件是我有时间。 ⑽ 他唱歌的充分必要条件是心情愉快。

⑾ 小王总是在图书馆看书，除非他病了或者图书馆不开门。 解 ⑴ 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：小杨晚上看电视。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：图书馆开门。

“小王总是在图书馆看书，除非他病了或者图书馆不开门”符号化为?(q ? ?r) ? p，或者 (?q ? r) ? p。也可符号化为 ?(q ? ?r) ? p，或者 (q ? ?r) ? p。 ⒊ 列出除?，?，?，?，?之外的所有二元联结词的真值表。

解 共有16个二元联结词，记除?，?，?，?，?之外的二元联结词为?1,?2,?,?11。

p 0 0 1 1

q 0 1 0 1 p 0 0 1 1 q 0 1 0 1 p?1q 0 0 0 0 p?2q 0 0 1 0 p?3q 0 0 1 1 p?4q 0 1 0 0 p?5q 0 1 0 1 p?6q 1 0 0 0 p?7q 1 0 1 0 p?8q 1 0 1 1 p?9q 1 1 0 0 p?10q 1 1 1 0 p?11q 1 1 1 1

⒋ 求下列公式在真值赋值( p1 / 1, p2 / 1, p3 / 0, p4 / 0)下的值： ⑴ 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)??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) ? ((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。

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p ? r q ? r p ? q p ? q ? r (q ? r) ? (p ? q ? r) A 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 (p ? r) ? ((q ? r) ? (p ? q ? r)) 是永真式。

(3) 将 (p ? q) ? ((p ? ?q) ? p) 记为A。

p 0 q 0 p ? q 1 ?q 1 p ? ?q 1 (p ? ?q) ? p 0 A 0

0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 (p ? q) ? ((p ? ?q) ? p) 是非永真的可满足式。

(6)

p 0 0 1 1 q 0 1 0 1 ? p 1 1 0 0 p ? q 1 1 0 1 ? (p ? q) 0 0 1 0 ?p ? ?(p ? q) 0 0 0 0 ?p ? ?(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/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 (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中出现的命题变元是p1,?, pn，v1和v2分别是使得A为真的真值赋值和使得A为假的真值赋值。取公式B1,?, Bn, C1,?, Cn如下：

?p??p若v2(pi)?1?p??p若v1(pi)?1Bi?? Ci??

p??p若v(p)?0p??p若v(p)?02i1i??任取真值赋值v，

p1,?,pnv(AB)?v[p1/v(B1),?,pn/v(Bn)](A)?v1(A)?1， 1,?,Bnp1,?,pnv(AC)?v[p1/v(C1),?,pn/v(Cn)](A)?v2(A)?0， 1,?,Cn所以，A的替换实例AB11,?,Bnn是永真式，A的替换实例AC11,?,Cnn是永假式。 A本身也是A的替换实例，它是非永真的可满足式。

8. 用真值表证明以下等值式。

(1) p ? (q ? r) ? (p ? q) ? ( p ? r)

p,?,pp,?,pp 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 q ? r 0 1 1 0 0 1 1 0 p ? (q ? r) 0 0 0 0 0 1 1 0 p ? q 0 0 0 0 0 0 1 1 p ? r 0 0 0 0 0 1 0 1 (p ? q) ? ( p ? r) 0 0 0 0 0 1 1 0 (2) (3) (4)

9.用等值演算证明以下等值式。 (1) p?(q?r)?q?(p?r) (2) (p?q)?(p?r)?p?q?r (3) (p ? q) ? (r ? q) ? p ? r ? q (4) p?(q?p)??p?(p?q)

v(p?q?r)?0。所以p?q?r,p?q??r|?/p?q?r。

30.判断以下公式组成的集合是否可满足，并说明理由。 (1) (p?q)?(s??r)，?(s??r)

(2) p1，?p1?p2，?p1??p2?p3,?，?p1????pn?pn?1,? (3) p?q，?p??q，p?q

解 (1) 可满足。真值赋值(p/1,q/0,r/1,s/0)满足它。

(2) 可满足。若真值赋值v使得v(pi)?1,i?1,2,?，则v满足它。 (3) 可满足。真值赋值(p/0,q/1)满足它。

31.设A,B,C是任意公式。A?B|?C当且仅当A|?C且B|?C。

证明1 （?）设A?B|?C。任取满足A的真值赋值v，则v(A?B)?1，因为A?B|?C，所以v(C)?1。这表明A|?C。任取满足B的真值赋值v，则v(A?B)?1，因为A?B|?C，所以v(C)?1。这表明B|?C。

（?）设A|?C且B|?C。任取满足A?B的真值赋值v，则v(A)?1或v(B)?1。 ① 若v(A)?1，因为A|?C，所以v(C)?1。 ② 若v(B)?1，因为B|?C，所以v(C)?1。 因此，A?B|?C。

证明2 A?B?C??(A?B)?C?(?A??B)?C

?(?A?C)?(?B?C)?(A?C)?(B?C)

A?B|?C

当且仅当A?B?C是永真式

当且仅当(A?C)?(B?C)是永真式 当且仅当A?C和B?C都是永真式 当且仅当A|?C且B|?C

32.设?1和?2是公式集合，B是公式，?2|?B，对于?2中每个公式A，?1|?A。证明：

?1|?B。

证明 任取满足?1的真值赋值v。对于?2中每个公式A，因为?1|?A，所以v(A)?1。这表明v满足?2。又因为?2|?B，所以v(B)?1。因此，?1|?B。 33.公式集合?不可满足当且仅当?|?0。

证明 （?）设?|?/0，则存在真值赋值v满足?且v(0)?0，因此?可满足。 （?）设?|?0。若?可满足，有真值赋值v满足?，由?|?0得出v(0)?1，这是不可能的。因此，?不可满足。

34.设n是正整数，??{p1?q1,?,pn?qn,p1???pn}?{?(qi?qj)|1?i?j?n}。证明：?|?(q1?p1)???(qn?pn)。

证明 设真值赋值v满足?，则v(p1???pn)?1，存在i?n使v(pi)?1。因为所以v(qi)?1。若1?j?i，因为v(?(qj?qi))?1，因此v(qj)?0。v(pi?qi)?1，若

i?j?n，因为v(?(qi?qj))?1，因此v(qj)?0。所以

v((q1?p1)???(qn?pn))?1。

本文来源：https://www.bwwdw.com/article/8x9v.html