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

Анализ требований к задаче минимизации ДНФ обнаружил ря общих свойств и позволил ввести особую меру сложности ДНФ.

Пусть F=F1∨F2∨...∨Fm, т.е. заданна в виде ДНФ булевой функции.

О: отображение L составляющая каждой ДНФ целое неотрицательное число и удовлетворяющая требованиям 1) 2) 3) 4) называется индексом простоты

1) L(F)≥0

2) F=F1∨(xi&F2) => L(F)≥L(F1∨F2)

3) Если F=F1∨F2 => L(F)≥L(F1)+L(F2)

4) Если ДНФ F1 получена из ДНФ F2 переименованием переменных, то L(F1)=L(F2)

В качестве индекса простоты можно взять:

Lk(F)- число элементарных конъюнкций, входящих в F

Lr(F)- сумма рангов элементарных конъюнкций, входящих в F. Рангом называется число переменных r входящих в Fi элементарную конъюнкцию ДНФ F.

L0(F)-число отрицаний в F.

О: Минимальная ДНФ - ДНФ F, реализующая заданную булеву функцию и имеющая минимальное значение L(F) называется минильной (относительно индекса простоты L).

Замечание: ДНФ минимальная относительно индекса Lr -просто минимальной, Lk- кратчайшей.

Сокращенные и тупиковые ДНФ

{не уверен что ето надо, но напечатал на всякий случай}

О: Говорят, что функция F1 своим значением с1 накрывает значение с2 функции F2, если на некоторой оценке <ε1,ε2,...εn> списка переменных <x1,x2,...,xn> то

F1(ε1...εn)=c1

F2(ε1...εn)=c2

О: Функция F1 называется импликантой функции F2, если она своими нулями накрывает все нули функции F2

Т1: Если F1,F2,...,Fm импликанты булевой функции F, то

F1∨F2∨...∨Fm

F1&F2&...&Fm, также импликанты.

Т2: Если F1∨F2∨...∨Fm импликанты булевой функции, то и F1,F2,...,Fm тоже импликанты.

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

Т3: Дизъюнкция всех простых импликант булевой функции совпадает с этой булевой функцией.

О: СкДНФ - ДНФ, составленная ищ простых импликант булевой функции называется сокращенной ДНФ(СкДНФ)

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

О: Тупиковая ДНФ - сокращенная ДНФ из которой удалены лишние импликанты называются тупиковой (ТДНФ)

Метод минизации Квайна:

Здесь рассматриваются булевы функции приведенные к СДНФ(в виде F=F1∨F2∨...∨Fm, где Fi - элементарная конъюнкция, содержащая весь список переменных <x1,...,xn>

Метод квайна основан на двух операциях:

1) (X&A)∨(X&A)≡(X&A)∨(X&A)∨A

2) A∨(A&B)≡A

Метод Квайна основан на следующей теореме:

Т.Квайна: Если в СДНФ произвести все возможные неполные склеивания, а затем все возможные поглощения, то получится СкДНФ.

Алгоритм минимизации:

10 Находим СДНФ, которая реализует заданную булеву функцию.

20 Находим ей эквивалентную СкДНФ по Т.Квайна.

30 Находим множество тупиковых ДНФ, каждая из которых реализует булеву функцию

40 Из множества тупиковых ДНФ по опр. минимальности находим минимальную ДНФ.