Канонічна форма

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Канонічна форма - така форма, що однозначно репрезентує об'єкт. Її часто плутають зі схожим поняттям нормальна форма.
В булевій алгебрі деяка булева функція може бути виражена у канонічному вигляді з використанням мінтермів або макстермів. Мінтерми і макстерми є взаємозамінними, що можна показати за допомогою законів де Моргана, які стверджують, що ¬(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).

Властивості досконалих форм[ред.ред. код]

Будь-яка кон'юнктивна або диз'юнктивна нормальна форма не дає однозначного подання функції, яке буде тільки при досконалих нормальних формах (ДДНФ та ДКНФ);

  • у ДДНФ (ДКНФ) немає двох однакових мінтермів (макстермів);
  • у ДДНФ (ДКНФ) жоден із мінтермів (макстермів) не містить двох однакових змінних;
  • у ДДНФ (ДКНФ) жоден із мінтермів (макстермів) не містить разом зі змінною її заперечення.


Приклади[ред.ред. код]

Див. також[ред.ред. код]