离散数学课后习题答案

1.3.1习题1.1解答

1设S={2，a，{3}，4}，R={{a}，3，4，1}，指出下面的写法哪些是对的，哪些是错

的？

{a}S,{a}R,{a,4,{3}}S,{{a},1,3,4}R,R=S,{a}S,{a}R,R,{{a}}RE,{}S,R,

{{3},4}。

解：{a}S，{a}R，{a，4，{3}}S，{{a}，1，3，4}R，R=S，{a}

S，{a}R，R，{{a}}RE，{}S，R，{{3}，4}

2写出下面集合的幂集合

{a，{b}}，{1，}，{X，Y，Z}

解：设A={a，{b}}，则(A)={，{a}，{{b}}，{a，{b}}}；

设B={1，}，则(B)={，{1}，{}，{1，}}；

设C={X，Y，Z}，则(C)={，{X}，{Y}，{Z}，{X，Y}，{X，Z}，{Y，Z}，{X，Y，

Z}}；

3对任意集合A，B，证明：

(1)AB当且仅当(A)(B)；

(2)(A)(B)(AB)；

(3)(A)(B)=(AB)；

(4)(A-B)((A)-(B)){}。

举例说明：(A)∪(B)≠(A∪B)

证明：(1)证明：必要性，任取x(A)，则xA。由于AB，故xB，从而x(B)，

于是(A)(B)。

充分性，任取xA，知{x}A，于是有{x}(A)。由于(A)(B)，故{x}(B)，由此

知xB，也就是AB。

（2）证明：

任取X(A)∪(B)，则X(A)或X(B)

∴XA或XB

∴X(A∪B)

∴X(A∪B)

所以(A)∪(B)(A∪B)

（3）证明：

先证(A)∩(B)(A∩B)

任取X(A)∩(B)，则X(A)且X(B)

∴XA且XB

∴XA∩B

∴X(A∩B)

所以(A)∩(B)(A∩B)

再证(A∩B)(A)∩(B)

任取Y(A∩B)，则YA∩B

∴YA且YB

∴Y(A)且Y(B)

∴Y(A)∩(B)

所以(A∩B)(A)∩(B)

故(A)∩(B)=(A∩B)得证。

举例：A={1}，B={a}

则(A)={，{1}}，(B)={，{a}}

(A)∪(B)={，{1}，{a}}

A∪B={1，a}

(A∪B)={，{1}，{a}，{1，a}}

可见{1，a}(A∪B)，{1，a}(A)∪(B)

所以(A)∪(B)≠(A∪B)

(4)对任意的集合x，若x=，则x(A-B)且x((A)-(B))∪{}。若x，则x(A-B)

当且仅当x(A-B)当且仅当xAx⊈B当且仅当x(A)x(B)当且仅当

x((A)-(B))。综上所述，可知(A-B)((A)-(B)){}。

4.设A,B,C为任意三个集合，下列各式对否？并证明你的结论。

（1）若AB且BC，则AC；

（2）若AB且BC，则AC；

（3）若AB且BC，则AC；

（4）若AB且BC，则AC。

解：（1）正确；（2）不正确，举一个反例即可；（3）不正确，举一个反例即可；（4）不

正确，举一个反例即可。

1.3.1习题1.2解答

3.R，S是集合A上的两个关系。试证明下列等式：

（1）(R•S)-1=S-1•R-1

（2）(R-1)-1=R

（3）(R∪S)-1=R-1∪S-1

（4）(R∩S)-1=R-1∩S-1

证明：

（1）先证(R•S)-1S-1•R-1，对任意(x，y)(R•S)-1，则(y，x)(R•S)，则存在aA，满

足(y，a)R且(a，x)S，那么(x，a)S-1且(a，y)R-1，所以(x，y)S-1•R-1，因此(R•S)-1

S-1•R-1；再证S-1•R-1(R•S)-1，对任意(x，y)S-1•R-1，则存在aA，满足(x，a)S-1且(a，

y)R-1，所以(y，a)R且(a，x)S，所以(y，x)(R•S)，所以(x，y)(R•S)-1，因此S-1•R-1

(R•S)-1。

（2）先证(R-1)-1R，对任意(x，y)(R-1)-1，则(y，x)R-1，则(x，y)R，所以(R-1)-1

R；再证R(R-1)-1，对任意(x，y)R，则(y，x)R-1，则(x，y)(R-1)-1，所以R(R-1)-1。

故(R-1)-1=R得证。

（3）先证(R∪S)-1R-1∪S-1，对任意(x，y)(R∪S)-1，则(y，x)R∪S，则(y，x)R

