离散数学最全最新答案屈婉玲.pdf

《离散数学最全最新答案屈婉玲.pdf》由会员分享，可在线阅读，更多相关《离散数学最全最新答案屈婉玲.pdf（18页珍藏版）》请在三一文库上搜索。

1、For personal use only in study and research; not for commercial use 第一章命题逻辑基本概念 课后练习题答案 4. 将下列命题符号化，并指出真值： （1）pq,其中， p:2 是素数， q:5 是素数 ,真值为 1； （2）pq,其中， p:是无理数， q:自然对数的底 e 是无理数 , 真值为 1； （3）pq,其中， p:2 是最小的素数， q:2 是最小的自然数 , 真值为 1； （4）pq,其中， p:3 是素数， q:3 是偶数 ,真值为 0； （5）pq,其中， p:4 是素数， q:4 是偶数 , 真值为 0. 5

2、. 将下列命题符号化，并指出真值： （1）pq,其中， p:2 是偶数， q:3 是偶数 ,真值为 1； （2）pq,其中， p:2 是偶数， q:4 是偶数 ,真值为 1； （3）pq,其中， p:3 是偶数， q:4 是偶数, 真值为 0； （4）pq, 其中， p:3 是偶数， q:4 是偶数 ,真值为 1； （5）pq,其中， p:3 是偶数， q:4 是偶数 , 真值为 0； 6. （1）(pq)(pq), 其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨； （2）(pq)(pq), 其中，p：刘晓月选学英语， q：刘晓月选学日语； . 7. 因为 p 与 q 不能同时为真 . 1

3、3.设 p:今天是星期一， q: 明天是星期二， r: 明天是星期三： （1）pq，真值为 1（不会出现前件为真，后件为假的情况）； （2）qp，真值为 1（也不会出现前件为真，后件为假的情况）； （3）pq，真值为 1； （4）pr，若 p 为真，则 pr真值为 0，否则， pr真值为 1. 16 设 p、q 的真值为 0；r、s 的真值为 1，求下列各命题公式的真值。 （1）p(q r)0(0 1) 0 （2） （p? r ）( qs) （0? 1）(1 1) 010. （3） （pqr）? (p qr) （111） ? (0 00)0 (4) （r s）(pq) （01）(1 0) 00

4、1 17判断下面一段论述是否为真：“是无理数。并且，如果3 是无理数，则 2也是无理数。另外 6 能被 2 整除， 6 才能被 4整除。” 答：p: 是无理数1 q: 3 是无理数0 r: 2是无理数1 s:6 能被 2 整除1 t: 6 能被 4 整除0 命题符号化为：p(qr)(ts)的真值为 1，所以这一段的论述为真。 19用真值表判断下列公式的类型： （4）(pq) (qp) （5）(pr) (pq) （6）(pq) (qr) (pr) 答：（4） p q pq q p qp (pq)(qp) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1

