Дискретная математика. ДМ. Министерство образования республики беларусь
 Скачать 107.85 Kb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» Кафедра электронных вычислительных машин Индивидуальная работа по курсу «Дискретная математика» Проверил: Поттосин Юрий Васильевич Минск 2017 Вариант задания - 7 Задача 1 Найти близкую к минимальной раскраску вершин графа, заданного следующей матрицей смежности:
Решение По данным матрицы смежности построим граф. Составим таблицу со степенями вершин полученного графа: 1 2 3 4 5 6 7 8 3 6 4 3 3 5 4 4 Далее отсортируем вершины таким образом, чтобы их степени убывали: 2 6 3 7 8 1 4 5 Первую неокрашенную вершину раскрашиваем в Р1, далее проверяем наличие связи со следующей неокрашенной вершиной. В данном случае в Р1 окрасится 5ая вершина. По этому же принципу раскрашиваем оставшиеся вершины графа. В результате получаем близкую к минимальной раскраску вершин графа. 2 6 3 7 8 1 4 5 Р1 Р2 Р2 Р3 Р3 Р3 Р3 Р1 Задача 2 Получить минимальную систему ДНФ для следующей системы полностью определенных булевых функций:
Решение Задача минимизации системы ДНФ формулируется следующим образом: для заданной системы булевых функций получить такую систему ДНФ, в которой общее число различных элементарных конъюнкций было бы минимальным. Применим метод Квайна-МакКласки. Для начала вспомним сведения из теории. Пусть F – некоторая система булевых функций. Элементарная конъюнкция является обобщенной простой импликантой для множества булевых функций F F, если она является импликантой для любой функции из F и перестает быть импликантой при удалении из нее любого литерала и не является импликантой ни для какой функции, не принадлежащей F. Процесс минимизации системы ДНФ по данному методу состоит из двух этапов: 1) нахождение множества всех обобщенных простых импликант для заданной системы; 2) выделение из этого множества минимального подмножества, удовлетворяющего условию, что для всякой функции, принадлежащей заданной системе, можно из этого подмножества получить задающую ее ДНФ. Исходная система булевых функций представлена в виде системы совершенных ДНФ, которая задана парой булевых матриц. Это парам матриц аргументов. Строки матрицы аргументов представляют конъюнкции максимального ранга, являющиеся членами заданных ДНФ. Другими словами, эти строки являются элементами булева пространства, на каждом из которых хотя бы одна функция заданной системы имеет значение 1. Столбцы матрицы функций соответствуют заданным функциям, и единицы в них показывают, какие конъюнкции принадлежат ДНФ соответствующей функции. То есть любая строка этой матрицы задает множество функций, имеющих значение 1 на наборе значений аргументов, представляемым одноименной строкой матрицы аргументов. Первый этап выполняется с помощью простого склеивания. При этом учитываются характеристики импликант. Под характеристикой понимается множество функций, для которого данная конъюнкция является импликантой. Начальные значения характеристик задаются строками матрицы функций. Результату склеивания приписывается в качестве характеристики пересечение характеристик склеиваемых конъюнкций, которое получается поразрядной конъюнкцией соответствующих векторов. Естественно, что если результатом поразрядной конъюнкции является вектор, все компоненты которого нули, то результат склеивания не рассматривается. Склеиваемым конъюнкциям приписывается знак «*», но приписывается он только тем конъюнкциям, характеристика которых совпадает с характеристикой результата склеивания. Для удобства сгруппируем исходные булевы векторы матрицы аргументов в подмножества, состоящие из векторов, имеющих одинаковое число единиц, и упорядочим эти подмножества по возрастанию (или убыванию) числа единиц в векторе. Получим
Выполняем процесс простого склеивания, получаем следующую последовательность пар матриц:
Полученную сокращенную систему ДНФ, которая содержит все обобщенные простые импликанты представим следующей парой матриц:
Строки матрицы |