Булевы Функции Функциональная полнота
Булевы Функции: Функциональная полнота.
В алгебре булевых функций P2=<P2;S>
S – Операцией является подстановка функции в функцию, суперпозиция.
Порождающее множество алгебры P2, принято называть полной системой булевых функций.
Система булевых функций является независимой, если не одной функцией этой системой нельзя выразить через остальные.
Система функций полна, если через неё можно выразить любую булеву функцию. Примеры полных систем:
Любую булеву функцию можно представить в нормальной форме используя только операции +,*,not.
{&, v, not}. Конъюнкцию с помощью законов Деморгана можно выразить через остальные элементы системы:
X&Y=not (not(X) v not(Y)) – поэтому система {v, not}. Аналогично по другому закону Деморгана можно получить v через &, not поэтому (&, not).
Импликация выражается через Дизъюнкцию и Отрицание: X v Y = not(X) - Y, следовательно {-, not} также полная.
Через сложение (по модулю 2), умножение и 1 можно выразить основные логические операции:
1) X&Y=X*Y
2) X v Y=X+Y+XY
3) Not(X)=X+1
4) X -- Y=X+Y+1
Поэтому {+,*,1} система полна, и каждую булеву функцию в виде многочлена от Н переменных, который в честь автора Полином И.И. Жегалкина.
Представление функции в форме Полинома Жегалкина. Следовательно, можно говорить о линейных булевых функциях, то есть функции вида f(X1,…,Xn)=A1X1+…+AnXn+B, обозначим буквой L множество всех линейных функций данного вида.
Система булевых функций полна, если через нее можно выразить какую-нибудь полную систему. Не пустое, собственное подмножество множество P2, замкнутое относительно суперпозиции образует под-алгебру.
F,g1,…,gn€H=>f(g1,g2,…,gn)€H, H<P2
Под-алгебра задается нетривиальным функцией, сохраняющимся при суперпозиции.
Любая подсистема, целиком лежащая в некоторой под алгеброй, неполна.
Примеры под алгебр:
1) Множество линейных функций L образует под алгебру. L – замкнутая относительно суперпозиции. Любое множество линейных функций не образует полную систему: линейные функции порождают снова линейные функции. Поэтому, например система {0,1,+, not, --} не полна.
2) Функция f сохраняет ноль если f(0,…,0). Множество C0 всех таких функций образует под алгебру. Любое множество функций целиком лежащее в С0 не образует полную систему. Например {&, v, +, 0}.
3) Функция F сохраняет 1 если f(1,1,…,1)=1 Любое множество функций сохраняющих единицу не когда не образуют полную группу.
4) Функция называется монотонной если для любых наборов. Множество М всех монотонных функций образует под алгебру. Любое множество монотонных функций не является полной системой.
5) NotF(notX1, notX2,…,notXn) называется двойственной для функции Х. Например & и v. Отображение F|-notF согласованно с суперпозицией. Значит что отображение. Функция самодвойственная если F=notF. Множество Д самодвойственных функций образует подалгебру.
Теорема (Поста): Система функций полна тогда и только тогда когда она не содержится целиком не в одной из под алгебр.
1) Множество линейных функций L образует под алгебру. L – замкнутая относительно суперпозиции. Любое множество линейных функций не образует полную систему: линейные функции порождают снова линейные функции. Поэтому, например система {0,1,+, not, --} не полна.
2) Функция f сохраняет ноль если f(0,…,0). Множество C0 всех таких функций образует под алгебру. Любое множество функций целиком лежащее в С0 не образует полную систему. Например {&, v, +, 0}.
3) Функция F сохраняет 1 если f(1,1,…,1)=1 Любое множество функций сохраняющих единицу не когда не образуют полную группу.
4) Функция называется монотонной если для любых наборов. Множество М всех монотонных функций образует под алгебру. Любое множество монотонных функций не является полной системой.
5) NotF(notX1, notX2,…,notXn) называется двойственной для функции Х. Например & и v. Отображение F|-notF согласованно с суперпозицией. Значит что отображение. Функция самодвойственная если F=notF. Множество Д самодвойственных функций образует подалгебру.
В доказательстве лишь нуждается достаточность. В действительности всегда найдется функция не попавшая сразу в 2. И поэтому число элементов меньше либо равно 4. Это число уменьшить нельзя: существуют полностью независимые системы булевых функций в точности из 4х элементов.
Упр1. Полна и независима???? Кто??? Для доказательство полноты достаточно выразить отрицание. Для доказательства независимости достаточно указать разделяющую под алгебру. Наименьшее число в полной системе = 1.
Упр2. X|Y = not(x) v not(y) Шефферт . Доказать что {|}{⬇} - полные системы
Упр3. Выяснить Существуют ли полные системы отличные от Стрелки Пирса и Штриха Шефферта.(будем искать функцию с помощью ее таблицы значений)
| X | Y | ||||
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 |