78
правок
Изменения
→Полные системы функций
{{Определение
|definition=
Например, если <tex>A = \left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex>
'''Замыканием''' множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.}}
{{Определение
|id=def1
|definition=
Множество <tex>A</tex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}}
[[Теорема Поста о полной системе функций|Критерий Поста]] формулирует необходимое и достаточное условие полноты системы булевых функций:<br/> '''Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</tex>.'''<br />
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
