• Алгебра Жегалкина. Полином Жегалкина.

Определение алгебры Жегалкина
Для записи формул алгебры Жегалкина используются следующие знаки и правила их применения:

• 0 - тождественный ноль, детектор 0;
• 1 - тождественная единица, тавтология;
• ^ - бинарная операция конъюнкция;
• ⊕ - бинарная операция сумма по модулю 2 (неравнозначность, исключающее ИЛИ);
• символы– строчные или прописные буквы;
• скобки, разделители и другие знаки, смысл которых будет разъясняться по мере применения.

Знаки 0, 1 (нульарные операции) – не используют более других знаков. Знак инверсии (унарная операция) ставится впереди переменной, знаки конъюнкции и дизъюнкции (бинарные операции) ставятся между переменными. Символы используются для обозначения переменных.
В отличие от алгебры Буля, в алгебре Жегалкина вместо дизъюнкции в качестве базовой операции выбрана операция сложение по модулю 2. В алгебре Жегалкина конъюнкция также является старшей операцией по отношению к операции сложение по модулю 2.
Напомним таблицы истинности, определяющие конъюнкцию, сложение по модулю 2:

 

Свойства суммы по модулю 2:

• Коммутативность:

A⊕B=B⊕A
A ⊕ B ⊕ C = C ⊕ A ⊕ B = B ⊕ C ⊕ A =
B ⊕ A ⊕ C = C ⊕ B ⊕ A = A ⊕ C ⊕ B =

• Ассоциативность:

(A ⊕ B) ⊕ C = A⊕ (B ⊕ C),
(A ⊕ B) ⊕ (C ⊕ D) = A ⊕ B ⊕ C ⊕ D = B ⊕ A ⊕ C ⊕ D

• Дистрибутивность конъюнкции относительно суммы по модулю два:

A*(B ⊕ C) =A*B⊕A*C.

• Сумма по модулю два относительно конъюнкции не дистрибутивна, т. е.:

A ⊕ (B*C) ≠ (A ⊕ B)*(A ⊕ C)
(A*B) ⊕ C ≠ (A ⊕ C)*(A ⊕ B)

• Другие свойства:

A ⊕ A = 0
A ⊕ 0 = A
A ⊕ 1 = ⌐A
1 ⊕ 1 = 0
0 ⊕ 0 = 0
0 ⊕ 1 = 1
Вычислим, например, значение выражения
1⊕0*1⊕1*1=1⊕0⊕1=1⊕1=0.

Полином Жегалкина — полином с коэффициентами вида 0 и 1, в котором конъюнкция используется как произведение, сумма по модулю 2 используется как  сложение. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).
Полином Жегалкина имеет вид:

H(x1,x2,…, xn)=C0 ⊕ C1 x1 ⊕C2 x2⊕ Cn xn⊕ C12 x1 x2⊕ C13 x1 x3⊕…⊕ C1…n x1…xn,

где C0, C1, …, C1…n – коэффициенты при переменных 1, x1, x2,…xn, x1x2,…, x1…xn соответственно.
Теорема. Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.
Доказательство. Любая функция f(x1, x2, …, xn) имеет свою таблицу истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент. Так как число наборов равно числу коэффициентов (и равно 2п), отсюда следует утверждение теоремы.
Доказательство этой теоремы показывает, как по таблице истинности построить полином Жегалкина.
Для булевых функций двух переменных полином Жегалкина имеет вид:

H(x₁,x₂) = C₀ ⊕ C₁ x₁ ⊕C₂ x₂⊕ C₁₂ x₁ x₂

Определим булевы функции двух переменных через операции алгебры Жегалкина (т. е. через конъюнкцию и сумму по модулю 2).
Предварительно дадим решение простейших уравнений, вытекающих из определения суммы по модулю 2:
Если a ⊕ 1 = 1, то a = 0
Если a ⊕ 0 = 1, то a = 1
Если a ⊕ 1 = 0, то a = 1
Если a ⊕ 0 = 0, то a = 0.
Функция f0(x1,x2)={0,0,0,0} есть тождественный ноль.
Функция f1(x1,x2)={0,0,0,1} есть конъюнкция.
Для функции f2(x1,x2)={0,0,1,0} определим значения коэффициентов полинома Жегалкина:
f2(0,0) = C0=0
f2(0,1) = C0⊕ C2=0
f2(1,0) = C0⊕ C1=1
f2(1,1) = C0⊕ C1⊕ C2⊕ C12=0

Имеем:
C0=0
0⊕ C2=0; C2⊕ 0=0; C2=0
0⊕ C1=1; C1 ⊕ 0=1; C1=1
0⊕ 1⊕ 0⊕ C12=0; C12⊕1 =0; C12=1
Искомый полином Жегалкина имеет вид:
H(x1,x2) = x1⊕ x1 x2

Для функции f3(x1,x2)={0,0,1,1} определим значения коэффициентов полинома Жегалкина:
f2(0,0) = C0=0
f2(0,1) = C0⊕ C2=1
f2(1,0) = C0⊕ C1=0
f2(1,1) = C0⊕ C1⊕ C2⊕ C12=1

C0=0
0⊕ C2=0; C2⊕ 0=0; C2=0
0⊕ C1=1; C1 ⊕ 0=1; C1=1
0⊕ 1⊕ 0⊕ C12=1; C12⊕1 =1; C12=0
Искомый полином Жегалкина имеет вид:
H(x1,x2) = x1
Для функции f4(x1,x2)={0,1,0,0} определим значения коэффициентов полинома Жегалкина:
f2(0,0) = C0=0
f2(0,1) = C0⊕ C2=1
f2(1,0) = C0⊕ C1=0
f2(1,1) = C0⊕ C1⊕ C2⊕ C12=0
Имеем:
C0=0
0⊕ C2=1; C2 ⊕ 0=1; C2=1
0⊕ C1=0; C1⊕ 0=0; C1=0
0⊕ 0⊕ 1⊕ C12=0; C12⊕1 =0; C12=1
Искомый полином Жегалкина имеет вид:
H(x1,x2) = x2⊕ x1 x2

H2(x1,x2)=x1^⌐x2=( x1⊕x2)=

 

Метод треугольника
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:

• Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000...00 до 111...11.
• Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
• Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
• Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
• Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т.д.
• Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций. Достоинством метода является то, что при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.

Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных P(A,B,C) показан на рисунке.

					000	001	010	011	100	101	110	111
A	B	C	F		1	C	B	BC	A	AC	AB	ABC
0	0	0	1		1	1	0	0	0	0	1	0
0	0	1	0		0	1	0	0	0	1	1
0	1	0	1		1	1	0	0	1	0
0	1	1	0		0	1	0	1	1
1	0	0	1		1	1	1	0
1	0	1	0		0	0	1
1	1	0	0		0	1
1	1	1	1		1

Искомый полином Жегалкина имеет вид:
H(A,B,C)=1⊕C⊕AB.

>