86364 (Решение практических заданий по дискретной математике)
Описание файла
Документ из архива "Решение практических заданий по дискретной математике", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "контрольные работы и аттестации", в предмете "математика" в общих файлах.
Онлайн просмотр документа "86364"
Текст из документа "86364"
Содержание
Введение
Задание 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. Принадлежность функции к классу 
.
Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:
.
Найдем коэффициенты 
.
