离散数学课后习题答案

　　（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；

　　（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；

　　（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；

　　（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；

　　（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.

2.将下列命题符号化，并指出真值：

　　（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；

　　（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；

　　（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；

　　（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；

　　（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；

3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；

　　（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.

4.因为p与q不能同时为真.

5.设p:今天是星期一，q:明天是星期二，r:明天是星期三：

　　（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；

　　（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；

　　（3）pq，真值为1；

　　（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.

　(2)：0，矛盾式，无成真赋值；

　(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；

7.(1)：∨∨∨∨⇔∧∧；

　(2)：∨∨∨⇔∧∧∧；

8.(1)：1⇔∨∨∨,重言式；

　(2)：∨⇔∨∨∨∨∨∨；

　(3)：∧∧∧∧∧∧∧⇔0，矛盾式. 

11.(1)：∨∨⇔∧∧∧∧；

　(2)：∨∨∨∨∨∨∨⇔1；

　(3)：0⇔∧∧∧. 

12.A⇔∧∧∧∧⇔∨∨.

　　(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确

　　(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为

　　　　(p→q)∧p→q(记作*1)

　　在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.

　　可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即

　　　　(p→q)∧p→q ⇒ q

　　(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为

　　　　(p→q)∧p→q(记作*2) 

　　可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等

　　　　(p→q)∧q→p

　　⇔(┐p∨q) ∧q →p

　　⇔q →p

　　⇔┐p∨┐q

　　⇔⇔∨∨

　　从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.

9.设p:a是奇数，q:a能被2整除，r:a：是偶数

　　推理的形式结构为 

　　　　(p→q┐)∧(r→q)→(r→┐p) (记为*)

　　可以用多种方法证明*为重言式，下面用等值演算法证明：

　　　　(p→┐q)∧(r→q)→(r→┐p)

　　⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) 　　(使用了交换律)

　　⇔(p∨q)∨(┐p∧r)∨┐q∨┐r

　　⇔(┐p∨q)∨(┐q∧┐r)

　　⇔┐p∨(q∨┐q)∧┐r

　　⇔1

10.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.

　　推理的形式结构为

　　　　(p→q)∧┐p→(┐q∧┐r)

　　⇔(┐p∨q) ∧┐p→(┐q∧┐r)

　　⇔┐p→(┐q∧┐r) 　　(使用了吸收律)

　　⇔p∨(┐q∧┐r)

　　⇔∨∨∨

　　由于主析取范式中只含有5个W极小项，故推理不正确.

11.略

14.证明的命题序列可不惟一，下面对每一小题各给出一个证明

　　① p→(q→r)　　　　　前提引入

　　② P　　　　　　　　　前提引入

　　③ q→r　　　　　　　 ①②假言推理

　　④ q　　　　　　　　　前提引入

　　⑤ r　　　　　 　　　 ③④假言推理

　　⑥ r∨s　　　　　　　 前提引入

　（2）证明：

　　① ┐(p∧r)　　　　　 前提引入

　　② ┐q∨┐r　　　　　 ①置换

　　③ r　　　　　　　　　前提引入

　　④ ┐q 　　　　　　　 ②③析取三段论

　　⑤ p→q　　　　　　　 前提引入

　　⑥ ┐p　　　　　　　　④⑤拒取式

　（3）证明：

　　① p→q　　　　　　　 前提引入

　　② ┐q∨q　　　　　　 ①置换

　　③ (┐p∨q)∧(┐p∨p) ②置换

　　④ ┐p∨(q∧p　　　　 ③置换

　　⑤ p→(p∨q) 　　　　 ④置换

15.(1)证明：

　　① S　　　　　　　　结论否定引入

　　② S→P　　　　　　 前提引入

　　③ P　　　　　　　　①②假言推理

　　④ P→(q→r)　　　　前提引入

　　⑤ q→r　　　　　　 ③④假言推论

　　⑥ q　　　　　　　　前提引入

　　⑦ r　　　　　　　　⑤⑥假言推理

　（2）证明：

　　① p　　　　　　　　附加前提引入

　　② p∨q　　　　　　 ①附加

　　③ (p∨q)→(r∧s)　前提引入

　　④ r∧s　　　　　　 ②③假言推理

　　⑤ s　　　　　　　　④化简

　　⑥ s∨t　　　　　　 ⑤附加

　　⑦ (s∨t)→u　　　　前提引入

　　⑧ u　　　　　　　　⑥⑦拒取式

16.(1)证明：

　　① p　　　　　　　　结论否定引入

　　② p→ ┐q　　　　　前提引入

　　③ ┐q ①②　　　　 假言推理

　　④ ┐r∨q　　　　　 前提引入

　　⑤ ┐r　　　　　　　③④析取三段论

　　⑥ r∧┐s　　　　　 前提引入

　　⑦ r　　　　　　　　⑥化简

　　⑧ ┐r∧r　　　　　 ⑤⑦合取

　（2）证明：

　　① ┐(r∨s)　　　　 结论否定引入

　　② ┐r∨┐s　　　　 ①置换

　　③ ┐r　　　　　　　②化简

　　④ ┐s　　　　　　　②化简

　　⑤ p→r　　　　　　 前提引入

　　⑥ ┐p　　　　　　　③⑤拒取式

　　⑦ q→s　　　　　　 前提引入

　　⑧ ┐q　　　　　　　④⑦拒取式

　　⑨ ┐p∧┐q　　　　 ⑥⑧合取

　　⑩ ┐(p∨q)　　　　 ⑨置换

　　口 p∨q　　　　　　 前提引入

　　⑾①口 ┐(p∨q) ∧(p∨q) ⑩口合取

17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。

　　前提：(p∧┐q) →r , p ,q →s , ┐s

　　结论：r

　　证明：

　　　　① q→s 前提引入

　　　　② ┐s 前提引入

　　　　③ ┐q ①②拒取式

　　　　④ p 前提引入

　　　　⑤ p∧┐q ③④合取

　　　　⑥（p∧┐q）→r 前提引入

　　　　⑦ r ⑤⑥假言推理

18．（1）设 p：今天是星期六，q：我们要到颐和园玩，s：颐和园游人太多。

　　前提：p→(p∨r) , s→┐q , p , s

　　结论：r

　　证明：

　　　　① s→┐q　　　 前提引入

　　　　② s　　　　　　前提引入

　　　　③ ┐q　　　　　①②假言推理

　　　　④ p　　　　　　前提引入

　　　　⑤ p→(q∨r)　　前提引入

　　　　⑥ q∨r　　　　 ④⑤假言推理

　　　　⑦r　　　　　　 ③⑥析取三段论

（2）设p:小王是理科学生，q：小王数学成绩好，r：小王是文科学生。

　　前提：p→q ,┐r→p ,┐q

　　结论：r

　　证明：

　　　　① p→q　　　　 前提引入

　　　　② ┐q　　　　　前提引入

　　　　③ ┐p　　　　　①②拒取式

　　　　④ ┐r→p　　　 前提引入

　　　　⑤ r　　　　　　③④拒取式

　(2)┐x( F (x) →G (x) ) ⇔x(F(x)∧ ┐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)：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 + y ＜0 )

9.(1)对任意数的实数x和y,若x ＜y,则x ≠ y；

　(2)对任意数的实数x和y,若x–y = 0,则x＜y；

　(3)对任意数的实数x和y,若x＜y,则x–y≠0；

　(4)对任意数的实数x和y,若x–y ＜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)为真,而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)为真,由于有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)中公式就为假了,所以它为可满足式。

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．提示：对每个公式分别找个成真的解释，一个成假的解释。

