Булевы Функции: Функциональная полнота.
В алгебре булевых функций 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 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
Стр(207) Задача 2.1 Выясните при каких значениях а и в функции f(x,y)=not((x v a)v(a&b)) g(x,y)=(x v b)-(a & y) – в зависимости от значений а и в возникают 4 случая, если одна из функций является штрихом шейфера то независимо от другой система полна, если из полученной системы можно получить какую либо полную, то полна. Если она целиком содержится в одной из подалгебрах
F(x,y,z)=x+y+z
{0,1,*,f} – полна и независима
Not(x)=X+1+0=f(x,1,0)
Покажем что С1.
Пусть система булевых функций удовлетворяет условию теоремы, те там найдется покрайней мере одна функция не попавшая в особые под алгебры. В частности там найдется функция не принадлежащая С0. Перенумеруем переменные в этой функции обозначив их одной буквой Х. Таким образом мы получаем функцию f(x) такая что f(0)=1 - F(1)=0 & 1. Аналогично из данной системы можно получить функцию G(x) такую что G(1)=0 и G(0)=0 & 1.
Случай 1.
| X | F | G |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
F(x)=not(x), G(x)=0 - В этом случае имеем {not(x),x,0,1}.
Случай 2.
| X | F | G |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
F(x)=g(x)=not(x) - {not(x),x}
Случай 3.
| X | F | G |
| 0 | 1 | 0 |
| 1 | 1 | 0 |
{1,0}
Случай 4.
| X | F | G |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
{1,not(x),x,0}
Четвертый случай фактически совпадает с первым, второй и третий недобор функций.
Упр.1
Доказать что с помощью not и не самодвойственной функции можно получить константу(Указания: С(x) является константой если С(not(x)), случай 2 сводится к случаю 1).
Упр.2
Доказать что через не монотонные функции можно получить отрицание(Указание: T(x1,x2,…,xn) не монотонная если существуют наборы J1,j2,…jn; B1,B2,…,Bn так чтоб f(J)>f(B), тк функция дискретна изменение функции осуществляется скачком за счет изменения лишь одного значения элемента.)
Упр.3
Итак, во всех четырех случаях мы получаем набор {not(x),x,0,1} . Доказать что с помощью нашего множества и не линейной функции можно получить умножение(Указание: Пусть функция S(x1,x2,…,xn), то есть в ее полиноме Жигалкина есть одночлены выше первой степени, пусть для определенности переменные x1,x2 создают эту степень, вынесем x1,x2 из всех одночленов затем вынесем Х1, а затем Х2, в результате мы получим представление S(x1,x2,…,xn)=x1,x2,g1(x3,…,xn)+x1,g2(x3,…,xn)+x2g3(X3,…,xn)+g4(x3,…,xn) ) g1(x3,…,xn) – не является 0, те при определенном наборе таким образом из нашей системы можно получить систему.
Замечание: Теорема Поста, означает что C0,C1,D,M,L – все максимальные под алгебры от P2. В P2 любая под алгебра содержится в максимальной под алгебре; поэтому результат Поста улучшить нельзя.