74
правки
Изменения
Поправил определение замыкания
{{Определение
|definition=
Если любая [[Определение булевой функции|булева функция]], являющаяся [[Суперпозиции|суперпозицией]] функций некоторого множества , принадлежит этому множеству, то такое множество называют '''замкнутым'''(англ. ''closed set'').}}
{{Определение
|definition=
'''Замыканием''' (англ. ''сlosure'') множества функций называется такое минимальное по включению замкнутое подмножество всех булевых функций, что любую из этих содержащее данное множество функций можно выразить через функции исходного множества.}}
{{Определение
|id=def1
|definition=
Множество булевых функций называется '''полной системой'''(англ. ''complete set''), если замыкание этого множества совпадает с множеством всех функций.}}
{{Определение
|definition=
Полная система функций называется '''безызбыточной'''(англ. ''irredundant functions''), если она перестает быть полной при исключении из неё любого элемента.
}}
Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
* Функциифункции, сохраняющие константу <mathTex>T_0</mathTex> и <mathTex>T_1</mathTex>;,* Самодвойственные самодвойственныые функции <mathTex>S</mathTex>;,* Монотонные монотонные функции <mathTex>M</mathTex>;,* Линейные линейные функции <mathTex>L</mathTex>.
== Замкнутые классы булевых функций ==
Класс функций сохраняющих ноль <tex>T_0</tex>.
{{Определение
|id = save0|definition=Говорят, что функция '''сохраняет ноль''', если <tex>f(0, 0, \dotsldots, 0) = 0</tex>.
}}
Класс функций сохраняющих единицу <tex>T_1</tex>.
{{Определение
|id = save1|definition=Говорят, что функция '''сохраняет одинединицу''', если <tex>f(1, 1, \dotsldots, 1) = 1</tex>.
}}
Класс самодвойственных функций <tex>S</tex>.
{{Определение
|id = selfDual|definition=Говорят, что функция '''самодвойственна'''(англ. ''self-dual''), если <tex>f(\overline{x_1},\dotsldots,\overline{x_n})=\overline{f(x_1,\dotsldots,x_n)}</tex>. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.
}}
Класс монотонных функций <tex>M</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>.
}}
Класс линейных функций <tex>L</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>n</tex> переменных равно <tex>~2^{n+1}</tex>.
{{
Теорема|statement=
Набор булевых функций <tex>K </tex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, т.е. иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
|proof=
===== Достаточность. =====Докажем, что если набор <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_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>f_s(0) = f_s(1) \Rightarrow f_s = \operatorname {const}</tex>.
Таким образом мы получили одну из констант.
}}
* <tex>\left\{\land,\lor,\neg\right\}</tex> (конъюнкция, дизъюнкция, отрицание);
* <tex>\left\{\land,\oplus,1\right\}</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 Википедия — Критерий Поста]