ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     3.6. НОРМАЛЬНІ ФОРМИ

      Під "нормальною формою" будемо розуміти синтаксично однозначний спосіб запису формули, що реалізує задану функцію.

Введемо позначення:

;

або

      ТЕОРЕМА про розклад булевих функцій по зиінних.

Кожну функцію алгебри логіки при довільному можна представити у вигляді:


,

де диз'юнкція береться по всім можливим комбінаціям.

За умови

,

(Без доведення).

Якщо диз'юнкція береться по всім можливим комбінаціям , то

,

Такий розклад називають доскональною диз'юнктивною нормальною формою (ДДНФ).

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

1) в таблиці істинності для функції

, відмітити всі рядки , де ;

2) для кожного такого рядка утворити логічний добуток

;

3) всі отримані кон'юнкції об'єднати знаком диз'юнкції.

      Приклад 2. Знайти ДДНФ для функції , що задана таблицею істинності (табл. 9): Розв'язання. Виділимо в таблиці три рядки (1;2;8), де

1-й рядок дасть добуток

2-й рядок -

8-й рядок -

Доскональна диз'юнктивна нормальна форма для даної функції приймає вид:

Таблиця 9.

Довільна функція алгебри логіки може бути представлена також у виді кон'юнктивної нормальної форми. Для цього запишемо ДДНФ функції .

Користуючись правилом де Моргана, отримаємо:

;

( ; ).

Таке зображення булевої функції носить назву доскональної кон'юнктивної нормальної форми (ДКНФ).

Для функції (приклад 2), для якої ДДНФ прийняла вид



ДКНФ





.

ЗМІСТ