==Формулировка теоремыПолные системы функций =={{Определение|definition=Если любая [[Определение булевой функции|булева функция]], являющаяся [[Суперпозиции|суперпозицией]] функций некоторого множества, принадлежит этому множеству, то такое множество называют '''замкнутым''' (англ. ''closed set'').}}
Система булевых {{Определение|definition='''Замыканием''' (англ. ''сlosure'') множества функций называется минимальное по включению замкнутое подмножество всех функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <math>~S,M,L,T_0,T_1</math>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функциясодержащее данное множество функций.}}
{{Определение|id==Доказательство =def1|definition=* ЗаметимМножество булевых функций называется '''полной системой''' (англ. ''complete set''), что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полнымэтого множества совпадает с множеством всех функций.}}
* Докажем достаточность этого утверждения.{{Определение|definition=У нас есть 5 Полная система функций: несохраняющая 1 - <math>f_1</math>, несохраняющая 0 - <math>f_0</math>, несамодвойственная - <math>f_s</math>, немонотонная - <math>f_m</math>, нелинейная - <math>f_l</math>называется '''безызбыточной'''(англ.''irredundant functions''), если она перестает быть полной при исключении из неё любого элемента.}}
Возьмем функциюАмериканский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:* функции, несохраняющую 0 - сохраняющие константу <Tex>T_0</Tex> и <mathTex>f_0T_1</mathTex>'''.''' ,* самодвойственныые функции <Tex>S</Tex>,* монотонные функции <mathTex>f_0M</mathTex>(0) = 1'''.''' ,* линейные функции <mathTex>f_0L</mathTex>(1) может принимать два значения:.
а) == Замкнутые классы булевых функций ==Класс функций сохраняющих ноль <mathtex>f_0T_0</mathtex>(1) . {{Определение|id = save0|definition= 1Говорят, что функция '''сохраняет ноль''', тогда если <math>f_0</mathtex>f(x, x0, x0, ...\ldots, x0) = <math>~10</mathtex>'''.'''}}
б) <math>f_0</math>(1) = 0, тогда <math>f_0</math>(x, x, x, ..., x) = ¬x'''.'''
Возьмем функцию, несохраняющую 1 - Класс функций сохраняющих единицу <mathtex>f_1T_1</mathtex>. {{Определение|id = save1|definition=Говорят, что функция '''сохраняет единицу''', если <math>f_1</mathtex>f(1, 1, \ldots, 1) = 0. <math>f_11</mathtex>(0) может принимать два значения:.}}
а) <math>f_1</math>(0) = 0, тогда <math>f_1</math>(x, x, x, ..., x) = <math>~0</math>'''.'''
б) Класс самодвойственных функций <mathtex>f_1S</mathtex>.{{Определение|id = selfDual|definition=Говорят, что функция '''самодвойственна''' (0англ. ''self-dual'') = 1, тогда если <math>f_1</mathtex>f(x\overline{x_1}, x\ldots, x\overline{x_n})=\overline{f(x_1, \ldots,x_n)}</tex>...Иными словами, функция называется самодвойственной, x) = ¬x'''если на противоположных наборах она принимает противоположные значения.''' }}
Возможны 4 варианта:Класс монотонных функций <tex>M</tex>.{{Определение|id = monotone|definition=Говорят, что функция '''монотонна''' (англ. ''monotonic function'') , если <tex>\forall i (a_i \leqslant b_i) \Rightarrow f(a_1,\ldots,a_n)\leqslant f(b_1,\ldots,b_n)</tex>.}}
Класс линейных функций <tex>L</tex>.{{Определение|id = linear|definition=Говорят, что функция '''1линейна''') Мы получили функцию (англ. '''НЕ'linear function''), если существуют такие <tex>a_0, a_1, a_2, \ldots, a_n</tex>, где <tex>a_i \in \{0, 1\}, \forall i=\overline{1,n}</tex>, что для любых <tex>x_1, x_2, \ldots, x_n</tex> имеет место равенство::<tex>f(x_1, x_2, \ldots, x_n) = 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<math/tex>f_sпеременных равно <tex>~2^{n+1}</mathtex>.
По определению найдется такой вектор <math>x_0</math>Функция является линейной тогда, что <math>f_s</math>(<math>x_0</math>) = <math>f_s</math>(¬<math>x_0</math>). <math>x_0</math> = (<math>x_{01}и только тогда, x_{02}когда в ее [[Полином_Жегалкина|полиноме Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной.Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].., x_{0k}</math>)'''.'''
Возьмем == Формулировка и доказательство критерия Поста =={{Теорема|statement=Набор булевых функций <mathtex>f_sK</mathtex>(является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <mathtex>x^{x_{01}}S,M, x^{x_{02}}L, ...T_0, x^{x_{0k}}T_1 </mathtex>), где <math>x^{x_{0i}}</math> = xиными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, при <math>x_{0i}</math> = 1 хотя бы одна немонотонная функция и <math>x^{x_{0i}}</math> = ¬x, при <math>x_{0i}</math> = 0'''хотя бы одна нелинейная функция.'''
Нетрудно заметить, что <math>f_s</math>(0) |proof= <math>f_s</math>(1) => <math>f_s</math> = '''const.'''Таким образом мы получили одну из констант'''.'''
'''2''')Мы получили '''НЕ''' и <math>~0</math>===== Необходимость. '''¬'''<math>~0</math> = <math>~1</math>'''.'''====
'''3''')Мы получили '''НЕ''' и Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора <mathtex>~1K</mathtex>. '''¬'''<math>~1</math> = входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор <mathtex>~0K</mathtex>'''не мог бы быть полным.'''
'''4'''===== Достаточность. =====Докажем, что если набор <tex>K</tex> не содержится полностью ни в одном из данных классов, то он является полным.# Рассмотрим функцию, не сохраняющую ноль {{---}} <tex>f_0</tex> (то есть функцию, для которой <tex>f_0(0) = 1</tex>). Тогда <tex> f_0(1)Мы получили <math/tex> может принимать два значения:## <tex>~f_0(1) = 1</mathtex> и , тогда <mathtex>~f_0(x, x, x, \ldots, x) = 1</tex>.## <tex>f_0(1) = 0</mathtex>, тогда <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>'''.'''
Рассмотрим немонотонную функцию <math>f_m</math>. Существуют такие <math>x_1, x_2, ..., x_n</math>, что <math>f_m(x_1, x_2, ..., x_{i-1}, 0, x_{i+1}, ..., x_n)</math> = 1, <math>f_m(x_1, x_2, ..., x_{i-1}, 1, x_{i+1}, ..., x_n)</math> = 0, зафиксируем все <math>x_1, x_2, ..., x_n</math>, тогда <math>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)</math> = ¬x'''.'Таким образом, возможны четыре варианта:''
В итоге мы имеем три функции: '''НЕ'''* Мы получили функцию <tex> \neg </tex>. Используем несамодвойственную функцию <tex>f_s</tex>. По определению, найдется такой вектор <mathtex>~0x_0</mathtex>, что <tex>f_s(x_0) = f_s(\lnot x_0)</tex>. Где <mathtex>~1x_0 = (x_{01}, x_{02}, \ldots, x_{0k})</mathtex>'''.'''
Используем нелинейную функцию Рассмотрим <math>f_l</math>'''.''' Среди нелинейных членов <math>f_l</mathtex>f_s(x^{x_{01}}, выберем тотx^{x_{02}}, в котором минимальное количество элементов\ldots, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <math>x_1x^{x_{0k}})</mathtex> и , где либо <mathtex>x_2x^{x_{0i}} = x</mathtex>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда при <mathtex>f_lx_{0i} = 1</mathtex> = . Либо <math>x_1</mathtex>x^<math>x_2{x_{0i}} = \lnot x</mathtex> ⊕ [, при <mathtex>x_1x_{0i} = 0 </mathtex>] ⊕ [. Нетрудно заметить, что <mathtex>x_2</math>] ⊕ [<math>~f_s(0) = f_s(1) \Rightarrow f_s = \operatorname {const}</mathtex>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.''' Таким образом мы получили одну из констант.
Рассмотрим несколько вариантов:*Мы получили <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>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>, <mathtex>~f_m(x_1, x_2, \ldots, x_{i-1}, 1 , x_{i+1}, \ldots, x_n) = 0</mathtex>. Возьмем отрицание от , зафиксируем все <mathtex>f_lx_1, x_2, \ldots, x_n</mathtex> и член , тогда <mathtex>~f_m(x_1, x_2, \ldots, x_{i-1}, x, x_{i+1}, \ldots, x_n)= \lnot x</mathtex> уберется'''.'''
2) Присутствуют 3 члена, без <math>~1</math>''В итоге имеем три функции: '' <mathtex>f_l\neg </mathtex> = , <mathtex>x_10</mathtex>^, <mathtex>x_2</math> ⊕ <math>x_1</math> ⊕ <math>x_21</mathtex>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''
3) Присутствуют 2 члена, без Используем нелинейную функцию <mathtex>~1f_l</mathtex>. Посторив две таблицы истинностиСреди нелинейных членов <tex>f_l</tex> (ее представления в виде [[Полином Жегалкина|полинома Жегалкина]]), для выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух различных вариантовв этом члене приравняем единице, видимоставшиеся два назовем <tex>x_1</tex> и <tex>x_2</tex>. Все элементы, что не входящие в обоих случаях данный член, примем равными нулю. Тогда эта функция истинна только будет представима в одной точке виде <tex>g_l =x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1]</tex> СДНФ будет состоять только из одного члена, а если это такгде в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, то не составляет труда выразить '''И'''входящий в выбранный член, через '''НЕ''' и <math>f_l</math>так как в выбранном члене минимальное число элементов).
4) Присутствует 1 член. Выразим ''Рассмотрим несколько вариантов:'И''', через '''НЕ''' и <math>f_l</math>.
Получается# Присутствует член <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>.# Присутствуют два члена, без <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>.# Присутствует один член. Выразим <tex> \wedge </tex> через <tex> \neg </tex> и <tex>g_l</tex> аналогично пункту 3. В итоге получим функцию<tex> \neg </tex>, а также либо функция '''И'''функцию <tex> \wedge </tex>, либо функцию <tex> \vee </tex>. Поскольку функцию <tex> \wedge </tex> можно выразить через <tex> \vee </tex> и <tex> \neg </tex>, а функцию <tex> \vee </tex> через <tex> \wedge </tex> и <tex> \neg </tex>, то мы получили базис <tex> \wedge </tex>, <tex> \vee </tex>, <tex> \neg </tex>. Любую булеву функцию, не равную тождественному нулю, можно представить в форме [[СДНФ]], то есть выразить в данном базисе. Если же функция '''ИЛИ'''равна тождественному нулю, но '''НЕ'то ее можно представить в виде <tex>x \land \lnot x</tex>. '' образует базис и с той и с другой функциями. Из тогоЗначит, что через полученные функции '''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 Лекции по дискретной математике] [[Категория: Дискретная математика и алгоритмы]][[Категория: Булевы функции]]
