== Полная система функций ==
{{Определение|definition=Система Американский математик Эмиль Пост сформулировал необходимое и достаточное условие [[Определение булевой Представление функцииформулой, полные системы функций|полноты системы булевых функций]] называется '''полной''', если можно построить их [[Суперпозиции|суперпозицию]], тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством <tex>P_2</tex>.}}Американский математик Эмиль Пост Для этого он ввёл в рассмотрение следующие замкнутые классы булевых функций:
* Функции, сохраняющие константу <math>T_0</math> и <math>T_1</math>;
* Самодвойственные функции <math>S</math>;
* Монотонные функции <math>M</math>;
* Линейные функции <math>L</math>.
Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.
== Замкнутые классы булевых функций ==
В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' {{---}} полная система функций, что и требовалось доказать.
}}
== Примеры полных систем булевых функций от двух переменных ==
Широко известна [[Представление функции формулой, полные системы функций|полная система функций]] <tex>\left\{\land,\lor,\neg\right\}</tex>. Однако, эта система функций не является безызбыточной, т. к. функцию <tex>\land</tex> можно выразить через <tex>\lor</tex> и <tex>\neg</tex>. Система функций <tex>\left\{\lor,\neg\right\}</tex> полная, т. к. функция <tex>\lor</tex> является несамодвойственной и нелинейной, а функция <tex>\neg</tex> не сохраняет 0, не сохраняет 1 и немонотонна. Система функций <tex>\left\{\land,\neg\right\}</tex> также является полной, т. к. функция <tex>\land</tex> является несамодвойственной и нелинейной, а функция <tex>\neg</tex> не сохраняет 0, не сохраняет 1 и немонотонна. Система функций <tex>\left\{\land,\lor,\neg\right\}</tex> используется для представления функций в [[СДНФ|СДНФ]] и [[СКНФ|СКНФ]].
Также существуют полные системы функций, состоящие только из одной функции. Это штрих Шеффера (<tex>\triangledown</tex>) и стрелка Пирса(<tex>\downarrow</tex>).
== Источники ==
