Logo GenDocs.ru


Поиск по сайту:  


Лекции - Основы дискретной математики - файл ОДМ - 4_5.htm


Лекции - Основы дискретной математики
скачать (158.5 kb.)

Доступные файлы (6):

ОДМ - 4_5.htm26kb.16.05.2003 02:17скачать
ОДМ - Лекции 13-15.htm43kb.16.05.2003 02:20скачать
ОДМ - Лекции 16-17.htm23kb.16.05.2003 02:21скачать
ОДМ - Лекции 9-10.htm31kb.16.05.2003 02:19скачать
ОДМ - Лекция 1.htm27kb.16.05.2003 02:16скачать
ОДМ - Лекция 6.htm26kb.16.05.2003 02:18скачать

содержание

ОДМ - 4_5.htm

Реклама MarketGid:
Бинарная операция это, по определению, отображение множества A ╢ A в множество A, при этом образ пары (x, y) обозначим, например, x © y, где © символ операции. Здесь A ≈ произвольное непустое множество и A╢ A ≈ множество всех упорядоченных пар (x, y) ≈ таких, что x, y О A (то есть, декартов квадрат множества A). Непустое множество A называется основным множеством операции.
Можно составить следующую иерархию множеств с бинарной операцией (разумеется, вместо © может быть вставлена любая ≈ +, √, *, И , З , Е , Д , С , ° и т.д. и т.п. ≈ в зависимости от необходимости и вкуса автора.
Группоид, обозначаемый символом (A, © ) ≈ множество A, на котором задана некоторая бинарная операция, обозначаемая © . Если множество группоида конечно, то есть ╫A  = card (A) = n, то таблица Кэли операции группоида есть таблица  n ╢ n, в которой элемент x © y О A находится в клетке пересечения строки x и столбца y. Конечный группоид можно считать заданным, если выписана его таблица Кэли.
 
 



Задача об авторитетах

 


У Саши и Даши авторитет Даша.
У Саши и Маши авторитет Саша.
У Саши авторитет Саша.
У Даши и Маши авторитет Саша.
У Даши авторитет Даша.
У Маши авторитет Петя.
У Пети и Даши авторитет Петя.
У Пети и Маши авторитет Петя.
У Пети и Саши авторитет Саша.
У Пети авторитет Саша.
 
 


^

ТАБЛИЦА КЭЛИ ДЛЯ ОПЕРАЦИИ ╚ АВТОРИТЕТ╩

 


 
 
 
 
 
АВТОРИТЕТ Даша Маша Петя Саша
Даша Даша Саша Петя Даша
Маша Саша Петя Петя Саша
Петя Петя Петя Саша Саша
Саша Даша Саша Саша Саша

* Затенен операционный квадрат
 
 


^

ТАБЛИЦА КЭЛИ, КОРЕЙСКИЙ ВАРИАНТ

 


 
 
 
 
 
АВТОРИТЕТ Ким Пак Чжо
Ким Ким Ким Ким
Пак  Ким Ким Ким
Чжо Ким Ким Ким

 
Квазигруппа (от латинского слова quasi ≈ как будто, почти и слова группа) ≈ группоид, бинарная операция которого (например, © ) такова, что каждое из уравнений a © x = b, y ©  a = b имеет единственное решение для любых элементов a, b этого множества. Квазигруппа ≈ одно из обобщений понятия группа. Особенно близки к группам квазигруппы с единицей ≈ лупы, определение которых получается из аксиом групп отбрасыванием требования ассоциативности. Квазигруппу можно рассматривать и как унивесальную алгебру с тремя бинарными операциями (дополнительно левое и правле деление).
Гомоморфный образ квазигруппы, вообще говоря, не квазигруппа, а группоид с делением. Гомоморфизмам квазигруппы на квазигруппе соответствуют конгруэнции специального типа (т.н. нормальные конгруэнции). Значительно большую роль, чем гомоморфизмы, в теории и классификации групп играют изотопии. Изотопия ≈ отношение эквивалентности для бинарных операций на фиксированном множестве, определяемое с помощью трех подстановок этого множества. Оказывается, что всякий группоид, изотопный квазигруппе, ≈ сам квазигруппа, а всякая квазигруппа изотопна некоторой лупе. Для групп понятие изотопии совпадает с понятием изоморфизма.
Таблица умножения конечной квазигруппы (ее таблица Кэли) в комбинаторике известна по названием латинский квадрат. Одна из задач комбинаторной теории квазигрупп ≈ отыскание систем взаимно ортогональных квазигрупп на заданном множестве ≈ важна для построения конечных проективных плоскостей.
 
 
Лупа, или квазигруппа с единицей, определение которой получается из аксиом группы отбрасыванием требования ассоциативности, особенно близка к группе.
 
 
Полугруппа ≈ множество, с определенной на нем бинарной операцией, удовлетворяющей закону ассоциативности, т.е. группоид (A, © ), в котором для каждой тройки элементов a , b и с  выполняется условие a ©( b © с) =(a © b) © с). Понятие полугруппы есть обобщение понятия группы: из аксиом группы остается лишь одна; этим объясняется и термин ╚ полугруппа╩ .
Теория полугрупп принадлежит к числу сравнительно молодых областей алгебры. Первые исследования, посвященные полугруппам, относятся к 20-м гг. 20 в. и связаны с именем А. К. Сушкевича. Он, в частности, определил строение конечной полугруппы без собственных идеалов. К концу 50-х гг. теория полугрупп сформировалась в самостоятельную ветвь современной алгебры с богатой проблематикой, разнообразными методами и тесными связями с многими областями математики ≈ как собственно алгебраическими (в первую очередь, с теорией групп и теорией колец), так и другими, например, с функциональным анализом, дифференциальной геометрией, алгебраической теорией автоматов.
 
 
  • Примеры полугрупп чрезвычайно многочисленны. Это, например:
  • различные множества чисел вместе с операцией сложения или умножения, замкнутые относительно рассматриваемой операции (т.е. содержащие вместе с любыми двумя своими элементами их сумму или, соответственно, произведение);
  • Полугруппа матриц относительно умножения;
  • Полугруппа функций относительно ╚ поточечного╩ умножения *  , задаваемого формулой (f* g) (x) = f(x) g(x);
  • Полугруппа матриц относительно операции пересечения или объединения;
  • Один из простейших примеров полугруппы ≈ множество всех натуральных чисел относительно сложения; эта полугруппа является частью (подполугруппой) группы целых чисел по сложению или, как говорят, вложима в группу целых чисел.
