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

Содержание

Введение

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

,

,

.

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

Фиксируем набор 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. Принадлежность функции к классу .

Из таблицы видно, что 111 > 000 , но . Следовательно, .

Строим критериальную таблицу:

	К0	К1	КЛ	КС	КМ
f1	-	-	-	-	-
f2	-	-	-	-	-

 

В таблице в каждом столбце стоят минусы. Следовательно, система булевых функций

является полной .

Найдем все возможные базисы. По критериальной таблице составим КНФ :

.

Приведем КНФ к ДНФ :

.

По полученной ДНФ выписываем искомые базисы:

.

Задание 5

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

Решение: