Вопрос 4: Теорема Жегалкина о представимости функции алгебры логики полиномом.

Монотонной конъюнкцией от переменных x1,…, xn называется любое выражение вида

все переменные различны

(ij ≠ ik, если j ≠ k); либо просто 1.

Полиномом Жегалкина над

X 1, …, Xn называется выражение вида

где l ≥ 1 и все Kj суть различные монотонные конъюнкции над X 1, …, Xn; либо константа 0.

Теорема 5 (теорема Жегалкина). Любую функцию алгебры логики f (X 1, …, Xn) можно

единственным образом выразить полиномом Жегалкина над X 1, …, Xn.

Доказательство. 1) Докажем существование полинома. Система { x · y, x ⊕ y, 1 } полна, следовательно, любую функцию алгебры логики f (X 1, …, Xn) можно реализовать формулой над { x · y, x ⊕ y, 1 }. a) Пользуясь дистрибутивностью, раскрываем все скобки в этой реализации и получаем, что

— конъюнкция переменных и единиц.

b) Преобразуем все полученные конъюнкции в элементарные, пользуясь при этом коммутативностью и соотношениями x · x = x, 1 · 1 = 1 и A · 1 = A. Очевидно, все конъюнкции станут монотонными. c) Преобразуем полученную сумму в полином Жегалкина, пользуясь при этом соотношениями A ⊕ A = A и A ⊕ 0 = A. В результате получим либо

либо константу 0.Существование доказано. 2) Докажем единственность представления. Подсчитаем число различных всевозможных монотонных конъюнкций от n переменных. Для этого составим таблицу вида:

где каждой переменной соответствует единица, если она присутствует в монотонной конъюнкции и ноль в противном случае. При этом константе единице поставим в соответствие

нулевой набор. Очевидно, что построенное отображение биективно. Следовательно, всего различных монотонных конъюнкций от n переменных — 2^ n. Построим аналогичное биективное отображение между всевозможными суммами монотонных конъюнкций и векторами

длины 2^ n — числа конъюнкций. Для этого составим таблицу вида:

где под соответствующей монотонной конъюнкцией стоит единица, если она входит в данную сумму, и ноль, если не входит. При этом константе ноль ставится в соответствие нулевой набор. Очевидно, такое отображение биективно. Всего таких различных сумм будет столько, сколько существует различных булевых векторов длины 2^n, то есть — 2^2^n. Мы получили, что число различных полиномов Жегалкина совпадает с числом функций алгебры логики. Поскольку отображение из множества полиномов во множество функций сюръективно, то оно и биективно, так как множества полиномов Жегалкина над n переменными и функций алгебры логики от n переменных равномощны. Единственность доказана.

Вопрос 5: Двойственность. Принцип двойственности. Замкнутость класса самодвойственных функций.

Функцией, двойственной к функции алгебры логики f (x 1, …, xn), назы-

вается функция:

Теорема 9 (принцип двойственности). Пусть

Тогда

Доказательство. Рассмотрим

Функция алгебры логики f (x 1, …, xn) называется самодвойственной, если

f (x 1, …, xn) = f * (x 1, …, xn).

Иначе говоря, S = { f | f = f *}.

Классу S принадлежат функции

Классу S не принадлежат функции

Поскольку

Теорема 10. Класс S замкнут.

Доказательство. Пусть f (X 1, …, Xn) ∈ S, i и

Тогда из принципа двойственности следует, что

Таким образом, мы получили, что Φ = Φ* и

Φ ∈ S. ТД.

Дата добавления: 2015-10-30