Page 40 - 4496

змінних можна визначити значення функції F і відповідно
з'ясувати чи є функція F здійсненою. Наведений спосіб дає
принципове вирішення проблеми ,але при великій кількості
змінних він практично нездійсненний через великий об'єм
обчислень.
Методи, які дають змогу для будь-якої перемикальної
функції визначити її тип без перебору всіх комбінацій змінних
ґрунтуються на тому, що вводяться вирази певної структури -
канонічні структури, а потім формуються прості правила для
будь-якої функції у цих структурах. Як канонічні звичайно
використовуються досконалі кон'юнктивна і диз'юнктивна
нормальні форми (ДДНФ і ДДКФ).

2.21 Нормальні та ДДНФ
Означення1. Логічний добуток будь-якої кількості
незалежних змінних, що входять із запереченням або без
нього називається елементарною кон'юнкцією.
Приклади
1 x 1 x 2 x - елементарна кон'юнкція;
3
2 x  x 2 x - не є елементарною кон'юнкцією;
3
1
Функція F (x 1 , x 2 ,...,x r ) - елементарна кон'юнкція рангу
r .
Означення 2. Якщо функцію задано у вигляді
диз'юнкції елементарних кон'юнкцій, то її задано
диз'юнктивною нормальною формою (ДНФ).
Приклад
f (x )  x 1 x 2 x 3  x 1 x 2 x 3  x 1 x 2 .
Означення3. Конституентою одиниці (мінтермом)
називають перемикальну функцію n аргументів, яка набуває
значення одиниці на одному із її кортежів. Максимальна
кількість конституент одиниці дорівнює кількості кортежів –
n
2 .
Твердження1. Будь-яка задана таблично функція
алгебри логіки може бути подана у вигляді
n
1
1
1
1
f (x 1, x 2, ..., x n) = F  F  ...  F =  F ,
1 2 n i
i 1
37