Реферат: Дискретная математика

\bookfoldsheets0Федеральное агентство по образованию РФ

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

(КОНСПЕКТ ЛЕКЦИЙ)

Преподаватель: профессор,Архипов ИгорьКонстантинович

1. МНОЖЕСТВА

Множество– совокупность элементов, обладающих каким-то одним общим свойством. (Этоопределение не является строгим, оно лишь показывает особенности построения множеств,т.е. для построения множества важно указать свойство, которым обладают все егоэлементы).

Если каждому элементу множества можно присвоить номери этот номер не повторяется, то такое множество называется счетным или конечным.

Если такого номера для каждого элемента не существует,то такое множество называется бесконечным.

Бесконечноемножество часто называют континуумом (например: совокупность точек наплоскости).

Еслиможно пересчитать все число элементов в счетном множестве, то эта сумманазывается мощностью множества.

Множествазадаются различными способами:

1. С помощью перечисления всех егоэлементов.

{0,1,2,3,4,5,6,7,8,9}

2. Алгоритмическая форма (в видепоследовательности или фомул).

а) конечное

М={2;4;6;8} <=> М={m|2n;n-целое;1<=n<=4}

б) бесконечное

А={х| |х-1|<3}

2. СВОЙСТВА СЧЕТНЫХ МНОЖЕСТВ

1. Всякое подмножество счетногомножества конечно или счетно

