Изменения

Если любая [[Определение булевой функции|булева функция]], являющаяся [[Суперпозиции|суперпозицией]] функций некоторого множества , принадлежит этому множеству, то такое множество называют '''замкнутым'''(англ. ''closed set'').}}

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

Множество булевых функций называется '''полной системой'''(англ. ''complete set''), если замыкание этого множества совпадает с множеством всех функций.}}

Полная система функций называется '''безызбыточной'''(англ. ''irredundant functions''), если она перестает быть полной при исключении из неё любого элемента.

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

|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\le leqslant b_i) \Rightarrow f(a_1,\dotsldots,a_n)\le 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(01) = 1</tex>, тогда <tex>f_0(x, x, x, \ldots, x) = 1</tex>. ## <tex>f_0(1) = 0</tex>, тогда <tex>f_0(x, x, x, \ldots, 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>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>. Возможны четыре варианта: 1) Мы получили функцию НЕ. Используем несамодвойственную функцию <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}, ..., 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>.

2) *Мы получили НЕ <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>.

3Рассмотрим немонотонную функцию <tex>f_m</tex>. Существуют такие <tex>x_1, x_2, \ldots, x_n</tex>, что <tex>f_m(x_1, x_2, \ldots, x_{i-1}, 0 , x_{i+1}, \ldots, x_n) Мы получили НЕ и = 1</tex>, <tex>f_m(x_1, x_2, \ldots, x_{i-1}, 1 , x_{i+1}, \ldots, x_n) = 0</tex>, зафиксируем все <tex>x_1, x_2, \ldots, x_n</tex>. , тогда <tex>f_m(x_1, x_2, \lnot ldots, x_{i-1}, x, x_{i+1 }, \ldots, x_n)= 0\lnot x</tex>.

4) Мы получили ''В итоге имеем три функции:'' <tex>1\neg </tex> и , <tex>0</tex>, <tex>1</tex>.

Рассмотрим немонотонную Используем нелинейную функцию <tex>f_mf_l</tex>. Существуют такие Среди нелинейных членов <tex>x_1, x_2, \ldots, x_nf_l</tex>(ее представления в виде [[Полином Жегалкина|полинома Жегалкина]]), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, что оставшиеся два назовем <tex>f_m(x_1, x_2, \ldots, x_{i-1}, 0 , x_{i+1}, \ldots, x_n) = 1</tex>, и <tex>f_m(x_1, x_2, \ldots, x_{i-1}, 1 , x_{i+1}, \ldots, x_n) = 0</tex>. Все элементы, зафиксируем все не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде <tex>g_l = x_1, \land x_2 [ \oplus x_1] [\oplus x_2, ][ \ldots, x_noplus ~1]</tex>, тогда <tex>f_mгде в квадратных скобках указаны члены, которые могут и не присутствовать (x_1, x_2остальные слагаемые будут равны нулю, \ldotsпоскольку в них есть как минимум один аргумент, x_{i-1}не входящий в выбранный член, x, x_{i+1}, \ldots, x_nтак как в выбранном члене минимальное число элементов)= \lnot x</tex>.

В итоге имеем три функции''Рассмотрим несколько вариантов: НЕ, <tex>0</tex>, <tex>1</tex>.''

Используем нелинейную функцию # Присутствует член <tex>f_l\oplus ~1</tex>. Среди нелинейных членов Возьмем отрицание от <tex>g_l</tex> и член <tex>f_l\oplus ~1</tex> (ее представления в виде [[Полином Жегалкина|полинома Жегалкина]])исчезнет.# Присутствуют три члена, выберем тотбез <tex>\oplus ~1</tex>: <tex>g_l= x_1 \land x_2 \oplus x_1 \oplus x_2</tex>. Составив таблицу истинности для этой функции нетрудно заметить, в котором минимальное количество элементовчто она эквивалентна функции <tex> \vee </tex>. Все аргументы# Присутствуют два члена, кроме без <tex>\oplus ~1</tex>. Построив две таблицы истинности для двухразличных вариантов, заметим, что в этом членеобоих случаях функция истинна только в одной точке, приравняем единицеследовательно, оставшиеся два назовем СДНФ функции <tex>g_l</tex> будет состоять только из одного члена. Если это так, то не составляет труда выразить <tex> \wedge </tex> через <tex>x_1\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 = x_1 \land x_2 ([ \oplus lnot]x_1] , [\oplus lnot]x_2], \ldots, [ \oplus ~1lnot]x_n)</tex>, где в квадратных скобках указаны члены<tex>\lnot</tex> ставится перед аргументами с номерами <tex>i_1, i_2, которые могут и не присутствовать (остальные слагаемые будут равны нулю\ldots, поскольку в них есть как минимум i_m</tex>.# Присутствует один аргумент не входящие в выбранный член, т. к. мы выбрали член, в котором минимальное число элементов)Выразим <tex> \wedge </tex> через <tex> \neg </tex> и <tex>g_l</tex> аналогично пункту 3.

В итоге получаем функцию НЕ, а также либо функцию И, либо функцию ИЛИ. Поскольку функцию И можно выразить через ИЛИ и НЕ, а функцию ИЛИ через И и НЕ, то мы получили базис И, ИЛИ, НЕ. Любую булеву функцию, не равную тождественному нулю, можно представить в форме [[СДНФ]], т. е. с помощью данного базиса. Если же функция равна тождественному нулю, то ее можно представить в виде <tex>x \land \lnot x</tex>. ''Значит, полученные функции образуют полную систему, т. к. поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K {{---}} полная система функций, что и требовалось доказать.''

Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[Полином Жегалкина|полиномов Жегалкина]]. Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы.

Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух Теорема о максимальном числе функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты.Максимально в базисе: максимально возможное число булевых функций в базисе — четыре.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и , соответственно , о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций.

== Источники информации ==