Материал: Diskretnaya_matematika

2.4.3. Минимизация днф методом Квайна

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

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

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

2. каждый член ДНФ, представляющий собой конъюнкцию ме­нее n членов (n – количество аргументов функции), развер­тывается в дизъюнкцию нескольких элементарных конъюнкций умножением на выражение вида (х₁х₁) • (х₂х₂)•…, тождественно равное едини­це;

3. приводятся, если возможно, подобные члены.

Второй этап. Отыскиваются все простые импликанты данной функции. Для этого выписываются все элементарные конъюнкции, входящие в СДНФ. Каждая из пар этих конъюнкций исследуется на возможность склеивания. Члены, участвовавшие хотя бы в одном склеивании, отмечаются, но не исключаются из дальнейших сравне­ний.

В результате выявляются группы конъюнкций, содержа­щие по (n- 1) члену. С этой группой конъюнкций проводится та же процедура, после которой получим группы конъюнкций, содержа­щие по (n- 2) членов и так далее, пока не останется ни одного члена, допускающего склеивания с каким либо другим членом.

Добавление к исходной ДНФ любого количества «склеенных» членов не изменяет вида функции. Последующее исключение всех членов, отмеченных в процессе склеивания, тоже не изменяет функ­цию, так как они поглощаются склеенными членами. Все неотме­ченные в процессе преобразований члены представляют собой про­стые импликанты, а их дизъюнкция эквивалентна исходной функ­ции.

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

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

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

Эту задачу можно выполнить в следующей последовательно­сти:

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

2. если после этого в таблице окажутся такие пары столбцов, что всем отмеченным клеткам второго столбца соответствуют в тех же строках отмеченные клетки первого столбца, а возможно, и неко­торые другие отмеченные клетки, то первый столбец вычеркивается. Это возможно потому, что какую бы совокупность простых импликантов, покрывающую элементарную конъюнкцию, которая соот­ветствует второму столбцу мы ни подобрали, этой совокупностью автоматически будет покрываться и конъюнкция, соответствующая первому столбцу;

3. строки, не содержащие после выполнения п.п. 1 и 2 ни од­ной отмеченной клетки, также вычеркиваются. Это возможно потому, что все конъюнкции, которые могут быть покрыты данным про­стым импликантом, уже покрыты другими простыми импликантами, которые должны войти в окончательное выражение для ДНФ;

4. в сокращенной таблице выявляется пара строк, содержащая хотя бы по одной отмеченной клетке в каждом столбце. Простые импликанты, соответствующие этим строкам, добавляются к ДНФ;

5. если оказывается несколько вариантов выполнения п. 4, то все они сравниваются, и выбирается простейший вариант.

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

f(х₁, х₂, х₃, х₄) = х₁ х₂ х₄  х₂ х₃ х₄ х₁х₂ х₃ х₁х₂х₄.

В результате развертывания элементар­ных конъюнкций получим:

Таблица 2.7. Импликантная таблица

Вычеркивая строки и столбцы, соответствующие обязательным импликантам х₁х₂х₄их₁х₂х₄, получим упрощенную импликантную таблицу (табл. 2.8).

Таблица 2.8. Упрощенная импликантная таблица

Из упрощенной таблицы видно, что простой импликант х₁х₃ х₄ покрывает обе оставшиеся конъюнкции. Теперь можно окончатель­но записать минимальную ДНФ для функцииf(х₁, х₂, х₃, х₄):

f(х₁, х₂, х₃, х₄) = х₁ х₂ х₄ х₁х₂х₄  х₁ х₃ х₄.

Для уменьшения количества проверок на возможность склеи­вания целесообразно все элементарные конъюнкции, содержащие одинаковое число букв, сгруппировать по признаку одинакового количества инвертированных (или не инвертированных) букв.

2.5. Синтез логических схем

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

Первый этап

1. По заданному в техническом задании алго­ритму выделяем независимые аргументы (входы) и выписываем все их комбинации (входные наборы). При большом количестве входов следует попытаться объединить их или реализовать устройство по частям.

2. Отмечаем запрещенные наборы, т.е. комбинации входных сигналов, которые не могут возникнуть.

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

4. Доопределяем таблицу на запрещенных наборах, пользуясь информацией, имеющейся в алгоритме, либо руководствуясь сле­дующим (не всегда наилучшим) соображением: если в таблице больше единичных значений выхода, чем нулевых, она доопределя­ется единичными значениями и наоборот.

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

Второй этап

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

Эффект применения эквивалентных преобразований зависит от последовательности их применения. Наиболее важными являются склеивание х_i х_i = 1 и поглощение х_i  х_iх_j = х_i. К сожалению, нельзя указать такой порядок применения эквивалентных преобра­зований, который обеспечивал бы наиболее простую форму записи функции.