Полные системы функций. Теорема Поста о полной системе функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м ('''.''' → .)
(не показано 35 промежуточных версий 11 участников)
Строка 1: Строка 1:
== Критерий Поста ==
+
== Полные системы функций ==
Критерий Поста — одна из центральных теорем в теории [[Определение булевой функции|булевых функций]], устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.
+
{{Определение
 +
|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>.
 +
 
 +
Функция является линейной тогда, и только тогда, когда в ее [[Полином_Жегалкина|полиноме Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].
 +
 
 +
== Формулировка и доказательство критерия Поста ==
 
{{
 
{{
 
Теорема|statement=
 
Теорема|statement=
Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
+
Набор булевых функций <tex>K</tex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
  
 
|proof=
 
|proof=
  
Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полным.
+
===== Необходимость. =====
  
Докажем достаточность этого утверждения.
+
Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора <tex>K</tex> входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор <tex>K</tex> не мог бы быть полным.
  
Рассмотрим функцию, несохраняющую 0 {{---}} <tex>f_0</tex>. <tex>f_0(0) = 1</tex>. <tex>f_0(1)</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_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>f_0(1) = 0</tex>, тогда <tex>f_0(x, x, x, \dots, x) = \neg x</tex>.
+
* Мы получили функцию <tex> \neg </tex>.
 +
Используем несамодвойственную функцию <tex>f_s</tex>. По определению, найдется такой вектор <tex>x_0</tex>, что <tex>f_s(x_0) = f_s(\lnot x_0)</tex>. Где <tex>x_0 = (x_{01}, x_{02}, \ldots, x_{0k})</tex>.  
  
Рассмотрим функцию, несохраняющую 1 {{---}} <tex>f_1</tex>. <tex>f_1(1) = 0</tex>. <tex>f_1(0)</tex> может принимать два значения:
+
Рассмотрим <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_1(0) = 0</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = 0</tex>.
+
*Мы получили <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>.
  
б) <tex>f_1(0) = 1</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = \lnot x</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>.
  
Возможны 4 варианта:
+
''В итоге имеем три функции:'' <tex> \neg </tex>, <tex>0</tex>, <tex>1</tex>.
  
1) Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <tex>f_s</tex>.
+
Используем нелинейную функцию <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>, где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).
  
По определению найдется такой вектор <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}})</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>\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>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.
  
Нетрудно заметить, что <tex>f_s(0) = f_s(1) \Rightarrow f_s = \operatorname {const}</tex>.
+
В итоге получим функцию<tex> \neg </tex>, а также либо функцию <tex> \wedge </tex>, либо функцию <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>. Любую булеву функцию, не равную тождественному нулю, можно представить в форме [[СДНФ]], то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде <tex>x \land \lnot x</tex>.  
Таким образом мы получили одну из констант.
 
  
2)Мы получили '''НЕ''' и <tex>0</tex>. <tex>\lnot 0 = 1</tex>.
 
  
3)Мы получили '''НЕ''' и <tex>1</tex>. <tex>\lnot 1 = 0</tex>.
+
''Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K {{---}} полная система функций, что и требовалось доказать.''
 +
}}
  
4)Мы получили <tex>1</tex> и <tex>0</tex>.
+
== Примеры ==
 +
Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</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</tex>, <tex>1</tex>.
+
Широко известны такие полные системы булевых функций:
 +
* <tex>\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> уберется.
+
Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций.
# Присутствуют 3 члена, без <tex>~1</tex>: <tex>f_l</tex> = <tex>x_1 \land x_2 \oplus x_1 \oplus x_2</tex>. Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ'''.
 
# Присутствуют 2 члена, без <tex>~1</tex>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <tex>f_l</tex>.
 
# Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <tex>f_l</tex>.
 
  
В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' {{---}} полная система функций, что и требовалось доказать.
+
== См. также ==
}}
+
* [[Определение_булевой_функции|Булевы функции]]
 +
* [[Суперпозиции|Суперпозиции]]
 +
* [[Полином_Жегалкина|Полином Жегалкина]]
  
== Источники ==
+
== Источники информации ==
  
