Изменения

Для Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:

|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.

'''Замечание:'''по  По [[Множества|закону де Моргана]]:

==Теорема Теоремы о максимальном числе функций в базисе==

|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> Тогда, так как <tex>X</tex> - безызбыточный базис четырьмя булевыми функциями, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> - полный, то <tex>\left | X \right | \le 5</tex> Рассмотрим <tex>f_0</tex>. В базисе обязательно найдётся функцияВозможны два случая: 1. <tex> f(x_11, x_21, \ldots, x_n1) = 0 </tex>, которая тогда функция <tex>f</tex> также не сохраняет нольединицу и немонотонная, т.е. <tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>. 2. <tex> f(01, 01, \ldots, 01) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная, т.е. <tex> f_0 = f_s </tex>. Тогда возможны два случая<tex>\left | X \right | \le 4</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>: <tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>; <tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>; <tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>; <tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>; Докажем, последняя система является базисом: <tex> 0 \notin T_1</tex>;

1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>fnotin T_0</tex> также не сохраняет единицу.;

2. <tex> f(1, 1, x\ldots, 1) = 1 </tex>, тогда функция <tex>fland y \notin L\ и\ S</tex> несамодвойственная.;

В любом случае, функция <tex>fx\oplus y\oplus z \notin M</tex> будет не принадлежать сразу двум классам Поста. Тогда исходный базис - избыточный, и его можно сократить до четырёх функций(доказывается с помощью таблицы истинности).