Учебное пособие 1161
.pdfФГБОУ ВО «Воронежский государственный технический университет»
Кафедра компьютерных интеллектуальных технологий проектирования
XXX-2016
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к выполнению практических работ по дисциплине «Дискретная математика»
для студентов направления подготовки бакалавров 09.03.02 «Информационные системы и технологии» (профиль «Информационные системы и технологии в машиностроении») очно-заочной формы обучения
Воронеж 2016
0
Составители: канд. техн. наук О.В. Собенина, А.А. Пак
УДК 681.3
Методические указания к выполнению практических работ по дисциплине «Дискретная математика» для студентов направления подготовки бакалавров 09.03.02 «Информационные системы и технологии» (профиль «Информационные системы и технологии в машиностроении») очно-заочной формы обучения / ФГБОУ ВО «Воронежский государственный технический университет»; сост. О.В. Собенина, А.А. Пак. Воронеж, 2016. 41 с.
Методические указания содержат необходимые теоретические сведения, примеры выполнения заданий, задачи для самостоятельного решения.
Предназначены для студентов 2 курса.
Методические указания подготовлены в электронном виде и содержатся в файле «Дискретная математика Практические работы.pdf».
Ил. 3. Библиогр.: 9 назв.
Рецензент канд. физ-мат. наук, доц. В.В. Горбунов
Ответственный за выпуск зав. кафедрой д-р техн. наук, проф. М.И. Чижов
Издается по решению редакционно-издательского совета Воронежского государственного технического университета
ФГБОУ ВО «Воронежский государственный
технический университет», 2016
1
1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Теоретические сведения
Под множеством понимается любое собрание определенных и различных между собой объектов, мыслимое как единое целое.
Множества будем обозначать заглавными буквами латинского алфавита; объекты, которые образуют множества, будем называть элементами множества и обозначать малыми буквами латинского алфавита. Если элемент x принадлежит множеству X, то этот факт записывается в виде x , иначе x ..
Множество, содержащее конечное число элементов, называется конечным; в противном случае множество называется бесконечным. Количество элементов конечного множества называется мощностью и обозначается =n, если множество X
содержит n элементов. Если множество не содержит ни одного элемента, то оно называется пустым и обозначается .
Для произвольных множеств X и Y можно определить два типа отношений – отношение равенства и отношение включения.
Два множества считаются равными, если они состоят из одних и тех же элементов. Принято обозначение X=Y, если X и Y равны, и X Y- иначе.
Если каждый элемент множества X является элементом множества Y, то говорят, что X включено в Y и обозначают
: (x x ).
Вэтом случае говорят, что множество X является подмножеством множества Y. В частности X и Y могут совпадать, поэтому называется также отношение нестрогого включения.
Если и , то говорят, что X есть собственное подмножество Y и обозначают , отношение между мно-
1
жествами в этом случае называется отношением нестрогого включения.
Невключение подмножества X в множество Y обозначает-
ся ( ).
Заметим, что если X является подмножеством Y и наоборот, то X и Y состоят из одних и тех же элементов, поэтому
( и ).
Для каждого множества X существует множество, элементами которого являются различные подмножества множества X. Такое множество называется семейством множества и обозначается p(X) [1, 2].Так как включено в любое множество, то
p( ).
Пример. Пусть x1, x2 , x3 . Тогда
p( ) x1 , x2 , x3 , x1,x2 , x1,x3 , x2 ,x3 , x1,x2 ,x3 , .
Если в рамках некоторого рассуждения рассматриваются подмножества некоторого множества, то оно называется универсальным, или универсумом и обозначается U [7].
Множество может быть задано различными способами [1, 2, 6]: перечислением элементов в скобках (для конечных множеств) или указанием их свойств, однозначно определяющих принадлежность элементов данному множеству, при этом используется запись
X={x x обладает свойством P(x)}
(выражение в скобках читается: множество всех элементов x, которые обладают свойством P(x). Так, множество натуральных чисел N={1,2,…} может быть описано следующим образом:
N={i если целое i N, то i 1 N,i 1}.
2
Операции над множествами
Объединением множеств X и Y называется множество, все элементы которого являются элементами множества
X или Y: ={x |
x или x Y }. |
Пересечением множеств X и Y называется множество
, элементы которого являются элементами обоих мно-
жеств X и Y: ={x | x X и x Y}.
Очевидно, что выполняются включения ;
.
Дополнением множества X называется множество всех
тех элементов x, которые не принадлежат множеству X: ={x | x U и x X}.
Разностью множеств X и Y называется множество X\Y всех тех элементов X, которые не принадлежат Y:
X\Y={x x и x }=X Y .
Абсолютное дополнение множества Х представляется с помощью операции относительного дополнения следующим
образом =U\X.
Симметричной разностью множества X и Y называется множество ( \ ) ( \ ).
Свойства операций над множествами
1., (коммутативность);
2.( ) ( ) , ( ) ( )
(ассоциативность);
3.( ) ( ) ( ),
( ) ( ) ( ) (дистрибутивность);
4., ;
5.U U, U ;
6.U, (комплиментарность);
7 . , (идемпотентность);
3
8., (законы де Моргана);
9.X (двойное отрицание);
10.( ) , ( ) (з-н поглощения).
Декартовым (прямым) произведением множеств X и Y на-
зывается множество упорядоченных пар вида
{(x,y) x и y }.
Примеры решения задач
Задача 1.
Пусть на универсуме E={a, b, c, d, e, f, g} определены множества X={a, c, d, f}, Y={b, d, e, f}. Найти X Y, X Y, , X\Y, Y\X, X Y.
Решение. X Y={ a, b, c, d, e, f}, X Y={d, f}, ={b, e, g}, X\Y={a, c}, Y\X={b, e}, X Y={a, b, c, e}.
Задача 2.
Равны ли следующие множества:
1){2, 4, 5} и {2, 4, 5, 2};
2){1, 2} и {{1,2}};
3){1, 2, 3} и {{1}, {2}, {3}}.
Решение. Для доказательства равенства произвольных множеств нужно проверить, что первое множество включено во второе, а второе включено в первое, т. е. любой элемент первого множества является элементом второго множества, а любой элемент второго множества является элементом первого.
1) Да. Это можно наглядно показать на следующей схеме, где стрелочка, идущая от элемента, показывает, какой элемент в
другом множестве ему соответствует. |
|
|
|
||||
{2, |
4, |
5} |
|
{2, |
4, |
5, |
2} |
{2, |
4, |
5, |
2} |
{2, |
4, |
5} |
|
|
|
|
|
4 |
|
|
|
2)Нет. Так как, например, элемент 1 из первого множества не имеет себе равного во втором множестве. Второе множество состоит из единственного элемента – множества {1, 2}.
3)Нет. Так как элементами первого множества являются числа 1, 2, 3, а элементами второго множества являются множества, состоящие из одного элемента {1}, {2}, {3}.
Задача 3.
Множество задано перечислением элементов А={2, 4, 6, 8, …, 32}. Задайте множество с помощью характерного для его элементов свойства.
Решение. Множества А представляет собой множество четных натуральных чисел от 2 до 32, поэтому это множество можно записать в виде
А={x N / x =2n, n=1,…, 16}.
Задача 4.
Доказать A (B C) = (A B) (A C).
Решение. Чтобы доказать равенство двух множеств X = Y нужно доказать, что X Y и X Y. Докажем, что A (B C) (A B) (A C). Для доказательства этого включения выберем произвольный элемент из множества A (B C) и покажем, что он принадлежит множеству (A B) (A C). Итак, пусть x A (B C). Тогда x A и x B C. Если x B, то x A B, а значит, x (A B) (A C). Если x C, то x A C, а значит, x (A B) (A C). Таким образом, A (B C) (A B) (A C).
Теперь докажем, что (A B) (A C) A (B C). Пусть x (A B) (A C). Если x A B, то x A и x B, отсюда следует, что x A и x B C, т.е. x A (B C). Если x A C, то x A и x C. Отсюда следует, что x A и x B C, т.е. x A (B C).
Итак, (A B) (A C) A (B C). Таким образом, получили, что
A (B C) (A B) (A C) и (A B) (A C) A (B C), а это значит, что эти два множества равны.
Решение подобных задач можно оформить в более формализованном виде, используя “{” для системы высказываний,
5
объединенных союзом “и”, “[”- для системы высказываний, объединенных союзом «или».
Задача 5.
Доказать тождество (A \ B)\C (A \C)\(B \C). Решение. Используя свойства операций над множествами,
покажем, что правую часть выражения с помощью равносильных преобразований можно привести к левой.
(A\C)\(B\C) (A C) (B C) (A C) (B C)
(A C) (B C) (A C B) (A C C)
(A C B) (A ) (A C B) A C B
A \ B \C
Задача 6.
Доказать тождество B (A\ B) .
Проведем доказательство методом от противного. Предположим, что множество B (A\ B) не пусто, т. е. существует хотя бы один элемент
x B, |
x B, |
x B, |
|
|
|
x B (A\ B) |
x A, x A, |
|
x A\ B |
|
|
|
x B |
x B. |
Никакой элемент x не может одновременно принадлежать самому множеству и его дополнению, поэтому мы пришли к противоречию.
Задача 7. Упростить выражение
(A B Y X) (A Y) (B Y) (Y X).
Решение.
(A B Y X ) (A Y ) (B Y ) (Y X ) (A B
Y X) (Y (A B X)) (Y (A B X))
(Y (A B X )) Y ((A B X ) (A B X ))
Y E Y .
6
Задача 8. Доказать закон де Моргана . Решение. С одной стороны,
|
|
x U |
|
x |
x |
||
x |
|
|
|
|
|
|
|
X Y |
|
|
|||||
|
|
x |
|
x |
|
|
|
|
|
|
x |
|
x .
Сдругой стороны,
x |
|
|
|
|
x |
x U |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
x |
|
x x x .
Так как и , то
, что и требовалось доказать.
Задачи и упражнения
1.Докажите тождество (А B) (А B)= А .
2.Докажите, что B (A\C) (B A)\(B C).
3.Упростите (A B) (A B) (A B).
4.Докажите тождество
[(A X) (B X)] (A X) (B X).
5.Упростите A\((A B) \ B).
6.Докажите закон поглощения X (X Y) X .
7.Докажите, что X (Y\ X) .
8.Решить систему соотношений относительно множества
Хи указать условия совместности системы
B\ X AB X CA B C
7
2. БИНАРНЫЕ ОТНОШЕНИЯ
Теоретические сведения
В множестве X n-местным или n-арным отношением называется подмножество R n-й декартовой степениn = .... заданного множества, R n , называется носителем отношения [2, 6, 7]. Одноместное отношение называется унарным, или свойством, и соответствует подмножеству множества X. Особую роль в приложениях играют бинарные отношения R Х Х. Каждому бинарному отношению можно поставить в соответствие матрицу бинарного отношения, которую также будем обозначать через R= rij n n(n ) и
элементы которой rij определяются по следующему правилу:
1, если (xi,xj ) R
rij =
0, если (xi,xj ) R
Свойства бинарных отношений Отношение R называется
рефлексивным, если для х Х (х, х) R;
антирефлексивным, если х Х (х, х) R; симметричным, если для х, у Х ((х,у) R (у,х) R);
антисимметричным, если для х, у Х ((х, у) R (у, х) R); транзитивным, если для x, у, z ((х, у) R и (у, z) R (x, z) R.
Матрица бинарного отношения содержит единицы на главной диагонали, если отношение является рефлексивным; такая матрица является симметричной относительно главной диагонали, если отношение симметрично; для антисимметричного отношения произведение элементов, расположенных симметрично относительно главной диагонали, равно нулю.
Пусть на множестве Х задано отношение U тогда
8