Xreferat.com » Рефераты по математике » Решение практических заданий по дискретной математике

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

Содержание


Введение

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


Решение практических заданий по дискретной
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: