Упрощение логических функций, заданных различным образом

1. Функция задана в произвольной форме.

Пример 1.Упростить логическую функцию, заданную выражением:

Решение:

А. Приведение функции к ДНФ путем использования законов и правил, т.е. .

Б. Вычерчивание конъюнкций, равных нулю.

Конъюнкция , конъюнкции , равны нулю, поэтому получаем упрощенную функцию .

Пример 2.Упростить логическую функцию, заданную выражением:

Решение:

А. Применение закона отрицания с целью последующего перехода к ДНФ, т.е. .

Б. Анализ промежуточного результата. Устанавливаем. Что первая скобка равна единице, т.к. и , где . Окончательно получаем: .

Пример 3.Упростить логическую функцию, заданную выражением:

.

Решение:

А. Упрощение функции путем использования закона отрицания и перенесения скобок:

Б. Применение правила расширения:

- из группы конъюнкций исключаем ;

- из группы конъюнкций исключаем ;

- из группы конъюнкций исключаем .

Окончательно получаем: .

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

Применяем правило расширения в следующей последовательности:

- из группы конъюнкций исключаем ;

- из группы конъюнкций исключаем .

В результате получаем .

Эта функция по рассмотренным правилам и законам упрощению не поддается.

Заметим, что если имеется несколько форм одной функции, которые не поддаются дальнейшим упрощениям, то они называются тупиковыми. Одна из них является минимальной.

2. Функция задана таблицей истинности

Пример 4.Упростить функцию F ( , , ) равную единице на наборах 3, 5, 6, 7 (011, 101, 110, 111).

Решение:

А. Построение таблицы истинности.

В первых трех столбцах записываются возможные наборы. В столбце F на наборах 011, 101, 110 и 111 проставляются единицы; на остальных наборах проставляются нули.

Б. Запись функции в СДНФ (см. правило записи).

Наборам 011, 101, 110, 111 соответствуют конъюнкциям , , , , поэтому функция будет записана в следующем виде: .

В. Упрощение функции.

Функции, записанные в СДНФ, первоначально упрощаются по правилу склеивания. Затем применяются другие правила и тождественные соотношения.

В данной функции первые три конъюнкции являются соседними с четвертой. Функция не изменится, если к ней подписать еще две конъюнкции , т.е. .

После склеивания пар соседних конъюнкций окончательно получим: .

Можно было не подписывать конъюнкцию , а просто склеить поочередно три первые конъюнкции с четвертой конъюнкцией.