II. Задачи для усвоения материала. В настоящее время интерес к дискретной математике неуклонно растёт

ПРЕДИСЛОВИЕ

В настоящее время интерес к дискретной математике неуклонно растёт. Всё больше в обязательную программу учебных заведений включаются курсы теории множеств, математической логики, комбинаторики, теории графов и их фрагменты. Специалисты в области современных компьютерных технологий уже осознали, что эти разделы математики являются фундаментом для построения необходимой сейчас хорошей теории математического обеспечения информационных технических систем. Многие специалисты, казалось бы, далёкие от математики, также начинают сознательно знакомиться с их содержанием.

Методические указания предназначены для студентов специальностей «Информатика и вычислительная техника», «Программная инженерия», «Профессиональное обучение», «Математическое обеспечение и администрирование информационных систем», изучающих дисциплину «Дискретная математика».

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

Тема 1 Основы теории множеств и комбинаторики.

1 «Операции над множествами»

I. Необходимые определения и формулировки теорем.

1. Назовите синонимы слова «множество».

2. Что такое «элемент множества»?

3. Что означает фраза «Множество А является подмножеством множества В»?

4. Что такое «пустое множество»?

5. Какие два множества называются равными?

6. Когда два множества равны? (поясните суть метода включений)

7. Какие операции на множествах существуют?

8. Что такое «объединение множеств»?

9. Что такое «пересечение множеств»?

10. Что такое «разность множеств А и В»?

11. Что такое «универсальное множество»?

12. Что такое «диаграммы Эйлера-Венна» и для чего они используются?

13. Поясните понятие «симметрическая разность множеств» и проиллюстрируйте его на диаграмме Эйлера-Венна.

14. Поясните понятие «дополнение множества до универсального» и проиллюстрируйте его на диаграмме Эйлера-Венна.

II. Задачи для усвоения материала.

1. Заданы множества , . Выписать все подмножества каждого из этих множеств. Сколько всего подмножеств у множества ? у множества ?

2. Сколько всего подмножеств у множества, содержащего 10 элементов?

3. Заданы множества А и В, а также универсальное множество U. Выписать множества , если

а) ;

б) ;

в) ;

г) ;

д)

е) ;

ж) ;

з) ;

и) .

4. Множества А, В, С представляют собой области, изображённые на рисунке 1.

Изобразите следующие множества:

а) ;

б) ;

в) ;

г) .

5. Множества А, В, С, D представляют собой области, изображённые на рисунке 2.

Изобразите следующие множества:

а) ;

б) ;

в) ;

г) ;

д) .

*Выберите два из ещё возможных изображений множеств и отобразите множества, указанные в пунктах а) – д).

6. Изобразите заданные множества на числовой прямой:

а) ;

б) ;

в) ;

г) .

7. Проиллюстрировать на диаграммах Эйлера-Венна и доказать методом включений формулы.

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) .

8. Дать теоретико-множественную интерпретацию и решить задачи. Проиллюстрировать на диаграммах Эйлера-Венна.

а) В результате поиска в Интернете выданы адреса Web-страниц www.cont1, www.cont2, www.cont3, www.st1, www.st2, www.st3, www.inf.ru, www.inf.au, содержащих комбинацию ключевых слов «electronic_libraries». Известно, что страницы с адресами www.cont1, www.cont3, www.st1, www.st2, www.inf.au содержат информацию о книгах по техническим наукам, страницы www.st1, www.st2, www.st3, www.inf.ru, www.inf.au – сведения о периодических изданиях. Адрес www.inf.au указывает на страницу с информацией об электронных библиотеках Австралии. Найти множество всех адресов, указывающих на страницы, содержащие информацию о периодических изданиях по техническим наукам, исключая издания в Австралии.

б) Имеется набор ключевых слов для поиска в Интернете информации, связанной с современными средствами электронного документооборота. Из этих ключевых слов можно выделить слова, позволяющие найти Web-страницы, содержащие информацию о современных текстовых процессорах, современных средствах хранения документов, способах передачи электронных документов по каналам связи, и некоторые страницы со специфической информацией. Требуется выделить из всех ключевых слов такие, которые позволят находить страницы, не связанные с хранением и передачей документов, однако содержащие сведения о современных текстовых процессорах.