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

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

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

Пример 6.6.1. Формула — элементарное произведение, а формула элементарным произведением не является.

Формула φ(x₁, x₂,…,x_п) называется импликантой формулы ψ(x₁, x₂,…,x_п), если φ — элементарное произведение и φ ψ ~ φ, т. е. для соответствующих формулам φ и ψ функций f_φ и f_ψ справедливо неравенство f_φ ≤ f_ψ. Формула φ(x₁, x₂,…,x_п) называется импликантой функции f, если φ — импликанта совершенной ДНФ, представляющей функцию f.

Импликанта φ(x₁, x₂,…,x_п)= формулы ψ называется простой, если после отбрасывания любой литеры из φ не получается формула, являющаяся импликантой формулы ψ.

Пример 6.6.2. Найти все импликанты и простые импликанты для формулы

φ (х,у) = х → у.

Всего имеется 8 элементарных произведений с переменными х и у. Ниже приведены их таблицы истинности:

x	y	φ = x →y							x	y

Из таблиц истинности заключаем, что формулы , , ху, , у — все импликанты формулы φ, а из этих импликант простыми являются формулы и у. Hапример, формула , не является простой импликантой, поскольку отбрасывая литеру , получаем импликанту .

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

Теорема. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ.

В примере функция, соответствующая формуле x→y, представима формулой , которая является ее сокращенной ДНФ.

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

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