Минимизация двоичных функции

Пусть двоичная функция f представлена в виде ДНФ:

. (5.1)

Определение 5.1. Сложностью представления (5.1) булевой функции f называется число операций « » и « » в записи (5.1).

Замечание 5.2. Операции «отрицания» в определении 5.1 не учитываются.

Определение 5.3. Задача минимизации для функции f заключается в нахождении заданий функции f в виде ДНФ, у которых сложности минимальны. Такие ДНФ называются минимальными (МДНФ).

Определение 5.4. Импликантами двоичной функции f называются элементарные конъюнкции, входящие во всевозможные ДНФ функции f. Импликанта функции f называется простой, если все элементарные конъюнкции, полученные из неё удалением некоторых переменных, не являются импликантами функции f.

Утверждение 5.5. Пусть . Следующие утверждения эквивалентны:

1. является импликантой функции f;

2. ;

3. .

Доказательство. Покажем эквивалентность первых двух утверждений. Если — импликанта и — та ДНФ, в которую входит , например, , то

.

Обратно, если — некоторая ДНФ, то в силу тождества конъюнкцию можно дописать в качестве (k + 1)-й импликанты в эту ДНФ не нарушая равносильности. Эквивалентность утверждений 2 и 3 следует из тождеств:

, .

Утверждение доказано.

Утверждение 5.6. В минимальной ДНФ функции f ( ) все импликанты являются простыми.

Доказательство. Пусть — минимальная ДНФ функции f. Предположим, что импликанта непростая. Тогда её можно представить в виде произведения двух элементарных конъюнкций от разных переменных, одна из которых, например , также является импликантой функции f. Согласно утверждению 5.5: , или иначе

.

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

Из этого утверждения вытекает, что задачу минимизации в классе ДНФ можно решать в два этапа.

1-й этап. Находят все простые импликанты функции f. Дизъюнкция всех простых импликант функции f называется сокращённой ДНФ этой функции.

Замечание 5.7. Сокращённая ДНФ функции f действительно является ДНФ для f, поскольку, повторяя доказательство утверждения 5.6 можно в произвольной ДНФ функции f заменить все импликанты на простые.

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