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 функция Из этого замечания можно сделать важный
вывод никакой из пяти классов не входит целиком ни в
какой из остальных четырех