J.Korean Math.Soc.39(2002),No.4,pp.621–651
(f,2)–ROTATIONAL EXTENDED STEINER
TRIPLE SYSTEMS WITH f=2AND f=3
Chung Je Cho
Abstract.An extended Steiner triple system of order v,denoted
by EST S(v),is said to be(f,k)–rotational if it admits an automor-
phism consisting of exactly f?xed elements and k cycles of length
v?f k .In this paper,we obtain a necessary and su?cient condition
for the existence of(f,2)–rotational extended Steiner triple systems
with f=2and f=3.
1.Introduction
An extended Steiner triple system of order v,denoted EST S(v),is an ordered pair(V,B)where V is a set of v elements and B is a set of triples of(not necessarily distinct)elements of V,called blocks,such that every unordered pair of(not necessarily distinct)elements of V occurs in exactly one block of B.
In an EST S(v),there are three types of blocks of the forms
{a,a,a},{a,a,b},{a,b,c},
where a,b and c are distinct elements.If there is a block of the form {a,a,a},then such an element a is called an idempotent,but the element b which forms a block{b,b,c}with b=c is a nonidempotent.We will denote by EST S(v,ρ)an extended Steiner triple system of order v withρidempotents.In1972,Johnson and Mendelsohn[6]obtained a necessary condition for the existence of an EST S(v,ρ),and,in1978,Bennett and Mendelsohn[1]showed the necessary condition was also su?cient.
Received October15,2001.Revised March11,2002.
2000Mathematics Subject Classi?cation:05B05,05B07,05B10.
Key words and phrases:extended Steiner triple system,automorphism of an ex-tended Steiner triple system.
This research was supported by the KISTEP in2000-2001.
622Chung Je Cho
Theorem1.1[1,6].Let0≤ρ≤v.Then there exists an EST S(v,ρ) if and only if
(i)v≡0(mod3)andρ≡0(mod3),or
(ii)v≡1,2(mod3)andρ≡1(mod3),but
(iii)when v is even,ρ≤v
2,and
(iv)whenρ=v?1,v=2.
An automorphism of an EST S(v,ρ)(V,B)is a permutation of V which preserves the blocks of B.An EST S(v,ρ)is said to be(f,k)–rotational if it admits an automorphism consisting of exactly f?xed
elements and k cycles of length v?f
k .Solutions to the existence problem
of an(f,k)–rotational EST S(v,ρ)were?rst given when f=0,k=1, as the existence of cyclic extended triple systems[2],when f=0,k≥2, as that of k–regular extended triple systems[3]which were completely determined for k=2,3and partially for k=4,when f=1,k≥1,as that of k–rotational extended triple systems[2]which were completely determined for k=1,2and partially for k=3.
If(V,B)is an EST S(v,ρ)with an automorphismα,then the cyclic group generated byα,<α>,acts on the set V.So the whole blocks B are partitioned into disjoint orbits of blocks under the cyclic group <α>.We say that a set of blocks which are taken from each of the orbits exactly one is called a set of starter blocks for the system under the automorphismα.
An(A,k)-system is a set of ordered pairs{(a r,b r)|r=1,2,...,k} that partition the set{1,2,...,2k}with the property that b r?a r= r for r=1,2,...,k;and there exists an(A,k)-system if and only if k≡0or1(mod4)[8,9].A(B,k)-system is a set of ordered pairs {(a r,b r)|r=1,2,...,k}that partition the set{1,2,...,2k?1,2k+1} with the property that b r?a r=r for r=1,2,...,k;and there exists a (B,k)-system if and only if k≡2or3(mod4)[7,8].A(C,k)-system is a set of ordered pairs{(a r,b r)|r=1,2,...,k}that partition the set {1,2,...,k,k+2,...,2k+1}with the property that b r?a r=r for r= 1,2,...,k;and there exists a(C,k)-system if and only if k≡0or3(mod 4)[8].A(D,k)-system is a set of ordered pairs{(a r,b r)|r=1,2,...,k} that partition the set{1,2,...,k,k+2,...,2k,2k+2}with the property that b r?a r=r for r=1,2,...,k;and there exists a(D,k)-system if and only if k≡1or2(mod4)and k=1[8].
In this paper,we obtain a necessary and su?cient condition for the existence of(f,2)–rotational extended Steiner triple systems with f=2 and f=3.
(f,2)–rotational extended Steiner triple systems623
2.(2,2)–rotational extended Steiner triple systems
Suppose that there exists a(2,1)–rotational EST S(v,ρ)whose ele ment-set is V={∞1,∞2}∪Z v?2and with an automorphism
α=(∞1)(∞2)(01···v?3).
Then either{∞1,∞1,∞1}and{∞1,∞2,∞2},or{∞2,∞2,∞2}and {∞2,∞1,∞1}must be blocks.So there must exist starter blocks of the forms
{∞1,0,a}and{∞2,0,b}
for some a=b in Z v?2and then at least one of the pairs{∞1,0}and {∞2,0}occur twice.Thus there is no(2,1)–rotational extended Steiner triple systems.
In a(2,k)–rotational EST S(v,ρ),if{a,a,a}is a block then the length of its orbit is either1or v?2
k
;so we have the following lemma.
Lemma2.1.If there exists a(2,k)–rotational EST S(v,ρ),then
ρ=1or1+n·v?2 k
for n=0,1,...,k.
Remark2.2.If there exists a(2,2)–rotational EST S(v,ρ),then
ρ=1,v
2
,or v?1.
But ifρ=v?1,v must be2(by Theorem1.1);so ifρ=v?1then v=2andρ=1.
Lemma 2.3.A necessary condition for the existence of a(2,2)–rotational EST S(v,ρ)is
(i)ρ=1and v≡2,4(mod6),or
(ii)ρ=v
2
and v≡0,2(mod6).
Proof.(i)Ifρ=1,then,by Theorem1.1,v≡1or2(mod3).But
v?2 2must be an integer.Thus v satis?es both v≡1,2(mod3)and
v≡0(mod2)and hence v≡2or4(mod6).
(ii)Ifρ=v
2then,by Theorem1.1,v
2
≡0or1(mod3)and hence
v≡0or2(mod6).
624Chung Je Cho
Now,we will construct(2,2)–rotational EST S(v,ρ)s.We assume that our(2,2)–rotational EST S(v,ρ)s have the element-set,
V={∞1,∞2}∪
Z v?2
2
×{1,2}
,
and the corresponding automorphism is
α=(∞1)(∞2)
0111···
v?2
2
?1
1
0212···
v?2
2
?1
2
,
where we write for brevity x i instead of(x,i).
Lemma2.4.There exists a(2,2)–rotational EST S(v,1)for v=8 and20.
Proof.If v=8,then the following triples
{∞1,∞1,∞1},{∞1,∞2∞2},{∞1,01,02},
{∞2,01,12},{01,01,22},{01,11,21},{02,02,12}
form a set of starter blocks for a(2,2)–rotational EST S(8,1).
If v=20,the following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},
{01,11,31},{01,01,41},{02,02,01},
{02,12,21},{02,22,71},{02,42,81}
{∞1,02,61},{∞2,02,31},{02,32,62}
form a set of starter blocks of a(2,2)–rotational EST S(20,1).
Lemma2.5.If v≡8(mod12),then there exists a(2,2)–rotational EST S(v,1).
Proof.Let v=12t+8=2(6t+3)+2and let t≥0be an arbitrary integer.The cases t=0and1have been treated in Lemma2.4.
If t≥2,then the following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},
{01,r1,(b r+t)1},r=1,2,...,t,
(f,2)–rotational extended Steiner triple systems625 where{(a r,b r)|r=1,2,...,t}is a(C,t)-system if t≡0,3(mod4),or a(D,t)-system if t≡1,2(mod4),and
{02,(2t+1)2,(4t+2)2},{02,02,(3t+1)2},
{01,(2t+1)1,(?c2t+1)2},
{∞1,02,(c3t+1)1},{∞2,02,(d3t+1)1},
{02,r2,(d r)1},r=1,2,...,2t,2t+2,...,3t,
where{(c r,d r)|r=1,2,...,3t+1}is an(A,3t+1)-system if t≡0,1 (mod4),or a(B,3t+1)-system if t≡2,3(mod4),and6t+3should be read as0,and
{01,01,02}if t≡0or1(mod4),or
{(6t+2)1,(6t+2)1,02}if t≡2or3(mod4),
form a set of starter blocks for a(2,2)–rotational EST S(v,1).
Lemma2.6.If v≡4(mod12),then there exists a(2,2)–rotational EST S(v,1).
Proof.Let v=12t+4=2(6t+1)+2and let t≥0be an arbitrary integer.If t=0,the following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{∞1,01,02},{∞2,01,01},{∞2,02,02} form a set of starter blocks for a(2,2)–rotational EST S(4,1).
If t≥1,then the following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},
{01,r1,(b r+t)1},r=1,2,...,t,
where{(a r,b r)|r=1,2,...,t}is an(A,t)-system if t≡0,1(mod4),or a(B,t)-system if t≡2,3(mod4),and
{02,02,(3t)2},
{∞1,02,(c3t)1},{∞2,02,(d3t)1},
{02,r2,(d r)1},r=1,2,...,3t?1,
626Chung Je Cho
where{(c r,d r)|r=1,2,...,3t}is an(A,3t)-system if t≡0,3(mod4), or a(B,3t)-system if t≡1,2(mod4),and6t+1should be read as0, and
{01,01,02}if t≡0,3(mod4),or
{(6t)1,(6t)1,02}if t≡1,2(mod4),
form a set of starter blocks for a(2,2)–rotational EST S(v,1).
Lemma2.7.If v≡2or26(mod48),then there exists a(2,2)–rotational EST S(v,1).
Proof.Let v=12t+2and let t≡0(mod2).If t=0,then the triples
{∞1,∞1,∞1},{∞1,∞2,∞2}
are starter blocks for a(2,2)–rotational EST S(2,1).
If t≥2is an even integer,then the following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{∞2,01,02},
{∞1,01,(3t)1},{∞1,02,(3t)2},{01,(2t)1,(4t)1},
and
01,01,
5t
2
1
,
01,(2r?1)1,
t
2
+t?1+r
1
,r=1,2,...,
t
2
,
{01,(2r)1,(3t?r)1},r=1,2,...,t
2
?1,
{02,r2,(b r)1},r=1,2,...,3t?1,
where{(a r,b r)|r=1,2,...,3t?1}is an(A,3t?1)-system if t≡2(mod 4),or a(B,3t?1)-system if t≡0(mod4),and
{02,02,(6t?1)1}if t≡2(mod4),or
{02,02,(6t?2)1}if t≡0(mod4),
form a set of starter blocks for a(2,2)–rotational EST S(v,1).
(f,2)–rotational extended Steiner triple systems627 Lemma2.8.If v≡14or38(mod48),then there exists a(2,2)–rotational EST S(v,1).
Proof.Let v=12t+2and let t≡1(mod2).Then the following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{∞2,01,02},
{∞1,01,(3t)1},{∞1,02,(3t)2},{01,(2t)1,(4t)1},
and
01,01,
3t?1
2
1
,
01,(2r)1,
t+1
2
+t?1+r
1
,r=1,2,...,
t?1
2
,
{01,(2r?1)1,(3t?r)1},r=1,2,...,t?1 2
,
{02,r2,(b r)1},r=1,2,...,3t?1,
where{(a r,b r)|r=1,2,...,3t?1}is an(A,3t?1)-system if t≡3(mod 4),or a(B,3t?1)-system if t≡1(mod4),and
{02,02,(6t?1)1}if t≡3(mod4),or
{02,02,(6t?2)1}if t≡1(mod4),
form a set of starter blocks for a(2,2)–rotational EST S(v,1).
Lemma2.9.There exists a(2,2)–rotational EST S(10,1).
Proof.The following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{∞1,01,21},{∞1,02,22},
{∞2,01,02},{01,01,11},{02,12,21},{02,02,31}
form a set of starter blocks of a(2,2)–rotational EST S(10,1).
Lemma2.10.If v≡10(mod12),then there exists a(2,2)–rotational EST S(v,1).
628Chung Je Cho
Proof.Let v=12t+10and let t be any nonnegative integer.The case t=0has been treated in Lemma2.9.If t≥1,then the following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{∞2,01,02},
{∞1,01,(3t+2)1},{∞1,02,(3t+2)2},
and
{01,01,(3t+1)1}if t≡0,1(mod4),or
{01,01,(3t)1}if t≡2,3(mod4),
and
{01,r1,(b r+t)1},r=1,2,...,t,
where{(a r,b r)|r=1,2,...,t}is an(A,t)-system if t≡0,1(mod4),or a(B,t)-system if t≡2,3(mod4),and
{02,r2,(b r)1},r=1,2,...,3t+1,
where{(a r,b r)|r=1,2,...,3t+1}is an(A,3t+1)-system if t≡0,1 (mod4),or a(B,3t+1)-system if t≡2,3(mod4),and
{02,02,(6t+3)1}if t≡0,1(mod4),or
{02,02,(6t+2)1}if t≡2,3(mod4),
form a set of starter blocks for a(2,2)–rotational EST S(v,1).
Lemmas2.3,2.5,2.6,2.7,2.8and2.10together yield the following theorem.
Theorem2.11.There exists a(2,2)–rotational EST S(v,1)if and only if v≡2or4(mod6).
Lemma2.12.There exists a(2,2)–rotational EST S(8,4)
(f,2)–rotational extended Steiner triple systems 629
Proof.The following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{01,01,01},{01,22,22},{01,11,21},{∞1,01,02},
{∞2,01,12},
{02,12,22}
form a set of starter blocks of a (2,2)–rotational EST S (8,4).
Lemma 2.13.There exists no (2,2)–rotational EST S (20,10)
Proof.If there exists a (2,2)–rotational EST S (20,10),by counting of the number of orbits,there must exist two orbits of length 3.Con-sequently,there exists a cyclic Steiner triple system of order 9,which is non-existing system. Lemma 2.14.If v ≡8(mod 12)and v =20,then there exists a (2,2)–rotational EST S v,v 2 .
Proof.Let v =12t +8=2(6t +3)+2.The case t =0has been treated in Lemma 2.12.By Lemma 2.13,t =1.Let t ≥2be an integer.Then the following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{01,01,01}
{01,r 1,(b r +t )1},
r =1,2,...,t,
where {(a r ,b r )|r =1,2,...,t }is a (C,t )-system if t ≡0,3(mod 4),or a (D,t )-system if t ≡1,2(mod 4),and
{01,(2t +1)1,(4t +2)1},{∞1,02,(c 2t +1)1},{∞2,02,(d 2t +1)1},{02,(2t +1)2,(4t +2)2},
{{02,r 2,(d r )1},
r =1,2,...,2t,2t +2,...,3t +1},
where {(c r ,d r )|r =1,2,...,3t +1}is an (A,3t +1)-system if t ≡0or 1(mod 4),or a (B,3t +1)-system if t ≡2or 3(mod 4),and 6t +3should be read as 0,and
{01,02,02}if t ≡0,1(mod 4),or {(6t +2)1,02,02}
if t ≡2,3(mod 4),
form a set of starter blocks for a (2,2)–rotational EST S v,v 2
.
630Chung Je Cho
Lemma 2.15.There exists no (2,2)–rotational EST S (12,6).Proof.Suppose that there exists a (2,2)–rotational EST S (12,6).Then we may say that it has starter blocks of the forms
{∞1,∞1,∞1},{∞1,∞2,∞2},{a 1,a 1,a 1},{∞1,a 1,b 2},{∞2,x 1,y 2},{u 1,v 1,w 2},{a 1,b 1,c 2},{x 2,y 2,z 1},
{r 2,s 2,t 1},
{a 2,a 2,x 1}.
We see that we need 11orbits of the form {a 1,b 2}.But there are only 5such orbits. Lemma 2.16.If v ≡0(mod 12)and v =12,then there is a (2,2)–rotational EST S v,v 2 .
Proof.Let v =12t =2(6t ?1)+2.By Lemma 2.15,t =1.Let t ≥2be an integer.Then the following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{01,01,01}
and
{02,12,(3t ?1)2}if t ≡1,2(mod 4),or {02,22,(3t ?1)2}if t ≡0,3(mod 4)
and
{01,r 1,(b r +t ?1)1},r =1,2,...,t ?1,
where {(a r ,b r )|r =1,2,...,t ?1}is an (A,t ?1)-system if t ≡1,2(mod 4),or a (B,t ?1)-system if t ≡0,3(mod 4),and let {(c r ,d r )|r =1,2,...,3t ?1}be an (A,3t ?1)-system if t ≡2,3(mod 4),or a (B,3t ?1)-system if t ≡0,1(mod 4)(if d r =6t ?1then d r should be read as 0),then
{01,(3t ?1)1,(d 3t ?1)2}and
{01,(3t ?2)1,(d 3t ?2)2}if t ≡1,2(mod 4),or {01,(3t ?3)1,(d 3t ?3)2}
if t ≡0,3(mod 4)
(f,2)–rotational extended Steiner triple systems 631
and
{02,r 2,(?c r )1},r =2,3,...,3t ?3
if t ≡2,3(mod 4),or
r =1,3,...,3t ?4,3t ?2if t ≡0,1(mod 4)
and
{∞2,01,02,},{01,(c 1)2,(c 1)2},{∞1,01,(d 1)2}if t ≡0,1(mod 4)or
{∞2,01,(6t ?2)2,},{01,(c 2)2,(c 2)2},{∞1,01,(d 2)2}if t ≡2,3(mod 4),form a set of starter blocks for a (2,2)–rotational EST S v,v 2
.
Lemma 2.17.There exists a (2,2)–rotational EST S (6,3).Proof.The following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{01,01,01},{01,12,12},{∞1,01,11},
{∞1,02,12},
{∞2,01,02}
form a set of starter blocks of a (2,2)–rotational EST S (6,3).
Lemma 2.18.If v ≡6or 18(mod 48),then there exists a (2,2)–
rotational EST S v,v
2 .
Proof.Let v =12t +6=2(6t +2)+2and let t ≡0or 1(mod 4).The case t =0has been treated in Lemma 2.16.Let t ≥2.Then the following triples
{∞1,∞1,∞1},
{∞1,∞2,∞2},
{01,01,01},
{∞1,01,(3t +1)1},{∞1,02,(3t +1)2},{∞2,01,02},
and
{01,r 1,(b r +t )1},
r =1,2,...,t,
632Chung Je Cho
where{(a r,b r)|r=1,2,...,t}is an(A,t)-system,and
{02,r2,(b r)1},r=1,2,...,3t,
where{(a r,b r)|r=1,2,...,3t}is an(A,3t)-system if t≡0(mod4),or a(B,3t)-system if t≡1(mod4),and
{02,02,(6t+1)1}if t≡0(mod4),or
{02,02,(6t)1}if t≡1(mod4),
form a set of starter blocks for a(2,2)–rotational EST S
v,v
2
.
Definition2.19.A(R1,3k)-system is a set{(a r,b r)|r=1,2,...,3k} such that
(i){a r,b r|r=1,2,...,3k}=Z6k+2\{0,9k+4
2},and
(ii)b r?a r=r+1for r=1,2,...,3k?1and b3k?a3k=3k?2. Lemma2.20.If k≡2(mod4),then there exists a(R1,3k)-system. Proof.If k≡2(mod4),form ordered pairs
(r,3k+2?r),r=1,2, (3)
2,
(3k+1+2r,6k?2r),r=1,2,...,3k?6
4,
(3k+2+2r,6k+3?2r),r=1,2,...,3k?2
4,
3k+2
2,9k
2
,(3k+2,6k).
Definition2.21.A(R2,3k)-system is a set{(a r,b r)|r=1,2,...,3k} such that
(i){a r,b r|r=1,2,...,3k}=Z6k+2\{0,9k?3
2},and
(ii)b r?a r=r+1for r=1,2,...,3k?1and b3k?a3k=3k?3.
Lemma 2.22.If k≡3(mod4)and k=3,then there exists a (R2,3k)-system.
Proof.Case1.k≡7(mod8):
(r,3k+1?r),r=1,2,...,3k?1
2 (3k+8+4r,6k?4r),r=0,1,...,3k?13
8,
3k+1
2,9k+1
2
,(6k+1,3k+4),
9k?1
2
,9k+5
2
.
(3k+r,6k?r),r=1,2,3,5,6,7,9,10,11,13,...,3k?7
2.
Case2.k≡3(mod8)and k=3:
(f,2)–rotational extended Steiner triple systems 633
(r,3k +1?r ),r =1,2,...,3k ?1
2,
(3k +8+4r,6k ?4r ),r =0,1,...,3k ?17
8, 3k +12,9k +12
,(6k +1,3k +4), 9k +32,9k +92
,(3k +r,6k ?r ),r =1,2,3,5,6,7,9,10,11,13,...,3k ?5
2
. Lemma 2.23.There exists a (2,2)-rotational EST S (42,21).Proof.The following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{01,01,01},{∞1,01,71},{∞1,02,72},{∞2,01,02},
{01,11,41},{01,21,71},{01,61,82},{01,81,92},{01,91,142},{02,12,92},{01,162,162},{02,22,51},{02,32,171},{02,42,131},{02,52,71},
{02,62,161},
{02,72,81},
form a set of starter blocks of a (2,2)-rotational EST S (42,21).
Lemma 2.24.If v ≡30or 42(mod 48),then there exists a (2,2)–
rotational EST S v,v 2 .Proof.Let v =12k +6=2(6k +2)+2and let k ≡2or 3(mod 4).The case k =3has been treated in Lemma 2.23.Let k =3.Then the following triples
{∞1,∞1,∞1},
{∞1,∞2,∞2},
{01,01,01},
{∞1,01,(3k +1)1},{∞1,02,(3k +1)2},{∞2,01,02},
and
{01,r 1,(b r +k ?1)1},r =1,2,...,k ?1,
where {(a r ,b r )|r =1,2,...,k ?1}is an (A,k ?1)-system if k ≡2(mod 4),or a (B,k ?1)-system if k ≡3(mod 4),and
{01,(3k ?2)1,(b 3k )2}if k ≡2(mod 4),or {01,(3k ?3)1,(b 3k )2}
if k ≡3(mod 4)
634Chung Je Cho
and
{02,12,(3k)2},
{01,(3k?1)1,(b3k?2)2},{01,(3k)1,(b3k?1)2},
{02,(r+1)2,(?a r)1},r=1,2,...,3k?3,
where{(a r,b r)|r=1,2,...,3k}is an(R1,3k)-system if k≡2(mod4), or a(R2,3k)-system if k≡3(mod4),and
01,
9k+4
2
2
,
9k+4
2
2
if k≡2(mod4),or
01,
9k?3
2
2
,
9k?3
2
2
if k≡3(mod4),
form a set of starter blocks for a(2,2)–rotational EST S
v,v
2
.
Definition2.25.A(S1,k?1)-system is a set{(a r,b r)|r=1,2,..., k?1}such that
(i){a r,b r|r=1,2,...,k?1}={1,2,...,k,k+2,...,2k?1},and
(ii)b r?a r=r for r=1,2,...,k?1.
Lemma2.26.If k≡2or3(mod4),then there exists a(S1,k?1)-system.
Proof.Case1.k=4t+2.
t=0:(1,2).
t=1:(10,11),(2,4),(6,9),(1,5),(3,8).
t≥2:
(r,4t+2?r),r=1,2,...,2t,
(4t+3+r,8t+4?r),r=1,2,...,t?1,
(5t+2+r,7t+3?r),r=1,2,...,t?1,
(2t+1,6t+2),(4t+2,6t+3),(7t+3,7t+4).
Case2.k=4t+3.
t=0:(1,2),(3,5).
t=1:(11,12),(3,5),(10,13),(2,6),(4,9),(1,7).
t≥2:
(r,4t+4?r),r=1,2,...,2t+1,
(f,2)–rotational extended Steiner triple systems 635
(4t +4+r,8t +5?r ),r =1,2,...,t ?1,(5t +3+r,7t +4?r ),r =1,2,...,t ?1,
(2t +2,6t +3),(6t +4,8t +5),(7t +4,7t +5).
Definition 2.27.A (S 2,k ?1)-system is a set {(a r ,b r )|r =1,2,...,k ?1}such that
(i){a r ,b r |r =1,2,...,k ?1}={1,2,...,k,k +2,...,2k ?2,2k },and
(ii)b r ?a r =r for r =1,2,...,k ?1.Lemma 2.28.If k ≡0or 1(mod 4),then there exists a (S 2,k ?1)-system.
Proof.Case 1.k =4t .
t =1:(2,3),(6,8),(1,4).
t =2:(1,2),(14,16),(3,6),(8,12),(5,10),(7,13),(4,11).t ≥3:
(r,4t +1?r ),r =1,2,...,2t ?1,(4t +1+r,8t ?3?r ),r =1,2,...,t ?2,(5t ?1+r,7t ?3?r ),r =1,2,...,t ?3,
(2t,6t ?2),(2t +1,6t ?3),(6t ?1,8t ?3),(8t ?2,8t ),(7t ?3,7t ?2).Case 2.k =4t +1.
t =1:(2,3),(8,10),(4,7),(1,5).t ≥2:
(r,4t +2?r ),r =1,2,...,2t ,(4t +4+r,8t +1?r ),r =1,2,...,2t ?2,(2t +1,4t +4),(4t +3,8t +2). Definition 2.29.A (S 3,3k )-system is a set {(a r ,b r )|r =1,2,...,
2k ?1,2k +1,...,3k }such that
(i){a r ,b r |r =1,2,...,2k ?1,2k +1,...,3k }
=
1,2,...3k 2,
3k +4
2
...,6k ?1 ,and (ii)b r ?a r =r for r =1,2,...,2k ?1,2k +1,...,3k ?1,and
b 3k ?a 3k =3k ?1.
636Chung Je Cho
Lemma 2.30.If k ≡2(mod 4),then there exists a (S 3,3k )-system.Proof.If k ≡2(mod 4),form ordered pairs
(r,3k +1?r ),r =1,2,...,3k ?2
2,
(3k +r,6k ?r ),r =1,2,...,k ?2
2(k >2), 9k ?22?r,9k ?2
2+r ,r =1,2,...,k ?1, 3k 2,9k ?22 , 11k ?22
,11k 2
.
Definition 2.31.A (S 4,3k )-system is a set {(a r ,b r )|r =1,2,...,
2k ?1,2k +1,...,3k }such that
(i){a r ,b r |r =1,2,...,2k ?1,2k +1,...,3k }
= 1,2,...3k ?12,3k +3
2
...,6k ?1
,and
(ii)b r ?a r =r for r =1,2,...,2k ?1,2k +1,...,3k ?1,and
b 3k ?a 3k =3k ?1.
Lemma 2.32.If k ≡3(mod 4),then there exists a (S 4,3k )-system.Proof.If k ≡3(mod 4),form ordered pairs
(r,3k ?r ),r =1,2,...,3k ?3
2,
(3k +r,6k ?1?r ),r =1,2,...,k ?3
2(k >3), 9k ?32
?r,9k ?3
2+r ,r =1,2,...,k ?1,
3k ?12,9k ?3
2 ,(3k,6k ?1), 11k ?32
,11k ?12 .
Definition 2.33.A (S 5,3k )-system is a set {(a r ,b r )|r =1,2,...,
2k ?1,2k +1,...,3k }such that
(i){a r ,b r |r =1,2,...,2k ?1,2k +1,...,3k }
= 1,2,...,3k ?22,3k +2
2
...,6k ?1
,and
(ii)b r ?a r =r for r =1,2,...,2k ?1,2k +1,...,3k ?1,and
b 3k ?a 3k =3k ?2.
Lemma 2.34.If k ≡0(mod 4),then there exists a (S 5,3k )-system.
(f,2)–rotational extended Steiner triple systems 637
Proof.If k ≡0(mod 4),form ordered pairs
(r,3k +1?r ),r =1,2,...,3k ?2
2,
(3k +r,6k ?1?r ),r =1,2,...,k ?4
2(k >4), 9k ?22?r,9k ?2
2+r ,r =1,2,...,k ?1, 3k +22,9k ?22
,(3k +1,6k ?1), 11k ?22
,11k 2 .
Definition 2.35.A (S 6,3k )-system is a set {(a r ,b r )|r =1,2,...,
2k ?1,2k +1,...,3k }such that
(i){a r ,b r |r =1,2,...,2k ?1,2k +1,...,3k }
= 1,2,...3k ?32,3k +1
2
,...,6k ?1
,and
(ii)b r ?a r =r for r =1,2,...,2k ?1,2k +1,...,3k ?1,and
b 3k ?a 3k =3k ?2.
Lemma 2.36.If k ≡1(mod 4),then there exists a (S 6,3k )-system.Proof.If k ≡1(mod 4),form ordered pairs
(r,3k ?r ),r =1,2,...,3k ?3
2(k >1),
(3k ?1+r,6k ?1?r ),r =1,2,...,k ?1
2(k >1), 9k ?32?r,9k ?3
2+r ,r =1,2,...,k ?1(k >1), 3k +12,9k ?32 , 11k ?32
,11k ?12
.
Lemma 2.37.If v ≡2(mod 12),then there exists a (2,2)–rotational
EST S (v,v 2).Proof.Let v =12k +2and let k be a nonnegative integer.The case k =0is trivial.If k ≥1,then the following triples
{∞1,∞1,∞1},{∞1,∞2,∞2},{01,01,01},{∞2,01,02},{∞1,01,(3k )1},{∞1,02,(3k )2},{01,(2k )1,(4k )1},
{02,(2k )2,(4k )2},
{01,r 1,(b r +k ?1)1},r =1,2,...,k ?1,
638Chung Je Cho
where {(a r ,b r )|r =1,2,...,k ?1}is either a (S 1,k ?1)-system if k ≡2or 3(mod 4),or a (S 2,k ?1)-system if k ≡0or 1(mod 4),and
02,02,
3k
2 1
if k ≡0(mod 4),or 02,02,
3k ?1
2
1
if k ≡1(mod 4),or 02,02,
3k +2
2
1
if k ≡2(mod 4),or 02,02,
3k +1
2 1
if k ≡3(mod 4)
and
{02,(a 3k )1,(b 3k )1},{02,r 2,(b r )1},
r =1,2,...,2k ?1,2k +1,...,3k ?1,
where {(a r ,b r )|r =1,2,...,2k ?1,2k +1,...,3k }is a (S t ,3k )-system
such that
t =3if k ≡2(mod 4),or t =4if k ≡3(mod 4),or t =5if k ≡0(mod 4),or t =6
if k ≡1(mod 4),
form a set of starter blocks of a (2,2)–rotational EST S
v,v 2 .
Lemmas 2.3,2.12through 2.37together yield the following theorem.
Theorem 2.38.There exists a (2,2)–rotational EST S v,v 2
if and only if v ≡0or 2(mod 6)and v =12,20.Now,we can conclude the following theorem.
Theorem 2.39.There exists a (2,2)–rotational EST S (v,ρ)if and only if
(i)ρ=1and v ≡2,4(mod 6),or (ii)ρ=v 2and v ≡0,2(mod 6)and v =12,20.
(f,2)–rotational extended Steiner triple systems 639
3.(3,2)-rotational extended Steiner triple systems
As before (2,2)–rotational EST S (v,ρ)s,we assume that our (3,2)–rotational EST S (v,ρ)s have the element-set
V ={∞1,∞2,∞3}∪(Z v ?32
×{1,2})
and the corresponding automorphism is
α=(∞1)(∞2)(∞3) 0111··· v ?32?1 1 0212··· v ?3
2?1 2
,
where we also write for brevity x i instead of (x,i ).
By an elementary argument,we have the following necessary condi-tion for the existence of a (3,k )–rotational EST S (v,ρ).
Lemma 3.1.If there exists a (3,k )–rotational EST S (v,ρ),then
ρ=0or 3+n ·
v ?3
k
for each n =0,1,···,k .
Remark 3.2.If there exists a (3,2)–rotational EST S (v,ρ),then ρis
0,
3,
v +32
or v.
Lemma 3.3.A necessary condition for the existence of a (3,2)–rotational EST S (v,ρ)is (i)ρ=v and v ≡1,3(mod 6),v =13,21,or
(ii)ρ=v +3
2and v ≡3,5(mod 6),v =5,or (iii)ρ=0,3and v ≡3(mod 6).Proof.(i)This follows from the existence of a (3,2)–rotational Steiner triple systems [4,5].(ii)If ρ=v +32,then
v +3
2
≡0or 1(mod 3)since the existence of EST S (v,ρ)implies ρ=0or 1(mod 3).Thus v ≡3or 5(mod 6).If v =5,then ρ=5+32=4=v ?1;so v must be 2.
(iii)If ρ=0or 3,then v ≡0(mod 3).But v ?3
2is an integer;so v ≡3(mod 6). The following theorem is a consequence of the existence of a (3,2)–rotational Steiner triple system of order v [4,5].
640Chung Je Cho
Theorem 3.4.There exists a(3,2)–rotational EST S(v,v)if and only if v≡1or3(mod6),v=13,21.
Lemma3.5.There exists a(3,2)–rotational EST S(9,3).
Proof.The following triples
{∞1,∞2,∞3},{01,01,11},{02,02.12},
{∞1,∞1,∞1},{∞2,∞2,∞2},{∞3,∞3,∞3},
{∞1,01,02},{∞2,01,12},{∞3,01,22}
form a set of starter blocks of a(3,2)–rotational EST S(9,3).
Lemma3.6.If v≡9(mod12),then there exists a(3,2)–rotational EST S(v,3).
Proof.Let v=12t+9=2(6t+3)+3and let t be a nonnegative integer.The case t=0has been treated in Lemma3.5.Let t≥1.Then the following triples
{∞1,∞2,∞3},{∞i,∞i,∞i},i=1,2,3,
and if t≡0,1(mod4),then
{∞1,01,02},{0i,0i,(3t+1)i},i=1,2,
or if t≡2,3(mod4),then
{∞1,(6t+2)1,02},{01,01,(3t)1},{02,02,(3t+1)2},
and
{01,r1,(b r+t)1},r=1,2,...,t,
where{(a r,b r)|r=1,2,...,t}is an(A,t)-system if t≡0,1(mod4)or a(B,t)-system if t≡2,3(mod4),and
{02,r2,(d r)1},r=1,2, (3)
{∞2,02,(d3t+1)1},{∞3,02,(c3t+1)1},
where{(c r,d r)|r=1,2,...,3t+1}is an(A,3t+1)-system if t≡0, 1(mod4)or a(B,3t+1)-system if t≡2,3(mod4),and here6t+3 should be regarded as0,form a set of starter blocks for a(3,2)–rotational EST S(v,3).
集合与关系《应用离散数学》 第3章 21世纪高等教育计算机规划教材
目录 3.1 集合及其运算 3.2 二元关系及其运算3.3 二元关系的性质与闭包3.4 等价关系与划分 3.5 偏序关系与拓扑排序3.6 函 数 3.7 集合的等势与基数3.8 多元关系及其应用
集合是现代数学中最重要的基本概念之一，数学概念的建立由于使用了集合而变得完善并且统一起来。集合论已成为现代各个数学分支的基础，同时还渗透到各个科学技术领域，成为不可缺少的数学工具和表达语言。对于计算机科学工作者来说，集合论也是必备的基础知识，它在开关理论、形式语言、编译原理等领域中有着广泛的应用。 本章首先介绍集合及其运算，然后介绍二元关系及其关系矩阵和关系图，二元关系的运算、二元关系的性质、二元关系的闭包，等价关系与划分、函数，最后介绍多元关系及其在数据库中的应用等。
3.1 集合及其运算 3.1.1 基本概念 集合是数学中最基本的概念之一，如同几何中的点、线、面等概念一样，是不能用其他概念精确定义的原始概念。集合是什么呢？直观地说，把一些东西汇集到一起组成一个整体就叫做集合，而这些东西就是这个集合的元素或叫成员。 例3.1 （1）一个班级里的全体学生构成一个集合。 （2）平面上的所有点构成一个集合。 （3）方程 的实数解构成一个集合。 （4）自然数的全体（包含0）构成一个集合，用N表示。 （5）整数的全体构成一个集合，用Z表示。 （6）有理数的全体构成一个集合，用Q表示。 （7）实数的全体构成一个集合，用R表示。
（8）复数的全体构成一个集合，用C表示。 （9）正整数集合Z+，正有理数集合Q+，正实数集合R+。（10）非零整数集合Z*，非零有理数集合Q*，非零实数集合R*。（11）所有n 阶(n≥2)实矩阵构成一个集合，用M n(R)表示，即
离散数学知识点总结 一、各章复习要求与重点 第一章 集 合 [复习知识点] 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图 3、序偶与迪卡尔积 本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求] 1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 [本章重点习题] P5~6，4、6； P14~15，3、6、7； P20，5、7。 [疑难解析] 1、集合的概念 因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。 2、集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 [例题分析] 例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。 解 }}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A }}2,1{},2{},1{,{)(φρ=B 于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ
1.【实验目的】 对称： 通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法 自反： 通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 2.【实验内容】 已知关系R 由关系矩阵M 给出，要求判断由M 表示的这个关系是否为对称关 系。假定R 的关系矩阵为：?????? ? ??=1234210330124321M 3.【实验要求】 C 语言编程实现 4.【算法描述】 对称： 从给定的关系矩阵来判断关系R 是否为对称是很容易的。若M （R 的关系矩阵）为对称矩阵，则R 是对称关系；若M 为反对称矩阵，则R 是反对称关系。因为R 为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。 算法实现： （1） 输入关系矩阵M （M 为n 阶方阵）； （2） 判断对称性，对于i=2，3，….，n ；j=1，2,……，i-1，若存在m ij =m ji ， 则R 是对称的； （3） 判断反对称性； （4） 判断既是对称的又是反对称的； （5） 判断既不是对称的又不是反对称的； （6） 输出判断结果。
自反： 从给定的关系矩阵来断判关系R是否为自反是很容易的。若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。 算法实现 （1）输入关系矩阵M（M为n阶方阵）。 （2）判断自反性，对于i=1，2，….，n；若存在m =0，则R不是自反 ii =1，则R是自反的；否则R既不是自反关系也不是的；若存在m ii 反自反关系。 （3）输出判断结果。 源代码 #include
一、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) 证明：因为 x∈(A∪B)－C?x∈(A∪B)－C ?x∈(A∪B)∧x?C ?(x∈A∨x∈B)∧x?C ?(x∈A∧x?C)∨(x∈B∧x?C) ?x∈(A－C)∨x∈(B－C) ?x∈(A－C)∪(B－C) 所以，(A∪B)－C＝(A－C)∪(B－C)。 二、设R={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图。 解：r(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R2=R5={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} t(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>， <5，5>} 三、证明等价关系 设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得
离散数学作业1_集合与关系 1. 设A、B、C为任意三个集合，判断下列命题的真与假。如命题为真，则证明之；否则，举反例说明。 （1）若A?C=B?C，则A=B(假命题) （2）若A?C=B?C ，则A=B(假命题) （3）若A?C=B?C 且A?C=B?C ，则A=B (真命题,参考ppt 1.2节例8) 2.证明A-B=A∩~B. 证明思路：任取x∈A-B?……? x∈A∩~B 证明：任取x∈A-B?x∈A且x/∈B（根据相对补的定义） ? x∈A且x∈~B(根据绝对补的定义) ? x∈A∩~B 3. 设A={1，2，3，4，5，6},下面各式定义的R都是A上的二元关系。试分别以序偶、关系矩阵、关系图三种形式分别写出R。 (1) R={
>,<6,1>,<6,2>,<6,3>,<6,6>} (3) R={<1,2>,<1,3>,<2,1>,<2,3>,<2,4>,<3,2>,<3,4>,<3,1>,<3,5>,<4,3 >,<4,5>,<4,2>,<4,6>,<5,4>,<5,6>,<5,3>,<6,5>,<6,4>} (4) 质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。 100以内的质数有2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，在100内共有25个质数。 注：1既不是质数也不是合数。因为它的约数有且只有1这一个约数。 R={<2,1>,<3,1>,<4,2>,<5,1>,<6,2>,<6,3>} 4. 设R是A到B的二元关系，证明：对于A的任意子集A1和A2, R(A1∩A2) = R(A1)∩R(A2)当且仅当? a∈A,b∈A,且a≠b有R(a)∩R(b) = Φ. 证明(1)先证充分性（由后推前）即已知 ? a∈A， b∈A ，有R(a)∩R(b) = Φ， 目的是证明对于A的任意子集A1和A2, 有 R(A1∩A2) = R(A1)∩R(A2) （下面通过证明R(A1∩A2) ?R(A1)∩R(A2)，以及R(A1)∩R(A2) ? R(A1∩A2)）
离散数学作业2_集合与关系 1. 设A={1,2,3,4,5}，R是集合A上的二元关系，aRb当且仅当a
2. 设A={a,b,c}, R={
离散数学作业 作业6 ——等价关系 1. 设R和S均为A上的等价关系，确定下列各式，哪些是A上的等价关系？如果是，证明之；否则，举反例说明。 （1）R∩S （2）R∪S （3）r (R-S) （4）R- S （5）R?S （6）R2 解：(1),(6)正确，其余错误。 2. R是集合A上的二元关系， a,b,c ,若aRb,且bRc,有cRb,则称R是循环关系。证明R是自反和循环的，当且仅当R是一等价关系。 分析: 需要证明两部分: (1)已知R是自反和循环的，证明:R是一等价关系 (2)已知R是一等价关系, 证明R是自反和循环的. 证明：（1）先证必要性。只需要证明R是对陈的和传递的。 任取(x,y)∈R。因为R是自反的，所以(y,y)∈R。由R是循环的可得(y,x)∈R，即R是对陈的。 任取(x,y)，(y,z)∈R。因R是循环的，所以(z,x)∈R。由R对称性得(x,z)∈R，即R是传递的。 （2）证充分性。只需要证明R是循环的。任取(x,y)，(y,z)∈R，下证(z,x)∈R。由于R是传递的，所以(x,z)∈R。又由R是对称的得(z,x)∈R。所以R是循环的。 3. 设|A|=n，在A上可以确定多少个不同的等价关系？ 解：2n!/((n+1)n!n!)
4. 给定集合S={ 1 , 2 , 3, 4, 5 }，找出S 上的等价关系R ，此关系R 能够产生划分{{1，2}，{3}，{4，5}}，并画出关系图。 解：{(1,2),(2,1),(4,5),(5,4)}S R I =? 5. 设A={1，2，3，4，5}。R 是集合A 上的二元关系，其关系矩阵如下图所示。求包含R 的最小等价关系和该等价关系所确定的划分。 ????????????????=0010001000 000000101000001R M 分析: 可以证明tsr(R)是包含R 的最小等价关系. 解：包含R 的最小等价关系的矩阵表示如下： 100000 1010001010 101000101?? ? ? ? ? ? ??? 上述等价关系确定的划分为{{1},{2,4},{3,5}}. 6. 自学华氏(WalShall)算法，写出算法的基本概念、基本步骤和一个 求解传递闭包的具体实例，并可清晰讲解算法整体实现过程。 7. （选做题）设R 与S 是A 上的等价关系，证明： （1）R S 是A 上的等价关系，iff R S=S R ； （2）R ∪S 是A 上的等价关系，if R S ?S 且 S R ?R. 分析: iff 是if and only if 的缩写, 是当且仅当的意思. 证明：（1）先证必要性。任取(x,z)∈R S ，则存在y 使得xRy,ySz 。因为R 与S 是A 上的等价关系，所以R 与S 是对陈的，即yRx,zSy,所以
Author ：ssjs Mail ： 看了离散数学中的关系整理了一点关于n 元集合中各种关系的计算，现写下这个方便大家学习交流理解。对文章所致一切后果不负任何责任，请谨慎使用。 如有错误之处请指正。 定义： 1，对称：对于a,b R a b ∈∈∈),b (),a (,A 有如果只要 2，反对称：如果R a b R b a b b ∈∈=∈),(),(a ,A ,a 和时仅当 3，自反：如果对每个元素R ),(A a ∈∈a a 有 4，反自反：如果对于每个R ),(A a ?∈a a 有 5，传递：如果对R ),(,R ),(R ),(,A ,,∈∈∈∈c a c b b a c b a 则且 6，非对称：如果R ),(R ),(?∈a b b a 推出【注】其中是含（a,a)这样的有序对的。 【重要】集合A 的关系是从A 到A 的关系 （也就是说集合A 的关系是A A ?的子集）。 如下结论： N 元集合上的自反关系数为：)1(2 -n n N 元集合上的对称关系数为：2/)1(2+n n N 元集合上的反对称关系数为：2/)1(n 3 2-n n N 元集合上的非对称关系数为：2/)1(3-n n N 元集合上的反自反关系数为：)1(n 2-n N 元集合上的自反和对称关系数为：2/)1(n 2-n N 元集合上的不自反也不反自反关系数为：)1(n n 222 2-?-n 下面是上面结论的计算 1，自反 2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由自反定义可知，对R ),(A a ∈∈?a a 有所以n 个有序对()).....3,2,1i X ,X (n i i =其中一定在所求关系中，否则的话此关系就不是自反的了，那么还有n n -2个有序对，所以由集合子集对应二进制串可得自反关系数为)1(n 222--=n n n 下图有助于理解。 （1,1) (2,2).......(n,n) | (1,2) (1,3).........(n-1,n) N n n -2个有序对 2，对称 2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由对称定义可知，对于R a b b ∈∈∈),b (),a (,A ,a 有只要。另外知道在n 平方个有序对中有n 个有序对()).....3,2,1i X ,X (n i i =其中，相应的就有n n -2个有序对（X,Y)且X Y ≠，定义可知后面 的n n -2个有序对只能成对出现，所以有2/)(n 2n -对。前面的那n 对可以出现任意多对。
湖南师范大学硕士研究生入学考试自命题考试大纲 考试科目代码：考试科目名称：离散数学 一、试卷结构 1) 试卷成绩及考试时间 本试卷满分为100分，考试时间为180分钟。 2)答题方式：闭卷、笔试 3)试卷内容结构 集合论40% 数理逻辑40% 图论20% 4)题型结构 a: 填空题，5小题，每小题5分，共25分 b: 计算题，3小题，每小题10分，共30分 c: 证明题，3小题，每小题15分，共45分 二、考试内容与考试要求 1、集合论 考试内容 集合及其表示集合的运算与性质二元关系的概念二元关系的五种性质关系矩阵与关系图关系的各种运算与性质关系闭包与性质相容关系等价关系序关系部分函数、满射、内射、双射的概念可逆、左可逆、右可逆函数特征函数集合的基数与性质 考试要求 （1）理解集合的表示、二元关系的概念、部分函数、满射、内射、双射的概念可逆、左可逆、右可逆函数的概念； （2）掌握集合的运算与性质、关系的五种性质、关系的运算与性质、关系闭包与性质、相容关系、等价关系、序关系. （3）了解特征函数集合的基数与性质．
2、数理逻辑 考试内容 命题与命题的真值五个基本联结词命题符号化合式公式真值表合式公式的类型等价式、蕴含式的证明范式和判定问题求主范式的方法变元、谓词和量词量词的辖域、前束范式合式公式的解释、求合式公式在给定解释下真值的方法 考试要求 （1）理解命题与命题的真值、联结词、合式公式与真值表、变元、谓词和量词等概念． （2）掌握合式公式的类型、等价式、蕴含式的证明、求主范式的方法、合式公式的解释、以及求在给定解释下真值的方法． （3）了解量词的辖域、前束范式． 3、图论 考试内容 图的基本概念路与回路和连通性图的矩阵表示欧拉图和哈密顿图平面图对偶图与着色树与生成树根树及其应用 考试要求 （1）理解图、路、回路和连通性等基本概念． （2）掌握一些特殊图类的性质，树的特征与应用． 三、参考书目 [1] 左孝凌等，《离散数学》，上海科技文献出版社，1982年 [2] 王兵山、张强、毛晓光，《离散数学》，国防科技大学出版社，1998年 [3] 耿素云、屈宛玲，《离散数学》，高等教育出版社，2003年
离散数学测验题——集合与关系(2012--2013) 班级学号姓名 注意事项： 1.独立完成，严禁抄袭！满分100分。 2.最迟上交时间：2012年10月31日（星期三）上课之前交齐。过时不交，成绩记为零。 3.在A4大小的纸上完成并装订好。 一、（52分）给定集合A={a, b, c, d}，且A中的关系R： R ={
() ()()2 34() ()()11111111 (11111) 11 1sr R sr R sr R M M M ??????====?????? 故()()*3 () ()()2()...tsr R sr R sr R sr R R M M M M M ∨∨∨==1111111111111 111????? ?=?????? ， 即R *={