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

Определение. Система функций {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].

3. Система {x₁Úx₂, } – полна в P₂.

Возьмем в качестве полной в Р₂ системы U={x₁Úx₂, , x₁&x₂}, B={x₁Úx₂, }. Надо показать, что x₁&x₂ представляется формулой над B. Действительно, по правилу Де Моргана получим: x₁&x₂= .

С помощью этой леммы докажем полноту еще ряда систем.

4. Система {x₁&x₂, } – полна в Р₂.

5. Система {x₁|x₂} полна в Р₂. Для доказательства возьмем в качестве полной в Р₂ системы U = {x₁&x₂, } и выразим х₁&х₂ и через х₁|x₂ :

= x₁ | x₁, x₁ & x₂ = = (x₁|x₂)|(x₁|x₂).

6. Система {x₁ x₂} полна в Р₂. U = {x₁Úx₂, }, = x₁ x₁, x₁Úx₂ = = (x₁ x₂) (x₁ x₂).

7. Система {x₁&x₂, x₁Åx₂, 0, 1}, U = {x₁&x₂, }, = x₁Å1.

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

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 получаем свободный член а₀.