- •Розділ 1. Математичні основи синтезу логічних схем
- •1.1. Деякі поняття і визначення булевої алгебри
- •1.2. Способи задання булевих функцій
- •1.3. Булеві функції від однієї і двох змінних
- •1.4. Принцип суперпозиції логічних функцій. Пріоритет операцій
- •1.5. Аксіоми та закони булевої алгебри
- •Аксіоми кон’юнкції, диз’юнкції і заперечення:
- •1.7. Аксіоми та закони алгебри Жегалкіна
- •1. Комутативний закон
- •2. Сполучний закон
- •3. Розподільний закон по відношенню до додавання за модулем 2
- •1.8. Аксіоми та закони для функцій Шеффера та Пірса
- •1.9. Аналітичне подання булевих функцій
- •1.10. Класи булевих функцій. Теорема про повноту
- •1.11. Розвинення логічних функцій за змінними
- •1.12. Зв’язок між дднф і дкнф. Канонічні нормальні форми
1.4. Принцип суперпозиції логічних функцій. Пріоритет операцій
Як уже відмічалось, кількість логічних функцій від n аргументів визначається числом і швидко зростає при зростанні n. Наприклад, при n=3 таких функцій буде , а при n=4 їх буде уже і т.д. Тому, як уже відмічалось, подання функцій за допомогою таблиць істинності з ростом числа змінних стає громіздким і незручним.
Розглянуті елементарні функції дозволяють одержувати складні булеві функції, в тому числі і для довільної кількості змінних, за допомогою узагальненої операції, яка називається операцією суперпозиції, яка полягає в підстановці замість змінних вхідної функції інших булевих функцій (в тому числі і змінних). Можливість такої підстановки зумовлена тим, що області значень їх змінних збігаються. Наприклад, маючи елементарні функції
, ,
можна, користуючись принципом суперпозиції, одержати наступні нові функції:
, .
У розглянутому прикладі функцію одержано шляхом підстановки у функцію замість змінної функцію ; функцію – із функції шляхом підстановки у функцію замість змінної функцію .
Використання принципу суперпозиції дає можливість встановити зв’язки між елементарними функціями, тобто побудувати логічні вирази, які дозволяють записати одні елементарні функції через інші.
Розглянемо зв’язки між деякими елементарними функціями.
З табл. 8 виходить. що функція на всіх наборах набуває значень, протилежних функції . Справді, виконуючи принци суперпозиції, запишемо .
Наведемо без пояснень деякі широко застосовувані співвідношення, які зв’язують елементарні функції:
1) , 2) , 3) ,
4) , 5) , 6) ,
7) , 8) ,
9) , 10) .
З наведених прикладів бачимо, що одна і та сама функція може бути задана різними формулами, наприклад, . Це означає, що серед цих формул є найпростіша. Пошук логічних формул, які найпростішим чином задають задану функцію, представляє практичний інтерес. Одним із способів побудови найпростіших логічних формул базується на використанні співвідношень (аксіом та законів) булевої алгебри.
Часто при записі логічних формул використовують інфіксний запис, коли знаки операцій розташовані між змінними. Для запису виразів у інфіксній формі необхідно визначити порядок виконання операцій, що здійснюється за допомогою дужок або задання пріоритету операцій.
За відсутності дужок операції виконуються у такій послідовності: заперечення, кон’юнкція, диз’юнкція, імплікація та еквівалентність:
¯, ~ .
Наявність у виразі дужок змінює звичайний порядок дій, при цьому в першу чергу виконуються операції в дужках.
Приклад 1. У заданій функції
опустити максимально можливе число дужок з урахуванням пріоритету операцій.
Розв’язання. .
1.5. Аксіоми та закони булевої алгебри
Булева алгебра базується на деяких аксіомах, із яких виводяться основні закони для перетворення виразів, що містять булеві змінні. Обґрунтування цих аксіом підтверджується таблицями істинності для розглядуваних операцій. Кожна аксіома подана у двох формах: кон’юнктивній і диз’юнктивній, що випливає із принципу двоїстості логічних операцій, згідно якого операції кон’юнкції і диз’юнкції допускають взаємну заміну, якщо одночасно поміняти логічну 1 на 0, а 0 на 1; знак на , а знак на .