![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Рассмотрим систему функций:
,
,
,
. (***)
Суперпозицию функций системы (***) можно преобразовать, пользуясь правилами элементарной алгебры и специальными правилами:
,
,
.
В частности, если раскрыть скобки и привести подобные члены, то полученная сумма «одночленов» называется многочленом Жегалкина.
Теорема 1: Для любой функции алгебры логики существует многочлен Жегалкина, задающий эту функцию.
Доказательство: Действительно, в предыдущем параграфе было доказано, что система функций является полной в
. Полную систему образует и система функции
, так как
. Теорема доказана.
Можно доказать, что каждая функция представляется в виде многочлена Жегалкина единственным образом. Это следует из доказанной теоремы и того факта, что число многочленов Жегалкина от переменных
равно
, т. е. совпадает с числом всех функций алгебры логики от этих переменных.
Определение 1: Функция называется линейной, если имеет место соотношение:
.
Теорема 2: Функция, представленная многочленом Жегалкина, существенно зависит от всех входящих в него переменных.
Доказательство: Пусть, например, – переменная, о которой идёт речь в условии теоремы. Сгруппируем члены, и вынесем
за скобки. Получим:
,
где функция – не равна тождественно нулю. В противном случае (в силу единственности представления функции многочленом Жегалкина)
не входила бы в многочлен для
. Возьмем значения переменных
, на которых
равна
. Тогда значение
будет зависеть от значения
.
Замечание: Множество всех линейных функций составляет замкнутый класс.
Для того чтобы произвольную функцию представить многочленом Жегалкина, нужно выразить все операции через конъюнкцию и отрицание, учитывая, что . Затем следует привести подобные слагаемые, используя при этом правила, указанные выше:
,
,
.
Далее будет рассмотрен класс функций, обладающих несколько иными свойствами.
Упорядочим множество , полагая
. Поскольку мы будем иметь дело с функциями от нескольких переменных, то введем частичное упорядочение двоичных наборов одинаковой длины.
Определение 2: Пусть — двоичные наборы. Будем говорить, что
предшествует
(обозначение
), если
для всех
, причем, по крайней мере, для одного
, имеет место строгое неравенство. Будем писать:
, если
или наборы
и
совпадают.
Это упорядочение является только частичным, так как не всякие наборы можно сравнивать.
Определение 3: Функция алгебры логики называется монотонной, если для всяких наборов
таких, что
имеем неравенство:
.
Например, нетрудно заметить, что константы, конъюнкция, дизъюнкция являются монотонными функциями.
Теорема 3: Множество всех монотонных функций образует замкнутый класс.
Доказательство: Т.к. функция — монотонна, то достаточно показать, что если функции
,
,
,...,
являются монотонными, то функция монотонной будет также функция:
.
Рассмотрим два произвольных набора таких, что
. В этом случае
, где
. Следовательно,
и, значит, в силу монотонности функции имеет место неравенство:
. Теорема доказана.
Дата публикования: 2014-11-03; Прочитано: 1391 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!