或(y，x)S，则(x，y)R-1或者(x，y)S-1，所以(x，y)R-1∪S-1，所以(R∪S)-1R-1∪S-1；

再证R-1∪S-1(R∪S)-1，对任意(x，y)R-1∪S-1，则(x，y)R-1或者(x，y)S-1，则(y，x)

R或(y，x)S，所以(y，x)R∪S，所以(x，y)(R∪S)-1，所以R-1∪S-1(R∪S)-1。故(R

∪S)-1=R-1∪S-1得证。

（4）先证(R∩S)-1R-1∩S-1，对任意(x，y)(R∩S)-1，则(y，x)R∩S，则(y，x)R

且(y，x)S，则(x，y)R-1且(x，y)S-1，所以(x，y)R-1∩S-1，所以(R∩S)-1R-1∩S-1；

再证R-1∩S-1(R∩S)-1，对任意(x，y)R-1∩S-1，则(x，y)R-1且(x，y)S-1，则(y，x)R

且(y，x)S，所以(y，x)R∩S，所以(x，y)(R∩S)-1，所以R-1∩S-1(R∩S)-1。故(R∩S)-1=

R-1∩S-1得证。

1.3.3习题1.3解答

2.将集合M中元素映射到自身的变换称为同一变换，记为I。设，是集合M上的两

个变换，如果•=•=I，则，是1–1变换，并且=-1。

证明：（1）先证、分别是单映射。

对任意x

1

，x

2

M，如果(x

1

)=(x

2

)，则有

x

1

=I(x

1

)=(•)(x

1

)=((x

1

))=((x

2

))=(•)(x

2

)=I(x

2

)=x

2

所以是单映射。

同理可证是单映射。

（2）再证、分别是满射。

因为和都是M到M的单映射，所以有(M)M，(M)M，于是

M=I(M)=(•)(M)=((M))(M)，

同理A=I(M)=(•)(M)=((M))(M)，

所以(M)=M，(M)=M，即、是满射。

（3）往证=-1。

由是1–1映射，故存在-1，对任意xM，

-1(x)=I(-1(x))=(•)(-1(x))=((-1(x))=(x)

故=-1。

习题2.1解答

2.说出下述每一命题的逆命题和逆否命题：

（1）如果天下雨，我将不去。

（2）仅当你去我将逗留。

（3）如果n是大于2的正整数，则方程xn+yn=zn无正整数解。

（4）如果我不获得更多帮助，我不能完成这个任务。

解：（1）逆命题为：如果我不去，那么天下雨；逆否命题为：如果我去，那么天不下

雨。

（2）逆命题为：仅当我将逗留你去；逆否命题为：你不去我将不逗留。

（3）逆命题为：如果方程xn+yn=zn无正整数解，则n是大于2的正整数；逆否命题为：如

果方程xn+yn=zn有正整数解，则n是不大于2的正整数。

(4)逆命题为：我不能完成这个任务，因为我没有获得更多帮助。逆否命题：如果我完成了

任务，则我获得了更多帮助。

3.给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值：

a)(P(QR))((PQ)(RS))

b)((PQ)R)(((PQ)R)S)

c)((PQ)R)((QP)(RS))

d)(P(Q(RP)))(QS)

解：

a)令G=(P(QR))((PQ)(RS))

则：T

I

(G)=(1(10))((11)(00))

=00=1

b)令G=((PQ)R)(((PQ)R)S)

则：T

I

(G)=((11)0)(((11)0)0)

=10=1

c)令G=((PQ)R)((QP)(RS))

=((PQ)R)(((QP)(PQ))(RS))

=(PQR)((QP)(PQ)(RS))

则：

T

I

(G)=(110)((11)(11)(00))=11=1

d)令G=(P(Q(RP)))(QS)

=(P(Q(RP)))(QS)

=(P(Q(RP)))(QS)

=((P(Q(RP)))(QS))((QS)(P(Q(RP))))

=(P(Q(RP)))(QS))((QS)(P(Q(RP))))

T

I

(G)=(1(1(01)))(10))((10)

(1(1(01))))

=11=1

习题2.2解答

3.对P和Q的所有值，证明PQ与PQ有同样的真值。证明（PQ）（PQ）

是恒真的。

解：对PQ的任意解释I，若I使PQ为真，则I使P为假或P和Q同时为真，若

I使P为假，则使P，此时PQ为真，若I使P和Q同时为真，则Q为真，此时PQ为

真，也就是说PQ为真时PQ为真。若I使PQ为假，则I使P为真Q为假，此时PQ

为假，也就是说PQ为假时PQ为假。综上知PQ与PQ同真同假，由定义知（P

Q）（PQ）是恒真的。

