Содержание
Введение
Задание 1
Представить с помощью кругов Эйлера множественное выражение
Используя законы и свойства алгебры множеств, упростить заданное выражение
Задание 2
Заданы множества кортежей
Показать, что эти множества представляют собой соответствия между множествами N1
и N2
, если N1
= N2
=  . Дать полную характеристику этих соответствий
Задание 3
Частично упорядоченное множество М задано множеством упорядоченных пар
Построить диаграмму и определить, является ли данное множество решеткой. Если заданное множество является решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной …
Задание 4
Является ли полной система булевых функций   ? Если система функций полная ,то выписать все возможные базисы
Задание 5
Минимизировать булеву функцию  по методу Квайна – Мак-Класки
Задание 6
Для неориентированного графа  , у которого   , 
а) вычислить числа  ;
б) определить хроматическое число  …
Задание 7
Для заданной сети  :
а) найти величину минимального пути и сам путь от вершины   до вершины  по алгоритму Дейкстры ;
б) используя алгоритм Форда-Фалкерсона, определить максимальный поток  ( v1
– вход , v6
– выход сети ) и указать минимальный разрез, отделяющий v1
от v6
, если задана матрица весов (длин, пропускных способностей) Р…
Литература
Введение
Проблемы, связанные с понятиями бесконечности, дискретности и непрерывности, рассматривались в математике, как и в философии, древнегреческими мыслителями, начиная с 6 века до нашей эры. Под влиянием сочинений Аристотеля они широко обсуждались средневековыми учеными и философами в странах Европы и Азии. Через всю историю математики проходит идея преодоления между актуальной и потенциальной бесконечностью, с одной стороны, между дискретным характером числа и непрерывной природой геометрических величин – с другой. Впервые проблема математической бесконечности и связанных с нею понятий была широко поставлена в наиболее общем виде в теории множеств, основы которой были разработаны в последней четверти 19 века Георгом Кантором.
Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания.
Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM.
SeoHammer делает продвижение сайта прозрачным и простым занятием.
Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
Что умеет делать SeoHammer
— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз,
а первые результаты появляются уже в течение первых 7 дней.
Зарегистрироваться и Начать продвижение
Задание 1
Представить с помощью кругов Эйлера множественное выражение
 .
Используя законы и свойства алгебры множеств, упростить заданное выражение.
Решение:
Используя круги Эйлера и, учитывая, что операция пересечения выполняется раньше операции объединения, получим следующие рисунки:
  
  
Объединяя заштрихованные области, получим искомое множество:
Упростим заданное выражение:
  =
  .
Задание 2
Заданы множества кортежей:
 .
Показать, что эти множества представляют собой соответствия между множествами N1
и N2
, если N1
= N2
= . Дать полную характеристику этих соответствий
Решение:
Найдем декартово произведение:
Видно, что заданные множества являются подмножествами этого пря-мого произведения. Следовательно, данные множества есть соответствия.
а)  .
Область определения:  . Следовательно, соответствие является частично определенным.
Область значений:  . Следовательно, соответствие является сюръективным.
Образом элемента  являются два элемента  . Значит соответствие не является функциональным. Из этого следует, что соответствие не является функцией, отображением.
б)  .
Область определения:  . Следовательно, соответствие является частично определенным.
Область значений:  . Следовательно, соответствие не является сюръективным.
Образом любого элемента из  является единственный элемент из  . Следовательно, соответствие является функциональным, функци-ей. Соответствие является частично определенным. Это означает, что функция является частично определенной и не является отображением.
в)  .
Область определения: .Следовательно, соответствие всюду определено.
Область значений:  . Следовательно, соответствие не является сюръективным.
Образом любого элемента из является единственный элемент из . Следовательно, соответствие является функциональным, функцией. Так как соответствие всюду определено, то имеем полностью определенную функцию, т.е. имеем отображение N1
в N2
.
г)  .
Область определения: . Значит, соответствие полностью определено.
Область значений:  . Значит, соответствие сюръективно.
Образом любого элемента из N1
является единственный элемент из N2
. Следовательно, соответствие является функциональным, функцией.
Так как соответствие всюду определено, сюръективно, функционально и прообразом любого элемента из является единственный элемент из , то соответствие является взаимно однозначным.
Так как функция полностью определена и соответствие сюръективно, то имеем отображение N1
на N2
.
Сервис онлайн-записи на собственном Telegram-боте
Попробуйте сервис онлайн-записи VisitTime на основе вашего собственного Telegram-бота:
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.
Для новых пользователей первый месяц бесплатно.
Зарегистрироваться в сервисе
Так как для любых двух различных элементов из N1
их образы из N2
также различны, то отображение является инъективным.
Так как отображение является одновременно сюръективным и инъективным, то имеем биективное отображение (взаимно однозначное отображение).
Задание 3
Частично упорядоченное множество М задано множеством упорядоченных пар
 .
