Читать онлайн «Алгебраические основы теории дискретных систем»

А. М. БОГОМОЛОВ, В. Н. САЛИЙ АЛГЕБРАИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ДИСКРЕТНЫХ СИСТЕМ и МОСКВА НАУКА•ФИЗМАТЛИТ 1 997 ►сфрИ ББК 22. 14 f f Издание осуществлено при поддержке 1574 т=><гттътя Российского фонда фундаментальных vr™. °. . || исследований по проекту 97-01-14099 Богомолова. М. , С а л и й В. Н. Алгебраические основы теории дискретных систем. —М. : Наука. Физматлит, 1997. -368 c. -ISBN 5-02-015033-9. Наряду с дискретной математикой современная прикладная алгебра является одним из главных инструментов теории систем. В книге выделен алгебраический материал, который наиболее широко используется в этой области: булевы алгебры и алгебры отношений, полугруппы и решетки, многоосновные и частичные алгебры, категории, функциональные системы, универсально-алгебраические конструкции. При этом в качестве основных моделей конечной системы рассматриваются ориентированный граф и детерминированный автомат. Может служить справочным пособием для научных работников, аспирантов и инженеров, а также для студентов университетов и высших технических учебных заведений. Ил. 121. Библиогр. 90 назв. Рецензент доктор физико-математических наук А. А. Разборов Научное издание БОГОМОЛОВ Анатолий Михайлович САЛИЙ Вячеслав Николаевич АЛГЕБРАИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ДИСКРЕТНЫХ СИСТЕМ Редактор Ф. И. Кизнер Корректор О. Ф. Алексеева ИБ № 41866 ЛР № 020297 от 27. 1191. Подписано в печать 08. 09. 97. Формат 60x90/16. Бумага офсетная. № 1. Печать офсетная. Усл. печ. л. 23. Усл. кр. -отт. 23. Уч. -изд. л. 25,3. Тираж 1000 экз. Заказ № 2313 С-030. Издательская фирма «Физико-математическая литература» РАН 117071 Москва В-71, Ленинский проспект, 15 Отпечатано в Московской типографии № 2 РАН 121099 Москва Г-99, Шубинский пер. , 6 1602040000—030 Б —пк1/1У>\—отг— 61-98. Наука, I полугодие © А. М. Богомолов, В. Н. Салий, иээ(\и)—41 100_ 1997 ISBN 5-02-015033-9 ОГЛАВЛЕНИЕ Предисловие * Введение ' Г л а в а 1. Множества и отношения 13 § 1. 1. Булевы алгебры 13 § 1. 2. Алгебры отношений 30 § 1. 3. Отношения эквивалентности 50 § 1. 4. Упорядоченные множества 68 Г л а в а 2. Алгебраические системы 91 § 2. 1. Основные конструкции универсальной алгебры 91 § 2. 2. Полугруппы И6 § 2. 3. Группы и кольца I36 § 2. 4. Решетки 157 § 2. 5. Функциональные системы 182 § 2. 6. Частичные и многоосновные алгебры. Категории 203 Г л а в а 3. Графы 227 § 3. 1. Основные алгебраические конструкции 227 § 3. 2. Неориентированные графы 246 § 3. 3. Специальные пути в ориентированных графах 265 § 3. 4. Направленные графы 284 Г л а в а 4. Автоматы 307 § 4. 1. Гомоморфизмы и конгруэнции 307 § 4. 2. Некоторые оптимизационные задачи для автоматов ... . 325 § 4. 3. Алгебраические свойства автоматов общего вида 340 § 4. 4. Представление языков в автоматах 355 Список литературы ПРЕДИСЛОВИЕ Наряду с дискретной математикой современная прикладная алгебра является одним из главных инструментов математической кибернетики. Булевы алгебры и алгебры отношений, полугруппы и решетки, многоосновные и частичные алгебры, категории, универсально-алгебраические конструкции,—с этим постоянно приходится сталкиваться читателю научной и технической литературы.