 |
Задание к лабораторной работе.
|
|
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ГОСУДАСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ
ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Методические указания и задания
к лабораторным работам
по курсу “Основы дискретной математики“, часть I
Донецк – 2010
УДК 004.021
Методические указания и задания к лабораторным работам по курсу "Основы дискретной математики, часть 1" (для студентов, обучающихся по направлениям подготовки «Программная инженерия» и «Компьютерные науки» очно-заочной формы обучения) / Сост.: И.А. Назарова. - Донецк: ДонНТУ, 2010. - 104с.
Методические указания и задания к лабораторным работам по курсу "Основы дискретной математики, часть 1" включают лабораторные работы по следующим основным темам курса:
- теория множеств;
- теория отношений;
- комбинаторика;
- булева алгебра.
Составитель: Назарова И.А., к.т.н., доцент
Рецензент: Скобцов Ю.О., д.т.н., профессор
Лабораторная работа № 1
Способы задания множеств. Операции над множествами.
Основные соотношения алгебры множеств
Цель работы: изучение способов задания множеств. Приобретение практических навыков в выполнении операций над множествами и проверке основных соотношений алгебры множеств.
Теоретическая справка
Множество – объединение в одно целое различимых между собой элементов.
Конечное множество – множество, состоящее из конечного числа элементов.
Бесконечное множество – множество, состоящее из бесконечного числа элементов.
Способы задания множеств
1) Перечисление элементов.
Например:
.
2) Задание определяющего свойства.
|
|
|
Например:
;
.
Пустое множество – множество, не содержащее ни одного элемента. Пустое множество обозначается 
или 
.
Универсальное – множество, содержащее все возможные элементы. Универсальное множество обозначается 
.
Утверждение " 
является элементом множества 
" записывается в виде 
( принадлежит множеству ).
Утверждение " а не является элементом множества А " записывается в виде 
(а не принадлежит множеству А).
Множества А и В называются равными (обозначается 
), если они состоят из одних и тех же элементов.
Если каждый элемент множества А является также элементом множества В, то говорят, что А содержится или включается в В.
В этом случае пишут 
.
Множество A называется подмножеством множества B, если .
В тех случаях, когда одновременно имеют место соотношения и 
, говорят, что A строго включается в B, и используют запись 
.
Операции над множествами
Объединением множеств A и B (A È B) называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств, т.е A È B = { а ½ а Î A или а Î B }.
Пересечением множеств A и B (A Ç B) называется множество, состоящее из всех элементов, принадлежащих каждому из этих множеств, т.е. А Ç B = { а ½ а Î А и а Î B }.
Разностью множеств А и B (А \ B) называется множество, состоящее из всех элементов множества A, не принадлежащих множеству B, т.е.
А \ B ={ а ½ а Î А и а Ï B }.
Дополнением множества А в универсальном множестве U (
, ØА) называется множество, состоящее из всех элементов универсального множества U, не принадлежащих множеству А, т.е.
.
Симметрической разностью множеств A и B (обозначается A Å B или 
) называется множество, состоящее из всех элементов, принадлежащих в точности одному из этих множеств, т.е.
A D B = { а ½ либо а Î A и а Ï B, либо а Ï A и а Î B },
A D B = (A \ B) È (B \ A) = (A È B) \ (A Ç B).
Операции над множествами можно проиллюстрировать графически с помощью кругов Эйлера (их также называют диаграммами Венна). В этом случае исходные множества изображают кругами или любыми другими замкнутыми линиями, а множество-результат выделяют штриховкой. Универсум обозначают прямоугольником.
|
|
|
Например:
1) Пусть множества и 
заданы на универсуме 
, 
.
Тогда, 
, 
, 
,
, 
,
, 
.
2) Пусть 
, 
.
Тогда, 
,
, 
, 
,
, 
.
3) 
, 
, 
. Изобразить графически на диаграммах Эйлера множество 
.
, 
, но 
, поэтому результат этой операции штриховкой отметить.
Основные законы алгебры множеств:
1) Коммутативные законы
2) Ассоциативные законы
3)Дистрибутивные законы
4)Законы с Æ и U
А È Æ = А А Ç U = А А È 
= U
А Ç Æ = Æ А È U = U А Ç = Æ
= Æ 
= U
6) Законы идемпотентности
, 
, 
7) Законы поглощения
А È (А Ç В) = А А È ( Ç В) = А È В
А Ç (А È В) = А А Ç ( È В) = А Ç В
8) Законы де Моргана
9) Законы склеивания
Задание к лабораторной работе.
Заданы множества X, Y, Z, U, правила образования:
X – множество букв имени студента;
Y – множество букв отчества студента;
Z – множество букв фамилии студента;
U – универсальное множество = 
È {ъ,ё, гласные, отсутствующие в множествах X, Y, Z }
1.Вычислить:
- X Ç Y, X Ç Z, Y ÇZ, X Ç Y Ç Z;
- Y È Z, X È Y È Z;
- X \ Z, Z \ X; X È 
; X D Z;
- X Ç 
, X È (Y Ç Z); (X \ Z) È (Y \ Z).
2. Нарисовать диаграммы Эйлера для следующих операций:
- X Ç Y Ç Z;
- (X Ç Y) È ;
- (
Ç 
);
- (X \ Z) È (Y \ Z).
3. Проверить экспериментально на множествах X, Y, Z справедливость следующих утверждений:
- 
= 
È ;
- 
= Ç ;
- X \ (Y È Z) = (X \ Y) Ç (X \ Z);
- X \ (Y Ç Z) = (X \ Y) È (X \ Z).
4. Записать булеан для произвольного подмножества множества Z мощности 4. Выписать все возможные разбиения и привести примеры 3 покрытий этого подмножества.
Контрольные вопросы.
1. Дать определение множества.
2. Привести примеры конечных и бесконечных множеств.
3. Указать существующие способы задания множеств.
4. Дать определения пустого и универсального множеств.
5. Что называют подмножеством множества?
6. Ввести понятия операций над множествами.
7. Привести примеры операций над множествами с помощью кругов Эйлера.
8. Записать основные законы и теоремы алгебры множеств
|
|
|
|
|
|
