Вопросы и упражнения

1. Используя метод диаграмм Вейча, необходимо найти МДНФ функции f(x₁, x₂, x₃), принимающей значение 1 на наборах:

1) 0,2,4,6.

2) 0,1,3,4.

3) 2,3,6,7.

4) 0,1,2,3,4.

2. Используя метод диаграмм Вейча, необходимо найти МДНФ функции f(x₁, x₂, x₃, x₄), принимающей значение 1 на наборах:

1) 3,8,9,10,12,13,15.

2) 0,5,8,9,10,12,13,15.

3) 0,8,10,11,13,15.

4) 1,2,3,12,13,14,15.

5) 2,3,7,8,10,11,12,15.

6) 0,4,6,7,8,10,13,15.

7) 0,4,5,7,8,10,11,13,15.

8) 0,4,5,6,7,14,15.

9) 2,4,7,9,10,14,15.

10) 0,3,7,8,9,10,11,12,15.

11) 0,2,3,5,11,12,15.

12) 0,2,4,7,8,10,13,15.

Сделать проверку с помощью таблиц истинности.

Тема 5. Минимизация булевых функций в классе ДНФ. Метод неопределённых коэффициентов

Любую логическую функцию можно представить в нормальной форме. Для простоты изложений и большей наглядности рассмотрение метода проведём при n=3. Представим функцию f(x₁, x₂, x₃) в виде следующей ДНФ:

где k^lmn – неопределённые коэффициенты, принимаемые значение 0 и 1, и подбираемые так, чтобы получающаяся после этого ДНФ была минимальной.

Критерий минимальности – минимальное количество букв в записи ДНФ. При определении ДНФ пользуются свойствами:

1) х₁+х₂+…+х_n=0, если х₁=х₂=…=х_n=0.

2) х₁+х₂+…+х_n=1, если хотя бы один член равен 1.

Если теперь задавать всевозможные наборы значений x₁, x₂, x₃ и приравнивать полученное после этого выражение (отбрасывая нулевые конъюнкции), значению функции на выбранных наборах, то получим систему 2³ уравнений для определения коэффициентов k.

Алгоритм минимизации ФАЛ методом неопределённых коэффициентов

1) Записать соответствующие уравнения, указав значения правых частей уравнений.

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

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

4) Оставшиеся единичные коэффициенты определят из уравнений соответствующую МДНФ.

Метод эффективен лишь для n<5.

Пример 5.1. Минимизировать ФАЛ, принимающую значение 1 на наборах: 0,1,2,3,7.

Решение. Составим систему уравнений:

.

Из уравнений 5, 6, 7 в силу свойств дизъюнкции следует, что

Вычеркнем эти элементы из оставшихся уравнений. После этого данные уравнения принимают вид:

Упростим каждое уравнение:

Т.о. Применив закон идемпотентности, получим

Искомая функция имеет вид: .

Значения функций на соответствующих наборах переменных совпадают, значит МДНФ найдена верно.