Изменения
Нет описания правки
{{Определение
|definition=
Если любая [[Определение булевой функции|булева функция]], являющаяся [[Суперпозиции|суперпозицией]] функций некоторого множества принадлежит этому множеству, то такое множество называют '''замкнутым'''.}}
{{Определение
|id=def1
|definition=
Множество <tex>A</tex> булевых функций называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}}
{{Определение
Класс функций <tex>T_0</tex>.
{{Определение
|definition=Говорят, что функция '''сохраняет 0ноль''', если <tex>f(0, 0, \dots, 0) = 0</tex>.
}}
Класс функций <tex>T_1</tex>.
{{Определение
|definition=Говорят, что функция '''сохраняет 1один''', если <tex>f(1, 1, \dots, 1) = 1</tex>.
}}
{{
Теорема|statement=
Набор булевых функций K является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, т.е. когда в нем имеется хотя бы одна функция, не сохраняющая 0ноль, хотя бы одна функция, не сохраняющая 1один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
|proof=
Докажем достаточность этого утверждения.
Рассмотрим функцию, не сохраняющую 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>.
Возможны 4 четыре варианта:
1) Мы получили функцию НЕ. Используем несамодвойственную функцию <tex>f_s</tex>.
Таким образом мы получили одну из констант.
2)Мы получили НЕ и <tex>0</tex>. <tex>\lnot 0 = 1</tex>.
3)Мы получили НЕ и <tex>1</tex>. <tex>\lnot 1 = 0</tex>.
4)Мы получили <tex>1</tex> и <tex>0</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>.
В итоге имеем три функции: НЕ, <tex>0</tex>, <tex>1</tex>.
Используем нелинейную функцию <tex>f_l</tex>. Среди нелинейных членов <tex>f_l</tex>(ее представления в виде [[Полином Жегалкина|полинома Жегалкина]]), выберем тот, в котором минимальное количество элементов, все элементы. Все аргументы, кроме двух, в этом члене, сделаем равными 1приравняем единице, оставшиеся 2 два назовем <tex>x_1</tex> и <tex>x_2</tex>, а все элементы, не входящие в данный член, сделаем равными 0нулю. Тогда эта функция будет представима в виде <tex>g_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> уберется.
# Присутствуют 3 три члена, без <tex>\oplus ~1</tex>: <tex>g_l= x_1 \land x_2 \oplus x_1 \oplus x_2</tex>. Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции ИЛИ.# Присутствуют 2 два члена, без <tex>\oplus ~1</tex>. Построив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить И, через НЕ и <tex>g_l</tex>. # Присутствует 1 один член. Выразим И, через НЕ и <tex>g_l</tex>.
В итоге получаем функцию НЕ, а также либо функцию И, либо функцию ИЛИ. Поскольку функцию И можно выразить через ИЛИ и НЕ, а функцию ИЛИ через И и НЕ, то мы получили базис И, ИЛИ, НЕ. Любую булеву функцию, не равную тождественному нулю, можно представить в форме [[СДНФ]], т. е. с помощью данного базиса. Если же функция равна тождественному нулю, то ее можно представить в виде <tex>x \land \overline{x}</tex>. Значит, полученные функции образуют полную систему, т. к. с их помощью можно выразить любую булеву функцию. Из этого следует, что 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> (конъюнкция, сложение по модулю 2два, константа 1один).Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[полином Жегалкина|полиномов Жегалкина]].
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты.
Максимально возможное число булевых функций в базисе — 4четыре.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций.
