Упрощение логических функций

Совершенные нормальные формы однозначно представляют ФАЛ. Если условие однозначности не является необходимым, то во многих случаях СНФ имеют некоторую избыточность, т. е. включают фиктивные переменные, от которых необходимо избавиться до аппаратной реализации ФАЛ. Минимальная форма представления ФАЛ содержит минимальное количество термов и переменных в термах и более не допускает никаких упрощений (минимизации). Так при минимизации СДНФ сокращается до минимума количество конъюнкций и число переменных в каждой из них.

Минимизация (упрощение) булевых функций производится с помощью теорем алгебры логики и может быть реализована аналитическими, графическими и арифметическими методами с помощью теоремы Квайна Мак-Класки.

Наиболее эффективными приемами аналитических методов минимизации являются вынесение за скобки общих членов, а также применение двойного отрицания, теоремы де-Моргана, законов поглощения и склеивания. При этом, наряду с полным склеиванием, т. е. использованием зависимости или (склеивание по ) часто применяют неполное склеивание — оба члена склеивания или один из них остаются и склеиваются с другими членами СДНФ. Неполное склеивание может рассматриваться как сочетание закона склеивания и идемпотентности. При преобразовании следует помнить, что логические операции имеют старшинство — в порядке убывания .

! Пример: Упростить выражение .

Чтобы проверить правильность достаточно вместо переменных в полученную функцию подставить их значения из таблицы.

Дата добавления: 2014-01-07