Курс лекций: Элементы дискретной математики

4- Курс лекций

Элементы дискретной математики

  СОДЕРЖАНИЕ: Лекция 1.Начала теории множеств

Лекция 1. Начала теории множеств.

План: 1. Понятие множества 2. Операции над множествами.

Рис. 11.6

Если A Ì В, то разность АВ называется дополнением множества А до множества В. Дополнение некоторого множества А до универсального множества U обозначаетсяили ùА. Таким образом, если А Ì В, то U можно представить в виде объединения двух непересекающихся множеств:

U = А È В

Говорят при этом, что множество U разбито на два множества на А и . Аналогичному разбиению можно подвергнуть множество А, или множество , или то и другое. При этом мы получим более мелкое разбиение исходного множества U. Этот процесс можно продолжить и далее. В итоге получим представление множества U в виде объединения попарно непересекающихся подмножеств: кратко U = , где А_i ÇА_j=Æ, если i≠j .

Для наглядного изображения соотношений между подмножествами какого-либо универсального множества используют диаграммы Эйлера-Венна (Джон Венн (1834—1923) — английский математик.). Само универсальное множество U, изображают в виде прямоугольника, а его подмножества — в виде кругов, расположенных внутри прямоугольника. Множества, полученные в результате операций над множествами А и В, изображены на рис. 11.6, а — в заштрихованными областями. Непересекающиеся множества, изображаются неперекрывающимися областями (рис. 11.7, а), а включение множества соответствует области, целиком располагающейся внутри другой (рис. 11.7, б). Дополнение множества А (до U), т.е. множество А изображается той частью прямоугольника, которая лежит за пределами круга, изображающего А (рис. 11.7, в).

Рис. 11.7

 

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

1.= А;

2. А È А = А, А ÇA = А;

3. А È = U, А Ç= А,

4. А È U = U, А Ç U = А,

5. А È Æ = А, А Ç Æ = Æ,

6. (закон де Моргана), (закон де Моргана);

7. АÈВ= В ÈА (коммутативность и),

