Вопрос по таблице истинности и линейной функции

Ну, вы знаете, что такое линейность в алгебраическом смысле. Это представимость функции в виде

F = C0 + C1·X1 + C2·X2 + … + Cn·Xn,
где Ci – постоянные коэффициенты.

В булевой алгебре то же самое, только вместо суммы берётся операция «Исключающее ИЛИ» , вместо произведения — операция «И» , а коэффициенты Ci могут, естественно, принимать только значения 0 или 1:

F = C0 # C1*X1 # C2*X2 # … # Cn*Xn.

Самый простой известный мне способ проверить линейность функции – это выразить её в виде полинома Жегалкина, т. е. используя только операции «Исключающее ИЛИ» , «И» и только неинверсные переменные и (при необходимости) константу 1.

Для этого можно представить функцию в виде ДНФ, а потом преобразовать с использованием следующих правил:

A + B = A # B # A*B
~A = 1 # A
A # A = 0
A # ~A = 1
От перестановки мест слагаемых/сомножителей сумма не меняется.
Скобки раскрываются как в обычной алгебре.

Порядок выполнения операций: сначала НЕ, потом И, потом исключающее ИЛИ.

Например, для функции F1 в последней табличке:

1) Строим ДНФ: F1 = X*~Y + ~X*Y

2) Преобразуем

F1 =( X*~Y) # ( ~X*Y) # (X*~Y*~X*Y)

Последняя скобка равна 0, т. к. X*~X=0, поэтому

F1 =( X*~Y) # ( ~X*Y)

Преобразуем далее

F1 = X*(1 # Y) # (1 # X)*Y

F1 = X # X*Y # Y # X*Y

Т. к. X*Y # X*Y = 0, окончательно получим:

F1 = X # Y

Резюме: функция F1 линейна.