1.1. Задача минимизации булевых функций

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

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