45. Полнота.

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

F={конъюнкция, дизъюнкция, отрицание} – является функционально полной, так как любую булевую функцию можно представить в виде конъюнкций, дизъюнкций и отрицаний. Функционально полной будет любая система F, функции которой можно выразить через конъюнкции, дизъюнкции и отрицания. Для любой логической функции можно записать, заменив в ней все операции, отличные от конъюнкции, дизъюнкции и отрицания на эти функции.

F={конъюнкция, отрицание} – является полной так как по закону де Моргана и двойному отрицанию можно получить дизъюнкцию.

С точки зрения функциональной полноты система функций F={конъюнкция, дизъюнкция, отрицание} можно считать избыточной, так как либо конъюнкцию либо дизъюнкцию можно выразить через отрицание и дизъюнкции или конъюнкцию.

Однако

46. Лемма о немонотонных функциях.

Если система функций содержит немонотонную функцию, то подстановкой констант можно получить отрицание, то есть существует такая подстановка n-1 константы, что получится функция одной переменной, реализующая отрицание.

Существует сигма и тау такие что сигма>тау

f(сигма)>f(тау).

Это возможно, когда f(сигма)=1, а f(тау)=0

Если наборы сигма и тау отл к комп., то в этих к компонетах а наборе сигма стоят 1, а в наборе тау – 0.

Если взять набор сигма и заменить поочередно в этих к комп. 0 и 1, то пол последовательность омега.

<₁<₂<…<_k-1<

Любые 2 набора стоящие радом отличаются только в одном комп., то есть я вл. соседними; очевидно, что в такой цепочке найдуться 2 набора _j и _j+1 такие что f(_j)=1 f(_j+1)=0, так как они отлиаются только в одном комп., то их можно рассматривать как функции одной переменной и получить следующее:

f(0)=1; f(1)=0 из немонотонной функции путем подстановки констант можно получить отрицание.

47. Лемма о нелинейных функциях.

Если f(x1, x2, …, xn) – нелинейная функция, то с помощью подстановок констант и использования отрицания из нее можно получить конъюнкцию и дизъюнкцию.

Рассмотрим функцию f(x1, x2, …, xn) – нелин.: значит ее полином Жегалкина содержит конъюнкцию нескольких переменных. Рассмотрим самую короткую из конъюнкций:

k=x₁x₂…x_k

Пусть x₃…x_k=1, тогда k=x₁x₂

Вместо x₁x₂ рассмотрим роазные варианты подстановки констант, в этом случае коньюнкция будет иметь вид:

k=x₁x₂+x₁+x₂+

На каждом наборе , ,  посчитаем fi.

Поскольку каждая из fi является результатом подстановки констант в f, то получим конъюнкцию и дизъюнкцию.

48. Функциональная полнота. Первая теорема о функциональной полноте.

Теорема:

Для того, чтобы система ф-ций была функционально полной в слабом смысле необходимо и достаточно, стобы она содержала хотя бы одну немонотонную и хотя бы одну не линейную ф-ции.

Необходимость:

Классы монотонных и линейных функций замкнуты и содержат константы 0 и 1, поэтому если система функций содержаит немонотонную и нелинейную ф-ции, то их нельзя получить с помощью суперпозиций ф-ций из F.

Достаточность:

Пусть система содержит нелинейную и немонотонную функции, тогда по лемме 1 из немонотонной функции можно получить отрицание, а по лемме 2 из нелинейной ф-ции можно получить дизъюнкции, конъюнкцию с использованием отрицания.

Пусть задана система функций F={,}. Система ф-ций является полной в слабом смысле, так как конъюнкция является не линейной, а  - немонотонной.

Является функция полной в слабом смысле так как она реализует константу 0, а константу 1 невозможно получить. Из того что конъюнкция – не лин. то по Лемме 2 можно получить дизъюнкцию и отрицание, т.к. сложение по модулю 2 – не монотонная то с его помощью можно получить отрицание.