Основные способы задания двоичных функций (стр. 2 )

Доказательство. Покажем, что по таблице функции однозначно определяются коэффициенты её многочлена Жегалкина. Воспользуемся методом неопределенных коэффициентов. Будем последовательно вычислять значения искомого многочлена на наборе из одних нулей, затем на наборе с одной единицей, затем – с двумя, и т. д. В результате получим систему:

Из первого уравнения находим , из второго ,…, из - ,

из - ,…, из последнего . Теорема доказана.

Определение 2.2.3. Конъюнкции , входящие в многочлен Жегалкина, называются одночленами. Степенью одночлена называется число входящих в него переменных (ранг конъюнкции). Степенью нелинейности (порядком) многочлена Жегалкина функции (обозначается ) называют максимальную из степеней входящих в него многочленов.

Многочлен Жегалкина можно вычислять исходя из ДНФ или СДНФ

функции , выразив операции дизъюнкция и отрицание через операции конъюнкция и сложение по модулю два :

Пример 2.2.4.

=

=

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

Поскольку каждую двоичную функцию можно задать своим многочленом Жегалкина, СДНФ или СКНФ, то, заменив все используемые в этих формулах операции на их выражения (по приведенным выше формулам) и раскрыв затем скобки получаем для всякой двоичной функции эквивалентную запись в виде некоторого действительного многочлена. Вместе с тем, можно заметить, что такая запись неоднозначна. Например, функцию можно представить действительными многочленами вида :

Перечисленные многочлены при и принимают значения 1 и 0 соответственно. Все многочлены в этом примере обладают той особенностью, что они содержат степени переменной , в то же время для двоичных переменных очевидны равенства:

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

Теорема 2.2.4. Любая двоичная функция однозначно представляется в виде следующего действительного многочлена :

все коэффициенты, которого являются целыми числами.

Доказательство. Полностью аналогично тому, которое было приведено в теореме 2.2.2. Необходимо только заменить операцию «» на «+».

Ниже, говоря «действительный многочлен», будем всюду иметь в виду определенный в теореме 2.2.4 многочлен

§ 2.3. Теорема о разложении в ряд Фурье.

Сопоставим каждому двоичному вектору линейную двоичную функцию ( сокращенно ()), и определим функции :

Например, векторам и соответствуют из функции

соответственно. Всего имеется функций вида . Как показывает следующая лемма, они образуют ортогональную систему функций.

Лемма 2.3.1. Для любых векторов справедливы равенства

Доказательство. Сначала заметим, что

Поскольку линейная функция при принимает значение 0 ровно . Теперь

. Отсюда и следует утверждение леммы.

Теорема 2.3.2. (о разложении в ряд Фурье). Для всякой двоичной функции имеется единственное разложение вида : , где коэффициенты являются рациональными числами. При этом значения коэффициентов определяются равенствами

.

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

Поскольку в последней сумме будет только одно нулевое слагаемое при y=x.

Покажем теперь, что коэффициенты однозначно определяются по функции . Предположим, существует другое разложение . Тогда . Домножив обе части этого равенства на для и просуммировав по полученные равенства, получаем :

Отсюда . Так как b-произвольный вектор из получаем требуемое утверждение.

Определение 2.3.2. Коэффициенты , , называется коэффициентами Фурье функции .

Лекция №3

Полнота и замкнутость. Критерий полноты системы. Функционально полные системы. Замкнутые классы булевых функций.

§3.1 Полнота и замкнутость. Функционально полные системы.

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

Имеют место следующие свойства замыкания:

Свойство 3.1.2. .

Свойство 3.1.3.

Свойство 3.1.4.

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

Определение 3.1.5. Система функций называется полной, если .

Утверждение 3.1.6. Система функций является полной системой функций.

Доказательство. Очевидно, что элементарная конъюнкция является формулой над . Отсюда следует, что дизъюнкция любого числа элементарных конъюнкций является формулой над . Отсюда и из равенства (2.1.13) следует, что любая функция ,представима над формулой . Следовательно, .

Утверждение 3.1.7. Система функций является полной системой функций.

Доказательство. Очевидно, что , из равенства следует, что . Отсюда и из свойств 3.1.3 и 3.1.4 имеем , т. е. . Таким образом, показано, что и . Полученные включения означают, что

Утверждение 3.1.8. Система функций является полной системой функций.

Доказательство. Очевидно, что , из равенства следует, что . Отсюда и из свойств 3.1.3 и 3.1.4 имеем , т. е. . Таким образом, показано, что и . Полученные включения означают, что

