37
правок
Изменения
→Теоремы о числе функций в базисе
{{Теорема
|statement = Максимально возможное число булевых функций в базисе — четыре.
|proof = Рассмотрим произвольный безызбыточный базис <tex> X \subseteq P_2</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex>
{{Теорема
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X \subseteq P_2</tex>, что <tex>\left | X \right | = k</tex>.
|proof=Приведём примеры базисов для каждого <tex>k</tex>:
