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

Двойственность. Класс самодвойственных функций.

Лекция 2

Пусть формула А содержит только операции конъюнкции, дизъюнкции и отрицания.

Будем называть операцию конъюнкции двойственной операции дизъюнкции, а операцию дизъюнкции

двойственной операции конъюнкции. Определение. Формулы А и А * называются двойственными, если формула А * получается из формулы А путем замены в ней каждой операции на двойственную.

Например, для формулы А º (х Úy)&z двойственной формулой будет формула А * º (х& у) Ú z .

Теорема. Если формулы А и В равносильны, то равносильны и им двойственные формулы, то есть

А* º В * .

Предварительно докажем лемму.

Лемма. Если для формулы A(x1 ,x2 ....xn) двойственной формулой является А*( x1 ,x2 ....xn), то справедлива равносильность А*(x1, ..., xn) = (1, ..., n).

(Доказательство леммы разбирается студентом самостоятельно см. Лихтарников «МЛ» стр. 28-29)

Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:

x f f*

Функции f(x) = x и g(x) = двойственны сами себе:

x f f* g g*

так как f*(0)=(1).

Определение 1. Если f*(x1, ..., xn) = f(x1, ..., xn), то f(x1, ..., xn) называется самодвойственной.

Множество всех самодвойственных функций обозначается через S.

Если f*– самодвойственна, то (1, ..., n) = f(x1, ..., xn), т.е. на противоположных наборах функция принимает противоположные значения.

Пример 1. Покажем, что функция х1Úх2 двойственна к x1&x2, функция х1х2 двойственна к функции x1|x2.

x1 x2 f=х1Úх2 f* g=x1|x2 g*=x1x2

 

Пример 2. Построить формулу, реализующую f*, если f = ((xy) Ú z) (y(xÅyz)). Покажем, что она эквивалентна формуле N = z(xÅy).

Найдем (xÅy)* и (xy)*.

x y xÅy (xÅy)* x y (xy)*

Из таблиц видно, что

(xy)* = x ~ y = = xy1, xy =yx,

(xy)* =y xy =y.

По принципу двойственности:

f* = yz((x(yz)1)) = yzz(x(yz)1) = z(yÚ(xÅzÅ)) = z(yÚ(xÅzÅ1)) = z(yÚ(xÅ)) = zyÚ(zxÅz) = z(yÚx) = z(xÅy).

Тогда f = (f*)* = [z(xÅy)]* = zÚ(x~y).

Обозначим множество всех функций двузначной алгебры логики Р2. Обозначим через Р2(n) число функций, зависящих от n переменных. Очевидно, Р2(n)=22 n.

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

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

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

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

Примерами неполных систем являются: {}, {0,1}.

 

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

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

Данная лемма может быть использована следующим образом:

1. Покажем, что система {x1Úx2, } – полна в P2.

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

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

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

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.