Теорема Поста

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

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

Определение двойственной булевой функции

Пример 1. Используя принцип двойственности, запишем булеву функцию, двойственную заданной булевой функции, расставим в полученной булевой функции скобки, указывающие порядок выполнения действий.

Нахождение двойственной булевой функции

Определение самодвойственной булевой функции

Критерий самодвойственности функции

Алгоритм получения констант 0 или 1 из самодвойственной функции

Пример 2. Несамодвойственная функция F = (01011001) задана вектором значений. Используя лемму о несамодвойственной функции, под­становкой вместо переменных x, y, z только переменную x и её отрицание получим одну из констант (0 либо 1).

Решение примера 2

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

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

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

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

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

Определение полинома Жегалкина

Алгоритм построения полинома Жегалкина

Подробнее о полиноме Жегалкина, а также примеры получения полинома Жегалкина для произвольной булевой функции можно посмотреть: https://dzen.ru/media/id/603a418d1684900aa2499416/626a3bfbba5af966073fd4b8.

Класс линейных булевых функций

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

Сравнимые и несравнимые наборы и др. необходимые определения

Критерий монотонности булевой функции

Теорема Поста о полноте системы булевых функций.

Формулировка теоремы Поста о полноте системы булевых функций

Если при проверке системы булевых функций на полноту обнаружится, что все булевы функции системы принадлежат одному из классов S, Т0, Т1, L, М, то такая система булевых функций не полна.

Если для каждого класса S, Т0, Т1, L ,М можно указать функцию системы, не принадлежа­щую этому классу, то такая система булевых функций полна.

Пример 3. Каким из замкнутых классов Поста принадлежит функция F(x, y, z), заданная своими нулевыми или единичными наборами: F (0, 1, 0) = F (1, 0, 0) = F (1, 0, 1) = 0?

Решение примера 3

Упражнение 1. Используя принцип двойственности, запишите булеву функцию, двойственную заданной булевой функции (см. варианты ниже), расставьте в полученной булевой функции скобки, указывающие порядок выполнения действий.

Варианты для Упражнения 1 (часть 1)

Варианты для Упражнения 1 (часть 2)

Упражнение 2. Несамодвойственная функция F задана вектором значений (см. варианты ниже). Используя лемму о несамодвойственной функции, под­становкой вместо переменных x, y, z только переменную x и её отрицание получите одну из констант (0 либо 1).

Варианты для Упражнения 2

Упражнение 3. Выясните, каким из замкнутых классов Поста принадлежит функция F(x, y, z), заданная своими нулевыми или единичными наборами (см. варианты ниже)?

Варианты для Упражнения 3