Методические указания

Логическая функция называется импликантой функции, если на любом наборе значение переменных, на котором значение функции g равно 1 (единице), значение функции f тоже равно единице. Простой импликантой р функции f называется элементарная конъюнкция, являющаяся импликантой функции f и такая, что никакая её собственная часть не является импликантой. Дизъюнкция любого множества импликант булевой функции является импликантой этой функции.

Дизъюнкция всех простых импликант булевой функции совпадает с этой функцией и называется сокращённой дизъюнктивной нормальной формой (СкДНФ) этой функции.

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

Дизъюнкция всех простых импликант, составляющих систему S, называется тупиковой дизъюнктивной нормальной формой (ТДНФ) функции f. Всякая тупиковая ДНФ функции f совпадает с этой функцией. Если сокращенная ДНФ однозначно определяема логической функцией, то для одной и той же функции может существовать несколько различных тупиков ДНФ.

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

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

Этап 1. Сокращенная ДНФ – форма представления функции, которая получается из ДНФ путем склеивания вначале конституент единицы между собой (склеиваются «соседние» по той или иной переменной) по всем переменным, а затем конъюнкции ранга n-1, n-2 и т.д. Простая импликанта есть элементарная конъюнкция, которая не склеивается ни с какой другой конъюнкцией, входящей в данную логическую функцию.

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

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

Этап 2. Отыскивается система тупиковых ДНФ. Выбор из них минимальных ДНФ можно реализовать методом Петрика. В соответствии с этим методом строим импликантную матрицу - булеву матрицу, строки которой соответствуют импликантам тупиковых ДНФ, а столбцы – конституентам единиц СДНФ. Элемент матрицы равен 1, если простые импликанты являются составной частью соответствующей конституенты единицы. Затем отыскивают кратчайшее строчное покрытие этой матрицы. Тупиковая ДНФ с наименьшей суммой рангов составляющих её простых импликант и является минимальной ДНФ.

Решение

Знаком (*) отметим конъюнкции, которые склеиваются в процессе решения (рис. 4).

Рис. 4

Строим импликантную матрицу. Она дополнена строкой, содержащей дизъюнкцию тех простых импликант, которые соответствуют строкам, покрывающим тот или иной столбец матрицы (табл. 6).

Таблица 6

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

p₁p₄(p₁ v p₂)(p₂ v p₃)(p₃ v p₄) = p₁p₄(p₂ v p₁p₃)(p₃ v p₄) = p₁p₄(p₂p₃ v p₁p₃ v p₂p₄ v v p₁p₃p₄) = p₁p₄(p₂p₃ v p₁p₃ v p₂p₄) = p₁p₂p₃p₄ v p₁p₃p₄ v p₁p₂p₄

Как видно из последней формулы, исходная функция имеет три тупиковых ДНФ. Минимальная ДНФ соответствует слагаемым p₁p₃p₄ и p₁p₂p₄ и представляет собой дизъюнкцию импликант, входящих в эти слагаемые. Таким образом, первая минимальная ДНФ имеет следующее характеристическое множество {000-, 1-01, 11--}, т.е. имеет вид , а вторая минимальная ДНФ – множество {000-, -001, 11--} и вид .