Самодвойственность. Класс S

Функции f (`х <sup>n</sup>) и g (`х ⁿ) двойственны (f = g^*), если они принимают противоположные значения на обратных наборах значений переменных f(`х <sup>n</sup>) =`g (`х ^n*).

Определение. Функция f (`хⁿ) называется самодвойственной, если f = f ^*

Множество самодвойственных функций n переменных обозначают Sⁿ, а все множество самодвойственных функций алгебры логики — S. Это множество является замкнутым предполным классом в Р₂.

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

Пример. Проверить самодвойственность функций:

а) Øх , б)`х ¯ у , в) (00101011).

Решение.Проверку производим по векторам истинности с использованием описанного выше их свойства для самодвойственных функций.

а) Делим вектор истинности функции Øх на две половины: (1÷ 0). Поскольку в первой половине один символ (1), то симметричное отражение дает его же. Инвертируя его, получим символ 0, который совпадает со второй половиной вектора. Следовательно, отрицание — самодвойственная функция.

б) Вектор истинности функции`х ¯ у делим на две половины: (00÷ 10). Симметричное отражение первой половины относительно разделяющей черты не меняет ее. После инвертирования получим последовательность (11), которая не совпадает со второй половиной вектора истинности (10). Поэтому`х ¯ у — не самодвойственная функция.

в) Делим вектор истинности на две половины (0010÷1011). Симметрично отразим первую половину относительно разделяющей черты — (0100) и инвертируем ее — (1011). Полученная последовательность совпала со второй половиной вектора истинности, следовательно, рассмотренная функция — самодвойственная.

Ответ: функции а) Øх и в) (00101011) — самодвойственны, функция б)`х¯у — нет.

Рассмотрим самодвойственность элементарных функций с учетом числа переменных n в них.

n=0. Константы 0 и 1 не являются самодвойственными.

n=1. Тождество и отрицание входят в S (х ÎS,Øх ÎS).

n=2. Ни одна из элементарных функций не входит в S. Все двухместные самодвойственные функции f (х,у)имеют одну фиктивную переменную и сводятся к функциям х, у, Øх, Øу.

Следовательно, для получения самодвойственных функций, имеющих две существенных переменных, необходимо рассматривать n ³ 3.

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