Дискретная математика Попов и др

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ Федеральное государственное автономное образовательное учреждение

высшего профессионального образования САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

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

МНОЖЕСТВА. КОМБИНАТОРИКА.

Методические указания для студентов заочной формы обучения

Санкт-Петербург

2013

1

Составители: доцент, канд.техн.наук В.П.Попов, профессор, д-р техн.наук В.В.Михайлов

Рецензент: доцент, канд. техн. наук, Н.В.Соловьев

Методические указания по дисциплине “Дискретная математика“ включают разделы “Теория множеств” и “Комбинаторика” с вариантами заданий для самоконтроля.

Предназначены для студентов заочной формы обучения по направлению 230100.62 “Информатика и вычислительная техника” Ивангородского гуманитарно-технического института (филиала) ФГАОУ ВПО “Санкт-Петербургский государственный университет аэрокосмического приборостроения”.

Подготовлено на кафедре прикладной математики и информатики Ивангородского гуманитарно-технического института (филиала) ФГАОУ ВПО “Санкт-Петербургский государственный университет аэрокосмического приборостроения”.

2

ПРЕДИСЛОВИЕ

Разделы дискретной математики теория множеств и комбинаторика тесно связаны друг с другом. Первый раздел учебно-методического издания посвящен представлениям в области классической теории множеств, которая является основой таких областей математики как комбинаторика, теория групп, отображения, перестановки, преобразования, топология, общая алгебра и др. Определѐнные представления в области теории множеств позволяют лучше усвоить второй раздел пособия – комбинаторику. Комбинаторика ориентирована на решение задач выбора и расположения элементов некоторых множеств. Во втором разделе рассмотрены задачи традиционной комбинаторики – размещения, перестановки, сочетания, раскладки, разбиения. Отдельные (весьма немногочисленные) примеры могут вызвать некоторые затруднения, но они будут преодолены если не при первом, то при повторном чтении данного учебно-методического издания. Учебнометодическое издание подготовлено в соответствии с требованиями ФГОС и программой дисциплины “Дискретная математика “, разработанной в ГУАП.

1 Элементы теории множеств

1.1 Понятие множества

В математике часто интересуются не отдельными объектами, а целыми классами объектов, например:

совокупность всех целых чисел;

совокупность всех натуральных чисел;

совокупность всех простых чисел;

совокупность всех треугольников;

совокупность всех букв и т.д.

Иногда, такие совокупности состоят из бесконечного (беcчисленного) множества отдельных элементов. Математики всегда интересовались понятием бесконечности. Но первые попытки изучения бесконечности привели к многочисленным парадоксам. Например, парадоксы Зенона (греческий философ). Первый парадокс - парадокс летящей стрелы (невозможность движения): чтобы стрела пролетела какой-то путь, сначала она должна преодолеть половину пути. Но прежде чем преодолеть полпути, надо преодолеть четверть пути, восьмую часть пути, шестнадцатую часть и т.д. Так как процесс деления пополам никогда не кончится (вот она бесконечность), то стрела никогда не сможет сдвинуться с места. Второй парадокс - сможет ли Ахиллес догнать Черепаху?

Прежде чем знакомиться со свойствами множеств, надо определить : а) что такое множество; б) какие действия можно выполнить над ними.

К сожалению, основному понятию теории множеств – понятию “множества” – дать точное, строгое определение не возможно.

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

3

а) – “совокупность” элементов (тогда надо дать определение “совокупности”). Например, “совокупность” – это набор элементов, что в свою очередь потребует определения термина “набор” и т.д. Такие вложенные определения будут повторяться до бесконечности.

б) – “собрание” элементов – те же проблемы. в) – “система”, “класс” – те же проблемы.

Это всѐ не математические определения, а использование словарного богатства русского языка ( его избыточности ). Чтобы определить какое-либо понятие, надо указать, частным случаем какого, более широкого понятия является определяемое понятие. Для понятия множества это не возможно, т.к. оно само является наиболее широким и не в каких других понятиях не содержится. Точно таким же неопределяемым понятием является термин “элемент“. Часто ,некоторые объекты объединены некоторым общим признаком, например:

-множество стульев в комнате,

-множество всех клеток человеческого тела,

-множество картофелин в данном мешке,

-множество студентов конкретной группы.

Для того ,что бы указать ,что данное множество M состоит из элементов а обычно пишут :

M={а} .

Здесь фигурные скобки { } обозначают, что элементы а объединены в одно целое – множество M. Например, а – каждый студент конкретной группы, M – множество студентов конкретной группы.

Факт принадлежности элемента а множеству M записывают с помощью символа , т.е. а M.

Читается эта запись т.о. “элемент а принадлежит множеству M”. Если же элемент b не принадлежит множеству M ,то пишут либо b M, либо b M.

Например, M – множество четных чисел, тогда 4 M , а 3 M . Основатель теории множеств – немецкий математик Георг Кантор, создал еѐ

