На головну

Побудова аналітичного вираження булевої функції по таблиці її значень

  1. At a Hotel - корисні слова і вирази
  2. C. Інтерполяція функції f (x) поза відрізка [a, b]. 1 сторінка
  3. C. Інтерполяція функції f (x) поза відрізка [a, b]. 2 сторінка
  4. C. Інтерполяція функції f (x) поза відрізка [a, b]. 3 сторінка
  5. C. Інтерполяція функції f (x) поза відрізка [a, b]. 4 сторінка
  6. C. Інтерполяція функції f (x) поза відрізка [a, b]. 5 сторінка
  7. Соціальні функції науки

Раніше ми розглянули можливості опису функції, заданої аналітично, за допомогою таблиці відповідностей. Широко поширеною є і зворотна задача - побудова аналітичного вираження деякої логічної функції, спочатку заданої таблично.

Нехай, наприклад, табличний (табл.7.1) задана функція y(х1,х2,х3).

Таблиця 7.1
y х1 х2 х3

Задану в табл.7.1 функцію можна описати таким чином: значення функції у дорівнює 1, коли (х1?0 і х2?0 і х3?0) або (х1?0 і х2?0 і х3?1) або (х1?0 і х2?1 і х3?1) або (х1?1 і х2?0 і х3?1) або (х1?1 і х2?1 і х3?0) або (х1?1 і х2?1 і х3?0). Союзу "або" відповідає операція диз'юнкції, а союзу "і" - операція кон'юнкції, вираз "хi?1 "еквівалентно"хi", А"хi?0 "еквівалентно» не хi". Таким чином, таблично задану функцію можна описати диз'юнкція кон'юнкція, тобто диз'юнктивній нормальною формою.

Розглянемо докладно алгоритм опису в вигляді диз'юнктивній нормальної форми функції, заданої таблично.

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

  Таблиця 7.2  
   функція  аргументи
y х1 х2 х3  відповідний мінітерм  
 
 
 
 
 
 
 
 
               

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

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

Якщо значення аргументів відповідають одному, хто входить в описі функції мінітерм, то значення цього мінітерм стає дорівнює одиниці, а значить і вся функція стає дорівнює одиниці. Якщо ж значення аргументів такі, що жоден з вхідних в опис функції мінітерм НЕ дорівнює одиниці, то вся функція дорівнює нулю. Побудова аналітичного опису такої функції і було завданням.

Отже, аналітичний опис функції заданої в табл.7.2 виглядає наступним чином:

.

Такий запис є досконалою диз'юнктивній нормальною формою.

До аналітичного опису функції, заданої таблично, можна підійти і з іншого боку - описувати аргументи відповідні нульових значень функції. Аналітичний опис з наведеного раніше прикладу буде наступним:

.

Так як  , то

.

Відповідно до законів де Моргана перетворимо:

.

Отримана запис є кон'юнкція диз'юнкцій, кожен Максітерм містить всі змінні, тобто запис являє собою досконалу кон'юнктівную нормальну форму.

Таким чином, будь-який таблично заданої логічної функції можна зіставити аналітичний вираз як у вигляді диз'юнктивній, так і у вигляді кон'юнктівной нормальної форми.

Запитання і завдання

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

7.2. Розгляньте рішення попередньої задачі для випадку трьох перемикачів.

 



Диз'юнктивна і Кон'юнктивна нормальні форми булевої функції (диз'юнкція кон'юнкція і кон'юнкція диз'юнкцій) | Мінімізація логічних функцій, оптимізація технічної реалізації функцій алгебри логіки

Поняття висловлювання. поняття операції | приклади | Інверсія (заперечення) | Кон'юнкція (логічне множення) | Диз'юнкція (логічне додавання) | Імплікація (логічне проходження) | Еквіваленція (подвійна імплікація) | Приклади практичного застосування булевої алгебри. переключательние схеми | тотожні перетворення | Автоматизація процедури зчитування і мінімізації логічних функцій за допомогою методу карт Карно |

© um.co.ua - учбові матеріали та реферати