Изменения
→Полные системы функций
== Полные системы функций ==
Множество <mathtex>A</mathtex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.
[[Теорема Поста о полной системе функций|Критерий Поста]] формулирует необходимое и достаточное условие полноты системы булевых функций:<br />'''Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <mathtex>T_0</mathtex>, <mathtex>T_1</mathtex>, <mathtex>S</mathtex>, <mathtex>M</mathtex>, <mathtex>L</mathtex>.'''<br />
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
Широко известны такие полные системы булевых функций:
* <mathtex>\left\{\land,\lor,\neg\right\}</mathtex> (конъюнкция, дизъюнкция, отрицание);* <mathtex>\left\{\land,\oplus,1\right\}</mathtex> (конъюнкция, сложение по модулю 2, константа 1).
Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[полином Жегалкина|полиномов Жегалкина]].
Максимально возможное число булевых функций в базисе — 4.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему <mathtex>\left\{\oplus,1\right\}</mathtex> можно назвать базисом класса линейных функций.
== Представление функции формулой ==
Если задана какая-либо полная система функций <math>A</math>, то '''любую''' функцию можно выразить, составив формулу, содержащую только функции из множества <math>A</math>. Например, если <math>A = \left\{\land,\neg\right\}</math>, то функция <math>a \lor b</math> представляется в виде <math>\neg(\neg a \land \neg b)</math>.
