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 самодвойственных функций- то есть функций таких, что 
. Из определения следует, что
двоичный набор значений самодвойственной функции антисимметричен относительно своей середины. Таким способом удобно проверять по таблице самодвойственность функции. Например, можно убедиться, что
одноместные функции 
- самодвойственные, а среди функций
двух переменных самодвойственными являются только функции с одной
несущественной переменной. Функция большинства (см
§1 гл.З) является самодвойственной
Из определения нетрудно вывести, что класс самодвойственных функций - замкнутый, поскольку в любой суперпозиции на противоположных наборах внутренние подформулы принимают противоположные значения, и, тем самым, наборы значений аргументов
внешней функции также противоположны. Пусть 
i - суперпозиция этих самодвойственных функций. Тогда 
[поскольку
!' 4) В начале §1 гл.4 мы убедились в возможности представления любой функции многочленом Жегалкина.
Подмножеством множества многочленов является класс L 'линейных функций- функции вида 
. Здесь
- переменные, - булева константа (0 или 1).
Очевидно, что класс линейных функций - замкнутый: подстановка сумм вместо переменных представляет собой сумму; при этом некоторые пары слагаемых могут взаимно сократиться ввиду эквивалентности
Пример:Пусть
Тогда суперпозиция 
[в
функцию подставляем функцию 
вместо X и функцию вместо Y ] представляет собой линейную функцию:
5) Введем отношение частичного порядка для булевых векторов:
для
Заметим, что для булевых переменных строгое неравенство 
означает, что 
поскольку других возможностей нет.
Равенство 
добавляет варианты 
. Поэтому
неравенству 
удовлетворяют 3 пары 
и не
удовлетворяет только пара (1, 0) Можно заметить, что 
эквивалентно 
Класс М монотонных функций- это класс функций таких, что если 
, то 
, т е. функция на большем наборе
принимает не меньшее значение.
Среди заданных в табл 6 функций двух существенных переменных монотонными являются конъюнкция и дизъюнкция.
Покажем, что класс монотонных функций - замкнутый Пусть функции
что 
и требовалось доказать.
Отметим, что для каждой упорядоченной пары (А, В) различных
классов из пяти рассмотренных предполных 
существует
функция, входящая в А и не входящая в В . Таблица 8 содержит такие примеры каждая функция таблицы входит в класс, соответствующий строке и не входит в класс, соответствующий столбцу Например, входит
в Л/ , но не входит в S функция-константа 0; входит в S, но не входит в L функция 
Из этого замечания можно сделать важный
вывод никакой из пяти классов 
не входит целиком ни в
какой из остальных четырех
