Изменения

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

'''Замыканием''' (англ. ''сlosure'') множества функций называется минимальное по включению замкнутое подмножество всех функций, содержащее данное множество функций.}}

Множество <tex>A</tex> булевых функций алгебры логики называется '''полной системой'''(англ. ''complete set''), если замыкание этого множества совпадает с множеством всех функций.}}

Полная система функций называется '''безызбыточной'''(англ. ''irredundant functions''), если она перестаёт перестает быть полной при исключении из неё любого элемента.

* Функциифункции, сохраняющие константу <mathTex>T_0</mathTex> и <mathTex>T_1</mathTex>;,* Самодвойственные самодвойственныые функции <mathTex>S</mathTex>;,* Монотонные монотонные функции <mathTex>M</mathTex>;,* Линейные линейные функции <mathTex>L</mathTex>.

Класс функций сохраняющих ноль <tex>T_0</tex>.

|id = save0|definition=Говорят, что функция '''сохраняет константу 0ноль''', если <tex>f(0, 0, \dotsldots, 0) = 0</tex>.

Класс функций сохраняющих единицу <tex>T_1</tex>.

|id = save1|definition=Говорят, что функция '''сохраняет константу 1единицу''', если <tex>f(1, 1, \dotsldots, 1) = 1</tex>.

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

|id = monotone|definition=Говорят, что функция '''монотонна'''(англ. ''monotonic function'') , если <tex>\forall i (a_i\le leqslant b_i) \Rightarrow f(a_1,\dotsldots,a_n)\le leqslant f(b_1,\dotsldots,b_n)</tex>.

|id = linear|definition=Говорят, что функция '''линейна'''(англ. ''linear function''), если существуют такие <tex>a_0, a_1, a_2, \dotsldots, a_n</tex>, где <tex>a_i \in \{0, 1\}, \forall i=\overline{1,n}</tex>, что для любых <tex>x_1, x_2, \dotsldots, x_n</tex> имеет место равенство::<tex>f(x_1, x_2, \dotsldots, x_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\dotsldots\oplus a_n\cdot x_n</tex>.

Очевидно, что количество Количество линейных функций от <tex>n</tex> переменных равно <tex>~2^{n+1}</tex>. Функция является линейной тогда, и только тогда, когда в ее полиноме [[Полином_Жегалкина|Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].

== Критерий Поста ==Критерий Поста — одна из центральных теорем в теории булевых функцийФункция является линейной тогда, устанавливающая необходимое и достаточное условие для тоготолько тогда, чтобы некоторый набор булевых функций обладал достаточной выразительностьюкогда в ее [[Полином_Жегалкина|полиноме Жегалкина]] присутствуют слагаемые, чтобы представить любую булеву функциюкаждое из которых зависит не более чем от одной переменной. Впервые сформулирован американским математиком Эмилем Постом в 1941гПостроить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].

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

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

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полным. Докажем достаточность этого утверждения. Рассмотрим функцию, несохраняющую 0 {{---}} <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, \dots, x) = \neg x</tex>Необходимость. Рассмотрим функцию, несохраняющую 1 {{---}} <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>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_sf_1(x, x, x, \ldots, x) = \lnot x</tex>.

По определению найдется такой вектор <tex>x_0</tex>''Таким образом, что <tex>f_s(x_0) = f_s(\lnot x_0)</tex>. <tex>x_0 = (x_{01}, x_{02}, ..., x_{0k})</tex>.возможны четыре варианта:''

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

2)*Мы получили '''НЕ''' <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>.

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

4)Мы получили ''В итоге имеем три функции:'' <tex>1\neg </tex> и , <tex>0</tex>, <tex>1</tex>.

Рассмотрим немонотонную Используем нелинейную функцию <tex>f_mf_l</tex>. Существуют такие Среди нелинейных членов <tex>x_1, x_2, \ldots, x_nf_l</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>g_l = x_1, \land x_2 [ \oplus x_1] [\oplus x_2, ][ \ldots, x_noplus ~1]</tex>, тогда <tex>f_mгде в квадратных скобках указаны члены, которые могут и не присутствовать (x_1, x_2остальные слагаемые будут равны нулю, \ldotsпоскольку в них есть как минимум один аргумент, x_{i-1}не входящий в выбранный член, x, x_{i+1}, \ldots, x_nтак как в выбранном члене минимальное число элементов)= \lnot x</tex>.

В итоге имеем три функции: '''НЕ'Рассмотрим несколько вариантов:'', <tex>0</tex>, <tex>1</tex>.

Используем нелинейную функцию # Присутствует член <tex>f_l\oplus ~1</tex>. Среди нелинейных членов Возьмем отрицание от <tex>f_lg_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>. Построив две таблицы истинности для двух различных вариантов, кроме двухзаметим, что в обоих случаях функция истинна только в этом членеодной точке, следовательно, сделаем равными 1СДНФ функции <tex>g_l</tex> будет состоять только из одного члена. Если это так, оставшиеся 2 назовем то не составляет труда выразить <tex>x_1\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> ложны, а все элементыостальные истины, не входящие в данный член, сделаем равными 0'''.''' Тогда то функцию <tex>f_l = x_1 \land x_2 wedge </tex> можно выразить как <tex>g_l([ \oplus lnot]x_1] , [\oplus lnot]x_2], \ldots, [ \oplus ~1lnot]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.

В итоге получаем функцию '''НЕ'''Значит, а также либо функцию '''И'''полученные функции образуют полную систему, либо поскольку с их помощью можно выразить любую булеву функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, этого следует, что '''F''' K {{---}} полная система функций, что и требовалось доказать.''

В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать [[Определение_булевой_функции#.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,\oplus,1\right\}</tex> (конъюнкция, сложение по модулю 2два, константа 1один).Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[полином Полином Жегалкина|полиномов Жегалкина]]. Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы.

Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух Теорема о максимальном числе функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты.Максимально в базисе: максимально возможное число булевых функций в базисе — 4четыре.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и , соответственно , о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций.

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