Головна |
нехай F - Двійкова функція від n змінних. Припустимо, що F не дорівнює тотожно нулю. нехай T1, T2,..., Tk - Всі крапки її визначення, в яких F= 1. Можна довести, що справедлива наступна формула:
,
де , J = 1,2, ..., k,
побудувати функцію F можна і по-іншому. якщо функція F не дорівнює тотожно одиниці і S1, S2, ..., Sm - Всі крапки області її визначення, в яких F= 0, то справедлива формула:
,
де , j = 1,2, ..., m.
З наведених формул видно, що будь-яку двійкову функцію можна записати, використовуючи лише операції, , .
Основна кон'юнкція - це кон'юнкція основних висловлювань змінних або їх заперечень. наприклад, .
Основна диз'юнкція - це диз'юнкція основних висловлювань змінних або їх заперечень. наприклад, .
Кон'юнктівной нормальною формою (КНФ) даної формули називається формула, рівносильна даній і представлена ??у вигляді кон'юнкції основних диз'юнкцій. наприклад, (A + B) (A + C + B) (D + A).
Диз'юнктивній нормальною формою (ДНФ) даної формули називається формула, рівносильна даній і представлена ??у вигляді диз'юнкції основних кон'юнкція. наприклад, AB + C + AC.
Теорема 1. Для того щоб формула алгебри висловлювань була тотожно істинною, необхідно і достатньо, щоб її КНФ містила в кожної елементарної диз'юнкції деякий висловлювання і його заперечення.
Теорема 2. Для того щоб формула алгебри висловлювань була тотожно хибною, необхідно і достатньо, щоб її ДНФ містила в кожної елементарної кон'юнкції деякий висловлювання і його заперечення.
Вчинені диз'юнктивні, кон'юнктівние і поліноміальні нормальні форми подання переключательних (логічних) функцій. Різноманіття формул, за допомогою яких може бути виражена будь-яка логічна функція, визначає різноманіття форм логічних функцій, т. Е. Способів їх запису шляхом застосування до змінних і їх групам елементарних логічних операцій. Найбільш зручними для практичного використання виявляються вчинені нормальні форми представлення складних логічних функцій. В алгебрі логіки доводять, що будь-яка логічна функція F (A, B, C, ..., N) може бути представлена ??тільки однією досконалої диз'юнктивній нормальною формою (крім константи нуль) або тільки однієї досконалої кон'юнктівной нормальною формою (крім константи одиниця).
нехай функція X = F (A, B, C) задана таблицею 4. Запис функції Х у вигляді логічної суми (диз'юнкції) логічних творів (кон'юнкція) змінних, для яких значення функції Х дорівнює 1, і є досконалою диз'юнктивній нормальною формою (СДНФ) уявлення логічної функції.
Таблиця 4
A | B | C | X |
СДНФ логічної функції слід знаходити в такій послідовності:
1) скласти твори змінних для рядків таблиці істинності, в яких Х дорівнює 1. Якщо значення змінної (А, В або С) В рядку дорівнює 0, то в творі записується заперечення цієї змінної;
2) написати суму творів, для яких функція Х дорівнює 1. Отримана сума і є СДНФ. У загальному вигляді
, (1)
Це правило називають правилом записи перемикальної функції по одиницям. Згідно з цим правилом, дані табл. 4 описуються аналітичним виразом, що зв'язує всі набори змінних, для яких Х= 1, у вигляді:
. (2)
запис функції Х у вигляді логічного твори (кон'юнкції) логічних сум (диз'юнкцій) змінних, для яких функція Х дорівнює 0, є досконалою кон'юнктівной нормальною формою (СКНФ) уявлення логічної функції.
Для табл. 4 аналітичний вираз в СДНФ, що зв'язує всі набори змінних, для яких Х= 0, має вигляд:
. (3)
Для подання логічної функції Х в СКНФ зробимо операцію заперечення лівої і правої частин рівності (3)
і на підставі законів подвійного заперечення і інверсії
. (4)
СКНФ логічної функції, згідно (4), слід знаходити в такій послідовності:
1) скласти логічні суми змінних для рядків таблиці істинності, в яких функція Х дорівнює 0. Якщо значення змінної (А, В або С) В рядку дорівнює 1, то в сумі записується заперечення цієї змінної;
2) написати логічне твір складених логічних сум. Отримане твір і є СКНФ. У загальному вигляді:
, (5)
де Fi - Складні диз'юнкції.
Це правило також називають правилом побудови перемикача функції по нулях.
Окрім представлення функцій у вигляді СДНФ і СКНФ використовують і досконалу поліноміальних нормальну форму СПНФ. Замість диз'юнкції може бути записана функція додавання за модулем два (сума Жегалкина):
, (6)
де Fi - Складні кон'юнкції.
Існує спеціальна таблиця, в якій всі елементарні логічні операції від двох аргументів представлені в двох досконалих нормальних формах.
Нормальні форми подання перемикальної функції іноді називають стандартними (Табл. 5).
Таблиця 5
f | A B | Назва функції | позначення функції | СДНФ | СКНФ |
f0 | Константа нуль | Не має | |||
f1 | Логічне твір, кон'юнкція | ||||
f2 | Заборона по В | ||||
f3 | змінна А | ||||
f4 | Заборона по А | ||||
f5 | Мінлива В | ||||
f6 | Сума по мо дулю 2, логічна нерівнозначність | ||||
f7 | Роз'єднання, диз'юнкція | ||||
f8 | Операція (стрілка) Пірса, операція Вебба | ||||
f9 | Еквівалентність, логічна рівнозначність | ||||
f10 | інверсія В | ||||
f11 | Імплікація від В до А | ||||
f12 | інверсія А | ||||
f13 | Імплікація від А до В | ||||
f14 | Операція (штрих) Шеффера | ||||
f15 | Константа одиниця | Не має |
Многочленом Жегалкина називається многочлен, який є сумою константи 0 або 1 і різних одночленним, в які всі змінні входять не вище, ніж в першого ступеня.
Теорема. Будь-яка функція булевої алгебри може бути представлена, і до того ж єдиним чином, за допомогою полінома Жегалкина виду
J = .
Уявімо, наприклад, у вигляді полінома вираз виду X1 X2. Для цього проведемо наступні міркування.
нехай
X1 X2 = aX1X2+ bX1+ cX2+ K,
де а, b, с, k - Невизначені коефіцієнти.
при X1 = X2 = 0 маємо k = 0. При Х1 = 1, X2= 0 маємо b= 1. При Х1= 0, Х2= 1 маємо с= 1. При X1= Х2= 1 маємо а + b + с = 1, т. Е. а = -1. Таким чином, отримуємо:
X1 X2 = - X1X2+ X1+ X2.
СПНФ утворюється шляхом заміни в СДНФ: на + і на
1 х.
,
,
В останньому випадку вираз для легко можна спростити, якщо розкрити дужки і взаємно скоротити всі однакові складові, що входять в формулу парне число раз:
.
Подібне спрощення, яке називається мінімізацією логічної функції, можна здійснити і по відношенню до СДНФ і СКНФ.
Таблиця 6
y | |||
Застосування законів алгебри логіки дозволяє знайти більш компактні аналітичні вирази для заданої функції у, Т. Е. Мінімальну діз'юнктівную нормальну форму . Наведемо відповідні форми представлення функції у, Заданої табл. 6:
,
і для СКНФ, т. е. мінімальну КНФ:
.
Після того, як знайдені мінімальні нормальні форми (МНФ), їх рекомендується перевірити на всіх наборах аргументів . змінні або часто називають термами. Саме повний набір з n термів утворює конституенту. У процесі ж мінімізації деякі терми з констітуєнт пропадуть. Тоді решту диз'юнкт або Кон'юнктів називають импликантой.
Як ми тільки що переконалися на прикладі, імпліканти з'являються в результаті склеювання суміжних констітуєнт, що розрізняються одним термо.
Контрольні питання і вправи
1. Дайте визначення логічної функції багатьох змінних.
2. Що таке вектор значень булевої функції? Наведіть приклад побудови таблиці істинності логічної функції багатьох змінних.
3. Скільки існує булевих функцій від n змінних?
4. Що таке ДНФ і КНФ?
5. Який алгоритм побудови СДНФ? Наведіть приклад побудови СДНФ.
6. Який алгоритм побудови СКНФ? Наведіть приклад побудови СКНФ.
7. Складіть СКНФ і СДНФ для функції .
8. Наведіть приклад побудови СПНФ.
Дискретна математика | Введення в алгебру логіки | Основні функції алгебри логіки | Формули алгебри логіки | Закони алгебри логіки і наслідки з них | Алгебра Жегалкина і лінійні функції | Методи мінімізації логічних функцій | Неповністю певні логічні функції | Бінарні діаграми рішень (БДР) | Побудова логічних схем |