XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 28
Текст из файла (страница 28)
2.20. Введем группу Б „движений" (поворотов) окружности как группу, элементами которой являются всевозможные повороты, измеряемые в радианах, причем поворот на любой угол, кратный 2я, отождествляется с нулевым поворотом (тождественным отображением множества точек окружности в себя). Доказать, что группа Б изоморфна фактор-группе и/Е, которая, в свою очередь, изоморфна аддитивной группе Б~ действительных чисел по модулю 1. 2.21. Пусть М = (С, +, О, (м„: а Е В)) — левый модуль над кольцом 1с = (В, +,, О, 1).
Является ли соответствие между элементами и кольца Я и отображениями ы,„взаимно однозначным? В частности, всегда ли нулевое отображение определяется только нулем кольца?т.? Указание: рассмотреть левый модуль матриц-столбцов т вида (х 0), х Е В, над кольцом верхнетреугольных матриц второго порядка и показать, что ответы на поставленные вопросы отрицательны.
З. ПОЛУХОЛЬЦА И Б,уЛЕВЫ АЛГЕБРЫ Полукольцо является одной из важнейших алгебр в современной дискретной математике. Эта глава посвящена рассмотрению нолунолец и булевых влгвбр. Изучаемые здесь методы, прежде всего метод решения систем линейных уравнений в полукольцах, имеют первостепенное значение для теории графов, булевых функций и теории формальных языков. 3.1. Полукольца.
Основные примеры Определение 3.1. 1лолукольцо — зто алгебра с двумя бинарными и двумя нульарными операциями 8 = (8, +,, О, 1), такая, что для произвольных злементов а, Ь, с множества 8 выполняются следующие равенства, называемые аксиомами полукольца: 1) а + (Ь+ с) = (а+ Ь) + с; 2)а+Ь=Ь+а; 3) а+О= а; 4) а.
(Ь с) = (а Ь) с; 5) а.1=1.а=а; 6) а. (Ь+с) =а 6+а с; 7) (Ь+с).а =Ь а+с а; 8) а.О=О.а=О. Первую операцию+ называют сложением нолуко юьца, а вторую операцию . — умножением полукольца 8; злементы 0 и 1 называют соответственно нулем и единицей полукольца 8. 176 з. полукольцл и вулявы ллгевры Аксиомы полукольца называют также основными тпождестпвами полукольца. Таким образом, из определения следует, что операция сложения полукольца ассоииатпивна и комиушашивна, а нуль полукольца является нейшральнььи злеменшом относительно операции сложения; операция умножения полукольца ассоциативна и единица полукольца является нейтральным элементом относительно операции умножения. Кроме этого имеет место свойство дисшрибушивносши (двусторонней) операции умножения относительно сложения полукольца.
Аксиому 8 полукольца называют аннулирующим свойстпвом нуля в полукольце. Используя понятие моноида, определение 3.1 можно переформулировать так. Полукольцо о = (Я, +,, О, 1) — это алгебра с двумя бинарными и двумя нульарными операциями, такая, что: 1) алгебра (Я, +, 0) является коммутативным моноидом (его называют аддитпивньтм моноидом полукольца); 2) алгебра (о,, 1) является моноидом (его называют мульшиплинашивным моноидом полукольца); 3) имеют место свойства (двусторонней) дистрибутивности операции сложения относительно операции умножения; 4) выполняется аннулирующее свойство нуля.
Сравнивая определение полукольца с определением 2.5 кольца, мы видим, что кольцо есть частный случай полукольца: если кольцо по сложению является абелевоб группой, то полукольцо — лишь коммутативиый моноид. Выделим два вида полуколец: номмутпативное полукольцо с коммутативной операцией умножения и идемпотпеншное полукольцо с идемпошеншноб операцией сложения. Пример 3.1. Рассмотрим алгебру К+ = (Й+ 0 (+со), шш, +, +со, О), где й+ — множество неотрицательных действительных чисел, пип — операция взятия наименьшего из двух данных чисел, 3.1.
Полукольца. Осяоввые примеры 177 + — операция сложения действительных чисел, +со — „плюс бесконечность" (в том же смысле, что и в математическом анализе), 0 — чисю „нуль". Эта алгебра — полукольцо, носителем которого является полуось ж+ = (х: х ) 0), пополненная элементом +со (множество всех неотрицательных действительных чисел вместе с „плюс бесконечностью"). Необычность полукольца Я.+ состоит в том, что в качестве его умножения взято сложение действительных чисел, тогда как в качестве сложения выбрана операция взятия наименьшего из двух чисел.
Согласно сигвашуре, элемент +со рассматривается как нуль полукольца. Действительно, шш(х,+со) = х для любого х Е К+ 0 (+ос), т.е. элемент +со есть нейтральный элемент относительно операции шш (операции сюжения в полукольце). Элемент +ос также обладает аннулирующим свойством относительно операции сложения чисел (операции умножения в полукольце): х+ (+ос) = +со.
Следовательно, выполняются аксиомы 3 и 8 полукольца. Остальные аксиомы полукольца также выполнены. Легко убедиться, что алгебра (ж+ 0(+со), ш1п, +со)— коммутативный моноид и алгебра (ж+ 01+со), +, 0) — также коммутативный моноид. Проверим свойства дистрибутивности, которые в данном случэе запишутся так: а+шш(6, с) =шш(а+6, а+с). Имеем а+ш1п(6 с) = ~ +Ь, Ь~(с; (а+с, Ь) с.
В то же время Га+Ь, 6<с; шш(а+ Ь, а+ с) = ~ (а+с, Ь) с. Таким образом, а+тш(6, с) =шш(а+6, а+с). 178 3. ПОЛУКОЛЪЦА И БУЛЕВЫ АЛГЕБРЫ Заметим, что в рассматриваемом полукольце умножение + коммутативно, а сложение ппп идемпотентно. Следовательно, Я,+ — идемпотентное коммутативное полукольцо. Пример 3.2. Рассмотрим алгебру В = ЦО, Ц, +,, О, 1), в которой операции + и заданы таблицами Кали (табл. 3.1 и 3.2). Таблица 3.3 Таблица 3.1 Проверка аксиом полукольца основана на этих таблицах и легко выполняется.
Обратим внимание, что два элемента О и 1, из которых в данном случае состоит носитель полукольца, одновременно являются соответственно нулем и единицей данного полукольца. Легко видеть, что рассматриваемое полукольцо коммутативное и идемпотентное. Интересно то, что операции полукольца В можно трактовать как логические связки „или" и „и", а элементы О и 1— как „ложь" и „истина" соответственно. Пример 3.3.
Рассмотрим еще несколько различных алгебр, являющихся полукольцами. Выполнение аксиом полукольца для всех приведенных алгебр легко проверяется. а. Алгебра Аl = (г1е, +,, О, 1) с носителем — множеством неотрицательных целых чисел и операциями сложения и умножения чисел есть коммутативное полукольцо. Оно не является идемпотентным. б. Алгебра ол = (2А, Ц П, И, А) с носителем — множеством всех подмножеств некоторого множества А и операциями объединения и пересечения есть полукольцо. Оно является идемпотентным и коммутативным.
3.1. Повуттолыта Основные примеры 179 в. Алгебра Ял = (2~"~, О, о, И, тт4) с носителем — множеством всех бинарных отпноитенит1 на множестве А — и операциями объединения и композииии отпношениб является полукольцом. Оно идемпотентное, но не коммутативное. г. Алгебра 8( в) = ((а, Ь), шах, шш, а, Ь), носителем которой служит отрезок числовой прямой, с операциями взятия максимума и минимума из двух чисел есть идемпотентное и коммутативное полукольцо.
В дальнейшем нас будут интересовать только идемпотентные полукольца, поскольку именно на их основе разрабатываются алгебраические методы анализа ориентпированньтх графов и конечных автпоматпов. На носителе идемпотентного полукольца 8 = (о, +,, О, 1) может быть введено отпноитение порядка, которое, естественно, согласуется со свойствами операций полукольца: для произвольных х, у Е Я положим х < у тогда и только тогда, когда х+у=у, т.е.
х < у ео х + у = у. (3.1) Проверим, что таким образом действительно определено отношение порядка. Для этого нужно показать, что введенное бинарное отношение рефлексивно, антписимметпрично и тпранэитпивно. Поскольку для любого х в силу идемпотентности сложения имеет место равенство х+ х = х, то, согласно (3.1), имеем х < х, т.е. введенное отношение рефлексивно. Соотношения х < у и у < х означают, что х + у = у и у + х = = х. Поскольку сложение коммутативно, то из этих равенств следует, что х = у. Значит, рассматриваемое отношение анти- симметрично. Соотношения х < у и у < г означают, что х+ у = у и у+ г = ю Тогда х+ я = х+ (у+ х) = (х+ у) + г = у+ г = г) откуда следует, что х < г.
Таким образом, введенное отношение транзитивно. 180 3. ПОЛУКОЛЬЦА И БУЛЕБЫ АЛГЕБРЫ Итак, отношение < на носителе произвольного идемпотентного полукольца есть отношение порядка. Будем называть его естественным порядком ндемпотентноео полукольца и говорить, что он задан в этом полукольце. Мы установили очень важный факт: всякое идемпотентное полукольцо можно рассматривать как упорядоченное мнозеес1вво, причем отношение порядка определяется через сложение этого полукольца согласно (3.1). Введенное отношение порядка можно интерпретировать так: „большее при сложении поглощает меньшее" (как, скажем, при объединении множества и некоторого его подмножества).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
