Методические рекомендации по проведению практических занятий для студентов специальностей 080801 «Прикладная информатика в экономике»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Бийский технологический институт (филиал)

государственного образовательного учреждения

высшего профессионального образования

«Алтайский государственный технический университет

им. И.И. Ползунова»

Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова

ДИСКРЕТНАЯ МАТЕМАТИКА

Методические рекомендации по проведению практических

занятий для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы

и технологии»

Бийск

Издательство Алтайского государственного технического университета им. И.И. Ползунова

2009

УДК 519.1
Рецензент: к.ф.-м.н., доцент кафедры МСИА БТИ АлтГТУ Пальчиков А.В.

Тушкина, Т.М.

Дискретная математика: методические рекомендации по прове-дению практических занятий для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» / Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2009. – 76 с.

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

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

УДК 519.1

Рассмотрены и одобрены

на заседании кафедры

высшей математики

и математической физики.

Протокол № 6 от 02.12.08 г.

1 ЦЕЛИ И ЗАДАЧИ ПРАКТИЧЕСКИХ ЗАНЯТИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Практические занятия способствуют закреплению теоретических знаний и приобретению навыков решения конкретных задач по основ-ным разделам дискретной математики: теории множеств, абстрактной алгебре, математической логике, комбинаторике, теории графов. Целью практических занятий является развитие познавательных спо-собностей, самостоятельности мышления и творческой активности студентов при изучении дисциплины «Дискретная математика».

Задачами практических занятий являются:

закрепление, углубление и расширение знаний студентов по дискретной математике;
обучение студентов методам решения основных классов задач дискретной математики;
приобретение студентами умений и навыков использования методов дискретной математики для решения ряда практичес-ких задач управления;
изучение и анализ литературных источников по дисциплине «Дискретная математика».

Важность овладения методами дискретной математики переоце-нить сложно, так как современная техника переработки информации целиком основана на дискретных представлениях.
2 СОДЕРЖАНИЕ ЗАНЯТИЙ
Ниже в таблице 1 представлены темы практических занятий по дисциплине «Дискретная математика».
Таблица 1 – Темы практических занятий по дисциплине «Дискретная математика»

Номер

темы Номер

занятияТема занятияОбъем, ч123411Множества. Операции над множествами222Свойства операций над множествами233, 4Бинарные отношения. Способы задания бинарных отношений. Операции над бинарными отношениями445Свойства бинарных отношений256, 7Замыкания бинарных отношений. Отношение эквивалентности. Отношение порядка4Продолжение таблицы 1

123468Соответствия и их свойства279Операции и их свойства2810Гомоморфизмы2911Алгебры с одной бинарной операцией. Полугруппы. Моноиды. Группы21012Подгруппы. Циклические группы. Группа подстановок21113–15Алгебры с двумя бинарными операциями. Кольца. Поля. Решетки. Булевы алгебры641216–19 Комбинаторика81320Контрольная работа21421, 22Орграфы и бинарные отношения. Связность. Компоненты связности41523–25Минимальные пути в нагруженных орграфах. Эйлеровы цепи и циклы. Сети и потоки6

2.1 Практические занятия № 1–2. Множества. Операции над

множествами. Свойства операций над множествами
2.1.1 Теоретические сведения и методические рекомендации

по решению задач

Интуитивное определение множества: множество – это любая определенная совокупность объектов, которые называются элементами множества.

Элементы множества различны и отличимы друг от друга.

Приняты следующие обозначения. Если a – элемент множества А, то пишут: аА. В противном случае: аА или аА.

Интуитивный принцип объемности: два множества А и В равны, если они содержат одни и те же элементы: А=В.

Множество А всех элементов, обладающих свойством , обозначается А=.

Множество, не содержащее ни одного элемента, называется пустым и обозначается знаком .

Множество А называется подмножеством множества В (), если любой элемент множества А является также и элементом множества В.

Два множества равны тогда и только тогда, когда каждое из них является подмножеством другого, т.е. тогда и только тогда, когда .

На утверждении, сформулированном выше, основан метод дока-зательства равенства двух множеств. Для того чтобы доказать, что множества А и В равны, необходимо доказать два факта:

1) , то есть ;

2) , то есть .

Мощностью

конечного множества М называется числен-ность его элементов. Два конечных множества А и В называются равномощными, если

Множество всех подмножеств данного множества М называется булеаном .

Для конечного множества М справедлив следующий факт: , где .

Объединением множеств А и В называется множество , состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или В, т.е..

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

Разностью множеств А и В называется множество , состоя-щее из тех и только тех элементов, которые принадлежат множеству А, но не принадлежат множеству В, т.е. .