А ÇВ = ВÇА (коммутативность п

8. А È (В È С) = (А È В) È С (ассоциативность È),

А Ç (В Ç С) = (А Ç В) Ç С (ассоциативность Ç)

9.А È (В ÇС) = (А È В) Ç (А È С) (дистрибутивность È относительно Ç);

А Ç (В È С) = (А Ç В) È (А Ç С) (дистрибутивность Ç относительно È).

Проверим для примера закон де Моргана . Пусть х Î . Тогда хÎ U и хÏ АÈВ. Следовательно, х Ï А и х Ï В. Отсюда хÎ и хÎ , и потому х Î Ç . Таким образом,

(11.1)

Если теперь хÎ Ç, то х Îи х Î . Отсюда х Î U и х Ï А, х Ï В. Значит, хÏ А È В, т. е. х Î . Итак,

(11.2)

Включения (11.1) и (11.2) в силу теоремы 11.1 и доказывают закон де Моргана.

Пользуясь операциями объединения, пересечения и вычитания множеств, можно из некоторых исходных множеств А, В, С и т.д. по­лучать новые множества: (АÈВ) Ç, (A) È(С) и т.д. К этим множествам можно применять указанные операции и получать еще более сложные выражения и т.д. Законы 1 — 9 позволяют преобразовывать эти выражения, упрощать их, из одних получать другие. Таким образом, получаем исчисление множеств, или алгебру множеств. Это исчисление является примером так называемой булевой алгебры, или алгебры Буля.

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

Предположим, что существует правило, по которому каждому элементу из D ставится в соответствие определенный элемент из Е. Тогда это правило называют отображением множества D в Е (рис. 11.8).

Например, каждому человеку земного шара можно поставить в соответствие цвет его волос. Так будет определено отображение множества людей в шкалу цветов. Подобно этому можно определить отображение множества людей в множество имен, множества книг в множество языков и т.д. Вместо слова «отображение» говорят также «функция» и, если задано отображение множества D в Е, то говорят, что на множестве D задана (определена) функция со значениями в Е. Для обозначения функции мы будем, как правило, использовать букву f. Эта договоренность не помешает нам при нужде использовать и другие буквы g, h, f, С и т. п.

Если на множестве D определена некоторая функция f со значениями в Е, то общий элемент множества D обозначается обычно х и называется независимой переменной или аргументом этой функции, а отдельные конкретные элементы множества D называются значениями аргумента. Значения аргумента часто обозначают той же буквой, что и сам аргумент, с прибавлением каких-либо индексов, например, х₀, х₁, х_n и т.п. Элемент из Е, соответствующий элементу х Î D, в силу правила f называется значением функции f элементе х и обозначается f (x) (читается: «эф от икс»).

Рис. 11.9

Множество D называется областью определения функции f Множество всех элементов f(х), соответствующих элементам хÎА, где А — произвольное подмножество множества D называется образом множества A и обозначается f(A). В частности, f(D) называется областью значений функции f. Область значений f(D) есть подмножество множества Е, которое в общем случае может и не совпадать со всем Е. Если же f(D) = Е, то говорят, что f есть отображение D на Е.

 

 

 

Две функции f и g равны (тождественны, совпадают), если совпадают их области определения, и если для любого х из области определения имеет место равенство

f (x) = g(x).

Если разным элементам х Î D, соответствуют разные элементы f (x) ÎЕ, то отображение f, называют взаимно однозначным (рис. 11.9).

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

Если f взаимно однозначное отображение, то каждому элементу YÎ f (D) можно поставить в соответствие определенный элемент хÎD, именно тот, значение функции на котором равно у. Так будет установлено отображение образа f (D) на множество D. Это отображение называется обратным по отношению к/и обозначается f ^-1.

Если образ f (D) есть подмножество множества D, то говорят, что функция f отображает D в себя. Например, функция f= sin x отображает все множество действительных чисел на подмножество этого множества — промежуток [-1, 1].

Вопросы для контроля знаний и подведения итога прочитанной лекции

1. Что понимают под термином «множество» и под элементами множества?

2. Как обозначаются и изображаются множества?

3. Укажите основные виды операций над множествами.

4. Что называют отображением множества D в Е?

 

 

Лекция 2. Комбинаторика

План: 1. Метод математической индукции. 2. Перестановки

Два правила перечисления в комбинаторике

Правило суммы. Если элемент А может быть выбран m способами, а элемент В другими n способами, то выбор "или А, или В" может быть… Правило произведения. Если элемент А может быть выбран т способами, и после…

Комбинаторные задачи

2. Сколько есть вариантов 6-значных чисел, содержащих цифры 1,1,1,3,3,5? 3. Сколько есть вариантов из 3 команд, занявших 3 первых места в турнире из 6… 4. Сколько есть вариантов 3-буквенных слов-кодов из 4 букв (А-аденин, Т-тимин, Г-гуанин, Ц-цитозин) для кодирования…

Перестановки

Перестановки без повторений

Пример. Перестановки из 3 различных элементов а, b и с: аbс, bса, саb, сbа, bас, асb. Число всех перестановок из п различных элементов (обозначается Рп) есть Рп=… Действительно, выберем какой-то один элемент из п различных. Его можно разместить среди последовательности п-1…

Таблица. Значения факториалов первых натуральных чисел и нуля.

N=	0
n!=	1

Решением задачи 1 является Р₆ = 6!= 720 различных вариантов расстановки на полке 6 различных книг.

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

Пример. Перестановки из 3 элементов, среди которых 2 одинаковых элемента типа а и 1 элемент типа b: ааb, аbа, bаа. Число перестановок из т элементов, среди которых k1 одинаковых элементов 1-го типа, k2 одинаковых элементов 2-го типа,..., kп одинаковых элементов n-го типа [обозначается Р (m; k1,k2 ,...,…

Размещения.

Размещения без повторений

Пример. Размещения из 3 различных элементов а,b и с по 2: аb, bа, ас, са, bс, сb. Число всех размещений из элементов п различных типов по т (обозначается ) есть = =n!/(n-m)!

Размещения с повторениями

Пример. Размещения с повторениями из 3 элементов а, b и с по 2: аb, bа, ас, са, bс, сb, аа, bb, cc. Число всех возможных размещений из га различных элементов по т (обозначается )… Действительно, в последовательности из т элементов n различных типов имеется т позиций. Поскольку элементы в разных…

Сочетания

Сочетания без повторений

При этом т < n, поскольку не допускается повторение элементов в их неупорядоченном наборе из т элементов. (Здесь и далее под неупорядоченным… Иногда сочетания называют разбиениями или композициями и даже размещениями.… Пример. Сочетания из 3 элементов а, b и с по 2 : аb(=bа) , ас(=са) , bс(=сb).

Сочетания с повторениями

При этом возможно т > п, поскольку допускается повторение элементов в их неупорядоченном наборе из т элементов. Пример. Сочетания с повторениями из элементов а, b и с по 2: аb(=bа), ас(=са),… Число всех сочетаний с повторениями элементов л различных типов по неупорядоченным наборам из т элементов…

Сочетания с повторениями и ограничением на встречаемость элементов каждого типа

Пример. Сочетания с повторениями из элементов а, b, с по 4, когда каждый тип элементов в любое сочетание входит хотя бы один раз: ааbс, аbbс,… Число всех сочетаний с повторениями элементов п различных типов по т… (m³n)= , где т ³п — необходимое условие, чтобы такие сочетания существовали.

Разбиения с фиксированными размерами частей

А. Неупорядоченные разбиения с фиксированными размерами частей

Называем такое разбиение неупорядоченным, таккак семейство — это неупорядоченнаясовокупность. Пример.Для множества {а,b,с} неупорядоченное разбиение это, например,… Для множества с п элементами обозначим через D(n; k1, k2,…, kn) число всех таких неупорядоченных разбиений,в которых…

Числа Стирлинга второго рода

S(n, k) = 0 для k > n. S(0, 0) = 1 (существует только один способ разбиения пустого множества на… S(n, 0) = 0 при n > 0.

Теорема 5.1 (рекуррентное соотношение для чисел Стирлинга второго рода).

S(n, n) = 1, n > 0;

S(n, 1) = 1, n > 0;

S(n, k) = S(n – 1, k – 1) + k S(n – 1, k), n > 0.

Доказательство.

В таблице приведены значения, вычисленные с помощью рекуррентного соотношения. Например, S(5, 3) = S(4, 2) + 3S(4, 3) = 7 + 3*18 = 25. Таблица значений для S(n, k )= Sп k Sп k k= 1 …

СПРАВОЧНЫЕ МАТЕРИАЛЫ ПО РАЗБИЕНИЯМ.

 

Числа Стирлинга второго рода

I. Определения.

— число способов разбиения множества изп элементов на т непустых подмножеств. В. Производящиефункции:

Неупорядоченные разбиения (все)

А. р(п) — число разбиений целого числа n на целые слагаемые независимо от их порядка. Например, 5=1+4=2+3=1+1+3=1+2+ + 2 = 1 + 1 + 1 + 2 = 1 + I + 1 + 1 + 1, так… В. Производящая функция:

Биномиальные коэффициенты (числа сочетаний без повторений )

А. или есть число способов выбора т предметов из собрания т различных предметов независимо от их порядка. В. Производящие функции:

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

А. - или E(n; m1, m2,…, mk) - число способов помещения различных предметов в т различных ящиков, где пk — число предметов в k-м ящике, k= 1,2,...… — число перестановок символов, составленных из циклов длины k для k= 1,2,...… или D(n; k1, k2,…, kn)— число всех возможных разбиений множества из различных предметов на подмножества , содержащие k…

Вопросы для контроля знаний и подведения итога прочитанной лекции

2. В чем состоят два основных правила перечисления в комбинаторике? 2. Что называют перестановкой без повторений? 3. Что называют перестановкой с повторениями?

Лекция 3. Алгебра высказываний и булева алгебра.

Цель: Изучить основные понятия булевой алгебры.

План:

1. Высказывания

2. Булевы функции

3. Вопросы для контроля знаний и подведения итога прочитанной лекции

Высказывания

Высказываниями являются, например, следующие предложения: «3x3 = 9», «7 — простое число», «Волга впадает в Черное море». Первые два предложения… Существуют предложения, относительно содержания которых в настоящий момент… Единственным существенным признаком высказывания является то, что оно либо истинно, либо ложно, но не может быть…

Булевы функции

Рассмотрим возможные функции от переменной х ÎD = {0, 1} (такая переменная называется логической переменной). При этом нас будут интересовать… Другой более интересной функцией является отрицание. Эта функция обозначается… Кроме этих двух функций можно указать еще только две функции, отображающие множество {0, 1} в себя. Это постоянные…

Булевы функции двух переменных.

f(х1,х2). (11.8) Так как каждая из переменных х1, х2 может принимать только два значения: 0 и… то областью определения функции (11.8) являются четыре варианта сочетаний: 00, 01, 10 и 11. Приняв эти сочетания за…

Вопросы для контроля знаний и подведения итога прочитанной лекции

1. Что называют отрицанием высказывания р?

2. Что называют конъюнкцией двух высказываний р и q?

3. Что называют дизъюнкцией двух высказываний р и q?

4. Что называют импликацией двух высказываний р и q?

5. Что называют эквиваленцией двух высказываний р и q?