приблизительно в 1870 г.

Если множество содержит конечное число элементов, его именуют конечным, а если в нем бесконечно много элементов, то именуют бесконечным. Например, множество деревьев парка – конечное, а множество точек на окружности

– бесконечно.

Мощность множества M – это число его элементов. Обозначается мощность | M |.

1.2 Способы задания множества

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

способ применим только к конечным множествам ( да и то не ко всем ). Примеры задания множеств:

4

1) Первый способ - задать множество перечислением его элементов ( самый простейший способ ). Например, множество студентов данной группы определяется их списком в групповом журнале: а,b,с,d,е M , множество стран на земном шаре определяется их списком в географическом атласе мира, множество элементов таблицы Менделеева.

Перечислительный, или явный способ задания множеств, неудобен в случае, когда элементов множества очень много, и совсем непригоден для задания бесконечных множеств. Кроме того, даже в тех случаях, когда явное задание множества является возможным и легким, но оно затуманивает сам смысл рассматриваемого множества, и скрывает причины, побудившие нас объединить в одно множество именно эти, а не другие элементы. Гораздо более распространен иной, неявный или описательный способ задания множеств.

2)Второй способ задания множеств, когда множество нельзя задать списком,

–указать некоторое характеристическое свойство, которым обладают элементы множества, т.е. сформулировать правило определения принадлежности элемента множеству. Например:

- множество синтаксических ошибок в тексте программы;

- множество натуральных чисел (числа целые, положительные и 0) Z+; - множество целых чисел Z;

- множество всех действительных чисел R.

По второму способу, в приведѐнных примерах, мы задали все множества общими свойствами их элементов. Другие примеры задания множеств по второму способу:

а) множество M - это решения тригонометрического уравнения вида

	sin x 1 x		2 n,
		2

где n- произвольный элемент множества Z (множества целых чисел);

б) множество групп первого курса какого либо факультета MГ. Каждый элемент множества MГ является множеством конкретных студентов, т.е. MГ является множеством множеств.

Бесконечные множества можно задавать только описательным способом. Любая совокупность элементов некоторого множества M именуется

подмножеством. Это же понятие возникает каждый раз, когда приходится рассматривать множество не как самостоятельное, а как часть другого, более широкого множества. Если множество В является подмножеством другого множества А, т.е. каждый элемент х из множества В является и элементом множества А, то в этом случае пишут B A или A B .

Эти два соотношения имеют один и тот же смысл: множество А содержит множество В в качестве своей части. Чисто внешне, эти соотношения близки к записям и В < А и А > В .

1.3 Основные операции над множествами

5

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

1) объединение (сумма) множеств - это образование единого (целого) множества из нескольких множеств. Объединением (суммой) нескольких множеств А, В, … называют новое множество, состоящие из тех и только тех элементов, которые входят хотя бы в одно из слагаемых множеств. Символ объединения множеств или +, соответственно объединение (сумму) множеств А и В , обозначают A B или А+В.

Следует отметить, что отдельные элементы могут входить не только в одно, а в несколько объединяемых (слагаемых) множеств. В этом случае всѐ равно они входят в сумму только один раз. Поэтому, для конечных множеств число элементов суммы может оказаться меньше, чем сумма числа элементов слагаемых множеств.

Это можно представить геометрически (рисунок 1). Пусть множество А состоит из точек фигуры, заштрихованной горизонтальными линиями, а множество В состоит из точек фигуры заштрихованной наклонными линиями, тогда множество А+В или A B, т.е. их объединение, составляет вся заштрихованная фигура.

A`

B

Рисунок 1

Очевидно, что операция объединения (сложения) множеств обладает многими свойствами сложения чисел. Так, выполняются:

а) переместительный закон (коммутативный)

А+В = В+А;

б) сочетательный закон (ассоциативный)

А+(В+С) = (А+В)+С .

6

Множества А+(В+С) или (А+В)+С можно обозначить и без скобок:

А+В+С,

т.к. сумма их представляет объединение всех трѐх множеств А,B и С. Геометрически это выглядит т.о. ( рисунок 2 ),

A`

B

C

Рисунок 2

т.е. объединение множеств А,В и С – это вся заштрихованная область.

Валгебре множеств есть особые множества:

–пустое множество;

–множество – единица.

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

Иногда появляется мысль вовсе исключить из рассмотрения подобное пустое множество: ведь если оно не содержит элементов, то это вообще не множество (и нечего о нѐм говорить). Однако, поступать так, было бы подобным исключению числа 0 из совокупности чисел: ведь набор из нуля предметов так же является пустым набором и говорить о числе предметов, содержащихся в этом наборе, как будто бессмысленно. Но на самом деле это совсем не бессмысленно, а очень даже осмысленно. Если бы мы не имели числа 0 ,то не могли бы вычесть одно из другого любую пару чисел, например 3-3. При отсутствии числа 0 эта разность вообще бы ничему не равнялась. Нам было бы трудно записывать в позиционной десятичной системе счисления, скажем, число 10810 - одна сотня, восемь единиц и совсем никаких десятков.

