13.3. Алгебра Жегалкина

Другая алгебра булевых функций строится на основе операций сложения по модулю 2 и конъюнкции. Она называется алгеброй Жегалкина (АЖ).

Свойства АЖ:

1. Коммутативность xy = yx, xy = yx.

2. Ассоциативность x (yz) = (xy)z, x (y z) = (x y) z.

3. Дистрибутивность умножения относительно сложения x (yz) = x y x z.

4. Свойства констант x 1 = x, x 0 = 0, x0 = x.

Справедливы также соотношения:

= 1x, x₁  x₂ = x₁x₂x₁ x₂, x₁x₂ = x₁    x₂.

Используя эти формулы, можно перейти от АЖ к БА и обратно.

Например.

1) x (  y) = x[(1x)y(1x) y] = x (1xyy  x y) = x (1xx y) = xx xx x y = x y.

2) 1xyx y = (1x)(1y) =   .

Через операции алгебры Жегалкина можно выразить все другие БФ. Пример показан в табл. 13.2.

Таблица 13.2.

x1  x2 =  x2 = 1x1x1 x2

x1 ~ x2 = (  x2)(x1  ) = 1x1x2

x1  x2 = = x1x1 x2

x1 | x2 = = 1x1 x2

x1  x2 = = 1x1x2x1 x2

13.4. Функциональная полнота бф

В алгебре логики из множества  = различных БФ n переменных y = f(x₁, ..., x_n) выделяют пять типов БФ.

1. Функции, сохраняющие константу 0, т.е. такие f(x₁, ..., x_n), что f(0, ..., 0) = 0, их число .

2. Функции, сохраняющие константу 1, т.е. такие f(x₁, ..., x_n), что f(1, ..., 1) = 1, их число равно половине общего числа всех функций n переменных т.е. .

3. Самодвойственные функции, т.е. такие, которые, принимают противоположные значения на любых двух противоположных наборах. Их число .

4. Линейные функции, т.е. такие, которые представляются в алгебре Жегалкина каноническим многочленом, не содержащим произведений переменных a₀ + a₁x₁ + ... + a_nx_n, где коэффициенты a₀, ..., a_n принимают значения 0 или 1. Так как всего коэффициентов n + 1, то число различных линейных функций будет .

5. Монотонные функции, т.е. такие, которые для любых двух наборов из множества значений переменных, частично упорядоченного соотношением (₁, ..., _n)  (₁, ..., _n), при _i  _i (i = 1, 2, ..., n), удовлетворяют неравенству f(₁, ..., _n)  f(₁, ..., _n).

Система функций, суперпозицией которых представляется любая функция из некоторого множества БФ, называется функционально полной. Если в такой системе допускаются константы 0 и 1, то ее называют ослаблено функционально полной. Говорят, что ФПС функций образует базис в логическом пространстве. Система функций называется минимально полным базисом, если удаление из нее любой функции превращает эту систему в неполную.

Теорема о функциональной полноте

Для того, чтобы БФ была полной, необходимо и достаточно, чтобы она включала хотя бы одну функцию: несохраняющую константу 0, несохраняющую константу 1, несамодвойственную, нелинейную, немонотонную.

Теорему понимают так: одна и та же функция может представлять в функционально полной системе (ФПС) одно или несколько требуемых свойств, если она обладает этими свойствами. Таблица характеризует свойства БФ с позиций функциональной полноты (знаком  отмечены свойства, которыми обладает данная функция).

		Свойства
БФ	Формулы	Несо-храня-ющие 0	Несо-храня-ющие 1	Несамо-двойст-венность	Нели-ней-ность	Немо-нотон-ность
Константа 0	0			
Константа 1	1			
Отрицание						
Конъюнкция	x1 x2				
Дизъюнкция	x1  x2				
Импликация	x1  x2					
Эквивалентность	x1 ~ x2					
Отрицание импликации	x1  x2					
Сумма по модулю 2	x1x2					
Штрих Шеффера	x1 | x2					
Стрелка Пирса	x1  x2					

Из таблицы видно, что операции: дизъюнкция и отрицание, конъюнкция и отрицание, штрих Шеффера, стрелка Пирса удовлетворяют теореме о функциональной полноте.

Система операций АЖ (сумма по модулю 2 и конъюнкция) вместе с константой 1 образуют ослабленно - функционально полную систему. Выбрав любую, неэлементарную функцию и дополнив ее одной или несколькими другими функциями так, чтобы они вместе удовлетворяли теореме о функциональной полноте, можно выразить через них все другие БФ.