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

ТЕОРЕМА ПОСТА О ПОЛНОТЕ

План лекции:

1. Важнейшие замкнутые классы булевых функций.

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

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

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

1.4. Класс монотонных функций.

1.5. Класс линейных функций.

2. Теорема Поста о полноте.

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

Важнейшие замкнутые классы булевых функций

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

Обозначим через класс всех булевых функций из , сохраняющих константу 0, то есть функций, которые равны нулю на нулевом наборе переменных:

.

Заметим, что если , а , то и .

Легко убедиться, что функции 0, , , , принадлежат классу , а функции 1, , , не входят в .

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

Покажем, что – замкнутый класс. Для этого надо доказать следующее утверждение.

Лемма 1. Суперпозиция функций из класса является функцией класса .

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

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

Теперь покажем, что функция , полученная в результате применения операции , принадлежит , если принадлежат :

.

Лемма доказана.

Пример 1. Функции и входят в , поэтому суперпозиция этих функций будет сохранять 0. Следовательно, система неполная.