== Критерий Поста Полные системы функций =={{Определение|definition=Критерий Поста — одна из центральных теорем в теории булевых Если любая [[Определение булевой функции|булева функция]], являющаяся [[Суперпозиции|суперпозицией]] функцийнекоторого множества, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностьюпринадлежит этому множеству, чтобы представить любую булеву функциюто такое множество называют '''замкнутым''' (англ. Впервые сформулирован американским математиком Эмилем Постом''closed set'').}}
{{Определение|definition='''Замыканием''' (англ. ''сlosure'') множества функций называется такое подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества.}} {{Определение|id=def1|definition=Множество булевых функций называется '''полной системой''' (англ. ''complete set''), если замыкание этого множества совпадает с множеством всех функций.}} {{Определение|definition=Полная система функций называется '''безызбыточной''' (англ. ''irredundant functions''), если она перестает быть полной при исключении из неё любого элемента.}} Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:* функции, сохраняющие константу <Tex>T_0</Tex> и <Tex>T_1</Tex>,* самодвойственныые функции <Tex>S</Tex>,* монотонные функции <Tex>M</Tex>,* линейные функции <Tex>L</Tex>. == Замкнутые классы булевых функций ==Класс функций сохраняющих ноль <tex>T_0</tex>. {{Определение|id = save0|definition=Говорят, что функция '''сохраняет ноль''', если <tex>f(0, 0, \ldots, 0) = 0</tex>.}} Класс функций сохраняющих единицу <tex>T_1</tex>. {{Определение|id = save1|definition=Говорят, что функция '''сохраняет единицу''', если <tex>f(1, 1, \ldots, 1) = 1</tex>.}} Класс самодвойственных функций <tex>S</tex>.{{Определение|id = selfDual|definition=Говорят, что функция '''самодвойственна''' (англ. ''self-dual''), если <tex>f(\overline{x_1},\ldots,\overline{x_n})=\overline{f(x_1,\ldots,x_n)}</tex>. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.}} Класс монотонных функций <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=Говорят, что функция '''линейна''' (англ. ''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</tex> переменных равно <tex>~2^{n+1}</tex>. Функция является линейной тогда, и только тогда, когда в ее [[Полином_Жегалкина|полиноме Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]]. == Формулировка и доказательство критерия Поста ==
{{
Теорема|statement=
Система Набор булевых функций F <tex>K</tex> является полной полным тогда и только тогда, когда она он не содержится полностью ни в одном из классов <tex>~S,M,L,T_0,T_1</tex>, т.е. иными словами, когда в ней нем имеется хотя бы одна функция, не сохраняющая 0ноль, хотя бы одна функция, не сохраняющая 1один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
|proof=
Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полным===== Необходимость.=====
----Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора <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) = 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>.
Рассмотрим функцию, несохраняющую 0 - <tex>f_0</tex>'''.''' <tex>f_0</tex>(0) = 1'''.Таким образом, возможны четыре варианта:''' <tex>f_0</tex>(1) может принимать два значения:
а) * Мы получили функцию <tex> \neg </tex>. Используем несамодвойственную функцию <tex>f_s</tex>. По определению, найдется такой вектор <tex>f_0x_0</tex>, что <tex>f_s(1x_0) = 1, тогда f_s(\lnot x_0)</tex>f_0. Где </tex>x_0 = (xx_{01}, xx_{02}, x\ldots, ..., xx_{0k}) = <tex>~1</tex>'''.'''
бРассмотрим <tex>f_s(x^{x_{01}}, x^{x_{02}}, \ldots, x^{x_{0k}}) </tex>f_0, где либо <tex>x^{x_{0i}} = x</tex>(1) = 0, тогда при <tex>f_0x_{0i} = 1</tex>(. Либо <tex>x, ^{x_{0i}} = \lnot x</tex>, x, ..при <tex>x_{0i} = 0 </tex>.Нетрудно заметить, xчто <tex>f_s(0) = f_s(1) \Rightarrow f_s = ¬x'''\operatorname {const}</tex>.Таким образом мы получили одну из констант.'''
Рассмотрим функцию*Мы получили <tex> \neg </tex> и <tex>0 \Rightarrow</tex> имеем константу, несохраняющую равную <tex>1 - </tex>f_1, поскольку <tex>\lnot 0 = 1</tex>'''.''' *Мы получили <tex> \neg </tex> и <tex>f_11 \Rightarrow</tex>(имеем константу, равную <tex>0</tex>, поскольку <tex>\lnot 1) = 0</tex>. *Мы получили <tex>f_11</tex>(и <tex>0) может принимать два значения:</tex>.
а) Рассмотрим немонотонную функцию <tex>f_1f_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>f_1x_1, x_2, \ldots, x_n</tex>, тогда <tex>f_m(xx_1, x_2, \ldots, x_{i-1}, x, xx_{i+1}, ... \ldots, xx_n) = <tex>~0\lnot x</tex>'''.'''
б) ''В итоге имеем три функции:'' <tex>f_1\neg </tex>(, <tex>0) = 1</tex>, тогда <tex>f_11</tex>(x, x, x, ..., x) = ¬x'''.'''
Возможны 4 варианта:Используем нелинейную функцию <tex>f_l</tex>. Среди нелинейных членов <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>, где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).
''Рассмотрим несколько вариантов:'1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <tex>f_s</tex>.
По определению найдется такой вектор # Присутствует член <tex>x_0\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>f_s\vee </tex>(.# Присутствуют два члена, без <tex>\oplus ~1</tex>. Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции <tex>g_l</tex> будет состоять только из одного члена. Если это так, то не составляет труда выразить <tex> \wedge </tex> через <tex> \neg </tex> и <tex>x_0g_l</tex>. Например, если функция <tex>g_l(x_1, x_2, \ldots, x_n) = </tex> принимает истинное значение, когда аргументы c номерами <tex>f_si_1, i_2, \ldots, i_m</tex>(¬ложны, а все остальные истины, то функцию <tex>x_0\wedge </tex>можно выразить как <tex>g_l([\lnot]x_1, [\lnot]x_2, \ldots, [\lnot]x_n). </tex>, где <tex>x_0\lnot</tex> = (ставится перед аргументами с номерами <tex>x_{01}i_1, x_{02}i_2, \ldots, i_m</tex>.# Присутствует один член.., x_{0k}Выразим <tex> \wedge </tex> через <tex> \neg </tex> и <tex>g_l</tex>)'''аналогично пункту 3.'''
Возьмем В итоге получим функцию<tex>f_s\neg </tex>(, а также либо функцию <tex>x^{x_{01}}, x^{x_{02}}\wedge </tex>, либо функцию <tex> \vee </tex>...Поскольку функцию <tex> \wedge </tex> можно выразить через <tex> \vee </tex> и <tex> \neg </tex>, x^{x_{0k}}а функцию <tex> \vee </tex> через <tex> \wedge </tex> и <tex> \neg </tex>), где то мы получили базис <tex>x^{x_{0i}}\wedge </tex> = x, при <tex>x_{0i}\vee </tex> = 1 и , <tex>x^{x_{0i}}\neg </tex> = ¬x. Любую булеву функцию, не равную тождественному нулю, можно представить в форме [[СДНФ]], то есть выразить в данном базисе. Если же функция равна тождественному нулю, при то ее можно представить в виде <tex>x_{0i}x \land \lnot x</tex> = 0'''.'''
Нетрудно заметить, что <tex>f_s</tex>(0) = <tex>f_s</tex>(1) => <tex>f_s</tex> = '''const.'''
Таким образом мы получили одну из констант'''.'''
'''2''')Мы получили '''НЕ''' Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K {{---}} полная система функций, что и <tex>~0</tex>требовалось доказать. '''¬'''<tex>~0</tex> = <tex>~1</tex>'''.'''}}
'''3''')Мы получили '''НЕ''' == Примеры ==Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>~1S</tex>. '''¬''', <tex>~1M</tex> = , <tex>~0L</tex>'''.'''
'''4''')Мы получили <tex>~1</tex> и <tex>~0</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>f_m</tex>. Существуют Широко известны такие полные системы булевых функций:* <tex>x_1\left\{\land, x_2\lor, ..., x_n\neg\right\}</tex>, что <tex>f_m(x_1, x_2, ..., x_{i-1}, 0 , x_{i+1}конъюнкция, ...дизъюнкция, x_nотрицание)</tex> = 1, ;* <tex>f_m(x_1, x_2, ..., x_\left\{i-1}\land, 1 \oplus, x_{i+1\right\}, ..., x_n)</tex> = 0, зафиксируем все <tex>x_1, x_2, ..., x_n</tex>, тогда <tex>f_m(x_1конъюнкция, x_2сложение по модулю два, константа один)...Первая система используется, x_{i-1}например, xдля представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], x_{i+1}, ..., x_n)</tex> = ¬x'''вторая — для представления в виде [[Полином Жегалкина|полиномов Жегалкина]].'''
В итоге мы имеем три функции: '''НЕ'''Первая из упоминавшихся выше полных систем безызбыточной не является, <tex>~0</tex>поскольку согласно законам де Моргана либо дизъюнкцию, <tex>~1</tex>'''либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы.'''
Используем нелинейную функцию <tex>f_l</tex>'''.''' Среди нелинейных членов <tex>f_l</tex>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <tex>x_1</tex> и <tex>x_2</tex>, а все элементы, не входящие Теорема о максимальном числе функций в данный член, сделаем равными 0'''.''' Тогда <tex>f_l</tex> = <tex>x_1</tex>^<tex>x_2</tex> ⊕ [<tex>x_1</tex>] ⊕ [<tex>x_2</tex>] ⊕ [<tex>~1</tex>], где базисе: максимально возможное число булевых функций в квадратных скобках указаны члены, которые могут и не присутствовать'''базисе — четыре.'''
Рассмотрим несколько вариантов:Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций.
1) Присутствует член <tex>~1</tex>== См. Возьмем отрицание от <tex>f_l</tex> и член <tex>~1</tex> уберется'''.'''также ==* [[Определение_булевой_функции|Булевы функции]]* [[Суперпозиции|Суперпозиции]]* [[Полином_Жегалкина|Полином Жегалкина]]
2) Присутствуют 3 члена, без <tex>~1</tex>: <tex>f_l</tex> = <tex>x_1</tex>^<tex>x_2</tex> ⊕ <tex>x_1</tex> ⊕ <tex>x_2</tex>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.''' = Источники информации ==
3) Присутствуют 2 члена, без <tex>~1<* [http:/tex>/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'''И''', через '''НЕ''' и <tex>f_l<s lattice]* [http://www.mielt.ru/dir/cat14/subj266/file299/tex>view1397. html Лекции по дискретной математике]
4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <tex>f_l</tex>. В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''}}== Источники ==* [http[Категория://ru.wikipedia.org/wiki/Заглавная_страница Википедия — свободная энциклопедияДискретная математика и алгоритмы]]* Образовательный сайт [http[Категория://mini-soft.ru/nstu/diskr/7_.php MiniSoftБулевы функции]]
