37
правок
Изменения
Нет описания правки
==Полнота стандартного базиса==
{{Теорема|id = theor1Утверждение
|statement = Стандартный базис является полной системой булевых функций
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]].
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex>
Следовательно, стандартный базис не является базисом ''(забавно)''избыточным, так как базисами являются подмножества системы:
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)
==Теорема о максимальном числе функций в базисе==
{{Теорема
|statement = Максимально возможное число булевых функций в базисе — четыре
|proof = Очевидно, что число булевых функций в базисе не превышает число [[Полные системы функций. Теорема Поста о полной системе функций|классов Поста]]. Попробуем ограничить базис четырьмя булевыми функциями. В базисе обязательно найдётся функция
<tex> f(x_1, x_2, \ldots, x_n) </tex>, которая не сохраняет ноль, т.е. <tex> f(0, 0, \ldots, 0) = 1 </tex>. Тогда возможны два случая:
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу.
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная.
В любом случае, функция <tex>f</tex> будет не принадлежать двум классам Поста.
}}
==Источники==
