Материал: Дискретная математика. методические указания к выполнению лабораторных работ для студентов направления подготовки «Информатика и вычислительная техника». Собенина О.В., Пак А.А
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Воронежский государственный технический университет»
Кафедра компьютерных интеллектуальных технологий проектирования
ДИСКРЕТНАЯ МАТЕМАТИКА
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к выполнению лабораторных работ для студентов направления подготовки
09.03.01«Информатика и вычислительная техника» очной и заочной форм обучения
Воронеж 2022
УДК 519.854(07)
ББК 22.176я7
Составители: О. В. Собенина, А. А. Пак
Дискретная математика: методические указания к выполнению
лабораторных |
работ для студентов направления подготовки 09.03.01 |
«Информатика |
и вычислительная техника» очной и заочной форм обучения / |
ФГБОУ ВО «Воронежский государственный технический университет»; сост.: О. В. Собенина, А. А. Пак. Воронеж: Изд-во ВГТУ,2022. 28с.
Методические указания содержат теоретические сведения и практические задания и варианты заданий для проведения лабораторных работ.
Предназначены для студентов 2 курса.
Методические указания подготовлены в электронном видеатся вифайлесодерж МУ ЛР_ДМ(очное, заочное).pdf.
Ил. 2. Библиогр.: 8 назв.
УДК 519.854(07) ББК 22.176я7
Рецензент - В. В. Горбунов канд. физ-мат. наук, доц. кафедры прикладной математики и механики ВГТУ
Издается по решению редакционно-издательского совета Воронежского государственного технического университет
ВВЕДЕНИЕ
Дискретная математика – область математики, занимающаяся изучением свойств дискретных структур, которые возникают как внутри математики, так и в ее приложениях. Дискретность (от лат discretus – разделенный, прерывистый) – прерывность; противопоставляется непрерывности. Например, система целых чисел (в противоположность системе действительных чисел) является дискретной; дискретное изучение какой-либо величины во времени – это изменение, происходящее через определенные промежутки времени (скачками).
Дискретная математика представляет собой важное |
направление в ма- |
|
тематике, в котором можно выделить |
характерные для дискретной мате- |
|
матики предметы исследования, методы и задачи, специфика которых обуслов-
лена в первую очередь необходимостью отказа в дискретной |
математи- |
|||
ке от основополагающих понятий классической |
математики – предела и не- |
|||
прерывности. В связи с этим для |
многих задач дискретной математики |
|||
сильные средства |
классической математики оказываются, как правило, ма- |
|||
лоприемлемыми. |
|
|
|
|
Дискретная математика включает в себя такие |
математические |
|||
разделы, как теория множеств и отношений, теория графов, теория алгоритмов,
комбинаторный анализ, |
математическую логику и другие, |
которые наиболее |
|
интенсивно стали развиваться в связи с внедрением |
вычислительной |
||
техники. Теория графов является |
эффективным аппаратом формали- |
||
зации современных |
инженерных задач, связанных с дискретными объек- |
||
тами. |
|
|
|
Методические указания содержат задания по основным разделам дисциплины «Дискретная математика»: решение теории множеств, решение задач теории множеств, решение задач теорий отношений, достижимость и связность в графе, деревья, остовы, кратчайшие остовы. По каждой теме даны теоретические сведения, необходимые для выполнения заданий, а также представлены примеры решения задач.
Представленный материал призван помочь студенту овладеть необходимыми знаниями по изучаемой дисциплине, а также научить использовать символику дискретной математики для формализации и решения дискретных задач.
3
ЛАБОРАТОРНАЯ РАБОТА № 1
РЕШЕНИЕ ЗАДАЧ ТЕОРИИ МНОЖЕСТВ
Цель работы: изучение основных понятий и определений теории множеств, свойств множеств и операций над ними. Получение практических навыков упрощения выражений и доказательства тождеств, содержащих множества.
Примеры решения задач
Задача 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.
Доказать 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), а это значит, что эти два множества равны.
Решение подобных задач можно оформить в более формализованном виде, используя “{” для системы высказываний, объединенных союзом “и”, “[”- для системы высказываний, объединенных союзом «или».
Задача 3.
Доказать тождество Решение. Используя правую часть выражения
привести к левой.
(
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
4
Практическая часть Задания
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
Содержание отчета
1.Номер и тема лабораторной работы.
2.Цель выполнения работы.
3.Условия задач приводятся полностью.
4.Решения излагаются подробно, объясняются все действия по ходу ре-
шения.
5.Анализ полученных результатов и вывод по работе.
ЛАБОРАТОРНАЯ РАБОТА № 2
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМИЧЕСКИХ ПРОЦЕДУР ТЕОРИИ МНОЖЕСТВ
Цель работы: изучение основных понятий и определений теории множеств, свойств множеств и операций над ними. Получение практических навыков программной реализации алгоритмических процедур теории множеств.
Программное средство: среда разработки приложений MS Visual Studio, языки программирования С#, C++.
ПРАКТИЧЕСКАЯ ЧАСТЬ Задания
Написать программу, реализующую следующую процедуру:
1.Даны два множества, заданные перечислением своих элементов. Получить симметрическую разность этих элементов.
5