11
правок
Изменения
м
Максимально Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.
Нет описания правки
{{
Теорема|statement=
Набор булевых функций <tex>K </tex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
|proof=
===== Необходимость. =====
Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К <tex>K</tex> входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор К <tex>K</tex> не мог бы быть полным.
===== Достаточность. =====
Докажем, что если набор <tex>K</tex> не содержится полностью ни в одном из данных классов, то он является полным.# Рассмотрим функцию, не сохраняющую ноль {{---}} <tex>f_0</tex>. (то есть функцию, для которой <tex>f_0(0) = 1</tex>) . Тогда <tex>f_0(1)</tex> может принимать два значения:
## <tex>f_0(1) = 1</tex>, тогда <tex>f_0(x, x, x, \ldots, x) = 1</tex>.
## <tex>f_0(1) = 0</tex>, тогда <tex>f_0(x, x, x, \dots, x) = \neg x</tex>.
# Рассмотрим функцию, не сохраняющую один {{---}} <tex>f_1</tex>. (то есть функцию, для которой <tex>f_1(1) = 0</tex>) . Тогда <tex>f_1(0)</tex> может принимать два значения:
## <tex>f_1(0) = 0</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = 0</tex>.
## <tex>f_1(0) = 1</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = \lnot x</tex>.
* Мы получили функцию <tex> \neg </tex>.
Используем несамодвойственную функцию <tex>f_s</tex>. По определению, найдется такой вектор <tex>x_0</tex>, что <tex>f_s(x_0) = f_s(\lnot x_0)</tex>. Где <tex>x_0 = (x_{01}, x_{02}, ...\ldots, x_{0k})</tex>.
Рассмотрим <tex>f_s(x^{x_{01}}, x^{x_{02}}, \ldots, x^{x_{0k}})</tex>, где либо <tex>x^{x_{0i}} = x</tex>, при <tex>x_{0i} = 1</tex>. Либо <tex>x^{x_{0i}} = \lnot x</tex>, при <tex>x_{0i} = 0 </tex>.
Таким образом мы получили одну из констант.
*Мы получили <tex> \neg </tex> и <tex>0\Rightarrow</tex> имеем константу, равную <tex>1</tex>. , поскольку <tex>\lnot 0 = 1</tex>.*Мы получили <tex> \neg </tex> и <tex>1 \Rightarrow</tex> имеем константу, равную <tex>0</tex>. , поскольку <tex>\lnot 1 = 0</tex>.
*Мы получили <tex>1</tex> и <tex>0</tex>.
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций.
== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D1%82%D0%B5%D1%80%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0 Википедия — Критерий Поста]