Симметрическая разность А+В множеств А и В определяется равенством А+В=(А\В)(В\А).

Если все рассматриваемые в ходе данного рассуждения множества являются элементами некоторого множества U, то множество U назы-вается универсальным для данного рассуждения или универсумом.

Дополнением множества А называется множество

, состоящее из тех и только тех элементов, которые не принадлежат множеству А, т.е.

Для более наглядного представления операций над множествами и их свойств применяют диаграммы Эйлера–Венна (рисунок 1). Каждое множество представляется множеством точек на плоскости.

Рисунок 1 – Диаграммы Эйлера–Венна

2.1.1.1 Свойства операций над множествами:

1) Коммутативность объединения1`) Коммутативность пересечения.. Ассоциативность объединения

.2`) Ассоциативность пересечения

.3) Дистрибутивность объединения относительно пересечения

.3`) Дистрибутивность пересечения относительно объединения

.) Идемпотентность объединения

.4`) Идемпотентность пересечения

.5) Свойства нуля

;

6) Свойства единицы

;

.7) Свойства дополнения

;

.8) Первый закон де Моргана

.8`) Второй закон де Моргана

.9) Первый закон поглощения

.9`) Второй закон поглощения

.10) Инволютивность

.11) Выражение для разности

.12) Выражение для дополнения

.Приняты следующие обозначения для числовых множеств:
N – множество натуральных чисел;

Z – множество целых чисел;

R – множество действительных чисел;

Q – множество рациональных чисел;

С – множество комплексных чисел.
2.1.2 Примеры решения задач

Задача 1. Доказать и проиллюстрировать на примере множеств , , тождество алгебры множеств, выражающее закон ассоциативности операции пересечения множеств.

Решение. Для доказательства тождества докажем два включения: и .

Пусть , тогда последовательно получаем

следовательно, ;

аналогично доказывается второе включение: пусть , тогда

Окончательно получаем, что .

Тем самым тождество доказано.

Убедимся в верности равенства на примере данных множеств А, В, С. Вычислим: , ; , . Очевидно, что .

Задача 2. Изобразить на координатной плоскости множества A и В точек координатной плоскости, удовлетворяющих соответственно соотношениям x²+y² ≤1 и x²+(y-1)² ≤1. Какие фигуры изображают множества AB, ?

Решение. Оба множества представляют собой на плоскости круги с радиусами R = 1, при этом центр первого круга находится в точке с координатами (0, 0), а второй – (0, -1). Фигуры, изображающие множества А, В, AB, , представлены на рисунке 2 (закрашены темным цветом).

А В AB
Рисунок 2 – Решение задачи 2 (2.1.2)
Задача 3. Доказать, что эквивалентны три предложения о произ-вольных множествах А, В и С: 1) ; 2) ; 3) .

Решение. Докажем, что из первого предложения следует второе. Действительно, так как , то осталось показать, что . Но если , то . В самом деле, . Следовательно, .

Докажем, что из второго предложения следует третье. Так как , то . По закону поглощения . Отсюда по закону коммутативности получаем .

Докажем теперь, что из третьего предложения следует первое. Так как , а по условию третьего предложения , то .
2.1.3 Задачи для самостоятельного решения

Какие из приведенных определений множеств являются корректными: ; ; ; . Принадлежит ли число 1 множеству D?
Даны множества Х ={l,2,3,4,5}, Y = {2,4,6,7}. Найдите XY,X∩Y,X\Y, Y\Х.
Проиллюстрируйте графически тождества

X(YZ)=(XY)(XZ), X(YZ)=( XY)( XZ).

Пусть R – множество вещественных чисел, X={x: хR; 0 ≤x ≤1}, Y={y: уR; 0 ≤y ≤2}. Что представляют собой множества XY, XY, X\Y?
Задать различными способами множество N: а) характерис-тическим свойством; б) порождающей процедурой.
Задать различными способами множество всех положительных четных чисел 2, 4, 6, …, не превосходящих 100: а) характеристическим свойством; б) порождающей процедурой.
Доказать, что множество А положительных четных чисел равно множеству В положительных целых чисел, представленных в виде суммы двух положительных нечетных чисел.
; ; ; . Найти ; ; .
A = {1,2,3,4,5,6}, B = {1,2,3}, C = {3,5,6,7,8}. Найти , , .
Представить множество диаграммой Эйлера–Венна.
Проиллюстрировать графически тождества , .
Проиллюстрировать на конкретных примерах, с помощью диаграмм и доказать следующие тождества: а) дистрибутивность пересечения относительно объединения, б) первый закон де Моргана.
Доказать .
А, В и С – некоторые множества. Какие из утверждений верны для всех множеств А, В и С:

