Определение и доказательство базисов в алгебре логики

Для того чтобы доказать, что выбранные подмножества являются базисами, необходимо подтвердить их полноту по теореме Поста. Система функций является полной, если она содержит хотя бы одну функцию, не входящую в каждый из пяти замкнутых классов: \( T_0, T_1, S, M, L \). Ниже приведены логические обоснования (формулы проверки) для каждого выделенного базиса. 1. Базис \( B_1 = \{f_1, f_2\} = \{xy \oplus z, x \oplus y \oplus 1\} \) \[ f_1 \notin T_1, f_1 \notin S, f_1 \notin M, f_1 \notin L \] \[ f_2 \notin T_0, f_2 \notin S, f_2 \notin M \] Проверка по классам: - \( T_0 \): \( f_2(0,0) = 1 \neq 0 \) (есть функция вне \( T_0 \)) - \( T_1 \): \( f_1(1,1,1) = 0 \neq 1 \) (есть функция вне \( T_1 \)) - \( S \): \( f_1 \) не самодвойственна - \( M \): \( f_1(1,1,0)=1 > f_1(1,1,1)=0 \) (не монотонна) - \( L \): \( f_1 \) содержит нелинейный член \( xy \) 2. Базис \( B_2 = \{f_1, f_4\} = \{xy \oplus z, \bar{x}\} \) \[ f_1 \notin T_1, f_1 \notin S, f_1 \notin M, f_1 \notin L \] \[ f_4 \notin T_0, f_4 \notin T_1, f_4 \notin M \] Проверка по классам: - \( T_0 \): \( f_4(0) = 1 \) - \( T_1 \): \( f_4(1) = 0 \) - \( S \): \( f_1 \notin S \) - \( M \): \( f_4(0) > f_4(1) \) - \( L \): \( f_1 \notin L \) 3. Базис \( B_3 = \{f_2, f_3\} = \{x \oplus y \oplus 1, x\bar{y}\} \) \[ f_2 \notin T_0, f_2 \notin S, f_2 \notin M \] \[ f_3 \notin T_1, f_3 \notin S, f_3 \notin M, f_3 \notin L \] Проверка по классам: - \( T_0 \): \( f_2(0,0) = 1 \) - \( T_1 \): \( f_3(1,1) = 0 \) - \( S \): \( f_3 \notin S \) - \( M \): \( f_3(1,0)=1 > f_3(1,1)=0 \) - \( L \): \( f_3 = x(y \oplus 1) = xy \oplus x \) (нелинейна) 4. Базис \( B_4 = \{f_3, f_4\} = \{x\bar{y}, \bar{x}\} \) \[ f_3 \notin T_1, f_3 \notin S, f_3 \notin M, f_3 \notin L \] \[ f_4 \notin T_0, f_4 \notin T_1, f_4 \notin M \] Проверка по классам: - \( T_0 \): \( f_4(0) = 1 \) - \( T_1 \): \( f_4(1) = 0 \) - \( S \): \( f_3 \notin S \) - \( M \): \( f_4 \) не монотонна - \( L \): \( f_3 \notin L \) Резюме: Во всех четырех случаях удаление любой функции из пары приводит к потере полноты (например, если убрать \( f_1 \) из первой пары, оставшаяся \( f_2 \) будет линейной, и мы не сможем выразить нелинейные функции). Следовательно, данные пары являются минимальными полными системами, то есть базисами.