Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Задание к лабораторной работе.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ГОСУДАСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

 

 

Методические указания и задания

к лабораторным работам

по курсу “Основы дискретной математики“, часть 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. Записать основные законы и теоремы алгебры множеств

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...