Учебник по дискретной математике

Оглавление
n1.doc (26 стр.)
Скачать
1   ...   10   11   12   13   14   15   16   17   ...   26

Теорема Жегалкина



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

Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:

, s = 0, 1, ..., n. Доказательство. Любая функция из Р2 может быть представлена формулой над {x1 & x2, x1x2, 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функции f(x1, ..., xn) от n переменных. Мы знаем, что всего таких функций, т.е. их таблиц истинности , 2n. Подсчитаем число различных полиномов Жегалкина от n переменных, т.е. число вариаций вида: . Число наборов равно числу всех подмножеств множества { x1, ..., xn }, сюда входит и пустое множество (если s = 0). Число подмножеств множества из n элементов равно 2n , а так как каждый набор входит с коэффициентом , принимающим два значения: 0 или 1, то число всевозможных полиномов будет . Так как каждому полиному соответствует единственная функция, число функций от n переменных равно числу полиномов, то каждой функции будет соответствовать единственный полином.

Определение. Функция f(x1, ..., xn), полином Жегалкина для которой имеет следующий линейный относительно переменных вид: f = а0 а1х1 а2х2 ... аnхn, называется линейной.

Лемма о нелинейной функции. Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию.

Доказательство. Пусть f(x1, ..., xn) – нелинейная функция. Тогда полином Жегалкина содержит для нее слагаемое, в котором присутствует произведение xixj. Будем считать для простоты, что x1x2 в многочлене Жегалкина является этим произведением. Произведя группировку слагаемых, функцию f представим в виде

Функция h0 не есть тождественный нуль, иначе в полиноме Жегалкина отсутствует слагаемое с произведением x1x2. Тогда существует набор (3, …, n) из 0 и 1, для которого h0(3, …, n) = 1. Пусть h1(3, …, n) = a, h2(3, …, n) = b, h3(3, …, n) = c. Тогда

Построим функцию:

где d = abc. Если d = 0, то h(x1, x2) = x1x2. Если d = 1, то h(x1, x2) = x1x2  1 и тогда Лемма доказана.

Функция f(x1, ..., xn) сохраняет константу a  {0, 1}, если f(a, …, a) = a.

Пример 4. Функция xy сохраняет 0, сохраняет 1. Функция xy сохраняет 1 и не сохраняет 0.

2.6. Замыкание и замкнутые классы



Определение 1. Пусть MР2. Замыканием М называется множество всех функций из P2, которые можно выразить формулами над М. Замыкание М обозначается [M].

Определение 2. Множество функций М называется замкнутым классом, если [M]=M.

Пример 1.

1) P2 – замкнутый класс.

2) Множество {1,x1x2} не является замкнутым классом. Его замыканием будет класс линейных функций: [{1, x1 x2}] = {f(x1, ..., xn) = c0 c1x1 cnxn}. Действительно, по определению формулы над М, функция f(G1, x3), где f – есть сумма по модулю 2, G1 – функция х1 х2, будет формулой над М: f(G1, x3) = (x1 x2) x3.


Замечание. В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному:

М – полная система, если [M] = P2.

3) A = {f(x1, ..., xn) f(1, 1, ..., 1) = 0} – незамкнутый класс. Возьмем формулу над этим множеством. Пусть f, g1, ..., gn A, т.е. f(1, 1, ..., 1) = 0, g1(1, 1, ..., 1) = 0, тогда f(g1, ..., gn) [A]. Посмотрим, принадлежит ли функция f(g1, ..., gn) множеству А. f(g1(1, ..., 1), g2(1, ..., 1), ..., gn(1, ..., 1) = f(0, ..., 0)), но f(0, ..., 0) не обязано быть равным 0. Действительно, пусть g1(x1, x2) = x1 x2, g2(x) = xA. Возьмем g2(g1(x1, x2)) = x1 x2 [A], g2(g1(1, 1)) = 1 1 = 0, следовательно, g2(g1(x1, x2)) A, отсюда [A] A и А – незамкнутый класс.

Важнейшие замкнутые классы в Р2



1) Т0 - класс функций, сохраняющих константу 0.

Т0 = { f(x1, ..., xnf(0, ..., 0) = 0, n = 1, 2, ...}. Покажем, что Т0 является собственным подмножеством Р2, т.е. Т0  и Т0 Р (не совпадает с Р2). Для этого достаточно привести примеры функций, входящих в Т0, и примеры функций из Р2, не входящих в Т0: x1&x2, x1x2, xТ0 и x1|x2, x1x2, Т0. Покажем далее, что [Т0] = Т0. Вложение Т0 [ Т0] очевидно, так как по определению формулы любая функция из Т0 является формулой над Т0 и, следовательно, принадлежит [Т0]. Покажем, что [Т0] Т0. Для этого надо показать, что Ф = f(f1, ..., fm) [ Т0], если все функции f, f1, f2, f3, ..., fm  Т0. Надо заметить, что в формуле в качестве функции f1 могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классу Т0, поэтому достаточно показать, что Ф = f (f 1, ..., fm)  Т0. Для этого рассмотрим следующую функцию: Ф(0, ..., 0) = f (f 1(0, ..., 0), f 2(0, ..., 0), ...) = f(0, ..., 0) = 0.

Число функций, зависящих от n переменных и принадлежащих Т0, будет равно
2) T1 класс функций, сохраняющих константу 1.

