Формулы алгебры логики, полученные с помощью таблиц истинности или другими способами, как правило, подлежат минимизации – упрощению.
Например, формулу
можно упростить, используя закон де Моргана для освобождения от отрицаний:
Минимизацию можно осуществить двумя группами методов.
Он предполагает использование законов алгебры логики, выраженных формулами:
закон исключенного третьего
закон противоречия
закон двойного отрицания
две формы закона де Моргана
A + A&B = A закон поглощения
A&B + A& = A закон склеивания
A+A + A
A&A = A две формы закона идемпотентности
а также формул преобразования логических операций:
импликации
эквивалентности
Пример:
Как видно, минимизация алгебраическими методами не всегда проста.
Они предполагают использование в качестве исходной формулы ту, которая получена с помощью таблиц истинности – совершенную дизъюнктивную нормальную форму логической функции.
Возьмем любую логическую функцию двух аргументов:
X
Y
F
Составляем сумму произведений аргументов тех строк, значение функции в которых истинно:
F =
Составляем таблицу, называемую диаграммой Вейча для функции двух аргументов:
X
Y
Записываем единицы в тех ячейках таблицы, которые соответствуют произведениям:
X
Y
Единицы, стоящие в ячейках, соприкасающихся сторонами, можно объединить (склеить). При этом вместо двух слагаемых остается одно, имеющее один аргумент, общий для объединяемых ячеек. В данном случае это . Результат минимизации:
F = =
При расстановке слагаемых так:
X
Y
получаем следующую минимальную форму:
F = X
При такой расстановке слагаемых:
X
Y
Имеются два объединения, которые соответствуют следующей минимальной форме:
Если таблица полностью заполнена единицами:
1
X
Y
То после объединения четырех соприкасающихся ячеек получаем следующую минимальную форму:
F = 1
Таким образом, объединять можно по две или по четыре ячейки, оставляя общий для них аргумент.
Диаграмма Вейча для функции трех аргументов имеет вид:
Z
X
Y
Здесь тоже можно объединять по две или четыре ячейки, соприкасающиеся сторонами. При этом остаются аргументы, общие для объединенных ячеек:
Z
1
X
Y
В этом случае имеются три объединения, образующие следующую минимальную форму:
F = X&Y + Y&Z + &Z
При объединении четырех соприкасающихся ячеек остается один общий для них аргумент:
Z
X
Y
В этом случае:
F = Y
Можно объединять ячейки, находящиеся на противоположных концах диаграммы: