Констітуенти і уявлення функцій - студопедія

Формула (або соответствующаяей функція) називається здійсненною, якщо вона не є тождест-венним нулем або одиницею. Рішення за допомогою кінцевого числа дій питання, чи є дана формула здійсненним, т. Е. Не дорівнює чи вона тотожно нулю або одиниці, носить назва-ня проблеми розв'язання.

Відповідь на це питання можна отримати, побудувавши для даної формули таблицю відповідності, що зводиться по суті до визна-поділу значень формули при всіляких наборах значенні входять до неї змінних. Якщо на всіх наборах формула прини-томить значення тільки 0 або тільки 1, то вона нездійсненна.

При великій кількості змінних такої спосіб практично неможливий через величезну числа можливих наборів значень змінних. Більш зручний шлях - приведення формули до нор-бітної формі. Якщо в процесі такого приведення формула не звертається в тотожний 0 або 1, то це свідчить про її здійсненності.

Для сукупності змінних вираз називають конституентов одиниці, а вираз - конституентов нуля (означає або, або). Дана конституента одиниці (нуля) звертається в одиницю (нуль) тільки при одному відповідаю-щем їй наборі значень змінних, який виходить, якщо всі змінні прийняти рівними одиниці (нуля), а їх заперечення - нулю (одиниці). Наприклад, конституенте одиниці відпо-ветствует набір (1011), а конституенте нуля - набір (1001).

Так як досконала діз'юнктівная (Кон'юнктивна) нор-мальна форма є диз'юнкція (кон'юнкція) констітуєнт одиниці (нуля), то можна стверджувати, що надається нею булева функція f () звертається в одиницю (нуль) тільки при наборах значень змінних, які відповідають цим конституентов. На інших наборах ця функція звертається в нуль (одиницю).

Справедливо і зворотне твердження, на якому заснований спосіб представлення у вигляді формули будь-якої булевої функції, заданої таблицею. Для цього необхідно записати диз'юнкції (кон'юнкції) констітуєнт одиниці (нуля), відповідних наборів зна-чень змінних, на яких функція приймає значення, рав-ве одиниці (нуля).

Приклад. Функції, заданої таблицею

відповідають вчинені нормальні форми:

Отримані вирази можна перетворити до іншого Відун підставі властивостей булевої алгебри.