Изменения

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

Система Набор булевых функций 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</tex> = <tex>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</tex> = систему <tex>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 Википедия — Замкнутые классы булевых функций]