Изменения

'''Замыканием''' (англ. ''сlosure'') множества функций называется такое минимальное по включению замкнутое подмножество всех булевых функций, что любую из этих содержащее данное множество функций можно выразить через функции исходного множества.}}

* Функциифункции, сохраняющие константу <Tex>T_0</Tex> и <Tex>T_1</Tex>,* Самодвойственныые самодвойственныые функции <Tex>S</Tex>,* Монотонные монотонные функции <Tex>M</Tex>,* Линейные линейные функции <Tex>L</Tex>.

|id = save0|definition=Говорят, что функция '''сохраняет ноль''', если <tex>f(0, 0, \dotsldots, 0) = 0</tex>.

|id = save1|definition=Говорят, что функция '''сохраняет одинединицу''', если <tex>f(1, 1, \dotsldots, 1) = 1</tex>.

|id = selfDual|definition=Говорят, что функция '''самодвойственна''' (англ. ''self-dual''), если <tex>f(\overline{x_1},\dotsldots,\overline{x_n})=\overline{f(x_1,\dotsldots,x_n)}</tex>. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.

|id = monotone|definition=Говорят, что функция '''монотонна''' (англ. ''monotonic function'') , если <tex>\forall i (a_i \leqslant b_i) \Rightarrow f(a_1,\dotsldots,a_n)\leqslant f(b_1,\dotsldots,b_n)</tex>.

|id = linear|definition=Говорят, что функция '''линейна''' (англ. ''linear function''), если существуют такие <tex>a_0, a_1, a_2, \dotsldots, a_n</tex>, где <tex>a_i \in \{0, 1\}, \forall i=\overline{1,n}</tex>, что для любых <tex>x_1, x_2, \dotsldots, x_n</tex> имеет место равенство::<tex>f(x_1, x_2, \dotsldots, x_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\dotsldots\oplus a_n\cdot x_n</tex>.

Набор булевых функций <tex>K </tex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К <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) = 0</tex>, тогда <tex>f_0(x, x, x, \dotsldots, x) = \neg x</tex>.# Рассмотрим функцию, не сохраняющую один {{---}} <tex>f_1</tex>. (то есть функцию, для которой <tex>f_1(1) = 0</tex>) . Тогда <tex>f_1(0)</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> \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>\oplus ~1</tex>. Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции <tex>g_l</tex> будет состоять только из одного члена. Если это так, то не составляет труда выразить <tex> \wedge </tex> через <tex> \neg </tex> и <tex>g_l</tex>. Например, если функция <tex>g_l(x_1, x_2, ...\ldots, x_n)</tex> принимает истинное значение, когда аргументы c номерами <tex>i_1, i_2, ...\ldots, i_m</tex> ложны, а все остальные истины, то функцию <tex> \wedge </tex> можно выразить как <tex>g_l([\lnot]x_1, [\lnot]x_2, ...\ldots, [\lnot]x_n)</tex>, где <tex>\lnot</tex> ставится перед аргументами с номерами <tex>i_1, i_2, ...\ldots, i_m</tex>.

Максимально Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.

== См. также ==* [[Определение_булевой_функции|Булевы функции]]* [[Суперпозиции|Суперпозиции]]* [[Полином_Жегалкина|Полином Жегалкина]] == Источники информации ==