- •2. Елементарні булеві функції та їх властивості.
- •3. Реалізація булевих функцій формулами.
- •4. Рівносильність та тотожність формул. Принцип двоїстості.
- •5. Диз’юнктивна та кон’юнктивна нормальні форми. Розкладання булевої функції за змінними. Досконалі диз’юнктивна та кон’юнктивна нормальні форми.
- •6. Зображення булевих функцій досконалими диз’юнктивними нормальними формами.
- •Для будь-якої формули і для будь-якого числа справедливий розклад:
- •Алгоритм знаходження дкнф для даної функції:
- •Алгоритм знаходження дкнф для даної функції за допомогою рівносильних перетворень:
- •8. Повні системи булевих функцій.
- •Алгоритм побудови скороченої днф
- •2 Етап мінімізації – побудова тупикової днф
- •Алгоритм побудови тупикової днф
- •10. Реалізація булевих функції схемами з функціональних елементів.
- •11. Аналіз і функціонування схеми з функціональних елементів.
- •12. Структурній синтез схем з функціональних елементів.
10. Реалізація булевих функції схемами з функціональних елементів.
Булеві функції широко застосовуються при описі роботи дискретних пристроїв, при дослідженні деяких електричних ланцюгів, перемикальних схем тощо.
Нехай є деякий пристрій дискретної дії, внутрішня структура якого нас не цікавить, але про який відомо, що він має впорядкованих входів, які занумеровані числами від 1 до і вихідів, які занумеровані числами від 1 до . На кожний з входів можуть подаватися сигнали (не обов’язково електричні), і при кожному наборі сигналів на входах на виходах також з’являються сигнали. Будемо вважати, що сигнали можуть мати два різні рівні, кожному з яких припишемо символ 0 або 1, причому набір сигналів на входах однозначно визначає набір сигналів на виходах. Такий пристрій називається функціональним елементом.
Графічно такий пристрій зображається у вигляді -полюсника:
… …
Ми детально розглянемо випадок -полюсника:
… …
який є графічним зображенням функціонального елемента з входами і одним виходом.
Функціональні елементи та їх композиції називаються схемами з функціональних елементів. Ні в яких двох функціональних елементів схеми виходи не з’єднані і ні в якого функціонального елемента немає зворотного зв’язку, тобто ніякий вхід функціонального елемента не з’єднаний з його виходом навіть через ланцюжок інших функціональних елементів.
Схеми з функціональних елементів будуються за наступними правилами:
1. Об’єднання двох схем з функціональних елементів є схема, входи і виходи якої є входами і виходами схем, що об’єднуються.
2. Результат ототожнення будь-яких двох входів схеми є схема, вихід якої збігається з виходом початкової схеми, а входами є входи початкової схеми крім одного з ототожнених
...
3. Результат ототожнення виходу однієї схеми з входом іншої є схема, входами якої є входи першої схеми і входи другої, які не ототожнювались з виходом першої, виходом є вихід другої схеми:
4. Результат розгалуження виходу схеми є схема, входами якої є входи початкової схеми, і два виходи, які виникли з виходу початкової схеми:
Означення. Базисом з функціональних елементів називається такій набір функціональних елементів, за допомогою якого можна побудувати будь-яку схему.
Приклад базиса з функціональних елементів:
&
- кон’юнктор
Значення на виході 1 тоді і тільки тоді, коли всі входи 1.
V
- диз’юнктор
Значення на виході 0 тоді і тільки тоді, коли всі входи 0.
-
_
Перетворює 0 на вході в 1 на виході і навпаки.
11. Аналіз і функціонування схеми з функціональних елементів.
Поставимо у відповідність кожному функціональному елементу булеву функцію наступним чином: кожному входу відповідає булева змінна , і кожному двійковому набору значень цих змінних відповідає величина , яка набуває значення 0 або 1, в залежності від того, який сигнал з’являється на виході при поданні цього набору на входи функціонального елемента. Функціональний елемент цілком характеризується булевою функцією від аргументів, де - кількість входів функціонального елемента. Виявляється, що для будь-якої булевої функції можна побудувати функціональний елемент, який є її технічною реалізацією.
Під аналізом схеми будемо розуміти знаходження функцій, які реалізуються даною схемою.
Нехай задані алфавіти змінних і . Припишемо входам і виходам схеми з функціональних елементів різні букви з алфавітів і . Таку схему будемо позначати як .
Зіставимо схемі систему рівнянь алгебри логіки:
(1)
яка визначається системою булевих функцій, які входять в праві частини рівнянь системи. Кожна булева функція характеризує функціональний елемент схеми.
Повна система булевих функцій, яка використовується для побудови схем в деякій задачі відповідає базису з функціональних елементів.
Надалі будемо використовувати стандартні позначення для булевих функцій , що найбільш часто зустрічаються.
Приклад. Інвертор характеризується булевою функцією запереченням:
_
Кон’юнктор характеризується булевою функцією кон’юнкцією
Диз’юнктор характеризується булевою функцією диз’юнкцією:
Функціонування схеми з функціональних елементів можна описати наступним чином:
Схема - це з’єднання функціональних елементів . Кожний функціональний елемент схеми є елементарним перетворювачем, який перетворює вхідний набір з нулів і одиниць в вихідне значення . В такому випадку, якщо на входи схеми подати набір , то, просуваючись від входів до виходів, він буде переходити в набір , який характеризує стани виходів. Виявляється, що
(1)
тобто перетворення, що описується рівняннями (1) відповідає нашому інтуїтивному уявленню про функціонування схеми з функціональних елементів.
І
_
Приклад. Розглянемо схему:
&
V
Для цієї схеми маємо систему з одного рівняння:
Функціонування даної схеми описує наступна таблиця комбінацій функціональних елементів:
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |