Задача минимизации функций алгебры логики. Теоремы Квайна и Мак-Класски.

Минимальной формой булевской функции называется такая форма, которая содержит количество символов, не превышающее количество символов в любой другой форме.

В общем случае минимальных форм может быть несколько.

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

Для построения системы простых импликант используют теоремы Квайна и Мак-Класски или численную процедуру минимизации на гиперкубах. Эти методы основаны на склеивании элементов, являющихся ближайшими соседями.

Вспомогательные характеристики конституэнт единицы, используемые в теоремах Квайна и Мак-Класски:

1) | x_e | = – десятичное представление двоичного набора.

2) index( x_e ) =

3) s_lp = abs ( | x_l | – | x_p | ) – разность

Теорема Квайна: Для того чтобы 2 конституэнты единицы склеивались необходимо и достаточно, чтобы:

1) | index (x_l ) - index (x_p )|=1

2) s_lp = 2^k , kÎZ⁺

3) | x_l | > | x_p | Þ index (x_l ) > index (x_p )

Теорема Мак-Класски:

Необходимыми и достаточными условиями склеивания импликант произвольного уровня являются:

1) Равенство последовательностей разностей

2) Возможность склеивания младших конституэнт единицы в склеиваемых импликантах.