檢驗(yàn)有限集合及其二元運(yùn)算是否構(gòu)成群的程序

2014-10-07 15:04:15 大云網(wǎng)　點(diǎn)擊量：評(píng)論 (0)

摘　要：利用C語(yǔ)言編制程序檢驗(yàn)有限集合及其上二元運(yùn)算是否適合結(jié)合律,是否存在單位元,每一個(gè)元是否存在逆元,從而快速檢查一個(gè)有限集合對(duì)所給二元運(yùn)算是否成一個(gè)群。關(guān)鍵詞：有限群　結(jié)合律　左單位元　左逆元　

摘　要：利用C語(yǔ)言編制程序檢驗(yàn)有限集合及其上二元運(yùn)算是否適合結(jié)合律,是否存在單位元,每一個(gè)元是否存在逆元,從而快速檢查一個(gè)有限集合對(duì)所給二元運(yùn)算是否成一個(gè)群。
關(guān)鍵詞：有限群　結(jié)合律　左單位元　左逆元　程序

在半群論、群論的研究中，經(jīng)常需要構(gòu)造反例以支持研究，這就面臨著檢驗(yàn)對(duì)集合特別是有限集合規(guī)定的代數(shù)運(yùn)算是否滿足構(gòu)成半群或群的條件，其中結(jié)合律的檢驗(yàn)尤為繁瑣，對(duì)含有N個(gè)元的集合，就結(jié)合律需檢驗(yàn)個(gè)式子，每個(gè)式子又需進(jìn)行四次二元運(yùn)算；雖然對(duì)于階數(shù)不高于20的群的個(gè)數(shù)和種類已完全得到[1]：

階數(shù)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
群數(shù)	1	1	1	2	1	2	1	5	2	2	1	5	1	2	1	14	1	5	1	5

但在實(shí)際構(gòu)建階數(shù)不大于20的群時(shí)，仍需與已知的群建立同構(gòu)映射；因而可借助編制程序利用計(jì)算機(jī)進(jìn)行快速檢驗(yàn);本文通過用數(shù)字字符代替字母字符,將文[2]最多可檢驗(yàn)含有65536個(gè)元的有限集合擴(kuò)展為任意有限集合。

1　預(yù)備知識(shí)

定義2.1[3] 群的第二定義

一個(gè)不空集合G對(duì)于一個(gè)叫做乘法的代數(shù)運(yùn)算來說作成一個(gè)群，假如

I，G對(duì)于乘法來說是封閉的；

II，結(jié)合律成立：a(bc)=(ab)c

對(duì)于G的任意三個(gè)元a,b,c都對(duì)；

III，G里至少存在一個(gè)左單位元e，能讓

ea=a

對(duì)于G中的任何元a都成立；

IV，對(duì)于G的每一個(gè)元a，在G里至少存在一個(gè)左逆元,能讓

定義2.2[3] 有限群的另一定義

　　一個(gè)有乘法的有限不空集合G作成一個(gè)群，假如

Ⅰ、G對(duì)于這個(gè)乘法來說是閉的；

Ⅱ、結(jié)合律成立：

對(duì)于G的任意三個(gè)元、、都成立；

Ⅲ、消去律成立：

2　程序

對(duì)于一個(gè)有限集合來說：如果利用有限群的另一定義來判斷所給的有限集合及其代數(shù)運(yùn)算是否構(gòu)成群：封閉性的檢驗(yàn)很簡(jiǎn)單，只需觀察所給的運(yùn)算表中沒有新元素出現(xiàn)即可，如果有新元素出現(xiàn)則不滿足封閉性，反之則滿足封閉性；對(duì)于消去律的驗(yàn)證，只需觀察集合A中的所有元素都出現(xiàn)在所給的運(yùn)算表中每行每列，因而只需檢驗(yàn)結(jié)合律是否成立；但對(duì)于一個(gè)給定的階數(shù)很大的群，在判斷消去律的時(shí)候就會(huì)顯得麻煩。這時(shí)依據(jù)群的第二定義檢驗(yàn)有限集合及其上二元運(yùn)算是否構(gòu)成群,可利用計(jì)算機(jī)的方法檢驗(yàn)結(jié)合律是否成立及左單位元，左逆元的存在性。下面，筆者給出利用C語(yǔ)言編制的檢驗(yàn)程序。

2.1　結(jié)合律及左單位元的檢驗(yàn)程序

#include <stdio.h>

#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<N; 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<n;i++)

scanf("%d",&a[i]);

printf("n Enter the elements of matrix B:n");

for(i=0;i<n;i++)

for(j=0;j<n;j++) scanf("%d",&b[i][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<n; i++ )

if ( s==1) break;

else

for( j=0; j<n; j++)

if (s==1) break;

else

for( k=0; k<n; 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];

{ 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<n;i++)

{for(j=0;j<n;j++)

if(b[i][j]==a[j])

{printf("%d",a[i]);

t++;}

}

printf("%4dn",t);

return;

}

2.2　左逆元的檢驗(yàn)程序

#include <stdio.h>

#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);

{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<n;i++)

scanf("%d",&a[i]);

printf("n Enter the elements of matrix B:n");

for(i=0;i<n;i++)

for(j=0;j<n;j++) scanf("%d",&b[i][j]);

printf("n");

for(i=0;i<n;i++)

{for(j=0;j<n;j++)

if(b[j][i]==m){

s=0;

break;

}

else s=1;

}

if(s==0)

printf("Yes!n");

else

printf("No!n");

}

在檢驗(yàn)過程中,需將運(yùn)算表輸入,輸入的過程即可檢驗(yàn)封閉性,因而本程序沒有對(duì)封閉性檢驗(yàn)的過程。

3　實(shí)例檢驗(yàn)

　　設(shè)集合A中包含e,a,b,c,d,f六個(gè)元.A的乘法由下表規(guī)定：

	e	a	b	c	d	f
e	e	a	b	c	d	f
a	a	e	d	f	b	c
b	b	f	e	d	c	a
c	c	d	f	e	a	b
d	d	c	a	b	f	e
f	f	b	c	a	e	d

試驗(yàn)證集合A對(duì)于該乘法來說是否作成群.

說明：由于本文中的程序僅對(duì)所給有限集A中的元為數(shù)字時(shí)能正常運(yùn)行.若對(duì)于所給有限集A中的元為其外的字母或符號(hào)時(shí)，須先對(duì)其做一個(gè)替換.

在利用程序檢驗(yàn)前，先做如下替換：分別用1,2,3,4,5,6代替字母e,a,b,c,d,f.則A的乘法表為

責(zé)任編輯：葉雨田

免責(zé)聲明：本文僅代表作者個(gè)人觀點(diǎn)，與本站無關(guān)。其原創(chuàng)性以及文中陳述文字和內(nèi)容未經(jīng)本站證實(shí)，對(duì)本文以及其中全部或者部分內(nèi)容、文字的真實(shí)性、完整性、及時(shí)性本站不作任何保證或承諾，請(qǐng)讀者僅作參考，并請(qǐng)自行核實(shí)相關(guān)內(nèi)容。

我要收藏

個(gè)贊