Подмножеством множества А называется множество А`все элементы которого принадлежат множеству А

Пример: />

2. Сумма конечного или счетногочисла конечных или счетных множеств есть конечное или счетное множество.

3. Множество всех рациональных чисел счетно.

4. Алфавитом называется любое непустое множество.

Пустое множество – множество, которое не содержит ни одного элемента.

Элементы множества под названием АЛФАВИТ называют буквами(символами).

Символом вданном алфавите любая конечная последовательность букв.

Для каждого множества А существуют множества,элементами которого являются только все его подмножества.

Такое подмножество называют семейством множеств А илибулеаном. (обозначается В(А))

Будем называть вектором (кортежем) упорядоченныйнабор элементов и обозначать его />,заметим, что в отличие от множества, элементы в векторе могут повторяться. Этиэлементы называются координатами или проекциями.

Количествоэлементов в векторе называется его длиной, если в векторе 2 элемента, тодвойка, если n элементов, то n-ка.

Теориямножеств строится на основе систем аксиом.

1. Аксиома существования: Существует по крайней мере одно множество.

2. Аксиома объемности: Если множества А и В составлены из однихи тех же элементов, то они совпадают.

3. Аксиома объединения: Для произвольных множеств А и Всуществует множество, элементами которого являются все элементы множества А и все элементы множества В и никакие другие элементы множество несодержит.

4. Аксиома разности: Для произвольных множеств А и Всуществует множество, элементами которого являются те и только те элементымножества А, которые не содержатся в множестве В.

5. Аксиома существованияпустого множества: Существуетмножество не содержащее ни одного элемента.

3. ОСНОВНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

1. Включение(объединение)

Множество А входит (включено) в множество В,или А является подмножеством В. />

Если всякий объект, обладающий свойством />, также обладает свойством />, то говорят, что свойство /> включает свойство />, т.е. />

2. Сумма

Сумма множеств А и В есть множество С,включающее в себя все элементы множество А и В.

Объект входит во множество /> если он входит вомножество А или во множество В.

3. Пересечение (произведение)

Пересечениеммножество А и В называется новое множество С. Элементымножества С принадлежат множеству А (обладают его свойствами) имножеству В (обладают его свойствами).

4. Вычитание (разность)

Разностьмножеств А и В есть множество С, элементы которогообладают свойствами множества А и не обладают свойствамимножества В или принадлежат множеству А и не принадлежатмножеству В.

5. Дополнение

Еслиимеется некоторое универсальное множество (универсум) Uи все рассматриваемые множества есть его подмножества, то дополнением /> называется такоемножество, элементы которого не входят в А, но принадлежат U.

ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

(Диаграммы Эймера, Венна)

/>1.

В А 3.

U />4.

4. ПРЯМОЕ ПРОИЗВЕДЕНИЕ А х В

Прямым произведением множеств А и В называетсямножество М всех пар (/>),таких, что />

Если А=В, то такое произведение называется />

Аналогично можно вывести операцию прямого произведениябольшего числа множеств.

Если в частности />одинаковы/> то получаем />

(Например, множество точек на плоскости являютсяпрямым произведением двух множеств).

Если множества конечные, мощность произведений /> равна мощностипроизведений />

5. ОСНОВНЫЕ ТОЖДЕСТВА АЛГЕБРЫ МНОЖЕСТВ

Независимостьрасположения:

/> (1)

/> (2)

Ассоциативность:

/> (3)

/> (4)

Дистрибутивность:

/> (7)

/> (8)

/> (9)

/> (10)

/> (11)

/> (12)

ЗАКОНЫ де Моргана

6. ЭЛЕМЕНТЫКОМБИНАТОРИКИ И ИХ ПРИМЕНЕНИЕ В ТЕОРИИ МНОЖЕСТВ

Основная задача комбинаторики– пересчет и перечисление элементов в конечных множествах.

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

2. Если необходимо выделить всеэлементы множества, обладающие заданными свойствами, то это задачаперечисления.

Рассмотрим следующиеэлементы комбинаторики, позволяющие решать вышеупомянутые задачи. К такимобъектам относятся:

- перестановки (с повторением ибез них);

- размещения (с повторением и безних);

- сочетания (с повторением и безних);

Перестановкаминазывают комбинации, состоящие из одних и тех же элементов и отличающиесятолько порядком их расположения. Число всех возможных перестановок обозначается/> (без повторений).

Перестановки с повторениями вычисляются по формуле:

/>, где /> - числоповторений элементов каждого вида.

Сочетаниемназываются такие комбинации элементов, которые отличаются между собой в каждойгруппе только самими элементами (но не порядком их расположения в группе).

/> (без повторения)

/> (с повторением)

Размещениемназываются такие комбинации элементов, которые отличаются между собой илисамими элементами или порядком их расположения в группе.

/> (без повторения)

/> (с повторением)

7. ПРИНЦИПЫ МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

При вычислении элементовмножеств требуется приводить доказательство, по которому вычисляютсяпоследующие элементы по предыдущим. Один из алгоритмов этих доказательств – принципматематической индукции.

Этот принцип заключаетсяв следующем:

Пусть при n=1 доказательство очевидно. Принимаем гипотезу, что оноочевидно при n=k,которое не равно 1 (/>). Тогда, еслидоказано, что требуемое равенство очевидно при k+1,то равенство доказано при любом n.

8. ОТОБРАЖЕНИЕ ОТНОШЕНИЯ ФУНКЦИИ

Понятие отображения ифункции выражают зависимостью одних переменных величин от других, при этомслово величина может иметь различную смысловую нагрузку. Это может быть элементлюбого множества, число, вектор и т.д.

Отображение –множества x во множество yопределяется тем, что каждому элементу />ставитсяв соответствие />

/> - графическое изображениеотображения, f – обозначение отображения.Закон, который выражается или в виде формулы или в виде алгоритма, т.е.последовательность действий, которые надо предпринять, чтобы получитьзависимость элементов множества y от элементов x. Например: всякая нумерация счетного множества являетсяего отображением на множество натуральных чисел N.

Так как отображениеможет быть истолковано как соответствие, то для того, чтобы показать, чтоданный элемент x поставлен в соответствиеэлементу y, пишут /> иговорят, что y есть образ элемента x при данном отображении f.

Пусть x` — подмножество множества x

