1632
правки
Изменения
м
==Доказательство ={{Определение|definition=Полная система функций называется '''I.безызбыточной''' Докажем прямую теорему(англ. ''irredundant functions''), если она перестает быть полной при исключении из неё любого элемента.'''}}
ПредположимАмериканский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:* функции, что '''F''' не содержит функцию, обладающую одним из перечисленных выше свойствсохраняющие константу <Tex>T_0</Tex> и <Tex>T_1</Tex>, но тогда мы не сможем через * самодвойственныые функции<Tex>S</Tex>, входящие в '''F''' выразить * монотонные функции<Tex>M</Tex>, обладающие этим свойством, и следовательно '''F''' не будет полной системой функций, что противоречит условию, следовательно '''F''' должна содержать все вышеперечисленные * линейные функции'''<Tex>L</Tex>.'''
'''II== Замкнутые классы булевых функций ==Класс функций сохраняющих ноль <tex>T_0</tex>.{{Определение|id = save0|definition=Говорят, что функция ''' Докажем обратную теоремусохраняет ноль''', если <tex>f(0, 0, \ldots, 0) = 0</tex>.'''}}
У нас есть 5 функций: несохраняющая 1 - <math>f_1</math>, несохраняющая 0 - <math>f_0</math>, несамодвойственная - <math>f_s</math>, немонотонная - <math>f_m</math>, нелинейная - <math>f_l</math>'''.'''
Возьмем функцию, несохраняющую 0 - Класс функций сохраняющих единицу <mathtex>f_0T_1</mathtex>. {{Определение|id = save1|definition=Говорят, что функция '''.сохраняет единицу''' , если <math>f_0</mathtex>f(01, 1, \ldots, 1) = 1'''.''' <math>f_0</mathtex>(1) может принимать два значения:.}}
а) <math>f_0</math>(1) = 1, тогда <math>f_0</math>(x, x, x, ..., x) = <math>~1</math>'''.'''
б) Класс самодвойственных функций <mathtex>f_0S</mathtex>.{{Определение|id = selfDual|definition=Говорят, что функция '''самодвойственна''' (1англ. ''self-dual'') = 0, тогда если <math>f_0</mathtex>f(x\overline{x_1}, x\ldots, x\overline{x_n})=\overline{f(x_1, \ldots,x_n)}</tex>...Иными словами, функция называется самодвойственной, x) = ¬x'''если на противоположных наборах она принимает противоположные значения.''' }}
Возьмем функцию, несохраняющую 1 - Класс монотонных функций <mathtex>f_1M</mathtex>. {{Определение|id = monotone|definition=Говорят, что функция '''монотонна''' (англ. ''monotonic function'') , если <math>f_1</mathtex>\forall i (a_i \leqslant b_i) \Rightarrow f(a_1,\ldots,a_n)\leqslant f(1b_1,\ldots,b_n) = 0. <math>f_1</mathtex>(0) может принимать два значения:.}}
аКласс линейных функций <tex>L</tex>.{{Определение|id = linear|definition=Говорят, что функция '''линейна''' (англ. ''linear function'') , если существуют такие <mathtex>f_1a_0, a_1, a_2, \ldots, a_n</mathtex>, где <tex>(a_i \in \{0) , 1\}, \forall i= 0\overline{1,n}</tex>, тогда что для любых <mathtex>f_1x_1, x_2, \ldots, x_n</mathtex> имеет место равенство::<tex>f(x, xx_1, xx_2, ...\ldots, xx_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\ldots\oplus a_n\cdot x_n<math/tex>.}}Количество линейных функций от <tex>n</tex> переменных равно <tex>~02^{n+1}</mathtex>'''.'''
б) <math>f_1</math>(0) = 1Функция является линейной тогда, и только тогда <math>f_1</math>(x, x, xкогда в ее [[Полином_Жегалкина|полиноме Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной.Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].., x) = ¬x'''.'''
Возможны 4 варианта:== Формулировка и доказательство критерия Поста =={{Теорема|statement=Набор булевых функций <tex>K</tex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <math>f_s</math>.|proof=
По определению найдется такой вектор <math>x_0</math>, что <math>f_s</math>(<math>x_0</math>) = <math>f_s</math>(¬<math>x_0</math>)==== Необходимость. <math>x_0</math> = (<math>x_{01}, x_{02}, ..., x_{0k}</math>)'''.'''====
Возьмем Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора <mathtex>f_sK</math>(<mathtex>x^{x_{01}}входили в один из перечисленных классов, x^{x_{02}}то и все суперпозиции, ...а, x^{x_{0k}}</math>)значит, где <math>x^{x_{0i}}</math> = xи замыкание набора входило бы в этот класс, при <math>x_{0i}</math> = 1 и набор <math>x^{x_{0i}}</math> = ¬x, при <mathtex>x_{0i}K</mathtex> = 0'''не мог бы быть полным.'''
Нетрудно заметить===== Достаточность. =====Докажем, что если набор <mathtex>f_sK</mathtex> не содержится полностью ни в одном из данных классов, то он является полным.# Рассмотрим функцию, не сохраняющую ноль {{---}} <tex>f_0</tex> (то есть функцию, для которой <tex>f_0(0) = 1<math/tex>f_s). Тогда <tex> f_0(1)</mathtex>может принимать два значения:## <tex>f_0(1) =1</tex> , тогда <mathtex>f_sf_0(x, x, x, \ldots, x) = 1</tex>.## <tex>f_0(1) = 0</mathtex>, тогда <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>.'''
'''3''')* Мы получили '''НЕ''' и функцию <mathtex>~1\neg </mathtex>. '''¬'''Используем несамодвойственную функцию <mathtex>~1f_s</mathtex> . По определению, найдется такой вектор <tex>x_0</tex>, что <tex>f_s(x_0) = f_s(\lnot x_0)</tex>. Где <mathtex>~0x_0 = (x_{01}, x_{02}, \ldots, x_{0k})</mathtex>'''.'''
'''4'''Рассмотрим <tex>f_s(x^{x_{01}}, x^{x_{02}}, \ldots, x^{x_{0k}})Мы получили <math/tex>, где либо <tex>x^{x_{0i}} = x</tex>, при <tex>~x_{0i} = 1</mathtex> и . Либо <mathtex>~x^{x_{0i}} = \lnot x</tex>, при <tex>x_{0i} = 0 </tex>. Нетрудно заметить, что <tex>f_s(0) = f_s(1) \Rightarrow f_s = \operatorname {const}</mathtex>'''.'''Таким образом мы получили одну из констант.
Рассмотрим немонотонную функцию *Мы получили <mathtex>f_m\neg </mathtex>. Существуют такие и <mathtex>x_1, x_2, ..., x_n0 \Rightarrow</mathtex>имеем константу, что равную <mathtex>f_m(x_1, x_2, ..., x_{i-1}</tex>, поскольку <tex>\lnot 0, x_{i+= 1}, </tex>..., x_n)*Мы получили <tex> \neg </mathtex> и <tex> = 1 \Rightarrow</tex> имеем константу, равную <tex>0<math/tex>f_m(x_1, x_2, ..., x_{i-1}, 1, x_{i+1}, ..., x_n)поскольку </mathtex> \lnot 1 = 0, зафиксируем все <math/tex>x_1, x_2, ..., x_n*Мы получили <tex>1</mathtex>, тогда и <mathtex>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)0</mathtex> = ¬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>, <mathtex>~f_m(x_1, x_2, \ldots, x_{i-1}, 1 , x_{i+1}, \ldots, x_n) = 0</mathtex>, зафиксируем все <mathtex>~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</mathtex>'''.'''
Используем нелинейную функцию <math>f_l</math>'''.'В итоге имеем три функции:'' Среди нелинейных членов <mathtex>f_l\neg </mathtex>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <mathtex>x_1</math> и <math>x_20</mathtex>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ [<math>x_1</math>] ⊕ [<math>x_2</math>] ⊕ [<mathtex>~1</mathtex>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''
Рассмотрим несколько вариантов:Используем нелинейную функцию <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) Присутствует член <math>~1</math>. Возьмем отрицание от <math>f_l</math> и член <math>~1</math> уберется'''.'Рассмотрим несколько вариантов:''
2) Присутствуют 3 члена, без # Присутствует член <mathtex>\oplus ~1</mathtex>: . Возьмем отрицание от <mathtex>f_lg_l</mathtex> = и член <mathtex>x_1\oplus ~1</mathtex>^исчезнет.# Присутствуют три члена, без <mathtex>x_2\oplus ~1</mathtex> ⊕ : <mathtex>g_l= x_1 \land x_2 \oplus x_1</math> ⊕ <math>\oplus x_2</mathtex>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ<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> ложны, а все остальные истины, то функцию <tex> \wedge </tex> можно выразить как <tex>g_l([\lnot]x_1, [\lnot]x_2, \ldots, [\lnot]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.'''
3) Присутствуют 2 членаВ итоге получим функцию<tex> \neg </tex>, без а также либо функцию <mathtex>~1\wedge </mathtex>, либо функцию <tex> \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>. Любую булеву функцию, не равную тождественному нулю, можно представить в обоих случаях функция истинна только в одной точке => форме [[СДНФ будет состоять только из одного члена, а если это так]], то не составляет труда есть выразить '''И'''в данном базисе. Если же функция равна тождественному нулю, через '''НЕ''' и то ее можно представить в виде <mathtex>f_lx \land \lnot x</mathtex>.
4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <math>f_l</math>.
Получается''Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что у нас есть функция '''НЕ'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> можно назвать базисом класса линейных функций. == См. также ==* [[Определение_булевой_функции|Булевы функции '''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 Википедия — Замкнутые классы булевых функций]* Образовательный сайт [http://mini- полная система функций''soft.ru/nstu/diskr/7_.php MiniSoft]* [http://en.wikipedia.org/wiki/Post%27s_lattice Post's lattice]* [http://www.mielt.ru/dir/cat14/subj266/file299/view1397.'''html Лекции по дискретной математике] [[Категория: Дискретная математика и алгоритмы]][[Категория: Булевы функции]]
rollbackEdits.php mass rollback
==Формулировка теоремыПолные системы функций =={{Определение|definition=Если любая [[Определение булевой функции|булева функция]], являющаяся [[Суперпозиции|суперпозицией]] функций некоторого множества, принадлежит этому множеству, то такое множество называют '''замкнутым''' (англ. ''closed set'').}}
{{Определение|definition='''FЗамыканием''' называется полной системой функций тогда и только тогда, когда она содержит функцию, (англ. ''несохраняющуюсlosure'' 1) множества функций называется минимальное по включению замкнутое подмножество всех функций, функцию, ''несохраняющую'' 0, ''немонотонную'', ''несамодвойственную'' и ''нелинейную'' функции'''содержащее данное множество функций.'''----}}
{{Определение
|id=def1
|definition=
Множество булевых функций называется '''полной системой''' (англ. ''complete set''), если замыкание этого множества совпадает с множеством всех функций.}}
'''2''')Мы получили '''НЕ''' и <math>~0</math>. '''¬'''<math>~0</math> = <math>~1</math>'''.'Таким образом, возможны четыре варианта:''
