Содержание
Введение
Задание 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 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)
(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. Следовательно, />.
Рассмотрим функцию />.
1.Принадлежность функции к классу />:
/>.
Следовательно, />.
2. Принадлежность функциик классу />:
/>.
Следовательно, />.
3. Принадлежность функциик классу />.
Предполагаем, что
/>.
Фиксируем набор 000:
/>,
/>.
Фиксируем набор 100:
/>,
/>.
Фиксируем набор 010:
/>,
/>.
Фиксируем набор 001:
/>,
/>.
Окончательно получаем
/>.
Это равенство несоблюдается на наборе 011:
/>,
/>.
Следовательно, />.
4. Принадлежность функциик классу /> .
Вычислим значения функциина оставшихся наборах:
/>
Строим таблицу :
(000)
(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 с.