Полная система булевых функций образует базис, если исключение любой функции из этой системы превращает её в неполную систему.
Например, функция образует базис в P2, а система базисом не является, поскольку из нее можно исключить функции или и оставшаяся система останется полной. В то же время, системы и являются базисами в P2.
Максимальное число функций в базисе равно 4.
Возможные базисы во множестве всех булевых функций: Базисы из 1 функции: ; Базисы из 2-х функций: ; Базис из 3-х функций: ; Базис из 4-х функций: ;