Определение самодвойственной функции. Носитель функции. Мощность носителя. Лемма о мощности носителя

Самодвойственная функция - булева функция, двойственная сама к себе. Функцией, двойственной к функции , называется функция .

Значит, функция является самодвойственной, если .

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

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

Определение 8.10. Носителем функции называется совокупность наборов, на которых функция обращается в 1.

Определение 8.11. Мощностью носителя называется количество единиц в векторе значений функции.

Лемма 8.2. Если мощность носителя функции отлична от половины, то функция не является линейной. Обратное не верно.

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

Теорема Поста. Таблица Поста. Следствие из теоремы Поста о числе базисных функций в наборе.

Теорема Поста. Для того чтобы некоторый набор функций K был полным, необходимо и достаточно, чтобы в него входили функции, не принадлежащие каждому из классов T₀, T₁, L, M, S.

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

Из этой теоремы следует довольно простой способ выяснения полноты некоторого набора функций. Для каждой из этих функций выясняется принадлежность к перечисленным выше классам. Результаты заносятся в так называемую таблицу Поста (в нашем примере эта таблица составлена для 4-х функций, причем знаком “+” отмечается принадлежность функции соответствующему классу, знак “–” означает, что функция в него не входит).

В соответствии с теоремой Поста набор функций будет полным тогда и только тогда, когда в каждом столбце таблицы Поста имеется хотя бы один минус. Таким образом, из приведенной таблицы следует, что данные 4 функции образуют полный набор, но эти функции не являются базисом. Из этих функций можно образовать 2 базиса: f ₃, f ₁и f ₃, f ₂. Полными наборами будут любые наборы содержащие, какой-либо базис.

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