习题2.3解答

2设S={G

1

，…，G

n

}是命题公式集合。试求出在不增加新原子的情况下从S出发演绎

出的所有命题公式。

提示：考虑G

1

…G

n

的主合取范式。

解：任设一公式G’为从S出发演绎出来的公式。则可知G’

为G=G

1

…G

n

的一个逻辑结果。而G有唯一一个与其等价的主合取范式，设为G’’。

可设G’’共有m个极大项，则可以知道令G’’取1的解释使这m个极大项也取1。则

从S出发的演绎出来的的所有命题公式正是从这m个极大项中任取n(0≤n≤m)个合取组

成，共有2m个，其中包括恒真公式这里用1表示。

设H为由若干极大项构成的合取公式。现在证明：

1)S=>H，即G=>H。从定义出发，设有一解释I使G=G

1

…G

n

取1值，必使G的

主合取范式也取1值。即使每一个极大项都取1值。从而使由若干极大项合取组

成的公式H也取1值，则有S=>H。

2)任意设公式H是S的一个逻辑结果，H是一些极大项的合取。现在要证组成H的

极大项都在G的主合取范式G”中。

反证法：若不然，假设H中有一个极大项m

k

不在G的主合取范式中。则取使m

k

为0的解释I，可有解释I使H取0值。而I使所有不等于m

k

的极大项都为1，则

可有G的主合取范式G’’在I下取1值，即G在I下取1值，这与G=>H矛盾。

5.设G

1

，…，G

n

是公式。证明：从{G

1

，…，G

n

}出发可演绎出公式G的充要条件是从

{G

1

，…，G

n

，G}出发可演绎出公式(RR)。其中R为任意公式。

证明：充分性，即{G

1

，…，G

n

，G}=>(RR)，可有

G

1

…G

n

G=>(RR)，因(RR)恒假，则G

1

…G

n

G恒假。那么有（G

1

…G

n

）

G恒真，即（G

1

…G

n

）G恒真，则有(G

1

…G

n

)=>G，因此有{G

1

，…，G

n

}蕴涵G。

必要性，即已知：{G

1

，…，G

n

}=>G，有（G

1

…G

n

）G恒真，即（G

1

…

G

n

）G恒真，那么对上式取非有G

1

…G

n

G恒假，也就是(G

1

…G

n

G)(RR)

恒真，其中R为任意一个公式，则有(G

1

…G

n

G)=>(RR)，即从{G

1

，…，G

n

，G}

出发可演绎出公式(RR)。

命题得证。

习题2.4解答

3.证明：命题公式G是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包

含一个原子及其否定。

证明：设公式G的合取范式为：G’=G

1

G

2

…G

n

若公式G恒真，则G’恒真，即子句G

i；i=1,2,…n

恒真

为其充要条件。

G

i

恒真则其必然有一个原子和它的否定同时出现在G

i

中，也就是说无论一个解释I

使这个原子为1或0，G

i

都取1值。

若不然，假设G

i

恒真，但每个原子和其否定都不同时出现在G

i

中。则可以给定一

个解释I，使带否定号的原子为1，不带否定号的原子为0，那么G

i

在解释I下的取值为0。

这与G

i

恒真矛盾。

因此，公式G是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一

个原子及其否定。

4.试将下列公式化为析取范式和合取范式：

a)P(PQ)

b)(PQ)(PQ)

解：a)P(PQ)

=P(PQ)(合取范式)

=(PP)(PQ)(析取范式)

=PQ(合取、析取范式)

b)(PQ)(PQ)

=((PQ)(PQ))((PQ)(PQ))

=((PQ)(PQ))((PQ)(PQ))

=(PQ(PQ))(PQ(PQ))

=(PQ)(PQ)(合取范式)

=((PQ)P)((PQ)Q)

=(PQ)(PQ)(析取范式)

习题3.1解答

1.设下面所有谓词的定义域都是{a，b，c}。试将下面谓词公式中的量词消除，写成与之

等价的命题公式。

(1)xR(x)xS(x)

(2)x(P(x)Q(x))

(3)xP(x)xP(x)

解：（1）xR(x)xS(x)等价的命题公式为：

R(a)R(b)R(c)(S(a)S(b)S(c))

（2）x(P(x)Q(x))等价的命题公式为：

(P(a)Q(a))(P(b)Q(b))(P(c)Q(c))

（3）xP(x)xP(x)等价的命题公式为：

(P(a)P(b)P(b))(P(a)P(b)P(b))

3．指出下列表达式中的自由变量和约束变量，并指明量词的作用域：

（1）(xP(x)xQ(x))(xP(x)Q(y))

