Пример минимизации методом неопределенных коэффициентов

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

Если теперь задавать всевозможные наборы значений аргументов и приравнивать полученное после этого выражение значению функции на выбранных наборах, то получим систему 2⁴ уравнений для определения коэффициентов К:

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

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

Пример минимизации методом Квайна-Мак-Класки.

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

Метод Квайна состоит из последовательного выполнения этапов:

1) Нахождение первичных импликант

2) Расстановка меток

3) Нахождение существенных импликант

4) Вычеркивание лишних столбцов

5) Вычеркивание лишних

6) Получение минимального покрытия

Выполним, приведенные этапы, для функции У₃.

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

СДНФ, которую мы нашли ранее, для функции У₃ имеет вид:

Составим минитермы для этой функции:

Таблица 2.2.1

Минитермы длиной 4