Файл: Diskretnaya_matematika.doc

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

Возвращаясь к примеру 2, отметим, что:

Импликант х₁х₄удов­летворяет следствию из теоремы 8:

х₁х₄ х₂х₄  х₁ х₂  1

и по­этому не входит ни в одну тупиковую форму.

Импликант х₂х₃х₄, для которого

х₂х₃х₄х₂х₄х₁х₂≢1 не удовлетворяет следствию.

Импликантх₁х₃х₄, для которого

х₁х₃х₄х₂х₄ х₁ х₂ ≢1, не удовлетворяет следствию.

Импликантх₁х₂х₃, для которого

х₁х₂ х₃х₂х₄  х₁ х₂ ≢ 1, не удовлетворяет следствию.

Таким образом, последовательность действий при выполнении второго этапа состоит в следующем:

1. для каждого простого импликанта сокращённой ДНФ про­верить, входит он в ядро или нет. Отметить неядерные импликанты;

2. проверить для отмеченных импликантов выполне­ние следствия из теоремы 8. Простые импликанты, для которых выпол­нено следствие, удалить из сокращённой ДНФ;

3. проверить возможность удаления оставшихся отмечен­ных конъюнкций. Из полученных тупиковых ДНФ выбрать минималь­ную ДНФ.

Рассмотрим эту последовательность действий на примере 2.

1. нашли ядро функции f(х₁, х₂, х₃, х₄), состоящее из простых импликантов х₂х₄ и х₁ х₂. Отметим курсивом в сокращённой ДНФ неядерные импликанты:

х₂х₄  х₁х₄  х₁ х₂  х₂ х₃ х₄ х₁ х₃ х₄ х₁х₂ х₃;

2. среди помеченных импликантов нашли удовлет­воряющий следствию из теоремы 8. Это импликант х₁х₄. Удалим его из со­кращённой ДНФ:

х₂х₄  х₁ х₂  х₂ х₃ х₄ х₁ х₃ х₄ х₁х₂ х₃;

3. для получения тупиковых ДНФ удаляем подмно­жества от­меченных импликантов. Можно удалить следующие подмножества:

{х₂ х₃ х₄,х₁ х₃ х₄,х₁х₂ х₃}^I, { х₂ х₃ х₄,х₁ х₃ х₄}^II, { х₂ х₃ х₄, х₁х₂ х₃}^III, {х₁ х₃ х₄,х₁х₂ х₃}^IV, {x₂ x₃ x₄ }^V, {х₁ х₃ х₄}^VI, {х₁х₂ х₃} ^VII.

При каждом удалении нужно проверять, представляет ли оставшаяся ДНФ функцию f(х₁, х₂, х₃, х₄).

Если удалить подмножество I, то получим ДНФ, не представ­ляющую функциюf(х₁, х₂, х₃, х₄), так как на наборе {0,1,1,1} функ­ция:

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

Если удалить подмножество II, то получим ДНФ, не представ­ляющую функциюf(х₁, х₂, х₃, х₄), так как на наборе {0,1,1,1} функ­ция

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

Если удалить подмножество III, получим минимальную ДНФ функции f(x₁, x₂, х₃, х₄):

х₂х₄х₁х₂х₁х₃х₄– минимальная ДНФ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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