3.3     Метод Блейка-Порецького

Метод дозволяє отримувати скорочену ДНФ булевої функції f з її довільної ДНФ. Базується на використанні формули узагальненого склеювання:

,

справедливість якої легко довести. Дійсно,

     ;     .

Таким чином,

.

В основу метода покладено таке твердження: якщо в довільній ДНФ булевої функції f виконати всі можливі узагальнені склеювання, а потім виконати всі поглинання, то в результаті отримаємо скорочену ДНФ функції f.

Приклад 1. Булева функція f1 задана довільною ДНФ

    

.

Знайти методом Блейка – Порецького скорочену ДНФ функцію f. Проводимо узагальнене склеювання. Легко побачити, що перший та другий елемент заданої ДНФ допускають узагальнене склеювання за змінною x1. В результаті склеювання маємо

.

Перший та третій елемент ДНФ допускають узагальнене склеювання як за елементом x1 так і за x2 , після склеювання за x1 маємо результат

.

Склеювання за x2 дає аналогічний результат

.

Другий та третій елемент ДНФ допускають узагальнене склеювання за змінною x2. Після склеювання отримуємо

.

Виконавши останнє узагальнене склеювання, переходимо до ДНФ:

.

Після виконання поглинань отримуємо

.

Спроби подальшого використання операції узагальненого склеювання і поглинання не дають результату. Отже, отримана скорочена ДНФ функції Далі задача пошуку мінімальної ДНФ вирішується за допомогою імплікантної матриці таким же чином, як і в методі Квайна.

Приклад 2. Булева функція f2 задана довільною ДНФ.

.

Знайти методом Блейка – Порецького скорочену ДНФ функції f2. Проводимо узагальнене склеювання. Легко побачити, що другий та четвертий елемент заданої ДНФ допускають узагальнене склеювання за змінною x3. В результаті склеювання маємо

.

Очевидно, що ніякі інші елементи заданої ДДНФ не допускають узагальнене склеювання за іншими змінними.

Виконавши останнє узагальнене склеювання, переходимо до ДНФ:

.

Після виконання поглинань отримуємо

.

Як і у першому прикладі подальше використання операції узагальненого склеювання і поглинання не дають результату, мінімальну ДНФ знаходять за допомогою імплікантної матриці, як у методі Квайна.

  Зміст