Дискретная математика (998286), страница 9
Текст из файла (страница 9)
Неформально говоря, замкнутость означает, что многократное выполнение допустимых шагов не выводит за определенные границы. Например, предел сходящейся последовательности чисел из замкнутого интервала 1а, Ь) обязательно принадлежит этому интервалу, а предел сходящейся последовательности чисел из открытого (то есть не замкнутого) интервала (а, Ь) может лежать вне этого интервала.
В некоторых случаях можно «расширить» незамкнутый объект так, чтобы он оказался замкнутым. 1.9.1. Замыкание отношения относительно свойства ПУсть В и  — отношения на множестве М. Отношение В' называется замыканием В относительно свойства С, если: 1. В' обладает свойством С; С(В'); 2. В' является надмножеством В: В с В', 3.
В' является наименьшим: С(В") 8г В с В" =» В' с В". Глава 1. Мноиестве и отношения 48 1.9.2. Транзитивное и рефлексивное транзитивное замыкания Пусть Я+ — объединение положительных степеней В, а В' объединение не. отрицательных степеней В: "' =бойз "":=0В' ТЕОРЕМА В+ — траюитивное зииыканив й. Докдздтадьство Проверим выполнение свойств замыкания при условии, что свойство С вЂ” это транзитивность. 1. Пусть ай+63сЬйнс. Тогда За ай"63сЗтп ЬВ с.
Следовательно, Лет,...,с„, айс,Я...Вс„1ВЬ и В4,...,И 1 Ьйт1,й...йт1 1йс, Таким образом, айстй... Вс 1ВЬйт3тВ... Вт3 1йс =ь ой"+ш+зс =и ай+с. 2. В = В' =Ф В с 0 В' =з В с В+. 1=1 3. ай+Ь =ь Вй ай"6 =ь Бсы...,сь з айстй...йсь тВЬ; В с В" =й айнстйн... Янек 1йнЬ =ь айн6. Таким образом, В+ с В". П ТЕОРЕМА В' — рвфдексивков траюитивнов зииыкакив В. Вычислить транзитивное замыкание заданного отношения можно следующим образом: В'=ИВ'= ИВ' Ю'= МЮ'= МК з-1 1=1 1 — 1 з-1 Такое вычисление будет иметь сложность О(из).
1.9.3. Алгоритм Уоршалла Рассмотрим алгоритм вычисления транзитивного замыкания отношения В на множестве М, (М) = и, имеющий сложность О(из). Алгоритм 1.8. Алгоритм Уоршалла Вход: отношение, заданное матрицей й Выход: трвизитивное замыкание отношения, заданное мзтрицей Т. Я:=и 1от В йот 1 Фо и оо 49 Упражиения Гог у й«ив Г то и йо Гог й 6 от 1 Го п йо ту,й]:=я(?й] уз[1,«]а3[йй] еад 1ог евд Гог Я:=Т евд Гог ОБОСНОВАНИЕ На каждом шаге основного цикла (по 1) в транзитивное замыкание добавляются такие пары элементов с номерами 7' и й (то есть ТЦ', й]: = 1), для которых существует последовательность промежуточных элементов с номерами в диапазоне от 1 до г, связанных отношением В. Действительно, последовательность промежуточных элементов с номерами в диапазоне от 1 до г, связанных отношением В, для элементов с номерами 7' и й существУет в одном из двух случаев: либо уже существует последовательность промежуточных элементов с номерами в диапазоне от 1 до 1 — 1 для пары элементов с номерами 7' и й, либо существуют две последовательности элементов с номерами в диапазоне от 1 до 1 — 1 — одна для пары элементов с номерами 7' и 1 и вторая для пары элементов с номерами 1 и й.
Именно это отражено в операторе Т[ А й]: = 3[7', й] ~/ 3[7', 1] й Я[К й]. После окончания основного цикла в качестве промежуточных рассмотрены все элементы, и, таким образом, построено транзитивное замыкание. П Комментарии Основные сведения, изложенные в этой главе, можно найти в любом учебнике по (дискретной) математике. Алгоритм 1.2 описан в [14]. Алгоритмы 1.3, 1А, 1.6— общеизвестный программистский фольклор. Алгоритм 1.7 описан в фундаментальной книге [8], которая входит в «золотой список» обязательного чтения любого программиста, Алгоритм 1.8 описан во многих источниках, например в [1]. Упражнения 1.1. Существует ли множество всех множеств? 1.2. Доказать, что ]АОВ] =]А]+]В] — ]АПВ]. 1.3, Доказать, что АОВ = (Аг1З) 0(АПВ) 0(АПВ). 1.4.
доказать, что я(2А + гп) = я(2А — гп) для 0 < гп < 2" — 1, где Я вЂ” функция из алгоритма 1.2. 16. Пусть Я: = ((т п) ] гп и 6 1Чй гп = пз). Какими свойствами обладает отношение Я? 1.6. Доказать теорему из подраздела 1.6.3. 1,7. Доказать, что если гв — отношение эквивалентности на конечном множестве М и]М] =]М/гв], то Ухе М][х] — ] =1. 50 Глава 1. Множества и отношении 1.8.
Пусть А — вполне упорядоченное множество с отношением порядка, В. Введем отношение В на множестве кортежей элементов нз А следующим образом: (аы..., а )В(Ьы...,Ь„): =(от < и МЧ 1' б 1..то а; = Ь;) Ч (3 т б 1..тп (а,ВЬ; 8сЧ~ Е 1.А — 1 а, = Ь )). Такое отношение называется лексикографичебагм, или аараентлиым'порядком.
Доказать, что алфавитный порядок есть полный порядок на множестве кортежей А+: = ( ), т А'. 1.9. Доказать вторую теорему из подраздела 1.9.2. ГЛАВА 2 Алгебраические структуры Алгебраические методы описания моделей находят самое широкое применение при формализации различных предметных областей. Грубо говоря, при построении модели предметной области все начинается с введения подходящих обозначений для операций и отношений с последующим исследованием их свойств.
Владение алгебраической терминологией, таким образом, входит в арсенал средств, необходимых для абстрактного моделирования, предшествующего практическому программированию задач конкретной предметной области. Материал этой главы помимо введения в терминологию общей алгебры содержит некоторое количество примеров конкретных алгебраических структур. В начале бегло рассматриваются классические структуры, которые обычно включаются в курсы общей алгебры, а затем обсуждаются некоторые более специальные структуры, наиболее часто применяемые в конкретных программных построениях. 2.1. Операции и алгебры Словом »алгебра» обозначают, вообще говоря, не только отрасль математики, но и один из конкретных объектов, изучаемых в этой отрасли.
К счастью, »алгебры» в узком смысле здесь не рассматриваются, а потому для краткости и без риска возникновения недоразумений слово »алгебра» используется как родовое понятие для обозначения разнообразных алгебраических структур. 2.1.1. Алгебраические структуры Всюду определенная (тотальная) функция у: М" -+ М называется и-орной (и-местной) операцией на М. Если операция у — бинарная (то есть у: М х М -+ М), то будем писать ауЬ вместо ~р(а, Ь) или а о Ь, где о — знак операции. ЗАМЕЧАНИЕ Такая форма записи называется инфиясиой, Глава 2. Алгебраические структуры Множество М вместе с набором операций Е = (~р„., р ), чч: М" — > М, где иг — арность операции р,, называется.алгебраической структурой, универсальной алгеброй или просто алгеброй.
Множество М называется основныч (нвсуигим) множеством, или основой (носителем); вектор арностей (пы...,и ) Называется типом; множество операций Е называется сигнатурой Запись: (М;Е) или (М~ ры ~ ут) ЗАМЕЧАНИЕ Операции у~ нонвчнонвстны (4инитарны), сигнатура Е конечна. Носитель не обязательно конечен, но не пуст. Если в качестве р; допускаются не только функции, но и отношения, то множество М вместе с набором операций и отношений называется моделью.
В приложениях обычно используется следующее обобщение понятия алгебры. Пусть М = (МО...,М„) — множество основ, Е = (ры...,р ) — сигнатура, причем чч: Ми х ° х Мг„— > М.. Тогда (М; Е) называется многоосновной алгеброй. )',ругими словами, многоосновная алгебра имеет несколько носителей, а каждая сперация сигнатуры действует из прямого произведения некоторых носителей з некоторый носитель.
2.1.2. Замыкания и подалгебры Подмножество Х с М называется замкнутым относительно операции р, если Чхы...,х„Е Х р(хы...,х„) Е Х. Если Х замкнуто относительно всех р е Е, то (Х; Ех) называется подалгвброй (М; Е), где Ех = (рх),рх = Мх" и = и;. Пример 1. Алгебра (К;+, ) — поле действительных чисел. Тип — (2,2). Все конечные подмножества, кроме (0), не замкнуты относительно обеих операций. Поле раиионагьных чисел (ф+, ) образует подалгебру.
2. Алгебра (2м;и,й, ) — алгебра подмнсзхвств над множеством М. Тип— (2,2,1). При зтом (2»; О, и, ) для любого подмножества Х множества М образует подалгебру. 3. Алгебра ((У ~ У: Е -к Ж) ь вв ), где дв; — операция дифференцирования. Множество элементарных функций образует подалгебру. ТЕОРЕМА Непустое пересечение подалгебр образует подаггвбру. доказательство ПУсть (Хн Е»,) — подалгебРа (М; Е). Тогда Уг УУ У~'(хы..., х„, ) Е Хг =ч =ь тд уд '(хы...,х,ц) и Пхь 2.1. Операции и алгебры Замыканием множества Х с М относительно сигнатуры Е (обозначается [Х]в) называется множество всех элементов (включая сами элементы Х), которые можно получить из Х, применяя операции нз Е.
Если сигнатура подразумевается, ее можно не указывать. Пример В алгебре целых чисел (У,;+, ) замыканием числа 2 являются четные числа, то есть [(2)] = (п и К [ и = 2й йг й и Ж) . Свойства замыкания: 1. ХсУ=ь[Х]с[У); 2. Хс[Х); 3. [[Х]] = [Х]; 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
