 |
Полнота, примеры полных систем
|
|
|
|
Определение. Система функций { f 1, f 2,..., f s,...}Ì P 2 называется полной в Р 2, если любая функция f (x 1,..., xn) Î P 2 может быть записана в виде формулы через функции этой системы.
Полные системы
1. P 2 – полная система.
2. Система M ={ x 1& x 2, x 1Ú x 2, 
} – полная система, т.к. любая функция алгебры логики может быть записана в виде формулы через эти функции.
Пример 1. Неполные системы: { 
}, {0,1}.
Лемма (достаточное условие полноты)
Пусть система 
U = { f 1, f 2,..., fs,...} полна в Р 2. Пусть B = { g 1, g 2,..., gk,...} – некоторая система из Р 2, причем любая функция fi Î U может быть выражена формулой над B, тогда система B полна в Р 2.
Доказательство. Пусть h ( x 1,..., xn ) Î P 2, т.к. U полна в Р 2, то h ( x 1,..., xn ) = = N [ f 1,..., fs ,...] = N [ L 1[ g 1,..., gk ],..., Ls [ g 1,..., gk ],...] = U [ g 1,..., gk ]. Здесь мы воспользовались тем, что для любого i 
n fi может быть выражена формулой над B, поэтому fi = Li [ gi ,..., gk ].
3. Система { x 1Ú x 2, } – полна в P 2.
Возьмем в качестве полной в Р 2 системы U ={ x 1Ú x 2, , x 1& x 2}, B ={ x 1Ú x 2, }. Надо показать, что x 1& x 2 представляется формулой над B. Действительно, по правилу Де Моргана получим: x 1& x 2= 
.
С помощью этой леммы докажем полноту еще ряда систем.
4. Система { x 1& x 2, } – полна в Р 2. 
5. Система { x 1| x 2} полна в Р 2. Для доказательства возьмем в качестве полной в Р 2 системы U = { x 1& x 2, } и выразим х 1& х 2 и 
через х 1| x 2 :
= x 1 | x 1, x 1 & x 2 = 
= (x 1| x 2)|(x 1| x 2).
6. Система { x 1 
x 2} полна в Р 2. U = { x 1Ú x 2, 
}, = x 1 x 1, x 1Ú x 2 = 
= (x 1 x 2) (x 1 x 2).
7. Система { x 1& x 2, x 1Å x 2, 0, 1}, U = { x 1& x 2, }, = x 1Å1.
Следствие. Полином Жегалкина.
f (x 1,..., xn) Î P 2, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как { x 1& x 2, x 1Å x 2, 0, 1} полна в Р 2. В силу свойства x & (y Å z) = xy Å xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х 
х 
... х 
, соединенных знаком Å. Такой полином называется полиномом Жегалкина.
|
|
|
Общий вид полинома Жегалкина:
где 
, s = 0, 1,..., n, причем при s = 0 получаем свободный член а 0.
Представление функции в виде полинома Жегалкина
1. Представим любую функцию формулой над { x 1& x 2, 
} и сделаем замену 
= x Å1. Этот способ удобен, если функция задана формулой.
Пример 2. (x 1 
(x 2 x 3))(x 1 Ú x 2) x 3 = (x 1Ú x 2 Ú x 3)(x 1 Ú x 2) x 3 = (` x 1 x 2 Ú x 1 x 3 Ú x 1 x 2 Ú x 2 Ú x 2 x 3) x 3 = (` x 1 x 3 Ú x 2) x 3 = x 1 x 3 x 2 x 3 = ((x 1 x 3Å1) x 2Å1) x 3 = x 1 x 2 x 3Å x 2 x 3Å x 3.
Надо помнить, что четное число одинаковых слагаемых в сумме по mod 2 дает 0.
2. Метод неопределенных коэффициентов. Он удобен, если функция задана таблицей.
Пример 3. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f (x 1, x 2, x 3) = (01101001) = а 0 Å а 1 х 1Å Å а 2 х 2 Å а 3 х 3 Å b 1 x 1 x 2 Å b 2 x 2 x 3 Å b 3 x 1 x 3 Å cx 1 x 2 x 3. Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (0, 0, 0) f (0, 0, 0) = 0, с другой стороны, подставив этот набор в полином, получим f (0, 0, 0) = а 0, отсюда а 0 = 0. f (0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим: f (0, 0, 1) = а 0 Å а 3, т.к. а 0 = 0, отсюда а 3 = 1. Аналогично, f (0, 1, 0) = 1 = а 2, f(0, 1, 1) = 0 = а 2 Å а 3 Å b 2 = b 2 = 0; а 1 = 1; 0 = а 1 Å а 3 Å b 3 = b 3 = 0; 0 = а 1 Å а 2 Å b 1 = b 1 = 0; 1 = 1 Å 1 Å 1 Å c; c = 0; f (x 1, x 2, x 3) = x 1 Å x 2 Å x 3.
Теорема Жегалкина
Каждая функция из 
может быть представлена в виде полинома Жегалкина единственным образом.
Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:
, s = 0, 1,..., n. Доказательство. Любая функция из Р 2 может быть представлена формулой над { x 1 & x 2, x 1Å x 2, 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функции f (x 1,..., xn) от n переменных. Мы знаем, что всего таких функций, т.е. их таблиц истинности, 2 n. Подсчитаем число различных полиномов Жегалкина от n переменных, т.е. число вариаций вида: 
. Число наборов 
равно числу всех подмножеств множества { x 1,..., xn }, сюда входит и пустое множество (если s = 0). Число подмножеств множества из n элементов равно 2 n, а так как каждый набор входит с коэффициентом 
, принимающим два значения: 0 или 1, то число всевозможных полиномов будет 
. Так как каждому полиному соответствует единственная функция, число функций от n переменных равно числу полиномов, то каждой функции будет соответствовать единственный полином.
|
|
|
|
|
|
