Класс функций, сохраняющих 1, т1

f(x₁,x₂,…,x_n)P₂(n)  f(1,1,…,1)=1.

.

Доказательство замкнутости класса Т₁ аналогично доказательству замкнутости класса Т₀. Мощность класса T₁(n)=|P₂(n)|/2. Неполнота класса Т₁ следует из существования функций, не сохраняющих 1. , а .

Лемма о функции, не сохраняющей 1: Если fТ₁, то отождествлением ее переменных или подстановками функций, сохраняющих 1, из нее можно получить константу 0 или функцию отрицания х.

Пример. Получим константу 0 и функцию отрицания из функции . Тождественная функция и константа 1 сохраняют 1 и, следовательно, могут участвовать в подстановках при доказательстве.

Произведем отождествление переменных, т.е. подстановку переменной x в формулу:

. Отождествлением переменных получили константу 0.

Следующая подстановка позволяет получит функцию отрицания.

.

Класс самодвойственных функций s

f(x₁,x₂,…,x_n)Sf(x₁,x₂,…,x_n)=f^*(x₁,x₂,…,x_n)=f(x_1,x₂,…,x_n).

Иначе, самодвойственная функция равна своей двойственной функции: .

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

Пусть и . Определим двойственную к F функцию:

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

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

.

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

Неполнота класса самодвойственных функций следует из существования не самодвойственных функций.

Лемма о не самодвойственной функции: Если f(x₁,x₂,…,x_n) S, то отождествлением переменных и подстановкой в нее самодвойственных функций х и х можно получить не самодвойственную функцию – константу 0 или 1.

 Пусть Тогда найдется набор значений переменных такой, что . Выполним подстановку в данную функцию самодвойственной функции Полученную суперпозицию запишем в виде:

По определению значения первичного терма

Далее определим значения Ф(x) при х=1.



Таким образом, получена не самодвойственная функция – константа. Используя функцию отрицания, можно получить другую константу. Рассмотрим примеры «работы» леммы над не самодвойственной функцией.

Пример1. так как f(01)=f(10)=1. Произведем указанную в лемме подстановку, выбрав набор (0,1). Тогда

Пример 2.

Тогда .

Пример 3. Пусть функция задана вектором (1011 1001). Здесь наборы с номерами 3 и 4 являются противоположными, и . МДНФ для этой функции имеет вид

.

Выполним подстановку на наборах значений переменных с номерами 3 и 4 в формулу.

Таким образом, получена константа 1. Из наборов с номерами 1 и 6 можно получить константу 0.