* [http://ru.wikipedia.org/wiki/Заглавная_страница Википедия — свободная энциклопедия]
+
* [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://mini-soft.ru/nstu/diskr/7_.php MiniSoft]
 
* [http://en.wikipedia.org/wiki/Post%27s_lattice Post's lattice]
 
* [http://en.wikipedia.org/wiki/Post%27s_lattice Post's lattice]
 +
* [http://www.mielt.ru/dir/cat14/subj266/file299/view1397.html Лекции по дискретной математике]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Булевы функции]]

Версия 15:25, 28 декабря 2017

Полные системы функций

Определение:
Если любая булева функция, являющаяся суперпозицией функций некоторого множества, принадлежит этому множеству, то такое множество называют замкнутым (англ. closed set).


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


Определение:
Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций.


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


Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:

  • функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math],
  • самодвойственныые функции [math]S[/math],
  • монотонные функции [math]M[/math],
  • линейные функции [math]L[/math].

Замкнутые классы булевых функций

Класс функций сохраняющих ноль [math]T_0[/math].

Определение:
Говорят, что функция сохраняет ноль, если [math]f(0, 0, \ldots, 0) = 0[/math].


Класс функций сохраняющих единицу [math]T_1[/math].

Определение:
Говорят, что функция сохраняет единицу, если [math]f(1, 1, \ldots, 1) = 1[/math].


Класс самодвойственных функций [math]S[/math].

Определение:
Говорят, что функция самодвойственна (англ. self-dual), если [math]f(\overline{x_1},\ldots,\overline{x_n})=\overline{f(x_1,\ldots,x_n)}[/math]. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.


Класс монотонных функций [math]M[/math].

Определение:
Говорят, что функция монотонна (англ. monotonic function) , если [math]\forall i (a_i \leqslant b_i) \Rightarrow f(a_1,\ldots,a_n)\leqslant f(b_1,\ldots,b_n)[/math].


Класс линейных функций [math]L[/math].

Определение:
Говорят, что функция линейна (англ. linear function), если существуют такие [math]a_0, a_1, a_2, \ldots, a_n[/math], где [math]a_i \in \{0, 1\}, \forall i=\overline{1,n}[/math], что для любых [math]x_1, x_2, \ldots, x_n[/math] имеет место равенство:
[math]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[/math].

Количество линейных функций от [math]n[/math] переменных равно [math]~2^{n+1}[/math].

Функция является линейной тогда, и только тогда, когда в ее полиноме Жегалкина присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью преобразования Мебиуса.

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

Теорема:
Набор булевых функций [math]K[/math] является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов [math] S,M,L,T_0,T_1 [/math], иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
Доказательство:
[math]\triangleright[/math]
Необходимость.

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

Достаточность.

Докажем, что если набор [math]K[/math] не содержится полностью ни в одном из данных классов, то он является полным.

  1. Рассмотрим функцию, не сохраняющую ноль — [math]f_0[/math] (то есть функцию, для которой [math]f_0(0) = 1[/math]). Тогда [math] f_0(1)[/math] может принимать два значения:
    1. [math]f_0(1) = 1[/math], тогда [math]f_0(x, x, x, \ldots, x) = 1[/math].
    2. [math]f_0(1) = 0[/math], тогда [math]f_0(x, x, x, \ldots, x) = \neg x[/math].
  2. Рассмотрим функцию, не сохраняющую один — [math]f_1[/math] (то есть функцию, для которой [math]f_1(1) = 0[/math]). Тогда [math]f_1(0)[/math] может принимать два значения:
    1. [math]f_1(0) = 0[/math], тогда [math]f_1(x, x, x, \ldots, x) = 0[/math].
    2. [math]f_1(0) = 1[/math], тогда [math]f_1(x, x, x, \ldots, x) = \lnot x[/math].

Таким образом, возможны четыре варианта:

  • Мы получили функцию [math] \neg [/math].

Используем несамодвойственную функцию [math]f_s[/math]. По определению, найдется такой вектор [math]x_0[/math], что [math]f_s(x_0) = f_s(\lnot x_0)[/math]. Где [math]x_0 = (x_{01}, x_{02}, \ldots, x_{0k})[/math].

Рассмотрим [math]f_s(x^{x_{01}}, x^{x_{02}}, \ldots, x^{x_{0k}})[/math], где либо [math]x^{x_{0i}} = x[/math], при [math]x_{0i} = 1[/math]. Либо [math]x^{x_{0i}} = \lnot x[/math], при [math]x_{0i} = 0 [/math]. Нетрудно заметить, что [math]f_s(0) = f_s(1) \Rightarrow f_s = \operatorname {const}[/math]. Таким образом мы получили одну из констант.

  • Мы получили [math] \neg [/math] и [math]0 \Rightarrow[/math] имеем константу, равную [math]1[/math], поскольку [math]\lnot 0 = 1[/math].
  • Мы получили [math] \neg [/math] и [math]1 \Rightarrow[/math] имеем константу, равную [math]0[/math], поскольку [math]\lnot 1 = 0[/math].
  • Мы получили [math]1[/math] и [math]0[/math].

Рассмотрим немонотонную функцию [math]f_m[/math]. Существуют такие [math]x_1, x_2, \ldots, x_n[/math], что [math]f_m(x_1, x_2, \ldots, x_{i-1}, 0 , x_{i+1}, \ldots, x_n) = 1[/math], [math]f_m(x_1, x_2, \ldots, x_{i-1}, 1 , x_{i+1}, \ldots, x_n) = 0[/math], зафиксируем все [math]x_1, x_2, \ldots, x_n[/math], тогда [math]f_m(x_1, x_2, \ldots, x_{i-1}, x, x_{i+1}, \ldots, x_n)= \lnot x[/math].

В итоге имеем три функции: [math] \neg [/math], [math]0[/math], [math]1[/math].

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

Рассмотрим несколько вариантов:

  1. Присутствует член [math]\oplus ~1[/math]. Возьмем отрицание от [math]g_l[/math] и член [math]\oplus ~1[/math] исчезнет.
  2. Присутствуют три члена, без [math]\oplus ~1[/math]: [math]g_l= x_1 \land x_2 \oplus x_1 \oplus x_2[/math]. Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции [math] \vee [/math].
  3. Присутствуют два члена, без [math]\oplus ~1[/math]. Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции [math]g_l[/math] будет состоять только из одного члена. Если это так, то не составляет труда выразить [math] \wedge [/math] через [math] \neg [/math] и [math]g_l[/math]. Например, если функция [math]g_l(x_1, x_2, \ldots, x_n)[/math] принимает истинное значение, когда аргументы c номерами [math]i_1, i_2, \ldots, i_m[/math] ложны, а все остальные истины, то функцию [math] \wedge [/math] можно выразить как [math]g_l([\lnot]x_1, [\lnot]x_2, \ldots, [\lnot]x_n)[/math], где [math]\lnot[/math] ставится перед аргументами с номерами [math]i_1, i_2, \ldots, i_m[/math].
  4. Присутствует один член. Выразим [math] \wedge [/math] через [math] \neg [/math] и [math]g_l[/math] аналогично пункту 3.

В итоге получим функцию[math] \neg [/math], а также либо функцию [math] \wedge [/math], либо функцию [math] \vee [/math]. Поскольку функцию [math] \wedge [/math] можно выразить через [math] \vee [/math] и [math] \neg [/math], а функцию [math] \vee [/math] через [math] \wedge [/math] и [math] \neg [/math], то мы получили базис [math] \wedge [/math], [math] \vee [/math], [math] \neg [/math]. Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде [math]x \land \lnot x[/math].


Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K — полная система функций, что и требовалось доказать.
[math]\triangleleft[/math]

Примеры

Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов [math]T_0[/math], [math]T_1[/math], [math]S[/math], [math]M[/math], [math]L[/math].

В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера или стрелку Пирса.

Широко известны такие полные системы булевых функций:

  • [math]\left\{\land,\lor,\neg\right\}[/math] (конъюнкция, дизъюнкция, отрицание);
  • [math]\left\{\land,\oplus,1\right\}[/math] (конъюнкция, сложение по модулю два, константа один).

Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.

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

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

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

См. также

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