Утверждение 3.1.9. Система функций является полной системой функций, где - двоичная функция, называемая штрихом Шеффера, задается таблицей

0  0 0  1 1  0 1 1	1 1 1 0

Доказательство. Очевидно, что . Из равенств:

и

следует, что . Далее доказательство текстуально аналогично доказательству утверждения 3.1.8 при подстановке вместо

Утверждение 3.1.10. Система функций , является полной системой функций.

Доказательство. Очевидно, что . Из равенства следует, что . Далее доказательство текстуально аналогично доказательству утверждения 3.1.8 при подстановке вместо

Утверждение 3.1.11. Система функций , является полной системой функций, где - двоичная функция, называемая стрелкой Пирса, задается таблицей:

0  0 0  1 1  0 1 1	1 0 0 0

Доказательство. Очевидно, что . Из равенств : и следует, что . Далее доказательство текстуально аналогично доказательству утверждения 3.1.8 при подстановке вместо и вместо

Определение 3.1.12. Каждая двоичная функция сама одна образующая полную систему называется Шефферовой функцией.

Пример 3.1.13. Функция является Шефферовой функцией. Это следует из утверждения 3.1.9.

Пример 3.1.14. Функция является Шефферовой функцией. Это следует из утверждения 3.1.11.

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

§3.2. Замкнутые классы булевых функций.

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

Замечание 3.2.2 Полное описание всех замкнутых классов было дано американским математиком Э. Постом. В частности, он доказал, что множество всех замкнутых классов булевых функций счетно и в каждом замкнутом классе можно выделить конечную подсистему , порождающую , т. е. имеющую своим замыканием класс , т. е. .

Определение 3.2.3. Булева функция называется функцией, сохраняющей константу 0, если .

Класс всех булевых функцией, сохраняющих константу 0, обозначим .

Определение 3.2.4. Булева функция называется функцией, сохраняющей константу 1, если .

Класс всех булевых функцией, сохраняющих константу 1, обозначим .

Определение 3.2.5. Булева функция называется линейной, если , такие ,что .

Класс всех булевых линейных функций обозначим через .

Определение 3.2.6. Булева функция называется аффинной функцией, если , такие, что .

Обозначим через класс всех булевых аффинных функций.

Определение 3.2.7. Булева функция называется самодвойственной функцией, если (3.2.8)

Класс всех булевых самодвойственных функций обозначим через S.

Далее определим понятие монотонной функции. Для этого нам необходимы некоторые дополнительные сведения. Изложим их. На множестве введем отношение , положив для наборов и : , где отношение на понимается как неравенство на множестве чисел {0,1}.

Несложно доказать, то отношение рефлексивно, транзитивно и антисимметрично, т. е. является отношением частичного порядка.

Определение 3.2.9. Булева функция называется монотонно возрастающей, или монотонной, если для любых наборов выполняется условие:

Замечание 3.2.10. Нульместные функции 0 и 1 также естественно считать монотонными.

Класс всех булевых монотонных функций обозначим через М.

Утверждение 3.2.11. Классы булевых функций и являются замкнутыми классами булевых функций.

Для доказательства данного утверждения нам необходимо определить понятие ранга формулы над классом .

Определение 3.2.12. Число всех символов функций из , встречающихся в формуле над , называется рангом формулы и обозначается через .

Замечание 3.2.13. Понятие ранга формулы над классом не следует путать с понятие ранга элементарной конъюнкции из определения 2.1.1.

Доказательство утверждения 3.2.11. Замкнутость перечисленных в утверждении 3.2.11 шести классов функций доказывается по одной и той же схеме. Проделаем это для какого-нибудь одного класса, например S.

Согласно определениям замыкания (определение 3.1.1) и замкнутого класса (определение 3.2.1) нам необходимо доказать, что любая функция, представимая формулой над S, принадлежит S. Докажем это индукцией по рангу формулы А, представляющей функцию .

Если , то , и утверждение очевидно, так как .

Пусть утверждение верно для всех , таких что , где .

Докажем, что утверждение верно и при .

Если , то А имеет вид: , где и - формулы меньших рангов, чем , т. е. . По предположению индукции формулы представляют булевы функции . Тогда для любых имеем:

Следовательно, удовлетворяет условию (3.2.8), т. е

§3.3 Критерий полноты системы булевых функций.

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

, , , , . (3.3.2)

(без доказательства).

Пример 3.3.3. Пусть функция задана таблицей 3.3.4

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	1 0 0 0 0 0 0 0

Таблица 3.3.4