Построить диаграмму и определить, является ли данное множество решеткой. Если заданное множество является решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной.
Решение:
Построим диаграмму:
Построим таблицу:
Пары
элементов
|
Н.Г. |
В.Г. |
Н.Н.Г. |
Н.В.Г. |
| 1,2 |
1 |
2,5 |
1 |
2 |
| 1,3 |
1 |
3,4,5 |
1 |
3 |
| 1,4 |
1 |
4,5 |
1 |
4 |
| 1,5 |
1 |
5 |
1 |
5 |
| 1,6 |
1 |
6,2,5 |
1 |
6 |
| 2,3 |
1 |
5 |
1 |
5 |
| 2,4 |
1 |
5 |
1 |
5 |
| 2,5 |
2,6,1 |
5 |
2 |
5 |
| 2,6 |
6,1 |
2,5 |
6 |
2 |
| 3,4 |
3,1 |
4,5 |
3 |
4 |
| 3,5 |
3,1 |
5 |
3 |
5 |
| 3,6 |
1 |
5 |
1 |
5 |
| 4,5 |
4,3,1 |
5 |
4 |
5 |
| 4,6 |
1 |
5 |
1 |
5 |
| 5,6 |
6,1 |
5 |
6 |
5 |
Так как любая пара элементов имеет единственную наибольшую нижнюю грань и единственную наименьшую верхнюю грань, то заданное частично упорядоченное множество М является решеткой.
Решетка М является дедекиндовой, когда выполняется равенство:
для таких  , что  .
Решетка М не является дедекиндовой, т.к. указанное равенство не вы-полняется, например, для элементов 2, 3, 4:
Одним из условий дистрибутивности решетки является ее дедекиндо-вость. Так как решетка М не является дедекиндовой, то она не является дистрибутивной решеткой.
Задание 4
Является ли полной система булевых функций ? Если система функций полная ,то выписать все возможные базисы.
Решение:
Рассмотрим функцию  .
1. Принадлежность функции к классу  :
 .
Следовательно,  .
2. Принадлежность функции к классу  :
 .
Следовательно,  .
3. Принадлежность функции к классу  .
Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:
 .
Найдем коэффициенты  .
Фиксируем набор 000:
 ,
 ,
Следовательно,  .
Фиксируем набор 100:
 ,
 ,
Следовательно,  .
Фиксируем набор 010:
 ,
 ,
 .
Следовательно,  .
Фиксируем набор 001:
 ,
 ,
 ,  .
Следовательно, функция (по нашему предположению) может быть представлена полиномом вида:
 .
Если функция линейная, то на всех остальных наборах ее значение должно равняться 1. Но на наборе 111  . Значит, функция не является линейной, т.е.  .
4. Принадлежность функции к классу  .
Функция самодвойственная, если на любой паре противоположных наборов (наборов, сумма десятичных эквивалентов которых равна  , где п – количество переменных функции) функция принимает противоположные значения.
Вычисляем  . Вычисляем значения функции на оставшихся наборах:
 
Строим таблицу:
(000)
0
|
(001)
1
|
(010)
2
|
(011)
3
|
(100)
4
|
(101)
5
|
(110)
6
|
(111)
7
|
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
На наборах 1 и 6, 2 и 5, 3 и 4 функция принимает одинаковые значения. Следовательно,  .
5. Принадлежность функции к классу  .
Из таблицы видно: 000 < 111 , но  . Следовательно,  .
Рассмотрим функцию  .
1. Принадлежность функции к классу :
 .
