Приведенная система простых ипликант и конъюнктивная форма импликантной матрицы.

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

Избыточная простая импликанта – та, мн-во истинности которой покрывается другими ипликантами.

Для построения приведённой системы простых импликант используют импликантную матрицу. В ней количество столбцов – |T_f| – мощность множества истинности исходной функции; количество строк – мощность системы простых импликант.

Элемент матрицы a_ij = 1, если i-ая простая импликанта покрывает j-ую конституэнту единицы, иначе a_ij = 0.

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

21. Теоремы Квайна и Мак-Класски и минимизация булевских функций на n-мерных гиперкубах – доказательство.

Что такое ваще склеивание (т.н. правила склейки):

Теорема Квайна: Для того чтобы 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 склеивающиеся конституэнты единицы. Представим их как кортежи единичек и ноликов. У них все разряды кроме одного одинаковые. Сложим их по модулю 2 (эта операция эквивалентна операции взятия разности их модулей). Получаем что их сумма по модулю (она же разность модулей) 2 равна целой степени двойки:
x₁ … … x_n
Å
x₁ … … x_n
=
0 …0 1 0 … 0 = 2 ^j-1.
Т.о. доказали теорему в одну сторону.

2) В обратную сторону – х.з., как. =( Но в общем-то аналогично. ;)

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

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

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

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