Решение практических заданий по дискретной математике
Содержание
Введение
Задание 1
Представить с помощью кругов Эйлера множественное
выражение
Используя законы и свойства алгебры
множеств, упростить заданное выражение
Задание 2
Заданы множества кортежей
Показать, что эти множества
представляют собой соответствия между множествами N1 и N2 , если N1 = N2 = . Дать полную характеристику этих соответствий
Задание 3
Частично упорядоченное множество М задано
множеством упорядоченных пар
Построить диаграмму и определить,
является ли данное множество решеткой. Если заданное множество является
решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной …
Задание 4
Является ли полной система булевых функций
? Если система функций полная ,то
выписать все возможные базисы
Задание 5
Минимизировать булеву функцию по методу Квайна – Мак-Класки
Задание 6
Для неориентированного графа , у которого ,
а) вычислить числа ;
б) определить хроматическое число …
Задание 7
Для заданной сети :
а) найти величину минимального пути и
сам путь от вершины до вершины по алгоритму Дейкстры ;
б) используя алгоритм Форда-Фалкерсона,
определить максимальный поток ( v1 – вход , v6 – выход сети ) и указать минимальный разрез,
отделяющий v1 от v6 , если задана матрица весов (длин,
пропускных способностей) Р…
Литература
Введение
Проблемы, связанные с
понятиями бесконечности, дискретности и непрерывности, рассматривались в
математике, как и в философии, древнегреческими мыслителями, начиная с 6 века
до нашей эры. Под влиянием сочинений Аристотеля они широко обсуждались средневековыми
учеными и философами в странах Европы и Азии. Через всю историю математики проходит
идея преодоления между актуальной и потенциальной бесконечностью, с одной
стороны, между дискретным характером числа и непрерывной природой
геометрических величин – с другой. Впервые проблема математической
бесконечности и связанных с нею понятий была широко поставлена в наиболее общем
виде в теории множеств, основы которой были разработаны в последней четверти 19
века Георгом Кантором.
Цель контрольной работы –
ознакомится с основными понятиями и методами решения по дискретной математике,
уметь применить полученные знания при решении практического задания.
Задание 1
Представить с помощью кругов
Эйлера множественное выражение
.
Используя законы и
свойства алгебры множеств, упростить заданное выражение.
Решение:
Используя круги Эйлера и,
учитывая, что операция пересечения выполняется раньше операции объединения,
получим следующие рисунки:
Объединяя заштрихованные
области, получим искомое множество:
Упростим заданное
выражение:
=
.
Задание 2
Заданы множества
кортежей:
.
Показать, что эти
множества представляют собой соответствия между множествами N1 и N2 , если N1 = N2 = . Дать полную характеристику этих соответствий
Решение:
Найдем декартово
произведение:
Видно, что заданные
множества являются подмножествами этого пря-мого произведения. Следовательно,
данные множества есть соответствия.
а) .
Область определения: . Следовательно,
соответствие является частично определенным.
Область значений: . Следовательно,
соответствие является сюръективным.
Образом элемента являются два элемента . Значит соответствие не
является функциональным. Из этого следует, что соответствие не является
функцией, отображением.
б) .
Область определения: . Следовательно,
соответствие является частично определенным.
Область значений: . Следовательно,
соответствие не является сюръективным.
Образом любого элемента
из является
единственный элемент из .
Следовательно, соответствие является функциональным, функци-ей. Соответствие является
частично определенным. Это означает, что функция является частично определенной
и не является отображением.
в) .
Область определения:.Следовательно,
соответствие всюду определено.
Область значений: . Следовательно,
соответствие не является сюръективным.
Образом любого элемента
из является
единственный элемент из .
Следовательно, соответствие является функциональным, функцией. Так как
соответствие всюду определено, то имеем полностью определенную функцию, т.е.
имеем отображение N1 в N2 .
г) .
Область определения: . Значит, соответствие полностью
определено.
Область значений: . Значит, соответствие
сюръективно.
Образом любого элемента
из N1 является единственный элемент из N2 . Следовательно, соответствие является
функциональным, функцией.
Так как соответствие
всюду определено, сюръективно, функционально и прообразом любого элемента из является единственный
элемент из , то
соответствие является взаимно однозначным.
Так как функция полностью
определена и соответствие сюръективно, то имеем отображение N1 на N2 .
Так как для любых двух
различных элементов из N1 их образы из N2 также различны, то отображение является инъективным.
Так как отображение
является одновременно сюръективным и инъективным, то имеем биективное
отображение (взаимно однозначное отображение).
Задание 3
Частично упорядоченное
множество М задано множеством упорядоченных пар
.
Построить диаграмму и
определить, является ли данное множество решеткой. Если заданное множество
является решеткой, то определить, является ли решетка дедекиндовой ,
дистрибутивной.
Решение:
Построим диаграмму:
Построим таблицу:
Пары
элементов
|
Н.Г.
|
В.Г.
|
Н.Н.Г.
|
Н.В.Г.
|
1,2
|
1
|
2,5
|
1
|
2
|
1,3
|
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. Принадлежность функции
к классу .
Строим критериальную
таблицу:
|
К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 с.