Изменения

== Критерий Поста Полные системы функций =={{Определение|definition=Критерий Поста — одна из центральных теорем в теории булевых Если любая [[Определение булевой функции|булева функция]], являющаяся [[Суперпозиции|суперпозицией]] функцийнекоторого множества, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностьюпринадлежит этому множеству, чтобы представить любую булеву функциюто такое множество называют '''замкнутым''' (англ. Впервые сформулирован американским математиком Эмилем Постом''closed set'').}}

== Формулировка и доказательство критерия =={{ОпределениеТеорема|statementdefinition=Система '''Замыканием''' (англ. ''сlosure'') множества функций называется такое подмножество всех булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном что любую из классов <tex>~S,M,L,T_0,T_1</tex>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функцияэтих функций можно выразить через функции исходного множества.}}

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

Заметим, что необходимость этого утверждения очевидна{{Определение|definition=Полная система функций называется '''безызбыточной''' (англ. ''irredundant functions''), так как если бы все функции из набора К входили в один она перестает быть полной при исключении из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полнымнеё любого элемента.}}

Докажем достаточность этого утверждения== Замкнутые классы булевых функций ==Класс функций сохраняющих ноль <tex>T_0</tex>.{{Определение|id = save0|definition=Говорят, что функция '''сохраняет ноль''', если <tex>f(0, 0, \ldots, 0) = 0</tex>.}}

а) Класс функций сохраняющих единицу <tex>f_0T_1</tex>(1) . {{Определение|id = save1|definition= 1Говорят, что функция '''сохраняет единицу''', тогда <tex>f_0если </tex>f(x1, x1, x\ldots, ..., x1) = <tex>~1</tex>'''.'''}}

Рассмотрим функцию, несохраняющую 1 - Класс самодвойственных функций <tex>f_1S</tex>.{{Определение|id = selfDual|definition=Говорят, что функция '''самодвойственна''' (англ.''self-dual'' ), если <tex>f_1</tex>f(1\overline{x_1},\ldots,\overline{x_n}) = 0. <tex>f_1\overline{f(x_1,\ldots,x_n)}</tex>(0) может принимать два . Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения:.}}

а) Класс монотонных функций <tex>f_1M</tex>.{{Определение|id = monotone|definition=Говорят, что функция '''монотонна''' (0англ. ''monotonic function'') = 0, тогда если <tex>f_1</tex>\forall i (a_i \leqslant b_i) \Rightarrow f(xa_1, x\ldots, xa_n)\leqslant f(b_1, ...\ldots, xb_n) = <tex>~0</tex>'''.'''}}

бКласс линейных функций <tex>L</tex>.{{Определение|id = linear|definition=Говорят, что функция '''линейна''' (англ. ''linear function'') , если существуют такие <tex>f_1a_0, a_1, a_2, \ldots, a_n</tex>(, где <tex>a_i \in \{0) , 1\}, \forall i= \overline{1, тогда n}</tex>, что для любых <tex>f_1x_1, x_2, \ldots, x_n</tex>имеет место равенство::<tex>f(x, xx_1, xx_2, ...\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 варианта:Функция является линейной тогда, и только тогда, когда в ее [[Полином_Жегалкина|полиноме Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]]. == Формулировка и доказательство критерия Поста =={{Теорема|statement=Набор булевых функций <tex>K</tex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

По определению найдется такой вектор <tex>x_0</tex>, что <tex>f_s</tex>(<tex>x_0</tex>) = <tex>f_s</tex>(¬<tex>x_0</tex>)==== Необходимость. <tex>x_0</tex> = (<tex>x_{01}, x_{02}, ..., x_{0k}</tex>)'''.'''====

Возьмем Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора <tex>f_sK</tex>(<tex>x^{x_{01}}входили в один из перечисленных классов, x^{x_{02}}то и все суперпозиции, ...а, x^{x_{0k}}</tex>)значит, где <tex>x^{x_{0i}}</tex> = xи замыкание набора входило бы в этот класс, при <tex>x_{0i}</tex> = 1 и набор <tex>x^{x_{0i}}</tex> = ¬x, при <tex>x_{0i}K</tex> = 0'''не мог бы быть полным.'''

Нетрудно заметить===== Достаточность. =====Докажем, что если набор <tex>f_sK</tex>не содержится полностью ни в одном из данных классов, то он является полным.# Рассмотрим функцию, не сохраняющую ноль {{---}} <tex>f_0</tex> (то есть функцию, для которой <tex>f_0(0) = 1</tex>). Тогда <tex>f_sf_0(1)</tex>может принимать два значения:## <tex>f_0(1) =1</tex>, тогда <tex>f_0(x, x, x, \ldots, x) = 1</tex> .## <tex>f_sf_0(1) = 0</tex> , тогда <tex>f_0(x, x, x, \ldots, x) = '''const\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>.'''

'''2''')Мы получили '''НЕ''' и <tex>~0</tex>. '''¬'''<tex>~0</tex> = <tex>~1</tex>'''.'Таким образом, возможны четыре варианта:''

'''3''')* Мы получили '''НЕ''' и функцию <tex>~1\neg </tex>. '''¬'''Используем несамодвойственную функцию <tex>~1f_s</tex> . По определению, найдется такой вектор <tex>x_0</tex>, что <tex>f_s(x_0) = f_s(\lnot x_0)</tex>. Где <tex>~0x_0 = (x_{01}, x_{02}, \ldots, x_{0k})</tex>'''.'''

'''4'''Рассмотрим <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>f_m\neg </tex>. Существуют такие и <tex>x_1, x_2, ..., x_n0 \Rightarrow</tex>имеем константу, что равную <tex>f_m(x_1, x_2, ..., x_{i-1}</tex>, поскольку <tex>\lnot 0 , x_{i+= 1}, </tex>..., x_n)*Мы получили <tex> \neg </tex> = 1, и <tex>f_m(x_1, x_2, ..., x_{i-1}, 1 \Rightarrow</tex> имеем константу, x_{i+1}, ...равную <tex>0</tex>, x_n)поскольку </tex> \lnot 1 = 0, зафиксируем все </tex>x_1, x_2, ..., x_n*Мы получили <tex>1</tex>, тогда и <tex>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)0</tex> = ¬x'''.'''

В итоге имеем три функции: '''НЕ'''Рассмотрим немонотонную функцию <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, \ldots, x_{i-1}, x, x_{i+1}, \ldots, x_n)= \lnot x</tex>'''.'''

Используем нелинейную функцию <tex>f_l</tex>'''.'В итоге имеем три функции:'' Среди нелинейных членов <tex>f_l\neg </tex>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <tex>x_10</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>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

1) Присутствует член <tex>~1</tex>. Возьмем отрицание от <tex>f_l</tex> и член <tex>~1</tex> уберется'''.'Рассмотрим несколько вариантов:''

2) # Присутствует член <tex>\oplus ~1</tex>. Возьмем отрицание от <tex>g_l</tex> и член <tex>\oplus ~1</tex> исчезнет.# Присутствуют 3 три члена, без <tex>\oplus ~1</tex>: <tex>f_lg_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>x_2ложны, а все остальные истины, то функцию <tex> \wedge </tex> ⊕ можно выразить как <tex>g_l([\lnot]x_1, [\lnot]x_2, \ldots, [\lnot]x_n)</tex> ⊕ , где <tex>x_2\lnot</tex>'''.''' Составив таблицу истинности для этой функцииставится перед аргументами с номерами <tex>i_1, i_2, нетрудно заметить\ldots, что она эквивалентна функции '''ИЛИi_m</tex>.# Присутствует один член. Выразим <tex> \wedge </tex> через <tex> \neg </tex> и <tex>g_l</tex> аналогично пункту 3.'''

3) Присутствуют 2 членаВ итоге получим функцию<tex> \neg </tex>, а также либо функцию <tex> \wedge </tex>, без либо функцию <tex>~1\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>f_lx \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 Википедия — свободная энциклопедияЗамкнутые классы булевых функций]