Дискретная математика. Ч.1. Основные алгебраические структуры: учебное пособие

Description

Даны основные алгебраические структуры, используемые в дискретной математике и ее приложениях. Приведены примеры, иллюстрирующие рассматриваемые понятия, определения и теоремы. Все разделы снабжены упражнениями для самостоятельной работы, а пособие дополнено набором вариантов домашних заданий. Главная задача учебного пособия заключается в оказании помощи студентам при первоначальном изучении алгебраических понятий дискретной математики и подготовке к изучению соответствующих разделов специальной литературы. Во 2-й части пособия изложены основы комбинаторики, теории графов и сетевых моделей. 3-я часть посвящена математической логике, теории автоматов и сложности вычислений. 4-я часть содержит практические примеры использования дискретных математических моделей в криптографии, помехоустойчивом кодировании, цифровой обработке сигналов и сжатии данных Пособие предназначено студентам специальности «Прикладная математика» факультета «К» НИЯУ МИФИ при изучении курса «Дискретная математика», а также может быть рекомендовано к использованию в учебном процессе факультета «Б». А.Н. ИВАНОВ ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. ОСНОВНЫЕ АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ УЧЕБНОЕ ПОСОБИЕ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РФ ДИСКРЕТНАЯ МАТЕМАТИКА ЧАСТЬ 1. ОСНОВНЫЕ АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ И 17 Во 2-й части пособия изложены основы комбинаторики, теории графов и сетевых моделей. 3-я часть посвящена математической логике, теории автоматов и сложности вычислений. 4-я часть содержит практические примеры использования дискретных математических моделей в криптографии, помехоустойчивом кодировании, цифровой обработке сигналов и сжатии данных Пособие предназначено студентам специальности «Прикладная математика» факультета «К» НИЯУ «МИФИ» при изучении курса «Дискретная математика», а также может быть рекомендовано к использованию в учебном процессе факультета «Б». Рецензент доцент каф. 42 И.А. Юров DiscrMath1_part2_open.pdf ПРЕДИСЛОВИЕ Если каждому элементу D поставить в соответствие его самого, то получится биективное отображение А( А1, т.е. А( А1(В, что и требовалось доказать.( Упражнения Полугруппа может иметь элемент е, такой что (a(A е*а = a*е = а. Таким образом, множество упорядоченных пар элементов группы отображается на группу. Таблица умножения группы полностью описывает это отображение. Первые элементы всех пар 2.4. Факторгруппы Э.Галуа первым показал, что смежные классы группы G по ее нормальной подгруппе К образуют группу, элементами которой являются множества элементов другой группы. Поэтому сначала необходимо определить бинарную операцию на множестве смежных классов группы G по нормальной группе К. Определение. (Произведением двух смежных классов R и S (упорядоченным) является множество всех упорядоченных пар {rs}, где r(R и s(S. ( Покажем, что если R и S – смежные классы группы G по ее нормальной подгруппе К, то R*S также будет смежным классом группы G по ее подгруппе К, т.е. операция взятия произведения является бинарной операцией на множестве смежных классов по подгруппе К. Если А является произвольной подгруппой G, то А*А = А, т.к. произведение любых двух элементов из подгруппы А принадлежит к А и, вместе с тем, умножая все элементы из А на единицу, получим уже всю подгруппу А. Пусть А будет теперь нормальным делителем группы G. Тогда, используя ассоциативность умножения подмножеств группы, равенства А*А=А и уА=Ау, (х,у(G получим хА*уА=хуА*А= хуА. Последнее равенство показывает, что для нахождения произведения двух данных смежных классов группы G по ее нормальному делителю А, следует произвольным образом выбрать в этих смежных классах по одному представителю и взять тот смежный класс, в котором лежит произведение этих представителей. 2. Роль единицы играет сам нормальный делитель А, являющийся одним из смежных классов разложения группы G по А, а именно, ввиду равенств А*А = А и хА = Ах, для любого х(G получим хА*А = хА А*хА = хА*А = хА. DiscrMath1_part3_open.pdf Кольца R и Q называются изоморфными, что обозначается в виде R(Q( Пример 61.(Кольцо всех квадратных матриц порядка n с действительными элементами изоморфно кольцу всех линейных преобразований, реализуемых в действительном n-мерном линейном векторном пространстве (с обычным сложением и умножением преобразований).( Определение.(Подгруппа А аддитивной группы кольца R называется подкольцом R, если (а1,а2(R ( а1а2(R. Подкольцо А кольца R называется левым (соответственно правым) идеалом кольца, если (а(А,(r(R ( аr(A (соответственно rа(A). В коммутативных кольцах понятия левого и правого идеала совпадают. Двусторонним идеалом кольца R называют подкольцо А, являющееся одновременно и левым и правым идеалом кольца R. Все кольцо R является идеалом самого себя и называется единичным идеалом. Элемент ( содержится в любом идеале. Подмножество {(}, содержащее лишь нулевой элемент кольца R, также является идеалом и называется нулевым идеалом. По отношению включения единичный идеал – это наибольший, а нулевой – наименьший среди всех идеалов. Все остальные идеалы называются нетривиальными идеалами. Кольцо, не имеющее никаких двусторонних идеалов, кроме единичного и нулевого, называется простым. ( Теорема 22 (теорема о гомоморфизмах колец). Для всякого гомоморфизма (: R(Q кольца R на кольцо Q существует изоморфизм Q на факторкольцо R/К кольца R по ядру К=Ker ( гомоморфизма (. Более точно, для эпиморфизма ( существует однозначно определенный изоморфизм ( кольца R/Ker ( на кольцо Q такой, что эпиморфизм ( является результатом последовательного применения канонического эпиморфизма (, а затем – изоморфизма (. Пусть f(х) = (аixi (0 ( i ( n) – ненулевой многочлен над Fq . Значит можно считать, что аn(0. Тогда аn называется старшим коэффициентом f(х), а0 - постоянным членом, а n - его степенью, обозначаемую символом deg(f)= deg(f(х))=n. Для удобства примем, что deg (() = - (. Многочлены f(х), у которых deg(f)(0, называются постоянными многочленами (или константами). Если старший коэффициент многочлена f(х) равен 1 (единице) Fq , то многочлен называют нормированным (или приведенным). Напомним, что многочлен над Fq назывется нормированным, если его старший коэффициент равен 1. Следствие теоремы DiscrMath1_part5_open.pdf Приложение 1. Варианты домашних заданий Вариант 27 Александр Николаевич Иванов Дискретная математика 5.pdf Приложение 1. Варианты домашних заданий Вариант 27 Александр Николаевич Иванов Дискретная математика 1.pdf ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РФ ДИСКРЕТНАЯ МАТЕМАТИКА ЧАСТЬ 1. ОСНОВНЫЕ АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ И 17 Во 2-й части пособия изложены основы комбинаторики, теории графов и сетевых моделей. 3-я часть посвящена математической логике, теории автоматов и сложности вычислений. 4-я часть содержит практические примеры использования дискретных математических моделей в криптографии, помехоустойчивом кодировании, цифровой обработке сигналов и сжатии данных Пособие предназначено студентам специальности «Прикладная математика» факультета «К» НИЯУ МИФИ при изучении курса «Дискретная математика», а также может быть рекомендовано к использованию в учебном процессе факультета «Б». Рецензент доцент каф. 42 И.А. Юров