Полнота, примеры полных систем

Определение. Система функций {f₁, f₂, ..., f_s, ...}ÌP₂ называется полной в Р₂, если любая функция f(x₁, ..., x_n) Î P₂ может быть записана в виде формулы через функции этой системы.

Полные системы

1. P₂ – полная система.

2. Система M={x₁&x₂, x₁Úx₂, } – полная система, т.к. любая функция алгебры логики может быть записана в виде формулы через эти функции.

Пример 1. Неполные системы: { }, {0,1}.

Лемма (достаточное условие полноты)

Пусть система U = {f₁, f₂, ..., f_s, ...} полна в Р₂. Пусть B = {g₁, g₂, ..., g_k, ...} – некоторая система из Р₂, причем любая функция f_i Î U может быть выражена формулой над B, тогда система B полна в Р₂.

Доказательство. Пусть h(x₁, ..., x_n) Î P₂, т.к. U полна в Р₂, то h(x₁, ..., x_n) = =N[f₁, ..., f_s, ...] = N[L₁[g₁, ..., g_k], ..., L_s[g₁, ..., g_k], ...] = U[g₁, ..., g_k]. Здесь мы воспользовались тем, что для любого i n f_i может быть выражена формулой над B, поэтому f_i=L_i[g_i, ..., g_k].

Следствие. Полином Жегалкина.

f(x₁, ..., x_n) Î P₂, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как {x₁&x₂, x₁Åx₂, 0, 1} полна в Р₂. В силу свойства x & (yÅz) = xy Å xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х х ...х , соединенных знаком Å. Такой полином называется полиномом Жегалкина.

Общий вид полинома Жегалкина:

где , s = 0, 1, ..., n, причем при s = 0 получаем свободный член а₀.

Представление функции в виде полинома Жегалкина

1. Представим любую функцию формулой над {x₁&x₂, } и сделаем замену =xÅ1. Этот способ удобен, если функция задана формулой.

Пример 2. (x₁ (x₂ x₃))(x₁ Ú x₂) x₃ = (x₁Ú x₂ Ú x₃)(x₁ Ú x₂) x₃ = (`x<sub>1</sub>x<sub>2</sub> Ú x<sub>1</sub>x<sub>3</sub> Ú x<sub>1</sub>x<sub>2</sub> Ú x<sub>2</sub> Ú x<sub>2</sub>x<sub>3</sub>)x<sub>3</sub> = (`x₁x₃ Ú x₂)x₃ = x₁x₃ x₂ x₃ = ((x₁x₃Å1)x₂Å1)x₃ = x₁x₂x₃Åx₂x₃Åx₃.

Надо помнить, что четное число одинаковых слагаемых в сумме по mod2 дает 0.

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

Пример 3. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f(x₁, x₂, x₃) = (01101001) = а₀ Å а₁х₁Å Å а₂х₂ Å а₃х₃ Å b₁x₁x₂ Å b₂x₂x₃ Å b₃x₁x₃ Å cx₁x₂x₃. Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (0, 0, 0) f(0, 0, 0) = 0, с другой стороны, подставив этот набор в полином, получим f(0, 0, 0) = а₀, отсюда а₀ = 0. f(0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим: f(0, 0, 1) = а₀ Å а₃, т.к. а₀ = 0, отсюда а₃ = 1. Аналогично, f(0, 1, 0) = 1 = а₂, f(0, 1, 1) = 0 = а₂ Å а₃ Å b₂ = b₂ = 0; а₁ = 1; 0 = а₁ Å а₃ Å b₃ = b₃ = 0; 0 = а₁ Å а₂ Å b₁ = b₁ = 0; 1 = 1 Å 1 Å 1 Å c; c = 0; f(x₁, x₂, x₃) = x₁ Å x₂ Å x₃.

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

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

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

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