发布时间 : 星期日 文章(完整版)离散数学答案(尹宝林版)第一章习题解答更新完毕开始阅读
A ? B1 ? … ? Bn ? 0 ? … ? 0 ? 0。若 k1,…, kn 中有kl1,?,klm是奇数，则
A?B1???Bn?pl1???plm，显然A不是永假式。
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 = 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个方程验证它们满足方程组。
因此，天津第一，北京第二，广州第三，上海第四。 17.某勘探队取回一块矿样，三人判断如下。 甲说：“矿样不含铁，也不含铜。” 乙说：“矿样不含铁，含锡。” 丙说：“矿样不含锡，含铁。”
已经知道，这三人中有一个是专家，一个是老队员，一个是实习队员。化验结果表明：这块矿样只含一种金属，专家的两个判断皆对，老队员的判断一对一错，实习队员的两个判断皆错。问：这三人的身分各是什么？
r:矿样含锡。 解 p:矿样含铁， q:矿样含铜，
甲说的两句话为：?p，?q
乙说的两句话为：?p，r 丙说的两句话为：?r，p
如果用一个公式表达出这三人中有一个是专家，一个是老队员，一个是实习队员，公式会非常
复杂。其实我们不必完全写出这样的公式。因为矿样只含一种金属，所以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。乙是老队员，即乙说的话一半对一半错，可表示为：?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?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，因此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, ?}是极小完全集。
(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) = 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) 任取由{?,?,?,?}生成的仅出现命题变元p的公式A，令真值赋值v?(p/1)，则v(A)?1，而v(?p)?0，因此{?,?,?,?}不能定义?。所以{?,?,?,?}不是完全集。
(2) 任取由{?,?,?}生成的仅出现命题变元p的公式A，令真值赋值v?(p/0)，则
v(A)?0，而v(?p)?1，因此{?,?,?}不能定义?。所以{?,?,?}不是完全集。
22. 二元联结词 ?（称为“与非”）和 ?（称为“或非”）的真值表如下。
p 0 0 1 1 证明：
q 0 1 0 1 p ? q p ? q 1 1 1 0 1 0 0 0 (1) {?}是完全集。 (2) {?}是完全集。
(3) 若 ? 是二元联结词且{?}是完全集，则 ? 是 ? 或 ? 。 证明 (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 ? 0 = 0或1 ? 1 = 1，则 ? 不能由{?}定义。因此，0 ? 0 = 1且1 ? 1 = 0。 若0 ? 1 ? 1 ? 0，则 ? 的真值表的最后一列有偶数个1，真值表最后一列有奇数个1的 ? 不能由{?}定义。所以，0 ? 1 = 1 ? 0。若0 ? 1 = 1 ? 0 = 1，则 ? 是 ? 。若
0 ? 1 = 1 ? 0 = 0，则 ? 是 ? 。
23.三元联结词?的真值表如下。 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,q,r) 1 1 0 0 0 0 1 0 证明 p?q??pqq，因为{?}是完全集，所以{?}是极小完全集。 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),
p ? ( q ? r), (p ? ?p ? q) ? ( p ? q ? r)
解 p ? ?q ? r是关于p, q, r的主析取范式，p ? q ? r是关于p, q, r的主合取范式。
26.是否有这样的公式，它既是主合取范式，又是主析取范式？如果有，举出一例。