??z((x,z)?R1?(x,z)?R2?(z,y)?R3)
??z((x,z)?R1?(z,y)?R3)??z((x,z)?R2?(z,y)?R3) ?(x,y)?R1R3?(x,y)?R2R3 ?(x,y)?R1R3?R2R3
所以得证(R1?R2)R3?R1R3?R2R3
(4 ) R3(R1?R2)?R3R1?R3R2。
证明：任取(x.,y),其中x,y?{a,b,c,d,e}，使得(x,y)?R3(R1?R2)。
??z((x,z)?R3?(z,y)?R1?R2) z?{a,b,c,d,e} ??z((x,z)?R3?(z,y)?R1?(z,y)?R2)
??z((x,z)?R3?(z,y)?R1)??z((x,z)?R3?(z,y)?R2) ?(x,y)?R3R1?(x,y)?R3R2 ?(x,y)?R3R1?R3R2
所以得证R3(R1?R2)?R3R1?R3R2。 (5) (R1?R2)R3?R1R3?R2R3。
证明：任取(x.,y),其中x,y?{a,b,c,d,e}，使得(x,y)?(R1?R2)R3。 ??z((x,z)?R1?R2?(z,y)?R3) z?{a,b,c,d,e} ??z((x,z)?R1?(x,z)?R2?(z,y)?R3)
??z((x,z)?R1?(z,y)?R3)??z((x,z)?R2?(z,y)?R3) ?(x,y)?R1R3?(x,y)?R2R3 ?(x,y)?R1R3?R2R3
所以得证(R1?R2)R3?R1R3?R2R3。 (6) R3(R1?R2)?R3R1?R3R2。
11
证明：任取(x.,y),其中x,y?{a,b,c,d,e}，使得(x,y)?R3(R1?R2)。
??z((x,z)?R3?(z,y)?R1?R2) z?{a,b,c,d,e} ??z((x,z)?R3?(z,y)?R1?(z,y)?R2)
??z((x,z)?R3?(z,y)?R1)??z((x,z)?R3?(z,y)?R2) ?(x,y)?R3R1?(x,y)?R3R2 ?(x,y)?R3R1?R3R2
所以得证R3(R1?R2)?R3R1?R3R2。
1.13 通常意义下的=是自然数集上的一个等价关系，请按照该等价关系给出自然数集的等价类 （02282075 冯蕊）
“=”关系将自然数集N分成无穷多个等价类：{0}，{1}，{2}，{3}，{4}，{5}，{6}，……
1.14.在什么样的假设下，人与人之间的“同乡关系”是等价关系。当“同乡关系”在给定的限定下成为等价关系时，它将所有的中国人分成什么样的等价类？
(吴玉涵 02282091) 答：假设出生在同一个省的关系为同乡关系。按照这样的同乡关系将中国人按照出生省份的不同划分出等价类。
1.16
?*上的二元关系RL 定义为：对任给的x,y??*，如果对于?z??*，
（1）对于?x?均有xz?L与yz?L，同时成立或者同时不成立，则xRLy。 (周期律 02282067)
证明：
?*
?*，故xRx，R
L
L
xz?L与xz?L显然是同时成立或同时不成立，对于?z?具有自反性。
对于?x,y??*，如果xRy, 故xz?L与yz?L同时成立或同时不成立，显
L
然故yz?L与xz?L同时成立或同时不成立，故yRLx, RL 具有对称性。
对于?x,y,p??*,如果xRy, yRp, 故xz?L与yz?L同时成立或同时不成
L
L
立，并且故yz?L与pz?L同时成立或同时不成立，故xz?L与pz?L同时成立或同时不
12
成立，故xRLp，故RL具有传递性。
综上，关系RL是在
?*上的等价关系。
（2）如果对于任给的x,y? 故对于?z? 对于?p??*，如果xRy，
L
?*，xz?L与yz?L同时成立或同时不成立，
L
?*,如果xzp?L,因为zp??*,又因为xRy, 故yzp?L，
因此，对于?p??*，?*,又因为xRy, 故yzp?L，
L
同理，可以证明如果xzp?L,因为zp?xzp?L与yzp?L同时成立或同时不成立，
故如果对于任给的x,y??*，如果xRy，则必有xzRyz。
L
L
综上，该关系的等价性和右不变性均得以证明。
1.17 设{0,1}*上的语言L={0n1m|n,m≥0},请给出{0,1}*关于L所确定的等价关系RL的等价类.
设L是Σ上的一个语言,Σ*上的二元关系RL定义为:对任给的x,y?Σ*,如果对于?z?Σ*,均有xz?L与yz?L同时成立或者同时不成立,则xRLy.
根据上述定义可知, {0,1}*关于L所确定的等价关系RL的等价类有三个.
(1) ?x,y?{0n1m|n≥0,m>0},都有?z?Σ*,均有xz?L与yz?L同时成立或者同
时不成立
(只有当z?{1n|n≥0}的时候,才同时成立,否则不成立)
(2) ?x,y?{0n1m|n≥0,m=0},都有?z?Σ*,均有xz?L与yz?L同时成立或者同
时不成立
(只有当z?{0n1m|n,m≥0}的时候,才同时成立,否则不成立)
(3) ?x,y?{0n1m|n,m≥0},都有?z?Σ*,均有xz?L与yz?L同时成立或者同时
不成立
(无论z取何值,都不同时成立)
三个等价类为{0n1m|n≥0,m>0}{0n1m|n≥0,m=0}和除此之外的{0,1}*上的字符
1.18 RL确定的{0，1}*的等价分类为：
[10]={x10y|x,y∈{0,1}*}∪{1|n≥1}
n
[0]={01|m-n=0}={0n1n|n≥0} [1]={01|m-n=1}
mn
mn
13
[2]={01|m-n=2} . . .
[h]={01|m-n=h}
. . .
其中，n，m均为非负整数。
1.19.给出下列对象的递归定义 (02282072 褚颖娜)
1． n个二元关系的合成
(1) R1R2={(a,c)|?(a,b)? R1且?(b,c) ? R2}
(2) R1R2??Rn = {(d,g)|?(d,e)?R1R2?? Rn-1且?(f,g) ? Rn } 2． 无向图中路的长度
在无向图Ｇ中，若两顶点v1,v2之间存在一条无向边，则v1,v2是Ｇ的一条长位１的路 若v1,v2??vn-1为一条长度为k-1的路，且vn-1,vn存在一条无向边，则v1，v2??vn-1,vn为Ｇ的一条长度为k的路 3． 有向图中路的长度
在有向图Ｇ中，若两顶点v1,v2之间存在一条有向边，则v1,v2是Ｇ的一条长位１的路 若v1,v2??vn-1为一条长度为k-1的路，且vn-1,vn存在一条有向边，则v1，v2??vn-1,vn为Ｇ的一条长度为k的路 4． n个集合的乘积
S1?S2={(a,b)|a? S1且b? S2}
S1? S2??Sn={(d,e)|d? S1? S2??Sn-1且e? Sn } 5． 字母a的n次幂
(1) a0=1; (2) an=an-1a; 6． 字符串x的倒序
若x为单字符，则x的倒序是它本身
若x的倒序为y, 若x后跟一字符a, 则xa的倒序为ay; 7． 字符串x的长度
若x为空串?，则|x|=0;
若字符串x的长度为k,其xa或ax的长度为k+1 8． 自然数
0为自然数，
如果x为自然数，则x+1为自然数
mn
mn
1.20.使用归纳法证明下列各题。 (吴玉涵 02282091)
14
1111n??????1?22?33?4n(n?1)n?1证明：(1)11（1）n=1时，?成立1?21?11111k（2）假设n=k时成立，即??????1?22?33?4k(k?1)k?111111当n?k?1时，??????1?22?33?4n(n?1)(n?1)(n?1?1)n1 =?n?1(n?1)(n?1?1)n(n?1?1)?1 =(n?1)(n?1?1)n?1 =（n?1）?1所以n?k?1时成立（3）由归纳原理，对任一n?N-?0?都成立
(2)当n?4时，2n?n2。证明：（1）当n=4时，2n?16?42成立（2）假设n=k时成立，即2k?k2当n?k?1时，2k+1?2?2k?2k222k2?（k+1）?k2?2k?1??k?1?2??k?1?2?????2由k?4知，2k2?（k+1）2所以，2k+1?（k?1），n?k?1时成立。
????（3）由归纳原理，?n?4?2n?n2
15