Решение практических заданий по дискретной математике (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. Принадлежность функции к классу .

Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:


.


Найдем коэффициенты .

Фиксируем набор 000:

,


,


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

Фиксируем набор 100:


,

,


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

Фиксируем набор 010:


,

,

.


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

Фиксируем набор 001:


,

,

, .


Следовательно, функция (по нашему предположению) может быть представлена полиномом вида:



.


Если функция линейная, то на всех остальных наборах ее значение должно равняться 1. Но на наборе 111 . Значит, функция не является линейной, т.е. .

4. Принадлежность функции к классу .

Функция самодвойственная, если на любой паре противоположных наборов (наборов, сумма десятичных эквивалентов которых равна , где п – количество переменных функции) функция принимает противоположные значения.


Случайные файлы

Файл
106992.rtf
74089-1.rtf
182315.rtf
174941.rtf
2321-1.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.