1-6. ОСНОВНЫЕ КЛАССЫ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ

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

В качестве первого класса таких функций мы рассмотрим класс функций, сохраняющих константу нуль, т. е. таких функций, для которых имеет место равенство

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

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

Этот класс, состоящий также из 2 функций, будем обозначать символом

Определение 1-4. Функция называется двойственной к функции если имеет место равенство

Определение 1-5. Функция называется самодвойственной, если она совпадает с двойственной себе функцией, т. е. имеет место равенство

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

Определение 1-6. Функция называется линейной, если она представима в следующем виде:

где коэффициент может принимать значение 0 или 1.

Класс линейных функций будем обозначать буквой Число членов этого класса равно

Будем говорить, что набор значений аргументов не меньше набора значений аргументов если между всеми компонентами наборов и установлено соотношение Отметим, что при таком определении набор не меньше набора а наборы несравнимы.

Определение 1-7. Функция называется монотонной, если для любых двух наборов таких, что имеет место равенство

Класс монотонных функций мы будем обозначать буквой М. Число функций класса М оценивается асимптотически

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

Нижняя оценка получена Э. Н. Гильбертом, а верхняя — В. К. Коробковым.

Определение 1-8. Функция называется симметричной, если она не изменяется при произвольной перенумерации аргументов:

где — любая перестановка аргументов

Класс таких функций будем обозначать буквой .