Нормальні форми булевих функцій
Нормальні форми - це особливий клас аналітичних виразів, що використовуються при вирішенні задачі мінімізації булевих функцій та для переходу від табличної форми завдання до аналітичної. Нормальні форми будуються виходячи з операцій кон'юнкції, диз'юнкції і заперечення, причому заперечення лише єдиної змінної.
Визначення.Елементарною кон'юнкцією (диз'юнкцією) називається кон'юнкція (диз'юнкція) кінцевого числа попарно помітних змінних або їх заперечень.
Елементарну кон'юнкцію (диз'юнкцію) називають такожкон'юнктивним (диз'юнктивним) термом.
В окремому випадку терм, як кон'юнктивний, так і диз'юнктивний, може складатися з єдиної літери (літералу). Під буквою розумітимемо аргумент булевої функції або його заперечення.
Прикладами термів є.
Вирази типу: термами не є, оскільки в першому випадку знак заперечення стоїть над двома змінними, а в другому зміннаx1перебуває у вираженні з запереченням і без нього.
Визначення.Рангом терму називається кількість літер, що входять до нього.
| Аргументи та функції (у символічній формі) | Значення аргументів та функцій | Позначення функцій | Найменування | Виродженість | Подання функції у булевому базисі |
| x1 | |||||
| x2 | |||||
| Логічний нуль | + | - | |||
| x1 & x2 | Кон'юнкція | - | |||
| x1 D x2 | Заборонаx1поx2 | - | |||
| x1 | Повторенняx1 | + | - | ||
| x2 Dx1 | Заборонаx2поx1 | - | |||
| x2 | Повторенняx2 | + | - | ||
| x1Å x2 | Сума за модулем 2, нерівнозначність, виключне АБО | - | |||
| x1Ú x2 | Диз'юнкція | - | |||
| x1¯ x2 | Функція Вебба, стрілка Пірса | - | |||
| x1 |
x2 (x1º x2)
| Значення аргументів | Значення функцій | ||||
| Сума за модулем 2 | Виключне АБО | Функція мажоритарності | |||
| x1 | x2 | x3 | x1Å x2Å x3 | XOR (x1, x2, x3) | x1#x2#x3 |
Визначення.Диз'юнктивною (кон'юнктивною) нормальною формою булевої функції називається диз'юнкція (кон'юнкція) кінцевого числа попарно помітних кон'юнктивних (Диз'юнктивних) термів.
Визначення.Конституентою одиниці (нуля) називається кон'юнктивний (диз'юнктивний) терм максимальногорангу, тобто. для булевої функції відnзмінних конституентів включаєnбукв.
Властивість конституенти.Конституента одиниці (нуля) приймає значення одиниці (нуля) однією і лише одному наборі аргументів.
Приклад: Приn= 4 кон'юктивний терм приймає значення, що дорівнює одиниці на наборі 1010, а диз'юнктивний терм приймає значення дорівнює нулю на наборі 1101.
Визначення.Диз'юнктивна (кон'юнктивна) нормальна форма називаєтьсяканонічної, якщо всі її кон'юнктивні (диз'юнктивні) терми представляють собою конституенти одиниці (нуля). Канонічні форми називають такождосконалими.
1. За допомогою канонічних форм найбільш просто здійснюється перехід від табличної форми завдання булевої функції до аналітичної.
2. За допомогою канонічних форм будь-яку булеву функцію можна представити у булевому базисі.
3. Будь-яка булева функція крім логічного нуля і логічної одиниці має єдині КДНФ і ККНФ. Логічну одиницю можна як КДНФ, а логічний нуль - як ККНФ.
4. Правило переходу від табличної форми завдання булевої функції до аналітичної:
а) у таблиці істинності виділяються всі набори аргументів, у яких функція дорівнює одиниці (нулю).
б) кожного з цих наборів становлять конституенти одиниці (нуля).
в) об'єднанням конституенти одиниці (нуля) знаками диз'юнкції (кон'юнкції) виходить аналітична форма як КДНФ (ККНФ).
Пояснення.При складанні конституент одиниці (нуля) використовують таке правило:Якщо певний аргумент приймає на наборі значення рівне нулю, то конституенту одиниці він входить із запереченням, а конституенту нуля без него.>
Приклад: отримаємо канонічні форми функціїy = x1 Å x2.
| x1 | x2 | y | Конституенти одиниці | Конституенти нуля |
| - | ||||
| - | ||||
| - | ||||
| - |
КДНФ - канонічна диз'юнктивна нормальна форма:
;
ККНФ - канонічна кон'юнктивна нормальна форма:
.
КДНФ і ККНФ є дві різні, але еквівалентні аналітичні форми булевої функції. Це означає, що з однієї форми можна отримати іншу, використовуючи закони булевої алгебри.
Існує інший спосіб отримання ККНФ:
а) складається КДНФ, але не для самої булевої функції, а для її заперечення.
б) береться заперечення над отриманою КДНФ, яка знімається із застосуванням закону двоїстості.
4. Числова та символічна форми представлення булевих функцій
Для будь-якої булевої функції можна запропонувати дві числові форми, що базуються на перерахуванні десяткових еквівалентів наборів аргументів, на яких функція набуває значення одиниці (нуля).
Наприклад:
Від числової форми легко перейти до КДНФ шляхом заміни кожного набору у перерахуванні конституентою одиниці.
.
Аналогічно можна перейти до ККНФ:
У самому компактному вигляді будь-яку булеву функцію можна представити в наступнійсимволічній формі : , деn-кількість аргументів, аN-десятковий еквівалент двійкового набору значень функції на впорядкованому множині аргументів.
Приклад:f 3 (Х)=x1Åx2Åx3=- символічна форма булевої функції.