Функционально замкнутые классы булевых функций. Замкнутые классы T0 , T1

Класс (множество) булевых функций функционально замкнут, если вместе с функциями он содержит все их суперпозиции. Класс всех булевых функций замкнут. Класс функций от одной переменной замкнут. Класс булевых функций от двух переменных не замкнут, так как если взять две функции от двух переменных f = x ~ y и g = t & p, то их четыре суперпозиции: (t & p) ~ y, x ~ (t & p), (x ~ y) & p и t & (x ~ y) будут зависеть от трёх переменных.

Класс T - это класс функций, хранящих ноль. Функция принадлежит T , если во всех нулях она равна нулю. Например, из 16 функций от двух переменных функции: f0, …, f7 принадлежат T , так как при x = 0 и y = 0 эти функции имеют значение ноль. Тогда как функции: f8, …, f15 не принадлежат T , так как при x = 0 и y = 0 эти функции имеют значение единица.

Класс T - это класс функций, хранящих единицу. Функция принадлежит T , если во всех единицах она равна единице. Например, из 16 функций от двух переменных восемь функций с нечётными номерами: f1, f3,…, f13, f15 принадлежат T , так как при x = 1 и y = 1 эти функции имеют значение единица. Тогда как восемь функций с чётными номерами: f0, f2, …, f12, f14 не принадлежат T , так как при x = 1 и y = 1 эти функции имеют значение ноль.

8. Теорема Поста, её необходимость. Таблица Поста.

Теорема Поста: для того, чтобы система булевых функций F = {F1, …, Fm} была полной, необходимо и достаточно, чтобы для каждого из классов T , T , S, L и M нашлась функция Fj из системы F, не принадлежащая этому классу.

Доказательство необходимости: Классы T , T , S, L и M попарно различны и не совпадают с классом всех булевых функций. Если бы все функции системы F принадлежали какому-либо из этих классов, то в силу замкнутости этого класса система F не была бы полной. Необходимость теоремы доказана.