78
правок
Изменения
Нет описания правки
== Полная система функций ==
Система булевых функций называется ''полной'', если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством <math>P_2</math>.
Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:
* Функции, сохраняющие константу <math>T_0</math> и <math>T_1</math>;
* Самодвойственные функции <math>S</math>;
* Монотонные функции <math>M</math>;
* Линейные функции <math>L</math>.
Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.
== Критерий Поста ==
Критерий Поста — одна из центральных теорем в теории [[Определение булевой функции|булевых функций]], устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.
