Повні системи перемикачів
Однією з найважливіших завдань, розв'язуваної у процесі синтезу комбінаційної схеми, є раціональний вибір логічних елементів, які будуть використовуватися під час технічної реалізації логічних схем. Тому основна вимога до набору логічних елементів полягає в тому, що на основі цього набору елементів, що реалізують елементарні логічні функції, можна побудувати комбінаційну схему, що реалізує довільну ПФ або (загалом) систему ПФ.
Отже, система логічних функцій, що описують синтезовану КС, має бути представлена у вигляді перемикальних функцій, що реалізуються обраним набором логічних елементів.
Система ПФ називаєтьсяфункціонально повною, якщо будь-яку булеву функцію довільної складності можна записати у вигляді формули з використанням функцій цієї системи.
Функціонально повна система ПФ називаєтьсябазисом. Найбільшого поширення набули базиси (штрих Шеффера), (стрілка Пірса).
Мінімальним базисомназивається такий базис, для якого виняток хоча б однієї з функцій, що утворюють цей базис, перетворює систему перемикальних функцій на неповну.
Базис може бути утворений елементарними функціями, що задовольняють умови теореми Посту - Яблонського.
Теорема. Для того, щоб система елементарних ПФ була функціонально повною, необхідно і достатньо, щоб вона включала хоча б одну функцію, що не зберігає нуль, не зберігає одиницю, самодвійну, не монотонну, не лінійну.
Доказ цієї теореми можна знайти у [6].
Сформулюємо низку визначень для класів перемикальних функцій, що згадуються в теоремі Посту – Яблонського.
Перший клас становлять функції, що зберігають константу 0. Для такихфункцій має виконуватися умова.
Другий клас складають функції, що зберігають константу 1. Для таких функцій має виконуватися умова .
Третій клас становлять самодвійні функції, які на парі протилежних аргументів набувають протилежних значень. Для самодвійних функцій виконується така рівність: . Прикладом такої функції може бути заперечення.
Четвертий клас становлять лінійні ПФ.Лінійною ПФназивається функція, яка може бути представлена поліномом за модулем 2 першого ступеня. У загальному вигляді лінійна ПФ може бути записана так: , де , .
П'ятий клас складають монотонні ПФ. Введемо критерій порівняння двох наборів аргументів. Два набори аргументів називаютьсяпорівняними, якщо значення кожного аргументу одного набору більше чи дорівнює значенню відповідних аргументів другого набору, тобто. ,
Монотонноюназивається така ПФ, на яку за будь-якому зростанні набору значення цієї функції не зменшуються, тобто. .
Приналежність деяких елементарних функцій того чи іншого класу представлена в табл. 3.6. На перетині рядка та стовпця поставлено позначку, якщо ця елементарна ПФ належить до зазначеного класу.
| Клас ПФ | Зберегти. 0 | Зберегти. 1 | Самодвійна | Монотонна | Лінійна |
| Константа 0 | Ú | Ú | Ú | ||
| Кон'юнкція | Ú | Ú | Ú | ||
| Диз'юнкція | Ú | Ú | Ú | ||
| Додавання за модулем 2 | Ú | Ú |
Закінчення табл. 3.6
| Еквівалентність | Ú | Ú | |
| Стрілка Пірса | |||
| Штрих Шеффера | |||
| Імплікація | Ú | ||
| Заперечення | Ú | Ú | |
| Константа 1 | Ú | Ú | Ú |
З наведеної таблиці випливає, що канонічний базис булевої алгебри І-АБО-НЕ, що включає кон'юнкцію, диз'юнкцію та заперечення, є функціонально повним відповідним вимогам теореми Посту – Яблонського. Такий базис є мінімальним, оскільки з нього без шкоди для повноти системи ПФ можна виключити кон'юнкцію чи диз'юнкцію. При цьому виходять системи ПФ, еквівалентні базисам І-НЕ, АБО-НЕ.
З табл. 3.6 можна отримати, наприклад, такі мінімальні базиси.
Базиси, що складаються з однієї елементарної ПФ:
1) стрілка Пірса;
2) штрих Шеффера.
Базиси, що складаються з двох елементарних ПФ:
1) заперечення, кон'юнкція;
2) константа 0, імплікація;
3) заперечення, диз'юнкція.
3.5. Канонічні форми аналітичного подання ПФ
Конституентою одиниціназивається функція, що приймає значення 1 тільки на одному наборі змінних. Конституента одиниці записується як логічний твірnрізних змінних, деякі з яких або всі можуть бути з запереченнями.
Конституентою нуляназивається функція, що приймає значення 0 на єдиному наборі змінних. Конституента нуля записується як логічна сумаnрізних змінних, частина яких або всі можуть бути з запереченнями.
Будь-яку конституенту 1 можна записати у вигляді кон'юнкції всіх її аргументів, при цьому змінна записується з інверсією, якщо в наборі, на якому функція приймає значення 1, змінна приймає значення 0. . На рештінаборах, як випливає з визначення, конституенту 1 приймає значення 0. Наведене вище твердження може бути доведено, наприклад, методом перебору.
Кожномуi-му набору аргументів поставимо у відповідність конституенту одиниці, що приймає одиничне значення тільки на цьому наборі.
Будь-яку перемикальну функцію, яка залежить від аргументів, можна представити у вигляді розкладання Шеннона:
.
Зробимо розкладання Шеннона за всіма змінними:
В отриманому виразі замінимо набори аргументів, поданих кон'юнкціями змінних, на відповідні конституенти 1. Тоді перемикальна функція у загальному вигляді може бути представлена таким чином:
,
де – значення функції наi-му наборі.
Скориставшись тим, що і в останньому виразі можна виключити доданки, для яких . Враховуючи, що , не можна писати коефіцієнти .
Таким чином, потрібну функцію можна представити у вигляді диз'юнкції конституент 1, відповідних наборам аргументів, на яких вона приймає значення 1. Така форма запису називаєтьсядосконалою диз'юнктивною нормальною формою(СДНФ). Така назва пояснюється тим, що кожен диз'юнктивний член включає твір всіх аргументів (досконала форма) і кожен твір є елементарним, тобто. під знаком інверсії можуть лише окремі змінні (нормальна форма).
Як приклад розглянемо процедуру запису СДНФ логічної функції, заданої таблицею істинності (табл. 3.7). Для представлення цієї функції у вигляді СДНФ необхідно виконати такі дії, засновані на наведених вище міркуваннях.
На першому етапі запишемофункцію як диз'юнкції конституент одиниці, відповідних тим наборам, у яких функція приймає значення 1:
Потім, висловивши конституенти одиниці через твори аргументів, отримаємо шукану СДНФ:
З СДНФ функції та СДНФ її заперечення, використовуючи закони де Моргана, можна отримати ще сім канонічних форм.
Інший канонічною формою запису єдосконала кон'юнктивна нормальна форма(СКНФ). Її відмінність від СДНФ полягає в тому, що СКНФ записується як кон'юнкція конституент нуля, відповідних тим наборам, на яких функція приймає значення 0. При цьому конституенти 0 записуються у вигляді елементарних диз'юнкцій аргументівxi, інверсії яких відповідають аргументу.
Наприклад запишемо СКНФ функції, заданої табл. 3.7, при цьому виконаємо послідовність дій, аналогічну до тієї, яка була наведена в попередньому прикладі.
На першому етапі запишемо функцію як кон'юнкції конституент нуля, відповідних тим наборам, у яких функція приймає значення 0:
Далі, висловивши конституенти нуля через диз'юнкції аргументів, отримаємо шукану СКНФ:
За допомогою законів де Моргана СКНФ функції можна отримати із СДНФ її заперечення, що записується по нулях. Як приклад розглянемо перетворення заперечення СДНФ функції, заданої табл. 3.7:
звідки, позбавляючись операції заперечення в початковій і кінцевій частинах висловлювання, отримаємо
.
У СДНФ можна замінити операцію диз'юнкції операцією суми за модулем 2. У тому, що рівність при цьому збережеться, можна переконатися шляхом зіставлення таблиць істинності виразів. Для розглянутого вище прикладу:
Така форма називаєтьсядосконалою поліноміальною нормальною формою(СПНФ).
Скористаємося співвідношенням та замінимо у СПНФ усі змінні із запереченнями на суми виду. Після спрощення отриманого виразу утворюється канонічний поліном Жегалкіна, який у загальному вигляді можна записати так [4]: