Мінімізація логічних функцій

Мінімальною диз’юнктивною нормальною формою функції f називається диз’юнктивна нормальна форма, яка містить мінімально можливе число входжень символів змінних серед усіх диз’юнктивних нормальних форм, які реалізують функцію f. Задачі побудови мінімальних диз’юнктивних нормальних форм називаються задачами мінімізації .

Нехай дано дві логічні функції g(x₁,…, x_n) і f(x₁,…, x_n). Кажуть, що логічна функція g входить в логічну функцію f і пишуть g Ì f, якщо виконується наступна умова: на всіх наборах, на яких f дорівнює нулю, g також дорівнює нулю.

Будь-яка функція g(x₁,…, x_n), яка входить в дану функцію f(x₁,…, x_n), називається її імплікантом. Інакше, функція g(x₁,…, x_n) називається імплікантом функції f(x₁,…, x_n), якщо для будь-якого набору (a₁, …, a_n) значень аргументів виконується нерівність f(x₁,…, x_n) ³ g(x₁,…, x_n). Цю умову можна еквівалентно подати у вигляді f(x₁,…, x_n) g(x₁,…, x_n) g(x₁,…, x_n).

Імплікант називається простим, якщо він являє собою кон’юнкцію змінних (можливо із запереченнями), і будь-яка кон’юнкція, одержана з нього в результаті видалення яких-небудь змінних, імплікантом не являється. Щоб вияснити, чи є імплікант, який має вигляд кон’юнкції, простим, досить дослідити наявність імплікантів серед кон’юнкцій, одержаних видаленням з нього рівно однієї змінної.

Довести, що функції і є імплікантами функції , можна також, переконавшись в справедливості співвідношень: .

В основі розв’язання задачі мінімізації логічних функцій лежить схема, яка містить два етапи: 1) відшукання всіх простих імплікантів функції f, тобто побудова її скороченої диз’юнктивної нормальної форми; 2) побудова тупикових (без зайвих імплікантів) диз’юнктивних нормальних форм з числа мінімальних.

Існують різні методи мінімізації логічних функцій.

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

(операція склеювання);

(операція поглинання);

(дистрибутивний закон).

При спрощенні завжди слід мати на увазі тотожність x Ú x = x, з якої випливає, що кожен доданок можна групувати з іншими неодноразово.

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

Метод Квайна. В методі Квайна прості імпліканти знаходяться по досконалій диз’юнктивній нормальній формі в результаті застосування до неї операції неповного склеювання і операції елементарного поглинання.

Метод Блейка дозволяє шукати прості імпліканти, використовуючи представлення функції в довільній диз’юнктивній нормальній формі, а також операцію узагальненого склеювання, яка описується виразом

Питання для самоперевірки

1.Що таке скорочена диз’юнктивна (кон’юнктивна) нормальна

форма?

2.Назвіть і охарактеризуйте методи, за якими утворюють мінімальні форми.

Література: [1], c. 58-74, 39-58; [2], c. 35-38.

Вправи

65. Методом послідовного застосування законів і тотожностей алгебри логіки знайти скорочену диз’юнктивну нормальну форму логічної функції: .

66. Методом Квайна знайти скорочену диз’юнктивну нормальну форму логічних функцій:

3) ;

4) .

67. Методом Блейка знайти скорочену диз’юнктивну нормальну форму логічних функцій:

;

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Бульові функції	\|	Контактні та логічні схеми

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.