Отправляет email-рассылки с помощью сервиса Sendsay

Система компьютерной алгебры GAP

Подписаться Бесплатная «Серебряная» новостная рассылка . Временно не выходит ,возобновит выход - нет информации Подписчиков 783 RSS
←   Сентябрь 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://www.gap-system.org/ukrgap/
Открыта: 05-02-2002

Автор
Александр Борисович Коновалов

Статистика

783 подписчиков
0 за неделю
←   Все выпуски   →

Система компьютерной алгебры GAP - # 27 (18-09-03)


Информационный Канал Subscribe.Ru
Рассылка "Система компьютерной алгебры GAP"
ведущий рассылки А.Б.Коновалов, a_konovalov@hotmail.com
выпуск 27 от 18 сентября 2003 г.

СОДЕРЖАНИЕ ВЫПУСКА:
  1. Бинарные отношения в GAP
  2. XVIII ESCOLA DE ALGEBRA (Бразилия, 2004)
  3. МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ ПО ТЕОРИИ ГРУПП "GROUPS ST ANDREWS 2005" (Шотландия, 2005)
На сайте Украинской группы пользователей GAP в разделе "Изучаем алгебру с GAP" опубликован материал по теме "Бинарные отношения". Его полный текст приводится ниже.
Бинарные отношения в GAP

Бинарным отношением R на множестве M называется подмножество декартового квадрата множества М. Бинарное отношение также можно рассматривать как соответствие, для которого область отправления и область прибытия совпадают с множеством M. Если множество M конечно, то бинарное отношение можно наглядно представить в виде ориентированного графа, в котором из вершины, соответствующей элементу x, проведено ребро в вершину, соответствующую элементу y, тогда и только тогда, когда x R y.

Для задания бинарных отношений на множестве {1, ..., n } в GAP используется функция BinaryRelationOnPoints. Ее аргументом является список list, состоящий, в свою очередь, из n списков (возможно, пустых), и означающий, что число i находится в отношении R с каждым из элементов i-го списка.

При этом n определяется автоматически как максимальное число, содержащееся в аргументе list. В случае несоответствия n длине списка list выводится сообщение об ошибке. Так, например, нельзя использовать запись BinaryRelationOnPoints([[1,2,3],[2]]) - вместо этого нужно писать BinaryRelationOnPoints([[1,2,3],[2],[]]).

Итак, зададим бинарное отношение R на множестве {1,2,3}, состоящее из упорядоченных пар (1,1), (1,2), (2,3), (3,1) и (3,2), что означает, что выполняются соотношения 1 R 1, 1 R 2, 2 R 3, 3 R 1 и 3 R 2.

gap> R:=BinaryRelationOnPoints([[1,2],[3],[1,2]]);
Binary Relation on 3 points

Исходный список, с помощью которого было задано бинарное отношение R, можно получить с помощью функции Successors:

gap> s:=Successors(R);
[ [ 1, 2 ], [ 3 ], [ 1, 2 ] ]

Таким образом, по определению функций BinaryRelationOnPoints и Successors, всегда выполняется равенство R = BinaryRelationOnPoints(Successors(R)).

Бинарное отношение равенства и пустое бинарное отношение на этом же множестве {1,2,3} можно получить непосредственно с помощью функций IdentityBinaryRelation и EmptyBinaryRelation (обратите внимание на результат, возвращаемый функцией Successors):

gap> IdentityBinaryRelation(3);
<equivalence relation on <object> >
gap> Successors(last);
[ [ 1 ], [ 2 ], [ 3 ] ]
gap> EmptyBinaryRelation(3);
Binary Relation on 3 points
gap> Successors(last);
[ [ ], [ ], [ ] ]

Теперь получим случайным образом составленное бинарное отношение на 3-х точках, а затем выясним, какими свойствами оно обладает. Заметьте, что количество точек можно узнать с помощью функции DegreeOfBinaryRelation:

gap> R:=RandomBinaryRelationOnPoints(3);
Binary Relation on 3 points
gap> Successors(last);
[ [ 1 ], [ 2, 3 ], [ 1, 3 ] ]
gap> DegreeOfBinaryRelation(r);
3

Бинарное отношение R на множестве M называется рефлексивным на M, если x R x для каждого элемента x множества M. В нашем случае R - рефлексивно:

gap> IsReflexiveBinaryRelation(R);
true

Пример бинарного отношения, которое не является рефлексивным:

gap> T:=BinaryRelationOnPoints([[2,3],[2],[3]]);
Binary Relation on 3 points
gap> IsReflexiveBinaryRelation(T);
false

Бинарное отношение R на множестве M называется антирефлексивным на M, если условие x R x не выполняется для каждого элемента x множества M. В нашем случае R не является антирефлексивным, что можно проверить следующим образом:

gap> r:=Successors(R);
[ [ 1 ], [ 2, 3 ], [ 1, 3 ] ]
gap> ForAll(r, i -> not Position(r,i) in i);
false

Бинарное отношение T из предыдущего примера не является ни рефлексивным, ни антирефлексивным:

gap> t:=Successors(T);
[ [ 2, 3 ], [ 2 ], [ 3 ] ]
gap> ForAll(t, i -> not Position(t,i) in i);
false

Пример антирефлексивного бинарного отношения:

gap> T:=BinaryRelationOnPoints([[2,3],[1],[2]]);
Binary Relation on 3 points
gap> t:=Successors(T);
[ [ 2, 3 ], [ 1 ], [ 2 ] ]
gap> ForAll(t, i -> not Position(t,i) in i);
true

Бинарное отношение R на множестве M называется симметричным на M, если для любых элементов x и y множества M из того, что x R y следует, что y R x. В нашем случае R не является симметричным:

gap> IsSymmetricBinaryRelation(R);
false

Пример симметричного бинарного отношения:

gap> T:=BinaryRelationOnPoints([[2,3],[1],[1]]);
Binary Relation on 3 points
gap> IsSymmetricBinaryRelation(T);
true

Бинарное отношение R на множестве M называется антисимметричным на M, если для любых элементов x и y множества M из того, что x R y и y R x следует, что x = y. В нашем случае R является антисимметричным:

gap> r:=Successors(R);
[ [ 1 ], [ 2, 3 ], [ 1, 3 ] ]
gap> IsAntisymmetricBinaryRelation(R);
true

Этот же результат можно было бы получить непосредственной проверкой:

gap> ForAll(r,i->ForAll(i,j->(not Position(r,i) in r[j] or j=Position(r,i))));
true

Зададим теперь новое бинарное отношение, которое отличается от R еще одним соотношением между 1 и 3, и проверим, что оно уже не является ни симметричным, ни антисимметричным:

gap> T:=BinaryRelationOnPoints([[1,3],[2,3],[1,3]]);
Binary Relation on 3 points
gap> t:=Successors(T);
[ [ 1, 3 ], [ 2, 3 ], [ 1, 3 ] ]
gap> IsAntisymmetricBinaryRelation(R);
false
gap> IsSymmetricBinaryRelation(T);
false

Бинарное отношение R на множестве M называется транзитивным на M, если для любых элементов x, y, z множества M из того, что x R y и y R z следует, что x R z. В нашем случае бинарное отношение R не является транзитивным. Легко проверить, что отношение равенства на этом же множестве {1,2,3} является транзитивным.

gap> IsTransitiveBinaryRelation(R);
false
gap> IsTransitiveBinaryRelation(IdentityBinaryRelation(3));
true

Бинарное отношение R на множестве M называется асимметричным на M, если для любых элементов x и y множества M из того, что выполняется условие x R y, следует, что не выполняется условие y R x. Сконструированное выше отношение R не является асимметричным:

gap> r:=Successors(R);
[ [ 1 ], [ 2, 3 ], [ 1, 3 ] ]
gap> ForAll(r,i->ForAll(i,j->(not Position(r,i) in r[j] )));
false

Пример асимметричного бинарного отношения:

gap> T:=BinaryRelationOnPoints([[2],[3],[1]]);
Binary Relation on 3 points
gap> t:=Successors(T);
[ [ 2 ], [ 3 ], [ 1 ] ]
gap> ForAll(t,i->ForAll(i,j->(not Position(t,i) in t[j] )));
true

Бинарное отношение R на множестве M называется отношением порядка на M, если оно транзитивно и антисимметрично. Отношение порядка называется нестрогим, если оно рефлексивно, и строгим, если оно антирефлексивно. Эти условия проверяются с помощью комбинаций перечисленных выше функций.

Бинарное отношение R на множестве M называется отношением предпорядка на M, если оно рефлексивно и транзитивно. Для проверки выполнения этого условия используется функция IsPreOrderBinaryRelation. Функция IsPartialOrderBinaryRelation возвращает true, если отношение является антисимметричным и является отношением предпорядка, и false в противном случае, т.е. если оно является отношением нестрогого порядка.

В GAP имееются функции для построения новых бинарные отношений, которые содержат в себе заданные, но обладают при этом некоторыми дополнительными свойствами.

