[Список тем]

Замкнутые классы

Пусть F = {f₁,...f_m}, где f_i P₂. Замыканием F (обозначается [F]) называется множество всех булевых функций, реализуемых формулами над F:
[F]:= {f P₂ | f = func T[F]}
Свойства замыкания:

1. F [F]
2. [[F]] = [F]
3. F₁ F₂ → [F₁] [F₂ ]
4. ([F₁] [F₂]) → [F₁ F₂]

Некоторые замкнутые классы
Класс (множество) функций F называется замкнутым, если [F]=F.
Рассмотрим следующие классы функций:

1. Класс функций, сохраняющих 0: P₀: = {f | f(0,...,0) = 0}. Это функции f0 - f7 (в старшем разряде двоичного числа, соответствующего функции, под нулевыми значениями аргументов стоят 0).
2. Класс функций, сохраняющих 1: P₁: = {f | f(1,...,1) = 1}. Это функции f1, f3, f5, f7, f9, f11, f13, f15 (в младшем разряде двоичного числа, соответствующего функции, под единичными значениями аргументов стоят 1).
3. Класс самодвойственных функций Ps:={f | f* = f}. Это функции f3, f5, f10, f12 для которых столбец значений (в таблице - строка), будучи инвертированным и перевернутым, перейдет сам в себя.
4. Класс монотонных функций: P_<= :={f | a<= b →f(a) <= f(b)}. Это функции f0, f1, f3, f5, f7, f10, f12, f15.
5. Класс линейных функций: P_L :={f | f = c₀ c ₁x₁... c_nx_n} т.е. при представлении в виде многочлена Жегалкина функция не содержит произведений переменных. Это функции f0, f10, f12, f15.

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

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

Полные системы функций

Система функций является полной, если с помощью ее функций можно получить все основные логические операции {&, , ¬}за конечное число действий.

1. система {&, ¬} - полная, так как x1x2 = ¬(¬x1 & ¬x2);
2. система {, ¬ } - полная, так как x1&x2 = ¬(¬x1 ¬x2);
3. система {|} - полная, так как ¬x = x|x; x1&x2 = ¬(x1 | x2) = (x1 | x2)|(x1 | x2);
4. система {↓} - полная, так как ¬x = x↓x; x1x2 = ¬(x1 ↓ x2) = (x1 ↓ x2)↓ (x1 ↓ x2);
5. система {0, 1, & , } - полная, так как ¬x= x 1. Представление функции в базисе {0, 1, & , } называется полиномом Жегалкина.

[Список тем]