Способи задання логічних функцій

Існують такі способи задання або запису логічних функцій – аналітичний, табличний, за допомогою карт Карно, графічний та кубічний.

Аналітично логічна функція може бути записана різними комбінаціями кон’юнкцій та диз’юнкцій логічних змінних. Зазвичай логічні функції записуються або у вигляді суми добутків логічних змінних (диз’юнкція кон’юнкцій) або у вигляді логічного добутку їх сум (кон’юнкція диз’юнкцій). Наведення функції у вигляді диз’юнкції кон’юнкцій називають диз’юнктивною нормальною формою (ДНФ):

,

а запис у вигляді кон’юнкції диз’юнкцій – відповідно, кон’юнктивною нормальною формою (КНФ):

.

Інверсія у відповідності з теоремою де Моргана будь-якої функції, приведеній в одній формі, призводить до заміни запису на іншу форму.

Наприклад, інверсія функції

представляється у вигляді:

.

Будь-яка логічна функція, задана в аналітичній формі, може бути перетворена на ДНФ або КНФ за допомогою тотожностей та законів алгебри логіки. При цьому для однієї і тієї ж функції може існувати декілька рівнозначних диз’юнктивних та кон’юнктивних нормаль­них форм.

У той же час, існує лише один вид ДНФ та КНФ, в яких функція може бути записана єдиним чином. Такі форми називаються досконалими диз’юнктивними (кон’юнктивними) нормальними формами (ДДНФ, ДКНФ). Вони характеризу­ються тим, що в ДДНФ кожна кон’юнкція, а в ДКНФ кожна диз’юнкція містять усі логічні змінні даної функції, з інверсіями або без них.

Прикладами ДДНФ та ДКНФ запису є функції чотирьох змінних

Оскільки кожна кон’юнкція функції, що наведена у ДДНФ, визначає її істинне значення, відповідаюче “1”, то такі кон’юнкції називаються конституєнтами одиниці (мінтермами). Аналогічно, диз’юнкції функції, що наведені у ДКНФ, називаються конституєнтами нуля (макстермами).

Якщо замінити логічні змінні та їх заперечення одиницями та нулями, то кожна кон’юнкція буде представляти собою двійкове число.

Це дозволяє, наприклад, вище наведену логічну функцію у₁ записати у вигляді:

.

Така форма називається досконалою скороченою диз’юнктивною формою або канонічною сумою.

Приклад 2.5. Функцію з прикладу 2.4 зобразити в скороченій диз’юнктивній канонічній формі.

Розв’язання. Перепишемо функцію, дещо змінивши нумерацію і порядок розміщення змінних:

.

Скорочена диз’юнктивна канонічна форма приведеної функції матиме вигляд (y порядку розміщення кон’юнкцій):

.

Аналогічно, функцію можна зобразити і у вигляді добутку макстермів. Така форма запису називається канонічним добутком. Наприклад:

.

Легко бачити можливість конвертації в представленні функції у вигляді макстермів та мінтермів, оскільки кожна з них доповнює функцію до повного перебору логічних змінних. Як приклади, можемо записати:

Індекси біля умовних позначень операцій диз’юнкції та кон’юнкції вказують на діапазон можливих мінтермів та макстермів логічних функцій. Нижній індекс іноді не вказується.

Досконала диз’юнктивна нормальна форма запису дозволяє легко перейти до інших форм запису – табличної та карт Карно.

У табл. 2.2 наведені функції у₁ … у₅двох змінних х₀та х₁. Табличний спосіб полягає у тому, що функція задається у вигляді таблиці відповідності (таблиці істинності станів). У таблицю вписують усі можливі комбінації аргументів у порядку зростання їх індексів і при кожній комбінації встановлюється значення функції. Кількість всіх можливих сполук аргументів, а, отже, і кількість значень функції дорівнює 2ⁿ, де n – кількість логічних змінних. З табличної форми запису легко перейти до аналітичної, використовуючи досконалу диз’юнктивну форму запису логічних функцій. Для цього функція записується як диз’юнкція конституєнт одиниці. Наприклад, функцію у₃ з табл. 2.2можемо записати у вигляді:

.

Ця функція може бути записана і з використанням нульових її значень:

Використовуючи властивість подвійної інверсії, легко встановити тотожність обох форм запису.

Логічна функція іноді може бути неповністю визначеною. У табл. 2.2 приводиться форма запису функції у₁ , яка є невизначеною при х₁ = х₀ = 1. При переході до аналітичної форми запису вона повинна бути довизначена.

Функції двох змінних займають у булевій алгебрі особливе місце. Для двох змінних кількість булевих функцій дорівнює 16. Ці функції називаються елементарними і складають максимальний набір функцій двох змінних. У табл. 2.3 наведені всі елементарні функції двох змінних.

За своєю застосованістю вони різні. Найбільш широке використання знаходять функції І, АБО, І-НІ, АБО-НІ, ВИКЛ. АБО. Вони універсальні тому, що за їх допомогою можна записати будь-яку іншу функцію.

Розроблений математичний апарат аналізу та синтезу булевих функцій найбільш відпові­дає цим функціям. Набір логічних функцій І, АБО, НІ дозволяє реалізувати будь-яку іншу функцію і називається функціонально повним.

Таблиця 2.3.

N	x0					Назва функції	Позначення
х1
						Константа нуль
						Кон’юнкція, І
						Заборона по х0
						Змінна х1	x1
						Заборона по х1
						Змінна х0	х0
						Викл. АБО, сума за mod 2	х1 Å х0
						Диз’юнкція, АБО	х1 + х0
						АБО-НІ, функція Пірса
						Рівнозначність, еквівалентність	х1 º х0
						Заперечення х0
						Імплікація по х0	х0® х1
						Заперечення х1
						Імплікація по х1	х1®х0
						Функція Шеффера І-НІ
						Константа 1

У практичній схемотехніці найбільш поширеними є системи, які реалізують логічні функції І-НІ, АБО-НІ, ВИКЛ. АБО. Вони дозволяють найбільш просто реалізовувати різні функції, мати більшу кількість входів, прості в технічній реалізації.

Теорема Шенона

Широке використання при перетворенні логічних функцій знаходять теорема Шенона та ряд тотожностей, які витікають з неї.

Теорема Шенона формулюється так: будь-яку функцію n зміних можна зобразити в формі:

. (2.1)

Теорема Шенона виявляється дуже корисною при виконанні перетворень логічних виразів, що містять операцію ВИКЛ. АБО.

Приклад 2.6. Виконати перетворення логічної функції:

.

Розв’язання. Використовуючи теорему Шенона, виконаємо наступний ряд перетворень:

З теоремою Шенона (2.1) пов’язані тотожності:

(2.2)

Виходячи з теореми де Моргана, тотожностям (1.18) відповідають наступні тотожності:

(2.3)

Тотожності (2.2) і (2.3) широко використовуються для спрощення логічних виразів. З них витікають формули, які широко використовуються:

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

Приклад 2.7. Спростити логічну функцію:

.

Використовуючи тотожність (1.18) відносно , маємо:

З тотожності (1.19) знаходимо:

.

В результаті знаходимо:

.

Приведені вище тотожності використовуються для того, щоб розкладати складні логічні функції на більш прості.