I §2. Предполные классы

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

1) Класс - класс функций, сохраняющих 0, т.е. функций, для которых . Замкнутость класса очевидна: если в

функцию вместо некоторых переменных

подставить функции, принадлежащие , то на нулевом наборе

аргументов все они имеют значение 0, и для внешней функции набор ее переменных будет также нулевым, откуда Z = 0.

2) Класс - класс функций, сохраняющих 1, те функций, для

которых Замкнутость устанавливается аналогично

предыдущему.

Примерами функций, принадлежащих классам , служат

функции , отрицание не принадлежит ни

функция принадлежит , но не принадлежит импликация

напротив, не принадлежит , но принадлежит

3) Для определения следующего класса введем понятие двойственности. Двойственная функция для функции

- функция . Если на

наборе функция принимает значение , то

двойственная ей функция на противоположном

ч

наборе принимает противоположное значение

Упражнение. Проверьте, например, что двойственной функцией к

конъюнкции является дизъюнкция , константа 1

двойственна константе 0.

Для булевых функций справедлив принцип двойственности -

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

Класс S самодвойственных функций - то есть функций таких, что . Из определения следует, что

двоичный набор значений самодвойственной функции антисимметричен относительно своей середины. Таким способом удобно проверять по таблице самодвойственность функции. Например, можно убедиться, что

одноместные функции - самодвойственные, а среди функций

двух переменных самодвойственными являются только функции с одной

несущественной переменной. Функция большинства (см

§1 Гл.З) является самодвойственной

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

внешней функции также противоположны. Пусть

i - суперпозиция этих самодвойственных функций. Тогда [поскольку

^!' 4) В начале §1 гл.4 мы убедились в возможности представления любой функции многочленом Жегалкина.

Подмножеством множества многочленов является класс L 'линейных функций - функции вида . Здесь

- переменные, - булева константа (0 или 1).

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

Пример: Пусть

Тогда суперпозиция [в

функцию подставляем функцию вместо X и функцию вместо Y ] представляет собой линейную функцию:

5) Введем отношение частичного порядка для булевых векторов:

для

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

Равенство добавляет варианты . Поэтому

аргументов все они имеют значение 0, и для внешней функции набор ее переменных будет также нулевым, откуда Z = 0.

2) Класс - класс функций, сохраняющих 1, те функций, для

которых Замкнутость устанавливается аналогично

предыдущему.

Примерами функций, принадлежащих классам , служат

функции , отрицание не принадлежит ни

функция принадлежит , но не принадлежит импликация

напротив, не принадлежит , но принадлежит

3) Для определения следующего класса введем понятие двойственности. Двойственная функция для функции

- функция . Если на

наборе функция принимает значение , то

двойственная ей функция на противоположном

ч

наборе принимает противоположное значение

Упражнение. Проверьте, например, что двойственной функцией к

конъюнкции является дизъюнкция , константа 1

двойственна константе 0.

Для булевых функций справедлив принцип двойственности -

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

Класс S самодвойственных функций - то есть функций таких, что . Из определения следует, что

двоичный набор значений самодвойственной функции антисимметричен относительно своей середины. Таким способом удобно проверять по таблице самодвойственность функции. Например, можно убедиться, что

одноместные функции - самодвойственные, а среди функций

двух переменных самодвойственными являются только функции с одной

несущественной переменной. Функция большинства (см