离散数学课后习题.doc

一、选择或填空
（数理逻辑部分）
1、下列哪些公式为永真蕴含式？(　　　)
(1)Q=>Q→P (2)Q=>P→Q (3)P=>P→Q (4)P(PQ)=>P
答：（1），（4）
2、下列公式中哪些是永真式？( )
(1)(┐PQ)→(Q→R) (2)P→(Q→Q) (3)(PQ)→P (4)P→(PQ)
答：（2），（3），（4）
3、设有下列公式，请问哪几个是永真蕴涵式?( )
(1)P=>PQ (2) PQ=>P (3) PQ=>PQ
(4)P(P→Q)=>Q (5) (P→Q)=>P (6) P(PQ)=>P
答：（2），（3），（4），（5），（6）
4、公式"x((A(x)®B(y，x))Ù $z C(y，z))®D(x)中，自由变元是( )，约束变元是( )。
答：x,y, x,z
5、判断下列语句是不是命题。若是，给出命题的真值。( )
(1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。　
(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。　
(5) 前进！ (6) 给我一杯水吧！
答：（1） 是，T （2） 是，F （3） 不是
（4） 是，T （5） 不是 （6） 不是
6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。
答：所有人都不是大学生，有些人不会死
7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。
(1)　只有在生病时，我才不去学校 (2) 若我生病，则我不去学校
(3)　当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校
答：（1） （2） （3） （4）
8、设个体域为整数集，则下列公式的意义是( )。
(1) "x$y(x+y=0) (2) $y"x(x+y=0)
答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0
9、设全体域D是正整数集合，确定下列命题的真值：
(1) "x$y (xy=y)　　(　　)　　(2) $x"y(x+y=y)　　(　　)
(3) $x"y(x+y=x) 　(　　)　　(4) "x$y(y=2x)　　 (　　)
答：（1） F （2） F （3）F （4）T
11、命题“2是偶数或-3是负数”的否定是（ ）。
答：2不是偶数且-3不是负数。
12、永真式的否定是（ ）
(1) 永真式　(2) 永假式　(3) 可满足式　(4) (1)--(3)均有可能
答：（2）
13、公式(PQ)(PQ)化简为（ ），公式 Q(P(PQ))可化简为（ ）。
答：P ，QP
15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。
答："x(R(x)Q(x))

（二元关系部分）
28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求(1)R (2) R-1 。
答：（1）R={<1,1>,<4,2>} (2) R={<1,1>,<2,4>}
29、举出集合A上的既是等价关系又是偏序关系的一个例子。(　　　　)
答：A上的恒等关系
30、集合A上的等价关系的三个性质是什么？( )
答：自反性、对称性和传递性
31、集合A上的偏序关系的三个性质是什么？( )
答：自反性、反对称性和传递性
32、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝
求(1)RR (2) R-1 。
答：RR ={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}
R-1 =｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝
33、设Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除关系，求R= {(　　　　　)}。
答：R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,
<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}
34、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=2y｝，求(1)R (2) R-1 。
答：（1）R={<1,1>,<4,2>,<6,3>} (2) R={<1,1>,<2,4>,(3，6>}
35、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求R和R-1的关系矩阵。
答：R的关系矩阵= R的关系矩阵=
36、集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,yA}，则R 的性质为（ ）。
(1) 自反的　　(2) 对称的　　 (3) 传递的，对称的 (4) 传递的
答：（2）

（代数结构部分）
37、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点<A,*>中，单位元是( )，零元是( )。
答：2，6
38、设A={3,6,9}，A上的二元运算*定义为：a*b=min{a,b}，则在独异点<A,*>中，单位元是( )，零元是( )；
答：9，3

（半群与群部分）
39、设〈G,*〉是一个群，则
(1) 若a,b,x∈G，ax=b，则x=( )；
(2) 若a,b,x∈G，ax=ab，则x=( )。
答： （1） ab （2） b
40、设a是12阶群的生成元， 则a2是( )阶元素，a3是( )阶元素。
答： 6,4
41、代数系统<G,*>是一个群，则G的等幂元是(　　　　)。
答：单位元
42、设a是10阶群的生成元， 则a4是( )阶元素，a3是( )阶元素。
答：5，10
43、群<G,*>的等幂元是(　　)，有(　　　)个。
答：单位元，1
44、素数阶群一定是( )群, 它的生成元是( )。
答：循环群，任一非单位元
45、设〈G,*〉是一个群，a,b,c∈G，则
(1) 若ca=b，则c=( )；(2) 若ca=ba，则c=( )。
答：（1） b (2) b
46、<H,,>是<G,,>的子群的充分必要条件是( )。
答：<H,,>是群 或 " a，b G， abH，a-1H 或" a,b G，ab-1H
47、群＜A,*＞的等幂元有(　　　)个，是(　　　)，零元有(　　　)个。
答：1，单位元，0
48、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是( )。
答：k
49、在自然数集N上，下列哪种运算是可结合的？（ ）
(1) a*b=a-b　　(2) a*b=max{a,b}　(3) a*b=a+2b　(4) a*b=|a-b|
答：(2)
50、任意一个具有2个或以上元的半群，它（ ）。
(1) 不可能是群　　(2) 不一定是群　
(3) 一定是群 　(4) 是交换群
答：(1)
51、6阶有限群的任何子群一定不是（ ）。
(1) 2阶　　(2) 3 阶 (3) 4 阶 　(4) 6 阶
答：(3)
（数理逻辑部分）
二、求下列各公式的主析取范式和主合取范式：
1、(P→Q)R　
解：(P→Q)R(PQ )R
(PR)(QR) （析取范式）
(P(QQ)R)((PP)QR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)（主析取范式）
((P→Q)R)(PQR)(PQR)(PQR)
(PQR)( PQR)（原公式否定的主析取范式）
(P→Q)R(PQR)(PQR)(PQR)
(PQR)(PQR)（主合取范式）
2、(PR)(QR)P
解： (PR)(QR)P（析取范式）
(P(QQ)R)((PP)QR)(P(QQ)(RR))
(PQR)(PQR)(PQR)(PQR)
( PQR)( PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR) (PQR)(PQR) (主析取范式)
（(PR)(QR)P）
(PQR)(PQR）（原公式否定的主析取范式）
(PR)(QR)P (PQR)(PQR)（主合取范式）
3、(P→Q)(RP)
解：(P→Q)(RP)　
(PQ)(RP)（合取范式）
(PQ(RR))(P(QQ))R)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)（主合取范式）
((P→Q)(RP))
(PQR)(PQR)(PQR)(PQR)
(PQR)（原公式否定的主合取范式）
(P→Q)(RP)　
(PQR)(PQR)(PQR)(PQR)(PQR)
（主析取范式）
4、Q→(PR)
解：Q→(PR)
QPR（主合取范式）
（Q→(PR)）
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR）（原公式否定的主合取范式）
Q→(PR)
(PQR)(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR）（主析取范式）
5、P→(P(Q→P))
解：P→(P(Q→P))
P(P(QP))
PP
T (主合取范式)
(PQ)(PQ)(PQ)(PQ)（主析取范式）
6、(P→Q)(RP)
解： (P→Q)(RP)(PQ)(RP)
(PQ)(RP)（析取范式）
(PQ(RR))(P(QQ)R)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)（主析取范式）
((P→Q)(RP))(PQR)(PQR)(PQR)
(PQR)(PQR)（原公式否定的主析取范式）
(P→Q)(RP)(PQR)(PQR)(PQR)
(PQR)(PQR)（主合取范式）
7、P(P→Q) 　　　　
解：P(P→Q)P(PQ)(PP)Q
T(主合取范式)
(PQ)(PQ)(PQ)(PQ)（主析取范式）
8、(R→Q)P
解：(R→Q)P(RQ )P
(RP)(QP) （析取范式）
(R(QQ)P)((RR)QP)
(RQP)(RQP)(RQP)(RQP)
(PQR)(PQR)(PQR)（主析取范式）
((R→Q)P)(PQR)(PQR）(PQR) (PQR)(PQR)（原公式否定的主析取范式）
(R→Q)P(PQR)(PQR)(PQR)
(PQR)(PQR)（主合取范式）
9、P→Q
解：P→QPQ（主合取范式）
(P(QQ))((PP)Q)
(PQ)(PQ)(PQ)(PQ)
(PQ)(PQ)(PQ)（主析取范式）
10、　PQ　
解： PQ （主合取范式）
(P(QQ))((PP)Q）
(PQ)(PQ)(PQ)(PQ）
(PQ)(PQ)(PQ)（主析取范式）
11、PQ
解：PQ（主析取范式）(P(QQ))((PP)Q)
(PQ)(PQ)(PQ)(PQ)
(PQ)(PQ)(PQ)（主合取范式）

12、（PR）Q
解：（PR）Q
(PR)Q
(PR)Q
(PQ)(RQ)（合取范式）
(PQ(RR))((PP)QR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)（主合取范式）
（PR）Q
(PQR)(PQR)(PQR)(PQR)(PQR) （原公式否定的主析取范式）
（PR）Q
(PQR)(PQR)(PQR)(PQR)
(PQR)（主析取范式）
13、（PQ）R
解：（PQ）R
(PQ)R
(PQ)R(析取范式)
(PQ(RR))((PP)(QQ)R)
(PQR)(PQR)(PQR)(PQR)(PQR)
(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(主析取范式）
（PQ）R
(PQ)R
(PQ)R(析取范式)
(PR)(QR)(合取范式)
(P(QQ)R)((PP)QR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(主合取范式)
14、(P(QR))(P(QR))
解：(P(QR))(P(QR))
(P(QR))(P(QR))
(PQ)(PR)(PQ)(PR)（合取范式）
(PQ(RR))(P(QQ)R)(PQ(RR))
(P(QQ)R)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(主合取范式)
(P(QR))(P(QR))
(PQR)(PQR)(原公式否定的主合取范式)
(P(QR))(P(QR))
(PQR)(PQR)(主析取范式)
15、P(P(Q(QR)))
解：P(P(Q(QR)))
P(P(Q(QR)))
PQR(主合取范式)
(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)
(原公式否定的主合取范式)
(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(主析取范式)
16、(PQ)(PR)
解、(PQ)(PR)
(PQ)(PR) (合取范式)
(PQ(RR)(P(QQ)R)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(主合取范式)
(PQ)(PR)
(PQ)(PR)
P(QR)(合取范式)
(P(QQ)(RR))((PP)QR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR)(PQR)
(主析取范式)

三、证明：
1、P→Q，QR，R，SP=>S
证明：
(1) R 前提
(2) QR 前提
(3) Q （1），（2）
(4) P→Q 前提
(5) P （3），（4）
(6) SP 前提
(7) S （5），（6）
2、A→(B→C)，C→(DE)，F→(DE),A=>B→F
证明：
(1) A 前提
(2) A→(B→C) 前提
(3) B→C （1），（2）
(4) B 附加前提
(5) C （3），（4）
(6) C→(DE) 前提
(7) DE （5），（6）
(8) F→(DE) 前提
(9) F （7），（8）
(10) B→F CP
3、PQ， P→R, Q→S => RS
证明：
(1) R 附加前提
(2) P→R 前提
(3) P （1），（2）
(4) PQ 前提
(5) Q （3），（4）
(6) Q→S 前提
(7) S （5），（6）
(8) RS CP，（1），（8）
4、(P→Q)(R→S)，(Q→W)(S→X)，(WX)，P→R => P
证明：
（1） P 假设前提
（2） P→R 前提
（3） R （1），（2）
（4） (P→Q)(R→S) 前提
（5） P→Q （4）
（6） R→S （5）
（7） Q （1），（5）
（8） S （3），（6）
（9） (Q→W)(S→X) 前提
（10） Q→W （9）
（11） S→X （10）
（12） W （7），（10）
（13） X （8），（11）
（14） WX （12），（13）
（15） (WX) 前提
（16） (WX)(WX) （14），（15）
5、(UV)→(MN), UP, P→(QS)，QS =>M
证明：
(1) QS 附加前提
（2） P→(QS) 前提
（3） P （1），（2）
（4） UP 前提
（5） U （3），（4）
（6） UV （5）
（7） (UV)→(MN) 前提
（8） MN (6),(7)
（9） M （8）
6、BD，(E→F)→D，E=>B
证明：
(1) B 附加前提
(2) BD 前提
(3) D （1），（2）
(4) (E→F)→D 前提
(5) (E→F) （3），（4）
(6) EF （5）
(7) E （6）
(8) E 前提
(9) EE （7），（8）
7、P→(Q→R)，R→(Q→S) => P→(Q→S)
证明：
（1） P 附加前提
（2） Q 附加前提
（3） P→(Q→R) 前提
（4） Q→R （1），（3）
（5） R （2），（4）
（6） R→(Q→S) 前提
（7） Q→S （5），（6）
（8） S （2），（7）
（9） Q→S CP，（2），（8）
（10） P→(Q→S) CP，（1），（9）
8、P→Q，P→R，R→S =>S→Q
证明：
（1） S 附加前提
（2） R→S 前提
（3） R （1），（2）
（4） P→R 前提
（5） P （3），（4）
（6） P→Q 前提
（7） Q (5），（6）
（8） S→Q CP，（1），（7）
9、P→(Q→R) => (P→Q)→(P→R)
证明：
(1) P→Q 附加前提
(2) P 附加前提
(3) Q (1),(2)
(4) P→(Q→R) 前提
(5) Q→R (2),(4)
(6) R (3),(5)
(7) P→R CP,(2),(6)
(8) (P→Q) →(P→R) CP,(1),(7)
10、P→(Q→R)，Q→P,S→R,P =>S
证明：
（1） P 前提
（2） P→(Q→R) 前提
（3） Q→R (1)，(2)
（4） Q→P 前提
（5） Q (1)，(4)
（6） R (3),(5)
（7） S→R 前提
（8） S (6)，(7)
11、A，A→B， A→C， B→(D→C) => D
证明：
（1） A 前提
（2） A→B 前提
（3） B (1)，(2)
（4） A→C 前提
（5） C (1)，(4)
（6） B→(D→C) 前提
（7） D→C (3)，(6)
（8） D (5)，(7)
12、A→(CB)，B→A，D→C => A→D
证明：
（1） A 附加前提
(2) A→(CB) 前提
(3) CB （1），（2）
(4) B→A 前提
(5) B （1），（4）
(6) C （3），（5）
(7) D→C 前提
(8) D （6），（7）
(9) A→D CP，（1），（8）
13、(PQ)(RQ) （PR）Q
证明、
(PQ)(RQ)
(PQ)(RQ)
(PR)Q
（PR）Q
(PR)Q
14、P(QP)P(PQ)
证明、
P(QP)
P(QP)
(P)(PQ)
P(PQ)
15、（PQ）（PR），(QR)，SPS
证明、
(1) （PQ）（PR） 前提
（2） P (QR) (1)
（3） (QR) 前提
（4） P （2），(3)
(5) SP 前提
(6) S (4),(5)
16、PQ，QR，RS P
证明、
(1) P 附加前提
（2） PQ 前提
（3） Q （1），（2）
（4） QR 前提
(5) R （3），（4）
(6 ) RS 前提
（7） R （6）
（8） RR （5），（7）
17、用真值表法证明ＰＱ (ＰＱ)(ＱＰ)
证明、
列出两个公式的真值表：

P Q
PQ （PQ）（QP）
F F
F T
T F
T T
T T
F F
F F
T T
由定义可知，这两个公式是等价的。
18、P→QP→(PQ)
证明、
设P→(PQ)为F，则P为T，PQ为F。所以P为T，Q为F ，从而P→Q也为F。所以P→QP→(PQ)。
19、用先求主范式的方法证明(P→Q)(P→R) (P→（QR）
证明、
先求出左右两个公式 的主合取范式
(P→Q)(P→R) (PQ)(PR)
(PQ(RR)))(P(QQ)R)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)
(P→（QR）) (P（QR）)
(PQ)(PR)
(PQ(RR))(P(QQ)R)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)
它们有一样的主合取范式，所以它们等价。
20、(P→Q)(QR) P
证明、
设(P→Q)(QR)为T，则P→Q和(QR)都为T。即P→Q和QR都为T。故P→Q，Q和R)都为T，即P→Q为T，Q和R都为F。从而P也为F，即P为T。从而(P→Q)(QR) P
21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效?
前提: (1) 若A队得第一，则B队或C队获亚军;
(2) 若C队获亚军，则A队不能获冠军;
(3) 若D队获亚军，则B队不能获亚军;
(4) A 队获第一;
结论: (5) D队不是亚军。
证明、
设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A（BC），CA，DB，A；结论符号化为 D。
本题即证明 A（BC），CA，DB，AD。
（1） A 前提
（2） A（BC）前提
（3） BC （1），（2）
（4） CA 前提
（5） C （1），（4）
（6） B （3），（5）
（7） DB 前提
（8） D （6），（7）
22、用推理规则证明PQ, (QR),PR不能同时为真。
证明、
(1) PR 前提
(2) P (1)
(3) PQ 前提
(4) Q (2),(3)
(5) (QR) 前提
(6) QR (5)
(7) Q (6)
(8) QQ (4),(7)

(7) 证明或解答：
（数理逻辑、集合论与二元关系部分）
3、列出下列二元关系的所有元素：
（1）A={0,1,2}，B={0,2,4}，R={<x,y>|x,y};
（2）A={1,2,3,4,5}，B={1,2}，R={<x,y>|2x+y4且x且yB};
（3）A={1,2,3}，B={-3,-2,-1,0,1}，R={<x,y>||x|=|y|且x且yB};
解：
(1) R={<0,0>,<0,2>,<2,0>,<2,2>}
(2) R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>};
(3) R={<1,1>,<1,-1>,<2,-2>,<3,-3>}。
4、对任意集合A,B，证明：若AA=BB，则B=A。
证明：
若B=，则BB=。从而AA =。故A=。从而B=A。
若B，则BB。从而AA。
对, <x,x>BB。因为AA=BB，则<x,x>A。从而xA。故BA。
同理可证，AB。
故B=A。
5、对任意集合A,B，证明：若A，AB=AC，则B=C。
证明：
若B=，则AB=。从而AC =。因为A，所以C=。即B=C。
若B，则AB。从而AC。
对,因为A，所以存在yA, 使<y,x>B。因为AB=AC，则<y,x>C。从而xC。故BC。
同理可证，CB。
故B=C。
6、设A={a,b}, B={c}。求下列集合：
(1) A{0,1}B； (2) B2A；
(3) (AB)2; (4) P(A)A。
解：
（1） A{0,1}B={<a,0,c>,<a,1,c>,<b,0,c>,<b,1,c>};
（2） B2A={<c,c,a>,<c,c,b>};
（3） (AB)2={<a,c,a,c>,<a,c,b,c>,<b,c,a,c>,<b,c,b,c>};
（4） P(A)A={<,a>,<,b>,<{a},a>,<{a},b>,<{b},a>,<{b},b>
,<A,a>,<A,b>}。
7、设全集U={a,b,c,d,e}, A={a,d}, B={a,b,c}, C={b,d}。求下列各集合：
（1）AB； （2）；（3）(A)C;
（4）P(A)-P(B); （5）(A-B)(B-C); （6）(AB)C;
解 ：
(1) AB={a}; (2) ={a,b,c,d,e};
(3) （A）C={b,d}; (4) P(A)-P(B)={{d},{a,d}};
(5) (A-B)(B-C)={d,c,a}; (6) (AB) C={b,d}。
8、设A,B,C是任意集合，证明或否定下列断言：
（1）若AB，且BC，则AC；
（2）若AB，且BC，则AC;
（3）若AB，且BC，则AC；
（4）若AB，且BC，则AC；
证明：
(1) 成立。
对xA, 因为AB，所以xB。又因为BC，所以xC。即AC。
(2) 不成立。反例如下：A={a}, B={a,b},C={a,b,c}。虽然AB，且BC，但AC。
(3) 不成立。反例如下：A={a}, B={{a},b},C={{{a},b},c}。虽然AB，且BC，但AC。
(4) 成立。因为AB, 且BC，所以AC。
9、A上的任一良序关系一定是A上的全序关系。
证明：
a，b∈A，则{a,b}是A的一个非空子集。≤是A上的良序关系，{a,b}有最小元。若最小元为a，则a≤b；否则b≤a。从而≤为A上的的全序关系。
10、若R和S都是非空集A上的等价关系，则RS是A上的等价关系。　
证明：
a∈A，因为R和S都是A上的等价关系，所以xRx且xSx。故xRSx。从而RS是自反的。
a,b∈A，aRSb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。故bRSa。从而RS是对称的。
a,b,c∈A，aRSb且bRSc，即aRb，aSb,bRc且bSc。因为R和S都是A上的等价关系，所以aRc且aSc。故aRSc。从而RS是传递的。
故RS是A上的等价关系。
11、设RA×A，则R自反 IAR。
证明：
xA，R是自反的，xRx。即<x,x>R，故IAR。
xA，IAR，<x,x>R。即xRx，故R是自反的。
12、设A是集合，RA×A，则R是对称的R＝R－1。
证明：
<x,y>R ，R是对称的，yRx。即<y,x>R，故<x,y>R_1 。从而RR-1。
反之<y,x>R-1,即<x,y>R 。R是对称的，yRx。即<y,x>R， R_1R。
故R=R-1。
x，yA，若<x,y>R ，即<y,x>R-1。 R=R-1，<y,x>R。即yRx，故R是对称的。
13、设A,B,C和D均是集合，RA×B，SB×C，TC×D，则
(1)　　R(ST)=(RS)(RT)；
(2)　　R(ST)(RS)(RT)；
证明：
（1）<x，z>R(ST)，则由合成关系的定义知yB，使得<x，y>R且<y，z>ST。从而<x，y>R且<y，z>S或<x，y>R且<y，z>T，即<x，z>RS或<x，z>RT。故<x，z>（RS）（RT） 。从而R(ST)（RS）（RT）。
同理可证（RS）（RT）R(ST)。
故R(ST)=（RS）（RT）。
(2) <x，z>R(ST)，则由合成关系的定义知yB，使得<x，y>R且<y，z>ST。从而<x，y>R且<y，z>S且<y，z>T，即<x，z>RS且<x，z>RT。故<x，z>（RS）（RT） 。从而R(ST)(RS）（RT）。
14、设〈A,≤〉为偏序集，BA，若B有最大(小)元、上(下)确界，则它们是惟一的。
证明：
设a,b都是B的最大元，则由最大元的定义ab，ba。是A上的偏序关系，a=b。即B如果有最大元则它是惟一的。
15、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：
1 1 1

2 3 2 3 2 3

解：
（1）R={<2,1>,<3,1>,<2,3>};MR=;它是反自反的、反对称的、传递的；
（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=;它是反自反的、对称的；
（3）R={<1,2>,<2,1>,<1,3>,<3,3>};MR=;它既不是自反的、反自反的、也不是对称的、反对称的、传递的。
16、设A={1,2,…,10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？
（1）B={{1,3,6},{2,8,10},{4,5,7}};
（2）C={{1,5,7},{2,4,8,9},{3,5,6,10}};
（3）D={{1,2,7},{3,5,10},{4,6,8},{9}}
解：
（1）和（2）都不是A的划分。
（3）是A的划分。其诱导的等价关系是
I{<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>,
<10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}。
17、R是A={1,2,3,4,5,6}上的等价关系，
R=I{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>}
求R诱导的划分。
解：
R诱导的划分为{{1,5},{2,4},{3,6}}。
18、A上的偏序关系的Hasse图如下。
(11) 下列哪些关系式成立：ab,ba,ce,ef,df,cf；
(12) 分别求出下列集合关于的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）：
(a) A; (b) {b,d}; (c) {b,e}; (d) {b,d,e}
a
e f

b d

c

解：
(1) ba,ce,df,cf成立；
(2) (a)的极大元为a,e,f,极小元为c;无最大元，c是最小元；
无上界，下界是c;无上确界，下确界是c。
(b)的极大元为b,d,极小元为b,d;无最大元和最小元；
上界是e，下界是c;上确界是e，下确界是c。
(c)的极大元为e,极小元为b;最大元是e，b是最小元；
上界是e，下界是b;上确界是e，下确界是b。
(d)的极大元为e,极小元为b,d;最大元是e，无最小元；
上界是e，下界是c;上确界是e，下确界是c。

（半群与群部分）
19、求循环群C12={e,a,a2,…,a11}中H={e,a4,a8}的所有右陪集。