Новиков Ф.А. Дискретная математика для программистов (860615), страница 14
Текст из файла (страница 14)
Пусть 2м — булеан над линейно упорядоченным конечным множеством М,а частичный порядок на булеапе — это включение. Тогда функция min(X),X с М из алгоритма 1.12, доставляющая минимальный элемент, являетсямонотонно убывающей, но не строго монотонной.3.
Пусть порядок на булеапе 2м — это собственное включение. Тогда функция,которая сопоставляет подмножеству X с М его мощность, X\Х\, являетсястрого монотонно возрастающей.1.8.6. Вполне упорядоченные множестваЧастично упорядоченное множество X называется вполне упорядоченным, еслилюбое его непустое подмножество имеет минимальный элемент. В частности,для любых двух элементов a,b е X один из них обязан быть минимальнымв подмножестве {а, 6}, а значит, вполне упорядоченное множество упорядоченолинейно.ЗАМЕЧАНИЕНе надо путать вполне упорядоченные множества и множества, на которых определён линейный (или полный) порядок.
Линейно упорядоченное множество может не быть вполнеупорядоченным.Примеры1. Всякое конечное линейно упорядоченное множество вполне упорядочено.2. Множество натуральных чисел N с обычным отношением порядка вполнеупорядочено.3. Множество рациональных чисел Q с обычным отношением порядка не является вполне упорядоченным, так как множество X : = { z e ( Q ) | x 2 > 2 } , равнокак и само множество Q, не имеет минимального элемента.4. Множество вещественных чисел М с обычным отношением порядка не является вполне упорядоченным, так как множество X : = {х £ К | х > 0}, равно каки само множество Е, не имеет минимального элемента.Говорят, что два линейно упорядоченных множества А и В изоморфны (обозначение А ~ В), если между ними существует взаимио-одпозпачное соответствие,сохраняющее порядок:А ~ В =Г \А\ = |Я| &(Vai,a 2 Е А (аг -< а2 к ахbi к а2Ь2 ==> Ьх -< Ь2)).Другими словами, два линейно упорядоченных множества Aw В изоморфны, если между ними существует строго монотонно возрастающее взаимно-однозначноесоответствие.72Глава 1.
Множества и отношенияЗАМЕЧАНИЕПоскольку вполне упорядоченные множества упорядочены линейно, понятие изоморфизма применимо и к вполне упорядоченным множествам.Пример Множества натуральных чисел и чётных чисел с обычным порядком < изоморфны, поскольку соответствие п у-> 2п является строго монотонновозрастающим.1.8.7. ИндукцияВажность вполне упорядоченных множеств определяется тем, что для них можнообобщить принцип индукции, применяемый обычно для множества натуральныхчисел.Т Е О Р Е М А (Индукция по вполне упорядоченному множеству) Пусть X — вполнеупорядоченное множество их о — его минимальный элемент, а Р — некоторый предикат, зависящий от элементов X.
Тогда еслиР(х 0 ) k Vxi е X ((Vx е X (х •< xiР(х)))Р(хО),тоWxeX(Р(х)).Обозначим Р: = {х е X \ Р(х)}, Р с X. Далее от противиого.Пусть Р Ф 0 . Поскольку X вполне упорядочение, Р имеет минимальный элемент, обозначим его х\. Тогда Vx € X (х -< х\ =$> Р{х)) по выбору х\ и значитР{хi) по условию теоремы, что противоречит выбору х\.•ДОКАЗАТЕЛЬСТВОЗАМЕЧАНИЕОбычная математическая индукция соответствует индукции по вполне упорядоченномумножеству натуральных чисел N.Индукция по вполне упорядоченному множеству сильнее обычного принципаматематической индукции в силу следующей замечательной теоремы.ТЕОРЕМАЛюбое множество может быть вполне упорядочено.Данное утверждение эквивалентно так называемой аксиоме выбора в теории множеств и само может быть принято за аксиому.
Мы опускаем доказательствоэквивалентности этой теоремы аксиоме выбора.73КомментарииПримерРассмотрим множество положительных рациональных чиселгде т и п взаимно просты.Определим отношение -< на множестве Q+ следующим образом:Ш1Ш2Def^. . ,рх— -< — = mi < т2 V (mi = т2 & п\ < п2),п1п2где < — обычное отношение порядка на N. Нетрудно видеть, что множество Q+с отношением -< является вполне упорядоченным, в то время как с обычнымотношением порядка < оно таковым пе является, см.
1.8.6.1.8.8. Алфавит, слово и языкВ этом подразделе вводятся некоторые термины, которые пе имеют прямого отношения к теории множеств, но часто используются в различных приложенияхи в следующих главах, а потому рассматриваются в первой главе. Пусть заданоконечное множество А = { a i , . . . , ап}, которое называется алфавитом. Элементы алфавита называются буквами, или символами. Обычно отдельные символыобозначаются начальными буквами латинского алфавита. Конечная последовательность букв называется словом (в данном алфавите), или цепочкой.
Буквы вслове линейно упорядочены (слева направо) и могут быть перенумерованы. Одна буква может входить в слово несколько раз, каждый отдельный экземплярбуквы в слове называется вхождением буквы в слово. Вхождения могут бытьидентифицированы, например, номером буквы в слове. Обычно слова обозначаются начальными буквами греческого алфавита. Множество слов в алфавите А.обозначается А*. Если слово а =...
ak G А*, то количество букв в слове называется длиной слова: |а| = \а\... ак\ = к. Пустое слово обозначается е, |е| = f О,е А, но е 6 А*. Если пустое слово исключается из рассмотрения, то множествослов в алфавите А обозначается А+. Таким образом, А* =А+ = А* -£. Дляслов определена операция конкатенации, или сцепления. Конкатенацией слов с* и/3 является слово а(3, полученное выписыванием подряд сначала всех букв словаа, а потом всех букв слова (3. Обычно операция сцепления никак не обозначается. Если а = aict2, то a i называется началом, или префиксом, слова а, а а2 —окончанием, или постфиксом, слова а.
Если при этом а.\ Ф £ (соответственно,а2 ф е), то a i (соответственно, а2) называется собственным началом (соответственно, собственным окончанием) слова а. Произвольное множество L слов внекотором алфавите называется языком в этом алфавите, L с А*.КомментарииОсновные сведения, изложенные в этой главе, можно найти в любом учебнике по (дискретной) математике.
Алгоритм 1.1 тривиален. Алгоритмы 1.2 и 1.3описаны в [8]. Алгоритмы 1.4-1.7 — общеизвестный программистский фольклор. Автору неизвестны другие публикации алгоритмов 1.8-1.10, несмотря на74Глава 1. Множества и отношенияих очевидность. Алгоритм 1.11 описан во многих источниках, например, в [2].Алгоритм 1.12 описан в фундаментальной книге [14], которая входит в «золотойсписок» обязательного чтения любого программиста.Упражнения1.1. Существует ли множество всех множеств?1.2. Доказать, что A U В = (А П В) U (А П В) U (А П В).1.3. Доказать, что Q(2k + га) = Q(2к - тп) для 0 < га < 2к - 1, где Q — функцияиз алгоритма 1.3.1.4. Пусть Q = f {(га, п) | m, п е N к га = п 2 }.
Какими свойствами обладает отношение Q?1.5. Доказать вторую теорему из подраздела 1.5.1.1.6. Доказать теорему из подраздела 1.6.3.1.7. Доказать, что если = — отношение эквивалентности на конечном множествеМ и \М\ = IМ/ = |, то Vx е М (|[х] = | = 1).1.8. Пусть А — линейно упорядоченное множество с отношением порядка R.Введем отношение R на множестве кортежей элементов из А следующимобразом:(ах,...
,am)R(bi,...Def,bn) = (т^пkVi6 1 ..га (а* =V (Зг G l..m ((aiRbi к V j € 1..г - 1 (а* = bj)))).Такое отношение называется лексикографическим, или алфавитным, порядком. Доказать, что алфавитный порядок есть линейный порядок на множестве кортежей А + = f U S i ^ •Глава 2АлгебраическиеструктурыАлгебраические методы находят самое широкое применение при формализацииразличных предметных областей. Грубо говоря, при построении модели предметной области всё начинается с введения подходящих обозначений для операцийи отношений с последующим исследованием их свойств.
Владение алгебраической терминологией, таким образом, входит в арсенал средств, необходимых дляабстрактного моделирования, предшествующего практическому программированию задач конкретной предметной области. Материал этой главы, помимо введения в терминологию общей алгебры, содержит некоторое количество примеровконкретных алгебраических структур.
Вначале бегло рассматриваются классические структуры, которые обычно включаются в курсы общей алгебры, а затемобсуждаются некоторые более специальные структуры, наиболее часто применяемые в конкретных программных построениях. Особого внимания заслуживаетпонятие матроида, обсуждаемое в этой главе, поскольку матроиды тесно связаныс важнейшим классом эффективных алгоритмов, называемых жадными.2.1. Алгебры и морфизмыСловом «алгебра» называют, вообще говоря, не только раздел математики, но иодин из конкретных объектов, изучаемых в этом разделе.
Поскольку «алгебры» вузком смысле здесь не рассматриваются, для краткости и без риска возникновения недоразумений слово «алгебра» в этом учебнике используется как родовоепонятие для обозначения разнообразных алгебраических структур.2.1.1. Операции и их носительВсюду определённая (тотальная) функция <р\ Мп —> М называется п-арной(п-местной) операцией на М. Если операция <р — бинарная (ip: М х М —• М), тобудем писать в инфиксной форме a<pb вместо <р(а, Ь) или а*Ь, где * — знак операции. Множество М вместе с набором операций £ =. .
. , </?m}, щ: Mni —• M,где щ — арность операцииназывается алгебраической структурой, универсальной алгеброй или просто алгеброй. При этом множество М называется основным (несущим) множеством или основой (носителем); вектор арностей ( щ , . . . , пт)76Глава 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
