Минимизация булевых функций

Теория:

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

Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза.

Логическая функция .. называется импликантойфункции , если на любом наборе значение переменных , на котором значение функции равно 1 (единице), значение функции тоже равно единице.

Простой импликантойg функции называется элементарная конъюнкция, являющаяся импликантой функции и такая, что никакая её собственная часть не является импликантой.

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

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

Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой.

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

Выбор из всех тупиковых форм формы с наименьшим числом вхождений переменных дает минимальную ДНФ (МНДФ).

Определим следующие три операции:

— операция полного склеивания

; (1)

— операция неполного склеивания

; (2)

– операция элементарного поглощения

. (3)

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

Таким образом, метод заключается в следующем;

а) попарном склеивании всех элементарных конъюнкций совершенной ДНФ между собой;

б) попарном склеивании полученных в предыдущем процессе склеивания элементарных конъюнкций меньшего числа переменных;

в) поглощения конъюнкциями меньшего числа переменных конъюнкций большего числа переменных.

Задача 8. Построить сокращенную ДНФ из совершенной ДНФ функции

Решение.

Пронумеруем элементарные конъюнкции СДНФ:

Выполним операцию попарного полного склеивания (1) элементарных конъюнкций в СДНФ (под результатами склеивания проставим номера склеиваемых конъюнкций):

Выполним все возможные попарные склеивания полученных элементарных конъюнкций трех переменных:

Дальнейшее склеивание в данном примере невозможно.

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

Выполним теперь в этом выражении поглощение (3), в результате чего получим:

.

Задача 9. Найти все импликанты и из них простые импликанты для формул:

а) (стрелка Пирса);

б) (штрих Шеффера);

в) (сложение по модулю 2).

Решение.

Имеется всего 8 элементарных произведений с переменными х и у. Таблицы истинности приведенных формул имеют вид:

Из таблицы истинности выделим импликанты:

а) импликанты: и она же является простой импликантойв);

б) импликанты: , , , , , из них простые: , ;

в) импликанты: , .

Импликантами не могут являться выражения для которых при значении функции одно из значений импликанты равно 1.)