Функционально-полные системы логических функций

Как уже было отмечено ранее, логическая функция может быть задана таблично, геометрически и аналитически. Первые два способа задают функцию непосредственно, как соответствие между двоичными наборами и значениями функции на этих наборах. Так может быть задана любая функция. Однако, оба способа громоздки. Формула - гораздо более компактный способ задания функции, однако, она задает функцию через другие функции. Поэтому, для любой системы функций возникает естественный вопрос: всякая ли логическая функция представима формулой над ? Если это возможно, то называется функционально полной системой логических функций. Функционально полная система называется базисом, если при удалении хотя бы одной функции полнота теряется.

Поиск базисов имеет большoе практическое значение, так как, имея элементы, реализующие функции какого-либо базиса, можно построить логическую схему, реализующую любую логическую функцию.