Page 45 - 4496

Згідно з поданою таблицею складемо ДДНФ:
1
F = m 0f 0 + m 1f 1 + m 2f 2 + m 3f 3 = m 0 + m 3 = A B + AB
Аналогічно отримуємо ДКНФ
0
F =(f 0+M 0)(f 1+M 1)(f 2+M 2)(f 3+M 3)=(f 1+M 1)(f 2+M 2)=M 1M 2=
(A+ B )( A +B)
Якщо розкрити дужки, то отримуємо
0
F =A A +AB+ A B + B B= A B +AB(A A =0 і B B =0).
1
0
Останній результат доказує тотожність функцій F і F .
2.24 Індекс (коефіцієнт) простоти
Допустимо, що заданий опис роботи системи (у вигляді
таблиці істинності). Необхідно за заданим описом знайти
структуру логічної системи. Поставлена задача є задачею
синтезу логічного пристрою.
Одним із основних питань цієї задачі є така: як для
довільної функції алгебри логіки f (x 1, x 2, ..., x n) побудувати її
мінімальну ДНФ або КНФ. (Задача мінімізації булевих
функцій).
Для того щоб вирішити цю задачу необхідно мати
критерій, за яким можна оцінити складність (простоту)
отриманого виразу. З цією метою вводиться індекс
(коефіцієнт) простоти ДНФ або КНФ.
Найчастіше зустрічаються такі типи коефіцієнтів
простоти:
L`(A) – число символів змінних, які використовуються
для запису ДНФ;
L``(A) – число елементарних кон`юнкцій, що входять до
логічної функції;
L```(A) – число символів інверсій, які зустрічаються в
запису ДНФ.
Приклад.
Розглянемо функцію

A 1= x 1 x 2 x 3+x 1 x 2 x 3+x 1 x 2x 3+x 1x 2 x 3+x 1x 2x 3
еквівалентну формулі
A 2=A 1= x 2 x 3+x 1(x 2+x 3)= x 2 x 3+x 1x 2+x 1x 3
Запишемо
A 1= x 2 x 3(x 1+ x 1)+x 1 x 2x 3+x 1x 2(x 3+ x 3)=
x 2 x 3+x 1 x 2x 3+x 1x 2;
42