5、1 0 0 1 1 所以公式类型为永真式/最后一列全为1 （5）公式类型为可满足式（方法如上例）/最后一列至少有一个1 （6）公式类型为永真式（方法如上例）/ 返回 第二章命题逻辑等值演算 本章自测答案 3. 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) (pqq) (2)(p(pq)(pr) (3)(pq)(pr) 答：(2)（p(pq)）(pr)(p(pq)(pr)ppqr1 所以公式类型为永真式 (3) P q r pq pr （pq）(pr) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1

6、 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4. 用等值演算法证明下面等值式： (2)(p q) (p r)(p (qr) (4)(p q) (pq)(pq) (p q) 证明（ 2）(p q) (p r) (pq) (pr) p(q r) p(q r) （4）(p q) (pq)(p(pq) (q(pq) (p p) (p q) (qp) (qq) 1(p q) (p q) 1 (p q) (p q) 5. 求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(pq) (qp) (2)(p q) qr (3)(p

7、(q r) (p qr) 解： （1）主析取范式 (pq) (qp) (pq)(qp) (pq)(qp) (pq)(qp)(qp)(pq)(pq) (pq)(pq)(pq) 320 mmm (0,2,3) 主合取范式： (pq)(qp) (pq)(qp) (pq)(qp) (p(qp)(q(qp) 1(pq) (pq) M1 (1) (2) 主合取范式为： (p q)qr(pq)qr (pq)qr0 所以该式为矛盾式 . 主合取范式为 (0,1,2,3,4,5,6,7) 矛盾式的主析取范式为 0 (3)主合取范式为： (p(qr) (pqr) (p(qr) (pqr) (p(qr)(pqr)

8、(p(pqr)(qr)(pqr) 11 1 所以该式为永真式 . 永真式的主合取范式为 1 主析取范式为 (0,1,2,3,4,5,6,7) 7.(1) ：?；(2) ：?； 8.(1) ： 1?, 重言式；(2) ： ?；(3) ：? 0， 矛盾式. 11.(1) ：? ；(2) ：? 1；(3) ： 0?. 12.A?. 第三章命题逻辑的推理理论 本章自测答案 6. 在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断 *是否为重言式，若 *是重言式，推理就正确，否则推理 就不正确，这里不考虑简单语句之间的内在联系 (1) 、(3) 、(6) 推理正确，其余的均不

9、正确，下面以(1) 、(2) 为例，证明 (1) 推理正确， (2) 推理不正确 (1) 设 p: 今天是星期一， q: 明天是星期三，推理的形式结构为 (pq)pq(记作 *1) 在本推理中，从 p 与 q 的内在联系可以知道， p 与 q 的内在联系可以知道， p 与 q 不可能同时为真，但在证明时，不考虑这一点，而只考虑*1 是否为重言式 . 可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为 p,B 为 q 时，*1为假言推理定律，即 (pq)pq ? q (2) 设 p: 今天是星期一， q: 明天是星期三，推理的形式结构为 (pq)pq(记

10、作 *2) 可以用多种方法证明 *2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等 (pq)qp ? ( pq) q p ? q p ? pq ? 从而可知， *2不是重言式，故推理不正确，注意，虽然这里的p 与 q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推 理不正确 . 9. 设 p:a 是奇数， q:a 能被 2 整除，r:a ：是偶数 推理的形式结构为 (pq)(r q)(r p) ( 记为*) 可以用多种方法证明 *为重言式，下面用等值演算法证明： (pq)(r q)(r p) ? ( pq) (qr) (qr) ( 使用了交换律 ) ? (pq

11、)( pr) qr ? ( pq)(qr) ? p(q q)r ? 1 10.设 p:a,b 两数之积为负数， q:a,b 两数种恰有一个负数， r ：a，b都是负数 . 推理的形式结构为 (pq)p(qr) ? ( pq) p(qr) ? p( qr) ( 使用了吸收律 ) ? p( qr) ? 由于主析取范式中只含有5 个 W极小项，故推理不正确 . 11. 略 14. 证明的命题序列可不惟一，下面对每一小题各给出一个证明 p(qr)前提引入 P前提引入 qr假言推理 q前提引入 r假言推理 r s前提引入 （2）证明： (pr)前提引入 qr置换 r前提引入 q 析取三段论 pq前提引入

12、 p拒取式 （3）证明： pq前提引入 qq置换 ( pq)(pp) 置换 p(qp置换 p(pq) 置换 15.(1) 证明： S结论否定引入 SP前提引入 P假言推理 P(qr)前提引入 qr假言推论 q前提引入 r假言推理 （2）证明： p附加前提引入 pq附加 (p q)(r s)前提引入 r s假言推理 s化简 s t附加 (s t) u前提引入 u拒取式 16.(1) 证明： p结论否定引入 p q前提引入 q 假言推理 rq前提引入 r析取三段论 r s前提引入 r化简 rr合取 （2）证明： (r s)结论否定引入 rs置换 r化简 s化简 pr前提引入 p拒取式 qs前提引入

13、 q拒取式 pq合取 (pq)置换 口 pq前提引入 口 (pq) (pq) 口合取 16 在自然推理系统P 中用归谬法证明下面各推理： (1) 前提： pq,rq,rs 结论：p 证明： p 结论的否定引入 pq 前提引入 q 假言推理 rq 前提引入 r 化简律 rs 前提引入 r 化简律 rr 合取 由于最后一步rr 是矛盾式 , 所以推理正确 . 17设 p：A到过受害者房间， q: A 在 11点以前离开， r ：A犯谋杀罪， s：看门人看见过 A。前提：(pq) r , p ,q s , s结 论： r证明： qs 前提引入 s 前提引入 q 拒取式 p 前提引入 pq 合取（pq

14、）r 前提引入 r 假言推理 18（1）设 p ：今天是星期六， q：我们要到颐和园玩， s：颐和园游 人太多。前提：p(pr) , sq , p , s结论： r证明： s q前提引入 s前提 引入 q假言推理 p前提引入 p(qr)前提引入 qr 假言推理r析取三段论 （2）设 p: 小王是理科学生， q：小王数学成绩好， r：小王是文科学生。前提： pq , rp , q结论：r证明： pq前提引入 q前提引入 p 拒取式 rp前提引入 r拒取式 返回 第四章 ( 一阶 ) 谓词逻辑基本概念 本章自测答案3. 在一阶逻辑中将下面将下面命题符号化, 并分别讨论个体域限制为(a),(b)条件

15、时命题的真值: (1) 对于任意 x, 均有2=(x+)(x). (2) 存在 x, 使得 x+5=9. 其中 (a) 个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1) 在两个个体域中都解释为 )(xxF ，在（ a）中为假命题，在(b) 中为真命题。 (2) 在两个个体域中都解释为)(xxG，在（ a）(b) 中均为真命题。 4.(1) x(F(x) G(x) ?x( F (x) G (x) ),其中 ,F(x) ：x 是有理数 ,G(x) ：x 能表示成分数； (2) x( F (x) G (x) ) ?x(F(x)

16、G(x), 其中 ,F (x)：x 在北京卖菜 ,G (x) ：x 是外地人； (3)x( F (x) G (x) ),其中 ,F (x)：x 是乌鸦 ,G (x) ：x 是黑色的； (4)xF(x) G(x),其中 ,F (x)：x 是人,G (x) ：x 天天锻炼身体。 因为本题中没有指明个体域, 因而使用全总个体域。 5.(1)xy (F(x) G( y ) H(x,y),其中 ,F(x) ：x 是火车,G(y) ：y 是轮船 ,H(x,y)：x 比 y 快； (2)xy (F(x) G( y ) H(x,y),其中 ,F(x) ：x 是火车,G(y) ：y 是汽车 , H(x,y) ：

17、x 比 y 快； (3) x(F(x) y(G (y) H (x,y)?x(F(x) y(G(y) H(x,y),其中 ,F(x) ：x 是汽车 ,G (y) ：y 是火车,H(x,y)：x 比 y 快； (4) x(F(x) y(G(y) H(x,y)?xy(F(x) G(y)H(x,y),其中 ,F(x) ：x 是汽车,G(y) ：y 是火车 ,H(x,y)：x 比 y 慢。 6. 各命题符号化形式如下： (1)xy (x y = 0) ； (2)xy (x y = 0) ； (3)xy (y =x+1) (4)xy(x y = y x) (5)xy(x y =x+ y) (6)xy (x

18、 + y 0 ) 9.(1) 对任意数的实数x 和 y, 若 x y, 则 x y ； (2) 对任意数的实数x 和 y, 若 xy = 0, 则 xy； (3) 对任意数的实数x 和 y, 若 xy, 则 xy0； (4) 对任意数的实数x 和 y, 若 xy 0, 则 x=y. 其中 ,(1)(3)真值为 1(2) 与(4) 真值为 0. 11.(1) 、(4) 为永真式 ,(2) 、(6) 为永假式 ,(3) 、(5) 为可满足式。 这里仅对 (3) 、(4) 、(5) 给出证明。 (3) 取解释 I 为：个体域为自然数集合N,F(x,y) ：x y, 在下,xy F(x,y)为真, 而

19、xy F(x,y)也为真( 只需取 x =0 即可), 于是(3) 中公 式为真 , 取解释 为：个体域仍为自然数集合N,而 F(x,y) ：x = y 。此时,xyF(x,y) 为真(取 y 为 x 即可), 可是xyF(x,y) 为假, 于是(3) 中公式 在 下为假, 这说明(3) 中公式为可满足式。 (4) 设 I 为任意一个解释 , 若在 I 下, 蕴涵式前件 xy F(x,y)为假, 则 xyF(x,y) yxF(x,y) 为真, 若前件xyF(x,y) 为真, 必存在 I 的个体域 D1中的个体常项x0, 使yF(x0,y) 为真, 并且对于任意 y,F(x0,y) 为真, 由于

20、有x0,F(x0,y) 为真, 所以xF(x,y) 为真, 又其中 y 是任意个体变项 , 所以yxF(x,y )为真, 由于 I 的任意性 , 所 以(4) 中公式为永真式 (其实, 次永真式可用第五章的构造证明法证明之)。 (5) 取解释为：个体域为自然数集合,F(x,y)：x = y 在下,(5) 中公式为真 , 而将 F(x,y) 改为 F(x,y) ：x y,(5)中公式就为假了 , 所以它为 可满足式。 10. 给定解释 I 如下： （a） 个体域 D=N(N为自然数集合 ). （b） D 中特定元素=2. （c） D 上函数=x+y,(x,y)=xy. （d） D 上谓词(x,y

21、):x=y. 说明下列各式在I 下的含义，并讨论其真值. (1)xF(g(x,a),x) (2)xy(F(f(x,a),y)F(f(y,a),x) 答:(1) 对于任意自然数x, 都有 2x=x, 真值 0. (2) 对于任意两个自然数x,y, 使得如果 x+2=y, 那么 y+2=x. 真值 0. 11. 判断下列各式的类型: (1) (3) yF(x,y). 解:(1) 因为1)()(pqppqp为永真式； 所以为永真式； (3) 取解释 I 个体域为全体实数 F(x,y) ：x+y=5 所以, 前件为任意实数x 存在实数 y 使 x+y=5，前件真； 后件为存在实数x 对任意实数 y 都

22、有 x+y=5，后件假， 此时为假命题 再取解释 I 个体域为自然数N ， F(x,y) ：:x+y=5 所以 , 前件为任意自然数x 存在自然数 y 使 x+y=5，前件假。此时为假命题。 此公式为非永真式的可满足式。 13（1）取解释为：个体域为自然数集合N ，F（x）：x 为奇数， G （x）：x 为偶数，在下， x （F（x）G （x）为真命题。取解释 为：个体域为整数集合Z，F（x）：x 为正整数， G （x）：x 为为负整数，在下， x （F（x）G （x）为假命题。（2）与（3）可类似解答。 14提示：对每个公式分别找个成真的解释，一个成假的解释。 返回 第五章谓词逻辑等值演算与

23、推理 本章自测答案 2.(1) (F(a) F(b) F (c) (G (a )G (b) G (c)(2) (F(a) F(b) F (c) (G (a)G (b) G (c)(3) (F(a) F(b) F (c) (G (a)G (b) G (c)(4) (F(a ,y) F(b,y) F (c,y) (G (a)G (b) G (c)5. 提示：先消去量词，后求真值，注意，本 题 3 个小题消去量词时， 量词的辖域均不能缩小， 经过演算真值分别为： 1,0,1 . (1) 的演算如下：xyF(x,y)? x (F(x,3)F(x,4) ? (F(3,3)F(3,4)(F(4,3)F(4

24、 ,4)? 11? 16. 乙说得对，甲错了。本题中，全称量词的指导变元为 x ，辖域为 (F (x) G(x,y), 其中 F(x ) 与 G(x,y) 中的 x 都是约束变元，因而不能将量词的辖域缩小。7. 演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定联结词 “ ”。演算的第二步，在原错的基础上又用错了等值式，即(F(x) (G(y) H(x,y) (F(x) G(y)H (x,y)12.公式的前束范式不 唯一，下面每题各给出一个答案。(1) xy (F(x) G(z,y);(2) xt (x,y) G(x,t,z);(3) x4 (F(,y) G(,y) (G(,y) F(x4

25、,y);(4) (F()G(,) (H () L(,);(5) (F(,)(F() G (,).13.(1)xy(F(x) G(y) H(x ,y),其中， F(x):x是汽车， G(y) ：y 是火车， H(x，y) ：x 比 y 跑 的快； (2)xy(F(x) G(y)H(x ,y),其中，F(x):x 是火车， G(y) ： y 是汽车， H(x， y) ： x 比 y 跑的快； (3)xy(F(x) G(y) H(x ,y), 其中， F(x):x是火车， G(y)：y 是汽车， H(x，y) ：x 比 y 跑的快； (4)xy(F(x) G(y) H(x ,y),其中， F(x):

26、x是飞机， G(y)：y 是 汽车， H(x，y) ：x 比 y 慢； 14.(1) 对 F(x) xG(x) 不能使用 EI 规则，它不是前束范式，首先化成前束范式。F(x) xG(x) x(F(y) G(x)因为量词辖域 (F(y) G(x) 中，除 x 外还有自由出现的y，所以不能使用EI 规则。 (2) 对 x F(x) y G(y) 也应先化成前 束范式才能消去量词，其前束范式为x y(F(x) G(y), 要消去量词，既要使用UI 规则，又要使用 EI 规则。 (3) 在自然推理系统 F 中 EG规则 为A(c)/ x(x)其中 c 为特定的个体常项， 这里 A(y) = F(y)

27、 G(y)不满足要求。 (4) 这里，使 F(a) 为真的 a不一定使 G(a) 为真，同样地使G(b)为真的 b 不一定使 F(b) 为真，如， F(x):x为奇数， G(x):x 为偶数，显然 F(3) G(4)为真，但不存在使F(x) G(x)为真的个 体。 (5) 这里 c 为个体常项，不能对F(c) G(c)引入全称量词。15.(1) 证明：xF(x) 前提引入xF(x) y(F(y)G(y) R(y) 前提引入y(F(y)G(y) R(y) 假言推理F(c) EI(F(c) G(c) R(c) UIF(c) G(c)附加R(c) 假言推理xR(x) EG(2) 证明xF(x) 前提

28、引入 x(F(x)G(a)R(x)前提引入F(c)EIF(c) G(a)R(a) UIG(a)R(c)假言推理R(c)化简F(c) R(c) 合取x(F(x) R(x)EG(3) 证明：xF(x) 前提引入xF(x) 置换F(c)UIx(F(x) G(x)前提引入F(c) G(c) UIF(c)析取三段论xF(x) EG(4) 证明 x(F(x) G(x)前提引入F(y) G(y)UIx(G(x)R(x) 前提引入G(y)R(y)UIx R(x) 前提引入R(y) UIG(y)析取三段论F（y）析取三段论 xF(x) UG17本题不能用附加前提证明法.20.(1) 与(2) 均可用附加前提证明

29、法。22.(1) 设 F(x) ：x 为偶数， G(x):x 能被 2 整除。前提:x(F(x) G (x) ，F(6)结论： G(6) (2) 设 F(x) ：x 是大学生， G(x):x 是勤奋的， a：王晓山。前提: x(F(x) G(x) ， G(a)结论： F(a) 23.(1) 设 F(x) ： x 是有理数，G(x):x 是实数， H(x) ： x 是整数。前提:x( F(x) G(x) ， x(F(x) H(x) 结论 :x(G(x) H(x)证明提示：先消存在量词。 (2) 设 F(x) ：x 是有理数，G(x):x 是无理数，H(x) ：x 是实数，I(x) ：x 是虚数。

30、前提: x(F(x)G(x) H(x) ， x( I(x)H(x)结论:x(I(x)(F(x) G(x)证明x(I(x)(H(x)前 提引入I(y) H(y)UIx(F(x)G(x) H(x)前提引入 (F(y) G(y) H(y)UIH(y)(F(y) G(y)置换 I(y) (F(y) G(y)假言三段论x(I(x)(F(x) G(x)UG24.设 F(x) ： x 喜欢步行， G(x) ： x 喜欢骑自行车，H(x)： x 喜欢乘汽车。前提:x(F(x) G(x) ， x(G(x) H (x) ，xH(x)结论:xF(x)证明xH(x) 前提引入H(c)UIx(G(x) H(x)前提引入

31、 G(c)H(c)UIG(c)析取三段论 x(F(x) G(x)前提引入F(c) G(c)UIF(c) 拒取式xF(x)UG25. 设 F(x) ：x 是科学工作者， G(x) ：x 是刻苦钻研的， H(x)：x 是聪明 的，I(x) ：x 在事业中获得成功。前提:x(F(x) G(x) ，x(G(x) H(x)I(x)， a：王大海，F(a) ，H(a)结论：I(a)证明F(a) 前提引入x(F(x) G(x)前提引入F(a) G(a)UI G(a)假言推理H(a)前提引入 x(G(x) H(x)I(x) 前提引入G(a)H(a)I(a)UIG(a)H(a) 合取I(a)假言推理 返回 第六

32、章集合代数 本章自测答案 4.(1) (2) (3) (4) (5) 6. 只有(2) 为真，其余为假。 6设 a,b,c各不相同，判断下述等式中哪个等式为真: （1） a,b ，c,= a,b ,c 假 （2） a ,b,a =a,b 真 （3） a ，b = a,b 假 （4） ， ，a,b = , ,a,b 假 8求下列集合的幂集： （1） a,b,c P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c （2） 1， 2，3 P(A)= , 1, 2,3, 1，2 ，3 （3） P(A)= , （4） ， P(A)= , 1, 2,3, 1，2 ，3 14化简下列集合表达式：

33、（1） （AB）B ）- （AB） （2） （ （ABC ）- （BC） ）A 解: (1) （AB）B ）-（AB）=（AB）B ）（AB） =（AB）（ AB）)B=B= （2） （ （ABC ）- （BC） ）A=（ （ABC）（ BC） ）A =（A（BC） ）（ （BC ）（BC ） ）A =（A（BC） ）A=（A（ BC） ）A=A 18某班有 25 个学生，其中14 人会打篮球， 12 人会打排球， 6 人会打篮球和排球，5 人会打篮球和网球，还有2 人会打这三种球。已知6 个会打网球的人 都会打篮球或排球。求不会打球的人数。 解: 阿 A=会打篮球的人 ，B=会打排球的人 ，

34、C=会打网球的人 |A|=14, |B|=12, |AB|=6,|AC|=5,| ABC|=2, |C|=6,CAB 如图所示。 25-(5+4+2+3)-5-1=25-14-5-1=5 不会打球的人共5 人 21. 设集合 A1 ，2 ，2 ，3，1 ，3, 计算下列表达式： （1）A （2）A （3）A （4）A 解: （1）A=1，22，31 ，3=1 ，2，3, （2）A=1，22，31 ，3= （3）A=123= （4）A= 27、设 A,B,C 是任意集合，证明 (1)(A-B)-C=A- B C (2)(A-B)-C=(A-C)-(B-C) 证明 (1) (A-B)-C=(AB)

35、 C= A( BC)= A(B C) =A- BC (2) (A-C)-(B-C)=(AC) (B C)= (AC) ( BC) =(ACB) (ACC)= (ACB) = A(BC) =A- BC 由（ 1）得证。 9.(1) 4；(2) 1,3,5,6；(3) 2,3,4,5,6；(4) , 1 ；(5) 4 ,1,4.11.(1)； (2) 1,4,5.22.(2) 、(3) 、(4) 、(8) 、(10) 为真，其余为假。24.(1) 为真，其余为假，因为(P-Q) = P ? (P-Q) Q = PQ ?= PQ(2)(3)(4)的反例： P =1 ，Q =226.(A B)(BA)

36、 = (A B)(BA)=(AB)(BB)(AA)(BA)=(AB)E (AB)=(AB) -(AB) 27.(1)(A-B)-C = ABC =A(BC) = A - (BC) (2)(A-C)-(B-C)AC (BC)=A C (BC) = (A C B)(AC C)=A C=(AB)- C (3)(A B-C=A BC =AC B=(AC)B28.(1)A (BA) = (A B)(AA) =(A B)=A B=B A (2)(AB)A) = (A B)A=(AB)A = A29. 由第 26 题有(A- B)(B- A)=(AB)( AB)，故 (A- B)(B -A)AB。假若xAB

37、，那么 xAB，因 此 x (AB) -(AB), 与 (A- B)(B- A) = (AB)- (AB) = AB 矛盾. 30.AB?x(x AxB) ?x(xBx A)?x(x BxA) ?BA AB ?AAAB ? EAB而ABE， 因此 AB ?AB=E反之，AB = E ? A( AB)= A ? A B = A ? AB 综合上述， AB?AB = E AB ? A-B =? A-BB反之 A-BB ? (A-B) BB ? A BB ? AB = B ? AB综合上述 AB? A-BB31. 任取 x ,x A ? x A=xP(A)=x P(B)=xB ? x B32. 先证

38、 C ACB ? CAB,任取 x,x C ? x C xC ? x AxB ? x AB,从而得到 C AB.再证 CAB ? CACB，这可以由 CABA,C ABB得到。 33.PQ ? P-Q=? P-QP，反之， P-QP ?P(P-Q)PP ? P-Q=? PQ34.令 X=，则有Y =，即 Y = . 35.AB ? AABA ? EBA因为 E为全集,BAE综合上述 BA=E. 36.由 ACBC,A-CB-C，利用 AC BD 有：(AC)(A -C) (B C)(B -C)? (A C)(AC)(BC)(BC)? (A (CC)(B(CC) ? AE BE ? AB37.恒

39、等变形法B=B (BA)=B(AB)=B(AC)=(BA)(BC)=(AC)(BC)=(AB)C=(A C)C=C 39.任取 x，有 xP(A) ? x A ? x B ? x P(B) ，因此 P(A)P(B). 40.(1) 任取 x 有xP(A)P(B) ? xP(A) xP(B) ? xAx B ? xAB ? xP(AB) (2) 任取 x有xP(A)P(B) ? xP(A)xP(B)? xAx B? xAB ? xP(AB)注 意与 (1) 的推理不同，上面的推理中有一步是“ ?” 符号，而不是“ ? ”符号。 (3) 反例如下：A = 1 ， B = 2 ，则P(A)P(B)=

40、 ,1,2 P(AB)=,1,2,1,2 返回 第七章二元关系 本章自测答案 3.(1) 任取,有 (A B) (C D) x A B y C D ? x Ax By C y D ? (x Ay C ) (x ByD) ? AC BD ? (AC)(BD) (2) 都为假 , 反例如下 : A =1, B =1,2, C =2, D =3 4.(1) 为假, 反例如下 :A =1, B =,C = 2; (2) 为真, 证明如下 : 任取 有 A(BC)(CD) ? xAByByC ? (xAyB)(x AyC) ? AB AC ? (AB)(AC) (3) 为真, 令 A = 即可; (4)

41、 为假, 反例如下 : A = 7.=, =, LA=, DA=, 9.(1), , , , (2),; (3), (4), 12.（略） 13.AB = , A B = domA = 1,2,3,domB = 1,2,4,dom(A B) = 1,2,3,4 ranA = 2,3,4,ranB = 2,3,4,ran(A B) = 4,fld(A - B) = 1,2,3 14.RR = , R= , R0,1 = , R1,2 = 2,3 16设 A=a,b,c,d ， 1 R ， 2 R为 A 上的关系，其中 1 R = ,a aa bb d 2 ,Ra db cb dc b 求 23

42、122112 ,RR RR RR。 解: R1R2=, R2R1= R1 2=R 1R1=, R2 2=R 2R2=, R2 3=R 2R2 2=, 18.(1)F(GH) = FG FH 任取 , 有 F (GH) ? t(F G H) ?t(F( G H) ?t(F G)( F H) ?t(F G)t(F H) ? FG FH? FG FH (2) 和(4) 类似可证 19.(2) 任取 y, 有 yRTW?x(x TW R) ?x(x TxW) R ?x(x A R)(xW R) ?x(x T R)x(x W R) ? yRTyRW? yRT RW (3) 任取, 有 F(AB)? xA

43、BF ? xAxB F ? (x A F)(x B F) ? FA FB ? FAF B 20.(1) 任取, 有 () ? ? ? (2) 和(1) 类似可证 . 21.只有对称性 , 因为 1+110,R,R不是自反的 , 又由于R,因此 R不是反自反的 , 根据 xRy? x+y = 10=yRx , 可知 R是对称的 , 又由于 , 都是属于 R,因此 R不是反对称的 , ,都属于 R,如果 R是传递的 , 必有属于 R.但这是不成立的 , 因此 R也不是传递的 . 22.(1) 关系图如图 7.15 所示; (P148) (2) 具有反自反性、反对称性、传递性. 26.(1)R=, = , (2)r(R)=, s(R)=, T(R)=, 31.(1)R = ,；(2)R ； (3)R. 32.(1) 不是等价关系，因为 R，R不是自反的； (2) 不是等价关系，因为R不是传递的， 1R3，3R2但是没有 1R2 ； (3) 不是等价关系，因为 R，R不是自反的； (4) 不是等价关系，因为R不是传递的。 (5) 是等价关系。 33关系图如图 7.17 说示 (P151)