发布时间 : 星期二 文章离散数学第1章习题答案更新完毕开始阅读552ee048c281e53a5802ffd0
第1章 命题逻辑
(1)若A∨C?B∨C，则A?B。 (2)若A∧C?B∧C，则A?B。 (3)若?A??B，则A?B。 (4)若A?C?B?C，则A?B。 (5)若A?C?B?C，则A?B。
解 (1)不正确。例如，设有一赋值：A＝T，B＝F，C＝T，则A∨C?B∨C，但A?B不成立。 (2)不正确。例如，设有一赋值：A＝T，B＝F，C＝F，则A∧C?B∧C，但A?B不成立。 (3)正确。因为?A??B?(?A??B)∧(?B??A)?(A∨?B)∧(B∨?A)?(B? A)∧(A?B)? A?B，所以，若?A??B，则A?B。
(4)不正确。例如，设有一赋值：A＝T，B＝F，C＝T，则A?C?B?C，但A?B不成立。 (5)正确。因为，若A?C?B?C，则A?C与B?C等值。当A?C与B?C都为真时，A和C等值且B和C等值，从而A和B等值，此时A?B；当A?C与B?C都为假时，A和C不等值且B和C也不等值，从而A和B等值，此时A?B。
总之有，若A?C?B?C，则A?B。 8.试给出下列命题公式的对偶式： (1)(P∧Q)∨R。 (2)T∨(P∧Q)。 (3)(P∨Q)∧F。
(4)?(P∧Q)∧(?P∨Q)。 解 (1)对偶式为(P∨Q)∧R。 (2)对偶式为F∧(P∨Q)。 (3)对偶式为(P∧Q)∨T。
(4)对偶式为?(P∨Q)∨(?P∧Q)。
9.分别用真值表法、分析法和公式法证明下列蕴涵式： (1)?(P?Q)?P。 (2)(P?Q)?Q?P∨Q。 (3)P?Q?P?(P∧Q)。 (4)(P?Q)∧(Q?R)?(P?R)。 证明 (1)真值表法：
P Q 0 0 0 1 1 0 1 1 P?Q 1 1 0 1 ? (P?Q) 0 0 1 0 P 0 0 1 1 由真值表可知，?(P?Q)?P。
9
第1章 命题逻辑
分析法：若?(P?Q)为真，则P?Q为假，从而P为真，而Q为假。故?(P?Q)?P。 公式法：因为?(P?Q)?P?(?P∨Q)∨P?T，所以?(P?Q)?P。 (2)真值表法：
P Q 0 0 0 1 1 0 1 1 P?Q 1 1 0 1 (P?Q)?Q 0 1 1 1 P∨Q 0 1 1 1 由真值表可知，(P?Q)?Q?P∨Q。
分析法：若P∨Q为假，都P和Q为假，于是P?Q为真，从而(P?Q)?Q为假。故(P?Q)?Q?P∨Q。
公式法：因为((P?Q)?Q)?(P∨Q)? ?(?(?P∨Q)∨Q)∨(P∨Q)
?((?P∨Q)∧?Q)∨(P∨Q) ?(?P∧?Q)∨(Q∧?Q)∨(P∨Q) ??(P∨Q)∨(P∨Q) ?T
所以，(P?Q)?Q?P∨Q。 (3)真值表法：
P Q 0 0 0 1 1 0 1 1 P∧Q 0 0 0 1 P?Q 1 1 0 1 P?(P∧Q) 1 1 0 1 由真值表可知，P?Q?P?(P∧Q)。
分析法：若P?(P∧Q)为假，则P为真且P∧Q为假，于是P为真且Q为假，从而P?Q为假。故P?Q?P?(P∧Q)。
公式法：因为(P?Q)?(P?(P∧Q))??(?P∨Q)∨(?P∨(P∧Q)
?(P∧?Q)∨(?P∨(P∧Q) ?(P∧?Q)∨(?P∨Q) ?(P∧?Q)∨?(P∧?Q) ?T
所以，P?Q?P?(P∧Q)。 (4)真值表法：
P Q R P?Q Q?R (P?Q)∧(Q?R) P?R 10
第1章 命题逻辑
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 由真值表可知，(P?Q)∧(Q?R)?(P?R)。
分析法：若P?R为假，则P为真而R为假。当Q为真时，Q?R为假；当Q为假时，P?Q为假。从而不管Q取什么值，都有(P?Q)∧(Q?R)为假。故(P?Q)∧(Q?R)?(P?R)。
公式法：因为((P?Q)∧(Q?R))?(P?R)??((?P∨Q)∧(?Q∨R))∨(?P∨R)
?(P∧?Q)∨(Q∧?R)∨?P∨R
?(P∧?Q)∨((Q∨?P∨R)∧(?R∨?P∨R)) ?(P∧?Q)∨(Q∨?P∨R)
?(P∨Q∨?P∨R)∧(?Q∨Q∨?P∨R) ?T
所以，(P?Q)∧(Q?R)?(P?R)。
10.将下列命题公式化成与之等价的仅含联结词?或?的公式： (1)P∧(Q?R)。 (2)(P?(Q∧R))∨P。 解 因为
?P??(P∧P)?P?P
P∧Q??(P?Q)?(P?Q)?(P?Q)
P∨Q??(?P∧?Q)??P??Q?(P?P)?(Q?Q) ?P??(P∨P)?P?P
P∨Q??(P?Q)?(P?Q)?(P?Q) P∧Q??P??Q?(P?P)?(Q?Q) 所以
(1)P∧(Q?R)?P∧(?Q∨R)
? P∧((?Q)?(?Q))?(R?R) ? P∧((Q?Q)?( Q?Q))?(R?R)
?(P?(((Q?Q)?( Q?Q))?(R?R)))?(P?(((Q?Q)?( Q?Q))?(R?R)))
P∧(Q?R)? P∧(?Q∨R)
? P∧((?Q)P?R)?((?Q)P?R) ? P∧((Q?Q)P?R)?(( Q?Q)P?R)
?(P?P)?((((Q?Q)P?R)?(( Q?Q)P?R))?(((Q?Q)P?R)?(( Q?Q)P?R)))
11
第1章 命题逻辑
(2)(P?(Q∧R))∨P?(?P∨(Q∧R))∨P
?(( P?P)∨((Q?R)?(Q?R)))∨P ?(( P?P)∨((Q?R)?(Q?R)))∨P
?((( P?P)?(P?P))?((((Q?R)?(Q?R)))?(((Q?R)?(Q?R)))))∨P ?((((( P?P)?(P?P))?((((Q?R)?(Q?R)))?(((Q?R)?(Q?R))))))?(((( P?
P)?(P?P))?((((Q?R)?(Q?R)))?(((Q?R)?(Q?R)))))))?(P?P)
(P?(Q∧R))∨P?(?P∨(Q∧R))∨P
?(( P?P)∨((Q?Q)?(R?R)))∨P
?((( P?P)?((Q?Q)?(R?R))))?(( P?P)?((Q?Q)?(R?R)))))∨P
?((((( P?P)?((Q?Q)?(R?R))))?(( P?P)?((Q?Q)?(R?R))))))?P)?(((((
P?P)?((Q?Q)?(R?R))))?(( P?P)?((Q?Q)?(R?R))))))?P)
11.证明{∧，∨}，{∨}和{?}都不是全功能联结词组。
证明 命题P经联结词∧和∨反复运算只能得出P，不能得出?P，所以{∧，∨}不是全功能联结词组。
命题P经联结词∨反复运算只能得出P，不能得出?P，所以{∨}不是全功能联结词组。 命题P经联结词?反复运算只能得出P和?P，不能得出P∧Q，所以{?}不是全功能联结词组。 12.证明{?，∧}是最小全功能联结词组。 证明 因为 P∨Q??(?P∧?Q) P?Q??P∨Q??(P∧?Q)
P?Q?(P?Q)∧(Q?P)??(P∧?Q)∧?(Q∧?P) 所以，{?，∧}是最小全功能联结词组。 13.完成定理1.8的证明。
证明 设A为简单析取式，其包含的所有命题变元为p1、p2、…、pn。
若A为永真式，但不同时含有某个命题变元及其否定，则不妨设A＝p1∨p2∨?∨pi∨?pi＋1∨?∨?pn，于是当p1、p2、?、pi的真值都是假，而pi＋1、?、pn的真值都是真时，A的真值为假，与A为永真式矛盾。
反之，若A同时含有某个命题变元及其否定，显然有A为永真式。 14.完成定理1.10的证明。
证明 公式A为矛盾式当且仅当A的析取范式的每个简单合取式都是矛盾式。由定理1.7可得，简单合取式是矛盾式当且仅当它同时有一个命题变元及其否定。因此，公式A为矛盾式当且仅当A的析取范式的每个简单合取式至少同时含有一个命题变元及其否定。
15.完成定理1.11的证明。
证明 公式A为永真式当且仅当A的合取范式的每个简单析取式都是永真式。由定理1.8可得，简
12