Полнота и базис в булевой алгебре.

Система F:={ ,..., } называется полной в , если любая функция f Î  представима в виде суперпозиции функций этой системы.

Функция (,..., ) называется суперпозицией функций (,..., ) и (,..., ),..., (,..., ), если

(,..., )= ( (,..., ),..., (,..., )).

Определим предварительно 5 классов булевых функций (классов Поста).

1. Классом  булевых функций (,..., ), сохраняющих константу 0, называется множество: :={ (,..., )| (0,...,0)=0}.

2. Классом  булевых функций (,..., ), сохраняющих константу 1, называется множество: :={ (,..., )| (1,...,1)=1}.

3. Классом L линейных булевых функций (,..., ) называется множество:

L:={ (,..., )| (,..., )= Å Å Å...Å }

где , Î{0,1}, i = .

Коэффициенты , ,..,  линейной функции  определяются из следующих соотношений:

= (0,...,0)=0, = Å (1,0,...,0),..., = Å (0,...,0,1).

Проверка линейности сводится к нахождению коэффициентов  и сопоставлению таблиц истинности данной формулы (,..., ) и полученной формулы Å Å Å...Å .

 

Пример 1. Проверим, является ли линейной функция Ú .

Имеем = 0 Ú 0 = 0, = 0 Å (1 Ú 0) = 1, = 0 Å (0 Ú 1) = 1. Таким образом, Å Å = . Сопоставляя таблицы истинности формул  и , убеждаемся, что они не совпадают, следовательно, функция  нелинейна.

Линейность булевой функции определить и другим способом – с помощью полинома Жегалкина 1–й степени от n переменных:

(,..., ) = Å

Полином Жегалкина называется нелинейным (линейным), если он содержит (не содержит) произведения переменных, т.е. линейность булевой функции равносильна линейности соответствующего полинома Жегалкина.

Для получения полинома Жегалкина булевой функции используются аксиомы булевой алгебры и вспомогательные равенства:

x Ú y = x Å y Å xy, x (y Å z)= xy Å xz, = x Å 1, x Å 0= x, x Å =1, x =0

Пример 2. Определить, будет ли линейной функция:

f (x, y, z)= .

Имеем (x, y, z)=( )Ú = = = = () = ×1 =(x Å 1) z Å x (y Å 1)(z Å 1) = xz Å 1× z Å xyz Å xz Å xy Å x = x Å z Å xy Å xyz.

Полученный полином Жегалкина является нелинейным, и, следовательно, функция f также нелинейна.

4. Классом S самодвойственных булевых функций (,..., ) называется множество:

S:={ (,..., )| (,..., )= (,..., )}.

5. Классом M монотонных булевых функций (,..., ) называется множество:

:={ (,..., )|(,..., )³(,..., )Û( ³ , i = )® (,..., )³ (,..., )}.

 

Пример 3. Определим, к каким классам Поста относится булева функция (x, y)= x | y.

1. f (0,0)=1, т.е. f (x, y)Ï .

2. f (1,1)=0, т.е. f (x, y)Ï .

3. f (1,0)¹ f (0,1), т.е. f (x, y)Ï S.

4. f (0,0)> f (1,1), т.е. f (x, y)Ï M.

5. f (x, y)=1Å xy, т.е. f (x, y)Ï L.

 

Отметим, что каждый класс Поста замкнут относительно операций замены переменных и суперпозиций, т.е. с помощью этих операций из функций, принадлежащих данному классу, можно получить только функции из этого же класса.

Для установления полноты системы S:={ ,..., } булевых функций используют критерий полноты Поста–Яблонского:

Система F:={ ,..., } булевых функций тогда и только тогда является полной, когда для каждой из пяти классов , , S, M, L в системе F найдется функция , не принадлежащая этому классу.

В силу критерия полноты функция f (x, y) x | y образует полную систему, т.е. с помощью функции Шеффера (x | y) можно получить любую функцию. В частности, x | x, x & y (x | y)| (x | y).

Система булевых функций F:={ ,..., } называется базисом, если она полна, а для любой функции Î S система F \{ } – неполна.

Примеры всех 17 базисов в , в каждом из которых нельзя вычеркнуть ни одну функцию без потери полноты в .

{○},{|},{®,~},{®,○},{®,®},{®,Å},{®,Ø},{®,Ø},{&,Ø},{Ú,Ø}, {®,1},{~,&,0},{~,Ú,0},{Å,&,~},{Å,Ú,~},{Å,&,1},{Å,Ú,1}.

Наиболее хорошо изученным является базис {&,Ú,Ø}.

 

Теорема 1.4.1. Каждый базис содержит не более четырех булевых функций.

Для доказательства функциональной полноты предъявленной системы F:={ ,..., } достаточно показать, что через функции Î F можно выразить все функции из базиса {&,Ú,Ø}. Справедливо и более общее утверждение.

Теорема 1.4.2. Если все функции функционально полной системы å* представимы формулами над å, то å также функционально полна.

 

Пример 4. В алгебре Жегалкина (;å={&,Å,1}) определить, является ли сигнатура å функционально полной системой.

 

Чтобы выяснить функциональную полноту системы å={&,Å,1}, достаточно показать, что через операции å можно выразить операции булевого базиса å*={&,Ú,Ø}:

1) = ,

2) = ×

Построенные таблицы истинности (табл. 1.4.1 и 1.4.2) подтверждают справедливость формул 1) и 2).

 

Таблица 1.4.1