（2）xy((P(x)Q(y))zR(z))

（3）A(z)(xyB(x，y，a))

（4）xA(x)yB(x，y)

（5）(xF(x)yG(x，y，z))zH(x，y，z)

解：（1）中的自由变量是Q(y)中的y，约束变量是P(x)、Q(x))和P(x)中的x，第一

个量词x的作用域是P(x)，第2个量词x的作用域是Q(x)，第三个量词x的作用域是

P(x)。

（2）此式中没有自由变量，x，y，z都是约束变量，x和y的作用域都是

(P(x)Q(y))zR(z)，而z的作用域是R(z)。

（3）z是自由变量，x和y是约束变量，xy的作用域是B(x，y，a)。

（4）x是自由变量，x和y是约束变量，x的作用域是A(x)，y的作用域是B(x，y)。

（5）x，y和z是自由变量并且x，y和z又是约束变量，x的作用域是F(x)，y的作用

域是G(x，y，z)，z的作用域是H(x，y，z)。

习题3.2解答

1.设I是如下一个解释：

D={a，b}

P(a，a)P(a，b)P(b，a)P(b，b)

1001

试确定下列公式在I下的真值：

（5）xy(P(x，y)P(y，x))；真值为1

（6）xP(x，x)真值为1

3.设I是如下一个解释：

D={3，2}

abf(3)f(2)P(3，3)P(3，2)P(2，3)P(2，2)

32231100

试求出下列公式在I下的真值：

4.(a，f(a))P(b，f(b))；真值为0

5.xyP(y，x)；真值为1

6.xy(P(x，y)P(f(x)，f(y)))；真值为0

习题3.3解答

1.设G

1

=x(P(x)Q(x))，G

2

=Q(a)，证明：P(a)是G

1

和G

2

的逻辑结果。

证明：设G=G

1

G

2

，往证若解释I满足G，则必满足P(a)。

反证法：若解释I满足G，而弄假P(a)，则在解释I下，P(a)为真；G

2

也必为真，所以

Q(a)为假。故P(a)Q(a)为假，则G

1

为假，因此G为假，这与解释I满足G矛盾。从而结

论得证。

4指出下面推理的错误：

（1）x(P(x)Q(x))前提

（2）P(y)Q(y)（1），UG

（3）xP(x)前提

（4）P(y)（3），ES

（5）Q(y)（2），（4）

（6）xQ(x)（5），EG

解：第（4）中的p(y)中的y不能由ES规则推出。因为此y是由第（1）步利用US

规则提出的，此时，应该选另外的符号，如符号“c”。

习题3.4解答

1.试将下列公式化成等价的前束范式：

(1)x(P(x)yQ(x，y))；

=x(P(x)yQ(x，y))

=xy(P(x)Q(x，y))

(2)x((yP(x，y))(zQ(z)R(x)))；

=x((yP(x，y))((zQ(z))R(x)))

=x((yP(x，y))((zQ(z))R(x)))

=x((yP(x，y))(z(Q(z))R(x)))

=xy(P(x，y)(z(Q(z))R(x)))

=xyz(P(x，y)Q(z)R(x))

(3)xy(zP(x，y，z)(uQ(x，u)vQ(y，v)))。

=xyz(P(x，y，z)((uQ(x，u))vQ(y，v)))

=xyz(P(x，y，z)(u(Q(x，u))vQ(y，v)))

=xyz(P(x，y，z)uv(Q(x，u)Q(y，v)))

=xyzuv(P(x，y，z)(Q(x，u)Q(y，v)))

2.找出下面公式的Skolem范式：

(1)(xP(x)yzQ(y，z))；

=((xP(x))yzQ(y，z))

=xP(x)(yzQ(y，z)))

=x(P(x)y(zQ(y，z)))

=xy(P(x)z(Q(y，z)))

=xyz(P(x)Q(y，z))

用f(x，y)代替z得Skolem范式:

xy(P(x)Q(y，f(x，y)))

(2)x(E(x，0)(y(E(y，g(x))z(E(z，g(x))E(y，z)))))。

＝x(E(x，0)(y(E(y，g(x))z(E(z，g(x))E(y，z)))))

＝x(E(x，0)(y(E(y，g(x))z(E(z，g(x))E(y，z)))))

＝xyz(E(x，0)(E(y，g(x))(E(z，g(x))E(y，z))))

＝xyz((E(x，0)E(y，g(x)))(E(x，0)E(z，g(x))E(y，z)))

用f(x)代替y得Skolem范式:

Skolem范式:xz((E(x，0)E(f(x)，g(x)))(E(x，0)E(z，g(x))E(f(x)，z)))