T1 = {f(x1, ...) f(1, 1, ...) = 1}; x1&x2, x1x2, xT1, х1х2, x1x2T1, следовательно Т1 – собственное подмножество Р2.

Покажем, что [T1] T1, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т1, можно рассмотреть Ф = f(f1, ..., fn) [T1], где f, f1, ..., fn T1. Найдем Ф(1, ..., 1) = f(f1(1, ..., 1), ..., fn(1, ..., 1)) = f(1, ..., 1) = 1, следовательно, Ф = f(f1, ..., fn) T1, отсюда следует [T1] = T1.
3) S класс самодвойственных функций.

S = {f(x1, ...)f* = f }; x, , x1x2x3S, x1&x2, x1x2, x1x2S, следовательно, S – собственное подмножество Р2. |S(n)| = . Покажем, что [S]S. Ф = f(f1, ..., fn) [S], если f, f1, ..., fn S, а также, что Ф S. По принципу двойственности, Ф* = f*(f1*, ..., fn*) = f(f1, ..., fn) = Ф, отсюда S – замкнутый класс.
4) Lкласс линейных функций.

L = {f(x1, ...) f = c0c1x1...cnxn}; очевидно, L , с другой стороны

L P2, так как x1&x2 L. Заметим, что тождественная функция принадлежит L и |L(n)| = 2n+1. Покажем, что [L] L. Рассмотрим Ф = f(f1, ..., fm), где f, f1, ..., fn L. Тогда Ф = а0 а1(с10 с11х1 ... c1nxn1)  a2(c20  c21x1 c22x2...c2nxn2)...an(cm0 cm1x1 ...  cmnxnm) = в0 в1х1 ... вnхnФL.
5) Мкласс монотонных функций.

Определение. Набор = (1, ..., n) предшествует набору = (1, ..., n) и обозначается , если для 1in ii, например: = (0010), = (0110), тогда . Не любые два набора находятся в отношении предшествования, например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования () является отношением порядка на множестве наборов длины n, множество таких наборов будет частично упорядоченным множеством по отношению к операции.

Определение. Функция f(x1, ..., xn) называется монотонной, если для двух наборов и , таких что , выполняется f()f(). Функции 0, 1, x, x1&x2, x1x2 M, x1x2, x1 x2, x1 ~ x2 M.

Для числа монотонных функций, зависящих от n переменных, существуют оценки сверху и снизу, но точное число сосчитать не удается. Покажем, что М замкнутый класс. Рассмотрим функцию Ф[M], Ф = f(f1, ..., fm), где f, f1, ..., fmM, причем можем считать, что все они зависят от n переменных. Пусть набор = 1, ..., n), = (1, ..., n). Рассмотрим Ф1, ..., n) = f(f11, ..., n), …, fm1, ..., n)) и Ф(1, ..., n) = f(f1(1, ..., n), ..., fm(1, ..., n)). Здесь f1() f1(), ..., fm() fm(), тогда набор (f1(), ..., fm())(f1(), ..., fm()), но тогда Ф() Ф(), так как fM, отсюда Ф = f(f1, ..., ) – монотонная функция.

Определение. Функция f есть суперпозиция над M, если f реализуется некоторой формулой над M.

Лемма о немонотонной функции. Отрицание можно получить суперпозицией констант 0 и 1, тождественной функции и немонотонной функции.

Доказательство. Пусть f(x1, ..., xn) – немонотонная функция. Тогда существуют наборы и , для которых но Пусть i1, …, ik есть все те номера аргументов, для которых , p=1, …, k. На всех остальных аргументных местах j имеем j = j. В выражении заменим нули на местах i1, …, ik на x. В результате получим функцию g(x), для которой g(0) = f() = 1 и g(1) = f() = 0. Функция g(x) является отрицанием.

Классы T0, T1, L, S, M пересекаются, но не совпадают, что видно из следующей таблицы, где «+» означает, что функция принадлежит данному классу и «-» – не принадлежит.




T0

T1

L

S

M

x

+

+

+

+

+



-

-

+

+

-

0

+

-

+

-

+

1

-

+

+

-

+

x1x2

+

+

-

-

+

A={x, , 0, 1, x1x2) не является полной системой функций так как всегда есть функции Р2 не входящие в эти классы.
Портфель ученика
© lib.rushkolnik.ru
При копировании укажите ссылку.
обратиться к администрации