　(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 ,4))

　　⇔1∧1⇔1

6.乙说得对，甲错了。本题中，全称量词 的指导变元为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,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):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) →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) 　　　　　　　　 ③UI

　　⑥F(c)∨G(c)　　　　　　　　　　　　 　④附加

　　⑦R(c)　　　　　　　　　　　　　　　　 ⑤⑥假言推理

　　⑧xR(x)　　　　　　　　　　　　　　 　⑦EG

(2)证明①xF(x)　　　　　　　　　　　　　 前提引入

　　②x((F(x)→G(a)∧R(x)))　　　　 　　前提引入

　　③F(c)　　　　　　　　　　　　　　　　 ①EI

　　④F(c)→G(a)∧R(a)　　　　　　　　　 　②UI

　　⑤G(a)∧R(c)　　　　　　　　　　　　 　③④假言推理

　　⑥R(c)　　　　　　　　　　　　　　　　 ⑤化简

　　⑦F(c)∧R(c)　　　　　　　　　　　　　 ③⑥合取

　　⑧x(F(x)∧R(x))　　　　　　　　　　　⑦EG

(3)证明：①┐xF(x)　　　　　　　　　　　 前提引入

　　②x┐F(x)　　　　　　　　　　　　　　①置换

　　③┐F(c)　　　　　　　　　　　　　　　 ②UI

