检验有限集合及其二元运算是否构成群的程序
检验有限集合及其二元运算是否构成群的程序
1程茜 2惠芳 2吴俊佳
(1青海师范大学 数学系，青海 西宁 810008;2青海师范大学第二附属中学 青海 西宁 810008)
摘要：利用C语言编制程序检验有限集合及其上二元运算是否适合结合律,是否存在单位元,每一个元是否存在逆元,从而快速检查一个有限集合对所给二元运算是否成一个群.
关 键 词 :有限群 结合律 左单位元 左逆元 程序
中图分类号 O157.2 文献标识码: A
Checking by C- Language Program for the Conditions of Finite Groups
1MA Cheng-ping 2Wu Jun-jia 1Chengqian
(1 Qinghai Normal University, Department of Mathematics,Qinghai Xining 810008; 2 Qinghai Normal University the second Affiliated Middle School, Qinghai Xining 810008;)
Abstract : The associative law, unit element, and inverse element are checked on finite set with binary operation by C- Language Program, so that it can be checked whether a finite set is a group for the giving binary operation quickly.
Keywords: finite group; associative law; left unit element; left inverse element; program
1. 引言
在半群论、群论的研究中，经常需要构造反例以支持研究，这就面临着检验对集合特别是有限集合规定的代数运算是否满足构成半群或群的条件，其中结合律的检验尤为繁琐，对含有N个元的集合，就结合律需检验个式子，每个式子又需进行四次二元运算；虽然对于阶数不高于20的群的个数和种类已完全得到[1]：
但在实际构建阶数不大于20的群时，仍需与已知的群建立同构映射；因而可借助编制程序利用计算机进行快速检验;本文通过用数字字符代替字母字符,将文[2]最多可检验含有65536个元的有限集合扩展为任意有限集合.
2. 预备知识
基金项目: 青海省科技项目(2011-Z-734),青海师范大学青年创新基金项目(2012-4-13), 青海师范大学教研项目(2012-6-4)
作者简介: 程茜(1990-),女,重庆人. E-mail:cq751201@126.com
定义2.1[3] 群的第二定义
一个不空集合G对于一个叫做乘法的代数运算来说作成一个群，假如
I，G对于乘法来说是封闭的；
II，结合律成立：a(bc)=(ab)c
对于G的任意三个元a,b,c都对；
III，G里至少存在一个左单位元e，能让
ea=a
对于G中的任何元a都成立；
IV，对于G的每一个元a，在G里至少存在一个左逆元,能让
=
定义2.2[3] 有限群的另一定义
一个有乘法的有限不空集合G作成一个群，假如
Ⅰ、G对于这个乘法来说是闭的；
Ⅱ、结合律成立：
对于G的任意三个元、、都成立；
Ⅲ、消去律成立：
若，那么；
若，那么.
3. 程序
对于一个有限集合来说：如果利用有限群的另一定义来判断所给的有限集合及其代数运算是否构成群：封闭性的检验很简单，只需观察所给的运算表中没有新元素出现即可，如果有新元素出现则不满足封闭性，反之，则满足封闭性；对于消去律的验证，我们只需观察集合A中的所有元素都出现在所给的运算表中每行每列；因而只需检验结合律是否成立；但对于一个给定的阶数很大的群，在判断消去律的时候就会显得麻烦，这时依据群的第二定义检验有限集合及其上二元运算是否构成群,我们可利用计算机的方法检验结合律是否成立及左单位元，左逆元的存在性.下面我们给出利用C语言编制的检验程序.
3.1 结合律及左单位元的检验程序
#include
#define N 100
int f( int m, int n, int b[N][N] )
{ return b[m][n]; }
int g( int m, int n, int a[N], int b[N][N] )
{ int k, t=-1;
for(k=0; k
if ( a[k]==f(m, n, b))
{ t=k; break; }
return t ;
}
getdata(int a[N], int b[N][N], int n )
{int i, j;
i=0; j=0;
printf( "\n Enter the elements of set A:\n");
for(i=0;i
scanf("%d",&a[i]);
printf("\n Enter the elements of matrix B:\n");
for(i=0;i
for(j=0;j
printf( "\n" );
return;
}
void check(int a[N], int b[N][N], int n)
{ int i, j, k, s=0;
for( i=0; i
if ( s==1) break;
else
for( j=0; j
if (s==1) break;
else
for( k=0; k
if (f(g(i,j,a,b),k,b)!=f (i,g(j,k,a,b),b))
{ s=1;
printf("NO!\n");
printf("%2c%2c%2c",a[i],a[j],a[k]);
printf("\n");
break;
}
if ( s==0 ) printf( "YES!\n");
return;
}
main()
{int i, j, n,t=0,a[N], b[N][N];
do
{ printf("\n Enter the data n: " );
scanf("%d",&n);
}while(n<=0||n>N);
getdata( a, b, n);
check(a, b, n);
for(i=0;i
{for(j=0;j
if(b[i][j]==a[j])
{printf("%d",a[i]);
t++;}
}
printf("%4d\n",t);
return;
}
3.2 左逆元的检验程序
#include
#define N 100
main()
{
int i,j,n,s,m,a[N],b[N][N];
printf("\n Enter the leftidentity m:\n");
scanf("%d",&m);
do
{printf("\n Enter the data n: ");
scanf("%d",&n);
}while(n<=0||n>N);
printf("\n Enter the elements of set A:\n");
for(i=0;i
scanf("%d",&a[i]);
printf("\n Enter the elements of matrix B:\n");
for(i=0;i
for(j=0;j
printf("\n");
for(i=0;i
{for(j=0;j
if(b[j][i]==m){
s=0;
break;
}
else s=1;
}
if(s==0)
printf("Yes!\n");
else
printf("No!\n");
}
在检验过程中,需将运算表输入,输入的过程即可检验封闭性,因而本程序没有对封闭性检验的过程.
4. 实例检验
4.1 三次对称群
设集合A中包含e,a,b,c,d,f六个元.A的乘法由下表规定：
试验证集合A对于该乘法来说是否作成群.
说明：由于本文中的程序仅对所给有限集A中的元为数字时能正常运行.若对于所给有限集A中的元为其外的字母或符号时，须先对其做一个替换.
在利用程序检验前，先做如下替换：分别用1,2,3,4,5,6代替字母e,a,b,c,d,f.则A的乘法表为
利用结合律和左单位元的检验程序进行检验，其运行过程如下：
Enter the data n: 6
Enter the elements of set A:
1 2 3 4 5 6
Enter the elements of matrix B:
1 2 3 4 5 6 2 1 5 6 3 4 3 6 1 5 4 2 4 5 6 1 2 3 5 4 2 3 6 1 6 3 4 2 1 5
YES!
111111 6
说明：替换e,a,b,c,d,f的字母只要是数字即可，但替换后的数字不能重复（集合中元素具有互异性）.YES!说明所给运算结合律成立，“111111 6”表示有六个1即单位元为1.
利用左逆元的检验程序进行检验，其运行过程如下：
Enter the leftientity m:
1
Enter the data n: 6
Enter the elements of set A:
1 2 3 4 5 6
Enter the elements of matrix B:
1 2 3 4 5 6 2 1 5 6 3 4 3 6 1 5 4 2 4 5 6 1 2 3 5 4 2 3 6 1 6 3 4 2 1 5
YES!
说明：结果表明此六元集合及所给运算满足: 以”1”为单位元, 每一个元都有左逆元; 因而此六元集合及其上定义的运算构成群.
设集合A中包含四个元.A的乘法由下表规定：
利用程序进行检验，其运行过程如下：
Enter the data n: 4
Enter the elements of set A:
1 2 3 4
Enter the elements of matrix B:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
YES!
1234 4
说明：结果表示该运算结合律成立，但是左单位元不存在，因为输出的是1234 四个不同的数字，显示有4个左单位元, 这与群有唯一左单位元矛盾,因而左逆元的检验程序就没有必要执行,所以A对于该运算不构成群.
5. 结果分析
利用上述C语言程序运行时，输入乘法表，运行结果与实际情况完全相同;对于任意一个有限集合及其上二元运算，利用上面的程序大大节省了检验时间. 本程序理论上可检验任意有限集合,但对于元素个数较高的有限集合，人工输入乘法表会比较繁琐，因而在实际过程中,本程序的实现还依赖于乘法表的输入.
参考文献：
[1] 施武杰,关于有限群的阶[J].常熟理工学院学报, 2005 ,vol. 19:1-5.
[2] 王绍恒,有限群的结合律的计算机检查法[J].西南师范大学学报（自然科学版）, 2000, vol.25:14-17.
[3] 张禾瑞 近世代数基础[M],高等教育出版社. 1978年
[4] 二级教程——C语言设计[M], 高等教育出版社.1998年
作者简介：
程茜，女，青海师范大学副教授；2003年取得硕士毕业证和理学硕士学位；主要研究领域：半群代数和量子编码。
作者联系方式：
通讯地址：青海省西宁市五四西路38号青海师范大学数学系 程茜
电话：15202512712
邮箱：cq751201@126.com
检验有限集合及其二元运算是否构成群的程序.doc