y` — подмножество множества y

тогда

Совокупность элементовмножества x, образом которых является y, называется прообразом и обозначается />

Рассмотрим частныеслучаи отображения одного множества в другое.

1. Есликаждый элемент множества Y имеет прообраз, являяющийсяэлементом множества X, то в этом случае отображениеf называется сюръективным.

2. Отображениеf называется инъективным, если для каждогоэлемента />существует не более одногопрообраза, т.е. при любых />, если />.

Если отображение f сюръективнои инъективно, то оно называется биеткивным или взаимооднозначным.

Рассмотрим на примеретри функции, отображающие множество Fдействительных чисел само на себя:

1) /> - инъективна, но несюръективна т.к. />, однако некаждый y имеет прообраз xт.к. y>0

2) /> - сюръективна, но неинъектина, т.к. y существует при любом x, однако для образа yсуществует несколько прообразов, т.к. существует несколько корней кубическогоуравнения />

3) /> - биективна, т.к. x однозначно выражается через xи x однозначно выражается через y.

Два множестваназываются эквивалентными, если между ними можно установить биективноеотображение.

ТОГДА:

Подмножество /> называется функцией />.

Таким образом функциюможно представить в виде графика, причем множество А – областьопределения функции, а множество В – область значения функции.

Рассмотрим, например,взаимно однозначное отображение множества R на R1, где R1 есть множествовсех положительных чисел />.Обратным ему будет отображение />. Длятаких отображений справедливо следующее тождество:

9. КОМПОЗИЦИЯ

/>, то их композицией(произведением) называют />,причем, если осуществляется композиция, то />.В математике такое отображение называют сложной функцией, y– промежуточный аргумент.

Для композиции справедливо следующие отображения:

- коммутативное — />

- ассоциативное — />

10. БИНАРНЫЕ ОТНОШЕНИЯ

Квадратом множестваА называется декартово произведение множества само на себя />

Бинарным отношениемТ в множестве А будем называть подмножество его квадрата

1. Отношение /> выполняется дляпар (6,8) (6,6)

2. Отношение имеет общий делитель не равный 1. Выполняетсядля пар (6,4) (4,2) (8,8) но не выполняется для пар (5,4)(3,8)

3. Любые элементы декартова произведения /> находятсяв бинарном отношении, если />,говорят, что /> связаны отношением Т.

4. Областью значений (изменением бинарного отношения) называется множество />, подчиненное условию

Как известно из курса математики пару (x,y), где /> изображают на координатнойплоскости точкой, тогда множество /> отобразитсякоординатной плоскостью, а его подмножество, т.е. бинарное отношение отобразитсясоответствующими графиками этих отношений.

(1)

(2)

Бинарные отношения на плоскости можно отобразить спомощью графов. Элементы множества /> обозначаютсявершинами графов. Если пара />, товершины а и в соединяются звеном.

Например:

(ав)(вс)(ас)(аа)

11. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ

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

СВОЙСТВА:

1. 1.1 Пусть /> - бинарноеотношение, /> - область его задания,тогда /> называется рефлексивным,если />, граф таких отношенийимеет вид петли при каждой вершине

1.2 />называется антирефлексивным,если />

2. 2.1Отношение может быть симметричным, если

/>(изображается любым графом)

2.2 Антисимметричным, если /> (изображаетсяориентированным графом)

3. 3.1 Транзитивным. Отношение называется транзитивным, если /> (изображается транзитивнымграфом – все вершины пересекаются)

Если для бинарного отношения />соблюдаетсятри условия: рефлексивность, симметричность и транзитивность, то такоеотношение называется эквивалентностью.

12.МАТРИЦЫ И ГРАФЫ

Понятие матрицы. Виды матриц. Свойства матриц.Линейные операции над матрицами. Единичные матрицы. Обратные матрицы

Матрицей называетсяпрямоугольная таблица чисел размером />, где m – число строк, а n –число столбцов.

Если m=n – матрица называется квадратной.

Если m-1 – матрица-строка.

Если n=1 – матрица-столбец.

Все числа, входящие вматрицу называются ее элементами. Если все элементы состоят их нулей, то это нулеваяматрица, она играет роль нуля в матричном исчислении.

Рассмотрим некоторые линейные операции надматрицами:

1. Сумма

/> />

Исходя из определения можно складывать ивычитать матрицы только одного размера.

2. Произведениематрицы на число называется матрица, где каждый элемент матрицыумножается на это число.

3. Матрицаумножается на матрицу по правилу строка на столбец

/>/>

/> <td/>

такоеправило не годится для всех матриц, а именно, количество строк во второйматрице должно равняться количеству столбцов в первой матрице.

Квадратныематрицы перемножаются только одного размера.

4. Единичнойматрицей называется квадратная матрица любого размера, где по главнойдиагонали стоят единицы, а все остальные элементы равны нулю.

/>, играет роль единицы в матричномисчислении.