　　④x(F(x)∨G(x))　　　　　　　　　　 前提引入

　　⑤F(c)∨G(c)　　　　　　　　　　　　　 ④UI

　　⑥F(c)　　　　　　　　　　　　　　　　 ③⑤析取三段论

　　⑦xF(x)　　　　　　　　　　　　　　　⑥EG

(4)证明①x(F(x)∨G(x))　　　　　　　　　前提引入

　　②F(y)∨G(y)　　　　　　　　　　　　　 ①UI

　　③x(┐G(x)∨┐R(x))　　　　　　　　 前提引入

　　④┐G(y)┐R(y)　　　　　　　　　　　　 ③UI

　　⑤x R(x)　　　　　　　　　　　　　　 前提引入

　　⑥R(y)　　　　　　　　　　　　　　　　 ⑤UI

　　⑦┐G(y)　　　　　　　　　　　　　　　 ④⑥析取三段论

　　⑧F（y）　　　　　　　　　　　　　　　 ②⑦析取三段论

　　⑨xF(x)　　　　　　　　　　　　　　 ⑧UG

17．本题不能用附加前提证明法.

20.(1)与(2)均可用附加前提证明法。

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是虚数。

　　前提: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)　　　　　　　　　　　　　　 ①UI

　　　　③x((F(x)∨G(x))→H(x))　　　　　　　 前提引入

　　　　④(F(y)∨G(y))→H(y)　　　　　　　　　　③UI

　　　　⑤┐H(y)→(┐F(y)∧┐G(y))　　　　　　　④置换

　　　　⑥I(y)→(┐F(y)∧┐G(y))　　　　　　　　②⑤假言三段论

　　　　⑦x(I(x)→(┐F(x)∧┐G(x))　　　　　　⑧UG

24.设F(x)：x喜欢步行，G(x)：x喜欢骑自行车，H(x)：x喜欢乘汽车。

　　前提:x(┐F(x)→┐G(x))， x(G(x)∨H(x))， x┐H(x)

　　结论:x┐F(x)

　　证明①x┐H(x)　　　　　　　　　　　　　　　 前提引入

　　　　②┐H(c)　　　　　　　　　　　　　　　　　①UI

　　　　③x(G(x)∨H(x))　　　　　　　　　　　　前提引入

　　　　④G(c)∨H(c)　　　　　　　　　　　　　　　③UI

　　　　⑤G(c)　　　　　　　　　　　　　　　　　　②④析取三段论

　　　　⑥x(F(x) →G(x))　　　　　　　　　　　 前提引入

　　　　⑦F(c)→┐G(c)　　　　　　　　　　　　　　⑥UI

　　　　⑧┐F(c)　　　　　　　　　　　　　　　　　⑤⑦拒取式

　　　　⑨x┐F(x)　　　　　　　　　　　　　　　 ⑧UG

25.设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)　　　　　　　　　　　 ⑥UI

　　　　⑧G(a)∧H(a)　　　　　　　　　　　　　　　④⑤合取

　　　　⑨I(a)　　　　　　　　　　　　　　　　　　⑦⑧假言推理

6.只有(2)为真，其余为假。

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 = P∩Q ⇒ = P∩Q

　　(2)(3)(4)的反例：P ={1} ，Q ={2}

26.(A–B)∪(B–A) = (A∩B)∪(B∩A)

　　=(A∪B)∩(B∪B)∩(A∪A)∩(B∪A)

　　=(A∪B)∩E∩(A∩B)=(A∪B)-(A∩B)

27.(1)(A-B)-C = A∩B∩C =A∩(B∪C) = A-(B∪C) 

　 (2)(A-C)-(B-C)A∩C∩(B∩C)

　　　 =A∩C∩(B∪C) = (A∩C∩B)∪(A∩C∩C)

　　　 =A∩∩C=(A–B)- C

　 (3)(A–B-C=A∩B∩C =A∩C∩B=(A–C)–B

28.(1)A∩(B∪A) = (A∩B)∪(A∩A) =(A∩B)∪

　　　 =A∩B=B∩A

　 (2)((A∪B)∩A) = (A∪B)∪A

　　　 =(A∩B)∪A = A

29.由第26题有(A-B)∪(B-A)=(A∪B)–(A∩B)，故(A-B)∪(B-A)A∪B。假若x∈A∩B，那么x∈A∪B，因此x(A∪B)-(A∩B),与(A-B)∪(B-A) = (A∪B)-(A∩B) = A∪B矛盾.

30.AB⇔x(x∈A→x∈B)⇔x(xB→xA)

　　　 ⇔x(x∈B→x∈A)⇔BA

　　　 AB ⇒ A∪AA∪B ⇒ EA∪B

　　而A∪BE，因此AB ⇒ A∪B=E反之，

　　　 A∪B = E ⇒ A∩(A∪B)= A ⇒ A∩B = A ⇒ AB 

　　综合上述，AB⇔A∪B = E

　　　 AB ⇒ A-B = ⇒ A-BB

　　反之A-BB ⇒ (A-B)∪BB ⇒ A∪BB ⇒ A∪B = B ⇒ AB

　　综合上述AB⇔A-BB

31.任取x ,x∈A ⇒ {x} A=>{x}∈P(A)=>{x}∈P(B)=>{x}B ⇒ x∈B

32.先证CA∧CB ⇒ CA∩B,任取x,x∈C ⇒ x∈C∧x∈C ⇒ x∈A∧x∈B ⇒ x∈A∪B,从而得到CA∪B.再证CA∩B ⇒ CA∧CB，这可以由CA∩BA,CA∩BB得到。

33.PQ ⇒ P-Q= ⇒ P-QP，反之，P-QP ⇒ P∩(P-Q)P∩P ⇒ P-Q= ⇒ PQ

34.令X=，则有∪Y =，即Y = .

35.AB ⇒ A∪AB∪A ⇒ EB∪A因为E为全集,B∪AE综合上述B∪A=E.

36.由A∩CB∩C,A-CB-C，利用A∪CB∪D有：

　 (A∩C)∪(A-C) (B∩C)∪(B-C)

　 ⇒ (A∩C)∪(A∩C)(B∩C)∪(B∩C)

　 ⇒ (A∩(C∪C)(B∩(C∪C) ⇒ A∩EB∩E ⇒ AB

37.恒等变形法

　　B=B∩(B∪A)=B∩(AB)=B∩(AC)

　　 =(B∩A)∪(B∩C)=(A∩C)∪(B∩C)

　　 =(A∪B)∩C=(A∪C)∩C=C

39.任取x，有x∈P(A) ⇒ x A ⇒ x B ⇒ x∈P(B)，因此P(A)P(B).

40.(1)任取x有

　　x∈P(A)∩P(B)⇔x∈P(A)∧x∈P(B)⇔xA∧xB

　　　　　　　　　⇔xA∩B⇔x∈P(A∩B)

(2)任取x有

　　x∈P(A)∪P(B)⇔x∈P(A)∨x∈P(B)⇔xA∧xB

　　　　　　　　　 ⇒ xA∪B⇔x∈P(A∪B)

　　注意与(1)的推理不同，上面的推理中有一步是“ ⇒ ”符号，而不是“⇔”符号。

(3)反例如下：A = {1}，B = {2}，则

　　P(A)∪P(B)= {,{1},{2}}

　　P(A∪B)={,{1},{2},{1,2}}

　　∈(A ∩ B)×(C ∩ D) <=>x∈A ∩ B ∧ y ∈C ∩ D

　⇔x ∈A∧x ∈ B∧y ∈C∧y ∈ D

　⇔(x ∈A∧y ∈C )∧(x∈B∧y∈D)

　⇔∈A×C∧< x,y >∈B×D

　⇔∈(A×C)∩(B×D)

　(2)都为假,反例如下:

　　A ={1}, B ={1,2}, C ={2}, D ={3}

4.(1)为假,反例如下:A ={1}, B =,C = {2};

　(2)为真,证明如下:任取有

　　∈A×(B∩C)×(C∩D)⇔x∈A∩B∧y∈B∧y∈C

　⇔(x∈A∧y∈B)∧(x∈A∧y∈C)

　⇔∈A×B∧∈A×C⇔∈(A×B)∩(A×C)

　(3)为真,令A = 即可;

　(4)为假,反例如下: A = 

7.={<2,2>,<3,3 >,<4,4>}

　={<2 . 3>,<2,4>,<3,2>,<3,4>,<4,2>,<4,3>}∪IA

　LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}

　DA={<2,2>,<2,4>,<3,3>,<4,4>}

9.(1){<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4> <2,6>,<4,1>,<4,2>,<4,4>, <4,6> <6,1>, <6,2>,<6,4> <6,6>}

　(2){<1,2>,<2,1>};

　(3){<1,1>,<2,1>,<4,1>,<6,1>,<2,2>,<4,2>,<4,4>,<6,6>}

　(4){<1,2>,<2,2>,<4,2>,<6,2>}

12.（略）

13.A∩B = {<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}, A ∩ B ={<2,4>}

　　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 = {<0,2>,<0,3>,<1,3>}

　 R= {<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}

　 R{0,1} = {<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}

　 R[{1,2}] = {2,3}

18.(1)F(G∪H) = FG∪FH

　　任取 ,有

　　　　∈F (G∪H)⇔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,有

　　y∈R[T∪W]⇔x(x∈T∪W∧∈R)

　　　⇔x((x∈T∨x∈W)∧∈R

　　　⇔x((x∈A∧∈R)∨(x∈W∧∈R))

　　　⇔x(x∈T∧∈R)∨x(x∈W∧∈R)

　　　⇔y∈R[T]∨y∈R[W]⇔y∈R[T]∩R[W]

(3)任取,有

　　∈F(A∩B)⇔x∈A∩B∈F

　　　⇔x∈A∧x∈B∧∈F

　　　⇔(x∈A∧∈F)(x∈B∧∈F)

　　　⇔∈FA∧∈FB

　　　⇔∈FA∩F B

20.(1)任取,有

　　∈(∪) <=>∈∪

　　　⇔∈∨∈ 

　　　⇔∈∨∈ 

　　　⇔∈∪ 

　 (2)和(1)类似可证.

21.只有对称性,因为1+1≠10,<1,1>R,R不是自反的,又由于<5,5>∈R,因此R不是反自反的,根据xRy⇔x+y = 10=>yRx ,可知R是对称的,又由于<1,9>,<9,1>都是属于R,因此R不是反对称的, <1,9>,<9,1>都属于R,如果R是传递的,必有<1,1>属于R.但这是不成立的,因此R也不是传递的.

22.(1)关系图如图7.15所示; (P148)

　 (2)具有反自反性、反对称性、传递性.

26.(1)R={<3,3>,<3,1>,<3,5>}, = {<3,3>,<3,1>,<3,5>}

　 (2)r(R)={<1,1>,<1,5>,<2,2>,<2,5>,<3,3>,<3,1>,<4,4>,<4,5>,<5,5>,<6,6>}

　　　s(R)={<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4>}

　　　T(R)={<1,5>,<2,5>,<3,3>,<3,1>,<3,5>,<4,5>}

31.(1)R = {<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}∪；(2)R； (3)R.

32.(1)不是等价关系，因为<1,1> R，R不是自反的；

　 (2)不是等价关系，因为R不是传递的，1R3，3R2但是没有1R2；

　 (3)不是等价关系，因为<2,2> R，R不是自反的；

　 (4)不是等价关系，因为R不是传递的。

　 (5)是等价关系。

33．关系图如图7.17说示 (P151)

　 [a] = [b] ={a,b},[c] = [d] = {c,d}

38.现取x，有x∈A ⇒ ∈R ⇒ ∈R∧∈R

　　 ⇒ ∈R∧∈ ⇒ ∈R∩R 

　 任取,有∈ R∩ ⇒ ∈R∧∈ 

　　 ⇒ ∈ ∧∈R ⇒ ∈R∩R 

　 任取,,有

　　　 ∈R∩ ∧∈R∩ 

　　 ⇒ ∈R∧∈ ∧∈R∧∈ 

　　 ⇒ (∈R∧∈R)∧(∈ ∧∈ 

　　 ⇒ ∈R∧∈R ⇒ ∈R∩R 

42.x,x∈A ⇒ ∈R ⇒ ∈R∧∈R ⇒ ∈T,T是自反的。

　　　 x,y∈A,∈T⇔∈R∧∈R

　 ⇔∈R∧∈R ⇒ ∈T,T是对称的。

　　　 x,y,z∈A,∈T∧∈T

　 ⇔∈R∧∈R∧∈R∧∈R

　 ⇒ ∈R∧∈R∧∈R∧∈R

　 ⇒ ∈R∧∈R ⇒ ∈T

　 T是传递的。

43．哈斯图如下图所示.

44.(a)偏序集,A={1,2,3,4,5},R={<1,3>,<1,5>,<2,4>,<2,5>,<3,5>,<4,5>}∪ 

　 (b)偏序集,A={a,b,c,d,e,f},R={,,}∪ 

　 (c)偏序集,A={1,2,3,4,5}, R={<1,2>,<1,4>,<1,5>,<1,3>,<2,4>,<2,5>,<3,4>,<3,5>,<4,5>}∪

45.(a)A={a,b,c,d,e,f,g}, ={,,,,,,, ,,}∪ 　 (b)A = {a,b,c,d,e,f,g},R口 = {,,,,,,}∪ 

46.哈斯图如图7.19所示 （P153）

　（1）极大元e,f；极小元a,f；没有最大与最小元。

　（2）极大元a,b,d,e；极小元a,b,c,e；没有最大与最小元。

　= {<1,a>,<2,a>}, = {<1,a>,<2,b>}, = {<1,a>,<2,c>}

　= {<1,b>,<2,a>}, = {<1,b>,<2,b>}, = {<1,b>,<2,c>}

　= {<1,c>,<2,a>}, = {<1,c>,<2,b>}, = {<1,c>,<2,c>}

3.(1)双射，反函数=,f({8}=|8|),({4}={4}；

　(2)双射，反函数：R→ R，（x）= logx, ({1}) = {2}, ({1,2}) ={0,1}；

　(3)单射，({5}) = {<5,6>}, ({2,3}) = {2}；

　(4)单射，({2,3}) = {5,7}, ({1,3}) = {0,1}；

　(5)单射，({-1,2}) = {1,2}, ({1}) = {-1,1}； 

　(6)单射，((0,1)) = (1/4,3/4),([1/4,1/2]) = [0,1/2]；

　(8)单射，((0,1)) = (1,+∞),({2,3}) = {1/2,1/3}.

4.(1) 单射 (2) 不单射,也不满射 (3) 不单射,也不满射 (4) 满射 (5) 单射 (6) 不单射，也不满射.

5.(1) 为真，其余都为假.

7.(1) 结果不唯一，={,,,};

　(2) 结果不唯一，={,,,}

　(3) 不能

　(4) 存在单射还书的充要条件是m ≤ n ，存在满射函数的充要条件是m ≥ n,

存在双射函数的充要条件是m = n .

9.双射函数与单射函数都是n!个

10.(1)不是单射，不是满射，也不是双射；

　 (2){<1,1>,<0,2>,<2,0>};

　 (3){3,5,7}

17.fg(x)=2x +7, bf(x) =2x +4, ff(x) =x +6, gg(x) =4x +3,

　 hf(x)=x/2 +3, gh(x) = x +1/2, fh(x) =(x +5)/2 gh f(x) =x +7/2

18.ff(n) =n+2, gf(n)=2n+1, fg(n)=2n+2, gh(n) =0

　　hg(n)=, hgf(n)=.

19.(1)gf(x)=x+8x +14, fg(x)=x+2

　 (2)都不是单射，也不是满射和双射。

　 (3)g和h有反函数，g:R→R,g(x) = x–4; h:R→R,h(x)=

20．

　 (1)fg:N→N, fg(x)

　 (2)不是单射，不是满射，也不是双射。

21.(1)单射，假设f() = f()，那么<,+1> = <,+1>。根据有序对相等的条件得=，因此f是单射的，但是f不是满射的，因为<0,0>ran 

　 (2)不存在反函数

　 (3)ran={｜n∈N}

24.这些函数都是不唯一的，以下只是一个可能的结果。

　 (1)f = {<1,a>,<2,b>,<3,c>}

　 (2)f(x) = 2x

　 (3)f(x) = ｜x｜ - 1

　 (4)f(x) = e 

　(2)不可以.

4.(1)封闭 (2)不封闭 (4)加法不封闭，乘法封闭 (5)不封闭 (7)封闭 (9)加法不封闭，乘法封闭

5.(1)没有交换律、结合律，对于一个运算不能考虑分配律；

　(3)加法满足交换律、结合律，乘法满足结合律，乘法对加法满足分配律；

　(4)乘法满足结合律

　(6)加法和乘法都满足交换律、结合律，乘法对加法满足分配律；

　(7)满足结合律；

　(8)乘法满足交换律、结合律；

　(9)乘法满足交换律、结合律；

　(10)乘法满足交换律、结合律。

6.(1)没有单位元、零元，没有可逆元素。

　(3)n阶全0矩阵是加法单位元，也是乘法的零元；n阶单位矩阵是乘法单位元；加法没有零元。任意n阶矩阵M对于加法都是可逆元，起逆元为 – M；只有n阶可逆矩阵(行列式不为0)对乘法是可逆元，其逆元为M .

　(4) 乘法单元为n阶单位矩阵，没有零元。每个矩阵M都有逆元M . 

　(6) 加法单位元0，没有零元，每个元素x都可逆，其逆元是它的相反数 – x 。

　　　当n = 1时，乘法有单位元1，只有两个可逆元素：1 = 1, ( - 1) = - 1.

　　　当n＞1时乘法没有单位元和可逆元素。

　(7)没有单位元和零元，也没有可逆元素。

　(8)乘法单位元为1，只有1是可逆元素，1 = 1

　(9)乘法单位元为1，只有1是可逆元素，1 = 1

　(10)乘法没有单位元、零元以及可逆元素。

8.(1)不可交换。反例：<0,1> * <1,2> = <0,1>,<1,2> * <0,1> = <0,3>.

可结合，因为 ,,∈Q × Q

( * ) *  =  * 

= 

 * ( * ) =  * 

= 

不是幂等的，因为<1,1> * <1,1> = <1,2>

(2) 容易严整<1,0>为单位元，没有零元，当 a≠0 时，的逆元为<1/ a,- b/a>

11.(1)能构成代数系统。满足交换律、结合律、无单位元，零元是1；

　 (3)能构成代数系统。满足交换律、结合律，单位元是10，零元是1。 

15.(1)能 (2)不能 (3)不能 (4)能

　(3)构成半群，不构成独异点，也不构成群；

　(4)构成半群、独异点和群

5.(1)假设a*b ≠ b*a，那么或者a*b = a , a = b ；或者a*b = b , b*a = a。若为前者，则

　　　　(a*b)*a = a*a = b , a*(b*a) = a*b = a

　　与结合律矛盾，若为后者，有

　　　　(a*b)* a = b*a = a ; a*(b*a) = a*a = b

　　也与结合律矛盾。

(2) 假设b*b = a ，那么或者a*b = b*a = a，或者a*b = b*a = b 。若为前者，则

　　　　(b*a)*a = a*a = b ; b*(a*a) = b*b = a

　　与结合律矛盾，若为后者，有

　　　　(b*a)*a = b*a = b ; b*(a*a) = b*b = a

　　也与结合律矛盾。

7.任取a + bi , c + di∈G , 有

　　　(a + bi)+(c + di)=(a + c)+(b + d)i∈G

　任取a + bi , c + di , e + i ∈G ,有

　((a + bi)+(c + di))+(e + i)=(a + c)+(b + d)i +(r + i)

　　　　　　　　　　　　　　　 = (a + c + e) + (b + d + ) i

同理

　　　(a + bi)+((c + di)+(e + i))=(a + c + e) + (b + d + ) i

　　单位元是0，a + bi的逆元是 – a – bi .

9. 能构成群，运算封闭。 x , y , z ∈A , 有

　　(xy)z = (x + y - 2) z = (x + y - 2) + z – 2 = x + y + z – 4

　　x(yz) = xо(y + z - 2) = x + (y + z - 2) – 2 = x + y + z – 4

结合律成立，单位元是2，x的逆元是4 – x。

11．设矩阵A=, B=， C=， D=，

那么运算表如表11.7所列

B

C

D 

　　　　B　　　　A　　　　D　　　　C　

　　　　C　　　　D　　　　A　　　　B

　　　　D　　　　C　　　　B　　　　A　 

　 (2)子群为={e},=G,={e,a,a,a,a},={e,a,a},

36.(1)στ=，τσ=，σ=，τ=，στσ=

(2)στ= (1 4 2 3 )，τ = (1 4 2 5 3 )， στσ = (1 5 2 4 3 )

(3)στ = (1 4)(1 2)(1 3)奇置换

　　τ = (14)(12)(15)(13)偶置换

　　στσ = (15)(12)(14)(13) 偶置换

（2）不是环，因为关于加法不封闭；

（3）是环，不是整环和域，因为乘法没有么元；

（4）不是环，因为正整数关于加法的负元不存在，关于加法不构成群；

（5）不是环，因为关于乘法不封闭。

6.(1) ( - a )( - a) = - - (a a) = 1 , ( - a)( - a ) = - - ( a a ) = 1 

因此 - a 是( - a)的逆元，根据逆元的唯一性得( - a) = - a 

(2) (b a )(a b) = b (a a) b = 1 , (ab) (b a ) = a (b b ) a = 1

因此b a 是ab的逆元，根据逆元唯一性有(a b) = b a .