Определение Функциональной Полноты по Таблице Поста

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