Алгоритм отримання СКНФ по таблиці істинності
2. Виписати для кожної зазначеної рядки диз'юнкцію всіх пере-сних наступним чином: якщо значення деякої змінної в дан-ної рядку дорівнює 0. то в диз'юнкцію включати саму цю змінну, есліравно 1, то її заперечення: - для 1-го рядка; - для 4-го рядка.
3. Всі отримані диз'юнкції зв'язати в кон'юнкцію: (2 *)
Якщо ми хочемо побудувати формулу деякої функції по таблиці істинності цієї функції, то завжди можна отримати СКНФ або СДНФ цієї функції.
20 Булева алгебра. Логічні функції однієї або кількох змінних.
Булеві функції двох змінних
У таблиці 2.3 представлені наступні функції двох змінних:
функція однієї зміною може мати чотири значення: y = x; y = x (заперечення х); y = 0 (константа 0); y = 1 (константа 1).
21 Суперпозиції функцій. Повні системи логічних функцій.
Нехай є деякий набір K. складається з кінцевого числа булевих функцій. Суперпозицією функцій з цього набору називаються нові функції, отримані за допомогою кінцевого числа застосування двох операцій;
можна перейменувати будь-яку змінну, що входить в функцію з K;
замість будь-якої змінної можна поставити функцію з набору K або вже утворену раніше суперпозицію.
Суперпозицію ще інакше називають складною функцією.
Приклад 7. 1. Якщо дана одна функція х | y (штрих Шеффера), то її суперпозиціями, зокрема, будуть наступні функції x | x, x | (X | y), x | (Y | z) і т. Д.
Замиканням набору функцій з K називається безліч всіх суперпозиций. Клас функцій K називається замкнутим. якщо його замикання збігається з ним самим.
Набір функцій називається повним. якщо його замикання збігається з усіма логічними функціями. Інакше кажучи, повний набір - це безліч таких функцій, через які можна виразити всі інші булеві функції.
Ненадлишкових повний набір функцій називається базисом ( "ненадлишкових" означає, що якщо якусь функцію видалити з набору, то цей набір перестане бути повним).
Система логічних функцій називаетсяФункціонально повною системою. якщо будь-яка логічна функція може бути виражена через функції за допомогою їх суперпозиції (бути виражена формулою над).
З (3.3) випливає, що система є функціонально повною. Очевидно, що будь-яка система, через функції якої можна висловити кон'юнкцію, диз'юнкцію і заперечення, буде повною. Дійсно, для будь-якої функції f можна взяти булеву формулу (по (3.3.-, (3.3.)
) Або (3.24.)), І все булеві операції в них замінити формулами над, що представляють ці операції. Нескладно також довести твердження.
Затвердження: якщо система - функціонально повна і любаяможет бути виражена суперпозицией через функції, тоді сістематоже функціонально повна.