Содержание
Введение

Задание 1

Представить с помощью кругов Эйлера множественное выражение

Используя законы и свойства алгебры множеств, упростить заданное выражение

Задание 2

Заданы множества кортежей

Показать, что эти множества представляют собой соответствия между множествами N₁ и N₂ , если N₁ = N₂ = . Дать полную характеристику этих соответствий

Задание 3

Частично упорядоченное множество М задано множеством упорядоченных пар

Построить диаграмму и определить, является ли данное множество решеткой. Если заданное множество является решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной …

Задание 4

Является ли полной система булевых функций  ? Если система функций полная ,то выписать все возможные базисы

Задание 5

Минимизировать булеву функцию  по методу Квайна – Мак-Класки

Задание 6

Для неориентированного графа , у которого  ,

а) вычислить числа ;

б) определить хроматическое число …

Задание 7

Для заданной сети :

а) найти величину минимального пути и сам путь от вершины   до вершины  по алгоритму Дейкстры ;

б) используя алгоритм Форда-Фалкерсона, определить максимальный поток  ( v₁ – вход , v₆ – выход сети ) и указать минимальный разрез, отделяющий v₁ от v₆ , если задана матрица весов (длин, пропускных способностей) Р…

Литература




Введение
Проблемы, связанные с понятиями бесконечности, дискретности и непрерывности, рассматривались в математике, как и в философии, древнегреческими мыслителями, начиная с 6 века до нашей эры. Под влиянием сочинений Аристотеля они широко обсуждались средневековыми учеными и философами в странах Европы и Азии. Через всю историю математики проходит идея преодоления между актуальной и потенциальной бесконечностью, с одной стороны, между дискретным характером числа и непрерывной природой геометрических величин – с другой. Впервые проблема математической бесконечности и связанных с нею понятий была широко поставлена в наиболее общем виде в теории множеств, основы которой были разработаны в последней четверти 19 века Георгом Кантором.

Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания.




Задание 1
Представить с помощью кругов Эйлера множественное выражение
.
Используя законы и свойства алгебры множеств, упростить заданное выражение.

Решение:

Используя круги Эйлера и, учитывая, что операция пересечения выполняется раньше операции объединения, получим следующие рисунки:
   
  
Объединяя заштрихованные области, получим искомое множество:

Упростим заданное выражение:












=



.




Задание 2
Заданы множества кортежей:


 

 

.
Показать, что эти множества представляют собой соответствия между множествами N₁ и N₂ , если N₁ = N₂ = . Дать полную характеристику этих соответствий

Решение:

Найдем декартово произведение:
 
Видно, что заданные множества являются подмножествами этого пря-мого произведения. Следовательно, данные множества есть соответствия.
а)  .



Область определения: . Следовательно, соответствие является частично определенным.

Область значений: . Следовательно, соответствие является сюръективным.

Образом элемента  являются два элемента . Значит соответствие не является функциональным. Из этого следует, что соответствие не является функцией, отображением.
б) .

Область определения: . Следовательно, соответствие является частично определенным.

Область значений: . Следовательно, соответствие не является сюръективным.

Образом любого элемента из  является единственный элемент из . Следовательно, соответствие является функциональным, функци-ей. Соответствие является частично определенным. Это означает, что функция является частично определенной и не является отображением.
в) .





Область определения:.Следовательно, соответствие всюду определено.

Область значений: . Следовательно, соответствие не является сюръективным.

Образом любого элемента из  является единственный элемент из . Следовательно, соответствие является функциональным, функцией. Так как соответствие всюду определено, то имеем полностью определенную функцию, т.е. имеем отображение N₁ в N₂ .
г) .
 
Область определения: . Значит, соответствие полностью определено.

Область значений: . Значит, соответствие сюръективно.

Образом любого элемента из N₁ является единственный элемент из N₂ . Следовательно, соответствие является функциональным, функцией.

Так как соответствие всюду определено, сюръективно, функционально и прообразом любого элемента из  является единственный элемент из , то соответствие является взаимно однозначным.

Так как функция полностью определена и соответствие сюръективно, то имеем отображение N₁ на N₂ .

Так как для любых двух различных элементов из N₁ их образы из N₂ также различны, то отображение является инъективным.

Так как отображение является одновременно сюръективным и инъективным, то имеем биективное отображение (взаимно однозначное отображение). 




Задание 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:
,

,

.
Следовательно,