Контрольная работа: Решение практических заданий по дискретной математике

Содержание

Введение

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

Вычислим значения функции на оставшихся наборах:

Строим таблицу :

(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

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

Решение:

1 этап. Определение сокращенной ДНФ.

По десятичным эквивалентам запишем 0-кубы :

Выполним разбиение на подгруппы:

.

Строим -кубы, сравнивая соседние группы (значок (*) указывает на участие данной импликанты в склеивании):

Выполняем разбиение всех -кубов в зависимости от расположения независимой переменной Х :


.

Выполняем сравнение кубов внутри каждой подгруппы с целью построения -кубов (значок (*) указывает на участие данной импликанты в склеивании):

.

Выполняем сравнение кубов внутри каждой подгруппы с целью построения -кубов (значок (*) указывает на участие данной импликанты в склеивании):

 или

.

Так как они одинаковы, то .

Запишем сокращенную ДНФ, в которую должны быть включены им-пликанта из К 3 и импликанты, не участвовавшие в склеивании (в нашем случае таких импликант нет) :


.

2 этап. Определение тупиковой ДНФ.

Так как все импликанты участвовали в склеивании, и сокращенная ДНФ состоит из одной простой импликанты, то строить таблицу покрытий нет необходимости, т.е.

.


Задание 6

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

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

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

Решение:

Построим граф:

а) Вычислим числа .

1) :

Используя алгоритм выделения пустых подграфов, построим дерево:

Согласно определению :


.

2) :

Используя алгоритм выделения полных подграфов, построим дерево:

Здесь - полные подграфы. Видно, что мощность носителей всех подграфов равна трем, т.е.

.

3) :


Построим модифицированную матрицу смежности  заданного графа G :

          1 2 3 4 5 6

 .

Находим минимальное число строк, покрывающих все столбцы модифи-цированной матрицы . Таких строк – одна. Следовательно,

.

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

Согласно алгоритму минимальной раскраски вершин графа, выделим все пустые подграфы графа G , т.е. построим дерево (оно построено в пункте а) ):


Построим таблицу:

1 2 3 4 5 6

1. {1,4,6} 1 1 1

2. {1,5} 1 1

3. {2,5} 1 1

4. {2,6} 1 1

5. {3} 1  

Определяем минимальное число строк, покрывающих все столбцы таблицы. Такими строками могут быть строки 1, 3, 5. Значит,

.

Зададимся красками: для множества вершин - краска синяя (С ), для множества вершин - краска красная ( К ), для множества вершин - краска зеленая ( З ).


Раскрасим вершины графа G :

 


Задание 7

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

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

б) используя алгоритм Форда-Фалкерсона, определить максимальный поток  ( v1 – вход , v6 – выход сети ) и указать минимальный разрез, отделяющий v1 от v6 ,

если задана матрица весов (длин, пропускных способностей) Р :

      v1 v2 v3 v4 v5 v6

Решение:

Построим сеть:

а) Найдем величину минимального пути и сам путь сети G . Используем для этого алгоритм Дейкстры.

Этап 1. Нахождение длины кратчайшего пути.

.


Шаг 1. Полагаем

1-я итерация.

Шаг 2. Составим множество вершин, непосредственно следующих за  с временными метками: . Пересчитываем временные метки этих вершин: ,

.

Шаг 3. Одна из временных меток превращается в постоянную:

Шаг 4. Следовательно, возвращаемся на второй шаг.

2-я итерация.

Шаг 2.

 

Шаг 3.

Шаг 4.  Переход на второй шаг.

3-я итерация.


Шаг 2.

 

Шаг 3.

 

Шаг 4.

Переход на второй шаг.

4-я итерация.

Шаг 2.

Шаг 3.

Шаг 4.  Переход на второй шаг.

5-я итерация.

Шаг 2.

 


 Шаг 3.

Шаг 4.  Конец первого этапа.

Следовательно, длина кратчайшего пути равна .

Этап 2. Построение кратчайшего пути.

1-я итерация.

Шаг 5. Составим множество вершин, непосредственно предшествующих  с постоянными метками :  Проверим равенство

для этих вершин:

 т.е.

 т.е.

 

Включаем дугу  в кратчайший путь,

Шаг 6.  Возвращаемся на пятый шаг.

2-я итерация.

Шаг 5.

 


Включаем дугу  в кратчайший путь, .

Шаг 6. . Завершение второго этапа.

Следовательно, кратчайший путь построен. Его образует последовательность дуг: .

Окончательно, кратчайший путь от вершины  до вершины v6 построен. Его длина (вес) равна . Сам путь образует последовательность дуг:

 