Следовательно,  .
2. Принадлежность функции к классу :
 .
Следовательно,  .
3. Принадлежность функции к классу .
Предполагаем, что
 .
Фиксируем набор 000:
 ,
 .
Фиксируем набор 100:
 ,
 .
Фиксируем набор 010:
 ,
 .
Фиксируем набор 001:
 ,
 .
Окончательно получаем
 .
Это равенство не соблюдается на наборе 011:
 ,
 .
Следовательно,  .
4. Принадлежность функции к классу .
Вычислим значения функции на оставшихся наборах:
Строим таблицу :
(000)
0
|
(001)
1
|
(010)
2
|
(011)
3
|
(100)
4
|
(101)
5
|
(110)
6
|
(111)
7
|
| 1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
Из таблицы видно, что на наборах 3 и 4 функция принимает одинаковые значения. Следовательно,  .
5. Принадлежность функции к классу .
Из таблицы видно, что 111 > 000 , но  . Следовательно,  .
Строим критериальную таблицу:
| К0 |
К1 |
КЛ |
КС |
КМ |
| f1 |
- |
- |
- |
- |
- |
| f2 |
- |
- |
- |
- |
- |
В таблице в каждом столбце стоят минусы. Следовательно, система булевых функций
является полной .
Найдем все возможные базисы. По критериальной таблице составим КНФ :
 .
Приведем КНФ к ДНФ :
 .
По полученной ДНФ выписываем искомые базисы:
 .
Задание 5
Минимизировать булеву функцию по методу Квайна – Мак-Класки.
Решение:
1 этап. Определение сокращенной ДНФ.
По десятичным эквивалентам запишем 0-кубы :
Выполним разбиение на подгруппы:
 .
Строим  -кубы, сравнивая соседние группы (значок (*) указывает на участие данной импликанты в склеивании):
Выполняем разбиение всех -кубов в зависимости от расположения независимой переменной Х :
 .
Выполняем сравнение кубов внутри каждой подгруппы с целью построения  -кубов (значок (*) указывает на участие данной импликанты в склеивании):
 .
Выполняем сравнение кубов внутри каждой подгруппы с целью построения  -кубов (значок (*) указывает на участие данной импликанты в склеивании):
 или
 .
Так как они одинаковы, то  .
Запишем сокращенную ДНФ, в которую должны быть включены им-пликанта из К 3
и импликанты, не участвовавшие в склеивании (в нашем случае таких импликант нет) :
 .
2 этап. Определение тупиковой ДНФ.
Так как все импликанты участвовали в склеивании, и сокращенная ДНФ состоит из одной простой импликанты, то строить таблицу покрытий нет необходимости, т.е.
 .
Задание 6
Для неориентированного графа , у которого  ,
а) вычислить числа ;
б) определить хроматическое число .
Решение:
Построим граф:
а) Вычислим числа  .
1)  :
Используя алгоритм выделения пустых подграфов, построим дерево:
Согласно определению :
 .
2)  :
Используя алгоритм выделения полных подграфов, построим дерево:
Здесь  - полные подграфы. Видно, что мощность носителей всех подграфов равна трем, т.е.
 .
3)  :
Построим модифицированную матрицу смежности  заданного графа G :
1 2 3 4 5 6
  .
Находим минимальное число строк, покрывающих все столбцы модифи-цированной матрицы . Таких строк – одна. Следовательно,
 .
б) Определим хроматическое число  .
Согласно алгоритму минимальной раскраски вершин графа, выделим все пустые подграфы графа G , т.е. построим дерево (оно построено в пункте а) ):
Построим таблицу:
1 2 3 4 5 6
1. {1,4,6} 1 1 1 
2. {1,5} 1 1
3. {2,5} 1 1
4. {2,6} 1 1
5. {3} 1
Определяем минимальное число строк, покрывающих все столбцы таблицы. Такими строками могут быть строки 1, 3, 5. Значит,
 .
