3.7     Мінімізація функцій в базисах І-НЕ та АБО-НЕ

Функції «стрілка Пірса» та «штрих Шеффера», як відмічено в п. 2.4, мають функціональну повноту. Нагадаємо, що зв’язок цих функцій з операціями диз’юнкції і кон’юнкції достатньо простий:

.

Узагальнюючи для n змінних, будемо мати:

;

.

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

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

Отже, КНФ функції f можна подати в такому вигляді:

де - елементарні диз’юнкції:

Використовуючи наведені співвідношення будемо мати :

Твердження доведено. Таким чином, мінімізацію функції можна відтворити в базисі І, АБО, НЕ, а потім перейти до стрілки Пірса. Операція заперечення реалізується за допомогою стрілки Пірса:

.

Оскільки функції «стрілка Пірса» та «штрих Шеффера» не підпорядковуються закону асоціативності, то це треба враховувати при переході від багатомісних операцій до двомісних. Такий перехід можна зробити за допомогою таких співвідношень:

справедливість яких легко перевіряється.

Приклад 1. Розглянемо функцію, яка задана діаграмою Вейча (див. табл. 3.12). Її мінімальна КНФ (одна з можливих):

.

Переходимо до операції «стрілка Пірса»:

.

Перехід до двомісних операцій дає можливість обрати кінцевий вираз:

.

Аналогічно відбувається перехід від ДНФ до виразу, що має тільки операції «штрих Шеффера». Мають місце аналогічні перехідні співвідношення

Таблиця 3.12

Приклад 2. Розглянемо ту ж саму функцію f (табл. 3.12). Її мінімальна ДНФ

Використовуючи перехідні співвідношення отримаємо

і далі переходимо до двомісних операцій, маємо кінцевий вираз

.