- •4.13. Специальные классы булевских функций определение
- •4.13.1. Функции, сохраняющие ноль
- •4.13.2. Функции, сохраняющие единицу
- •4.13.3. Самодвойственные функции
- •Определение
- •Определение
- •4.13.4. Монотонные функции
- •Определение
- •4.13.5. Линейные функции
- •4.14. Критерий функциональной полноты
- •4.14.1. Построение функций-констант
- •4.14.3. Построение конъюнкции
- •4.15. Предполные классы булевских функций определение
Определение
Пусть f(x1, . . . , xn) P2. Функция g(x1, . . . , xn) P2 называется двойственной к функции f, если
g(x1, . . . , xn) = .
Двойственная функция к заданной функции f обозначается как f*.
Нетрудно проверить, что , , .
Кроме того, легко убедиться в справедливости следующего свойства: функция, двойственная к двойственной функции, совпадает с исходной функцией, т.е. справедливо равенство: f** = f.
Определение
Функция f называется самодвойственной, если f = f*.
То есть всякая самодвойственная функция на любых двух противоположных наборах значений переменных принимает противоположные значения. Примерами самодвойственных функций являются тождественная функция f(x) = x и отрицание f(x) = .
Множество всех самодвойственных функций обозначается как S.
Установленное ранее свойство симметричности расположения противоположных наборов в табличном задании булевских функций позволяет использовать следующую схему построения табличного задания функции, двойственной к заданной функции.
Пусть f(x1, . . . , xn) произвольная булевская функция, заданная таблично.
1. Выпишем столбец значений f в обратном порядке.
2. В полученном столбце выполним замену всякого значения в нем на противоположное значение.
Полученный в результате столбец значений функции представляет собой столбец значений двойственной функции f*. Действительно, первое преобразование позволяет по столбцу значений функции f(x1, . . . , xn) получить столбец значений функции f( ).
Второе преобразование переводит функцию f( ) в ее отрицание, т.е. окончательная функция это f*.
Если функция f задана формулой, то для получения формульного представления функции f* можно воспользоваться следующей теоремой.
ТЕОРЕМА 4.7 (О формуле для двойственной функции)
Пусть f(x1, . . . , xn) представляется формулой U (g1,..., gn). Тогда функция f* представляется формулой
U* = U(g*1, . . . , g*n).
Доказательство
Докажем теорему индукцией по глубине формулы U.
1. Базис индукции. Покажем, что если f = , то представляется формулой . Запишем цепочку равенств:
=
=
= .
2. Индуктивное предположение. Предположим, что доказываемое в свойство выполняется для всех формул, глубина которых не превосходит n.
3. Индуктивный переход. Пусть f = U(g1,..., gn), где U(g1,..., gn) это формула глубины n + 1, составленная с помощью символов переменных и функций g1,..., gn
Предположим, что U = h(U1, . . . , Un), где для формул U1, . . . , Un и представляемых ими булевских функций w1, . . . , wn справедлива доказываемая теорема.
Тогда аналогично доказательству базиса индукции можно показать, что = .
Поскольку всякая функция представляется формулой , то представляется формулой , т.е. формулой U( ,..., ).
Доказательство окончено.
Пример. Пусть U = . Тогда U* = .
Определим число самодвойственных функций, имеющих n переменных. Из условия самодвойственности следует, что на противоположных наборах значений переменных всякая принимает противоположные значения. Поэтому всякая однозначно определяется своим заданием на наборах верхней половины табличного задания булевских функций n переменных, то есть на 2n-1 наборах.
Следовательно, число функций n переменных в S равно .
Покажем, что множество функций S является замкнутым классом. Поскольку тождественная функция f(x) = x является самодвойственной, то для доказательства замкнутости класса всех самодвойственных функций достаточно проверить, что если h = , где f, g1, . . . , gn это самодвойственные функции, то h = h*.
Воспользуемся теоремой о формуле для двойственной функции. Тогда h* = = = = h, т.е. S это замкнутый класс.
Лемма (О несамодвойственной функции)
Если f S, то подстановкой вместо переменных этой функции функций x и можно получить одну из функций констант.
Доказательство
Пусть f S. Тогда найдётся таких два противоположных набора и , что f = f . Определим вспомогательные функции:
, где i =1,..., n.
Тогда функция h(x) = f( совпадает с одной из функций констант.
Определим значения h(0) и h(1):
h(0) = f ( = f .
h(1) = f( = f .
Следовательно, h(0) = h(1).
Доказательство окончено.
Замечание. Поскольку функции-константы не являются самодвойственными, то доказанная лемма утверждает, что из любой несамодвойственной функции можно получить простейшую несамодвойственную функцию.
Упражнение. Доказать утверждение, обратное утверждению, сформулированному в лемме о несамодвойственной функции.