Минимизация функций

Можно выделить метод Квайна-Мак-Класки, который представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Опишем процесс формализации:

Выбор всех строк из таблицы истинности, где функция принимает значение 1(конституанты единицы).Разбивка на непересекающиеся группы. Склеивание только между номерами соседних групп. Неотмеченные после склеивания номера являются простыми импликантами. Метод Блейка — Порецкого позволяет получать сокращенную ДНФ булевой функции f из ее произвольной ДНФ. Базируется на применении формулы обобщенного склеивания. В основу метода положено следующее утверждение: если в произвольной ДНФ булевой функции f произвести все возможные обобщенные склеивания, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции f. Метод Петрика используется для нахождения всех минимальных покрытий конституент единицы и позволяет получить все тупиковые ДНФ по импликантной матрице. Суть метода заключается в следующем. По импликантной матрице строится так называемое конъюнктивное представление мипликантной матрицы. Для этого все простые импли-канты обозначаются разными буквами (обычно прописными латин-скими). После этого, для каждого i-ro столбца импликантной матрицы строится дизъюнкция всех букв, обозначающих строки матрицы, пересечение которых с i-м столбцом отмечено крестиком.

Конъюнктивное представление импликантной матрицы образуется как конъюнкция построенных дизъюнкций для всех столбцов матрицы. К конъюнктивному представлению матрицы могут быть применены все соотношения булевой алгебры с целью его упрощения. После раскрытия скобок и выполнения всех возможных поглощений получается дизъюнкция конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ[6].

ЗАКЛЮЧЕНИЕ

На основе логических функций строятся логические схемы или цепи. Соответственно стоимость проекта тем ниже, чем проще сама функция (цена, а так же сложность пропорциональны числу логических операций и числу вхождений переменных или их отрицаний).В исследовании рассмотрены вопросы минимизации функций и выделены такие способы как: Путем алгебраических преобразований. С помощью карт Карно. Методом Квайна.Методами Квайна-Мак-Класки, Блейка — Порецкого, Петрика. Первые три способа иллюстрируются практическими примерами, что позволяет наглядно продемонстрировать возможности минимизации функций. Следует отметить, что метод минимизации функций путем алгебраических преобразований наиболее трудоемкий и его использование возможно на достаточно простых функциях. Специальные методы минимизации (карты Карно, метод Квайна и т. д.) позволяют провести минимизацию более просто, исключая вероятность появления ошибки. Таким образом, можно сделать вывод о достижении цели и решении задач, определенных во введении. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫАкимов О. Е. Дискретная математика - М.: Лаборатория Базовых Знаний, 2011.

— 376 с. Гаврилов Г. П. Задачи и упражнения по дискретной математике - М.: ФИЗМАТЛИТ, 2006.

— 416 с. Микони С. В. Дискретная математика для бакалавра: множества, отношения, функции, графы: учебное пособие — Санкт-Петербург: Лань, 2012. — 186 с. Микушин А. В., Сажнев А. М., Сединин В. И. Цифровые устройства и микропроцессоры. СПб, БХВ-Петербург, 2010.

Новиков Ю. В. Основы цифровой схемотехники. Базовые элементы и схемы. Методы проектирования. М.: Мир, 2001. — 379 с.

http://ptca.narod.ru/lec/lec1.html Булевы функции.