Пусть F – есть некоторое подмножество функций из P2.

Определение: Суперпозиция функций (булева формула) над F определяется индуктивно следующим образом:

1. Всякая функция f(x₁, x₂,…,x_n) из F есть суперпозиция (формула) над F.

2. Если А(x₁, x₂,…,x_m) (m – шаг индукции) – есть суперпозиция над F и каждое из выражений A₁, A₂,…,A_m есть либо суперпозиция над F, либо переменная, то функция A(A₁, A₂,…,A_n) – есть суперпозиция над F.

Замечание: Суперпозиция функций над F есть обычная подстановка функций из F.

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

Замечание: Одна и та же функция может быть записана разными формулами.

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

Определение: Замыкание класса F – множество всех суперпозиций над F. Обозначается [F] – замыкание класса F.

Замечание: Класс F – замкнутый, если F = [F].

Замечание:
1. F⊆[F]
2. [[F]] = [F] идемпотентность
3. F1⊆F2 ⇒ [F1] ⊆ [F2]

Определение: Система G функций из замкнутого класса F полна в F (является порождающей системой для F), если [G] = F. Система функций H полна в P2, если [H] = P2.

Полная в F система функций G называется базисом для F, если всякая собственная подсистема системы F полной для G уже не является.

Комментарии запрещены.