Метод Квайна

Метод Квайна применяют к ЛФ, заданным в СДНФ. На первом этапе выполняется переход от СДНФ к сокращенной ДНФ путем проведения всех возможных склеиваний. Для этого каждый раз в группе конъюнкций отыскиваются пары A_i·x_i и A_i·x_i, где А_i - общая часть конъюнкций. С учетом закона повторения, каждая конъюнкция может участвовать в нескольких склеиваниях (т.е. она может иметь другую пару A_j·x_j и A_j·x_j ). Полученные импликанты вновь подвергают попарному сравниванию, и так до тех пор, пока не получим сокращенную ДНФ.

Пример:

__1__ __ __ 2 3__ __ 4__ 5

F = Х1·Х2·Х3 + Х1·Х2·Х3 + Х1·Х2·Х3 + Х1·Х2·Х3 + Х1·Х2·Х3.

Проверяем все возможные пары конъюнкций 1-2, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5 и находим, что склеивание возможно для пар 1-3, 2-5, 3-4, 4-5

(4-я - 2 раза). __ __ __ __ __ __ __ __

F = (Х1·Х2·Х3 + Х1·Х2·Х3) + (Х1·Х2·Х3 + Х1·Х2·Х3) + (Х1·Х2·Х3 +

__ __ __1__ 2 3__ 4

Х1·Х2·Х3) + (Х1·Х2·Х3 + Х1·Х2·Х3) = Х2·Х3 + Х2·Х3 + Х1·Х2 + Х1·Х3.

Опять сравниваем попарно конъюнкции 1-2, 1-3, 1-4, 2-3, 2-4, 3-4. Эти пары уже не смежные, не склеиваются, т.е. получили сокращенную ДНФ.

Второй этап метода Квайна заключается в переходе от сокращенной ДНФ к тупиковым ДНФ и выборе среди них минимальной ДНФ.

Для выявления лишних простых импликант строится импликантная матрица, которая иногда также называется таблицей покрытий. Каждая строка импликантной матрицы соответствует одной простой импликанте, а столбцы - конъюнкциям исходного выражения (минтермам).

1 2 3 4 5

	x1 x2 x3	x1x2x3	x1x2 x3	x1x2x3	x1x2x3
1) x2 x3	x		x
2) x2x3		x			х
3) x1x2			x	x
4) x1x3				х	х

Каждая импликанта сравнивается со всеми минтермами. Если импликанта является частью некоторого минтерма (то есть ее можно получить из минтерма зачеркиванием некоторых букв), то говорят, что импликанта поглощает (покрывает) минтерм, и на пересечении строки и столбца ставится условный знак-отметка. Покрытие означает, что на соответствующих наборах аргументов импликанта обеспечивает единичные значения логической функции. Для нашего примера импликанта (1) покрывает минтермы (1) и (3). Аналогично заполняем и другие строки таблицы. Минимальной ДНФ будет соответствовать такая система минимального количества строк таблицы, которая будет иметь отметки во всех столбцах, то есть будет обеспечивать покрытие всех минтермов. Рекомендуется следующий алгоритм выявления тупиковых ДНФ:

1) Выделяются все обязательные (или существенные) импликанты, которые имеют пометку, единственную в каком-либо столбце. Такие импликанты нельзя удалять, они обязательно будут присутствовать в минимальной ДНФ, и далее они не проверяются.

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

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

Из таблицы примера видим, что простая импликанта (1) обеспечивает единичное значение логической функции на наборе 000 (и только эта импликанта, больше пометок в этом столбце нет), импликанта (2) - на наборе 011 (и она тоже единственная). Поэтому эти импликанты существенные, и их удалять нельзя. Простую импликанту (3) можно считать лишней и вычеркнуть. После этого импликанту (4) вычеркивать нельзя, она осталась единственной в четвертом столбце таблицы. Однако, если изменить порядок испытаний и сначала испытать импликанту (4), то ее можно удалить, но оставить импликанту (3).

В результате получаем две тупиковые ДНФ:

__ __ __

1) F1т = Х2·Х3+Х2·Х3+Х1·Х3, в которую не включена импликанта Х1·Х2;

__ __ __

2) F2т = X2·X3+X2·X3+X1·X2, в которую не включена импликанта Х1·Х3.

Тупиковые формы имеют одинаковое суммарное число переменных (шесть), поэтому любую из них можно выбрать в качестве минимальной ДНФ.

Для этого метода разработаны различные модификации, в том числе ориентированные на ЭВМ.

Дата добавления: 2015-07-11