习题3.5解答

1．将下面的命题符号化，并证明之。

(1)“已知每一个大学生都是诚实的，而约翰是不诚实的，证明约翰不是大学生”。

P(x)：x是大学生；Q(x)：x是诚实的；约翰记为a。

G

1

：x(P(x)Q(x))；G

2

：Q(a)；C：P(a)

证明略。

(2)“已知：每一个运动员都是强壮的，而每一个即强壮又聪明的人在他所从事的事业中都

将获得成功，彼得是运动员而且是聪明的，证明彼得在他的事业中将会成功”。

P(x)：x是运动员；Q(x)：x是强壮的；R(x)：x是聪明的；S(x)：x在他的事业中成功；彼

得记为a。

G

1

：x(P(x)Q(x))；G

2

：x((Q(x)R(x))S(x))；G

3

：P(a)R(a)；C：S(a)

证明略。

(4)“已知海关人员检查每一个进入本国的不重要人物，某些走私者进入该国时仅仅被走私

者所检查，没有一个走私者是重要人物，证明海关人员中的某些人是走私者”。

E(x)：x进入国境；V(x)：x是重要人物；C(x)：x是海关人员；P(x)：x是走私者；S(x，y)：

y检查x；

G

1

：x(E(x)V(x))y(C(y)S(x，y)))；

G

2

：x(P(x)E(x)y(S(x，y)P(y)))；

G

3

：x(P(x)V(x))；

C：x(P(x)C(x))

证明：1x(E(x)V(x))y(C(y)S(x，y)))P

2(E(a)V(a))y(C(y)S(a，y)))US,1

3x(P(x)E(x)y(S(x，y)P(y)))P

4P(a)E(a)y(S(a，y)P(y))US,3

5P(a)I,4

6E(a)I,4

7y(S(a，y)P(y))I,4

8S(a,z)P(z)US,7

9x(P(x)V(x))P

10(P(a)V(a)US,9

11V(a)T,5,10,I

12y(C(y)S(a，y))T,2,6,11,I

13C(b)S(a，b)ES,12

14C(b)13,I

15x(P(a)C(a))T,5,14,EG。

习题6.2解答

1.设（G，·）是代数系统，则（G×G，*）是代数系统，这里G×G的运算“*”规

定如下：

（a，b）*（c，d）=（a·b，c·d），

其中，a，b，c，d为G中任意元素。证明：当（G，·）是半群时，（G×G，*）是半群；

当（G，·）有单位元素时，（G×G，*）有单位元素；当（G，·）是群时，（G×G，*）

是群；

证明：设（G，·）是半群，a，b，c，d，e，f为G中任意元素，若有(a，b),(c，d)，

(e，f)属于G×G，则有

(a，b)*((c，d)*(e，f))=(a，b)*(c·e，d·f)=(a·(c·e)，b·(d·f))

=((a·c)·e，(b·d)·f))=((a·c)，(b·d))*(e，f)=((a，b)*(c，d))*(e，f)，

这就证明了当（G，·）是半群时，（G×G，*）是半群。

设（G，·）有单位元素1，(a，b)是（G×G，*）中任意元素，则有(a，b)=(a·1，b·1)=(a，

b)*(1，1)且(a，b)=(1·a，1·b)=(1，1)*(a，b)，故(1，1)就是（G×G，*）的单位元素。

设（G，·）是群，1是群（G，·）的单位元素，则由前面的证明知(1，1)就是（G×

G，*）的1且（G×G，*）是半群。

我们来证明（G×G，*）中的任意元素(a，b)有逆元素。(1，1)=(a·a’，b·b’)=(a，b)*(a’，

b’)，其中a’和b’分别是a和b在群（G，·）中的逆元素。同样有(1，1)=(a’·a，b’·b)=(a’，

b’)*(a，b)，这就证明了(a’，b’)是(a，b)的逆元素，从而说明（G×G，*）是群。

5.设集合G={a，b，c}上的二元运算表如下：

·abc

aabc

bbac

cccc

则（G，·）是否为半群？是否为群？为什么？

解：由于G非空且对任意的a，b属于G，有a·b属于G，故（G，·）是代数系统。又

由于·运算满足结合律，故（G，·）是半群，但（G，·）不是群，因为元素c没有逆元素。

习题8.2解答

1.设S是所有命题做成的集合，说明S在什么运算下做成代数格？在什么部分序下做

成半序格。

解：S在合取运算()和析取运算()下做成代数格。不难验证这两种运算有交换律、结

合律、吸收律。

S在蕴涵()这个部分序下做成半序格。ABAB=A且AB=B.

