![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Класи булевих функцій
Вводяться в розгляд п’ять класів булевих функцій: 1) клас функцій, що зберігають константу нуль ( 2) клас функцій, що зберігають константу одиниця ( 3) клас самодвоїстих функцій 4) клас монотонних функцій ( 5) клас лінійних функцій Клас функцій, що зберігають нуль (К0), містить всі функції, які приймають нульове значення при всіх нульових значеннях змінних. Визначення 13.1. Якщо булева функція на нульовому наборі змінної дорівнює нулю, то функція зберігає константу нуль:
Клас функцій, що зберігають одиницю (К1), включає всі функції, які на наборі з одиниць приймають значення одиниця. Визначення 13.2. Якщо булева функція на одиничному наборі (наборі з одиниць) дорівнює одиниці, то говорять, що функція зберігає одиницю:
Перш ніж розглядати клас лінійних функцій (КЛ), необхідно ввести наступні допоміжні поняття. Визначення 13.3. Формули, що містять знаки Визначення 13.4. Вираз вигляду Теорема Жегалкіна. Будь-яка булева функція може бути зображена поліномом вигляду
де Визначення 13.5. Булева функція називається лінійною, якщо вона може бути зображена поліномом першого ступеня, тобто виразом вигляду
Кількість лінійних функцій дорівнює Приклад 13.1. Одержати всі лінійні функції від двох змінних. Розв’язок. Кількість лінійних функцій від двох змінних визначається як
Коефіцієнти
Таблиця 13.1 – Клас лінійних функцій від двох змінних
Якщо довільну булеву функцію від двох змінних шляхом еквівалентних перетворень можна зобразити в одній із вказаних восьми форм, то така функція є лінійною, тобто належить класу До класу монотонних функцій (КМ) відносяться такі, для яких виконана умова монотонності: на кожній парі порівнянних двійкових наборів значення функції мають бути порівнянні в тому ж порядку. Множина {0, 1} упорядковується за принципом порівнянності: 0< 1 (0 порівняний з одиницею). Нехай Визначення 13.6. Набір Визначення 13.7. Функція називається монотонною, якщо для будь-яких наборів
тобто на кожній парі порівнянних двійкових наборів значення функції мають бути порівнянні. Приклад 13.2. Обґрунтувати, чи належить функція Розв’язок.Слід скласти таблицю істинності булевої функції
Таблиця 13.2 – Значення функції
Для дослідження функції на монотонність зображується гіперкуб
Рисунок 13.1 – Гіперкуб для функції від трьох змінних
У вершини гіперкуба додаються значення функції на відповідних двійкових наборах (рис.13.2).
Рисунок 13.2 – Розподіл значень функції
Аналіз розподілу значень функції в гіперкубі показує, що функція не є монотонною, оскільки існують нулі, що покривають одиниці, а саме: Таким чином, функція не належить до класу монотонних: Для класу самодвоїстих функцій (КС) слід розглянути поняття двоїстої функції. Визначення 13.8. Булева функція
Приклад 13.3. Кон’юнкція й диз’юнкція двоїсті один одному, інверсія двоїста сама собі: 1) 2) Інвертуємо таблицю істинності кон’юнкції, замінивши на протилежні значення аргументів і самої функції (табл. 13.3). Таблиця 13.3 – Подвійність кон’юнкції та диз’юнкції за таблицями істинності
Визначення 3.14. Функція, що співпадає зі своєю двоїстою, називається самодвоїстою:
Самодвоїста функція на протилежних двійкових наборах Приклад 13.4. Показати, що функція Розв’язок. Слід перетворити таблицю істинності функції (табл. 13.4).
Таблиця 13.4 – Самодвоїстість функції
Видно, що в результаті перетворень функція не змінилася, отже, вона самодвоїста. Принцип двоїстості. Якщо у формулі алгебри логіки Приклад 13.5. Можна показати, що наступні рівності двоїсті один одному:
КНФ і ДНФ двоїсті один одному. Властивості булевих функцій від двох змінних щодо приналежності їх до класів наведені в таблиці 13.5. Таблиця 13.5 – Приналежність булевих функцій від двох змінних класам
13.2 Повнота функцій алгебри логіки Визначення 13.15. Система функцій алгебри логіки Приклад 13.6. Функціонально повними є системи:
Теорема Поста-Яблонського (критерій функціональної повноти). Для того щоб ФАЛ 1) не зберігає нуль – 2) не зберігає одиницю – 3) нелінійну – 4) немонотонну – 5) несамодвоїсту – Визначення 13.16. Повна система ФАЛ, за допомогою якої кожна ФАЛ може бути зображена суперпозицією вихідних функцій, називається базисом. До базису відносяться системи функцій: базис 1: І, АБО, НІ базис 2 (кон’юнктивний базис Буля): І, НІ базис 3 (диз’юнктивний базис Буля): АБО, НІ базис 4 (базис Шефера): функція Шефера базис 5 (базис Веба): функція Веба базис 6 (базис Жегалкіна): Базис 1 надлишковий, базиси 4 і 5 мінімальні (видалення хоча б однієї функції перетворює систему ФАЛ у неповну). Таким чином, всі названі вище класи функцій мають таку властивість: кожна ФАЛ, отримана за допомогою операції суперпозиції й підстановки з функцій одного класу, обов'язково належатиме цьому ж класу. Поліноміальна форма орієнтована на технології тестування цифрових систем з використанням активізації або визначення булевих похідних. Класи булевих функцій є теоретичною основою трансформування опису цифрової системи в різні аналітичні форми. Функціональна повнота визначає інваріантність зображення цифрового пристрою за допомогою різних наборів бінарних і унарної операцій. 13.3 Контрольні запитання
1. Які існують класи булевих функцій? 2. Як визначається клас функцій, що зберігають нуль? 3. Які функції зберігають константу одиниця? 4. Що таке двоїста функція? 5. Як визначається властивість самодвоїстості? 6. Які двійкові набори є протилежними? 7. Що таке поліном? 8. Що таке поліном Жегалкіна? 9. Як формулюється теорема Жегалкіна? 10. Як визначається поліном першого ступеня? 11. Що таке лінійна функція? 12. Як формулюється властивість монотонності булевої функції? 13. Як визначається клас монотонних функцій? 14. Як виконується перевірка самодвоїстості функції за допомогою таблиці істинності? 15. Як одержати функцію, двоїсту стосовно даної? 16. Скільки існує лінійних функцій від 17. Як визначається функціональна повнота? 18. Яка система функцій називається базисною? 19. Яка теорема визначає критерій функціональної повноти? 20. Як формулюється критерій функціональної повноти? 21. Як виконується перевірка монотонності функції за допомогою гіперкуба? 14 БУЛЕВІ ПОХІДНІ
Математичний апарат булевою диференціального числення використовується в структурно-аналітичних методах синтезу тестів, що перевіряють, для комбінаційних пристроїв. Булеві похідні дозволяють аналітично виразити умови активізації шляхів у схемі.
|