Далеко не всякая полугруппа вложима в какую-нибудь группу: необходимыи условием такой вложимости является закон сокращения ≈ каждое из равенств ac = bc, ca = cb влечет за собой a = b; выполнение закона сокращения не достаточно для такой вложимости, но, например, коммутативная полугруппа с законом сокращения вложима в группу.
 
 
  • Если на множестве FX всех конечных последовательностей элементов произвольного множества (алфавита) ^ X задать операцию * формулой
(x1, . . . , xm) *  (y1, . . . , yn) = (x1, . . . , xmy1, . . . , yn),

 то FX станет полугруппой; она называется свободной полугруппой над алфавитом X. Роль свободных полугрупп в общей теории определяется тем, что всякая полугруппа есть гомоморфный образ подходящей свободной полугруппы. Важную роль играют свободные полугруппы и в некоторых приложениях, прежде всего в теории формальных языков и кодов.
  • Всякая совокупность пребразований произвольного множества M, замкнутая относительно операции композиции (последовательного выполнения), будет полугруппой относительно этой операции; такова, в частности, совокупность всех преобразований множества M, называемая симметрической полугруппой на множестве M. Многие важные совокупности преобразований оказываются полугруппами относительно композиции, причем часто они не являются группами. С другой стороны, всякая полугруппа изоморфна некоторой полугруппе преобразований. Все это определяет как роль полугрупп преобразований в общей теории полугрупп, так и роль теории полугрупп для изучения в самом общем виде преобразований с точки зрения их композиции. В большой степени через рассмотрение преобразований осуществляются связи теории полугрупп с другими областями математики.
Как и в других алгебраических теориях, одной из главных задач теории полугрупп является классификация всевозможных полугрупп, описание их строения. Это осуществляется прежде всего наложением на рассматриваемые полугруппы различых ограничений и выделение тем самым различных типов полугрупп. Среди важных типов ≈ регулярные полугруппы, то есть полугруппы, в которых для любого элемента a существует такой элемент x, что axa = a. Регулярными являются, например, полугруппа всех матриц данного порядка над телом, симметрические полугруппы, полугруппы всех частичных преобразований множеств. Регулярные полугруппы принадлежат к числу наиболее активно изучаемых в теории полугрупп.
Заметную часть общей теории составляет теория представлений полугрупп преобразованиями и матрицами. Точка зрения теории представлений нередко проливает дополнительный свет на некоторые типы полугрупп, естественно определяемые с точки зрения аксиоматики. Внесение в полугруппы дополнительных структур, согласованных с полугрупповой операцией, выделяет особые разделы теории полугрупп, такие, как теория топологических полугрупп, теория упорядоченных полугрупп.
 
 
Моноид ≈ это, по определению, полугруппа с единицей.
 
 
Группа (нем. Gruppe) ≈ одно из основных понятий современной математики ≈ есть лупа, являющаяся в то же время полугруппой.
Теория групп изучает в самой общей форме операции, наиболее часто встречающиеся в математике и ее приложениях (примеры таких операций ≈ сложение чисел, умножение чисел, сложение векторов, последовательное выполнение преобразований и т.п.). При этом теория групп изучает не совсем произвольные операции, а лишь те, которые обладают рядом основных войств, перечисляемых в определении группы.
Формальное определение группы таково. Пусть ^ G ≈ произвольное непустое множество, на котором задана бинарная алгебраическая операция
° , т.е. для любых двух элементов a, b, из G определен некоторый элемент (обозначаемый, например, a ° b) также из G. Если при этом выполняются условия: 1) (a °b) ° c = a °  (b ° c) для любых a, b и c из G; 2) в G существует такой элемент e (называемый единицей, иногда ≈ нейтральным элементом), что a° e = e ° a = a для любого a из G; 3) для любого a из G существует такой элемент a √1 (обратный к a элемент), что a ° a √1 = a √1 ° a = e, то множество G с заданной на нем операцией °   назовем группой.
Примеры групп. 1) множество G различных движений эвклидовой плоскости, самосовмещающих данную фигуру, операцией на котором служит композиция движений (если j , y ≈ два движения из G, то результатом их композиции назовем движение j  ° y , равносильное последовательному выполнению сначала движения j , а затем движения y ), образует т.н. группу симметрий фигуры. Единицей в этой группе будет тождественное преобразование плоскости, а обратным к j элементом ≈ обратное к j преобразование. Группа G является характеристикой большей или меньшей симметричности фигуры: чем больше множество G, тем симметричнее фигура. Например, группа симметрий квадрата (рис., а) состои т из восьми движений
 
 




 


 (четыре поворота вокруг центра квадрата и четыре отражения: два ≈ относительно диагоналей и два ≈ относительно прямых, соединяющих середины противоположных сторон). Для круга (рис. б) группа симметрий уже содержит бесконечно много элементов (например, все повороты вокруг центра), а для фигуры, нарисованной на рисунке (в) группа симмерий состоит из одного тождественного преобразования.
Если Z ≈ множество всех целых чисел, а операция на Z ≈ их обычное сложение + , то Z ≈ группа. Роль  e  будет играть число 0, а роль обратного к z элемента ≈ число √z. Часть H множества Z , состоящая из четных чисел, сама будет группой относительно той же операции. В таком случае говорят, что Hподгруппа группы Z . Обе групы Z и H удовлетворяют следующему дополнительному условию: 4) a + b = b a для любых a и b из группы. Всякая группа, в которой выполняется условие 4) называется коммутативной или абелевой.
3) Множество всех подстановокn символов образует группу относительно умножения подстановок, называемую симметрической группой. При n Ё  3 симметрическая группа неабелева. Порядок (число элементов) симметрической группы равен n ! .
 
 


 


Предыдущий раздел  Оглавление    Следующий раздел

 
Реклама:





Скачать файл (158.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru