Решение практических заданий по дискретной математике

Содержание


Введение

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

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.