37
правок
Изменения
→Теорема о максимальном числе функций в базисе
{{Теорема
|statement = Максимально возможное число булевых функций в базисе — четыре
|proof = ОчевидноРассмотрим произвольный базис, что в котором число булевых функций в базисе не превышает число равно числу [[Полные системы функций. Теорема Поста о полной системе функций|классов Поста]]. Попробуем ограничить базис четырьмя булевыми функциями. В базисе обязательно найдётся функция
<tex> f(x_1, x_2, \ldots, x_n) </tex>, которая не сохраняет ноль, т.е. <tex> f(0, 0, \ldots, 0) = 1 </tex>. Тогда возможны два случая:
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная.
В любом случае, функция <tex>f</tex> будет не принадлежать сразу двум классам Поста. Тогда исходный базис - избыточный, и его можно сократить до четырёх функций.
}}
