Метод Неопределённых коэффициентов

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:35, 1 июня 2016.

Метод неопределенных коэффициентов – один из методов минимизации функций алгебры логики. Данный метод может быть применен для ФАЛ от любого числа аргументов.

Описание

Метод состоит из последовательного выполнения этапов:

  1. Представляем функцию в виде ДНФ с неопределенными коэффициентами;
  2. Задаем все возможные значения аргументов и приравниваем к полученному значению функции 0 или 1;
  3. Составляем систему уравнений для коэффициентов и приравниваем, соответственно, к 0 или 1 значению функции;
  4. Все коэффициенты в уравнениях с 0 значением функции также равны 0;
  5. Вычеркиваем из уравнений с 1 значением функции все коэффициенты равные 0, из уравнений с 0 значениями ;
  6. В полученных уравнениях оставляем коэффициенты с минимальным количеством индексов, которые присутствуют в максимальном количестве строк;
  7. Выбираем минимальное покрытие, в котором присутствуют коэффициенты с разными индексами, отсюда получаем МДНФ.

Представление

Представление функции в СДНФ с неопределенными коэффициентами:




Здесь представлены все возможные коньюнкции, которые могут входить в ДНФ функции
Система уравнений для определения значений коэффициентов на различных наборах.

Пример

Вариант 1

В качестве функции возьмем . Составляем систему:


Из уравнений с 0 значениями получаем: =>

Отсюда получаем МДНФ:

Вариант 2

Таблица истинности исходной функции:

Рис.1. Таблица истинности исходной функции

Шаг 1. Избавляемся от нулевых коэффициентов



Шаг 2. Сортируем уравнения по возрастанию



Шаг 3. Ищем часто встречающиеся термы минимального ранга



Шаг 4. Избавляемся от повторов


Получаем следующую ДНФ:

Достоинства

  1. Основным достоинством применения данного метода это возможность его использования при большом числе переменных n = 16 и более в профессиональных разработках, он ориентирован на использование в САПР с применением ЭВМ для минимизации полностью и не полностью определенных функций.
  2. Метод неопределенных коэффициентов, также как и метод Квайна-Мак-Класски, можно использовать для минимизации ФАЛ, заданных как в СДНФ, так и в СКНФ.
  3. Удобно минимизировать системы булевых функций, так как легко выделять общие части реализуемой системы ФАЛ.
  4. Метод является алгоритмически систематическим, легко формализуется и легко алгоритмизируется, не зависит от навыков разработчика.

Недостатки

  1. Затруднительно использовать метод для числа переменных > 6 для ручной минимизации.
  2. Метод не является алгоритмически инвариантным - время работы метода растёт экспоненциально с увеличением входных данных. Поэтому для функций с очень большим количеством переменных используют эвристические алгоритмы.

Список литературы

  1. Поспелов Д. А. Логические методы анализа и синтеза схем. Изд. 3-е, перераб. и доп., М., «Энергия», 1974., с 55
  2. http://mybiblioteka.su/1-36381.html