И ещѐ многое мы не смогли бы сделать, поэтому идея возникновения нуля

7

считается одним из	выдающихся (замечательных) событий во			всей истории
арифметики. Поэтому, если множество			– пустое множество,	то для любого
множества А: А +	=А.

Несколько сложнее обстоит дело с “множеством-единицей”. Это множество будем обозначать буквой I, похожей по написанию на число 1. Множество-единица - это универсальное множество, его смысл аналогичен роли единицы. Значение этого множества мы оценим после того, как рассмотрим операцию пересечения (произведения) множеств. Рассмотрим несколько примеров объединения множеств. Пусть два множества имеют элементы M1 = {a,b,c,d}, M2 = {b,c,e,p} .

Их объединение будет множество M3, элементы которого: M3=M1+M2 или

M3= M1 M2 ={a b,c,d,e,p}.

Пусть –M, множество студентов ( юношей ) группы,

– M2 множество студеток ( девушек ) группы.

Тогда M1 M2 будет множество всех обучающихся в этой группе.

2) Вторая операция над множествами – пересечение (произведение, умножение) множеств. Пересечением множеств А и В называют новое множество, содержащее те и только те элементы, которые входят в каждое из множеств А и В

.Т.е. пересечение множеств – это общая часть этих множеств. Обозначение пересечения множеств – символ или A∙B (как в алгебре).

Геометрический смысл этой операции (рисунок 3) следующий: если множество А состоит из точек фигуры заштрихованной горизонтальными линиями, а множество В – состоит из точек фигуры ,заштрихованной наклонными линиями ,то пересечением этих множеств А∙В или А В будет фигура из горизонтальных и наклонных линий ( т.е. покрытая решеткой ).

A
`
	B

Рисунок 3

Кстати, название операции “пересечение” происходит от того ,что при пересечении двух геометрических фигур , получают множество точек пересечения обоих фигур в самом обычном смысле этого слова. Т.к. пересечением множеств является новое множество, элементами которого будут элементы, принадлежащие одновременно как одному, так и другому множеству, то для множеств M1 и M2 предидущего примера M4 = M1 M2 , или M4 =M1∙M2 , или M4 ={b,c}.

8

Если имеются два множества M1={a,b,c,d,e} и В={1,2,3}, то их пересечение не содержит ни одного общего элемента, точнее содержит пустое множество элементов, и это будет записываться так: M1 B = .

Например, пусть А – множество умеющих играть в шахматы в студенческой группе, а В – множество пловцов ( умеющих плавать ) в этой же группе, тогда А∙В или А В есть множество тех шахматистов, которые умеют плавать.

Для пересечения (умножения) множеств выполняются:

а) переместительный (коммутативный ) закон А∙В=В∙А или А В = В А, т.е. понятно ,что “множество А∙В это множество шахматистов, которые умеют

плавать”, и “множество плавцов, которые умеют играть в шахматы”- это одно и тоже множество.

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

Геометрически (рисунок 4) это означает, что при пересечении трѐх множеств А,В,С, множество А∙В∙С покрыто тройной штриховкой

A`

B

C

Рисунок 4

в) для любых трѐх множеств А,В и С выполняется также распределительный (первый дистрибутивный ) закон: (А+В)∙С=А∙С+В∙С.

Вернѐмся к особым множествам – пустое множество и множество-единица. Если бы не причислять к числу множеств пустое множество , то мы не смогли бы указать пересечения любых двух множеств, например таких, как представлено на рисунке 5.

9

`	B
A	`

Рисунок 5

Пересечение множеств А и В пустое, как например множество студентов в группе и множество слонов. Вот почему мы писали

А+ =А .

Вернѐмся к множеству-единице I. Это множество такое ,что пересечение (произведение) его и любого множества А совпадает с А. Это множество I должно содержать вообще все элементы всех множеств. В таком случае под I будем понимать “самое большое множество”, содержащее все рассматриваемые нами элементы (предметы) в предыдущих множествах (множество студентов в группе, множество всех элементов в таблице Менделеева, множество всех точек квадрата ). Это особое множество I (рисунок 6) в алгебре множеств называется единичным или универсальным множеством.

I

Рисунок 6

Очевидно ,что для любого множества из “меньших множеств”, например А (даже если А совпадает с I), мы будем иметь: А∙I =А и А+I =I.

В этом глубокое отличие единичного множества от числа 1 .Какое бы множество А мы не сложили (объединили) с единичным, получим тоже множество I, т.к. по определению множество I является “самым большим” и поэтому увеличить ещѐ его уже невозможно. В заключение отметим ещѐ два закона алгебры множеств, противоречащих представлениям, полученным при изучении элементарной алгебры. Очевидно ,что каким бы ни было множество А,

10