Решение задачи: Выделение базисов булевых функций

Для решения задачи по поиску базисов из заданного множества функций необходимо проверить каждую функцию на принадлежность к пяти замкнутым классам Поста: \(T_0\) (сохранение нуля), \(T_1\) (сохранение единицы), \(S\) (самодвойственность), \(M\) (монотонность) и \(L\) (линейность). Выпишем функции из множества \(A\): \(f_1 = xy \oplus z\) \(f_2 = x \oplus y \oplus 1\) (что эквивалентно \(\neg(x \oplus y)\)) \(f_3 = xy\) \(f_4 = x\) Составим таблицу принадлежности функций классам Поста: 1. Функция \(f_1 = xy \oplus z\): \(f_1(0,0,0) = 0 \cdot 0 \oplus 0 = 0 \in T_0\) \(f_1(1,1,1) = 1 \cdot 1 \oplus 1 = 0 \notin T_1\) Проверка на самодвойственность: \(\neg f_1(0,0,0) = 1 \neq f_1(1,1,1) = 0\), значит \(\notin S\) Проверка на монотонность: \(f_1(1,1,0) = 1\), \(f_1(1,1,1) = 0\). При увеличении набора значение уменьшилось, значит \(\notin M\) Проверка на линейность: содержит произведение \(xy\), значит \(\notin L\) 2. Функция \(f_2 = x \oplus y \oplus 1\): \(f_2(0,0) = 0 \oplus 0 \oplus 1 = 1 \notin T_0\) \(f_2(1,1) = 1 \oplus 1 \oplus 1 = 1 \in T_1\) Проверка на самодвойственность: \(\neg f_2(0,0) = 0\), \(f_2(1,1) = 1\); \(\neg f_2(0,1) = \neg(0 \oplus 1 \oplus 1) = 1\), \(f_2(1,0) = 1 \oplus 0 \oplus 1 = 0\). Не самодвойственна \(\notin S\) Проверка на монотонность: \(f_2(0,0) = 1\), \(f_2(0,1) = 0\), значит \(\notin M\) Проверка на линейность: представлена в виде суммы по модулю 2, значит \(\in L\) 3. Функция \(f_3 = xy\): \(f_3(0,0) = 0 \in T_0\) \(f_3(1,1) = 1 \in T_1\) Проверка на самодвойственность: \(\neg f_3(0,0) = 1 \neq f_3(1,1) = 1\), но \(\neg f_3(0,1) = 1 \neq f_3(1,0) = 0\), значит \(\notin S\) Проверка на монотонность: конъюнкция монотонна \(\in M\) Проверка на линейность: содержит произведение, значит \(\notin L\) 4. Функция \(f_4 = x\): \(f_4(0) = 0 \in T_0\) \(f_4(1) = 1 \in T_1\) Проверка на самодвойственность: \(\neg f_4(0) = 1 = f_4(1)\), значит \(\in S\) Проверка на монотонность: \(\in M\) Проверка на линейность: \(\in L\) Итоговая таблица: Функция | \(T_0\) | \(T_1\) | \(S\) | \(M\) | \(L\) \(f_1\) | + | - | - | - | - \(f_2\) | - | + | - | - | + \(f_3\) | + | + | - | + | - \(f_4\) | + | + | + | + | + Согласно критерию Поста, система функций является полной тогда и только тогда, когда она содержит хотя бы одну функцию, не входящую в каждый из пяти классов. Для нахождения всех базисов (минимальных полных подсистем) проанализируем комбинации: Класс \(T_0\) не содержит \(f_2\). Класс \(T_1\) не содержит \(f_1\). Класс \(S\) не содержит \(f_1, f_2, f_3\). Класс \(M\) не содержит \(f_1, f_2\). Класс \(L\) не содержит \(f_1, f_3\). Проверим подмножество \(\{f_1, f_2\}\): \(T_0\): \(f_2 \notin T_0\) (есть) \(T_1\): \(f_1 \notin T_1\) (есть) \(S\): \(f_1, f_2 \notin S\) (есть) \(M\): \(f_1, f_2 \notin M\) (есть) \(L\): \(f_1 \notin L\) (есть) Система \(\{f_1, f_2\}\) полная. Так как при удалении любой из них полнота теряется (например, без \(f_1\) все функции будут в \(T_1\)), это базис. Проверим подмножество \(\{f_2, f_3\}\): \(T_0\): \(f_2 \notin T_0\) (есть) \(T_1\): Обе функции в \(T_1\). Условие не выполняется. Система не полная. Проверим подмножество \(\{f_1, f_2, f_3\}\): Оно содержит базис \(\{f_1, f_2\}\), поэтому не является базисом (не минимально). Проверим функции с участием \(f_4\): \(f_4\) принадлежит \(T_0, T_1, S, M, L\). Она не помогает перекрыть ни один класс, который не был бы уже перекрыт другими функциями. Формула нахождения базисов (через характеристические функции классов): Пусть \(x_i\) — включение функции \(f_i\) в базис. Составим КНФ, где каждая скобка отвечает за отсутствие принадлежности классу: \[ K = (x_2) \wedge (x_1) \wedge (x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2) \wedge (x_1 \vee x_3) \] Упрощаем выражение: \[ K = x_2 \wedge x_1 \wedge (x_1 \vee x_3) = x_1 \wedge x_2 \] Единственное минимальное решение — это выбор функций \(f_1\) и \(f_2\). Ответ: В данной системе существует только один базис: \[ B = \{xy \oplus z, x \oplus y \oplus 1\} \]