Условие:
Дана система функций \{x ∧ y, 0\}. Выберите функцию, при добавлении которой в систему, получается базис.
эквивалентность
импликация
отрицание
штрих Шеффера
Решение:
Мы хотим построить базис (функционально полный набор булевых функций) из уже имеющейся системы {x ∧ y, 0} (то есть функции конъюнкции и нулевой константы) при добавлении одной дополнительной функции.
Основная идея такова. Известно, что для булевой функции ключевым моментом является наличие операции, которая даёт возможность получить отрицание (комплемент). Действительно, если добавить отрицание, то с помощью него и уже имеющихся констант и конъюнкции можно выразить, например, операцию дизъюнкции по формуле x ∨ y = ¬(¬x ∧ ¬y) и, таким образом, получить все булевые функции. То есть набор {...