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

Задача: Из полной системы булевых функций \( A = \{f_1, f_2, f_3, f_4\} \) выделить всевозможные базисы. Даны функции: \[ 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 \). - Не монотонна (\( M \)): \( f_1(1,1,0) = 1 \), \( f_1(1,1,1) = 0 \). - Не линейна (\( 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(0,1) = 0 \), \( f_2(1,0) = 0 \). Функция \( S \), если \( f(\bar{x}) = \bar{f}(x) \). Здесь \( f_2(0,0)=1, f_2(1,1)=1 \) — не самодвойственна. - Не монотонна (\( M \)): \( f_2(0,0) = 1 \), \( f_2(1,0) = 0 \). - Линейна (\( L \)). 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 \)). - Не монотонна (\( M \)): \( f_3(1,0) = 1 \), \( f_3(1,1) = 0 \). - Не линейна (\( L \)): \( x\bar{y} = 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 \)). - Не монотонна (\( 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 f_4 & - & - & + & - & + \\ \hline \end{array} \] Система является базисом, если она полна (содержит функции вне каждого класса), но при удалении любой функции полнота теряется. Проверка полноты подмножеств: Класс \( M \) не содержит ни одной функции из списка, значит любое подмножество не принадлежит \( M \). Чтобы не принадлежать \( T_0 \), нужно взять \( f_2 \) или \( f_4 \). Чтобы не принадлежать \( T_1 \), нужно взять \( f_1, f_3 \) или \( f_4 \). Чтобы не принадлежать \( S \), нужно взять \( f_1, f_2 \) или \( f_3 \). Чтобы не принадлежать \( L \), нужно взять \( f_1 \) или \( f_3 \). Возможные базисы: 1. \( \{f_1, f_2\} \): - Не в \( T_0 \) (из-за \( f_2 \)) - Не в \( T_1 \) (из-за \( f_1 \)) - Не в \( S \) (обе) - Не в \( M \) (обе) - Не в \( L \) (из-за \( f_1 \)) Это базис, так как обе функции необходимы. 2. \( \{f_1, f_4\} \): - Не в \( T_0 \) (из-за \( f_4 \)) - Не в \( T_1 \) (обе) - Не в \( S \) (из-за \( f_1 \)) - Не в \( M \) (обе) - Не в \( L \) (из-за \( f_1 \)) Это базис. 3. \( \{f_2, f_3\} \): - Не в \( T_0 \) (из-за \( f_2 \)) - Не в \( T_1 \) (из-за \( f_3 \)) - Не в \( S \) (обе) - Не в \( M \) (обе) - Не в \( L \) (из-за \( f_3 \)) Это базис. 4. \( \{f_3, f_4\} \): - Не в \( T_0 \) (из-за \( f_4 \)) - Не в \( T_1 \) (обе) - Не в \( S \) (из-за \( f_3 \)) - Не в \( M \) (обе) - Не в \( L \) (из-за \( f_3 \)) Это базис. Ответ: Базисами являются пары функций \( \{xy \oplus z, x \oplus y \oplus 1\} \), \( \{xy \oplus z, \bar{x}\} \), \( \{x\bar{y}, x \oplus y \oplus 1\} \), \( \{x\bar{y}, \bar{x}\} \).