2.设(L，，⊕)是一个格，a,bL。令S={x|(xL)(axb)}其中是与(L,,⊕)等价的

半序格中的部分序。

证明：(S,，⊕)是L的子格。

设c，dS,则c,dL，且ac,db所以ac*d而显然有c*db

c⊕dbac⊕d

故S对*，⊕运算封闭

即(S，*，⊕)是L的子格。

3.设D是集合S上的整除关系。以下部分序集是否为格：

(1)S={1，2，3，4，6，12}

(2)S={1，2，3，4，6，8，10，12}

(3)S={1，2，3，4，5，6，7，8，9，10}

(4)S={2，3，6，12，24，36}

解：（1）和（4）是格。

习题8.3解答

1.设(L，)是格，若a,b,cL,abc，则a⊕b=b*c(a*b)⊕(b*c)=(a⊕b)*(a⊕c)

证明：因abc故a⊕b=b=b*ca*b=a,b*c=b,a⊕b=b,a⊕c=c

故(a*b)⊕(b*c)=(a⊕b)=b(a⊕b)*(a⊕c)=b*c=b

即(a*b)⊕(b⊕*c)=(a⊕b)*(a⊕c).

习题8.4解答

1．证明：在有余分配格（L，×，）中，对任意a，b∈L，有

a≤ba×b′=0

b′≤a′a′b=1

a≤bb′≤a′

证明：

①abab’=0

)∵a≤b，∴ab=a，

∴ab’=(ab)b’=a(bb’)=a0=a

)ab=(ab)0=(ab)(ab’)=a(b+b’)=a1=a

故ab

②)∵b’a’，∴b’a’=a’，

∴a’b=(b’a’)b=a’(b’b)=a1=1

)a’b’=(a’b’)1=(a’b’)(a’b’)

=a’(b’b)=a’0=a’

∴b’a’。

③abb’a’

abab=aa’b’=a’b’a’

4．设（L，×，）为模格，试证明若有

（ab）×c=b×c

则有（cb）×a=b×a。

证明：一方面，由cb≥b知，(cb)×a≥b×a。

另一方面,

(cb)×a≤(cb)×(ab)

由（L，×，）为模格，且b≤ab，知

(ab)×(bc)=b((ab)×c)

而(ab)×(bc)=(cb)×(ab)，且由已知，（ab）×c=b×c，得：

(cb)×a≤(cb)×(ab)=(ab)×(bc)

=b((ab)×c)

=b(b×c)=b，

因此,(cb)×a≤b，又显然，(cb)×a≤a，因此，(cb)×a≤b×a。

综上(cb)×a=b×a.

例题

例1.2.1设A，B，C，D是任意四个非空集合，若AC，BD，则A×BC×D。

证明：任取(x，y)A×B，往证(x，y)C×D。

由(x，y)A×B知，xA，且yB。又由AC，BD知，xC，且yD，因此，

(x，y)C×D。故，A×BC×D。

例1.2.2设A，B，C，D是任意四个集合，求证（A×B）（C×D）=（AC）×（BD）。

证明：首先证明（A×B）（C×D）（AC）×（BD）。任取（x,y）（A×B）

（C×D），则（x,y）（A×B），且（x,y）（C×D），故xA，yB，xC，yD，即

xAC，yBD，因此，（x,y）（AC）×（BD）。

由于以上证明的每一步都是等价的，所以上述论证反方向进行也是成立的。故可证得

（AC）×（BD）（A×B）（C×D）。

因此，（A×B）（C×D）=（AC）×（BD）。

例1.2.2设A，B，C是三个集合，已知AB=AC，AB=AC，求证B=C。

证法1：使用反证法。假设B≠C，则必存在x，满足xB，且xC，或者xB，且

xC。不妨设xB，且xC，

①若xA，则xAB，但xAC，与AB=AC矛盾。

②若xA，则xAB，但xAC，与AB=AC矛盾。

所以原假设不对，B=C。

证法2：利用已知以及集合运算的交换律、分配律与吸收律，有

B=B(AB)

=B(AC)

=(BA)(BC)

=(CA)(BC)

=C(AB)

=C(AC)

=C

例1.2.6设



，是集合A上的二元运算，对任意a,b,cA，满足：

（1）(a



b)



c=a



(b



c),(ab)c=a(bc);

（2）a



b=b



a,ab=ba;

（3）a



（ba）=a,a（b



a）=a。

现在定义A上的关系“≤”如下：

a≤ba



b=a,

试证明：

①≤是A上的部分序关系；

②对任意a,bA，{a,b}均有一个上确界和下确界。

证明：①只需证明≤具有自反性、反对称性和传递性。

由题设“≤”关系的定义知，a≤ba



