Канонічна форма
Канонічна форма - така форма, що однозначно репрезентує об'єкт. Її часто плутають зі схожим поняттям нормальна форма.
В булевій алгебрі деяка булева функція може бути виражена у канонічному вигляді з використанням мінтермів або макстермів. Мінтерми і макстерми є взаємозамінними, що можна показати за допомогою законів де Моргана, які стверджують, що ¬(x˄y˄z˄...)=(¬x˅¬y˅¬z˅...), або навпаки ¬(x˅y˅z˅...)=(¬x˄¬y˄¬z...), де знак "¬" позначає логічне ні, "∨" — логічне або, "∧" — логічне і. Ця властивість називається двоїстістю булевих функцій, тобто будь-яку булеву функцію можна виразити за допомогою двох операцій (˅,¬) або (˄,¬). Отже, канонічна форма є сумою мінтермів, або макстермів булевої функції.
Формальне визначення
Нехай ми маємо множину, на якій визначене відношення еквівалентності. Воно розбиває множину на класи еквівалентності. Можна вибрати один елемент з кожного класу еквівалентності, та назвати його канонічною формою. Тепер цей елемент однозначно ідентифікує свій клас розбиття. Алгоритм отримання канонічної форми з довільного елементу класу еквівалентності називають канонізацією. Канонізація еквівалентна визначенню класу еквівалентності.
Використання
Зазвичай використання булевих функцій потрібне для спрощення будови мікросхем(виключення зайвих вузлів та скорочення часу виконання певних функцій).
Існує шістнадцять видів булевих функцій із двома змінними, але в цифрових пристроях використовуються лише три з них: кон'юнкція, диз'юнкція і заперечення, які позначаються ˄,˅, ¬ відповідно.
Мінтерми
Конституентою одиниці (мінтермом) називають булеву функцію, що представлена у вигляді елементарної кон'юнкції, яка набуває значення 1 тільки на одному з кортежів (наборів) своїх змінних. Кількість різних конституент одиниці для функціЇ, яка містить n аргументів дорівнює числу різних кортежів, тобто 2n.
Наприклад, (¬a∧b∧c), (a∧¬b∧c) та (a∧b∧¬c) є трьома мінтермами з восьми існуючих для булевої функції з 3-ма змінними. Останній можна прочитати, як a і b і не c.
Позначення мінтермів
Загалом для кожного мінтерму існує своєрідний номер (індекс), який дорівнює двійковому числу, яке відповідає цьому мінтерму. Наприклад, мінтерм (a∧¬b∧c) має індекс або двійкову форму 101 , де кожен елемент мінтерму без заперечення записуються як 1 (a=1, c=1), а з запереченням відповідно навпаки рівний 0 (¬b=0). Отже, мінтерм (a∧¬b∧c)) має порядковий номер 510=1012.
Досконала диз'юнктивна нормальна форма
Мінтерм є істинним (еквівалентний 1) лише при одній комбінації своїх елементів. Наприклад, мінтерм (a∧¬b∧c) істинний при a=1 ¬b=0 та c=1. Будь-яку булеву функцію можна записати через «суму її мінтермів». Якщо функцію подано у вигляді диз'юнкції елементарних кон'юнкцій, то її задано у диз'юнктивній нормальній формі (ДНФ). Досконалою диз'юнктивною нормальною формою (ДДНФ) булевої функції називається диз'юнкція тих мінтермів, які перетворюються в одиницю на тих самих наборах змінних, що й задана функція. Будь-яка булева функція має одну ДДНФ (кількість її членів дорівнює кількості одиничних значень функції) і кілька ДНФ. Будь-яка ДНФ утворюється внаслідок більшого або меншого скорочення ДДНФ, причому від будь-якої ДНФ можна перейти до ДДНФ. Такий перехід називається розгортанням.
Можна навести такі властивості ДДНФ, що виділяють її з усіх ДНФ:
- в ній немає однакових доданків;
- жоден із доданків не містить двох однакових співмножників;
- жоден із доданків не містить змінну разом із її запереченням;
- в кожному окремому доданку є як співмножник або змінна xi, або її заперечення для будь-якого i = 1, 2, …, n.
До прикладу наведемо таблицю, в якій булева функція F(a, b,c) є диз'юнктивною сумою всіх комбінацій своїх елементів.
| a | b | c | F(a,b,c) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Очевидно що 2,3,5, 8-ий кортежі є мінтермами, тобто дану функцію F(a, b, c) можна записати через їх диз'юнктивну суму: F(a, b, c) = (¬a∧¬b∧c) ∨ (¬a∧b∧¬c) ∨ (a∧¬b∧¬c) ∨ (a∧b∧c). Цей запис еквівалентний всім кортежам даної функції.
Макстерм
Конституентою нуля (макстермом) називають булеву функцію, що представлена у вигляді елементарної диз'юнкції, яка набуває значення 0 тільки на одному з кортежів своїх змінних. Кількість різних конституент нуля для функцій n аргументів дорівнює числу різних кортежів, тобто 2n.
Позначення макстермів
Індексація макстермів відбувається за оберненим до позначення мінтермів правилом, тобто якщо елемент макстерму стоїть у заперечній формі, то йому присвоюється одиниця, а якщо без, то нуль. Наприклад, макстерм (¬a∨¬b∨c) має індекс 6, або ж 110 у двійковій формі запису (¬a=1, ¬b=1,c=0).
Досконала кон'юнктивна нормальна форма
Кожен з макстермів приймає хибне значення (0) тільки при одній комбінації своїх елементів. Наприклад, макстерм (¬a∨b∨¬c) є хибним тільки, коли і a=1, і c=1, і b=0.
Кожну булеву функцію можна подати у формі всіх її макстермів. Якщо функцію подано у вигляді кон'юнкції елементарних диз'юнкцій, то її задано у кон'юнктивній нормальній формі (КНФ). Досконалою кон'юнктивною нормальною формою (ДКНФ) булевої функції називається кон'юнкція тих макстермів, які перетворюються в нуль на тих самих наборах змінних, що й задана функція. Також по аналогії з ДДНФ, будь-яка булева функція має одну ДКНФ (кількість її членів дорівнює кількості нульових значень функції) і декілька КНФ. Можна навести такі властивості ДКНФ, що виділяють її з усіх КНФ:
- в ній немає однакових співмножників;
- жоден із співмножників не містить двох однакових доданків;
- жоден із співмножників не містить якої-небудь змінної разом з її запереченням;
- в кожному окремому співмножнику є як складова або змінна xi, або її заперечення для будь-якого i=1,2,…,n.
| a | b | c | F(a,b,c) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
В наведеній таблиці булева функція F(a,b,c) є кон'юнктивною сумою всіх комбінацій своїх елементів. Очевидно, що 1,2,3,5-ий рядки відповідають макстермам функції F(a,b,c), тобто цю функцію можна записати у вигляді : F(a, b, c) = (a∨b∨c) ∧ (a∨b∨¬c) ∧ (a∨¬b∨c) ∧ (¬a∨b∨c).
Властивості досконалих форм
Будь-яка кон'юнктивна або диз'юнктивна нормальна форма не дає однозначного подання функції, яке буде тільки при досконалих нормальних формах (ДДНФ та ДКНФ);
- у ДДНФ (ДКНФ) немає двох однакових мінтермів (макстермів);
- у ДДНФ (ДКНФ) жоден із мінтермів (макстермів) не містить двох однакових змінних;
- у ДДНФ (ДКНФ) жоден із мінтермів (макстермів) не містить разом зі змінною її заперечення.