Функционально полные системы функций. Определение. Система функций S = {f1 fn} называется полной, если любую булеву функцию можно представить в виде суперпозиции функций из этой системы (т.е

Определение. Система функций S = {f₁…f_n} называется полной, если любую булеву функцию можно представить в виде суперпозиции функций из этой системы (т.е. можно представить формулой, куда входят только функции из этой системы).

"f = F_S

S = {V, &, NOT или отрицание - --}

Теорема 1.

Если система S1 полна, и любая ее функция представима в виде суперпозиции функций из системы S2, то и система S2 также полна.

Доказательство

S₁= {ф₁…ф_k}

"f_i = Е_S2 - условие.

"f = FS = FS₂ – ч.т.д.

Мы заменили все функции суперпозицией из S2.

Теорема 2.

Если система функций полна, то будет полной и система, состоящая из двойственных функций.

Доказательство следует из принципа двойственности.

Основные типы функционально полных систем.

S = {&, V, NOT}

S = {&, NOT}

____

_ _

X V Y = (XY)

S = {/} – полна.

___

X/Y = (XY)

X/X = NOT(XX) = NOT(X)

S = {¯}

Система Жегалкина {+,&,1}.

NOT (X) = x+1

X V Y = xy+x+y

Многочлены Жегалкина.

Одночленом будем называть любое выражение вида

А * X₁X₂X₃…X_n

A = {0 или 1} x₁x₃ – одночлен.

Многочленом Жегалкина называется сумма по модулю 2 различных одночленов.

А1X1+А2X2+А3X3+A4X1X2 + A5X1X3+A6X2X3+A7X1X2X3 – общий вид многочлена Жегалкина для трех переменных. Чтобы выписать общий вид многочлена Жегалкина для нужного числа переменных нужно перебрать все возможные конъюнкции переменных и сложить их по модулю 2 друг с другом, а также с переменными, входящими в функцию. Перед каждой конъюнкцией нужно расставить буквенные коэффициенты.

Теорема

Любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде многочлена Жегалкина.

Доказательство на лекции 8.

Поиск многочлена Жегалкина (МЖ) для любой выбранной булевой функции производится методом неопределенных коэффициентов. Для этого нужно выписать общий вид МЖ для нужного числа переменных, затем, подставив искомые значения переменных в МЖ, приравнять его к функции на нужном векторе. Таким образом получается система уравнений с неизвестными числами А. Решив ее, мы получим искомый МЖ.

Лекция 8

Продолжение темы «Многочлены Жегалкина»

Теорема.

Любая булева функция представима в виде многочлена Жегалкина (МЖ).

Доказательство

1. Существование

F = ДНФ = F{&,V, NOT}

X V Y = XY+X+Y

NOT(X) = X+1

Из этого следует, что функция представима в виде МЖ.

2. Единственность

Сосчитаем МЖ

ЭК без отрицания 2ⁿ – 1 + 1

Всего разных многочленов Жегалкина 2^N – 1, где N = 2ⁿ

Это число совпадает с числом разных булевых функций, отличных от нуля.

Отсюда следует, что любой булевой функции соответствует единственный многочлен Жегалкина. Теорема доказана полностью.