Зададимся красками: для множества вершин  - краска синяя (С ), для множества вершин  - краска красная ( К ), для множества вершин  - краска зеленая ( З ).
Раскрасим вершины графа G :
Задание 7
Для заданной сети  :
а) найти величину минимального пути и сам путь от вершины   до вершины  по алгоритму Дейкстры ;
б) используя алгоритм Форда-Фалкерсона, определить максимальный поток  ( v1
– вход , v6
– выход сети ) и указать минимальный разрез, отделяющий v1
от v6
,
если задана матрица весов (длин, пропускных способностей) Р :
v1
v2
v3
v4
v5
v6
Решение:
Построим сеть:
а) Найдем величину минимального пути и сам путь сети G . Используем для этого алгоритм Дейкстры.
Этап 1. Нахождение длины кратчайшего пути.
 .
Шаг 1. Полагаем 
1-я итерация.
Шаг 2. Составим множество вершин, непосредственно следующих за  с временными метками:  . Пересчитываем временные метки этих вершин:  ,
 .
Шаг 3. Одна из временных меток превращается в постоянную:
Шаг 4.  Следовательно, возвращаемся на второй шаг.
2-я итерация.
Шаг 2.
Шаг 3.
Шаг 4.  Переход на второй шаг.
3-я итерация.
Шаг 2.
Шаг 3.
Шаг 4.
 Переход на второй шаг.
4-я итерация.
Шаг 2.
Шаг 3.
Шаг 4.  Переход на второй шаг.
5-я итерация.
Шаг 2.
Шаг 3.
Шаг 4.  Конец первого этапа.
Следовательно, длина кратчайшего пути равна  .
Этап 2. Построение кратчайшего пути.
1-я итерация.
Шаг 5. Составим множество вершин, непосредственно предшествующих  с постоянными метками :  Проверим равенство
для этих вершин:
 т.е.
 т.е.
Включаем дугу  в кратчайший путь, 
Шаг 6.  Возвращаемся на пятый шаг.
2-я итерация.
Шаг 5.
Включаем дугу  в кратчайший путь, .
Шаг 6.  . Завершение второго этапа.
Следовательно, кратчайший путь построен. Его образует последовательность дуг:  .
Окончательно, кратчайший путь от вершины  до вершины v6
построен. Его длина (вес) равна . Сам путь образует последовательность дуг:
б) Определим максимальный поток через сеть G. Для этого используем алгоритм Форда-Фалкерсона.
Выбираем произвольно путь из вершины v1
в вершину v6
. Пусть это будет путь  . Минимальную пропускную способность на этом пути, равную 10, имеет дуга , т.е.  Увеличим на этом пути поток до 10 единиц. Дуга становится насыщенной. Дуга имеет на данный момент пропускную способность, равную 10.
Путь  Следовательно, поток на этом пути можно увеличить на 9 единиц. Дуги  становятся насыщенными.
Других маршрутов нет (другие маршруты проходят через насыщенные дуги). Поток максимален. Делаем разрез вокруг вершины v1
по насыщенным дугам
и получаем его величину  единиц.
8. Используя алгоритм Краскала, построить остов с наименьшим весом для неориентированного взвешенного графа  , у которого  , если заданы веса (длины) ребер:
□ Построим граф G :
1. Упорядочим ребра в порядке неубывания веса (длины):
2. Возьмем ребро u1
и поместим его в строящийся остов.
Возьмем ребро u2
и поместим его в строящийся остов (т.к. оно не образует с предыдущим ребром цикла).
Берем ребро u3
и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).
Берем ребро u4
и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).
Берем ребро u5
и помещаем его в строящийся остов (т.к. оно не образует цикла с предыдущими ребрами).
Ребра  не рассматриваем, т.к. они образуют циклы с предыдущими ребрами.
Проверим окончание алгоритма. Число входящих в остов ребер равно 5. Заданный граф имеет п = 6 вершин и  . Таким образом, остов содержит все вершины заданного графа G .
Вес (длина) построенного остова
равен   .
Литература
1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.
2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энерго атомиздат, 1987. – 496 с.
3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с.
4. Шапорев С.Д. Дискретная математика. – СПб.: БХВ-Петербург, 2006. - 400 с.
5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с.
6. Хаханов В.И., Чумаченко С.В. Дискретная математика ( конспект теоретического материала). – Харьков: ХНУРЭ, 2003. – 246 с.
7. Богданов А.Е. Курс лекций по дискретной математике.–Северодонецк: СТИ, 2006. – 190 с.
|