b=a,故a≤aa



a=a，因此要证明≤具有自

反性，只需证明a



a=a。

而a



a=a



（a（b



a））由（3）的第2式

=a



（（b



a）a）由（2）的第2式

=a由（3）的第1式

因此，a≤a，≤具有自反性。

对任意a,bA，如果a≤b且b≤a，由“≤”关系的定义知，a



b=a，且b



a=b，再由（2）

的第1式知，a



b=b



a,，故a=b。因此，≤具有反对称性。

对任意a,b,cA，如果a≤b且b≤c，由“≤”关系的定义知，a



b=a，且b



c=b，故

ac=(ab)c

=a(bc)由（1）的第1式

=ab

=a，

因此，a≤c，≤具有传递性。

综上，≤是A上的部分序关系。

例6.2.1设S=Q×Q，Q为有理数集合，﹡为S上的二元运算，对于任意的，

∈S，有：

﹡=，

问：（1）﹡的单位元是什么？

（2）当a≠0时，的逆元是什么？

解：（1）设﹡的单位元是

1

,e

2

>，则对于任意的∈S，有：

1

,e

2

>﹡=

1

x,e

1

y+e

2

>，

﹡

1

,e

2

>=

1

,xe

2

+y>，

因为

1

,e

2

>是单位元，所以

1

,e

2

>﹡=﹡

1

,e

2

>=。

故











yeye

xxe

21

1且











yyxe

xxe

2

1

，

解得：











0

1

2

1

e

e

。

因此，﹡的单位元是<1，0>。

（2）当a≠0时，设的逆元为，则

﹡=<1，0>，

而

﹡=，

故















0ab

1

1-

1

b

aa

。

解得：























a

b

b

a

a

1

1

1

。

因此，的逆元为<

a

b

a

,

1

>。

例6.2.2设（G，·）是一个群，若群G的每一个元素都满足方程x2=1（其中1是G的

单位元），那么G是交换群。

证明：对任意的a，b∈G，则运算的封闭性有a·b∈G，故由题意知，

a2=1，b2=1，

（a·b）2=1。

又（a·b）2=a·b·a·b，故

a·b·a·b=1。

因此，

a·b=a·1·b=a·(a·b·a·b)·b

由（G，·）是群，运算满足结合律，所以

a·(a·b·a·b)·b=a2·（b·a）·b2=1·（b·a）·1=b·a

即，a·b=b·a，所以，G是交换群。

例6.2.3设（G，·）是一个半群，e是左壹，且对每一个x∈A，存在x’∈A，使得x·x’=e。

试证明：对于任意的a，b，c∈A，如果a·b=a·c，则b=c。

证明：对于任意的a，b，c∈A，如果a·b=a·c，由题设条件知，对a∈A，存在a’

∈A，使得a·a’=e。在等式a·b=a·c的两边同时左乘a’，得到

a’·（a·b）=a’·（a·c）。

因（G，·）是一个半群，运算满足结合律，故

a’·（a·b）=（a’·a）·b=e·b，

a’·（a·c）=（a’·a）·c=e·c。

由e是左壹知，

e·b=b，

e·c=c。

综上，b=c。

例6.2.14设（R，-）和(R

+

，÷)是两个代数系统，其中R和R

+

分别为实数集合与正实

数集合，-与÷分别为算术加法与除法，试证明：（R，-）和(R

+

，÷)同构。

证明：构造函数f(x)=ex。

（1）证明该映射为R到R

+

的1-1映射。

显然f为R到R

+

的映射。

对任意y∈R

+

，都有x=lny，使得ex=y，所以f为R到R

+

上的映射（满射）。

对于任意a,b∈R，若a≠b，则ea≠eb，所以f为单射。

（2）证明f为同态映射。

对于任意a,b∈R，有f(a-b)=ea-b=ea÷eb=f(a)÷f(b)。所以，f为R到R

+

的同态映射。

综上，f是R到R

+

的同构映射，即，（R，-）和(R

+

，÷)同构。

例8.2.1请判断下面关于格的命题的真假性

⑴设（L，×，）是格，则（L，×）和（L，）均为交换半群。

⑵设（L，×，）是格，a，b∈L，那么，ab=a和ab=b至少有一个成立。

⑶设（L，×，）是格，a∈L，若a有余元素，那么该余元素是唯一的。

⑷设N为正整数集合，|为其上的整除关系，则（N，|）为有余分配格。

解：

⑴该命题为真命题。

因为若（L，×，）是格，则×和均满足交换律、结合律和运算的封闭性，所以

（L，×）和（L，）均为交换半群。。

⑵该命题为假命题。

