Полные системы булевых функций Базисы

• Система булевых функций называется полной, если любая булева функция представима в виде суперпозиции функций из этой системы.  

• Примеры полных систем: дизъюнкция, конъюнкция, отрицание и полином Жигалкина.  

• Система, состоящая из дизъюнкции, конъюнкции и отрицания, является полной.  

• Система, состоящая из кольцевой суммы, конъюнкции и единицы, также является полной.  

• Дизъюнкцию можно выразить через конъюнкцию и отрицание.  

• Конъюнкцию можно выразить через дизъюнкцию и отрицание.  

• Система, состоящая только из штрих-шефера, является полной.  

• Система, состоящая только из стрелки Пирса, также является полной.  

• Система булевых функций полна тогда и только тогда, когда для каждого класса Поста в системе есть функция, ему не принадлежащая.  

• Теорема Поста доказывает, что классы Поста замкнуты относительно суперпозиций.  

• Пример: проверка полноты системы функций импликация, кольцевая сумма и отрицание.  

• Рассматриваются функции отрицания, импликации и кольцевой суммы.  

• Обозначаются функции как ф от икс, ж от икс, игрек и аш.  

• Проверяется принадлежность функций классам Поста.  

• Отрицание не принадлежит классам П-ноль и П-один.  

• Функция отрицания линейна и самодвойственна.  

• Монотонность отрицания не выполняется.  

• Импликация не принадлежит классам П-ноль и П-один.  

• Функция содержит слагаемое, равное произведению всех переменных.  

• Самодвойственность и монотонность нарушены.  

• Кольцевая сумма принадлежит классам П-ноль и П-один.  

• Линейность и самодвойственность нарушены.  

• Монотонность не выполняется.  

• Базис - это минимальная полная система функций.  

• Удаление функции из базиса делает систему неполной.  

• Примеры базисов: ф и ж, ф и аш, ж и аш.  

• Любой базис состоит не более чем из четырех функций.  

• Доказательство через противоречие: функция не принадлежит классу П-ноль и принадлежит остальным классам.  

• Противоречие показывает, что базис не может состоять из пяти функций.