Решение задачи: Критерий Поста для булевых функций

Для решения данной задачи необходимо воспользоваться критерием Поста о функциональной полноте системы булевых функций. Согласно теореме Поста, система функций является функционально полной тогда и только тогда, когда она не содержится целиком ни в одном из пяти замкнутых классов: 1. \( T_0 \) — класс функций, сохраняющих ноль. 2. \( T_1 \) — класс функций, сохраняющих единицу. 3. \( S \) — класс самодвойственных функций. 4. \( M \) — класс монотонных функций. 5. \( L \) — класс линейных функций. На практике это означает, что в таблице Поста для полной системы в каждом столбце (соответствующем классу) должен стоять хотя бы один минус. Если в каком-то столбце стоят только плюсы, это значит, что все функции системы принадлежат данному классу, и система не является полной. Проанализируем представленные варианты таблиц: Вариант 1: В столбце \( M \) (монотонные функции) у всех функций \( f_1, f_2, f_3 \) стоят плюсы. Это значит, что вся система состоит только из монотонных функций. Такая система не является полной. Вариант 2: Проверим каждый столбец на наличие хотя бы одного минуса: - Столбец \( T_0 \): есть минусы (у \( f_1 \) и \( f_3 \)). - Столбец \( T_1 \): есть минусы (у \( f_1 \) и \( f_3 \)). - Столбец \( S \): есть минус (у \( f_2 \)). - Столбец \( M \): есть минусы (у \( f_1 \) и \( f_2 \)). - Столбец \( L \): есть минусы (у всех функций). В каждом столбце есть хотя бы один минус. Следовательно, эта система функций является функционально полной. Вариант 3: В столбце \( S \) (самодвойственные функции) у всех функций стоят плюсы. Система не является полной. Ответ: Функционально полной системе соответствует вторая таблица (средняя на изображении).