В лекции приводятся определения основных классов булевых функций, а также формулируется теорема Поста о полноте.
Класс самодвойственных функций.
Пример 1. Используя принцип двойственности, запишем булеву функцию, двойственную заданной булевой функции, расставим в полученной булевой функции скобки, указывающие порядок выполнения действий.
Пример 2. Несамодвойственная функция F = (01011001) задана вектором значений. Используя лемму о несамодвойственной функции, подстановкой вместо переменных x, y, z только переменную x и её отрицание получим одну из констант (0 либо 1).
Класс булевых функций, сохраняющий константу 0.
Класс булевых функций, сохраняющий константу 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?
Упражнение 1. Используя принцип двойственности, запишите булеву функцию, двойственную заданной булевой функции (см. варианты ниже), расставьте в полученной булевой функции скобки, указывающие порядок выполнения действий.
Упражнение 2. Несамодвойственная функция F задана вектором значений (см. варианты ниже). Используя лемму о несамодвойственной функции, подстановкой вместо переменных x, y, z только переменную x и её отрицание получите одну из констант (0 либо 1).
Упражнение 3. Выясните, каким из замкнутых классов Поста принадлежит функция F(x, y, z), заданная своими нулевыми или единичными наборами (см. варианты ниже)?