设L={，{x},{y},{x，y}}，则（L，∩，∪）是一个格，若令a={x}，b={y}，则a∪

b=a和a∪b=b两者均不成立。

⑶该命题为假命题。

因为一个元素可能有两个以上的余元素。

⑷该命题为假命题。

因为根据有余格的定义，有余格一定是有界格，而（N，|）显然不存在上界，因而不可

能是有余分配格。

例8.2.2证明：若一个有界格（L，×，，0，1）含有不只一个元素，则该有界格中

任何一个元素的余元素必不是它自身。

证明：我们已经知道在有界格中0，1互为余元素。若存在x≠0，x≠1，但x以自身为

余元素，则有

x×x=0，xx=1，

而又由于

x×x=x，xx=x，

所以，x=0，x=1，即0=1。由题设有界格（L，×，，0，1）含有不止一个元素知，0=1

显然是矛盾的。因此，若一个有界格含有不只一个元素，则任何一个元素的余元素必不是它

自身。

例8.2.4设（L，×，，0，1）是有界格，相应的部分序关系是≤，证明：对于a，b

∈L，

（1）若ab=0，则a=b=0，

（2）若a×b=1，则a=b=1。

证明：（1）因为a≤ab，由题设ab=0，所以a≤0。另一方面，因0是L上的最小

元，有0≤a。由≤的反对称性知，a=0。同理可证b=0。

（2）因为a×b≤a,由题设a×b=1，所以1≤a。另一方面，因1是L上的最大元，有

a≤1。由≤的反对称性知，a=1。同理可证b=1。

例8.2.5设（L，×，，0，1）是有界分配格，证明：L中拥有余元素的的各元素构

成一个代数子格。

证明：设L中拥有余元素的的各元素构成的集合为L’，对于任意的a，b∈L’，它们的

余元素分别记为a’和b’。

首先考察a×b，因为

(a×b)×(a’b’)=(a×b×a’)(a×b×b’)=00=0

(a×b)(a’b’)=(aa’b’)×(ba’b’)=1×1=1

所以a×b有余元素a’b’，a×b∈L’。

同理，ab有余元素a’×b’，所以，ab∈L’。

因此，L’对运算×，封闭，故L’是L的代数子格。

例8.2.7设f是格（L，×，+）到格（S，∧，∨）的同态映射，试证明（L，×，+）

的同态象是（S，∧，∨）的子格。

证明：（L，×，+）的同态象是f(L)={f(x)|x∈L}。任取s

1

，s

2

∈f(L)，则有l

1

，l

2

∈L，

满足f(l

1

)=s

1

，f(l

2

)=s

2

。由f是格（L，×，+）到格（S，∧，∨）的同态映射，知：

s

1

∧s

2

=f(l

1

)∧f(l

2

)

=f(l

1

×l

2

)，

s

1

∨s

2

=f(l

1

)∨f(l

2

)

=f(l

1

+l

2

)。

由（L，×，+）是格知，l

1

×l

2

∈L，l

1

+l

2

∈L，因此，f(l

1

×l

2

)∈f(L)，f(l

1

+l

2

)∈f(L)，即，

s

1

∧s

2

∈f(L)，s

1

∨s

2

∈f(L)，故，f(L)对运算∧和∨封闭。（L，×，+）的同态象是（S，∧，

∨）的子格。

例8.2.8设（L，×，+）是一分配格，a∈L，设

f(x)=x+a，x∈L，

g(x)=x×a，x∈L，

证明：f和g都是（L，×，+）到自身的格同态映射。

证明：对任意的x，y∈L，有：

f(x)+f(y)=(x+a)+(y+a)

=(x+y)+a

=f(x+y)

f(x)×f(y)=(x+a)×(y+a)

=(x×y)+aL是分配格

=f(x×y)。

因此，f是（L，×，+）到自身的格同态映射。

同理可证，g是（L，×，+）到自身的格同态映射。

例8.2.9设f是格（L，≤

1

）到格（S，≤

2

）的满同态映射。证明：若（L，≤

1

）是有

界格，则（S，≤

2

）也是有界格。

证明：因（L，≤

1

）是有界格，设最大元为1，最小元为0。令f(1)=1’,f(0)=0’，则1’，

0’∈S。因f是满设，故对任意的x’∈S，都有x∈L，使得f(x)=x’。又因为f是同态映射，

因此亦是保序映射，故由0≤

1

x≤

1

1，有f(0)≤

2

f(x)≤

2

f(1)，即0’≤

2

x’≤

2

1’，这就是说1’和

0’分别是（S，≤

2

）的最大元和最小元。因此，（S，≤

2

）是有界格。