Метод Петрика

Метод базируется на составлении логического выражения, представляющего собой условие покрытия всех вершин из упрощенной таблицы покрытий и преобразования этого выражения [13-16].

Суть метода заключается в следующем. Все простые импликанты обозначаются простыми буквами. Затем для каждого i-го столбца импликантной матрицы строится дизъюнкция всех букв, обозначающих простые импликанты, перекрывающие данный столбец. Далее импликантная матрица представляется конъюнкцией всех построенных для отдельных столбцов дизъюнкций.

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

Пример 4.5. Функция задана таблицей истинности.

Привести данную функцию к минимальной форме методом Петрика.

Решение. Для получения сокращенной формы воспользуемся методом Квайна – Мак-Класки.

Приведем импликантную матрицу, в которой для каждой простой импликанты введено буквенное обозначение:

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

В результате операции поглощение, полученное выражение преобразуется к виду:

Далее в соответствии с распределительным законом получим

и выражение приводится к виду

Наконец, переходя от конъюнктивной формы выражения к его дизъюнктивной форме, получаем окончательно

Из полученного выражения следует, что имеется четыре тупиковых ДНФ. Из них минимальная ДНФ (с минимальным числом букв) Следовательно, МДНФ функции: