檢驗有限集合及其二元運算是否構成群的程序

2014-10-07 15:04:15 大云網　點擊量：評論 (0)

摘　要：利用C語言編制程序檢驗有限集合及其上二元運算是否適合結合律,是否存在單位元,每一個元是否存在逆元,從而快速檢查一個有限集合對所給二元運算是否成一個群。關鍵詞：有限群　結合律　左單位元　左逆元　

摘　要：利用C語言編制程序檢驗有限集合及其上二元運算是否適合結合律,是否存在單位元,每一個元是否存在逆元,從而快速檢查一個有限集合對所給二元運算是否成一個群。
關鍵詞：有限群　結合律　左單位元　左逆元　程序

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

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

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

1　預備知識

定義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的任意三個元、、都成立；

Ⅲ、消去律成立：

2　程序

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

2.1　結合律及左單位元的檢驗程序

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

}