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

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

К настоящему времени разработано достаточно большое число методов и приемов минимизации логических функций. Наиболее известными и распространенными среди них являются:

1) расчетный метод – метод непосредственных логических преобразований;

2) табличный метод – метод карт Карно или Вейча – Карно;

3) расчетно-табличный метод Квайна.

Исходной формой для любого из этих методов является одна из совершенных нормальных форм СНДФ или СНКФ. В общем случае любой из упомянутых методов состоит из трех этапов.

1. Переход от СНД(К)Ф к сокращенной сНД(К)Ф путем выполнения всех возможных склеиваний друг с другом сначала конституент, а затем всех членов сумм (произведений) более низкого ранга до тех пор, пока склеивание возможно.

Таким образом, под сокращенной формой логической функции будем понимать нормальную дизъюнктивную (конъюнктивную) форму функции, членами которой являются не склеивающиеся друг с другом элементарные конъюнкции (дизъюнкции).

Члены сНД(К)Ф носят название простых (или первичных) импликант. Не исключено, что сНД(К)Ф CНД(К)Ф.

2. Переход от сНД(К)Ф к тупиковой нормальной дизъюнктивной (конъюнктивной) форме (ТНД(К)Ф) путем устранения избыточных импликант. Под тупиковой будем понимать такую НД(К)Ф логической функции, в которой нет ни одной лишней (избыточной) импликанты.

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

Термин тупиковая форма означает, что дальнейшая минимизация путем использования аксиом и законов алгебры логики в рамках нормальных форм уже невозможна.

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