Определение: Арифметические функции в алгебре логики есть сложение и умножение по модулю 2.

Следующие свойства математических операций проверяются непосредственно.
1) x+(y+z) = (x+y)+z
2) x+y=y+x
3) x+0=x
4) x+(-x) = 0
5) x(yz) = (xy)z
6) xy = yx
7) x*1 =x
8) x*x^-1 =1, x≠0
9) x(y+z) = xy+xz
10) x+x=0
11) x*x =x (идемпотентность)

Замечание: Двухэлементное множество {0,1} с определенными на нем операциями сложения и умножения по mod 2 образуют поле F.

Замечание: Поле F (по свойству 10) имеет характеристику 2, а операция умножения идемпотентна. Следующие 4 равенства устанавливают связь между арифметическими и логическими операциями.

1) ¬x=x+1
2) x&y = x*y
3) x*y = ¬(¬x&¬y) = (x+1)(y+1)+1 = xy+x+y +1+1 = xy+x+y
4) x+y = ¬xy∨x¬y (СДНФ)

Теорема: Класс линейных функций замкнут относительно суперпозиции.

Доказательство: Пусть линейная функция f(x₁, x₂,…,x_n) = a₁x₁ + a₂x₂+…+a_nx_n+a_n+1, а также функции
g_i(x₁, x₂,…,x_m) = b_i1x₁ + b_i2x₂+…+b_inx_n+b_im+1, i=1,2,..n
Тогда их суперпозиции:
f(g₁, g₂, …, g_n)=a₁(b₁₁x₁+b₁₂x₂+…+b_1mx_m+b_1m+1x_m,)+a₂(b₂₁x₁+b₂₂x₂+…+b_2mx_m+b_2m+1)+
…+a_n(b_n1x₁+b_n2x₂+…+b_nmx_m+b_nm+1)+a_n+1 =
={сгрупируем по столбцам } =
= (b₁₁a₁+b₁₂a₂+…+b_n1a_n)x₁+(b₁₂a₁+b₂₂a₂+…+b_n2a_n)x₂ +…+(b_1ma₁+b_2ma₂+…+b_nma_n)x_m+
+(b_1m+1a₁+…+b_nm+1a_n)+a_n+1 = c₁x₁ + …+ c_mx_m + c_m+1 — линейная функция.

Комментарии запрещены.