Новиков Ф.А. Дискретная математика для программистов (860615), страница 16
Текст из файла (страница 16)
Например, в этом учебнике рассматривается изоморфизм множеств (1.2.2), линейно упорядоченных множеств (1.8.6), графов (7.1.6).ОТСТУПЛЕНИЕТермин «морфизм», вынесенный в название раздела, используется как собирательное понятие, подобно тому, как в объектно-ориентированном программировании используетсятермин «абстрактный класс». Напомним, что абстрактный класс — это класс, не могущийиметь непосредственных экземпляров, по являющийся обобщением (предком) некоторыхконкретных классов, которые могут иметь непосредственные экземпляры.2.2.
Алгебры с одной операциейЕстественно начать изучение алгебраических структур с наиболее простых. Самой простой структурой является алгебра с одной унарной операцией. Здесьэтот случай не рассматривается, хотя он достаточно содержателен. Следующимпо порядку сложности является случай алгебры с одной бинарной операцией*: М х М —• М, который и рассматривается в этом разделе.2.2.1. ПолугруппыПолугруппа — это алгебра с одной ассоциативной бинарной операцией:а * (Ь * с) — (а * Ь) * с.Примеры1. Множество непустых слов А+ в алфавите А образует полугруппу относительно операции конкатенации (см. 1.8.8).2. Всякое множество тотальных функций одного аргумента {/ | / : М —> М],замкнутое относительно суперпозиции, является полугруппой.Если в полугруппе существует система образующих, состоящая из одного элемента, то такая полугруппа называется циклической.82Глава 2.
Алгебраические структурыПример (N;+) является циклической полугруппой, поскольку {1} являетсясистемой образующих.2.2.2. Определяющие соотношенияПусть Р = (М; *) — полугруппа с конечной системой образующих А,АеМ,А= { а ь . . . ,о„}. Тогда\Лт G М (3yi,...,yk€ А {х ==у1*...*ук)).Если опустит!» обозначение операции *, то всякий элемент а € М можно представить как слово о; в алфавите А, то есть М с А+.
Обозначим через а элемент,определяемый словом а. Слова а и (3 могут быть различными, но соответствующие им элементы fv и j3 могут быть равны: а = (3, а,(3 е А+, а,(3 е М. Такиеравенства называются определяющими соотношениями. Если в полугруппе нетопределяющих соотношений и все различные слова, составленные из образующих, суть различные элементы носителя, то полугруппа называется свободной.Всякая конечно-порождённая полугруппа может быть получена из свободнойвведением определяющих соотношений. Пусть в конечно-порождённой полугруппе некоторый элемент а определяется словом а, причём а =и заданоопределяющее соотношение 7 = а. Тогда вхождение слова 7 в слово а можно заменить словом а, причём полученное слово (Заб будет определять тот жесамый элемент а. Такое преобразование слова будем называть применением определяющего соотношения.
Два слова в алфавите А считаются равными, если одноиз другого получается применением определяющих соотношений, то есть словаравны, если равны определяемые ими элементы. Отношение равенства слов в полугруппе с определяющими соотношениями является отношением эквивалентности. Классы эквивалентности по этому отношению соответствуют элементамполугруппы.Примеры1.
В полугруппе (N; +) имеется конечная система образующих {1}. Другими словами, каждое натуральное число можно представить как последовательностьзнаков 1. Очевидно, что различные слова в алфавите {1} суть различныеэлементы носителя, то есть эта полугруппа свободна.2. Пусть полугруппа У задана системой двух образующих {а, 6} и двумя определяющими соотношениями, аа = а и ЬЪ = Ь. Следующий элементарный алгоритм определяет, равны ли два слова, а и /3, в полугруппе Т.Вход: входные слова а : array [l..s] of {a,b} и (3 : array [1 ..t] of {a, 6};Выход: значение выражения a = (3 в полугруппе У.if a[l] Ф (3[ 1] thenreturn false { первые буквы не совпадают }end ifNa := 0 { счётчик изменений буквы в а }for i from 2 to з doif a[i] Ф a[i - 1] then832.3.
Алгебры сдвумяоперациямиNa := Na + 1 { буква изменилась }e n d ifend forN/з : = 0 { счётчик и з м е н е н и й буквы в @ }for г from 2 to t doif fi[i) ф p\i - 1] t h e nNp := Np + 1 { буква изменилась }e n d ifend forr e t u r n Nn = Np { слова равны, если з н а ч е н и я счётчиков одинаковы }В предыдущем примере о п р е д е л я ю щ и е соотношения таковы, что равенство любых слов как элементов легко проверяется. О д н а к о это не всегда так.(Марков 1 -Пост 2 ) Существуетравенства слов алгоритмическиТЕОРЕМАзнаванияДОКАЗАТЕЛЬСТВОполугруппа, в которой проблеманеразрешима.распо-( Б е з доказательства).•ЗАМЕЧАНИЕТермин «алгоритмическая неразрешимость» принадлежит теории алгоритмов, которая нерассматривается в этом учебнике, а потому строгое определение этого термина здесьне приводится.
Неформально можно сказать, что проблема называется алгоритмическинеразрешимой, если не существует программы (алгоритма) её решеиия. Здесь словосочетание «не существует» означает не то, что программа ещё не составлена, а то, чтотребуемая программа не может быть составлена в принципе. В теории алгоритмов строгоустановлено, что алгоритмически неразрешимые проблемы существуют. Приведём простое наблюдение, которое не является строгим доказательством последнего утверждения,но может служить косвенным намёком на причины существования алгоритмически неразрешимых проблем. Пусть в конечном алфавите А задано слово А, А 6 А* и язык L, L С А*.Проблема: определить, принадлежит ли слово А языку L? Обозначим через PL{OL) программу, которая для заданного слова А € А* выдаёт 1, если А € L, и выдаёт 0 в противномслучае.
Множество всех программ не более чем счётно (просто потому, что всякая программа — это слово в конечном алфавите). В то же время множество всех языков несчётно,потому что это множество всех подмножеств счётного множества. Таким образом, заведомо существуют языки, для которых не существует программы, распознающей все словаэтого языка. Приведённое наблюдение не является доказательством, потому что мы неопределили, как именно задаются объекты a, L и PL(Q:).П р и м е р Г. С. Ц е й т и н 3 нашел легко о п и с ы в а е м ы й п р и м е р полугруппы, в которой проблема равенства слов алгоритмически неразрешима. В этой полугруппевсего пять образующих {а, 6, с, d, е} и семь о п р е д е л я ю щ и х соотношений:ас = са;ad = da;be = cb\bd = db\1Андрей Андреевич Марков (1903-1979).2Эмиль Леон Пост (1897-1954).3Григорий Самуилович Цейтип (р. 1937).abac = abace;eca — ae\edb = be.84Глава 2.
Алгебраические структурыТем не менее невозможно составить программу, которая бы для любых заданныхслов в алфавите {а,6, с, d, е} проверяла, можно ли преобразовать одно слово вдругое применением указанных определяющих соотношений.ОТСТУПЛЕНИЕНекоторые программисты полагают, что если в условиях задачи всё дискретно и конечно,то для решения такой задачи программу можно составить в любом случае (используя метод «полного перебора»). Предшествующие теорема и пример показывают, что это мнениеошибочно.2.2.3. МоноидыМоноид — это полугруппа с единицей:З е (Va (а * е = е * а = а)).ЗАМЕЧАНИЕЕдиницу также называют нейтральным элементом.Примеры1.
Множество слов А* в алфавите А вместе с пустым словом е образует моноид.2. Пусть Т — множество термов над множеством переменных V и сигнатурой Е.Подстановкой, или заменой переменных, называется множество парСт ={ti//Vi}i£j,где U — термы, а Vi — переменные. Результатом применения подстановки ак терму t (обозначается ta) называется терм, который получается заменойвсех вхождений переменных Vi соответствующими термами U. Композицией подстановок а\ = {U//vi}i£iи= {tj//vj}jGjназывается подстановка(7i о а2{tk//vk}keK,где К = IU J , а{исг2,tj,если к е / ,если к £ I.Множество подстановок образует моноид относительно композиции, причёмтождественная подстановка {vi//vi} является единицей.ТЕОРЕМА 1Единица моноида единственна.Пусть существуют две единицы: ei,e2- Тогда е\ * е2 = е\ к, е\ *е\ = е2.•ДОКАЗАТЕЛЬСТВО* е2 = е22.3.
Алгебры сдвумяоперациями85ТЕОРЕМА 2 Всякий моноид над М изоморфен некоторому моноиду преобразований над М.Пусть М = (М; *) — моноид над М = {е, а, Ь, с, . . . } . ПостроимЭ' = (F; о) — моноид преобразований над М, гдеF: = {fm: Af-> М | fm(x): = х * т}теМ ,ДОКАЗАТЕЛЬСТВОа о — суперпозиция функций, h: М —»• F, /г(га): = / т . Тогда — моноид, поскольку суперпозиция функций ассоциативна, / е — тождественная функция (так какf e ( x ) = х * е = х ) и F замкнуто относительно о, так как f a ° f b =fa*bfa*b(x)= х * (а * b) = (х * а) * b = f a ( x ) * 6 = f b ( f a { x ) ) . Далее, /г — гомоморфизм,так как /г(а * Ь) = /а*ъ — fa ° fb — h(a) о /г(Ь).
И наконец, h — биекция, поскольку h — сюръекция по построению, и h — инъекция (так как (/ а (е) = е * а =- а & /ь(е) = е * Ь = Ь ) ^ { а ф Ь = > / а ф / ь )).•2.2.4. ГруппыТеория групп, некоторые положения которой рассматриваются в этом подразделе, является ярчайшим примером мощи алгебраических методов, позволяющих получить из немногих базовых понятий и аксиом множество важнейшихследствий. Группа — это моноид, в которомVa ( З а - 1 (а * а - 1 = а - 1 * а — е)) .Элемент а"1 называется обратным, а операция * называется умножением.ЗАМЕЧАНИЕТак как операция умножения в группе пе обязательно коммутативна, то, вообще говоря,свойства a - 1 * а = е и а * а - 1 = е пе равносильны.
Можно было бы различать обратныеслева и обратные справа элементы. Введенная аксиома требует существования двустороннего обратного элемента. Можно показать, что она следует из более слабых аксиомсуществования левой единицы и левого обратного элемента.Мощность носителя G группы S называется порядком группы и обозначается |G|.Примеры1. Множество невырожденных квадратных матриц порядка п образует группуотносительно операции умножения матриц. Единицей группы является единичная матрица (единицы на главной диагонали, остальные элементы равнынулю). Обратным элементом является обратная матрица.2.
Множество перестановок на множестве М, то есть множество взаимно однозначных функций / : М —у М, является группой относительно операции суперпозиции. Единицей группы является тождественная функция, а обратнымэлементом — обратная функция.86Глава 2. Алгебраические структурыТЕОРЕМА 1Обратный элемент единственен.Пусть а * а - 1 = а - 1 *a = e&ca*bДОКАЗАТЕЛЬСТВО= а- 1* е = аТЕОРЕМА 2- 1= b*a = е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