Функция SymmetricClosureBinaryRelation возвращает минимальное бинарное отношение, которое содержит в себе заданное, и является симметричным (сравните, как изменяется при этом результат, возвращаемый функцией Successors):

gap> C:=SymmetricClosureBinaryRelation(R);
Binary Relation on 3 points
gap> Successors(C);
[ [ 1, 3 ], [ 2, 3 ], [ 1, 2, 3 ] ]

Аналогичное назначение имеют функции TransitiveClosureBinaryRelation и ReflexiveClosureBinaryRelation

gap> C:=TransitiveClosureBinaryRelation(R);
Binary Relation on 3 points
gap> Successors(C);
[ [ 1 ], [ 1, 2, 3 ], [ 1, 3 ] ]

gap> C:=ReflexiveClosureBinaryRelation(R);
Binary Relation on 3 points
gap> IsReflexiveBinaryRelation(C);
true
gap> Successors(C);
[ [ 1 ], [ 2, 3 ], [ 1, 3 ] ]

В последнем случае C=R, так как R являлось транзитивным.

Бинарное отношение R на множестве M называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Очевидно, что R не является отношением эквивалентности. GAP также легко проверит это:

gap> IsEquivalenceRelation(R);
false

Очевидно, что последовательное применение рефлексивного, транзитивного и симметричного замыкания приведет к отношению эквивалентности:

gap> C:=TransitiveClosureBinaryRelation(R);
Binary Relation on 3 points
gap> C:=ReflexiveClosureBinaryRelation(c);
Binary Relation on 3 points
gap> C:=SymmetricClosureBinaryRelation(c);
Binary Relation on 3 points
gap> IsEquivalenceRelation(C);
true
gap> Successors(C);
[ [ 1, 2, 3 ], [ 1, 2, 3 ], [ 1, 2, 3 ] ]

В этом случае мы получили полное отношение эквивалентности, так любые два элемента x и y множества M находятся в отношении C.

Построим теперь отношение сравнимости по модулю три на множестве M={1,2,3,4,5,6}.

gap> R:=BinaryRelationOnPoints([[1,4],[2,5],[3,6],[1,4],[2,5],[3,6]]);;
gap> Successors(R);
[ [ 1, 4 ], [ 2, 5 ], [ 3, 6 ], [ 1, 4 ], [ 2, 5 ], [ 3, 6 ] ]
gap> IsEquivalenceRelation(R);
true

Мы можем получить разбиение множества M на классы эквивалентности:

gap> EquivalenceRelationPartition(R);
[ [ 1, 4 ], [ 2, 5 ], [ 3, 6 ] ]

и классы эквивалентности:

gap> C:=EquivalenceClasses(R);
[ {1}, {2}, {3} ]

Классы эквивалентности имеют свое внутреннее представление в системе GAP. Возьмем первый из элементов полученного списка классов эквивалентности, и проверим, что он действительно является таковым, с помощью функции IsEquivalenceClass:

gap> C[1];
{1}
gap> IsEquivalenceClass(C[1]);
true

Мы можем получить список элементов этого класса следующим образом:

gap> Elements(C[1]);
[ 1, 4 ]

Далее, для каждого элемента множества M можно найти класс эквивалентности, которому он принадлежит:

gap> EquivalenceClassOfElement(R,1);
{1}

В заключение дадим понятие о том, как можно находить обратные отношения, выполнять операции отрицания, пересечения, объединения, разности и композиции отношений, заданных на множестве M = { 1, ..., n }. Для заданного бинарного отношения R нужно определить с помощью функции DegreeOfBinaryRelation(R) порядок множества M, и вычислить его декартов квадрат. Затем из списка Successors(R) сформировать список упорядоченных пар, образующих бинарное отношение. Тогда вычисление результата может быть запрограммированно непосредственно исходя из определения этих операций (оставляем это читателю). Учтите, что для операций пересечения, объединения, разности, композиции необходимо проверять, что оба отношения заданы на одном и том же множестве M.

Соответствующий раздел документации по системе GAP 4.3 на английском языке находится здесь.
XVIII ESCOLA DE ALGEBRA
г.Кампинас, Бразилия, 19-23 июля 2004 г.
http://www.ime.unicamp.br/~escola
МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ ПО ТЕОРИИ ГРУПП "GROUPS ST ANDREWS 2005"
г.Сент-Эндрюс, Шотландия, 31 июля - 13 августа 2005 г.
Следите за обновлением информации в разделе "Конференции"!
С уважением,
Коновалов Александр Борисович , председатель Украинской группы пользователей GAP ,
доцент кафедры алгебры и геометрии Запорожского государственного университета
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное