ДИСКРЕТНАЯ МАТЕМАТИКА

Список обозначений

Множество — это совокупность, группа некоторых объектов, называемых элементами, объединенных каким-нибудь общим свойством. Множества обозначают большими латинскими бук­вами: .

— пустое множество, т. е. множество, не имеющее элементов;

— множество всех натуральных чисел;

— множество всех целых чисел;

— множество всех рациональных чисел;

— множество всех действительных чисел;

— множество всех комплексных чисел;

— для всех, для любого;

— существует, найдется;

— существует (найдется) единственный;

Знак заменяет выражение «если и только если»;

Знак заменяет выражение «влечет»;

— элемент принадлежит множеству ;

— элемент не принадлежит множеству ;

— подмножество в { };

— не содержится в ;

— равно, т. е. и ;

— строго содержится в, т. е. и ;

— пересечение множеств и, т. е. {X| X и };

X KJ Y объединение множеств X и Y, т. е. {X .XGX или

};

— разность множеств и, т. е. множество {X X

И };

■ — конец доказательства.

Введение

Дискретная математика в наше время — это обширная наука, которая базируется на классических разделах математи­ки — алгебре, теории чисел, математическом анализе и теории вероятностей. Особенно важны для глубокого понимания мето­дов дискретной математики алгебра и теория чисел. Такие ал­гебраические структуры, как полугруппы, группы, кольца, поля, решетки, булевы алгебры используются во всех видах кодирова­ния информации, в теории графов, теории автоматов, теории бу­левых функций, комбинаторике и математической логике.

Без основательного знания теории чисел также невозможно усвоить многие разделы дискретной математики и успешно применять методы дискретной математики на практике. Более того, даже весьма продвинутая и сложная наука — алгебраиче­ская геометрия находит приложения в теории кодирования.

В данном пособии авторы излагают основные понятия и ме­тоды современной алгебры, а также классические результаты теории чисел, используемые в дискретной математике. Многие результаты даются с доказательствами, так как авторы считают, что глубокое понимание алгебры и теории чисел невозможно без умения доказывать теоремы. Кроме того, в тексте приводится достаточно много примеров вычислительного характера и задач для самостоятельного решения.

Основу данного пособия составили лекции, которые Б. М. Веретеников читал студентам разных специальностей на радиотехническом факультете в течение последних десяти лет. Лекционный материал существенно расширен за счет доказа­тельств и большого числа дополнительных задач. Планируется продолжение, в котором будут рассмотрены конкретные области дискретной математики: теория алгебраического кодирования, алфавитное кодирование, теория автоматов, булевы функции, теория графов и комбинаторика.

Авторы надеются, что чтение пособия поможет читателю усвоить основные методы алгебры и теории чисел и использо­вать их в дальнейшем для изучения различных разделов дис­кретной математики.

Для понимания материала, изложенного в пособии, предва­рительной особой подготовки не требуется. Определенную ма­тематическую культуру можно развить, имея большое желание и достаточное усердие.

В заключение отметим, что авторы предполагают использо­вание пособия студентами и преподавателями УрФУ различных факультетов и специальностей.

Глава I. Бинарные отношения
§
1. Определение и способы задания
бинарного отношения

Определение. Пусть некоторое множество. Тогда множе­ство упорядоченных пар ( ), где, называется Де­

Картовым квадратом множества и обозначается или

. Кратко ( ) .

Аналогично определяется любая натуральная степень мно­жества.

Определение. Множество A^ = {(A^, …,α⅛)∣Vi = 1, Jc ∈ Л}

Называется ^-й степенью множества A.

Определение. Пусть A — конечное множество, состоящее из П элементов. Тогда число П называется ПоряДком множества A и обозначается ∣A∣.

Определение. Бинарным отношением на множестве A называется любое подмножество р декартова квадрата AxA.

Отметим очевидные примеры бинарных отношений:

• A x A == — универсальное отношение на A;

Ф — пустое бинарное отношение;

• ( ) — диагональ.

Если — конечное множество, то любое бинарное отноше­ние на можно задать списком упорядоченных пар, содержа­щихся в этом бинарном отношении. Например, на множестве

{ } можно задать следующие бинарные отношения:

Pι = {( 1, 2),(2, 2),(3, 1)}, P2 = {(3, 2)},^

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *