Изменения

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

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых {{Определение|definition='''Замыканием''' (англ. ''сlosure'') множества функций называется минимальное по включению замкнутое подмножество всех функций:* Функции, сохраняющие константу <math>T_0</math> и <math>T_1</math>;* Самодвойственные функции <math>S</math>;* Монотонные функции <math>M</math>;* Линейные функции <math>L</math>содержащее данное множество функций.}}

Заметим, что существуют функции{{Определение|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>. Функция является линейной тогда, и только тогда, чтобы представить любую булеву функциюкогда в ее [[Полином_Жегалкина|полиноме Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Впервые сформулирован американским математиком Эмилем ПостомПостроить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].

== Формулировка и доказательство критерия Поста ==

Система Набор булевых функций F <tex>K</tex> является полной полным тогда и только тогда, когда она он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, т.е. иными словами, когда в ней нем имеется хотя бы одна функция, не сохраняющая 0ноль, хотя бы одна функция, не сохраняющая 1один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полным===== Необходимость.=====

Докажем достаточность Заметим, что необходимость этого утвержденияочевидна, так как если бы все функции из набора <tex>K</tex> входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор <tex>K</tex> не мог бы быть полным.

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

а) <tex>f_0(1) = 1</tex>''Таким образом, тогда <tex>f_0(x, x, x, \ldots, x) = 1</tex>.возможны четыре варианта:''

б) * Мы получили функцию <tex> \neg </tex>. Используем несамодвойственную функцию <tex>f_s</tex>. По определению, найдется такой вектор <tex>x_0</tex>, что <tex>f_0f_s(1x_0) = 0f_s(\lnot x_0)</tex>, тогда . Где <tex>f_0x_0 = (x, xx_{01}, xx_{02}, \dotsldots, xx_{0k}) = \neg x</tex>.

Рассмотрим функцию<tex>f_s(x^{x_{01}}, несохраняющую 1 x^{x_{02}}, \ldots, x^{x_{0k}})</tex>, где либо <tex>x^{x_{---0i}} = x</tex>, при <tex>f_1x_{0i} = 1</tex>. Либо <tex>f_1(1) x^{x_{0i}} = \lnot x</tex>, при <tex>x_{0i} = 0</tex>. Нетрудно заметить, что <tex>f_1f_s(0)= f_s(1) \Rightarrow f_s = \operatorname {const}</tex> может принимать два значения:.Таким образом мы получили одну из констант.

а) *Мы получили <tex> \neg </tex> и <tex>f_1(0) = 0\Rightarrow</tex>имеем константу, тогда равную <tex>1</tex>f_1(x, xпоскольку <tex>\lnot 0 = 1</tex>.*Мы получили <tex> \neg </tex> и <tex>1 \Rightarrow</tex> имеем константу, xравную <tex>0</tex>, поскольку <tex>\ldots, x) 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_1f_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_1f_m(xx_1, x_2, \ldots, x_{i-1}, x, xx_{i+1}, \ldots, xx_n) = \lnot x</tex>.

Возможны 4 варианта''В итоге имеем три функции:'' <tex> \neg </tex>, <tex>0</tex>, <tex>1</tex>.

1Используем нелинейную функцию <tex>f_l</tex>. Среди нелинейных членов <tex>f_l</tex> (ее представления в виде [[Полином Жегалкина|полинома Жегалкина]]) Мы получили функцию '''НЕ''', выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем <tex>x_1</tex> и <tex>x_2</tex>. Все элементы, не входящие в данный член, примем равными нулю. Используем несамодвойственную функцию Тогда эта функция будет представима в виде <tex>f_sg_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1]</tex>, где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).

# Присутствует член <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>f_sg_l</tex> будет состоять только из одного члена. Если это так, то не составляет труда выразить <tex> \wedge </tex> через <tex> \neg </tex> и <tex>g_l</tex>. Например, если функция <tex>g_l(x^{x_{01}}x_1, x^{x_{02}}x_2, \ldots, x^{x_{0k}}x_n)</tex>принимает истинное значение, где когда аргументы c номерами <tex>x^{x_{0i}} = xi_1, i_2, \ldots, i_m</tex>ложны, при а все остальные истины, то функцию <tex>x_{0i} = 1\wedge </tex> можно выразить как <tex>g_l([\lnot]x_1, [\lnot]x_2, \ldots, [\lnot]x_n)</tex> и , где <tex>x^{x_{0i}} = \lnot x</tex>ставится перед аргументами с номерами <tex>i_1, i_2, при \ldots, i_m</tex>x_{0i} = 0 .# Присутствует один член. Выразим <tex> \wedge </tex> через <tex> \neg </tex> и <tex>g_l</tex>аналогично пункту 3.

Нетрудно заметитьВ итоге получим функцию<tex> \neg </tex>, что а также либо функцию <tex>f_s(0) = f_s(1) \Rightarrow f_s = wedge </tex>, либо функцию <tex> \operatorname {const}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>.

3)Мы получили '''НЕ'Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K {{---}} полная система функций, что и требовалось доказать.'' и <tex>1</tex>. <tex>\lnot 1 = 0</tex>.}}

4)Мы получили == Примеры ==Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>1T_1</tex> и , <tex>S</tex>, <tex>M</tex>, <tex>0L</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>, <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>она сама по себе формирует полную систему. В качестве примера можно назвать [[Определение_булевой_функции#.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>0\left\{\land,\lor,\neg\right\}</tex>(конъюнкция, дизъюнкция, отрицание);* <tex>\left\{\land,\oplus,1\right\}</tex>(конъюнкция, сложение по модулю два, константа один).Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[Полином Жегалкина|полиномов Жегалкина]].

Используем нелинейную функцию <tex>f_l</tex>. Среди нелинейных членов <tex>f_l</tex>Первая из упоминавшихся выше полных систем безызбыточной не является, выберем тотпоскольку согласно законам де Моргана либо дизъюнкцию, в котором минимальное количество элементов, все элементы, кроме либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух, в этом члене, сделаем равными 1, оставшиеся 2 назовем <tex>x_1</tex> и <tex>x_2</tex>, а функций. Вторая система является безызбыточной — все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <tex>f_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1]</tex>, где в квадратных скобках указаны члены, которые могут и не присутствоватьтри её элемента необходимы для полноты системы.

Рассмотрим несколько вариантовТеорема о максимальном числе функций в базисе:максимально возможное число булевых функций в базисе — четыре.

# Присутствует член <tex>~1</tex>. Возьмем отрицание от <tex>f_l</tex> Иногда говорят о системе функций, полной в некотором замкнутом классе, и член <tex>~1</tex> уберется, соответственно, о базисе этого класса.# Присутствуют 3 членаНапример, без <tex>~1</tex>: систему <tex>f_l = x_1 \land x_2 left\oplus x_1 {\oplus x_2</tex>. Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ'''.# Присутствуют 2 члена, без <tex>~1\right\}</tex>. Построив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <tex>f_l</tex>. # Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <tex>f_l</tex>можно назвать базисом класса линейных функций.

В итоге получаем функцию '''НЕ''', а == См. также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через ==* [[Определение_булевой_функции|Булевы функции '''F''' можно выразить базис, следует, что '''F''' {{---}} полная система функций, что и требовалось доказать.]]* [[Суперпозиции|Суперпозиции]]}}* [[Полином_Жегалкина|Полином Жегалкина]]

== Источники информации ==

* [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 Википедия — Замкнутые классы булевых функций]