Минимизация логических функций. Вычислительная техника

Минимизация

упрощение формы записи
схема реализуется с наименьшим числом элементов

Минимальная нормальная форма

Нормальная форма логической функции, содержащая наименьшее число элементов
Минимальная ДНФ

Методы минимизации

Непосредственных преобразований

Квайна и
Мак-Класки

Карно-Вейча

МЕТОД НЕПОСРЕДСТВЕННЫХ ПРЕОБРАЗОВАНИЙ

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

Метод непосредственных преобразований
Применение законов алгебры логики
Результат − тупиковая форма

Тупиковая форма

Логическое выражение, к слагаемым которого больше не могут быть применены

Функции a и b называются равносильными, если при одинаковых входных данных

ЗАКОНЫ ЛОГИКИ

1. Идемпотентность

a & a ≡ a
a ∨ a ≡ a

2. Коммутативность

a & b ≡ b & a
a ∨ b ≡

3. Ассоциативность

a & (b & с) ≡ (a & b) &

4. Дистрибутивность

a & (b∨с) ≡ (a & b) ∨ (a &

5. Закон двойного отрицания

¬(¬a) ≡ a

6. Законы поглощения

a & (a ∨ b) ≡ a
a ∨ (a

7. Законы де Моргана

¬(a ∨ b) ≡ ¬a & ¬ b
¬(a

8. Закон исключённого третьего

¬a ∨ a ≡ 1

9. Закон противоречия

¬a & a ≡ 0

10. Свойства тавтологии и противоречия

1 & a ≡ a 1 ∨

11. Законы склеивания

(a & b) ∨ (a & ¬b) ≡ a
(a

12. Законы поглощения

a & (a ∨ b) ≡ a
a ∨ (a

Пример

Минимизировать СДНФ
(¬А ⋅ ¬В ⋅ С) ∨
∨(А ⋅ ¬В ⋅ С)

Пример

(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨
∨(А

Пример

(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨
∨(А

Пример

(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨
∨(А

Пример

(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨
∨(А

Пример

(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨
∨(А

Проблема

Определить, какие элементарные конъюнкции / дизъюнкции надо склеивать

КАРТЫ ВЕЙЧА-КАРНО

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

Эдвард Вестбрук Вейч

Американский физик
1952
«Метод диаграмм для минимизации логических функций»

1924 —

Морис Карно

род. 1924

Американский физик
1953
Усовершенствовал метод Вейча

Карта Карно

Графическое представление таблицы истинности логических функций
Таблица, содержащая по 2n

Код Грея

система счисления, в которой два соседних значения различаются только

Пример

Пример

Пример

Пример

Пример

Пример

Пример

Правила

ДНФ КНФ
1. Объединяем смежные клетки с единицами (нулями) в максимально

Правила

5. Крайние строки и столбцы являются соседними между собой

Правила

6.Несмежные области, расположенные симметрично оси(ей), могут объединяться в одну

Правила

7. Для каждой области записываем конъюнкцию (дизъюнкцию) переменных, не изменяющих

Пример

F = ¬ X2 ∨ X1

Пример ‒ МДНФ

F = X1 ⋅¬ X2 ∨ ¬X1⋅ X2

Пример ‒ МКНФ

F = (X1 ∨ X2) ⋅ (¬X1∨ ¬ X2)

Пример

Формула

(¬А ⋅ ¬В ⋅ С) ∨
∨(А ⋅ ¬В ⋅ С) ∨
∨(А

(А ∨ В ∨ С) ⋅
⋅ (А ∨ ¬В ∨ С)

Пример

Пример
F = ¬В ⋅ С ∨ A ⋅ C
МДНФ

Пример
F = С ⋅ (A ∨ ¬В)
МКНФ

Недостатки

Применим для функций до 7 переменных
Выбор областей ‒ визуально
Нет алгоритма, обеспечивающего

МЕТОД КВАЙНА И МАК-КЛАСКИ

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

Виллард ван Орман Куайн

Американский философ, логик и математик
1993
премия Рольфа Шока в

Эдвард Дж. Мак-Класки

Почётный профессор Стэнфордского университета.
Пионер в области электротехники
Первый алгоритм проектирования