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

Для решения задачи по выделению базисов из системы булевых функций воспользуемся критерием Поста. Система функций является базисом, если она полна (содержит функции, не сохраняющие константы 0 и 1, несамодвойственные, немонотонные и нелинейные) и при этом никакое её собственное подмножество не является полным. Обозначим функции системы \( A \): \[ f_1 = xy \oplus z \] \[ f_2 = x \oplus y \oplus 1 \] \[ f_3 = x\bar{y} \] \[ f_4 = \bar{x} \] Составим таблицу принадлежности функций пяти замкнутым классам Поста: \( T_0 \) (сохранение нуля), \( T_1 \) (сохранение единицы), \( S \) (самодвойственность), \( M \) (монотонность), \( L \) (линейность). 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 \) - Несамодвойственна (\( S \)): \( f_1(0,0,0)=0 \), \( \bar{f_1}(1,1,1)=1 \), значения совпадают, значит \( \notin S \). - Немонотонна (\( M \)): при увеличении \( z \) с 0 до 1 значение меняется с 1 на 0 (при \( x=y=1 \)). - Нелинейна (\( L \)): содержит произведение \( xy \). 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 \) - Самодвойственна (\( S \)): \( \bar{f_2}(\bar{x}, \bar{y}) = \overline{(x \oplus 1) \oplus (y \oplus 1) \oplus 1} = \overline{x \oplus y \oplus 1} = x \oplus y \), не совпадает с \( f_2 \). Значит \( \notin S \). - Немонотонна (\( M \)): \( f_2(0,0)=1 \), \( f_2(1,0)=0 \). - Линейна (\( L \)): представлена в виде суммы по модулю 2. 3. Анализ \( f_3 = x\bar{y} \): - \( f_3(0,0) = 0 \cdot 1 = 0 \in T_0 \) - \( f_3(1,1) = 1 \cdot 0 = 0 \notin T_1 \) - Несамодвойственна (\( S \)): \( f_3(0,0)=0 \), \( \bar{f_3}(1,1)=1 \), \( \notin S \). - Немонотонна (\( M \)): \( f_3(1,0)=1 \), \( f_3(1,1)=0 \). - Нелинейна (\( L \)): \( x(y \oplus 1) = xy \oplus x \). 4. Анализ \( f_4 = \bar{x} \): - \( f_4(0) = 1 \notin T_0 \) - \( f_4(1) = 0 \notin T_1 \) - Самодвойственна (\( S \)): \( \bar{f_4}(\bar{x}) = \overline{\bar{\bar{x}}} = \bar{x} \in S \). - Немонотонна (\( M \)): \( \notin M \). - Линейна (\( L \)): \( x \oplus 1 \in L \). Таблица классов: Функция | T0 | T1 | S | M | L --- | --- | --- | --- | --- | --- f1 | + | - | - | - | - f2 | - | + | - | - | + f3 | + | - | - | - | - f4 | - | - | + | - | + Для полноты системы нужно иметь хотя бы один "минус" в каждом столбце. - Класс \( T_0 \): отсутствуют \( f_2, f_4 \). - Класс \( T_1 \): отсутствуют \( f_1, f_3, f_4 \). - Класс \( S \): отсутствуют \( f_1, f_2, f_3 \). - Класс \( M \): отсутствуют все. - Класс \( L \): отсутствуют \( f_1, f_3 \). Проверка подмножеств на базис: 1. Пара \( \{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 \)), это базис. 2. Пара \( \{f_1, f_4\} \): - \( T_0 \): \( f_4 \notin T_0 \) - \( T_1 \): \( f_1, f_4 \notin T_1 \) - \( S \): \( f_1 \notin S \) - \( M \): \( f_1, f_4 \notin M \) - \( L \): \( f_1 \notin L \) Система полна. Это базис. 3. Пара \( \{f_2, f_3\} \): - \( T_0 \): \( f_2 \notin T_0 \) - \( T_1 \): \( f_3 \notin T_1 \) - \( S \): \( f_2, f_3 \notin S \) - \( M \): \( f_2, f_3 \notin M \) - \( L \): \( f_3 \notin L \) Система полна. Это базис. 4. Пара \( \{f_3, f_4\} \): - \( T_0 \): \( f_4 \notin T_0 \) - \( T_1 \): \( f_3, f_4 \notin T_1 \) - \( S \): \( f_3 \notin S \) - \( M \): \( f_3, f_4 \notin M \) - \( L \): \( f_3 \notin L \) Система полна. Это базис. Ответ: Всевозможные базисы системы: 1) \( \{xy \oplus z, x \oplus y \oplus 1\} \) 2) \( \{xy \oplus z, \bar{x}\} \) 3) \( \{x\bar{y}, x \oplus y \oplus 1\} \) 4) \( \{x\bar{y}, \bar{x}\} \)