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

СПЕЦИАЛЬНЫЕ КЛАССЫ БУЛЕВСКИХ

ФУНКЦИЙ

ОПРЕДЕЛЕНИЕ

Множество функций B называется замкнутым классом, если [B] = B.

Например, множество {x, } является замкнутым классом. Рассмотрим пять специальных классов булевских функций, свойства которых будут использованы при нахождении простых необходимых и достаточных условий полноты произвольных систем функций в P₂.

ФУНКЦИИ, СОХРАНЯЮЩИЕ НОЛЬ

Обозначим как Т₀ множество всех таких булевских функций, которые на нулевом наборе значений переменных принимают значение 0.

О таких функциях говорят, что они сохраняют 0, т.е. множество б.ф., сохраняющих ноль, это:

Т₀ = {f(x₁,...,x _n) ½ f(0,...,0) = 0}.

Сформулируем простейшие свойства класса T₀.

1. Класс T₀ является замкнутым классом функций.

Для проверки справедливости последнего утверждения достаточно проверить, что всякая формула U(f₁, . . . , f_p), составленная с помощью функций f₁, . . . , f_p, сохраняющих ноль, представляет функцию f_U, которая также сохраняет ноль.

Проведем обоснование этого свойства в соответствии с определением понятия формулы над классом функций.

1.1.Если U = f(x₁,. . . , x_n), где f(x₁, . . . , x_n)ÎT₀, то
f (0, . . . , 0) = 0и f_U = f.

1.2.Если U = f (U₁,...,U_n), где f (x₁, . . . , x _n) Î T₀, а
U₁, . . . ,U_n - это или символы переменных или подформулы формулы U, составленные с помощью функций из T₀ и символов переменных. Заметим, что поскольку обозначение переменной представляет тождественную функцию I(x) = x, то U₁, . . . ,U_n можно рассматривать как подформулы, представляющие некоторые функции из класса T₀. Тогда функция f( ) также принадлежит классу T₀.

Действительно, f(g₁(0,. . . , 0),. . . , g_n (0, . . . ,0))= f(0, . . . ,0)=0.

2. Определим число различных функций переменных
x₁, . . . , x_n, которые содержатся в T₀.

Поскольку функции из T₀ на всех наборах значений переменных, отличных от нулевого набора, принимают произвольные значения, и таких ненулевых наборов 2ⁿ-1, то в T₀ содержится ровно различных булевских функций n переменных.

ФУНКЦИИ, СОХРАНЯЮЩИЕ ЕДИНИЦУ

Обозначим как T₁ множество всех булевских функций, которые на единичном наборе значений переменных принимают значение 1. О таких булевских функциях говорят, что они сохраняют единицу, т.е. Т₁ = {f(x₁, . . . , x_n) ½ f(1, . . . , 1) = 1}.

Класс T₁ является замкнутым и содержит различных функций n переменных. Последние свойства могут быть обоснованы аналогично тому, как это делалось для класса T₁.

САМОДВОЙСТВЕННЫЕ ФУНКЦИИ

Двоичные наборы и называются противоположными наборами.

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

Докажем это утверждение. Заметим, что середина таблицы располагается между последним набором верхней половины таблицы (0, 1, . . . , 1) и первым набором значений переменных в нижней половине таблицы (1, 0,. . . , 0).

Тогда, пусть и - произвольные противоположные наборы. Для определенности будем считать, что s₁ =0.

1. Для набора , расположенного в верхней половине таблице, определим расстояние до нижнего набора верхней половины таблицы, т.е. количество наборов до набора (0, 1, . . . ,1). Нетрудно видеть, что искомое расстояние представляется числом, имеющим двоичное представление в виде набора .

2. Определим двоичный набор, находящийся на таком же расстоянии от набора (1,0, . . . , 0), являющегося первым набором нижней половины таблицы

Нетрудно проверить, что 10. . . 0+ = .

Следовательно, набор, отстоящий от (1, 0, . . . , 0) на расстоянии , - это набор, который является противоположным . Поэтому расстояния от противоположных наборов и до середины таблицы равны.

ОПРЕДЕЛЕНИЕ

Пусть f(x₁, . . . , x_n) Î P₂. Функция g(x₁, . . . , x_n) Î P₂ называется двойственной к функции f, если

g(x₁, . . . , x_n) = .

Двойственная функция к заданной функции f обозначается как f*.

Нетрудно проверить, что , , .

Кроме того, легко убедиться в справедливости следующего свойства: функция, двойственная к двойственной функции, совпадает с исходной функцией, т.е. справедливо равенство: f** = f.

ОПРЕДЕЛЕНИЕ

Функция f называется самодвойственной, если f = f*.

То есть всякая самодвойственная функция на любых двух противоположных наборах значений переменных принимает противоположные значения. Примерами самодвойственных функций являются тождественная функция f(x) = x и отрицание f(x) = .

Множество всех самодвойственных функций обозначается как S.

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

Пусть f(x₁, . . . , x_n) - произвольная булевская функция, заданная таблично.

1. Выпишем столбец значений f в обратном порядке.

2. В полученном столбце выполним замену всякого значения в нем на противоположное значение.

Полученный в результате столбец значений функции представляет собой столбец значений двойственной функции f*. Действительно, первое преобразование позволяет по столбцу значений функции f(x₁, . . . , x_n)получить столбец значений функции f( ).

Второе преобразование переводит функцию f( ) в ее отрицание, т.е. окончательная функция - это f*.

Если функция f задана формулой, то для получения формульного представления функции f* можно воспользоваться следующей теоремой.

ТЕОРЕМА 4.7 (О формуле для двойственной функции)

Пусть f(x₁, . . . , x_n)представляется формулой U (g₁,..., g_n). Тогда функция f* представляется формулой

U* = U(g*₁, . . . , g*_n).

Доказательство

Докажем теорему индукцией по глубине формулы U.

1. Базис индукции.Покажем, что если f = , то представляется формулой . Запишем цепочку равенств:

=

=

= .

2. Индуктивное предположение. Предположим, что доказываемое в свойство выполняется для всех формул, глубина которых не превосходит n.

3.Индуктивный переход. Пусть f = U(g₁,..., g_n), где U(g₁,..., g_n) - это формула глубины n + 1, составленная с помощью символов переменных и функций g₁,..., g_n

Предположим, что U = h(U₁, . . . , U_n), где для формул U₁, . . . , U_n и представляемых ими булевских функций w₁, . . . , w_n справедлива доказываемая теорема.

Тогда аналогично доказательству базиса индукции можно показать, что = .

Поскольку всякая функция представляется формулой , то представляется формулой , т.е. формулой U( ,..., ).