а) если и , то ;

б) если и , то Ш;

в) если А≠В и В≠С, то А≠С;

г) если и , то В = Ш?

Существуют ли такие множества А, В и С, что Ш; Ш; Ш.
Даны произвольные множества А, В такие, что . Что представляют собой и ?
Даны произвольные множества C, D такие, что . Что представляют собой и ?
Даны множества А,В и С такие, что и , , . Доказать, что , , .
Доказать, что для произвольных множеств А, В имеет место соотношение тогда и только тогда, когда .
Доказать тождества:

а);

б) ;

в) ;

г);

д) ;

е) ;

ж) ;

з) .

21. Даны множества А, В и С такие, что . Доказать, что:

а) ;

б) ;

в) .

22. Пусть универсум U – конечный, и число элементов в нем не превосходит размерности ЭВМ. Пронумеруем элементы U: . Пусть А – подмножество U, представим А машин-ным словом С, в котором i-й символ определяется из условия:

Аналогично можно представить любое другое подмножество U. Найти объединение, пересечение и дополнение множеств, представ-ленных машинными словами. Проиллюстрировать на примере.

23. Решить систему уравнений

при условии, что .

2.2 Практические занятия № 3–7. Бинарные отношения.

Способы задания бинарных отношений. Операции над

бинарными отношениями. Свойства бинарных отношений.

Замыкания бинарных отношений. Отношение

эквивалентности. Отношение порядка
2.2.1 Теоретические сведения и методические рекомендации

по решению задач

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

Прямым (декартовым) произведением множеств А и В назы-вается множество упорядоченных пар, в котором первый эле-мент каждой пары принадлежит А, а второй принадлежит В, т.е.

.

Бинарным отношением из множества А во множество В назы-вается подмножество , т.е. .

Областью определения бинарного отношения называется мно-жество такое у, что .

Областью значений бинарного отношения называется мно-жество такое х, что .

Тождественным называется отношение .

Универсальным называется отношение .

Обратным отношением для называется отношение .

Композицией отношений и называется отношение существует такое z, что и .

Пусть и . Перенумеруем элементы множества А.

Матрицей отношения называется квадратная матрица порядка n, элементы которой

Бинарные отношения обладают следующими свойствами.

Рефлексивным называется отношение такое, что .

Антирефлексивным называется отношение такое, что .

Симметричным называется отношение такое, что .

Антисимметричным называется отношение такое, что .

Транзитивным называется отношение такое, что .

Связным называется отношение такое, что или . Другими словами, или , или .

Свойства бинарных отношений можно установить с помощью следующих признаков:

рефлексивно тогда и только тогда, когда ;
антирефлексивно тогда и только тогда, когда ;
симметрично тогда и только тогда, когда ;
антисимметрично тогда и только тогда, когда ;
транзитивно тогда и только тогда, когда ;
транзитивно тогда и только тогда, когда .

Пусть и – отношения на множестве А. Отношение называется замыканием относительно свойства С, если

а) обладает свойством С, т.е. ;

б) является надмножеством : ;

в) является наименьшим: (любое , обладающее свойством С и содержащее в себе , содержит в себе также и ).

Для вычисления замыканий бинарных отношений необходимо опираться на следующие факты:

1) транзитивным замыканием бинарного отношения является объединение положительных степеней

2) рефлексивным и транзитивным замыканием бинарного отно-шения является объединение неотрицательных степеней .

Рефлексивное, симметричное и транзитивное отношение, задан-ное на множестве А, называется эквивалентностью на множестве А.

Классом эквивалентности , порожденным элементом , называется подмножество множества А, состоящее из тех и только тех элементов у, которые состоят в отношении эквивалентности с х.

Совокупность множеств , , …, называется разбиением множества А, если выполняются два условия:

1) ;

2) = Ш, , .

Всякое отношение эквивалентности на множестве А определяет разбиение множества А, причем среди элементов разбиения нет пустых. Верно и обратное утверждение: всякое разбиение на множестве А, не содержащее пустых элементов, определяет отношение эквивалентности на этом множестве.

Антисимметричное и транзитивное отношение, заданное на мно-жестве А, называется отношением порядка на множестве А.

Порядок, обладающий свойством рефлексивности, называется нестрогим, а свойством антирефлексивности – строгим.

Порядок, являющийся связным, называется полным (линейным), в противном случае порядок называется частичным.

ДИСКРЕТНАЯ МАТЕМАТИКА