Полные системы функций. Теорема Поста о полной системе функций — различия между версиями
Algo1s041 (обсуждение | вклад) м (→Полные системы функций) |
Algo1s041 (обсуждение | вклад) м |
||
Строка 59: | Строка 59: | ||
{{ | {{ | ||
Теорема|statement= | Теорема|statement= | ||
− | Набор булевых функций K является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция. | + | Набор булевых функций <tex>K</tex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция. |
|proof= | |proof= | ||
Строка 65: | Строка 65: | ||
===== Необходимость. ===== | ===== Необходимость. ===== | ||
− | Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора | + | Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора <tex>K</tex> входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор <tex>K</tex> не мог бы быть полным. |
===== Достаточность. ===== | ===== Достаточность. ===== | ||
− | # Рассмотрим функцию, не сохраняющую ноль {{---}} <tex>f_0</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) = 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>f_0(1) = 0</tex>, тогда <tex>f_0(x, x, x, \dots, x) = \neg x</tex>. | ||
− | # Рассмотрим функцию, не сохраняющую один {{---}} <tex>f_1</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) = 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_1(0) = 1</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = \lnot x</tex>. | ||
Строка 78: | Строка 79: | ||
* Мы получили функцию <tex> \neg </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}, | + | Используем несамодвойственную функцию <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>. |
Рассмотрим <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(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>. | ||
Строка 84: | Строка 85: | ||
Таким образом мы получили одну из констант. | Таким образом мы получили одну из констант. | ||
− | *Мы получили <tex> \neg </tex> и <tex>0</tex> | + | *Мы получили <tex> \neg </tex> и <tex>0 \Rightarrow</tex> имеем константу, равную <tex>1</tex>, поскольку <tex>\lnot 0 = 1</tex>. |
− | *Мы получили <tex> \neg </tex> и <tex>1</tex> | + | *Мы получили <tex> \neg </tex> и <tex>1 \Rightarrow</tex> имеем константу, равную <tex>0</tex>, поскольку <tex>\lnot 1 = 0</tex>. |
*Мы получили <tex>1</tex> и <tex>0</tex>. | *Мы получили <tex>1</tex> и <tex>0</tex>. | ||
Строка 120: | Строка 121: | ||
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы. | Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы. | ||
− | + | Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре. | |
Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций. | Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций. | ||
− | == Источники == | + | == Источники информации == |
* [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%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 Википедия — Критерий Поста] |
Версия 22:24, 18 января 2016
Содержание
Полные системы функций
Определение: |
Если любая булева функция, являющаяся суперпозицией функций некоторого множества, принадлежит этому множеству, то такое множество называют замкнутым (англ. closed set). |
Определение: |
Замыканием (англ. сlosure) множества функций называется такое подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества. |
Определение: |
Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций. |
Определение: |
Полная система функций называется безызбыточной (англ. irredundant functions), если она перестает быть полной при исключении из неё любого элемента. |
Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
- функции, сохраняющие константу и ,
- самодвойственныые функции ,
- монотонные функции ,
- линейные функции .
Замкнутые классы булевых функций
Класс функций сохраняющих ноль
.Определение: |
Говорят, что функция сохраняет ноль, если | .
Класс функций сохраняющих единицу
.Определение: |
Говорят, что функция сохраняет один, если | .
Класс самодвойственных функций
.Определение: |
Говорят, что функция самодвойственна (англ. self-dual), если | . Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.
Класс монотонных функций .
Определение: |
Говорят, что функция монотонна (англ. monotonic function) , если | .
Класс линейных функций .
Определение: |
Говорят, что функция линейна (англ. linear function), если существуют такие
| , где , что для любых имеет место равенство:
Количество линейных функций от
переменных равно .Функция является линейной тогда, и только тогда, когда в ее полиноме Жегалкина присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью преобразования Мебиуса.
Формулировка и доказательство критерия Поста
Теорема: |
Набор булевых функций является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов , иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция. |
Доказательство: |
Необходимость.Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор не мог бы быть полным.Достаточность.Докажем, что если набор не содержится полностью ни в одном из данных классов, то он является полным.
Таким образом, возможны четыре варианта:
Используем несамодвойственную функцию . По определению, найдется такой вектор , что . Где .Рассмотрим , где либо , при . Либо , при . Нетрудно заметить, что . Таким образом мы получили одну из констант.
Рассмотрим немонотонную функцию . Существуют такие , что , , зафиксируем все , тогда .В итоге имеем три функции: , , .Используем нелинейную функцию полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем и . Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов). . Среди нелинейных членов (ее представления в видеРассмотрим несколько вариантов:
В итоге получим функциюСДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде . , а также либо функцию , либо функцию . Поскольку функцию можно выразить через и , а функцию через и , то мы получили базис , , . Любую булеву функцию, не равную тождественному нулю, можно представить в форме
|
Примеры
Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов
, , , , .В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера или стрелку Пирса.
Широко известны такие полные системы булевых функций:
- (конъюнкция, дизъюнкция, отрицание);
- (конъюнкция, сложение по модулю два, константа один).
Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы.
Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему
можно назвать базисом класса линейных функций.