Некоторые понятия и определения

Под минимизацией понимается сокращение числа аргументов до минимума в заданном логическом выражении, не изменяя его значения. При синтезе схем дискретных устройств прежде всего необходимо получить логическое выражение, согласно которому должна работать электрическая схема заданного устройства. Если логическое выражение будет сложным, то электрическая схема, соответствующая этому выражению, будет содержать много элементов автоматики, а следовательно она будет дорогой и менее надежной.

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

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

Таким образом процесс минимизации ФАЛ заключается в том, чтобы из СДНФ получить тупиковые ДНФ, а из тупиковых выбрать минимальную ДНФ. Разработаны и используются несколько методов минимизации ФАЛ как аналитических, так и табличных.

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