2-7. МИНИМИЗАЦИЯ В ДРУГИХ БАЗИСАХ

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

Пусть имеется полная система Тогда для представления некоторой функции в этой системе нужно решить две задачи: в какой форме искать запись функции по функциям и как найти минимальную запись по этим функциям. Для решения первой задачи можно предложить некоторый регулярный метод. Вторая задача в общем виде пока еще не нашла своего решения.

Рассмотрим сначала проблему разложения произвольной функции по полной системе функций

Воспользуемся представлениями (1-25) и (1-28), полученными нами в § 1-7. Если в этих соотношениях заменить характеристические функции и дизъюнкцию или характеристические функции и конъюнкцию через функции то мы получим один из возможных методов решения поставленной задачи о нахождении представления любой функции алгебры логики в системе функций Вместо выражений (1-25) и (1-28) можно воспользоваться выражениями

(1-26) и (1-29). В этом случае через , нужно выразить соответствующие характеристические функции, а также функции сложения по модулю два или эквивалентности.

Пример 2-12. Найти формулу представления для произвольной функции в базисе, состоящем из импликации и отрицания.

Эта задача была решена в § 1-7 с помощью теорем 1-6 и 1-7, в которых было показано, что произвольная функция может быть представлена в форме

или

Заменяя теперь операции конъюнкции и дизъюнкции на основании (1-19)

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

и

Здесь — числа номеров в множествах .

Буквами , обозначены импликативные функции, стоящие под знаками дизъюнкции и конъюнкции.

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

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

Мы рассмотрели весьма подробно проблему минимизации лишь для случая, когда стандартными логическими элементами являются элементы, реализующие функции отрицания, конъюнкции и дизъюнкции. Для остальных систем стандартных элементов эта проблема по существу рассматривалась лишь для базиса, состоящего из суммы по модулю два, конъюнкции и константы единица и для базиса, состоящего из функций Вебба или Шеффера. К рассмотрению этих базисов мы и переходим.