ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ

— функции, осуществляющие однозначное отображение множества наборов в которых аргументы принимают значение из множеств в множество

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

Т. о., каждая П. ф. может быть задана конечной таблицей, содержащей N строк. В левой части этой таблицы перечисляются все возможные наборы аргументов заданной П. а в правой — ее значения на этих наборах. С ростом к-ва аргументов или при больших мощностях множеств значение N быстро увеличивается, и табличное задание П. ф. становится неэффективным. Кроме табличного задания, П. ф. всегда можно представить в. аналитической форме. Наиболее распространенными являются аналитические представления П. использующие характеристические функции. Характеристическая функция - должна обладать следующим свойством: на наборе с номером она принимает некоторое фиксированное значение а, а на всех остальных наборах принимает отличное от этого значения, но одинаковое для всех наборов другое значение р. Пусть, напр., для набора с номером и равна для наборов с номерами.

отличными от . Определим две спец. операции и О со следующими свойствами; где есть значение П. ф. на наборе с номером Тогда П. ф. у может быть записана в стандартной форме:

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

Одной из центральных проблем в теории П. ф. является полноты проблема, сущность которой сводится к следующему: требуется определить, можно ли построить любую П. ф., применяя к заданной системе П. ф. операции суперпозиции (подстановки). Необходимые и достаточные условия проверки полноты системы функций получены лишь для ф. а. л. и П. ф. с совпадающими множествами X и Y при . Второй крупной проблемой в теории П. ф. является проблема минимизации аналитического описания П. ф. Даже для случая ф. а. л. эта проблема представляет значительные трудности, связанные с большим перебором, неизбежным при поиске миним. аналитических выражений. Еще большие трудности возникают при минимизации П. ф. с .

Д. Л. Поспелов.