Лекція 3. Форми подання перемикальних функцій

 

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

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

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

Термін диз’юнктивна вказує, що зовнішньою функцією розкладання є диз’юнкція, а внутрішньою — кон’юнкція, так як для обчислення значення функції спершу знаходяться значення всіх кон’юнкцій, а потім обчислюється їх диз’юнкція.

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

Наприклад, таблиця істинності перемикальної функції Y (див. табл. 1.1) має такий вигляд:

Таблиця 1.1 – Таблиця істинності перемикальної функції Y

Х1 Х2 Х3 Y

 

ДДНФ перемикальної функції (1.12) записується наступним чином:

( 1.12)

При побудові канонічних форм використовуються найпростіші вирази, що являють собою кон’юнкції або диз’юнкції декількох різних змінних, взятих із запереченнями або без них. Ці вирази відповідно називаються елементарним добутком (кон’юнкцією, термом) і елементарною диз’юнкцією (диз’юнктивним термом).

Елементарний добуток, що містить всі змінні x1, x2, … , xn функції та рівний 1 на одному наборі аргументів і 0 на інших, називається конституентою одиниці.

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

Ефективний спосіб знаходження МДНФ при невеликій кількості змінних (не більше 6) полягає у застосуванні так званих діаграм Вейча, які є різновидом таблиць істинності [5].

Кожна змінна на діаграмі Вейча розбиває її навпіл. Кожному набору значень аргументів відповідає одна клітка діаграми Вейча. Якщо на даному наборі функція рівна одиниці, то у відповідній йому клітці записується 1. Клітки, що відповідають наборам, на яких функція рівна нулю, або заповнені нулями, або залишають порожніми. Наборам (0,0); (0,0,0), … і конституентам , відповідають клітки з номером 0. Наборам (0,1), (0,0,1), … і конституентам , — клітки з номером 1.

Мінімізація перемикальної функції полягає у застосуванні операції склеювання до конституент (елементарних добутків), у яких усі букви, за винятком одної, співпадають. Такі конституенти називаються сусідніми. Всі сусідні конституенти мають на діаграмі сусідні клітки, за винятком кліток, розташованих у меж діаграми. Для усунення цього винятку, умовно ототожнюють протилежні межі діаграми (верхню з нижньою і ліву з правою), тобто діаграму подумки згортають. Будь-яким двом сусіднім кліткам відповідає елементарний добуток, який є спільною частиною відповідно двох конституент та має на одну букву менше. Будь-яким чотирьом сусіднім кліткам відповідає елементарний добуток, який є спільною частиною відповідно чотирьох конституент і має на дві букви менше і т. д. Тому склеювати можна сусідні 2, 4, 8, 16 і т.д. одиниць на діаграмі Вейча.

Знаходження МДНФ зводиться до визначення мінімальної кількості найбільш коротких елементарних добутків, що накривають всі одиниці на діаграмі Вейча данної функції.

Нехай деяка функція задана таблицею істинності (табл. 1.2), якій відповідає діаграма Вейча на рис 1.1.

Таблиця 1.2 – Таблиця істинності функції Y

Х1 Х2 Х3 Y1
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Рис 1.1. Діаграма Вейча функції Y

 

 

МДНФ цієї функції (1.13) має вигляд:

(1.13)

Рівняння (1.14) – (1.17) визначають можливі канонічні нормальні форми цієї функції.

(1.14)

(1.15)

(1.16)

(1.17)

Форми, які були отримані з МДНФ функції за рівняннями (1.14) – (1.17) мають назви (I/АБО), (І-НЕ/І-НЕ), (АБО/І-НЕ), (АБО-НЕ/АБО) відповідно з визначенням внутрішньої та зовнішньої функції розкладання.

Скориставшись МДНФ заперечення заданої функції (1.18), тобто

, (1.18)

отримаємо рівняння (1.19) – (1.22), які визначають ще чотири канонічні нормальні форми:

,

(1.19)

(1.20)

(1.21)

1.22)

Форми, які були отримані з МДНФ заперечення функції за формулами (1.19) – (1.22) мають назви (І/АБО-НЕ), (І-НЕ/І), (АБО/І), (АБО-НЕ/АБО-НЕ) відповідно з визначенням внутрішньої та зовнішньої функції розкладання.

Всі отримані форми є дворівневими (нормальними).