发布时间 : 星期一 文章(完整版)离散数学答案(尹宝林版)第一章习题解答更新完毕开始阅读
非永真的可满足式。
设A中出现的命题变元是p1,…, pn，v1和v2分别是使得A为真的真值赋值和使得A为假的真值赋值。取公式B1,…, Bn, C1,…, Cn如下：
?p??p若v2(pi)?1?p??p若v1(pi)?1 Ci?? Bi??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)
(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?q
(6) ?(p ? q) ? p ? q
p ? ?q ? ?(p ? ?q) ? (p ? (q ? 1)) ? 1 ? (p ? q) ? (1 ? 1) ? (p ? q) ? 0 ? p ? q
10.用等值演算证明以下公式是永真式。 (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) (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)?1?1?1
11.用等值演算证明以下公式是永假式。 (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) ?(?p?q)?(?q?r)?p??r?((?p?q)?p)?((?q?r)??r) ?p?q??q??r?0
12.找出与下列公式等值的尽可能简单的由{?,?}生成的公式。 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中出现偶数次。
证明 首先证明：若A是由{?}生成的仅出现一个命题变元p的公式，则
?1A???p对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?1?p。
设在A中的出现的所有命题变元为p1,?,pn，它们的出现次数分别为k1,?,kn。因为
A?B??(A?B)??(B?A)?B?A，并且
(A?B)?C??(?(A?B)?C)?A?B?1?C?1 ?A?B?C?1?1??(A??(B?C))?A?(B?C)
所以?满足交换律和结合律，存在由{?}生成的公式B1,?,Bn，使得
A?B1???Bn，并且Bi仅出现命题变元pi，出现次数为ki，i?1,?,n。若k1,?,kn全为偶数，则A?B1???Bn?1???1?1。若k1,?,kn中有
kl1,?,klm是奇数，则A?B1???Bn?pl1???plm，显然A不是永真式。15.设A是由{?}生成的公式。证明：A是永假式当且仅当每个命题变元在A中出现偶数次。
证明 首先证明：若A是由{?}生成的仅出现一个命题变元p的公式，则
?0A???p对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。若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全为偶数，则