б) Определим максимальный поток  через сеть G. Для этого используем алгоритм Форда-Фалкерсона.

Выбираем произвольно путь из вершины v1 в вершину v6 . Пусть это будет путь . Минимальную пропускную способность на этом пути, равную 10, имеет дуга , т.е.  Увеличим на этом пути поток до 10 единиц. Дуга  становится насыщенной. Дуга  имеет на данный момент пропускную способность, равную 10.

Путь  Следовательно, поток на этом пути можно увеличить на 9 единиц. Дуги  становятся насыщенными.

Других маршрутов нет (другие маршруты проходят через насыщенные дуги). Поток максимален. Делаем разрез вокруг вершины v1 по насыщенным дугам


и получаем его величину  единиц.

8. Используя алгоритм Краскала, построить остов с наименьшим весом для неориентированного взвешенного графа , у которого , если заданы веса (длины) ребер:

 

□ Построим граф G :

1. Упорядочим ребра в порядке неубывания веса (длины):

2. Возьмем ребро u1 и поместим его в строящийся остов.

Возьмем ребро u2 и поместим его в строящийся остов (т.к. оно не образует с предыдущим ребром цикла).

Берем ребро u3 и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).

Берем ребро u4 и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).

Берем ребро u5 и помещаем его в строящийся остов (т.к. оно не образует цикла с предыдущими ребрами).

Ребра  не рассматриваем, т.к. они образуют циклы с предыдущими ребрами.

Проверим окончание алгоритма. Число входящих в остов ребер равно 5. Заданный граф имеет п = 6 вершин и . Таким образом, остов содержит все вершины заданного графа G .

Вес (длина) построенного остова

равен .


Литература

1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.

2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энерго атомиздат, 1987. – 496 с.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с.

4. Шапорев С.Д. Дискретная математика. – СПб.: БХВ-Петербург, 2006. - 400 с.

5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с.

6. Хаханов В.И., Чумаченко С.В. Дискретная математика ( конспект теоретического материала). – Харьков: ХНУРЭ, 2003. – 246 с.

7. Богданов А.Е. Курс лекций по дискретной математике.–Северодонецк: СТИ, 2006. – 190 с.

Задача остовных деревьев в k-связном графе
Министерство Науки и Образования Республики Молдова Молдавский Государственный Университет Кафедра Информатики и Дискретной Оптимизации Дипломная ...
Это множество состоит из k вершин и, следовательно, но оно не разделяет вершины a и b. Значит, имеется (a, b)-цепь Р, первое ребро которой не принадлежит ни одной из цепей Pi (i=)
Все вершины из V\A и соединяющие их ребра в графе GA будут же, как и в графе G. Назовем построенный граф GA стягиванием графа G по множеству А.
Раздел: Рефераты по математике
Тип: реферат
Орграфы, теория и применение
Федеральное агентство по образованию РФ Государственное образовательное учреждение высшего профессионального образования "Санкт-Петербургский ...
A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.
Если G - произвольный планарный (р, орграф и р^З, то а^Зр - 6. Ориентированный граф, или орграф, D состоит из конечного непустого множества V вершин и заданного набора X ...
Раздел: Рефераты по математике
Тип: реферат
AGraph: библиотека классов для работы с помеченными графами
§1. Актуальность разработки библиотек для работы с графами К настоящему времени накоплен большой опыт решения теоретико-графовых задач на ЭВМ ...
В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на ...
... и т.д. Вид графа, во-первых, задает набор атрибутов, которые определены для вершин и ребер данного графа (например, вес ребра для взвешенного графа или указатель на родительскую ...
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа
Алгоритмический язык Паскаль
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ им. А.В. ЛУНАЧАРСКОГО КАФЕДРА ИНФОРМАТИКИ Дипломная ...
Первый элемент блока - это указатель вершины стека, который можно задать с помощью индекса I. При записи в стек указатель вершины стека будет сдвигаться в сторону конца массива ...
Выделяют из всех деревьев так называемые УПОРЯДОЧЕННЫЕ деревья - такие, у которых ребра (т.е. соответствующие им элементы), выходящие из каждой вершины, упорядочены по какому-либо ...
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа
ПТЦА - Прикладная теория цифровых автоматов
Прикладная теория цифровых автоматов. Методы анализа и синтеза комбинационных схем. Техническим аналогом булевой функции в вычислительной технике ...
В результате анализа КС прямым методом получается множество наборов входных переменных, обеспечивающих заданное значение на выходе, что позволяет записать в алгебраическом виде БФ ...
При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними.
Раздел: Остальные рефераты
Тип: реферат