Аналитические методы минимизации булевых функций. Метод Квайна. Метод карт Карно. Простые импликанты (стр. 3 )

Рассмотрим второй случай:

f=x3+x1+x2.

Общее правило минимизации:

1.  Для данной функции построить карту Карно

2.  Если в таблице стоит «прямоугольник», состоящий из четырех единиц (с учетом склейки краев), эти единицы покрываются одним литералом, являющимся общим для четырех ячеек.

3.  Непокрытые единицы, входящие в склеиваемые пары, покрываются двумя литералами.

4.  Единицы, которые не склеиваются ни с одной единицей, покрываются тремя литералами.

Замечание: при покрытии единиц следует учитывать закон поглощения.

Карты Карно для не полностью определенных функций:

Иногда некоторые сочетания аргументов для цифрового устройства несущественны, так как они не могут возникать на входе устройства, тогда на соответствующих местах карты Карно мы можем поставить и 0, и 1, более удобный вариант для минимизации.

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

Метод применим для минимизации функций алгебры логики от любого числа переменных.

Исходную логическую функции можно записать в виде логической суммы конъюнктивных членов с неопределенными коэффициентами, которые могут быть равны либо 0, либо 1. Эти конъюнктивные члены представляют собой возможные комбинации, составленные из переменных и их отрицаний. Неопределенные коэффициенты, фигурирующие в конъюнктивных членах, принято снабжать двумя наборами индексов – нижним и верхним. Нижний набор указывает на то, из каких переменных составлена конъюнкция, а верхний – о том, взята переменная или ее отрицание.

Полученные таким образом соотношения для булевой функции с неопределенными коэффициентами вычисляют на всех двоичных наборах, что приводит к системы линейных уравнений относительно неопределенных коэффициентов. При минимизации конкретной булевой функции в правые части написанных уравнений подставляют значения этой функции и среди решений полученной системы отбирают те, которые содержат минимальное количество переменных.

Алгоритм определения коэффициентов:

1. Исходное уравнение разбить на систему уравнений, равных числу строк в таблице истинности.

2. Напротив каждого выражения поставить соответствующее значение функции.

3. Выбрать строку, в которой значение функции и приравнять все к нулю.

4. Просмотреть строки, где функция имеет единичное значение, и вычеркнуть все коэффициенты, встречающиеся в нулевых строках.

5. Проанализировать оставшиеся коэффициенты в единичных строках.

6. Используя правило, что дизъюнкция равна 1 если хотя бы один из , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно.

7. Записать исходный вид функции.

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

где kО{0,1} ‑ коэффициенты. Метод заключается в подборе коэффициентов таким образом, чтобы получаемая ДНФ была минимальной.

Если теперь задать всевозможные значения переменных от 000 до 111, то получим 2n (23 =8) уравнений для определения коэффициентов k:

;

;

;

;

;

;

;

.

Рассматривая наборы, на которых функция принимает нулевое значение, определяют коэффициенты, которые равны 0, и вычеркивают их из уравнений, в правой части которых стоит 1. Из оставшихся коэффициентов в каждом уравнении к единице приравнивают по одному коэффициенту, определяющему конъюнкцию наименьшего ранга. Остальные коэффициенты приравнивают к 0. Итак, единичные коэффициенты k определяют соответствующую минимальную форму.

Пример. Минимизировать заданную функцию

,

если известны значения: ; ; ; ; ; ; ; .

Решение.

=1;

=0;

=0;

=0;

=1;

=1;

=1;

=1.

После вычеркивания нулевых коэффициентов получим:

=1;

=1;

=1;

=1;

=1.

Приравняем к единице коэффициент , соответствующий конъюнкции наименьшего ранга и обращающий четыре последних уравнения в 1, а в первом уравнении целесообразно приравнять к 1 коэффициент . Остальные коэффициенты приравнивают к 0.

Ответ: вид минимизированной функции .

Следует отметить, что метод неопределенных коэффициентов эффективен, когда число переменных невелико и не превышает 5-6.

Пример 2.

1=f(1, 1, 1)=

1=f(1, 1, 0)=

1=f(1, 0, 1)=

1=f(1, 0, 0)=

0=f(0, 1, 1)=

0=f(0, 1, 0)=

0=f(0, 0, 1)=

0=f(0, 0, 0)=

На отмеченных 5, 6, 7 наборах функций равна нулю, поэтому и все K=0. Но эти же коэффициенты входят и в другие уравнения, поэтому их нужно удалить. Получим:

Получим в результате конечную функцию: f(x1, x2, x3)=x1

Метод Квайна

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

Метод Квайна основывается на применении двух основных соотношений.
Соотношение склеивания где F - любое элементарное произведение.

Соотношение поглощения X Ú XF = X

Справедливость обоих соотношений легко проверяется. Суть метода заключается в последовательном выполнении всех возможных склеиваний и затем всех поглощений, что приводит к сокращенной ДНФ. Метод применим к CДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью.
Для доказательства достаточно показать, что произвольная простая импликанта р = xi1xi2 ... xin может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания):

A = A (x v /x) = Ax v A/x

по всем недостающим переменным xi^(k+l), ..., Xi^n исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта.