§6. Нормальні форми та поліноми

Піднесення до степеня булевих змінних визначається наступним чином: , .

Елементарною кон’юнкцією називається вираз , де всі змінні, що входять в склад кон’юнкції, різні, .

Диз’юнктивною нормальною формою (ДНФ) даної булевої функції називається її представлення у вигляді диз’юнкції деяких елементарних кон’юнкцій.

Для будь-якої булевої функції справедлива формула диз’юнктивного розкладу по сукупності змінних:

.

Досконалою диз’юнктивною нормальною формою (ДДНФ) даної булевої функції називається її представлення у вигляді:

.

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

1. у таблиці істинності для функції ( ) відмітити всі рядки , де ;

2. для кожного такого рядка утворити кон’юнкцію ;

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

Елементарною диз’юнкцією називається вираз , де всі змінні, що входять в склад диз’юнкції, різні, .

Кон’юнктивною нормальною формою (КНФ) даної булевої функції називається її представлення у вигляді кон’юнкції деяких елементарних диз’юнкцій.

Для будь-якої булевої функції справедлива формула кон’юнктивного розкладу по сукупності змінних:

.

Досконалою кон’юнктивною нормальною формою (ДКНФ) даної булевої функції називається її представлення у вигляді:

.

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

1. у таблиці істинності для функції ( ) відмітити всі рядки , де ;

2. для кожного такого рядка утворити диз’юнкцію ;

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

Поліномом Жегалкіна булевої функції називається її представлення у вигляді суми за модулем два деяких елементарних кон’юнкцій і, можливо, константи 1.

Поліном Жегалкіна може бути знайдений за допомогою формули

,

в котрій потрібно розкрити дужки та спростити вираз за допомогою співвідношень:

, , , .

Приклад 10. Знайти ДДНФ, ДКНФ та поліном Жегалкіна для функції , що задана таблицею істинності (табл. 11):

Таблиця 11.

№
1	0	0	0	1
2	0	0	1	1
3	0	1	0	0
4	0	1	1	1
5	1	0	0	0
6	1	0	1	0
7	1	1	0	0
8	1	1	1	1

Розв'язання. Для знаходження ДДНФ виділимо в таблиці рядки (1;2;4;8), де .

1-ий рядок дасть кон’юнкцію

2-ий рядок –

4-ий рядок –

8-ий рядок –

ДДНФ для даної функції прийме вигляд:

.

Для знаходження ДКНФ розглянемо рядки (3;5;6;7), де .

3-ій рядок дасть диз’юнкцію

5-ий рядок –

6-ий рядок –

7-ий рядок –

ДКНФ для даної функції прийме вигляд:

.

Для знаходження полінома Жегалкіна знову виділимо в таблиці 9 рядки (1;2;4;8), де :

1-ий рядок дасть кон’юнкцію

2-ий рядок –

4-ий рядок –

8-ий рядок –

Поліном Жегалкіна для даної функції прийме вигляд:

.