Главная | Обратная связь
МегаЛекции

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





Определение. Система функций {f1, f2, ..., fs, ...}ÌP2 называется полной в Р2, если любая функция f(x1, ..., xn) Î P2 может быть записана в виде формулы через функции этой системы.

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

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

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

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

 

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

 

Пусть система U = {f1, f2, ..., fs, ...} полна в Р2. Пусть B = {g1, g2, ..., gk, ...} – некоторая система из Р2, причем любая функция fi Î U может быть выражена формулой над B, тогда система B полна в Р2.

Доказательство. Пусть h(x1, ..., xn) Î P2, т.к. U полна в Р2, то h(x1, ..., xn) = =N[f1, ..., fs, ...] = N[L1[g1, ..., gk], ..., Ls[g1, ..., gk], ...] = U[g1, ..., gk]. Здесь мы воспользовались тем, что для любого i n fi может быть выражена формулой над B, поэтому fi=Li[gi, ..., gk].

3. Система {x1Úx2, } – полна в P2.

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

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

4. Система {x1&x2, } – полна в Р2.

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

= x1 | x1, x1 & x2 = = (x1|x2)|(x1|x2).

6. Система {x1 x2} полна в Р2. U = {x1Úx2, }, = x1 x1, x1Úx2 = = (x1 x2) (x1 x2).

7. Система {x1&x2, x1Åx2, 0, 1}, U = {x1&x2, }, = x1Å1.

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

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

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

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

 

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



 

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

Пример 2. (x1 (x2 x3))(x1 Ú x2) x3 = (x1Ú x2 Ú x3)(x1 Ú x2) x3 = (`x1x2 Ú x1x3 Ú x1x2 Ú x2 Ú x2x3)x3 = (`x1x3 Ú x2)x3 = x1x3 x2 x3 = ((x1x3Å1)x2Å1)x3 = x1x2x3Åx2x3Åx3.

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

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

Пример 3. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f(x1, x2, x3) = (01101001) = а0 Å а1х1Å Å а2х2 Å а3х3 Å b1x1x2 Å b2x2x3 Å b3x1x3 Å cx1x2x3. Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (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 Å b2 = b2 = 0; а1 = 1; 0 = а1 Å а3 Å b3 = b3 = 0; 0 = а1 Å а2 Å b1 = b1 = 0; 1 = 1 Å 1 Å 1 Å c; c = 0; f(x1, x2, x3) = x1 Å x2 Å x3.

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

 

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

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

, 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 переменных равно числу полиномов, то каждой функции будет соответствовать единственный полином.





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:
©2015- 2021 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.