Решение задачи: критерий Поста и функциональная полнота

Для решения данной задачи необходимо воспользоваться критерием Поста о функциональной полноте системы булевых функций. Согласно теореме Поста, система функций \( F = \{f_1, f_2, \dots, f_n\} \) является функционально полной тогда и только тогда, когда она не содержится целиком ни в одном из пяти замкнутых классов: 1. \( T_0 \) — класс функций, сохраняющих ноль. 2. \( T_1 \) — класс функций, сохраняющих единицу. 3. \( S \) — класс самодвойственных функций. 4. \( M \) — класс монотонных функций. 5. \( L \) — класс линейных функций. На практике это означает, что в таблице Поста в каждом столбце (соответствующем классу) должен стоять хотя бы один минус \( - \). Если в каком-то столбце стоят только плюсы \( + \), это значит, что вся система функций принадлежит данному классу и не является полной. Проанализируем представленные варианты таблиц: 1. Первая таблица: В столбце \( T_0 \) есть минус (у \( f_3 \)). В столбце \( T_1 \) есть минус (у \( f_1 \)). В столбце \( S \) есть минус (у \( f_2 \)). В столбце \( M \) есть минусы (у \( f_1, f_2 \)). В столбце \( L \) есть минус (у \( f_3 \)). Вывод: В каждом столбце есть хотя бы один минус. Система полна. 2. Вторая таблица: В столбце \( T_1 \) стоят только минусы (это допустимо), но в столбце \( L \) стоят только плюсы \( + \). Это значит, что все функции системы линейны, и система не полна. 3. Третья таблица: В столбце \( T_0 \) стоят только плюсы \( + \). Это значит, что все функции сохраняют ноль. Система не полна. 4. Четвертая таблица (на втором фото): В столбце \( L \) стоят только минусы, но в столбце \( S \) стоят только плюсы \( + \). Система не полна. 5. Пятая таблица (на втором фото): В столбце \( T_1 \) стоят только минусы, но в столбце \( M \) стоят только плюсы \( + \). Система не полна. Правильный ответ: Первая таблица. Запись для тетради: Система булевых функций является функционально полной, если она не входит целиком ни в один из классов Поста (\( T_0, T_1, S, M, L \)). В таблице Поста это условие выполняется, если в каждом столбце имеется хотя бы один знак \( - \). Этому условию удовлетворяет первая таблица: \[ \begin{array}{|c|c|c|c|c|c|} \hline & T_0 & T_1 & S & M & L \\ \hline f_1 & + & - & + & - & + \\ \hline f_2 & + & + & - & - & + \\ \hline f_3 & - & + & + & + & - \\ \hline \end{array} \] Так как в каждом столбце есть хотя бы один минус, система функций \( \{f_1, f_2, f_3\} \) полна.