==Формулировка теоремыПолные системы функций =={{Определение|definition=Если любая [[Определение булевой функции|булева функция]], являющаяся [[Суперпозиции|суперпозицией]] функций некоторого множества, принадлежит этому множеству, то такое множество называют '''замкнутым''' (англ. ''closed set'').}}
Система {{Определение|definition='''Замыканием''' (англ. ''сlosure'') множества функций называется такое подмножество всех булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном что любую из классов <math>~S,M,L,T_0,T_1</math>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функцияэтих функций можно выразить через функции исходного множества.}}
{{Определение|id==Доказательство =def1|definition=Множество булевых функций называется '''полной системой'I.''(англ. ' Докажем прямую теорему'complete set''), если замыкание этого множества совпадает с множеством всех функций.'''}}
Предположим, что {{Определение|definition=Полная система функций называется '''Fбезызбыточной''' не содержит функцию, обладающую одним из перечисленных выше свойств, но тогда мы не сможем через функции, входящие в ''(англ. 'F'irredundant functions'' выразить функции, обладающие этим свойством), и следовательно '''F''' не будет если она перестает быть полной системой функций, что противоречит условию, следовательно '''F''' должна содержать все вышеперечисленные функции'''при исключении из неё любого элемента.'''}}
'''IIАмериканский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций.''' Докажем обратную теорему'''Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:* функции, сохраняющие константу <Tex>T_0</Tex> и <Tex>T_1</Tex>,* самодвойственныые функции <Tex>S</Tex>,* монотонные функции <Tex>M</Tex>,* линейные функции <Tex>L</Tex>.'''
У нас есть 5 == Замкнутые классы булевых функций: несохраняющая 1 - ==Класс функций сохраняющих ноль <mathtex>f_1T_0</mathtex>. {{Определение|id = save0|definition=Говорят, что функция '''сохраняет ноль''', несохраняющая 0 - если <math>f_0</mathtex>f(0, несамодвойственная - <math>f_s</math>0, немонотонная - <math>f_m</math>\ldots, нелинейная - <math>f_l0) = 0</mathtex>'''.'''}}
Возьмем функцию, несохраняющую 0 - <math>f_0</math>'''.''' <math>f_0</math>(0) = 1'''.''' <math>f_0</math>(1) может принимать два значения:
а) Класс функций сохраняющих единицу <mathtex>f_0T_1</mathtex>(1) . {{Определение|id = save1|definition= 1Говорят, что функция '''сохраняет единицу''', тогда <math>f_0если </mathtex>f(x1, x1, x\ldots, ..., x1) = <math>~1</mathtex>'''.'''}}
б) <math>f_0</math>(1) = 0, тогда <math>f_0</math>(x, x, x, ..., x) = ¬x'''.'''
Возьмем функцию, несохраняющую 1 - Класс самодвойственных функций <mathtex>f_1S</mathtex>. {{Определение|id = selfDual|definition=Говорят, что функция '''самодвойственна''' (англ. ''self-dual''), если <math>f_1</mathtex>f(1\overline{x_1},\ldots,\overline{x_n}) = 0. <math>f_1\overline{f(x_1,\ldots,x_n)}</mathtex>(0) может принимать два . Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения:.}}
а) Класс монотонных функций <mathtex>f_1M</mathtex>.{{Определение|id = monotone|definition=Говорят, что функция '''монотонна''' (0англ. ''monotonic function'') = 0, тогда если <math>f_1</mathtex>\forall i (a_i \leqslant b_i) \Rightarrow f(xa_1, x\ldots, xa_n)\leqslant f(b_1, ...\ldots, xb_n) = <math>~0</mathtex>'''.'''}}
бКласс линейных функций <tex>L</tex>.{{Определение|id = linear|definition=Говорят, что функция '''линейна''' (англ. ''linear function'') , если существуют такие <mathtex>f_1a_0, a_1, a_2, \ldots, a_n</mathtex>(, где <tex>a_i \in \{0) , 1\}, \forall i= \overline{1, тогда n}<math/tex>f_1, что для любых <tex>x_1, x_2, \ldots, x_n</mathtex> имеет место равенство::<tex>f(xx_1, xx_2, x\ldots, ..., xx_n) = ¬x'''a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\ldots\oplus a_n\cdot x_n</tex>.}}Количество линейных функций от <tex>n</tex> переменных равно <tex>~2^{n+1}</tex>.'''
Возможны 4 варианта:Функция является линейной тогда, и только тогда, когда в ее [[Полином_Жегалкина|полиноме Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].
'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию == Формулировка и доказательство критерия Поста =={{Теорема|statement=Набор булевых функций <mathtex>f_sK</mathtex>является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
По определению найдется такой вектор <math>x_0</math>, что <math>f_s</math>(<math>x_0</math>) |proof= <math>f_s</math>(¬<math>x_0</math>). <math>x_0</math> = (<math>x_{01}, x_{02}, ..., x_{0k}</math>)'''.'''
Возьмем <math>f_s</math>(<math>x^{x_{01}}, x^{x_{02}}, ===== Необходимость..., x^{x_{0k}}</math>), где <math>x^{x_{0i}}</math> = x, при <math>x_{0i}</math> = 1 и <math>x^{x_{0i}}</math> = ¬x, при <math>x_{0i}</math> = 0'''.'''=
Нетрудно заметитьЗаметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора <mathtex>f_sK</math>(0) = <math>f_s</math>(1) =tex> входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор <mathtex>f_sK</mathtex> = '''const.'''Таким образом мы получили одну из констант'''не мог бы быть полным.'''
'''2'''===== Достаточность. =====Докажем, что если набор <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<math/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</mathtex>). '''¬'''Тогда <mathtex>~f_1(0)</mathtex> может принимать два значения:## <tex>f_1(0) = 0</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = 0<math/tex>~.## <tex>f_1(0) = 1</mathtex>, тогда <tex>f_1(x, x, x, \ldots, x) = \lnot x</tex>'''.'''
'''3''')Мы получили '''НЕ''' и <math>~1</math>. '''¬'''<math>~1</math> = <math>~0</math>'''.'Таким образом, возможны четыре варианта:''
'''4''')* Мы получили функцию <tex> \neg </tex>. Используем несамодвойственную функцию <tex>f_s</tex>. По определению, найдется такой вектор <mathtex>~1x_0</mathtex> и , что <mathtex>~0f_s(x_0) = f_s(\lnot x_0)</tex>. Где <tex>x_0 = (x_{01}, x_{02}, \ldots, x_{0k})</mathtex>'''.'''
Рассмотрим немонотонную функцию <mathtex>f_m</math>. Существуют такие <math>x_1, x_2, ..., x_n</math>, что <math>f_mf_s(x_1, x_2, ...x^{x_{01}}, x^{x_{i-102}}, 0\ldots, x^{x_{i+10k}}, ..., x_n)</mathtex> = 1, где либо <mathtex>f_m(x_1, x_2, ..., x^{x_{i-10i}, 1, x_{i+1}, ..., x_n)= x</mathtex> = 0, зафиксируем все при <mathtex>x_1, x_2, ..., x_nx_{0i} = 1</mathtex>, тогда . Либо <mathtex>f_m(x_1, x_2, ..., x^{x_{i-10i}}, = \lnot x</tex>, при <tex>x_{i+10i}, .. = 0 </tex>.Нетрудно заметить, x_nчто <tex>f_s(0)= f_s(1) \Rightarrow f_s = \operatorname {const}</mathtex> = ¬x'''.'''Таким образом мы получили одну из констант.
В итоге мы *Мы получили <tex> \neg </tex> и <tex>0 \Rightarrow</tex> имеем три функции: '''НЕ'''константу, равную <mathtex>~1</tex>, поскольку <tex>\lnot 0= 1</mathtex>.*Мы получили <tex> \neg </tex> и <tex>1 \Rightarrow</tex> имеем константу, равную <tex>0</tex>, поскольку <tex>\lnot 1 = 0<math/tex>.*Мы получили <tex>~1</mathtex> и <tex>0</tex>'''.'''
Используем нелинейную Рассмотрим немонотонную функцию <mathtex>f_lf_m</mathtex>'''.''' Среди нелинейных членов Существуют такие <mathtex>f_lx_1, x_2, \ldots, x_n</mathtex>, выберем тотчто <tex>f_m(x_1, в котором минимальное количество элементовx_2, все элементы \ldots, кроме двухx_{i-1}, в этом члене 0 , сделаем равными x_{i+1}, \ldots, оставшиеся 2 назавем <math>x_1x_n) = 1</mathtex> и , <mathtex>f_m(x_1, x_2</math>, а все элементы \ldots, x_{i-1}, 1 , x_{i+1}, не входящие в данный член \ldots, сделаем равными x_n) = 0'''.''' Тогда <math>f_l</mathtex> = , зафиксируем все <mathtex>x_1</math>^<math>, x_2, \ldots, x_n</mathtex> ⊕ [, тогда <mathtex>f_m(x_1</math>] ⊕ [<math>, x_2</math>] ⊕ [<math>~, \ldots, x_{i-1}, x, x_{i+1}, \ldots, x_n)= \lnot x</mathtex>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''
Рассмотрим несколько вариантов''В итоге имеем три функции:'' <tex> \neg </tex>, <tex>0</tex>, <tex>1</tex>.
1) Присутствует член Используем нелинейную функцию <mathtex>~1f_l</mathtex>. Возьмем отрицание от Среди нелинейных членов <mathtex>f_l</mathtex> (ее представления в виде [[Полином Жегалкина|полинома Жегалкина]]), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем <tex>x_1</tex> и <tex>x_2</tex>. Все элементы, не входящие в данный член , примем равными нулю. Тогда эта функция будет представима в виде <mathtex>g_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1]</mathtex> уберется''', где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).'''
2) Присутствуют 3 члена, без <math>~1</math>: <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ <math>x_1</math> ⊕ <math>x_2</math>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'Рассмотрим несколько вариантов:''
3) # Присутствует член <tex>\oplus ~1</tex>. Возьмем отрицание от <tex>g_l</tex> и член <tex>\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>.# Присутствуют 2 два члена, без <mathtex>\oplus ~1</mathtex>. Посторив Построив две таблицы истинности, для двух различных вариантов, видимзаметим, что в обоих случаях функция истинна только в одной точке =, следовательно, СДНФ функции <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>.# Присутствует один член. Выразим <tex> \wedge </tex> через '''НЕ''' <tex> \neg </tex> и <mathtex>f_lg_l</mathtex>аналогично пункту 3.
4) Присутствует 1 членВ итоге получим функцию<tex> \neg </tex>, а также либо функцию <tex> \wedge </tex>, либо функцию <tex> \vee </tex>. Выразим '''И'''Поскольку функцию <tex> \wedge </tex> можно выразить через <tex> \vee </tex> и <tex> \neg </tex>, а функцию <tex> \vee </tex> через '''НЕ''' <tex> \wedge </tex> и <mathtex> \neg </tex>, то мы получили базис <tex> \wedge </tex>, <tex> \vee </tex>, <tex> \neg </tex>. Любую булеву функцию, не равную тождественному нулю, можно представить в форме [[СДНФ]], то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде <tex>f_lx \land \lnot x</mathtex>.
Получается, что у нас есть функция '''НЕ'''Значит, а также либо функция '''И'''полученные функции образуют полную систему, либо функция '''ИЛИ''', но '''НЕ''' образует базис и поскольку с той и с другой функциямиих помощью можно выразить любую булеву функцию. Из того, что через функции '''F''' можно выразить базис, этого следует, что '''F''' K {{--- }} полная система функций, что и требовалось доказать.''}} == Примеры ==Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</tex>. В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать [[Определение_булевой_функции#.D0.91.D0.B8.D0.BD.D0.B0.D1.80.D0.BD.D1.8B.D0.B5_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8|штрих Шеффера]] или [[Определение_булевой_функции#.D0.91.D0.B8.D0.BD.D0.B0.D1.80.D0.BD.D1.8B.D0.B5_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8|стрелку Пирса]]. Широко известны такие полные системы булевых функций:* <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 Википедия — Критерий Поста]* [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D1%8B%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%8B_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D1%8B%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9 Википедия — Замкнутые классы булевых функций]* Образовательный сайт [http://mini-soft.ru/nstu/diskr/7_.php MiniSoft]* [http://en.wikipedia.org/wiki/Post%27s_lattice Post's lattice]* [http://www.mielt.ru/dir/cat14/subj266/file299/view1397.'''html Лекции по дискретной математике] [[Категория: Дискретная математика и алгоритмы]][[Категория: Булевы функции]]
